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.

Tao Analysis I - 3.5.9

Exercise 3.5.9

Suppose that $I$ and $J$ are two sets, and for all $\alpha \in I$ let $A_{\alpha}$ be a set, and for all $\beta \in J$ let $B_{\beta}$ be a set. Show that

$$(\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) = \bigcup_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cap B_{\beta})$$

What happens if one interchanges all the union and intersection symbols here?

Solution Strategy

For this solution I wanted to develop the proof using only a chain of equivalences $\iff$, rather than the more verbose approach of proving one direction $\implies$, and the other direction $\impliedby$.

This math stack exchange answer helped clarify this approach, which is still unfamiliar to me (link). 

In addition this wikipedia article on manipulating prenex normal form is useful (link).

Solution Part One

Let's start with the LHS.

$$x \in (\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) \iff x \in (\bigcup_{\alpha \in I} A_{\alpha}) \land x \in (\bigcup_{\beta \in J} B_{\beta})$$

Using the definition of the union of sets, this means both of the following are true:

• $x$ is an element of at least one $A_{\alpha}$
• $x$ is an element of at least one $B_{\beta}$

For the next step we have to take care with the use of the $\exists$ existential quantifier.

$$x \in (\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) \iff (\exists \alpha\in I) \; [x \in A_{\alpha}] \land (\exists \beta\in J) \; [x \in B_{\beta}]$$

This is essentially writing out what we have written in the bullet points.

If there exists an $\alpha \in I$ and a $\beta \in J$ which meet certain conditions,  then there exists an $(\alpha, \beta) \in I \times J$ where the same conditions are met. That is,

$$\begin{align}x \in (\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) & \iff (\exists \alpha\in I) \; [x \in A_{\alpha}] \land (\exists \beta\in J) \; [x \in B_{\beta}] \\ \\ & \iff (\exists (\alpha, \beta) \in I\times J ) \; [x\in A_{\alpha} \land x \in B_{\beta}] \\ \\ & \iff (\exists (\alpha, \beta) \in I\times J ) \; [x\in A_{\alpha}\cap B_{\beta}] \\ \\ & \iff x \in \bigcup_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cap B_{\beta})  \end{align}$$

Thus, we have shown

$$(\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) = \bigcup_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cap B_{\beta}) \; \square$$

Solution Part Two

Now consider what happens if we interchange the union and intersection symbols. We have a new proposal to show:

$$(\bigcap_{\alpha \in I} A_{\alpha}) \cup (\bigcap_{\beta \in J} B_{\beta}) = \bigcap_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cup B_{\beta})$$

The proof is almost the same, so we'll only write down the essence of it.

Let's start with the LHS.

$$(\bigcap_{\alpha \in I} A_{\alpha}) \cup (\bigcap_{\beta \in J} B_{\beta}) \iff x \in (\bigcap_{\alpha \in I} A_{\alpha}) \lor x \in (\bigcap_{\beta \in J} B_{\beta})$$

Using the definition of the intersection of sets, this means either or both of the following are true:

• $x$ is an element of every $A_{\alpha}$
• $x$ is an element of every $B_{\beta}$

For the next step we have to take care with the use of the $\forall$ "for all" quantifier.

$$x \in (\bigcap_{\alpha \in I} A_{\alpha}) \cup (\bigcap_{\beta \in J} B_{\beta}) \iff (\forall \alpha\in I) \; [x \in A_{\alpha}] \lor (\forall \beta\in J) \; [x \in B_{\beta}]$$

We continue in a similar manner to the above,

$$\begin{align}x \in (\bigcap_{\alpha \in I} A_{\alpha}) \cup (\bigcap_{\beta \in J} B_{\beta}) & \iff (\forall \alpha\in I) \; [x \in A_{\alpha}] \lor (\forall \beta\in J) \; [x \in B_{\beta}] \\ \\ & \iff (\forall (\alpha, \beta) \in I\times J ) \; [x\in A_{\alpha} \lor x \in B_{\beta}] \\ \\ & \iff (\forall (\alpha, \beta) \in I\times J ) \; [x\in A_{\alpha}\cup B_{\beta}] \\ \\ & \iff x \in \bigcap_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cup B_{\beta})  \end{align}$$

Thus, we have shown

$$(\bigcup_{\alpha \in I} A_{\alpha}) \cup (\bigcup_{\beta \in J} B_{\beta}) = \bigcap_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cup B_{\beta}) \; \square$$

Tao Analysis I - 3.5.8

Exercise 3.5.8

Let $X_1, \ldots , X_n$ be sets. Show that the Cartesian product $\prod_{i=1}^{n} X_i$ is empty if and only if at least one of the $X_i$ is empty.

Let's remind ourselves of Definition 3.5.6 for Cartesian products. 

If $(X_i)_{1 \leq i \leq n}$ is an ordered $n$-tuple of sets, we define their Cartesian product as

$$\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 \}$$

We need to how both of the following:

• $\prod_{i=1}^{n} X_i = \emptyset \implies \exists X_i = \emptyset$
• $\exists X_i = \emptyset \implies \prod_{i=1}^{n} X_i = \emptyset$

Let's start with the second statement as it is easier to prove. If at least one $X_i$ is empty, let's call it $X_j$ then there is no $x_j= \in X_i$. This means the $n-$tuple $(x_i)_{1 \leq i \leq n}$ can't be formed with $n$ components. Thus the cartesian product, a set, is empty.

Now let's consider the first statement. The cartesian product is empty only if the $n$-tuples can't be formed with $n$ components. This only happens if one of the $X_i$ is empty. 

By proving both statements, we have shown the Cartesian product $\prod_{i=1}^{n} X_i$ is empty if and only if at least one of the $X_i$ is empty. $\square$

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

Tao Analysis I - 3.5.6

Exercise 3.5.6

Let $A$, $B$, $C$, $D$ be non-empty sets. Show that $A \times B \subseteq C \times D$ if and only if $A \subseteq C$ and $B \subseteq D$, and that $A \times B = C \times D$ if and only if $A = C$ and $B = D$. 

What happens if some or all of the hypotheses that the $A$, $B$, $C$, $D$ are non-empty are removed?

Show $A \times B \subseteq C \times D \iff A \subseteq C$ and $B \subseteq D$

To show $A \times B \subseteq C \times D$ if and only if $A \subseteq C$ and $B \subseteq D$ we need to prove the following two statements:

• $A \times B \subseteq C \times D \implies A \subseteq C \land B \subseteq D$
• $A \subseteq C \land B \subseteq D \implies A \times B \subseteq C \times D$

Let's start with the second statement as it easier to prove.

$$A \subseteq C \land B \subseteq D \implies A \times B \subseteq C \times D$$

We need to show - is a statement I was advised by a mathematician friend to get into the habit of writing - $(\forall a\in A, b \in B) \; [(a,b) \in C \times D]$.

Given $A$ and $B$ are assumed non-empty, we can always pick an element $a \in A$ and $b \in B$ to form a tuple $(a,b)$.

By assumption, $A \subseteq C$ and $B \subseteq D$, and so we can deduce $a \in C$ and $b \in D$. So the tuple $(a,b)$ is in $C \times D$ by definition of cartesian products. Thus we have shown $A \subseteq C \land B \subseteq D \implies A \times B \subseteq C \times D$.

Now let's consider the first statement.

$$A \times B \subseteq C \times D \implies A \subseteq C \land B \subseteq D$$

We need to show $(\forall a \in A)\;[a \in C]$ and $(\forall b \in B)\;[b \in D]$.

Since $A$ and $B$ are assumed non-empty, we can always pick an arbitrary $a \in A$ and $b \in B$ to form a tuple $(a,b)$.

By definition of cartesian products, $(a,b) \in A \times B$. By hypothesis $A \times B \subseteq B \times D$, and so $(a,b) \in C \times D$. 

Again, by definition of cartesian products, this means $a \in C \land b \in D$. Thus we have shown $A \times B \subseteq C \times D \implies A \subseteq C \land B \subseteq D$.

By showing both statements, we have shown $A \times B \subseteq C \times D \iff A \subseteq C$ and $B \subseteq D$. $\square$.

Show $A \times B = C \times D \iff A = C$ and $B = D$

To show $A \times B = C \times D$ if and only if $A = C$ and $B = D$ we need to prove the following two statements:

• $A \times B = C \times D \implies A = C \land B = D$
• $A = C \land B = D \implies A \times B = C \times D$

Again, let's start with the second statement as it is easier to prove.

$$A = C \land B = D \implies A \times B = C \times D$$

We need to show $(\forall a \in A, b \in B) \; [(a,b) \in C \times D]$ and $(\forall c \in C, d \in D) \; [(c,d) \in A \times B]$.

Since $A$ and $B$ are assumed non-empty, we can always pick an arbitrary $a \in A$ and $b \in B$ to form a tuple $(a,b)$. By definition of cartesian products, $(a,b) \in A \times B$. By hypothesis, $A = C$ and $B = D$, and so we can deduce $a \in C$ and $b \in D$. And so $(a,b) \in C \times D$ by definition of cartesian products. This gives us $ A \times B \subseteq C \times D$.

To show $A \times B = C \times D$, we also need to show $C \times D \subseteq A \times D$.

Since $C$ and $D$ are assumed non-empty, we can always pick an arbitrary $c \in C$ and $d \in D$ to form a tuple $(c,d)$. The same argument as for $(a,b)$ gives us $C \times D \subseteq A \times D$.

So we have shown $A = C \land B = D \implies A \times B = C \times D$.

Now consider the first statement.

$$A \times B = C \times D \implies A = C \land B = D$$

We need to show $(\forall a \in A)[a \in C]$, $(\forall b \in B)[b \in D]$, $(\forall c \in C)[c \in A]$, and $(\forall d \in D)[d \in B]$.

Since $A$ and $B$ are assumed non-empty, we can always pick an arbitrary $a \in A$ and $b \in B$ to form a tuple $(a,b)$. By definition of cartesian products $(a,b) \in A \times B$. By hypothesis $A \times B = C \times D$, and so $(a,b) \in C \times D$. By definition of cartesian products, we deduce $a \in C$ and $b \in D$.

We have shown $(\forall a \in A)[a \in C]$ and $(\forall b \in B)[b \in D]$. We still need to show $(\forall c \in C)[c \in A]$, and $(\forall d \in D)[d \in B]$.

Since $C$ and $D$ are assumed non-empty, we can always pick an arbitrary $c \in C$ and $d \in D$ to form a tuple $(c,d)$. A symmetric argument to that for $(a,b)$ gives us $c \in A$ and $d \in B$.

So we have shown $A \times B = C \times D \implies A = C \land B = D$.

By showing both statements, we have proven $A \times B = C \times D \implies A = C \land B = D$. $\square$

Removing The Non-Empty Set Assumptions

Consider the first proposal:

$$A \times B \subseteq C \times D \iff A \subseteq C \land B \subseteq D$$

If only $A=\emptyset$, then $A \times B = \emptyset$, which is a subset of any set, not just $C \times D$. There is therefore no relationship between $B$, $C$, and $D$ required to make the LHS true. The proposal is therefore not always true.

Because $B$ is symmetric to $A$, if only $B=\emptyset$, the proposal also fails.

However, if both $A=\emptyset$ and $B=\emptyset$, then the proposal holds.

Now consider the second proposal:

$$A \times B = C \times D \iff A = C \land B = D$$

If only $A=\emptyset$, then $A=C=\emptyset$, and the statement becomes $\emptyset = \emptyset \iff \emptyset = \emptyset \land B = D$. The LHS is true regardless of any relationship between $B$ and $D$, so the proposal is not always true. By symmetry, this applies to $B=\emptyset$ too.

If only both $A=B=\emptyset$, then $A=C=\emptyset$ and $B=D=\emptyset$, and the statement becomes $\emptyset = \emptyset \iff \emptyset = \emptyset \land \emptyset = \emptyset$, which is fine. By symmetry, this applies to $C=D$ too.

If however, only $A=C=\emptyset$ then the statement becomes $\emptyset = \emptyset \iff \emptyset = \emptyset \land B=D$. The LHS can be true regardless of $B$ and $D$, and so the proposal is not always true.

By symmetry, this applies to $B=D$ too.

If all $A=B=C=D=\emptyset$ then the proposal holds.

Note - we can intuitively think of $\emptyset \times A$ as multiplying by zero, and this "losing information" about $A$.

Tao Analysis I - 3.5.5

Exercise 3.5.5

Let $A$, $B$, $C$, $D$ be sets. Show that $(A \times B) \cap (C \times D)=(A \cap C) \times (B \cap D)$.

Is it true that $(A  \times  B)  \cup  (C  \times  D) = (A  \cup  C)  \times  (B  \cup  D)$?

Is it true that $(A  \times  B) \setminus (C  \times  D) = (A \setminus C)  \times  (B \setminus D)$?

Let's draw a picture to help clarify our thinking.

We can see visually that:

• $(A \times B) \cap (C \times D)=(A \cap C) \times (B \cap D)$.
• $(A  \cup  C)  \times  (B  \cup  D)$ contains $(c,b)$ where $c \in C, b \in B$, but $(A  \times  B)  \cup  (C  \times  D)$ does not.
• $(A  \times  B) \setminus (C  \times  D)$ contains $(a,e)$ where $a \in A, e \in B \cap D$, but $(A \setminus C)  \times  (B \setminus D)$ does not.

Show $(A \times B) \cap (C \times D)=(A \cap C) \times (B \cap D)$

Let's write out what $(A \times B) \cap (C \times D)$ means,

$$ (x,y) \in (A \times B) \cap (C \times D) \iff (x,y) \in \{(a,b): a \in A, b \in B \} \land (x,y) \in \{(c,d): c \in C, d \in D \}$$

We can see that $x$ must be in both $A$ and $C$, and $y$ must be in both $B$ and $D$.

Therefore, the RHS is equivalent to

$$(x,y) \in \{(s,t): s \in A \cap C, t \in B \cap D\}$$

Thus we have shown $(A \times B) \cap (C \times D)=(A \cap C) \times (B \cap D)$. $\square$

Is it true that $(A  \times  B)  \cup  (C  \times  D) = (A  \cup  C)  \times  (B  \cup  D)$?

Let's write out what $(A  \times  B)  \cup  (C  \times  D)$ means,

$$ (x,y) \in (A  \times  B)  \cup  (C  \times  D) \iff (x,y) \in \{(a,b): a \in A, b \in B\} \lor (x,y) \in \{(c,d): c \in D, d \in D\}$$

Here we need to be careful about what this means. It means that

$$ (x \in A \land y \in B) \lor (x \in C \land y \in D) $$

Note in particular that $(c, b): c \in C, b \in B$ is not compatible with this, and is therefore not in the set $(A  \times  B)  \cup  (C  \times  D)$. 

Let's consider the other set, $(A  \cup  C)  \times  (B  \cup  D)$. This means

$$ (x,y) \in (A  \cup  C)  \times  (B  \cup  D) \iff (x,y) \in \{(a,b): a \in A \lor C, b \in B \lor D\}$$

This time, the ordered pair $(c, b): c \in C, b \in B$  is in this set.

Therefore the two are not equivalent, $(A  \times  B)  \cup  (C  \times  D) \neq (A  \cup  C)  \times  (B  \cup  D)$. $\square$

A counter-example can illustrate this. Consider $A=\{1\}, B=\{2\}, C=\{3\}, D=\{4\}$. 

Then  $(A  \times  B)  \cup  (C  \times  D) = \{(1,2), (3,4)\}$, and $(A  \cup  C)  \times  (B  \cup  D) = \{(1,2), (1,4), (3,2), (3,4)\}$, a different set. The latter contains $(3,2)$, the former does not.

Is it true that $(A  \times  B) \setminus (C  \times  D) = (A \setminus C)  \times  (B \setminus D)$?

Let's write out what $(A  \times  B) \setminus (C  \times  D)$ means,

$$(x,y) \in (A  \times  B) \setminus (C  \times  D) \iff (x,y) \in \{ (a,b): a \in A, b \in B \} \land (x,y) \notin \{(c,d): c \in C, d \in D\}$$

Again, with some care, we establish what this means. (revision on negating statements)

$$ (x \in A \land y \in B) \land (x \notin C \lor y \notin D)$$

Consider the ordered pair $(a,e): a \in A, e \in B \cap D$. This satisfies the above condition, so is a member of the set $(A  \times  B) \setminus (C  \times  D)$

Now let's consider the other set, $(A \setminus C)  \times  (B \setminus D)$. This means

$$ (x,y) \in (A \setminus C)  \times  (B \setminus D) \iff (x,y) \in \{(a,b): a \in A \land a \notin C, b \in B \land b \notin D\} $$

That is, $x \in A \land x \notin C \land y \in B \land  y \notin D$.

The ordered pair $(a,e): a \in A, e \in B \cap D$ is not in this set.

Therefore the two are not equivalent, $(A  \times  B) \setminus (C  \times  D) \neq (A \setminus C)  \times  (B \setminus D)$. $\square$

Again, a counter-example will illustrate this. Consider $A=\{1\}, B=\{2,3\}, C=\{4\}, D=\{3,5\}$. 

Then, $(A  \times  B) \setminus (C  \times  D) = \{(1,2), (1,3)\}$, and $(A \setminus C)  \times  (B \setminus D) = \{(1,2)\}$, a different set. The former contains $\{1,3\}$, the latter does not.

Tao Analysis I - 3.5.4

Exercise 3.5.4

Let $A$, $B$, $C$ be sets. Show that $A \times (B \cup C)=(A \times B) \cup (A \times C)$, that $A \times (B \cap C)=(A \times B) \cap (A \times C)$, and that $A \times (B \setminus C)=(A \times B) \setminus (A \times C)$.

Show $A \times (B \cup C)=(A \times B) \cup (A \times C)$

Let's write out what $A \times (B \cup C)$ means,

$$(a,d) \in A \times (B \cup C) \iff (a,d) \in \{ (x,y) : x \in A,  y \in B \cup C\}$$

The RHS is equivalent to

$$(a,d) \in \{ (x,y) : x \in A,  y \in B\} \lor (a,d) \in \{ (x,y) : x \in A,  y \in C\}$$

Which is equivalent to

$$(a,d) \in A \times (B \cup C) \iff (a,d) \in (A \times B) \cup (A \times C)$$

Thus, we have shown $A \times (B \cup C)=(A \times B) \cup (A \times C)$. $\square$

Show $A \times (B \cap C)=(A \times B) \cap (A \times C)$

Let's write out what $A \times (B \cap C)$ means

$$(a,d) \in A \times (B \cap C) \iff (a,d) \in \{ (x,y) : x \in A,  y \in B \cap C\}$$

The RHS is equivalent to

$$(a,d) \in \{ (x,y) : x \in A,  y \in B\} \land (a,d) \in \{ (x,y) : x \in A,  y \in C\}$$

Which is equivalent to

$$(a,d) \in A \times (B \cap C) \iff (a,d) \in (A \times B) \cap (A \times C)$$

Thus, we have shown $A \times (B \cap C)=(A \times B) \cap (A \times C)$. $\square$

Show $A \times (B \setminus C)=(A \times B) \setminus (A \times C)$

Let's write out what $A \times (B \setminus C)$ means

$$(a,d) \in A \times (B \setminus C) \iff (a,d) \in \{ (x,y) : x \in A,  y \in B \setminus C\}$$

The RHS is equivalent to

$$(a,d) \in \{ (x,y) : x \in A,  y \in B\} \land (a,d) \notin \{ (x,y) : x \in A,  y \in C\}$$

Which is equivalent to

$$(a,d) \in A \times (B \setminus C) \iff (a,d) \in (A \times B) \setminus (A \times C)$$

Thus, we have shown $A \times (B \setminus C)=(A \times B) \setminus (A \times C)$. $\square$

Tao Analysis I - 3.5.3

Exercise 3.5.3

Show that the definitions of equality for ordered pair and ordered $n$-tuple are consistent with the reflexivity, symmetry, and transitivity axioms, in the sense that if these axioms are assumed to hold for the individual components $x$, $y$ of an ordered pair $(x, y)$, then they hold for the ordered pair itself.

The approach is the same for both ordered pair and $n-tuple$ but for clarity we'll do the special easier case of an ordered pair first, then do the more general $n$-tuple.

Ordered Pair

Two ordered pairs $(x,y)$ and $(x',y')$ are equal if and only if $x=x'$ and $y=y'$, by Definition 3.5.1.

Let's consider reflexivity, $A=B \implies B=A$. So let's assume $(x,y)=(x',y')$. This means $x=x'$ and $y=y'$. Since reflexivity holds for $x, y, x', y'$, we can say $x'=x$ and $y'=y$, which is equivalent to $(x',y')=(x,y)$. Thus we have shown reflexivity, $(x,y)=(x',y') \implies (x',y')=(x,y)$. $\square$

Now let's consider symmetry, $(x,y)=(x,y)$. This is true because we know the components obey the equivalence property $x=x$ and $y=y$, which means the ordered pair is equal to itself by definition 3.5.1. $\square$

Finally, consider transitivity, $A=B \land B=C \implies A=C$. Let's start with $(x,y)=(x',y')$ and $(x',y')=(x'',y'')$. Using definition 3.5.1, we know that $x=x', y=y'$ and also $x'=x'', y'=y''$. Since these individual components obey the equivalence property of transitivity, we can say $x=x'', y=y''$. By definition 3.5.1 this tells us $(x,y)=(x'',y'')$. We have shown ordered pairs obey transitivity, $(x,y)=(x',y')$ and $(x',y')=(x'',y'')$ implies $(x,y)=(x'',y'')$. $\square$

n-Tuples

Definition 3.5.6 generalises equality of ordered pairs to n-tuples:

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

Let's consider reflexivity, $A=B \implies B=A$. Given two equal n-tuples, $(x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n}$, we know by the above definition 3.5.1 that $x_i = y_i$ for all $1 \leq i \leq n$. Since these individual components $x_i$ and $y_i$ obey reflexivity, we can say $y_i = x_i$ for all $1 \leq i \leq n$. This is equivalent to $(y_i)_{1 \leq i \leq n} = (x_i)_{1 \leq i \leq n}$, thus we have shown reflexivity. $\square$

Let's now consider symmetry, $(x_i)_{1 \leq i \leq n}=(x_i)_{1 \leq i \leq n}$. For this to be true we must have $x_i = x_i$ for all $1 \leq i \leq n$. This is indeed the case as the individual components $x_i$ obey symmetry. This we have shown symmetry. $\square$

Finally, consider transitivity, $A=B \land B=C \implies A=C$. Let's start with $(x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n}$, and $(y_i)_{1 \leq i \leq n} = (z_i)_{1 \leq i \leq n}$. This tells us $x_i = y_i$ for all $1 \leq i \leq n$, and $y_i = z_i$ for all $1 \leq i \leq n$. Since these individual elements obey transitivity, we have $x_i = z_i$ for all $1 \leq i \leq n$. This is equivalent to $(x_i)_{1 \leq i \leq n} = (z_i)_{1 \leq i \leq n}$. Thus, we have shown transitivity. $\square$.

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$

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.

Tao Analysis I - 3.4.11

Exercise 3.4.11

Let $X$ be a set, let $I$ be an on-empty set, and for all $\alpha \in I$ let $A_\alpha$ be a subset of $X$.

Show that

$$ X \setminus \bigcup_{\alpha \in I}A_\alpha = \bigcap_{\alpha \in I}( X \setminus A_\alpha) $$

and

$$ X \setminus \bigcap_{\alpha \in I}A_\alpha = \bigcup_{\alpha \in I}( X \setminus A_\alpha) $$

Part One

Let's start by considering $\bigcup_{\alpha \in I}A_\alpha$. By definition we have

$$ x \in \bigcup_{\alpha \in I}A_\alpha \iff (x \in A_\alpha \text{ for some } \alpha \in I)  $$

If $x$ is not in $\bigcup_{\alpha \in I}A_\alpha$, then we have

$$ x \notin \bigcup_{\alpha \in I}A_\alpha \iff (x \notin A_\alpha \text{ for all } \alpha \in I)  $$

Note the quantifier changes from "for some" to "for all" when negated.

So,  $x \in X \setminus \bigcup_{\alpha \in I}A_\alpha $ means

$$(x \in X) \land (x \notin \bigcup_{\alpha \in I}A_\alpha )$$

That is,

$$(x \in X) \land (x \notin A_\alpha \text{ for all } \alpha \in I) $$

That means $x \in X$ and also $x \notin A_\alpha$ for each and every $A_\alpha$. This is equivalent to

$$x \in \bigcap_{\alpha \in I} (X \setminus A_\alpha ) $$

We have shown,

$$X \setminus \bigcup_{\alpha \in I}A_\alpha = \bigcap_{\alpha \in I}( X \setminus A_\alpha) \; \square$$

Part Two

The approach is similar to Part One.

Let's start by considering $\bigcap_{\alpha \in I}A_\alpha$. By definition we have

$$ x \in \bigcap_{\alpha \in I}A_\alpha \iff (x \in A_\alpha \text{ for all } \alpha \in I)  $$

If $x$ is not in $\bigcap_{\alpha \in I}A_\alpha$, then we have

$$ x \notin \bigcap_{\alpha \in I}A_\alpha \iff (x \notin A_\alpha \text{ for some } \alpha \in I)  $$

Note the quantifier changes from "for all" to "for some" when negated. It might be easier to read "for some" as "at least one" in this example.

So,  $x \in X \setminus \bigcap_{\alpha \in I}A_\alpha $ means

$$(x \in X) \land (x \notin \bigcap_{\alpha \in I}A_\alpha )$$

That is,

$$(x \in X) \land (x \notin A_\alpha \text{ for some } \alpha \in I) $$

That means $x \in X$ and also $x \notin A_\alpha$ for some $A_\alpha$. This is equivalent to

$$x \in \bigcup_{\alpha \in I} (X \setminus A_\alpha ) $$

We have shown,

$$ X \setminus \bigcap_{\alpha \in I}A_\alpha = \bigcup_{\alpha \in I}( X \setminus A_\alpha) \; \square$$

Tao Analysis I - 3.4.10

Exercise 3.4.10

Suppose that $I$ and $J$ are two sets, and for all $\alpha \in I \cup J$ let $A_\alpha$ be a set. Show that

$$ \left( \bigcup_{\alpha \in I} A_\alpha \right) \cup \left( \bigcup_{\alpha \in J} A_\alpha \right)  = \bigcup_{\alpha \in I \cup J} A_\alpha $$

If $I$ and $I$ are non-empty, show that

$$ \left( \bigcap_{\alpha \in I} A_\alpha \right) \cap \left( \bigcap_{\alpha \in J} A_\alpha \right)  = \bigcap_{\alpha \in I \cup J} A_\alpha $$

Union of Unions

Let's first consider the set $ \left( \bigcup_{\alpha \in I} A_\alpha \right)$. By definition (3.2), we have

$$ x \in \left( \bigcup_{\alpha \in I} A_\alpha \right) \iff x \in A_\alpha \text{ for some } \alpha \in I $$

Similarly, 

$$ x \in \left( \bigcup_{\alpha \in J} A_\alpha \right) \iff x \in A_\alpha \text{ for some } \alpha \in J $$

Now, by definition of pairwise union, if $x \in X \cup Y \iff (x \in Y) \lor (x \in Y)$. So we have,

$$ x \in  \left( \bigcup_{\alpha \in I} A_\alpha \right) \cup \left( \bigcup_{\alpha \in J} A_\alpha \right) \iff (x \in A_\alpha \text{ for some } \alpha \in I) \lor (x \in A_\alpha \text{ for some } \alpha \in J) $$

The two membership conditions are combined in disjunction.

The RHS is equivalent to $(x \in A_\alpha \text{ for some } \alpha \in I \lor J)$. This is the definition of $\bigcup_{\alpha \in I \cup J} A_\alpha$.

Thus, we have shown

$$ \left( \bigcup_{\alpha \in I} A_\alpha \right) \cup \left( \bigcup_{\alpha \in J} A_\alpha \right)  = \bigcup_{\alpha \in I \cup J} A_\alpha \; \square $$

Intersection of Intersections

Let's consider the set $\left( \bigcap_{\alpha \in I} A_\alpha \right)$. By definition (3.4), we have

$$ x \in  \left( \bigcap_{\alpha \in I} A_\alpha \right) \iff x \in A_\alpha \text{ for all } \alpha \in I  $$

Similarly,

$$ x \in  \left( \bigcap_{\alpha \in J} A_\alpha \right) \iff x \in A_\alpha \text{ for all } \alpha \in J  $$

Now, by definition of pairwise intersection, $x \in X \cap Y \iff (x \in Y) \land (x \in Y)$. So we have,

$$ x \in  \left( \bigcap_{\alpha \in I} A_\alpha \right) \cap \left( \bigcap_{\alpha \in J} A_\alpha \right) \iff (x \in A_\alpha \text{ for all } \alpha \in I) \land (x \in A_\alpha \text{ for all } \alpha \in J) $$

The two membership conditions are combined in conjunction.

The RHS is equivalent to $(x \in A_\alpha \text{ for all } \alpha \in I \land J)$. This is the definition of $\bigcup_{\alpha \in I \cap J} A_\alpha$.

Thus, we have shown

$$ \left( \bigcap_{\alpha \in I} A_\alpha \right) \cap \left( \bigcap_{\alpha \in J} A_\alpha \right)  = \bigcap_{\alpha \in I \cup J} A_\alpha \; \square $$

Tao Analysis I - 3.4.9

Exercise 3.4.9

Show that if $\beta$ and $\beta'$ are two elements of a set $I$, and to each $\alpha \in I$ we assign a set $A_{\alpha}$, then

$$ \{ x \in A_{\beta} : x \in A_{\alpha} \text{ for all } \alpha \in I \} = \{ x \in A_{\beta'} : x \in A_{\alpha} \text{ for all } \alpha \in I \} $$

and so the definition of $\bigcap_{\alpha \in I} A_{\alpha}$ defined in (3.3) does not depend on $\beta$.

Also explain why (3.4) is true.

Let's remind ourselves what the more general definition of intersection (3.3) says:

Given any non-empty set $I$ , and given an assignment of a set $A_{\alpha}$ to each $\alpha \in I$, we can define the intersection $\bigcap_{\alpha \in I}A_{\alpha}$ by first choosing some element $\beta$ of $I$ (which we can do since $I$ is non-empty), and setting

$$ \bigcap_{\alpha \in I} A_{\alpha} := \{ x \in A_{\beta} : x \in A_{\alpha} \text{ for all } \alpha \in I  \} $$

which is a set by the axiom of specification.

Thoughts

Since the intersection contains only elements which are members of all $A_\alpha$, it doesn't matter which $\beta$ is chosen to select one $A_{\alpha=\beta}$. 

Another way to think about this is that, it is impossible to pick a bad $A_\beta$ because if an element is not in $A_\beta$ then it can't be in the intersection.

Another point worth making is that the definition looks over-complicated. Why can't be as simple as the following?

$$ \bigcap_{\alpha \in I} A_{\alpha} := \{ x : x \in A_{\alpha} \text{ for all } \alpha \in I  \} $$

The reason is that defining sets using logical statements can lead to paradoxes, as Tao introduced earlier. However, defining sets as subsets of known sets guarantees they are sets.

Solution

To show the two sets are equivalent, we need to show an element of one is also an element of the other.

If $x \in \{ x \in A_{\beta} : x \in A_{\alpha} \text{ for all } \alpha \in I  \}$ then it must conform to the membership condition $x \in A_{\alpha} \text{ for all } \alpha \in I$.

Since $A_{\beta'}$ is one of the $A_\alpha$, then $x \in A_{\beta'}$. 

So we have $x \in A_{\beta'}$, and also $x \in A_{\alpha} \text{ for all } \alpha \in I$. This is equivalent to  $x \in \{ x \in A_{\beta'} : x \in A_{\alpha} \text{ for all } \alpha \in I  \}$. This is the definition of the second set.

By a symmetric argument, if $x$ is a member of the second set, it is also a member of the first.

Thus we have shown the two sets are equivalent. $\square$.

Now let's consider why (3.4) is true. Let's restate (3.4):

$$ y \in \bigcap_{\alpha \in I} A_\alpha \iff ( y \in A_\alpha \text{ for all } \alpha \in I ) $$

Let's show this in the usual manner, that each statement implies the other.

If  $y \in \bigcap_{\alpha \in I} A_\alpha$, then by definition (3.3) of the intersection of a family of sets, we have $y \in  \{ x \in A_{\beta} : x \in A_{\alpha} \text{ for all } \alpha \in I  \}$. This means $y$ must conform to the membership condition $y \in A_{\alpha} \text{ for all } \alpha \in I $. We have shown

$$y \in \bigcap_{\alpha \in I} A_\alpha \implies y \in A_{\alpha} \text{ for all } \alpha \in I $$

Now the converse, if $y \in A_{\alpha} \text{ for all } \alpha \in I$ is true then the membership condition $\{ y \in A_{\beta} : y \in A_{\alpha} \text{ for all } \alpha \in I  \}$ for the intersection is met, noting that $A_\beta$ is one of the $A_\alpha$. Thus we have shown

$$ y \in A_{\alpha} \text{ for all } \alpha \in I \implies y \in \bigcap_{\alpha \in I} A_\alpha $$

By showing both implications, we have shown that (3.4) is true. $\square$

Tao Analysis I - 3.4.8

Exercise 3.4.8

Show that Axiom 3.5 can be deduced from Axiom 3.1, Axiom 3.4, and Axiom 3.12.

Let's remind ourselves of these axioms.

Axiom 3.5 (Pairwise union). Given any two sets $A$, $B$, there exists a set $A \cup B$, called the union of $A$ and $B$, which consists of all the elements which belong to $A$ or $B$ or both. In other words, for any object $x$,

$$ x \in A \cup B \iff (x \in A \lor x \in B)$$

Axiom 3.1 (Sets are objects). If $A$ is a set, then $A$ is also an object. In particular, given two sets $A$ and $B$, it is meaningful to ask whether $A$ is also an element of $B$.

Axiom 3.4 (Singleton sets and pair sets). If $a$ is an object, then there exists a set $\{a\}$ whose only element is $a$, i.e., for every object $y$, we have $y \in \{a\}$ if and only if $y = a$; we refer to $\{a\}$ as the singleton set whose element is $a$. Furthermore, if $a$ and $b$ are objects, then there exists a set $\{a, b\}$ whose only elements are $a$ and $b$; i.e., for every object $y$, we have $y \in \{a, b\}$ if and only if $y = a$ or $y = b$; we refer to this set as the pair set formed by $a$ and $b$.

Axiom 3.12 (Union). Let $A$ be a set, all of whose elements are themselves sets. Then there exists a set $\bigcup A$ whose elements are precisely those objects which are elements of the elements of $A$, thus for all objects $x$

$$x \in \bigcup A \iff (x \in S \text{ for some } S \in A)$$

Thoughts

The Axiom of Union 3.12 is a generalisation of Axiom of Pairwise Union 3.5. 

This suggests we should apply the given constraints to Axiom 3.12 to yield 3.5.

Solution

Consider two sets, $A$ and $B$. 

Axiom 3.1 tells us these sets are objects. As such they can be considered elements of other sets.

Axiom 3.4 for pair sets tells us that two objects A and B, then there exists a s set $C = \{A, B\}$ whose only elements are $A$ and $B$. In our case, $A$ and $B$ are also sets themselves.

Axion 3.12 tells us that there exists a set $\bigcup C$ whose elements are precisely those objects which are elements of the elements of $C$. That is,  the elements of $\bigcup C$ are the elements of $A$ or $B$, or both.

$$ x \in \bigcup \{A,B\} \iff (x \in A \lor x \in B)$$

This is the definition of a pairwise set of $A$ and $B$, this Axiom 3.5 follows from Axions 3.1, 3.4 and 3.12. $\square$

Tao Analysis I - 3.4.7

Exercise 3.4.7

Let $X, Y$ be sets. Define a partial function from $X$ to $Y$ to be any function $f:X' \to Y'$ whose domain $X'$ is a subset of $X$, and whose codomain $Y'$ is a subset of $Y$. Show that the collection of all partial functions from $X$ to $Y$ is itself a set. (Hint: use Exercise 3.4.6, the power set axiom, the replacement axiom, and the union axiom.)

Strategy

Intuitively the idea is to recognise that a set of all function from a single $X'$ and a single $Y'$ can be formed using the power set axiom. Then we need a way to expand from a single $X'$ to all subsets of $X$, and the same for all subsets of $Y$, in order for us to account for all functions from any subset of $X$ to any subset of $Y$. 

Initially, this may suggest two uses of the union axion, but it turns out the first iteration can be done with the replacement axiom.

Solution

First consider $X$. We know from Exercise 3.4.6 which proves Lemma 3.4.10 that if $X$ is a set, then there exists a set of all subsets of $X$, the power set of $X$. Let's call this $P(X)$, and similarly, $P(Y)$ for the power set of $Y$.

$$P(X) = \{X' : X' \subseteq X\} = \{X'_1, X'_2, X_3', \ldots \}$$

$$P(P) = \{Y' : Y' \subseteq Y\} = \{Y'_1, Y'_2, Y'_3, \ldots \}$$

Now, given an $X' \in P(X)$, and a $Y' \in P(Y)$, the power set axiom tells us there exists a set of all functions from $X' \to Y'$.

$$(Y')^{X'} = \{ f: X' \to Y' \}$$

Let's apply the axiom of replacement to $P(X)$. Consider the following statement $S(X', C)$

$$S(X', C) : C = (Y')^{(X')}$$

The statement is true if C = $(Y')^{(X')}$. There is only one $C$ for a given $X'$, thus the axiom of replacement is applicable, and tells us the following set exists:

$$A = \{ (Y')^{(X_1')}, (Y')^{(X_2')}, (Y')^{(X_3')}, \ldots   \}$$

This $A$ is a set of sets. Each member set consists of all the functions from each $X_i'$ to a fixed $Y'$.

Let's remind ourselves of the Union Axiom 3.12.

Let $A$ be a set, all of whose elements are themselves sets. Then there exists a set $\bigcup A$

whose elements are precisely those objects which are of the elements of the element of $A$, thus for all objects $x$

$$ x \in \bigcup A \iff (x \in S \text{ for some } S \in A) $$

Let's apply the union axiom to our $A=\{ (Y')^{(X'_i)} \}$.

$$ B = \bigcup_{j} A =  \{ (Y'_{j})^{ (X'_i) } \}$$

Here the union is indexed by $j$ over all subsets $Y'_j \subseteq Y$. 

All functions from every $X'$ to a fixed $Y$ are contained in a member set of $A$. Since $B$ is a union of all $(Y'_{j})^{ (X'_i) }$, it contains all functions from every $X' \subseteq X$ to every $Y' subseteq Y$.

Therefore this set $B$ consists of all the partial functions from $X$ to $Y$, and is a set by the axioms that constructed it, as above. $\square$

Tao Analysis I - 3.4.6

Exercise 3.4.6 (edited as per errata)

Prove Lemma 3.4.10. (Hint: start with the set $\{0, 1\}^X$ and apply the replacement axiom, replacing each function $f$ with the object $f^{-1}(\{1\})$.)

Let's write out Lemma 3.4.10. (edited as per errata)

Let $X$ be a set. Then $\{Y :Y \text{ is a subset of } 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$.

Let's also remind ourselves of the Axiom of Replacement 3.7.

Let $A$ be a set. For any object $x \in A$, and any object $y$, suppose we have a statement $P(x, y)$ pertaining to $x$ and $y$, such that for each $x \in A$ there is at most one $y$ for which $P(x, y)$ is true. Then there exists a set 

$$\{y : P(x, y) \text{ is true for some } x \in A\}$$

such that for any object $z$,

$$ z \in \{y : P(x, y) \text{ is true for some } x \in A\} \iff P(x,z) \text{ is true for some } x \in A$$

And the Power Set Axiom 3.11.

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

Exploration

The lemma we need to prove is about existence. We need to prove that the given set exists. We also note that the axiom of replacement and the power set axiom are also about existence.

Let's also sketch out what the proof might look like illustrating the axioms and lemma with a small example (not proof). The following diagram shows $A=\{a, b\}$ and $Y=\{0,1\}$, and the four functions which make up the power set $Y^X=\{f_1, f_2, f_3, f_4\}$.

We can see the inverse images $f^{-1}(\{1\})$ are all the subsets of $X$. Note that $f_2$ does not have an inverse image $f_2^{-1}(\{1\})$ because it does not map any element of $X$ to $1 \in Y$.

Solution

Let's start arbitrary set $X$ and a specific set $Y=\{0,1\}$. 

The Power Set Axiom 3.7 tells us that there exists a set $\{0,1\}^X$, which consists of all the functions $f$ from $X$ to $\{0,1\}$. 

$$\{0,1\}^X = \{f: X \to \{0,1\}\}$$

Now let's apply the Axiom of Replacement 3.7 to this set. Consider a statement $P$ as follows:

$$P(f, A) : A = f^{-1}(\{1\})$$

The statement $P$ is true if the set $A$ is the inverse image of $\{1\}$ with respect to the function $f$.

By definition of inverse images, there is exactly one $A$ satisfying the statement $P$ for each $f$, thus we can use the replacement axiom. 

Thus, by the Axiom of Replacement, there exists a set

$$B=\{A: A=f^{-1}(\{1\})\}$$

This set $B$ consists of the inverse images of $\{1\}$ for every $f \in \{0,1\}^X$.

We now need to show that:

• each $A=f^{-1}(\{1\})$ is a subset of $X$
• the set $B$ consists of all subsets of $X$

If $x \in A = f^{-1}(\{1\})$ then by definition of inverse images, $f(x) \in \{1\}$. Since $\{1\}$ is in $Y$, and the function is $f$, by definition of a function (domain, co-domain, mapping) we conclude $x \in X$. Thus $x \in f^{-1}(\{1\}) \implies x \in X$. That is $x \in A \implies A \subseteq X$. We have shown that each $A$ is a subset of $X$.

Every subset of $A$ can characterised by a function:

$$f_A(a) = \begin{cases} 1  & x \in A \\  0 & x \notin A \end{cases}$$

Such a function is a member of $\{0,1\}^X$ by definition. And as such, $A=f_A^{-1}(\{1\})$ is a member of $B$. Thus, all subsets of $X$ are in $B$.

Thus, we have shown that if $X$ is a set, then there exists a set of subsets of $X$. $\square$

Further Discussion

The above argument will work for any $Y$ with cardinality more than 1.  This is because an element of $Y$ can have an inverse image which is any subset of $X$. 

This is not possible if the cardinality of $Y$ is 1. In this case, all elements of $X$ map to this single element of $Y$ and no partitioning of $X$ into subsets is possible.

Tao Analysis I - 3.4.5

Exercise 3.4.5

Let $f : X \to Y$ be a function from one set $X$ to another set $Y$ . Show that $f(f^{-1}(S))=S$ for every $S \subseteq Y$ if and only if $f$ is surjective. Show that $f^{-1}(f(S))=S$ for every $S \subseteq X$ if and only if $f$ is injective.

Show $f(f^{-1}(S))=S$ if and only if $f$ is surjective.

We need to prove both:

• $f(f^{-1}(S))=S \implies f$ is surjective.
• $f$ is surjective $\implies f(f^{-1}(S))=S$.

Let's start with $f(f^{-1}(S))=S \implies f$ is surjective. 

This is a statement of the form $A \implies B$, which we'll prove by showing the logically equivalent contrapositive $\neg B \implies \neg A$.

So, let's consider that $f$ is not surjective. This means there exists an $s \in S$ for some $S \subseteq Y$, such that $f(x) \neq s$ for all $x \in X$.

The inverse image $f^{-1}(S)$ is, by definition, the set $\{x \in X : f(x) \in S\}$.

If we apply $f$ to the elements of this set, we obtain the set $\{f(x) \in S\}$. However, this set cannot contain $s$ because $f(x) \neq s$ for all $x \in X$.  Therefore the set $\{f(x) \in S\}$ is not always $S$.

Therefore, $f$ not surjective implies $f(f^{-1}(S)) \neq S$.

This is logically equivalent to $f(f^{-1}(S))=S \implies f$ is surjective.

Now let's show $f$ is surjective $\implies f(f^{-1}(S))=S$.

To do this we need to show that under the assumption $f$ is surjective, both of the following are true:

• $f(f^{-1}(S)) \subseteq S$
• $S \subseteq f(f^{-1}(S))$

Let's start with the first $f(f^{-1}(S)) \subseteq S$. 

If $y \in f(f^{-1}(S))$ then $y=f(x)$ for some $x \in f^{-1}(S)$. By definition $f^{-1}(S)$ is the set $\{x \in X: f(x) \in S\}$. 

So if $f(x) \in S$ then $y=f(x) \in S$. That is, $y \in f(f^{-1}(S)) \implies y \in S$. This is equivalent to $f(f^{-1}(S)) \subseteq S$. Note we didn't need $f$ to be surjective for this.

Now let's consider $S \subseteq f(f^{-1}(S))$. 

Since $f$ is surjective, for every $y \in S$ there exists an $x \in f^{-1}(S)$ such that $f(x)=y$. 

Here, $x \in f^{-1}(S)$ gives us $y = f(x) \in f(f^{-1}(S))$. Hence, $y \in S \implies y \in f(f^{-1}(S))$. This is equivalent to $S \subseteq f(f^{-1}(S))$. 

Having shown both $f(f^{-1}(S)) \subseteq S$, and $S \subseteq f(f^{-1}(S))$, we can conclude $f(f^{-1}(S))=S$. This was under the assumption that $f$ is surjective, so we have $f$ is surjective $\implies f(f^{-1}(S))=S$.

Finally, having shown $f(f^{-1}(S))=S \implies f$ is surjective, and $f$ is surjective $\implies f(f^{-1}(S))=S$, we can say $f(f^{-1}(S))=S \iff f$ is surjective. $\square$

Show $f^{-1}(f(S))=S$ if and only if $f$ is injective.

We need to prove both:

• $f^{-1}(f(S))=S \implies f$ is injective.
• $f$ is injective $\implies f^{-1}(f(S))=S$.

Let's start with $f^{-1}(f(S))=S \implies f$ is injective.

This is a statement of the form $A \implies B$, which we'll prove by showing the logically equivalent contrapositive $\neg B \implies \neg A$.

So, let's consider $f$ is not injective. This means there exists an $x_1 \in X$ and $x_2 \in X$, where $x_1 \neq x_2$, such that $f(x_1)=f(x_2)$.

Let's consider the case $S=\{x_1\}$. If $f(x_1) = y \in Y$, then $f(S)=\{y\}$. Since $f(x_1)=f(x_2)$, we also have $y = f(x_2)$.

Now, the inverse image $f^{-1}(f(S))$ is the set $\{ x \in X : f(x) \in f(S) \}$, which here is $\{ x \in X : f(x) \in \{y\} \}$. 

Both $x=x_1$ and $x=x_2$ satisfy the membership condition of this set, and so this set is not $S=\{x_1\}$. 

We have shown that $f$ is not injective implies $f^{-1}(f(S)) \neq S$ for all $S \subseteq X$. This is logically equivalent to $f^{-1}(f(S))=S \implies f$ is injective.

Now let's show $f$ is injective $\implies f^{-1}(f(S))=S$.

To do this we need to show that under the assumption $f$ is injective, both of the following are true:

• $f^{-1}(f(S)) \subseteq S$
• $S \subseteq f^{-1}(f(S))$

Let's start with the first $f^{-1}(f(S)) \subseteq S$.

By definition of inverse images, $f^{-1}(f(S))$ is the set $\{x \in X: f(x) \in f(S)\}$. If $x'$ is a member of this set then $f(x') \in f(S)$.

But $f(S)$ is the set $\{f(x_s): x_s \in S\}$. This means there is an $x_s \in S$ such that $f(x_s) = f(x')$. 

Because $f$ is injective, this implies $x_s=x'$. This $x'$ is also in $S$.

We have shown $x \in f^{-1}(f(S)) \implies x \in S$. That is, $f^{-1}(f(S)) \subseteq S$. 

Now let's consider $S \subseteq f^{-1}(f(S))$.

By definition of inverse images, $f^{-1}(f(S))$ is the set $\{x \in X: f(x) \in f(S)\}$. 

If $x \in S$, then $f(x) \in f(S)$, and so $x$ meets the membership conditions of this set. That is, $x \in S  \implies x \in f^{-1}(f(S))$. This is equivalent to $S \subseteq f^{-1}(f(S))$. Note that we don't need $f$ to be injective for this.

By showing both $f^{-1}(f(S)) \subseteq S$ and $S \subseteq f^{-1}(f(S))$ under the assumption $f$ is injective, we have proven $f$ is injective $\implies f^{-1}(f(S))=S$.  $\square$

Tao Analysis I - 3.4.4

Exercise 3.4.4

Let $f:X \to Y$ be a function from one set $X$ to another set $Y$, and let $U$, $V$ be subsets of $Y$. Show that $f^{-1}(U \cup V)= f^{-1}(U) \cup f^{-1}(V)$, that $f^{-1}(U \cap V)= f^{-1}(U) \cap f^{-1}(V)$, and that $f^{-1}(U \setminus V)= f^{-1}(U) \setminus f^{-1}(V)$.

Before we attempt the exercise, let's remind ourselves of Definition 3.4.5 for inverse images. If $U$ is a subset of $Y$, we define the set $f^{-1}(U)$ to be the set

$$f^{-1}(U) := \{x \in X: f(x) \in U\}$$

That is, $f^{-1}$ consists of all the elements of $X$ which map into $U$:

$$f(x) \in U \iff x \in f^{-1}(U)$$

We call $f^{-1}(U)$ the inverse image of $U$.

Show $f^{-1}(U \cup V)= f^{-1}(U) \cup f^{-1}(V)$

Let's apply Definition 3.4.5 to $f^{-1}(U \cup V)$,

$$f^{-1}(U \cup V) := \{x \in X: f(x) \in U \cup V\}$$

This is the set of $x$ such that either $f(x) \in U$ or $f(x) \in V$, or both, using the definition of union.

Let's consider both cases:

• $f(x) \in U$. Definition 3.4.5 tells us $f(x) \in U \iff x \in f^{-1}(U)$
• $f(x) \in V$. Definition 3.4.5 tells us $f(x) \in U \iff x \in f^{-1}(V)$

Since either or both of these are true, we have either or both of the following are true:

• $x \in f^{-1}(U)$
• $x \in f^{-1}(V)$

This is equivalent to $x \in f^{-1}(U) \cup f^{-1}(V)$.

Thus, we have shown $f^{-1}(U \cup V)= f^{-1}(U) \cup f^{-1}(V)$. $\square$

Note that we didn't have to show inclusion in both directions because the definitions we used are bidirectional $\iff$.

Show $f^{-1}(U \cap V)= f^{-1}(U) \cap f^{-1}(V)$

Let's apply Definition 3.4.5 to $f^{-1}(U \cap V)$,

$$f^{-1}(U \cap V) := \{x \in X: f(x) \in U \cap V\}$$

This is the set of $x$ such that $f(x) \in U$ and $f(x) \in V$, using the definition of intersection.

Let's consider the two cases, both of which must be true:

• $f(x) \in U$. Definition 3.4.5 tells us $f(x) \in U \iff x \in f^{-1}(U)$
• $f(x) \in V$. Definition 3.4.5 tells us $f(x) \in U \iff x \in f^{-1}(V)$

Since both of these are true, then both of the following are true:

• $x \in f^{-1}(U)$
• $x \in f^{-1}(V)$

This is equivalent to $x \in f^{-1}(U) \cap f^{-1}(V)$.

Thus, we have shown $f^{-1}(U \cap V)= f^{-1}(U) \cap f^{-1}(V)$. $\square$

Note that we didn't have to show inclusion in both directions because the definitions we used are bidirectional $\iff$.

Show $f^{-1}(U \setminus V)= f^{-1}(U) \setminus f^{-1}(V)$

Let's apply Definition 3.4.5 to $f^{-1}(U \setminus V)$,

$$f^{-1}(U \setminus V) := \{x \in X: f(x) \in U \setminus V\}$$

This is the set of $x$ such that $f(x) \in U$ and $f(x) \notin V$. 

Let's consider the two cases, both of which must be true:

• $f(x) \in U$. Definition 3.4.5 tells us $f(x) \in U \iff x \in f^{-1}(U)$
• $f(x) \notin V$. Definition 3.4.5 tells us $f(x) \in U \iff x \notin f^{-1}(V)$

Since both of these are true, then both of the following are true:

• $x \in f^{-1}(U)$
• $x \notin f^{-1}(V)$

This is equivalent to $x \in f^{-1}(U) \setminus f^{-1}(V)$.

Thus, we have shown $f^{-1}(U \setminus V)= f^{-1}(U) \setminus f^{-1}(V)$. $\square$

Note that we didn't have to show inclusion in both directions because the definitions we used are bidirectional $\iff$.

Tao Analysis I - 3.4.3

Exercise 3.4.3

Let $A$, $B$ be two subsets of a set $X$, and let $f:X \to Y$ be a function. Show that $f(A \cap B) \subseteq f(A) \cap f(B)$, that $f(A) \setminus f(B) \subseteq f(A \setminus B)$, $f(A∪B)= f(A) \cup f(B)$. For the first two statements, is it true that the $\subseteq$ relation can be improved to $=$?

Before we dive into the exercise, let's draw a picture to aid our thinking.

Show that $f(A \cap B) \subseteq f(A) \cap f(B)$

We need to show that

$$y \in f(A \cap B) \implies y \in f(A) \cap f(B)$$

If $y \in f(A \cap B)$ then there exists an $x \in (A \cap B)$ such that $y = f(x)$. 

Now, 

$$x \in (A \cap B) \iff (x \in A) \land (x \in B)$$

So,

$$ y \in f(A \cap B) \implies (y \in f(A)) \land (y \in f(B))$$

Note, this is a one-way implication because for a function, given an element of the domain, we can only say there is only one element in the co-domain. For an element in the co-domain, we can't say there is only one corresponding element of the domain.

Thus, we have shown that if $y \in f(A \cap B)$ then $y \in f(A) \cap f(B)$. 

This is equivalent to $f(A \cap B) \subseteq f(A) \cap f(B)$. $\square$

Can $\subseteq$ be strengthened to $=$?  All we need is a counter-example to show this can't be done.

Consider $X=Y=\mathbb{Z}$, $A=\{-1\}$, $B=\{1\}$, with $f:x \mapsto x^2$. Here:

• $f(A \cap B) = f(\emptyset) = \emptyset$, the empty set.
• $f(A) \cap f(B) = \{1\} \cap \{1\} = \{1\}$.

Here $f(A) \cap f(B) \nsubseteq f(A \cap B)$, a counter-example showing that equality is not possible for general $f$. $\square$

As an extra exercise, let's ask if $f$ injective would enable equality? If $f$ is injective, by definition that means $f(s) = f(t) \implies s=t$.

So if $y \in f(A) \cap f(B)$ then $y \in f(A) \land y \in f(B)$. So both of the following must be true:

• There exists an $a \in A$ such that $y=f(a) \in f(A)$.
• There exists a $b \in B$ such that $y=f(b) \in f(B)$.

We have $y=f(a)=f(b)$, which, if $f$ is injective, means $a=b$. Now this $x=a=b$ is in both $A$ and $B$, that is $x \in (A \cap B)$. This gives us $y=f(x) \in f(A \cap B)$. 

So we have shown that if $f$ is injective, $f(A) \cap f(B) \subseteq f(A \cap B)$. This, combined with the previous result that $f(A \cap B) \subseteq f(A) \cap f(B)$, gives us equality $f(A \cap B) = f(A) \cap f(B)$. $\square$

Show that $f(A) \setminus f(B) \subseteq f(A \setminus B)$

We need to show that $y \in f(A) \setminus f(B) \implies y \in f(A \setminus B)$.

The meaning of $y \in f(A) \setminus f(B)$ is that $y \in f(A) \land y \notin f(B)$. 

This means both of the following are true:

• There exists an $x \in A$ such that $f(x) = y$.
• For all $x \in B$ it is the case that $f(x) \neq y$. (see note at bottom)

This, $x \in A \land x \notin B$. That is, $x \in (A \setminus B)$. This implies $f(x) = y \in f(A \setminus B)$. 

Thus we have shown that $f(A) \setminus f(B) \subseteq f(A \setminus B)$.

Can $\subseteq$ be strengthened to $=$?  All we need is a counter-example to show this can't be done.

Consider $X=Y=\mathbb{Z}$, $A=\{-1\}$, $B=\{1\}$, with $f:x \mapsto x^2$. Here:

• $f(A) \setminus f(B) = \{1\} \setminus \{1\} = \emptyset$, the empty set.
• $f(A \setminus B) = f(\{-1\} \setminus\{1\}) = f(\{-1\}) = \{1\}$.

Here $f(A \setminus B) \nsubseteq f(A) \setminus f(B)$, a counter-example showing that equality is not possible for general $f$. $\square$

Show that $f(A∪B)= f(A) \cup f(B)$

We need to show both:

• $y \in f(A \cup B) \implies y \in f(A) \cup f(B)$
• $y \in f(A) \cup f(B) \implies y \in f(A \cup B)$

If $y \in f(A \cup B)$ then there exists an $x \in A \cup B$ such that $y = f(x) \in f(A \cup B)$. That $x$ could be in $A$ or it could be in $B$, or both. That means $(x \in A) \lor (x \in B)$. Let's consider both cases:

• $x \in A \implies y = f(x) \in f(A) \in f(A) \cup f(B)$
• $x \in B \implies y = f(x) \in f(B) \in f(A) \cup f(B)$

This means $y = f(x) \in f(A) \cup f(B)$. 

We have shown $y \in f(A \cup B) \implies y \in f(A) \cup f(B)$.

If $y \in f(A) \cup f(B)$ that means $y \in f(A)$ or $y \in f(B)$, or both. Let's consider both cases.

• If $y \in f(A)$ then there exists an $x \in A$ such that $y = f(x) \in f(A) \in f(A) \cup f(B)$.
• If $y \in f(B)$ then there exists an $x \in B$ such that $y = f(x) \in f(B) \in f(A) \cup f(B)$.

This $x$ is in $A$ or $B$, or both. And both cases imply $y = f(x) \in f(A \cup B)$.

We have shown $y \in f(A) \cup f(B) \implies y \in f(A \cup B)$.

By showing both implications, we have shown $f(A∪B)= f(A) \cup f(B)$. $\square$

Note: Negation of Quantifiers

Above we said that the meaning of $y \in f(A) \setminus f(B)$ is that $y \in f(A) \land y \notin f(B)$. We then said this means both of the following are true:

• There exists an $x \in A$ such that $f(x) = y$.
• For all $x \in B$ it is the case that $f(x) \neq y$. 

For the second bullet point we used negation of quantifiers - we "swap the quantifiers and negate the predicate".

$$ \neg [\exists x: f(x)=y] \quad \iff \quad \forall x [f(x) \neq y]$$

You can read more here: (pdf) and (pdf).