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 to prove two propositions

  1. Dec 5, 2009 #1
    Hi everyone,

    we recently covered some implications of the AC and are now to prove the followings statements with the help of the AC or one of its equivalent:

    (1) Every uncountable set has a subset of cardinality [tex]\aleph_1[/tex] (the least initial ordinal not less or equal than [tex]\aleph_0[/tex], the latter being the cardinality of the set of natural numbers, i.e. [tex]N[/tex] itself)

    (2) If B is an infinite set and A is a subset of B such that |A| < |B|, then |B - A| = |B|

    I have mostly thought about (1) and to fix f as a choice function for such an uncountable set; then the image of this set under f is an element of it, of cardinality less or equal than that of the uncountable one (call it A).

    (well I just realized that it is possible to edit the post so I'll be back with my full post in the proper form with my main attempts on (1) )
    Last edited: Dec 6, 2009
  2. jcsd
  3. Dec 6, 2009 #2
    Are you allowed to use the fact that AC is equivalent to the well-ordering theorem (every set can be well-ordered, i.e. is in bijection with some ordinal)? If so, (1) becomes downright trivial.

    How difficult (2) is depends on what assumptions you're allowed to use - you're essentially asked to prove that the sum of two cardinals is their maximum. The proof that I'm familiar with proceeds by first demonstrating that the product of two cardinals is their maximum. A maximo-lexicographical ordering will prove useful.
    Last edited: Dec 6, 2009
  4. Dec 6, 2009 #3
    Hi and thanks for taking a look at my question. Yes indeed I may use the AC or any of its equivalent including the Well-OP; I figured out (1) btw with its application.

    I am going to try and think about the way you suggested for (2) which I know requires the AC. I will keep you updated on my progresses.

    Edit 1: OK first of all we have shown in class that the product of two cardinals is their maximum, so I can readily use this fact to keep going.

    Edit 2: I am basically allowed to use any theorem that follows more or less readily from the AC as we have covered in class most of its equivalent (Zorn's Lemma, Parliamentary axiom, WellOP etc.) You suggest a use of maximo-lexicographic ordering, may you explain a little bit more? I.e. how this could be useful and at what stage this should be used.
    Last edited: Dec 6, 2009
  5. Dec 8, 2009 #4


    User Avatar
    Science Advisor

    Ok, so you probably also know [tex]|B|+|A|=\max(|B|,|A|)=|B|[/tex].

    It's obvious (inclusion is injection) that [tex]|B-A|\leq|B|[/tex]. Also, we have [tex]|B|\leq|(B-A)+A|[/tex], i.e. [tex]|B|+|A|\leq |B-A|+|A|[/tex], so [tex]|B|\leq|B-A|[/tex].
    With Schroder-Bernstein we get [tex]|B|=|B-A|[/tex].
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook