Axiom of Choice: Unveiling the Mystery Behind Unsolvable Problems

[Dragonfall]

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

 

[fopc]

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.

 

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

 

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

 

[gel]

I think this is quite interesting, from http://en.wikipedia.org/wiki/Banach-Tarski_paradox#The_von_Neumann_paradox_in_the_Euclidean_plane", 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.

 

[Dragonfall]

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.

 

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

 

[fopc]

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.

 

[fopc]

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?

 

[morphism]

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

 

[n_bourbaki]

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.

 

[n_bourbaki]

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?

 

[Dragonfall]

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.

 

[gel]

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.

 

[n_bourbaki]

Here is the Conway paper I was thinking of.

http://citeseer.ist.psu.edu/cache/papers/cs/26688/http:zSzzSzmath.dartmouth.eduzSz~doylezSzdocszSzthreezSzthree.pdf/division-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'.

 

[morphism]

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.

 

[gel]

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

 

[gel]

Here is the Conway paper I was thinking of.

http://citeseer.ist.psu.edu/cache/papers/cs/26688/http:zSzzSzmath.dartmouth.eduzSz~doylezSzdocszSzthreezSzthree.pdf/division-by-three.pdf

I had a read though that. It's very interesting and quite an easy read. Looks useless, but interesting nonetheless.