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

[NasuSama]

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?

 

[Simon Bridge]

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

 

[micromass]

I don't think those axioms are right.

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

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

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

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

The question is: Is there a way to prove Axiom of Choice I from Axiom of Choice II?

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]

 

[NasuSama]

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]

Oh oops. Sorry for some sort of typos.

 

[NasuSama]

Wouldn't the proof starts with the Cartesian product of some sets instead of product of ordered pairs?

 

[NasuSama]

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]

 

[Zelyucha]

I don't think those axioms are right.



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

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.


NasuSama,

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

 

[micromass]

Wouldn't the proof starts with the Cartesian product of some sets instead of product of ordered pairs?

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.

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]

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.

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

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

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]

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.

 

[micromass]

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.

You can't choose [itex]F=\emptyset[/itex] since then [itex]F[/itex] wouldn't be a function.

However, if R = ∅ then the Axiom of Choice doesn't apply because it specifically refers to a collection of nonempty sets.

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

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.

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

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

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.

 

[Zelyucha]

You can't choose [itex]F=\emptyset[/itex] The Axiom of Choice is an axiom in ZFC. I guess you mean ZF.

Well yeah, since the Z in ZFC is for Ernst Zermelo who formulated it first.

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.

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:

The Cartesian product of a collection of non-empty sets is non-empty

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.

 

[micromass]

then if the set is not empty then R is a non-empty.

Why can't the empty set be a relation?