# Axiom of Choice

1. Jul 21, 2008

### Dragonfall

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

2. Jul 23, 2008

### fopc

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.

3. Jul 23, 2008

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

4. Jul 23, 2008

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

5. Jul 23, 2008

### gel

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

6. Jul 23, 2008

### Dragonfall

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.

7. Jul 24, 2008

### n_bourbaki

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'.

8. Jul 24, 2008

### fopc

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.

Last edited: Jul 24, 2008
9. Jul 24, 2008

### fopc

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?

10. Jul 24, 2008

### morphism

There exists a subset of $\mathbb{R}$ which is not Lebesgue measurable.

11. Jul 24, 2008

### n_bourbaki

Yes.

Yes, and the result for surjections does (I believe) need the axiom of choice. This is why I included it.

12. Jul 24, 2008

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

13. Jul 24, 2008

### Dragonfall

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.

14. Jul 24, 2008

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

15. Jul 24, 2008

### n_bourbaki

16. Jul 24, 2008

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

17. Jul 25, 2008

### gel

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).

18. Jul 25, 2008