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

Is there a way to prove Axiom of Choice I from Axiom of Choice II?

  1. Mar 1, 2013 #1
    I am learning interesting topics in set theory class. I believe that there is a straight proof of Axiom of Choice II by Axiom of Choice I.

    If you don't know the axioms, see below:

    Axiom of Choice I states that for any relation R, there is a function [itex]F\subseteq R[/itex] with [itex]dom(F) = dom(R)[/itex].

    Axiom of Choice II states that the Cartesian product of nonempty sets is always nonempty. That is, if H is a function with domain I and if [itex](\forall i \in I)H(i)\neq ∅[/itex], then there is a function f with domain I such that [itex](\forall i \in I)f(i) \subseteq H(i)[/itex].

    The question is: Is there a way to prove Axiom of Choice I from Axiom of Choice II?
  2. jcsd
  3. Mar 2, 2013 #2

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper

    iirc: these are axioms in the same order - so "no".
    axioms are statements taken to be true in order to draw conclusions from them.
    if II could be proven from I then you won't need II to continue.
    ... now to be proved wrong ;)
  4. Mar 2, 2013 #3
    I don't think those axioms are right.

    What if you take [itex]R=\emptyset[/itex]? Then it clearly doesn't hold?

    You want [itex]f(i)\in H(i)[/itex] and not [itex]f(i)\subseteq H(i)[/itex].

    Anyway, if you correct your two axioms enough, then I and II are indeed equivalent (as they should be). The proof is really a good exercise, but to prove I from II, you should think of

    [tex]\prod_{i\in I} \{(i,y)~\vert~(i,y)\in R\}[/tex]
  5. Mar 2, 2013 #4
    Oh oops. Sorry for some sort of typos.
  6. Mar 2, 2013 #5
    Wouldn't the proof starts with the Cartesian product of some sets instead of product of ordered pairs?
    Last edited: Mar 2, 2013
  7. Mar 2, 2013 #6
    Here is my approach.

    I define:

    [itex]X_{i\in I} H(i) = f | f with dom(f) = I and \forall i \in I f(i) \in H(i)[/itex]

    Assume that H(i) and f(i) are not empty, and that H(i) has the domain I.

    If dom(f) = I and dom(H) = I, then dom(f) = dom(H) = I. Then, we need to show that [itex] f \subseteq H [/itex]

    Let [itex](i,y) \in f[/itex]. It should be clear that [itex](i,y) \in f(i) \in H(i)[/itex] → [itex](i,y) \in H(i)[/itex]. So [itex]f \subseteq H[/itex]
  8. Mar 2, 2013 #7

    I agree. If R is a nonempty set of ordered pairs(a relation) and F = ∅, then dom(F)≠dom(R) and so Axiom I clearly fails. However, if R = ∅ then the Axiom of Choice doesn't apply because it specifically refers to a collection of nonempty sets.


    The Axiom of Choice states that every collection of non-empty sets has a choice function. That is: If I≠∅ is an index set and the nonempty collection of sets
    [tex]S_{i \in I}[/tex] has the property that that [tex]S_{\forall i \in I} \ne \emptyset[/tex] then [tex]\exists f \; | \; f(i) \in S_{i}, \forall i \in I[/tex]

    Given that the Axiom of Choice is not falsifiable in ZFC set theory the best you can do is to show equivalents of it.

    My approach would be to reformulate Axiom of Choice I as the statement: For every relation R ≠ ∅, there exists a function F such that [tex]F(h) \in h \; , \; \forall h \in \mathcal{P}(R) \sim \emptyset[/tex].
  9. Mar 2, 2013 #8
    I'm not taking the product of order pairs. I'm defining the following subset of [itex]R[/itex]. For each [itex]i\in I[/itex], let

    [tex]R_i = \{(i,y)~\vert~(i,y)\}[/tex]

    and then I take the product

    [tex]\prod_{i\in I} R_i[/tex]

    Apply the second form of AC on that.

    The usual notation is with \prod. So I guess it should be

    [tex]\prod_{i\in I} H(i) = f[/tex]

    But I don't see what it means to set a product of sets equal to a function.

    What does it mean for H(i) to have domain I?? H(i) is just a set.

    Why does [itex]f\subseteq H[/itex] show what we want?

    Furthermore, in this entire proof, you have postulated the existence of [itex]f[/itex]. But you have to actually construct [itex]f[/itex] in some way.
  10. Mar 2, 2013 #9
    You can't choose [itex]F=\emptyset[/itex] since then [itex]F[/itex] wouldn't be a function.

    The OP never said anything about nonempty sets. He should have, though.

    The Axiom of Choice is an axiom in ZFC. I guess you mean ZF.

    I'm not sure how this would help us. Your [itex]F[/itex] would then be a function with domain [itex]\mathcal{P}(R)[/itex]. That is not the intention of the Axiom of Choice I. I don't doubt that it is equivalent to your statement however, but it's making things difficult.
  11. Mar 2, 2013 #10
    Well yeah, since the Z in ZFC is for Ernst Zermelo who formulated it first.

    For any non-empty set S, [itex]\mathcal{P}(R) \sim ]emptyset[/itex] is itself a collection of non-empty sets. An equivalent statement(the way Paul Halmos defines it in his book Naive Set Theory[/I) is:

    What I'm trying to do is clarify what the Axiom of Choice actually says. When I first learned it from the book I referenced, it made very little sense. But once you understand what a Choice function is(a function that picks out an element from a non-empty set), then it becomes more clear. Since a (finitary)relation R on a set is just a collection of n-tuples, then if the set is not empty then R is a non-empty. Now in the case of a finite collection of non-empty finite sets, you actually can prove the existence of a choice function on them.
  12. Mar 2, 2013 #11
    Why can't the empty set be a relation?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook