# Proof: Cartesian Product of Two Sets is a Set ZF

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

$A \times B = \left \{ \left \langle u, v \right \rangle \mid u \in A \land v \in B \right \}$

2) Taking the Axiom of Replacement

$\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 )$

3) First prove that the following is a set

$\forall x \left ( \lbrace \langle x, y \rangle \mid y \in t \rbrace \right )$

4) Taking (1) from Section 6

$\langle x, y \rangle = \langle u, v \rangle \iff x = u \land y = v$

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

$\forall z \exists y \forall v \left ( v \in y \leftrightarrow \left ( \exists u \in z \right ) \psi \left ( u, v \right ) \right )$

6) $\forall t \left ( t \in y \right )$ and $z = \langle x, y \rangle$

$\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 )$

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

7) Now taking the Axiom of Union

$A \cup B = \lbrace x \mid x \in A \lor x \in B \rbrace$

8) And the Axiom of Replacement

$\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 )$

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

$A \times B = \left \{ \left \langle u, v \right \rangle \mid u \in A \land v \in B \right \}$

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

• I guess the follow through is proving by replacement that if y is in t then y cannot be in s given the pair y(in replacement) = {s,t}. This said then for all s = A, for all t = B, A union B is a set by a proof already given 5.19 iii). This seems a bit convoluted to me and I will have to reevaluate the steps. Mar 12 '11 at 8:02
• This would still require using Power Set as below to finalize the proof! Mar 12 '11 at 8:24
• What book are you using? Mar 12 '11 at 13:03
• Basic Set Theory by Azriel Levy Mar 12 '11 at 16:28
• According to Wikipedia, the AoR is dependent on the definition of a Mapping, which in turn is dependent on the definition of a Function, which is dependent on Relation, dependent on Cartesian Product. So it seems that you can't prove a Cartesian Product exists unless you have proven that a Cartesian Product exists. Catch22. Jul 31 '13 at 21:45

How does this proof suit you? I'm afraid it makes no use of the axiom of Replacement though, but I think it may be a little clearer.

Consider any ordered pair $\langle u, v\rangle$ such that $u\in A$ and $v\in B$. By definition, $\langle u, v\rangle=\{\{u\},\{u,v\}\}$. Now $\{u\}\subseteq A$ so $\{u\}\subseteq A\cup B$, hence $\{u\}\in\mathscr{P}(A\cup B)$. Similarly, $\{u,v\}\subseteq A\cup B$, so $\{u,v\}\in\mathscr{P}(A\cup B)$. It follows that $\{\{u\},\{u,v\}\}\subseteq\mathscr{P}(A\cup B)$, so $\{\{u\},\{u,v\}\}\in\mathscr{PP}(A\cup B)$, and all of these sets are known to exist by the Union Axiom and the Power Set Axiom. Then by the axiom schema of specification, you know there exists a set $$E=\{t\in\mathscr{PP}(A\cup B)\ |\ \exists u\exists v(u\in A\land v\in B\land t=\langle u,v\rangle\}.$$

This set is unique by the Axiom of Extensionality, and is the set of all ordered pairs $\langle u, v\rangle$ with $u\in A$ and $v\in B$.

• I think I should be able to derive from this the answer that the text is suggesting I find. Thank you for the proof. Mar 12 '11 at 4:53

Regarding the use of Replacement and Union without Powerset, the proof can be as follows:

I will assume that $(x,y)=\{\{x\},\{x,y\}\}$. First you show that for every $x\in A$ the set $\{(x,y)\ : y\in B\}$. To do this, fix an $x\in A$. Then you define a class-function that sends every element of $Y$ to $(x,y)$. The formula used in replacement would be $\phi(y,z):= z=(x,y)$ (keep in mind that $x$ is fixed). Or more typically $z=\{\{x\},\{x,y\}\}$ or even more typically: $$(\forall w)(w\in z\iff[((\forall u)(u\in w\iff u=x))\lor((\forall u)(u\in w\iff u=x\lor u=y))])$$

To see that this satisfies the uniqueness of $z$ that is required for replacement simply observe that the sentence says that $z$ is a set that contains exactly $\{x\}$ and $\{x,y\}$ and through the axiom of extensionality this $z$ is unique. So for every set $x\in X$ we have defined a set $B_x=\{(x,y)\ :y\in B\}$.

Again using the axiom of replacement we obtain a set $C=\{B_x\ :x\in A\}$. Intuitively we create a class-function that sends every $x\in A$ to $B_x$. The formula that will be used for replacement will be $\psi(x,v):= v=B_x$. Typically this will be written:

$(\forall z)(z\in v\iff$ $$(\forall w)(w\in z\iff[(\exists y\in B)((\forall u)(u\in w\iff u=x))\lor((\forall u)(u\in w\iff u=x\lor u=y))]))$$ The proof that this $v$ is a set is done in the previous paragraphs and the proof of the uniqueness is again due to extensionality. So we have proved that $C=\{B_x\ :x\in A\}$ is indeed a set. From the axiom of union $\bigcup C$ is a set. Now I claim that $\bigcup C$ is the cartesian product $A\times B$.

To see this first take $a\in\bigcup C$. This means that there exists an $x\in A$ such that $a\in B_x$. Which means that there is an $y\in B$ such that $a=(x,y)$. Now take $x\in A$ and $y\in B$. First observe that $(x,y)\in B_x$. Then since $B_x\in C$ we have $(x,y)\in \bigcup C$.

I don't really follow what your book is saying, but maybe this is the proof they wanted:

First, given $x$ and $y$, $\{x,y\}$ exists by the axiom of pairing, and $\{x\} = \{x,x\}$ exists by the axiom of pairing, so $\{\{x\},\{x,y\}\} = \langle x,y\rangle$ exists by a third application of pairing. Now, viewing $x$ as a parameter, we have proved that for each $y \in Y$, the set $\langle x,y\rangle$ exists, so by the axiom of replacement, for each $x$ the set $S_x = \{ \langle x,y\rangle : y \in Y\}$ exists. This last step may also require the axiom of comprehension depending on exactly how your book phrases the axiom of replacement. Now, since $X$ is a set, apply the axiom of replacement again to get that $\{\langle x,y\rangle : x \in X, y \in Y\}$ exists.

I'll leave it up to you to formalize that proof to verify what formulas are used in the applications of replacement.

This is a strange way to prove that cartesian products exist, however, because the theorem can be proved as yunone indicated using the axiom of powerset but not the axiom of replacement. That fact is relevant in set theory because we sometimes work with models that do satisfy the axiom of powerset but not the axiom of replacement (e.g. $V_{\omega + \omega}$).

• I'm not sure if by 'exists' you are meaning the same as 'is a set'. I'm not proving the existence of the Cartesian Product but that in fact it is not a 'proper class' if it is the product of two sets. Mar 12 '11 at 16:35
• I mean to prove that the cartesian product is a set. Mar 12 '11 at 17:14
• I thought as much, thanks for the reply! :) Mar 12 '11 at 17:25