Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Axiom of Choice

  1. Jul 21, 2008 #1
    Can someone give me a list of problems which at first sight require the axiom of choice, but do not?
  2. jcsd
  3. Jul 23, 2008 #2
    Here are two problems.
    One will fit on your list, the other won't.

    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.
  4. Jul 23, 2008 #3
    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.
  5. Jul 23, 2008 #4
    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?
  6. Jul 23, 2008 #5


    User Avatar

    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.

    Last edited by a moderator: Apr 23, 2017
  7. Jul 23, 2008 #6
    Nope, since you can define h:T->S by [itex]h(t)=f^{-1}(t)[/itex] if [itex]t\in f(S)[/itex] and [/itex]h(t)=g(t)[/itex] otherwise.
  8. Jul 24, 2008 #7
    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'.
  9. Jul 24, 2008 #8
    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
  10. Jul 24, 2008 #9
    If I understand you correctly, we now have injections, and you ask for a bijection?

    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?
  11. Jul 24, 2008 #10


    User Avatar
    Science Advisor
    Homework Helper

    There exists a subset of [itex]\mathbb{R}[/itex] which is not Lebesgue measurable.
  12. Jul 24, 2008 #11

    Yes, and the result for surjections does (I believe) need the axiom of choice. This is why I included it.
  13. Jul 24, 2008 #12
    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?
  14. Jul 24, 2008 #13
    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.
  15. Jul 24, 2008 #14


    User Avatar

    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.
  16. Jul 24, 2008 #15
  17. Jul 24, 2008 #16


    User Avatar
    Science Advisor
    Homework Helper

    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.
  18. Jul 25, 2008 #17


    User Avatar

    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).
  19. Jul 25, 2008 #18


    User Avatar

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Axiom of Choice
  1. The Axiom of Choice (Replies: 9)

  2. Axiom of choice (Replies: 3)

  3. The Axiom of Choice? (Replies: 11)

  4. The Axiom of Choice (Replies: 8)