Proof: Cartesian Product of Two Sets is a Set ZF

Solution 1:

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

Solution 2:

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

Solution 3:

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}$).