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

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.

• Please use MathJax Commented May 22, 2023 at 15:20
• You have shown that such a set exists, but you haven't shown the most important part: that this definition accords with our usual understanding of what an ordered pair is. You have to show that if $(a,b)=(c,d)$ then $a=c$ and $b=d$. Commented May 22, 2023 at 16:07
• As for MathJax, you don't have to install anything -- it's built into the web page. See here for a tutorial. Basically, you enclose equations in dollar signs to render them in MathJax; so \$x=y\$ comes out as $x=y$. Sets are a bit awkward, because the curly brackets { and } are MathJax delimiters, so to get them to display properly you have to precede them with a backslash: \$\{x\}\$ comes out as $\{x\}$. Commented May 22, 2023 at 16:08
• I went ahead and edited to put in MathJax/LaTeX formatting. Click Edit to have a look at source code (modify if I've inadvertently changed something). Commented May 22, 2023 at 20:29
• I'm not sure how your pair axiom is stated, but generally, it requires $a, b$ to exist, not $\{a\}$ and $\{b\}$. Also, all you have done is argued for the existence of certain sets. The problem also specifies proving that $\{\{a\}, \{a,b\}\}$ acts like an ordered pair. In particular, that $\{\{a\}, \{a,b\}\} = \{\{x\}, \{x,y\}\}$ if and only if $x = a$ and $y = b$. Commented May 23, 2023 at 11:53

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