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.