Tao Analysis I - 3.5.2

Exercise 3.5.2

Suppose we define an ordered $n$-tuple to be a surjective function $x : \{i \in \mathbb{N} : 1 \leq i \leq n\} \to X$ whose codomain is some arbitrary set $X$ (so different ordered n-tuples are allowed to have different ranges); we then write $x_i$ for $x(i)$ and also write $x$ as $(x_i)_{1 \leq i \leq n}$. Using this definition, verify that we have $(x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n}$ if and only if $x_i = y_i$ for all $1 \leq i \leq n$. 

Also, show that if $(X_i)_{1 \leq i \leq n}$ are an ordered n-tuple of sets, then the Cartesian product, as defined in Definition 3.5.6, is indeed a set. (Hint: use Exercise 3.4.7 and the axiom of specification.)

Let's remind ourselves of Definition 3.5.6 (Ordered $n$-tuple and $n$-fold Cartesian product):

Let $n$ be a natural number. An ordered $n$-tuple $(x_i)_{1 \leq i \leq n}$ (also denoted $(x_1, \ldots , x_n)$) is a collection of objects $x_i$ , one for every natural number $i$ between 1 and $n$; we refer to $x_i$ as the $i^{th}$ component of the ordered $n$-tuple.

Two ordered $n$-tuples $(x_i )_{1 \leq i \leq n}$ and $(y_i )_{1 \leq i \leq n}$ are said to be equal iff $x_i = y_i$ for all $1 \leq i \leq n$.

If $(X_i)_{1 \leq i \leq n}$ is an ordered $n$-tuple of sets, we define their Cartesian product $\prod_{1 \leq i \leq n}X_i$ (also denoted $\prod_{i=1}^{n}X_i$ or $X_1 \times  \ldots \times X_n$) by

$$ \prod_{1 \leq i \leq n} X_i := \{ (x_i)_{1 \leq i \leq n} : x_i \in X_i \text{ for all } 1 \leq i \leq n \} $$

Exploration

The terminology here is quite dense and confusing, so let's illustrate it with small examples to help clarify our thinking.

Let's start with the idea of an n-tuple as a function. The following shows a function which maps from a domain $\{1,2,3\}$ to a codomain $\{a,b,c\}$. 

Specifically, the function maps 1 to $a$, 2 to $b$, and 3 to $c$. 

To fully describe this function, we can list the output values as an ordered n-tuple, $(a,b,c)$. 

However, to do this we also need to know which elements of the domain these output values correspond to, and for this we need to order the domain too. We can do this simply as $i \in \mathbb{N}: 1 \leq i \leq 3$, which gives 1, then 2, then 3, in that order.

To illustrate the notation, we can write $f_i$ for $f(i)$, that is $f_2$ for $f(2)$. We can also write simply $f$ for $(f_i)_{1 \leq i \leq 3}$.

Part One

We need to show that $(x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n}$ if and only if $x_i = y_i$ for all $1 \leq i \leq n$. To do this we need to show both:

• $(x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n} \implies x_i = y_i$ for all $1 \leq i \leq n$
• $x_i = y_i$ for all $1 \leq i \leq n \implies (x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n}$

The first statement assumes the two functions $x$ and $y$ are equal. Functions are equal if they have the same domain, codomain, and also map the same inputs to the same outputs. This last requirement can be written as $x(i) = y(i)$ for all $1 \leq i \leq n$, which is what we needed to show.

The second statement assumes the two functions map the same inputs to the same outputs, $x(i)=y(i)$. The domain is the same because it is defined for both as $i\in \mathbb{N}: 1 \leq i \leq n$. The range is the same because $x(i) = y(i)$ for all $1 \leq i \leq n$. Since the function is surjective, the range is also the domain. Thus we have demonstrated the three requirements for the functions to be equal, $(x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n}$.

Having shown both implications, we have proved that $(x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n}$ if and only if $x_i = y_i$ for all $1 \leq i \leq n$. $\square$

Part Two - Exploration

I found this quote difficult so I began with an example illustration of some of the objects involved in the exercise.

An ordered $n$-tuple of sets, is a tuple with sets as elements. For example, a 2-tuple $(X_1, X_2)$, where $X_1$ and $X_2$ are sets, not primitive objects like natural numbers. 

To illustrate, the cartesian product of those sets, let's fill in the content of those sets. For example, $X_1=\{a,b\}$, and $X_2=\{c\}$. The cartesian product is a set of 2-tuples, as per definition 3.5.6, which here is

$$\prod_{1 \leq i \leq 2} X_i = \{(a,c), (b,c)\}$$

It is worth being clear that the cartesian product is a set of ordered $n$-tuples.

Let's think about how we might construct the cartesian product:

• we can form the union of the original sets, $\bigcup {X_1, X_2} = \{a,b,c\}$
• each element of the cartesian product is a 2-tuple $(x_1, x_2)$ where $x_1 \in X_1, x_2 \in X_2$
• that 2-tuple is a partial function from the domain $\{1,2\}$ to the codomain $\{a,b,c\}$
• the collection of all such partial functions is a set by exercise 3.4.7
• we can select from that set, using the axiom of specification, just those partial functions that meet our needs: have a domain $\{1,2\}$, have codomain $\{a,b,c\}$, map $i$ to $x_i \in X_i$, and are surjective, which gives us the set $\{(a,c), (b,c)\}$
• the resulting set is the desired cartesian product

Part Two -  Solution

The exercise hints at using the axiom of specification, which can only be applied to one set. This suggests we need to form a single set from the $n$ sets $X_i$, where $1 \leq i \leq n$.

Let's begin with the union of those sets,

$$Y = \bigcup_{1 \leq i \leq n} X_i$$

Thus, any element of any $X_i$ is a member of $Y$. And so this set $Y$ is useful because we can use its elements to build the cartesian product's tuples.

Now, consider a partial function from $\{1 \leq i \leq n\} \to Y$. This is a function which maps from a subset of the domain $\{1 \leq i \leq n\}$ to a subset of the codomain $Y$. The collection of all such partial functions is a set, a result proved in Exercise 3.4.7. Let's call this set $F$.

Some, but not all, elements of this set $F$ are functions, $n$-tuples, that are the elements of the cartesian product. We can select them using the Axiom of Specification to form the set $C$, using a statement $S$.

$$C = \{f \in F: S(f) \text{ is true}\} $$

here the statement $S(f)$ is

$$\begin{align}S(f) \; : \; & \operatorname{dom} f = \{1 \leq i \leq n\} \\ & \land \operatorname{codomain} f = Y \\ & \land f(i) \in X_i \\ & \land f \text { is surjective} \end{align}$$

That is, the statement $S(f)$ is true is the function $f \in F$ has a domain \{1 \leq i \leq n\}, has a codomain $Y=\bigcup X_i$, maps as $f(i) \in X_i$, and is surjective.

The resulting set $C$ contains only the elements of the cartesian product $\prod_{1 \leq i \leq n} X_i$, as per Definition 3.5.6.

We have shown the cartesian product is a set by constructing it using the axioms, as above. $\square$