Tao Analysis I - 3.5.1

Exercise 3.5.1

(i) Suppose we define the ordered pair $(x, y)$ for any objects $x$ and $y$ by the formula $(x, y) := \{\{x\}, \{x, y\}\}$. Show that such a definition (known as the Kuratowski definition of an ordered pair) indeed obeys the property (3.5).

(ii) Suppose we instead define an ordered pair using the alternate definition $(x, y) := \{x, \{x, y\}\}$. Show that this definition (known as the short definition of an ordered pair) also verifies (3.5) and is thus also an acceptable definition of ordered pair. (Warning: this is tricky; one needs the axiom of regularity, and in particular Exercise 3.2.2.)

(iii) Show that regardless of the definition of ordered pair, the Cartesian product $X \times Y$ of any two sets $X,Y$ is again a set. (Hint: first use the axiom of replacement to show that for any $x \in X$, that $\{(x, y) : y ∈ Y\}$ is a set, and then apply the axiom of union.)

Let's remind ourselves of property (3.5):

Two ordered pairs $(x, y)$ and $(x′, y′)$ are considered equal if and only if both their components match, i.e.,

$$(x,y)=(x',y') \iff (x=x' \land y=y')$$

Part (i)

Let's consider two ordered pairs, $(x,y)$ and $(a,b)$. Let's write these in the form of the Kuratowski definition.

$$ (x,y) := \{ \{x\}, \{x, y\} \} $$

$$ (a,b) := \{ \{a\}, \{a, b\} \} $$

For the two ordered pairs to be equal, the two sets, $\{ \{x\}, \{x, y\} \}$ and $\{ \{a\}, \{a, b\} \}$, must be equal. Two sets are equal if every member of one is also a member of the other.

This means the following four statements must be true:

• $\{x\} \in \{ \{a\}, \{a, b\} \}$
• $\{x,y\} \in \{ \{a\}, \{a, b\} \}$
• $\{a\} \in \{ \{x\}, \{x, y\} \}$
• $\{a, b\} \in \{ \{x\}, \{x, y\} \}$

Each of these statements implies the following, listed in corresponding order:

• $(x = a) \lor (x = a = b)$
• $(x = a \land y = b) \lor (x = b \land y = a)$
• $(a = x) \lor (a = x = y)$
• $(a = x \land b = y) \lor (a = y \land b = x)$

These make use of the fact that a set with two (distinct) elements can't equal a singleton set. That is, $\{x\} \neq \{a,b\}$, unless $a=b$, in which case $\{a,b\}=\{a\}=\{b\}$, a singleton set.

These last four statements are only all true if:

$$(x = a) \land (y = b)$$

This is because the first and third statements set $x=a$ in all cases. Then the second and fourth statements set $b=y$, or the case where $x=y=a=b$.

This shows the Kuratowski definition of an ordered pair obeys property 3.5. $\square$

Part (ii)

We take a similar approach to the above. 

Before we do, let's remind ourselves of the result of Exercise 3.2.2:

• If $A$ is a set, then $A \notin A$. 
• If $A$ and $B$ are sets, then either $A \notin B$ or $B \notin A$, or both.

Let's consider two ordered pairs, $(x,y)$ and $(a,b)$. Let's write these in the form of the "short" definition.

$$ (x,y) := \{ x, \{x, y\} \} $$

$$ (a,b) := \{ a, \{a, b\} \} $$

For the two ordered pairs to be equal, the two sets, $\{ x, \{x, y\} \}$ and $\{ a, \{a, b\} \}$, must be equal. Two sets are equal if every member of one is also a member of the other.

This means the following four statements must be true:

• $x \in \{ a, \{a, b\} \}$
• $\{x,y\} \in \{ a, \{a, b\} \}$
• $a \in \{ x, \{x, y\} \}$
• $\{a, b\} \in \{ x, \{x, y\} \}$

Each of these statements implies the following, listed in corresponding order:

• $(x = a) \lor (x = \{a, b\})$
• $(x = a \land y = b) \lor (a = \{x, y\})$
• $(a = x) \lor (a = \{x, y\})$
• $(a = x \land b = y)  \lor (x = \{a,b\})$

This requires more work to resolve. We start with two cases, $x=a$ suggested by the first and third statements,  or $x \neq a$.

case $x=a$

The first statement then suggests $x = a = \{a, b\}$. However, this is ruled out by the axiom of regularity. If $x=a$ is a fundamental object, then it cannot be a set $\{a,b\}$. If $x=a$ is a set, then it cannot be a member of $\{a,b\}$ by the axiom of regularity.

Similarly,  the second statement suggests $a=\{x,y\}$, which is ruled out by the axiom of regularity, following a similar argument as above. This leaves $x=a \land y=b$. That is, $y=b$.

The third statement suggests $a=\{x,y\}$, also ruled out by the axiom of regularity.

The fourth statement suggests $x=\{a,b\}$, which is ruled out by the axiom of regularity, leaving $b=y$.

So the case $x=a$ leaves only $b=y$.

case $x \neq a$

Since $x \neq a$, all four statements tell us the following two statements must be true:

• $a = \{x, y\}$
• $x = \{a, b\}$

This is ruled out by the axiom of regularity in the second form presented above: if $A$ and $B$ are sets, then either $A \notin B$ or $B \notin A$, or both. So $x$ must not be an element of $\{x, y\}$, $a$ must not be an element of $\{a,b\}$

So the case $x \neq a$ is ruled out.

Considering both cases leaves us with

$$(x = a) \land (y = b)$$

This shows the "short" definition of an ordered pair obeys property 3.5. $\square$

Part (iii)

For any two sets, $X$ and $Y$, we want to show that the cartesian product $X \times Y$ is also a set.

Fix an $x' \in X$ and apply the Axiom of Replacement to Y as follows. Consider the statement $P$:

$$ P(\;y, (x'y)\;) : (x',y) \text{ is an ordered pair with } y \in Y $$

This statement $P$ is true if $(x', y)$ is an ordered pair with $y \in Y$. For every $y \in Y$ it is true for at most one ordered pair $(x', y)$, therefore it is suitable for use by the Axiom of Replacement. This gives us a new set $S$ of ordered pairs:

$$ S_{x'} = \{ (x', y) : y \in Y\} $$

Remember, $x'$ is fixed.

Now we need to iterate over $x \in X$ and we can do this using the Axiom of Union, which defines the following set:

$$T = \bigcup_{x \in X} S_x = \{ (x, y) : x \in X, y \in Y\}$$

This set $T$ contains all the combinations of $x \in X$ and $y \in Y$ in the form of ordered pairs $(x,y)$. 

This is the Cartesian product $X \times Y$, and is a set by the axioms of construction we used. $\square$

Update to Part (iii)

This discussion (link) has clarified an important point and is worth discussing here.

The axiom of union is quite intuitive, which is good, but does risk us overlooking some details.

The detail I had glossed over is that the union $\bigcup S$ requires $S$ to be a set (of sets). Ensuring that $S$ is a set is something I had glossed over, so the following approach is a little more rigorous.

Step 1:

• Fix an $x' \in X$ and use the axiom of replacement on $Y$. Use the statement $$P(x', (x', y)): (x',y) \text{ is an ordered pair for } y \in Y$$ which is true for at most one ordered pair $(x', y)$ for each $y \in Y$. This gives us a set $S_{x'}=\{(x', y): y \in Y\}$. That is, the set exists due to the axiom of replacement.

Step 2:

• Now use the axiom of replacement again, this time on $Y$. Use the statement $$Q(x, S{_x}): S_{x} \text{ is the set of ordered pairs } \{(x,y): y \in Y\} \text{ for } x \in X)$$ which is true for at most one $S_x$ for each $x \in X$. This gives us a set of sets $S = \{S_x : x \in X\}$. Again, this set exists due to the axiom of replacement.

Step 3:

• Now we know $S$ exists, we can use the axion of union, $\bigcup S = \{(x,y): (x,y) \in S_x\}$. This is equivalent to $\bigcup S = \{(x,y): x \in X, y \in Y\} = X \times Y$, as required.