Cartesian Product: Terence Tao, Analysis 1 (Exercise 3.5.1)

elementary-set-theory

Exercise 3.5.1. Suppose we define the ordered pair $(x, y)$ for any objects $x$ and $y$ by the formula
$$
(x, y) := \bigl\{\{x\}, \{x, y\}\bigr\}
$$
(thus using several applications of
Axiom 3.3). Thus for instance,
$(1, 2)$ is the set $\{\{1\}, \{1, 2\}\}$,
$(2, 1)$ is the set $\{\{2\}, \{2, 1\}\}$, and
$(1, 1)$ is the set $\{\{1\}\}$.
Show that such a definition indeed obeys the property (3.5), and also whenever $X$ and $Y$ are sets, the Cartesian product $X \times Y$ is also a set. Thus this definition can be validly used as a definition of an ordered pair. For an additional challenge, show that the alternate definition
$$
(x, y) := \bigl\{x, \{x, y\}\bigr\}
$$
also verifies (3.5) and is thus also an acceptable definition of ordered pair. (For this latter task one needs the axiom
of regularity, and in particular Exercise 3.2.2.)

I am aware of the different proofs presented on stack exchange, but I cannot follow them. Hence, I present my own proof in order to receive feedback with regards to its soundness:

$\forall a \in X,\, \exists \{a\}$,
(from the singleton set axiom).

$\forall b \in Y,\, \exists \{b\}$,
(from the singleton set axiom).

This implies, since {a} is an object $\forall a \in X$, and since $\{b\}$ is an object $\forall a \in X$, there exists $\{a,b\}$ for each $a \in X$ and for each $b \in Y$ (from the singleton and pair set axiom.)

Also, for all $a$ belonging to $X$ there exists a set
$$
M := \Bigl\{ \bigl\{ \{m\}, \{g, h\} \bigr\}
\mid a \in X,\, g \in X,\, h \in Y \Bigr\}.
$$
Each element of this set is of the form
$\bigl\{\{m\}, \{g,h\}\bigr\}$,
where $m \in X,\, g \in X,\, h \in Y$. Such an element is a valid construction given the "'singleton/pair' set axiom".

Now, given the set $M$, we may invoke axiom of specification, in order to construct set
$$
R := \Bigl\{ \bigl\{ \{m\}, \{g, h\} \bigr\}
\mid m \in X,\, g \in X,\, h \in Y,\, \text{and}\, m=g \Bigr\}.
$$

Thus completing the proof.

Correct? Incorrect? Please help.

Best Answer

I do not know exactly how Terence Tao states his axioms, but the general form of this I am familiar with is

  • Axiom of pairs: $\forall a \forall b \exists S \forall x (x \in S \iff x = a\vee x = b)$.

S is commonly denoted by $\{a, b\}$ or $\{b, a\}$.

From this, you prove the existences of singletons $\forall a, \{a\} = \{a,a\}$, and $\forall a\forall b\exists\{\{a\}, \{a, b\}\}$, which we denote by $(a,b)$.

Next is a construction axiom:

  • If $T(x)$ is some construction based on $x$, then $$\forall A\exists B\forall y(y \in B \iff \exists x(x\in A \wedge y = T(x))).$$

I.e., for any set $A$, there is a set $\{T(x) \mid x \in A\}$.

Using this axiom, for all $x \in X, \exists S_x = \{(x,y) \mid y \in Y\}$.

And using it again, there is a set $\mathcal C = \{S_x \mid x \in X\}$.

Finally, using the axiom of union, $X \times Y = \bigcup \mathcal C$.

Related Question