Physics Forums

Thread Closed

Page 1 of 2   1   2  >

## Axiom of Choice

Can someone give me a list of problems which at first sight require the axiom of choice, but do not?

PhysOrg.com  science news on PhysOrg.com  >> Front-row seats to climate change>> Attacking MRSA with metals from antibacterial clays>> New formula invented for microscope viewing, substitutes for federally controlled drug

Quote by Dragonfall 					 				 				Can someone give me a list of problems which at first sight require the axiom of choice, but do not?
Here are two problems.
One will fit on your list, the other won't.

Preliminaries:
R denotes set of real numbers
N denotes set of natural numbers

1) f:R->N arbitrary surjection.
Show there exists an injection g:N->R s.t. f(g(b)) = b for every b in N.

2) f:R->R arbitrary surjection, continuous and non-decreasing.
Show there exists an injection g:R->R s.t. f(g(b)) = b for every b in R.

Well for 2, since continuous functions map compact sets to compact sets, and the intervals where f is constant are compact, g(x) can be defined as the minimal element of f inverse of x.  1 is not possible without AC.

## Axiom of Choice

Here's one where 'experience' may tell you to use the axiom of choice.

Suppose that S and T are infinite sets. Let f:S-->T be a surjection, and let g:T-->S be another surjection. Write down a bijection between S and T.

That requires the axiom of choice. Now change the word surjection to injection. Does the proof require AC, now?

I think this is quite interesting, from wikipedia, about a result of Banach & Tarski which they believed required the axiom of choice.

Vitali's and Hausdorff's constructions depend on Zermelo's axiom of choice ("AC"), which is also crucial to the Banach–Tarski paper, both for proving their paradox and for the proof of another result: Two Euclidean polygons, one of which strictly contains the other, are not equidecomposable. They remark: Le rôle que joue cet axiome dans nos raisonnements nous semble mériter l'attention (The role this axiom plays in our reasoning seems, to us, to deserve attention) and point out that while the second result fully agrees with our geometric intuition, its proof uses AC in even more substantial way than the proof of the paradox. Thus Banach and Tarski imply that AC should not be rejected simply because it produces a paradoxical decomposition. Indeed, such an argument would also reject some geometrically intuitive statements! Ironically, in 1949 A.P.Morse showed that the statement about Euclidean polygons can be proved in ZF set theory and thus does not require the axiom of choice.

Quote by n_bourbaki 					 				 				Now change the word surjection to injection. Does the proof require AC, now?
Nope, since you can define h:T->S by $h(t)=f^{-1}(t)$ if $t\in f(S)$ and [/itex]h(t)=g(t)[/itex] otherwise.

1) f is invertible is it?  2) How do you know that h is an injection? In fact your h *cannot* be an injection, unless f is already a bijection (but you assumed that by writing down it's inverse). If we assume that you're taking a one sided inverse, then the map from h from f(S) to S is surjective, thus if there is any element in t in T\f(S), then necessarily g(t)=h(t') for some t' in f(S).  You certainly don't need the axiom of choice, though not for the reasons you wrote. I thought you might like an example of two superficially similar statements one using and one not using the axiom of choice.  I seem to recall Conway having a similar thing for 'dividing a set into 3'.

Quote by Dragonfall 					 				 				Well for 2, since continuous functions map compact sets to compact sets, and the intervals where f is constant are compact, g(x) can be defined as the minimal element of f inverse of x.  1 is not possible without AC.
If by "the minimal element of f inverse of x" you mean "the min of the pre-image of the unit set {x} under f", then OK.
Of course, I don't what else you could have possibly meant.

"1 is not possible without AC." Fine. Can't say I'd disagree with you. With a slight generalization it can be shown to be
equivalent to AC.

Quote by n_bourbaki 					 				 				Here's one where 'experience' may tell you to use the axiom of choice.   Suppose that S and T are infinite sets. Let f:S-->T be a surjection, and let g:T-->S be another surjection. Write down a bijection between S and T.   That requires the axiom of choice. Now change the word surjection to injection. Does the proof require AC, now?
If I understand you correctly, we now have injections, and you ask for a bijection?

Schroder-Bernstein.
The classical proof of this theorem is a constructive-existence proof (no AC).
But contrary to what was suggested in another post, the construction of the bijection is non-trivial (my opinion).

Here's one you might think about:

f:A->B arbitrary injection (A,B arbitrary sets).
Show there exists a surjection g:B->A s.t. g(f(a)) = a for every a in A.

Can we get by without AC?

Recognitions:      Homework  Help     Science  Advisor  There exists a subset of $\mathbb{R}$ which is not Lebesgue measurable.

Quote by fopc 					 				 				If I understand you correctly, we now have injections, and you ask for a bijection?
Yes.

Schroder-Bernstein.  The classical proof of this theorem is a constructive-existence proof (no AC).
Yes, and the result for surjections does (I believe) need the axiom of choice. This is why I included it.

Quote by morphism 					 				 				There exists a subset of $\mathbb{R}$ which is not Lebesgue measurable.
I always thought that did require the axiom of choice, something to do with viewing R as a vector space over Q? What's the non AC method?

Quote by fopc 					 				 				Schroder-Bernstein
Ah yes, now I remember. Back when I took set theory I wrote that "if there are injections from S to T and from T to S, then S and T are in bijection" is "obvious" in an exercise. I lost many, many points.

Quote by n_bourbaki 					 				 				I always thought that did require the axiom of choice, something to do with viewing R as a vector space over Q? What's the non AC method?
Actually, that does require the Axiom of Choice (or something similar). Maybe he meant that there exists a subset of R which is not Borel measurable. That doesn't require AC.

Here is the Conway paper I was thinking of.  http://citeseer.ist.psu.edu/cache/pa...n-by-three.pdf  it also gives a discussion of what is entailed in avoiding AC, and why one might wish to do it without just going 'ugh, it's false'.

Recognitions:
Homework Help
Science Advisor

Quote by gel 					 				 				Actually, that does require the Axiom of Choice (or something similar). Maybe he meant that there exists a subset of R which is not Borel measurable. That doesn't require AC.
No, I meant Lebesgue measurable. Apparently all you need to construct such a set is the Hahn-Banach theorem (which is strictly weaker than choice); see this paper by Foreman and Wehrung.

Quote by morphism 					 				 				No, I meant Lebesgue measurable. Apparently all you need to construct such a set is the Hahn-Banach theorem (which is strictly weaker than choice); see this paper by Foreman and Wehrung.
ok, well that shows that it isn't equivalent to AC, but I assumed that the OP wanted things that can be proved using standard ZF axioms. Otherwise you could just say the Hahn-Banach theorem doesn't require AC as another example.

In the wikipedia link I posted above, it mentions that the "ultrafilter lemma" is enough to prove the Banach-Tarski paradoxical decomposition, which would also give non Lebesgue measurable sets (which I why I added the disclaimer ...or something similar... to my prev post).

Thread Closed

Page 1 of 2   1   2  >

Thread Tools

|                                      |                                            |         |
|--------------------------------------|--------------------------------------------|---------|
| Similar Threads for: Axiom of Choice |                                            |         |
| Thread                               | Forum                                      | Replies |
|                                      | General Math                               | 9       |
|                                      | Set Theory, Logic, Probability, Statistics | 2       |
|                                      | Set Theory, Logic, Probability, Statistics | 3       |
|                                      | General Math                               | 9       |
|                                      | Set Theory, Logic, Probability, Statistics | 9       |
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 4, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9311724305152893, "perplexity_flag": "middle"}