Tao Analysis I - 3.5.12 (i)

Exercise 3.5.12 (i)

This exercise will establish a rigorous version of Proposition 2.1.16 that avoids circularity (in particular, avoiding the use of any object that required Proposition 2.1.16 to construct).

(i) Let $X$ be a set, let $f : \mathbb{N} \times X \to X$ be a function, and let $c$ be an element of $X$. Show that there exists a function $a : X \to X$ such that

$$a(0) = c$$

and

$$a(n++) = f(n, a(n)) \text{ for all } n \in \mathbb{N}$$

and furthermore that this function is unique. (Hint: first show inductively, by a modification of the proof of Lemma 3.5.11, that for every natural number $N \in \mathbb{N}$, there exists a unique function $a_N:\{n \in \mathbb{N}:n \leq N\} \to X$ such that $a_N(0)=c$ and $a_N(n++)= f(n,a_N(n))$ for all $n \in \mathbb{N}$ such that $n < N$.)

Discussion

I found this exercise tricky because it needs clarity on what we need to do and show. This answer on math stack exchange is helpful on proof strategy (link).

It is also worth pondering on the point of the exercise. It shows that some recursively defined functions can be valid functions. Without proof we can't assume a function defined in terms of itself is a valid function. 

Exploration

To clarify the objects we're dealing with let's write out some examples.

For $N=0$, we have $a_N$ as

$$a_0 : \{0\} \to X \quad \text{ where } \quad a_0(0) = c$$

Note that $a_0$ is a function, defined over the domain $\{0\}$, the subscript zero is not a parameter or input to that function.

Our definition of $a_N$ must conform to the two conditions:

• $a_N(0)=c$
• $a_N(n++)= f(n,a_N(n))$ for all $n \in \mathbb{N}$ such that $n < N$

Our $a_0$ meets the first condition by its own definition.

What about the second condition? The second condition is vacuously true because there are no $n \in \mathbb{N}$ such that $n < N=0$.

For $N=1$, we have $a_N$ as

$$a_1 : \{0, 1\} \to X \quad \text{ where } \quad \begin{cases}a_1(0) &= c \\ \\ a_1(1) &= f(0, a_1(0)) \\ & = f(0, a_0(0)) \end{cases}$$

Here $a_1(0)$ is trivially defined to be $c$, and $a_1(1)$ maps to a unique element of $X$ because $f$ is given as a well-defined function. Thus $a_1$ is also a well-defined function.

For $N=2$, we have $a_N$ as

$$a_2 : \{0, 1,2\} \to X \quad \text{ where } \quad \begin{cases}a_2(0) &= c \\ \\ a_2(1) &= f(0, a_2(0)) \\ & = f(0, a_1(0))  \\ \\ a_2(2) &= f(1, a_2(1)) \\ & = f(1, a_1(1)) \end{cases}$$

Note how we choose to define $a_1(0)=a_0(0)=c$, and $a_2(1)=a_1(1)$ , and in general

$$a_N(n)=a_{N-1}(n)$$

because we want each $a_N$ to be equal to all previous $a_M$ over their shared domain $\{0, \ldots, M\}$, where $M < N, n \leq N$.

So in general we have $a_N$ as

$$a_N : \{0, \ldots, N\} \to X \quad \text{ where } \quad \begin{cases}a_N(0) &= c \\ \\ a_N(n++) &= f(n, a_N(n)) \\ & = f(n, a_{N-1}(n)) \end{cases}$$

where $n < N$.

On the question of uniqueness, each $a_N$ is unique if $f$ is unique, which it is because we are told it is a well-defined function.

Solution

To show that for every natural number $N \in \mathbb{N}$ there exists a unique function $a_N$ as defined in the question, we will use induction on $N$. 

Consider the statement $P(N):$ there is a unique function $a_N:\{n \in \mathbb{N}:n \leq N\} \to X$ which meets the two conditions:

• $a_N(0)=c$
• $a_N(n++)= f(n,a_N(n))$ for all $n \in \mathbb{N}$ such that $n < N$

Base case P(0): We can define a function $a_0 : \{0\} \to X$ where $a_0(0) = c$.

This meets the first condition by definition, and the second condition is vacuously true because there is no $n \in \mathbb{N}$ such that $n<N=0$.

This $a_0:\{0\}\to X$ is also unique. If there were another function $b_0:\{0\}\to X$ which met the same conditions, it would mean $b_0(0)=c$. Since they map every element of the domain, in this case $\{0\}$, to the same $c \in X$, the two functions are equal.

Inductive Hypothesis P(N): We will assume the function $a_N:\{0, \ldots, N\} \to X$ exists, meets the two conditions, and is unique.

Inductive Step P(N++): We need to show $a_{N+1}$ exists, meets the two conditions, and is unique. Let's define it as follows:

$$a_{N+1} : \{0, \ldots, N+1\} \to X \quad \text{ where } \quad \begin{cases}a_{N+1}(0) &= c \\ \\ a_{N+1}(n++) &= f(n, a_{N++}(n)) \\ & = f(n, a_{N}(n)) \end{cases}$$

where $n < N+1$.

By its definition it meets the first condition, $a_{N+1}(0)=c$. The second condition is met because we chose to define $a_{N}$ to equal $a_{N-1}$ over their shared domain $\{0, \ldots, N-1\}$, which gives us $f(n, a_{N++}(n)) = f(n, a_{N}(n))$, which in turn means $a_{N+1}$ exists.

The inductive hypothesis tells us $a_N$ exists and is unique. This means $f(n, a_{N}(n))$ is unique because $f$ is a well-defined function. So if $f(n, a_{N}(n))$  exists and is unique, we have shown $a_{N+1}$ exists and is unique.

Thus, by induction, a unique $a_N$ exists for all $N \in \mathbb{N}$. 

This means there exists a function $a : X \to X$ such that

$$a(0) = c$$

and

$$a(n++) = f(n, a(n)) \text{ for all } n \in \mathbb{N}$$

and furthermore that this function is unique. $\square$

Tao Analysis I 3.5.11

Exercise 3.5.11

Show that Axiom 3.11 can in fact be deduced from Lemma 3.4.10 and the other axioms of set theory, and thus Lemma 3.4.10 can be used as an alternate formulation of the power set axiom. (Hint: for any two sets $X$ and $Y$ , use Lemma 3.4.10 and the axiom of specification to construct the set of all subsets of $X \times Y$ which obey the vertical line test. Then use Exercise 3.5.10 and the axiom of replacement.)

Let's remind ourselves of Axiom 3.11

Axiom 3.11 (Power set axiom). Let $X$ and $Y$ be sets.Then there exists a set, denoted $Y^X$, which consists of all the functions from $X$ to $Y$, thus

$$f \in Y^X \iff f: X \to Y$$

And also remind ourselves of Lemma 3.4.10

Lemma 3.4.10. Let $X$ be a set. Then the set $\{Y: Y \subseteq X\}$ is a set. That is to say, there exists a set $Z$ such that $Y \in Z \iff Y \subseteq X$ for all objects $Y$.

Discussion

Interestingly, most people in my experience, think of the "power set axiom" as that described in Lemma 3.4.10 and not the formulation in Axion 3.11.

Solution

For any two sets $X$ and $Y$ we can form the cartesian product, $X \times Y$ as per Definition 3.5.4.

Now we apply Lemma 3.4.10 to $X \times Y$ to form the set of all subsets of $X \times Y$, which we can call $P(X \times Y)$.

Not every set in $P(X \times Y)$ will obey the vertical line test, so we can use the axiom of specification to filter out those that do, to form a set $Z$

$$Z = \{G \in P(X \times Y): G \text{ obeys the vertical line test}\}$$

The elements $G$ of $Z$ are all the graphs from $X \to Y$ which obey the vertical line test.

We can use the axiom of replacement on $Z$ to replace each element $G$ with an ordered triple $(X, Y, G)$, which we can do because for each $G$ there is a unique $(X, Y, G)$. 

This gives us a set of all the ordered triples $(X, Y, G)$ where $G$ is a graph from $X$ to $Y$ which obeys the vertical line test. Thus, by exercise 3.5.10 part (iii), this is a set of all the functions from $X$ to $Y$. $\square$

Tao Analysis I - 3.5.10

Exercise 3.5.10

If $f:X \to Y$ is a function, define the graph of $f$ to be the subset of $X \times Y$ defined by $\{(x, f(x)) : x \in X\}$.

(i) Show that two functions $f:X \to Y$, $\tilde{f}:X \to Y$ are equal if and only if they have the same graph.

(ii) Conversely, if $G$ is any subset of $X \times Y$ with the property that for each $x \in X$, the set $\{ y \in Y : (x,y) \in G \}$ has exactly one element ($G$ obeys the vertical line test), show that there is exactly one function $f:X \to Y$ whose graph is equal to $G$.

(iii) Suppose we define a function $f$ to be an ordered triple $f = (X, Y, G)$, where $X$, $Y$ are sets, and $G$ is a subset of $X \times Y$ that obeys the vertical line test. We then define the domain of such a triple to be $X$, the codomain to be $Y$, and for every $x \in X$, we define $f(x)$ to be the unique $y \in Y$ such that $(x,y) \in G$. Show that this definition is compatible with Definition 3.3.1 in the sense that every choice of domain $X$, codomain $Y$, and property $P(x,y)$ obeying the vertical line test produces a function as defined here that obeys all the properties required of it in that definition, and is also similarly compatible with Definition 3.3.8.

Exploration

It is worth thinking a little about what the graph is and isn't. The graph is all the mappings from $x \in X$ to $f(x) \in Y$. It is an important and very informative part of the definition of a function, alongside specifying the domain and co-domain. A graph on its own is not technically the same as a function.

Part (i)

We need to show the following two statements:

• Two functions are equal $\implies$ they have the same graph.
• Two functions with the same graph $\implies$ they are equal.

Let's start with the first statement. Consider two functions $f_1: X \to Y$ and $f_2: X \to Y$. If these two functions are equal, they have the same domain, same co-domain and the same mapping between the two. This last requirement is $f_1(x)=f_2(x)$ for every $x \in X$.

The graph of $f_1$ is $\{(x, f_1(x)) : x \in X\}$.

The graph of $f_2$ is $\{(x, f_2(x)) : x \in X\}$. 

Since the two functions are the same, we have $f_1(x)=f_2(x)$ for all $x \in X$, and so the graphs of $f_1$ and $f_2$ are the same.

Let's now consider the second statement. If we have two functions $f_1:X \to Y$ and $f_2:X \to Y$ with the same graph, we have:

$$\{(x, f_1(x)) : x \in X\} =  \{(x, f_2(x)) : x \in X\} $$

This means the two functions map each $x \in X$ to the same element of the co-domain, that is, $f_1(x)=f_2(x)$ for all $x \in X$. We are given that the two function share the same domain, $X$, and also the same co-domain, $Y$. Together, this allows us to say the two functions are equal. 

Having shown both statements, we have proven that two functions $f:X \to Y$, $\tilde{f}:X \to Y$ are equal if and only if they have the same graph. $\square$

Part (ii)

Let's first show the existence of $f:X \to Y$. We can define a function $f$ with the following properties:

• it has a domain $X$
• it has a co-domain $Y$
• it maps each $x \in X$ to a unique $y \in Y$ as $f(x) = y$

We need to show that the mapping is unique, that is, for every $x \in X$ there is only one $y \in Y$, the vertical line test. We are given that for each $x \in X$ the set $\{ y \in Y : (x,y) \in G \}$ has exactly one element, which is equivalent to the vertical line test.

Thus the function $f(x)=y$ exists, and has a graph $\{(x, f(x)): x \in X\}$

Now let's show the function $f:X \to Y$ is unique. Consider two functions $f_1:X \to Y$ and $f_2:X \to Y$ which meet the given criteria, that is, both have a graph equal to $G \subseteq X \times Y$. We have shown in part (i) that two functions which the same graph are equal. Therefore $f_1=f_2$. 

We have shown there is exactly one function $f:X \to Y$ whose graph is equal to $G$. $\square$

Part (iii)

Let's remind ourselves of Definition 3.3.1:

Definition 3.3.1 (Functions). Let $X$, $Y$ be sets, and let $P(x,y)$ be a property pertaining to an object $x \in X$ and an object $y \in Y$, such that for every $x \in X$, there is exactly one $y \in Y$ for which $P(x,y)$ is true (vertical line test). Then we define the function $f: X \to Y$ defined by $P$ on the domain $X$ and codomain $Y$ to be the object, which, given any input $x \in X$, assigns an output $f(x) \in Y$, defined to be the unique object $f(x) \in Y$ for which $P(x,f(x))$ is true. Thus, for any $x \in X$ and $y \in Y$,

$$y = f(x) \iff P(x,y) \text{ is true}$$

Let's also remind ourselves of Definition 3.3.8:

Definition 3.3.8 (Equality of functions). Two functions $f"X \to Y$, $g:X' 'to Y'$ are said to be equal if their domains and codomains agree, and furthermore that $f(x)=g(x)$ for all $x \in X$. 

Let's be clear about what is required of us. We need to show that:

• A function defined with a domain $X$, codomain $Y$ and property $P(x,y)$ as per Definition 3.3.1 produces a function as defined by the ordered triple $(X, Y, G)$. 
• Such a function defined by the ordered triple $(X, Y, G)$ obeys the properties as required by Definition 3.3.1 and 3.3.8.

Let's consider the first objective.

For a given domain $X$ and codomain $Y$, we can form a unique ordered pair $(X, Y)$. Now a function, as per Definition 3.3.1, has a property $P(x,y)$ which for any $x \in X$ is true for exactly one $y \in Y$ (vertical line test). Thus we can form a set $G \subseteq X \times Y$ such that $G$ obeys the vertical line test. To do this we can use the Axiom of Replacement on the set $X$ and replace each $x$ with the ordered pair $(x,y)$ such that $P(x,y)$ is true, which we know is only true for one $y$ for each $x$. Then we can form an ordered triple $(X, Y, G)$ which is unique to the domain $X$, codomain $Y$ and property $P(x,y)$.

Let's now consider the second objective.

The properties of Definition 3.3.1 are met by virtue of how we constructed $(X, Y, G)$. For example, we know $G$ obeys the vertical line test because it is constructed using $P(x,y)$ which by definition must obey the vertical line test.

Definition 3.3.8 states that two functions are the same if they have the same domain, codomain and map elements from the domain to the codomain in the same way. If we have two functions $(X, Y, G)$ and $(X', Y', G')$, these ordered $n$-tuples are only equal if $X=X'$, $Y=Y'$ and $G=G'$. That is, the domains are the same,  the codomains are the same, and the. graphs are the same. We have already shown in part (i) that equal graphs implies equal functions.