Proof Cartesian Product of Two Sets is a Set

[Xittenn]

Hi I'm having trouble with this proof. I'm not sure if I did the first part right and how I should use the second part properly. I am following the hint in the book to use the Axiom of Replacement to prove step three below and follow through with Replacement and Union to finalize the proof.

 

1) Prove that the Cartesian Product of two sets is a set

 

[math] A \times B = \left \{ \left \langle u, v \right \rangle \mid u \in A \land v \in B \right \} [/math]

 

 

2) Taking the Axiom of Replacement

 

[math] \forall u \forall v \forall w \left ( \psi \left ( u, v \right ) \land \psi \left ( u, w \right ) \rightarrow v = w \right ) \rightarrow \forall z \exists y \forall v \left ( v \in y \leftrightarrow \left ( \exists u \in z \right ) \psi \left ( u, v \right ) \right ) [/math]

 

 

3) First prove that the following is a set

 

[math] \forall x \left ( \lbrace \langle x, y \rangle \mid y \in t \rbrace \right ) [/math]

 

 

4) Taking (1) from Section 6

 

[math] \langle x, y \rangle = \langle u, v \rangle \iff x = u \land y = v [/math]

 

 

5) Use then this u and v for the Axiom of Replacement reduced to the following where v is unique

 

[math] \forall z \exists y \forall v \left ( v \in y \leftrightarrow \left ( \exists u \in z \right ) \psi \left ( u, v \right ) \right ) [/math]

 

 

6) [math] \forall t \left ( t \in y \right ) [/math] and [math] z = \langle x, y \rangle [/math]

 

[math] \forall \langle x, y \rangle \exists t \forall v \left ( v \in t \leftrightarrow \left ( \exists u \in \langle x, y \rangle \right ) \langle u, v \rangle \right ) [/math]

 

Hence [math] y \in t [/math] proving that [math] \forall x \left ( \lbrace \langle x, y \rangle \mid y \in t \rbrace \right ) [/math] is a set by the Axiom of Replacement

 

 

7) Now taking the Axiom of Union

 

[math] A \cup B = \lbrace x \mid x \in A \lor x \in B \rbrace [/math]

 

 

8) And the Axiom of Replacement

 

[math] \forall u \forall v \forall w \left ( \psi \left ( u, v \right ) \land \psi \left ( u, w \right ) \rightarrow v = w \right ) \rightarrow \forall z \exists y \forall v \left ( v \in y \leftrightarrow \left ( \exists u \in z \right ) \psi \left ( u, v \right ) \right ) [/math]

 

 

9) And prove that the Cartesian Product of two sets is a set

 

[math] A \times B = \left \{ \left \langle u, v \right \rangle \mid u \in A \land v \in B \right \} [/math]

 

 

If there is something I can make more clear that would allow others to more easily aid me let me know. :|

Edited March 12, 2011 by Xittenn

[Xittenn]

I guess the follow through is proving by replacement that [math] y \in t \rightarrow y \not\in s [/math] given the pair [math] y(in \; replacement) = \lbrace s, t \rbrace [/math]. This said then [math] \forall s (s = A) \forall t (t = B)(A \cup B) [/math] is a set by a proof already given 5.19 iii) and using power set to tie it all together. This seems a bit convoluted to me and I will have to reevaluate the steps.

 

Still uncertain. :/

Edited March 12, 2011 by Xittenn