Tao Analysis I - 3.5.7

Exercise 3.5.7

Let $X$, $Y$ be sets, and let $\pi_{X \times Y \to X}:X \times Y \to X$ and $\pi_{X \times Y \to Y}:X \times Y \to Y$ be the maps $\pi_{X \times Y \to X} (x, y) := x$ and $\pi_{X \times Y \to Y}(x, y) := y$; these maps are known as the co-ordinate functions on $X × Y$. Show that for any functions $f : Z \to X$ and $g : Z \to Y$, there exists a unique function $h:Z \to X \times Y$ such that $\pi_{X \times Y \to X} \circ h= f$ and $\pi_{X \times Y \to Y} \circ h=g$. (Compare this to the last part of Exercise 3.3.8, and to Exercise 3.1.7.) This function $h$ is known as the pairing of $f$ and $g$ and is denoted $h = (f, g)$.

Exploration

Lt's illustrate some of these new ideas with a small example.

Consider $X=\{x_1, x_2\}$ and $Y=\{y_1\}$. The cartesian product is therefore $X \times Y = \{(x_1, y_1), (x_2, y_1)\}$.

The function $\pi_{X \times Y \to X}:X \times Y \to X$ maps from the cartesian product, the set of ordered $n$-tuples, to the codomain which is the set X. An example of the mapping $\pi_{X \times Y \to X} (x, y) := x$ is

$$\pi_{X \times Y \to X}(x_2, y_1) = x_2$$

The map essentially extracts the "first coordinate" from the pair in the ordered 2-tuple.

Similarly, an example of the mapping for the other function, $\pi_{X \times Y \to Y}(x, y) := y$, is

$$\pi_{X \times Y \to Y}(x_2, y_1) := y_1$$

This extracts the "second coordinate" from the ordered 2-tuple.

Let's draw a picture to illustrate the described functions $f : Z \to X$, $g: Z \to Y$, and $h : Z \to X \times Y$.

Our aim is to show that for any $f$ and $g$, the function $h$ exists and is unique, given the constraints $\pi_{X \times Y \to X} \circ h= f$ and $\pi_{X \times Y \to Y} \circ h=g$.

Solution Part One

For exercises that ask us to prove a set exists, we typically construct the set from the axioms of set theory. However, to show a function exists is a little different as Tao discusses in his book. He writes, in Remark 3.3.2, that the existence of functions could have been made axiomatic, but they aren't because they can be constructed using ordered triple (domain, codomain, graph/mapping) and the operations of axiomatic set theory.

For our purposes, to show a function exists, we need to make clear its domain and codomain, and then ensure the mapping is well-defined, it conforms to the requirement that each element of the domain maps to only one element of the codomain, the "vertical line test".

It is suggested there might exist a function $h:Z \to X \times Y$ such that the following two conditions are met:

$$\forall z \in Z \; [ \pi_{X \times Y \to X} ( h(z) ) = f(z) ]$$

$$\forall z \in Z \; [ \pi_{X \times Y \to Y} ( h(z) ) = g(z) ]$$

Let's assume such a function does exist. What form does it take?

We know that for all $z \in Z$, $h(z)$ takes the form of an ordered pair $(h_1(z), h_2(z))$ where $h_1(z) \in X$ and $h_2(z) \in Y$. That is, $h_1:Z \to X$ and $h_2:Z \to Y$.

What is $h_1(z)$ and $h_2(z)$?

We use the two conditions to answer this:

$$ \pi_{X \times Y \to X}(h(z)) = h_1(z) = f(z)$$

$$ \pi_{X \times Y \to Y}(h(z)) = h_2(z) = g(z)$$

So we have

$$h(z) = (f(z), g(z))$$

We have shown that if there exists a function $h:z \to X \times Y$ that conforms to the two conditions above, then it must be of the unique form $h(z) = (f(z), g(z))$. 

To show existence, we use the definition of the function we derived $h(z)=(f(z), g(z))$ and show it conforms to any required constrains, and is well-behaved as a function:

• the domain of $h$ is $Z$
• the codomain of $h$ is $X \times Y$
• the first condition is met, $\pi_{X \times Y \to X} ( h(z) ) = \pi_{X \times Y \to X} (f(z), g(z))= f(z)$
• the second condition is met, $\pi_{X \times Y \to Y} ( h(z) ) = \pi_{X \times Y \to Y} (f(z), g(z))= g(z)$
• $h(z)=(f(z), g(z))$ is unique to $z$ because both $f$ and $g$ are well-defined functions, where $f(z)$ is unique to $z$, $g(z)$ is unique to $z$, and so $h(z)=(f(z), g(z))$ is also unique to $z$.

This solution was helped by this answer (link).

Solution Part Two

We are asked to compare this result with last part of Exercise 3.3.8, and to Exercise 3.1.7.

Drawing pictures is the easiest way to show the similarities between the sets and functions in these exercises.

In the following we can see there is a duality between the existence of a unique function that maps to $X \times Y$ in the first instance, and maps from $X \cup Y$ in the second.

And in the following we can see similar duality regarding intersection and union where the function is replaced by a predicate "is a subset of".

Apparently this nudge by Tao relates to category theory, something beyond this book, but discussed here (link).