By defining ordered pair as $(x,y) := \{\{x\},\{x,y\}\}$, show that a Cartesian product of two sets is a set.

elementary-set-theorysolution-verification

I would like to solve following task presented in the book:

Task. Using the following definition of the ordered pair
$$(x,y) := \{\{x\},\{x,y\}\}$$
Show that for two arbitrary sets $A$ and $B$, Cartesian product $A \times B$ is a set.

Couple of notes:

  1. With our new definition of the ordered pair, the definition of the Cartesian product I will use is
    $$X \times Y = \{\{\{x\},\{x,y\}\} \mid x \in X, x \in Y\}$$

  2. According to power axiom presented in the book: For some sets $X$ and $Y$, there exists set $Y^{X} = \{f \mid \text{$f$ is a function from $X$ to $Y$}\}$.

  3. For arbitrary set $X$, I will denote power set as $\mathscr P(X)$

My attempt:

By power axiom and axiom of specification, we can construct following set:

$$S := \{f \in A^{B} \mid \text{ f is a constant function}\}$$

We further define function $$G(f) := \Big\{\{\{y\},\{y,x\}\} \in \mathscr P\Bigr(\mathscr P \Bigr(\text{domain}(f) \cup \text{image}(f)\Bigl)\Bigl)\ \mid x \in \text{domain}(f) \text{ and y $\in$ image}(f) \Big\}$$

Note that

$$G(f) = \{\{\{f(x)\},\{f(x),x\}\} \mid x \in \text{domain}(f)\}$$

Using function $G$ and axiom of replacement, we can construct following set

$$Z := \bigcup \{G(f) \mid f \in S \}$$

Now we show that $Z = A \times B$

Take $X \in Z$. Then $X = \{\{f(x)\},\{f(x),x\}\}$ for some $f \in S$ and $x \in \text{domain}(f)$. But note that $f: B \rightarrow A$, and so $f(x) \in A$ and $x \in B$. Hence $\{\{f(x)\},\{f(x),x\}\} \in A \times B$

Take some $X \in A \times B$. Then $X = \{\{a\},\{a,b\}\}$ for some $a \in A$ and $b \in B$. We can define function $f: B \rightarrow A$ such that $f(x) = a$ for all $x \in B$. Evidently, $f \in S$, and since $b \in \text{domain}(f)$ and $f(b) = a$, we conclude that $\{\{a\},\{a,b\}\} \in G(f)$ and thus $\{\{a\},\{a,b\}\} \in Z$ and so $X \in Z$.

Hence $Z = X \times Y$, which means that $X \times Y$ is indeed a set.

$\blacksquare$

Is it correct?

Best Answer

This solution seems perfectly fine to me. The only thing that I would comment on this is that maybe you should add a comment on why $G(f)$ is a function for each $f \in S$ and not just a set; this of course follows since each $f$ is constant.

Here is however a more straightforward proof of the statement without having to construct the sets $S$ and $G(f)$; just note that $$A \times B = \Big\{ z \in \mathcal P (\mathcal P (A \cup B)) : \exists x \exists y \big( (x \in A) \wedge (y \in B) \wedge (z = \{\{x\}, \{x,y\}\})\big) \Big\},$$ and the left hand side of the equality is a set by powerset, union and separation axioms.

Related Question