1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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 wikipedia, about a result of Banach & Tarski which they believed required the axiom of choice.

  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

Have something to add?

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)