## 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