Tao Analysis I - 3.1.9

Exercise 3.1.9

Let $A$, $B$, $X$ be sets such that $A \cup B = X$ and $A \cap B = \emptyset$. Show that $A = X \setminus B$ and $B = X \setminus A$.

Show that $A = X \setminus B$

Let's start by writing down the meaning of $A \cup B = X$,

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

and also the meaning of $A \cap B = \emptyset$,

$$\neg \exists x [(x \in A ) \land (x \in B)]$$

This is saying that there is no $x$ that is in both $A$ and $B$. We can write this as two separate statements,

$$x \in A \implies x \not \in B$$

$$x \in B \implies x \not \in A$$

Now, let's consider $A$.  From $x \in X \iff (x \in A) \lor (x \in B)$, we have

$$x \in A \implies x \in X$$

And we already have

$$x \in A \implies x \not \in B$$

These two statements are both be true, so we can write them as

$$x \in A  \implies (a \in X) \land (x \not \in B)$$

This gives us $A \subseteq X \setminus B$. 

We need to show $X \setminus B \subseteq A$. Let's consider $X \setminus B$,

$$(x \in X) \land (x \not \in B)$$

Using $x \in X \iff (x \in A) \lor (x \in B)$, we have two cases,  at least one of which is true,

• $x \in X \implies x \in A$
• $x \in X \implies x \in B$

The first case gives us

$$\begin{align}(x \in X) \land (x \not \in B) &\implies (x \in A) \land (x \not \in B) \\ \\ &\implies (x \in A) \end{align}$$

which confirms $X \setminus B \subseteq A$.

The second case gives us

$$(x \in X) \land (x \not \in B) \implies (x \in B) \land (x \not \in B)$$

which is a contradiction, meaning only the first case is true.

So having shown both $A \subseteq X \setminus B$, and $X \setminus B \subseteq A$, we can conclude $A = X \setminus B$. $\square$

Show that $B = X \setminus A$

We could prove this using the same logic as above, or we could simply use symmetry to argue that interchanging the variables $A$ and $B$ doesn't change the given information and constraints (because union and intersection are commutative), but does lead the desired conclusion. $\square$

Tao Analysis I - 3.1.8

Exercise 3.1.8

Let $A$, $B$ be sets. Prove the absorption laws $A \cap (A \cup B)=A$ and $A \cup (A \cap B)= A$.

Show $A \cap (A \cup B) = A$

Let's write out the LHS using the definitions of intersection and union (Definition 3.1.22, Axiom 3.5).

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

This tells us the following two statements are both true:

• $(x \in A)$
• $(x \in A) \lor (x \in B)$

Both statements are only true when $(x \in A)$. So we can say $A \cap (A \cup B) \implies A$.

We now need to show $A \implies A \cap (A \cup B)$. 

$$x \in A \implies x \in A \cup B$$

This is because, by definition, $A \subseteq A \cup X$ for any $X$. 

Furthermore, since $x \in A$ is true, we have

$$x \in A \implies (x \in A) \land (x \in A \cup B)$$

This is equivalent to $A \implies A \cap (A \cup B)$.

Having shown both  $A \cap (A \cup B) \implies A$ and $A \implies A \cap (A \cup B)$, we can conclude $A \cap (A \cup B) = A$. $\square$

Show $A \cup (A \cap B) = A$

Let's write out the LHS using the definitions of union and intersection.

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

This tells us that either, or both, of the following two statements are true:

• $(x \in A)$
• $(x \in A) \land (x \in B)$

These become two cases to consider. 

In the first case, $(x \in A)$, so $A \cup (A \cap B) \implies A$.

In the second case, $(x \in A) \land (x \in B) \implies $(x \in A)$, so again  $A \cup (A \cap B) \implies A$.

Both cases gives us $A \cup (A \cap B) \implies A$.

We now need to show $A \implies A \cup (A \cap B)$. This is straight forward, because $A \implies A \cup X$ for any $X$, by definition. So we have  $A \implies A \cup (A \cap B)$.

So having shown both $A \cup (A \cap B) \implies A$ and $A \implies A \cup (A \cap B)$, we can conclude $A \cup (A \cap B) = A$. $\square$

Note

The proof of the first identity can be shorted as follows:

Let's write out the LHS using the definitions of intersection and union (Definition 3.1.22, Axiom 3.5).

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

This tells us the following two statements are both true:

• $(x \in A)$
• $(x \in A) \lor (x \in B)$

Both statements are only true if and only if $(x \in A)$. That is,

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

So we can say $A \cap (A \cup B) = A$. $\square$

Tao Analysis I - 3.1.7

Exercise 3.1.7

Let $A$, $B$, $C$ be sets. Show that $A \cap B \subseteq A$ and $A \cap B \subseteq B$. Furthermore, show that $C \subseteq A$ and $C \subseteq B$ if and only if $C \subseteq A \cap B$. In a similar spirit, show that $A \subseteq A \cup B$ and $B \subseteq A \cup B$, and furthermore that $A \subseteq C$ and $B \subseteq C$ if and only if $A \cup B \subseteq C$.

Show $A \cap B \subseteq A$ and $A \cap B \subseteq B$

Let's start with Definition 3.1.22 of intersection,

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

Both $(x \in A)$ and $(x \in B)$ are true. This gives us

$$\begin{align}x \in (A \cap B) &\implies (x \in A) \\ \\ x \in (A \cap B) &\implies (x \in B) \end{align}$$

This is equivalent to the two statements we want to prove $A \cap B \subseteq A$ and $A \cap B \subseteq B$. $\square$

Show $C \subseteq A$ and $C \subseteq B$ if and only if $C \subseteq A \cap B$

Let's start by writing down the meanings of $C \subseteq A$ and $C \subseteq B$,

$$\begin{align}(x \in C) &\implies (x \in A) \\ \\ (x \in C) &\implies (x \in B)  \end{align}$$

Both of these statements are true, so we have

$$(x \in C) \implies (x \in A) \land (x \in B)$$

This gives us $(C \subseteq A) \land (C \subseteq B) \implies C \subseteq (A \cap B)$.

We now need to show $C \subseteq (A \cap B) \implies (C \subseteq A) \land (C \subseteq B)$. Let's apply the definition of intersection to $C \subseteq (A \cap B)$

$$\begin{align}x \in C &\implies x \in (A \cap B) \\ \\ & \implies (x \in A) \land (x \in B)\end{align}$$

This gives us two statements which are true,

$$\begin{align}(x \in C) &\implies (x \in A) \\ \\ (x \in C) &\implies (x \in B)  \end{align}$$

This is equivalent to $C \subseteq (A \cap B) \implies (C \subseteq A) \land (C \subseteq B)$.

Having shown both

$$(C \subseteq A) \land (C \subseteq B) \implies C \subseteq (A \cap B)$$

and

$$C \subseteq (A \cap B) \implies (C \subseteq A) \land (C \subseteq B)$$

we can conclude 

$$(C \subseteq A) \land (C \subseteq B) \iff C \subseteq (A \cap B) \; \square$$

Show $A \subseteq A \cup B$ and $B \subseteq A \cup B$

The definition of union, Axiom 3.5, tells us that $x \in X \implies x \in (X \cup Y)$ for any $Y$. 

So we have

$$\begin{align}x \in A &\implies x \in (A \cup B) \\ \\ x \in B &\implies x \in (A \cup B) \end{align}$$

This immediately gives us $A \subseteq A \cup B$ and $B \subseteq A \cup B$. $\square$

Show $A \subseteq C$ and $B \subseteq C$ if and only if $A \cup B \subseteq C$

Let's start by writing down the meanings of $A \subseteq C$ and $B \subseteq C$,

$$\begin{align}(x \in A) &\implies (x \in C) \\ \\ (x \in B) &\implies (x \in C)  \end{align}$$

Either, or both, statements $(x \in A)$ and $(x \in B)$ implies $(x \in C)$, which we write as

$$(x \in A) \lor (x \in B) \implies (x \in C)$$

This is equivalent to $(A \subseteq C) \lor (B \subseteq C) \implies (A \cup B \subseteq C)$.

We need to show also $(A \cup B \subseteq C) \implies (A \subseteq C) \lor(B \subseteq C)$. Let's apply the definition of union,

$$(x \in A) \lor (x \in B) \implies x \in C$$

This tells us that either, or both, $(x \in A) \implies (x \in C) $ and $(x \in B) \implies (x \in C)$ are true. That is, $(A \subseteq C) \lor(B \subseteq C)$.

Having shown both

$$(A \subseteq C) \lor (B \subseteq C) \implies (A \cup B \subseteq C)$$

and

$$(A \cup B \subseteq C) \implies (A \subseteq C) \lor(B \subseteq C)$$

we can conclude

$$A \subseteq C \land B \subseteq C \iff A \cup B \subseteq C \; \square$$

Tao Analysis I - 3.1.6

Exercise 3.1.6

Prove Proposition 3.1.27. (Hint: one can use some of these claims to prove others. Some of the claims have also appeared previously in Lemma 3.1.12.)

Let's write out Proposition 3.1.27.

Proposition 3.1.27 (Sets form a boolean algebra). Let $A$, $B$, $C$ be sets, and let $X$ be a set containing $A$, $B$, $C$ as subsets.

(a) (Minimal element) We have $A\cup \emptyset = A$ and $A \cap \emptyset = \emptyset$.

(b) (Maximal element)We have $A \cup X = X$ and $A \cap X=A$.

(c) (Identity) We have $A \cap A=A$ and $A \cup A=A$.

(d) (Commutativity) We have $A \cup B=B \cup A$ and $A \cap B=B \cap A$.

(e) (Associativity) We have $(A \cup B) \cup C = A \cup (B \cup C)$ and $(A \cap B) \cap C = A \cap (B \cap C)$.

(f) (Distributivity) We have $A \cap (B \cup C)=(A \cap B) \cup (A \cap C)$ and $A \cup (B \cap C)=(A \cup B) \cap (A \cup C)$.

(g) (Partition) We have $A \cup (X \setminus A) = X$ and $A \cap (X \setminus A) = \emptyset$.

(h) (De Morgan laws) We have $X \setminus (A \cup B)=(X \setminus A) \cap (X \setminus B)$ and $X \setminus (A \cap B)=(X \setminus A) \cup (X \setminus B)$.

Let's prove each in turn.

(a) Minimal Element

We need to show $A\cup \emptyset = A$ and $A \cap \emptyset = \emptyset$.

Let's start with the first and use the definition of a pairwise union, Axiom 3.5.

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

The definition of an empty set, Axiom 3.5, tells us that an empty set has no members. That is, $x \in \emptyset$ is never true. So the above simplifies to

$$x \in (A\cup \emptyset) \iff (x \in A)$$

Thus $A\cup \emptyset = A$. $\square$

Now let's consider $A \cap \emptyset = \emptyset$ and use the definition of intersection, Definition 3.1.22.

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

The definition of an empty set, Axiom 3.5, tell us that an empty set has no members. So the expression $(x \in A) \land (x \in \emptyset)$ is always false. That is, $x \in (A\cap \emptyset)$ is never true. 

Thus $A\cap \emptyset = \emptyset$. $\square$

(b) Maximal Element

We  need to show $A \cup X = X$ and $A \cap X=A$.

We have already shown in Exercise 3.1.5 that $A \subseteq B$, $A \cup B=B$, $A \cap B=A$ are logically equivalent. Here we have $A \subseteq X$ and so $A \cup X=X$, $A \cap X=A$ are true. $\square$

(c) Identity

We need to show $A \cap A=A$ and $A \cup A=A$.

Let's use the definition of a pairwise union, Axiom 3.5, and equate $A = B$.

$$\begin{align}x \in (A \cup A) &\iff (x \in A) \lor (x \in A) \\ \\ & \iff (x \in A) \end{align}$$

This gives us $A \cap A=A$. $\square$

Now let's use the definition of intersection, Definition 3.1.22, and equate $A=B$.

$$\begin{align}x \in (A \cap A) &\iff (x \in A) \land (x \in A) \\ \\ & \iff (x \in A) \end{align}$$

This gives us $A \cup A=A$. $\square$

(d) Commutativity

We need to show $A \cup B=B \cup A$ and $A \cap B=B \cap A$.

Let's use the definition of a pairwise union, Axiom 3.5.

$$\begin{align}x \in (A \cup B) &\iff (x \in A) \lor (x \in B) \\ \\ & \iff (x \in B) \lor (x \in A) \end{align}$$

The second line is justified because logical disjunction is commutative.

So we have  $A \cup B=B \cup A$. $\square$

Now let's use the definition of intersection, Definition 3.1.22.

$$\begin{align}x \in (A \cup B) &\iff (x \in A) \land (x \in B) \\ \\ & \iff (x \in B) \land (x \in A)  \end{align}$$

The second line is justified because logical conjunction is commutative.

So we have  $A \cap B=B \cap A$. $\square$

(e) Associativity

We need to show $(A \cup B) \cup C = A \cup (B \cup C)$ and $(A \cap B) \cap C = A \cap (B \cap C)$.

The first identity that union is associative is Lemma 3.1.12 proven in the text. 

Now we turn to the second identity $(A \cap B) \cap C = A \cap (B \cap C)$. Using Definition 3.1.22 of intersection,

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

This gives us $x \in C$.

Considering $(A \cap B)$,

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

This gives us $x \in A$ and $x \in B$.

So in summary we have that all $x \in A$,  $x \in B$ and $x \in C$ are true.

Using $x \in B$ and $x \in C$, and Definition 3.1.22 of intersection,

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

And using $x \in A$,

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

That is, $(A \cap B) \cap C = A \cap (B \cap C)$. $\square$

(f) Distributivity

We need to show $A \cap (B \cup C)=(A \cap B) \cup (A \cap C)$ and $A \cup (B \cap C)=(A \cup B) \cap (A \cup C)$.

Let's start with the first identity, and use Definition 3.1.22 of intersection,

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

This gives us $x \in A$ as true, as well as $x \in (B \cup C)$.

Consider $(B \cup C)$ and use the definition of a pairwise union, Axiom 3.5,

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

This gives us two combinations, at least one of which must be true

• $(x \in A) \land (x \in B)$
• $(x \in A) \land (x \in C)$

"At least one of which must be true" means a disjunction between the two statements.

$$x \in (A \cap (B \cup C)) \iff (x \in A \land x\in B) \lor (x \in A \land x\in C)$$

This proves the first identity $A \cap (B \cup C)=(A \cap B) \cup (A \cap C)$. $\square$.

Now let's consider the RHS of the second identity, and use Definition 3.1.22 of intersection,

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

Applying the definition of union Axiom 3.5, we have two combinations, both of which must be true

• $x \in A \lor x \in B$
• $x \in A \lor x \in C$

If $x \in A$ then both of these statements are true. If $x \not \in A$, then both statements are only true if $x \in B$ and $x \in C$.  That is, $(x \in A) \lor ((x \in B) \land (x \in C))$.

So we have shown, $A \cup (B \cap C)=(A \cup B) \cap (A \cup C)$. $\square$

(g) Partition

We need to show $A \cup (X \setminus A) = X$ and $A \cap (X \setminus A) = \emptyset$.

Let's start with the first identity $A \cup (X \setminus A) = X$, and use Axiom 3.5 which defines union,

$$x \in (A \cup (X \setminus A)) \iff (x \in A) \lor (x \in X \setminus A)$$

Since $A \subseteq X$, we have $x \in A \implies x \in X$, which gives us

$$\begin{align}x \in (A \cup (X \setminus A)) &\implies (x \in X) \lor (x \in X \setminus A) \\ \\ &\implies x \in X\end{align}$$

The last step is true because $x \in X$ is true, or $x \in X \setminus A$ is true, and in both cases $x \in X$.

So we have $A \cup (X \setminus A) \subseteq X$. We now need to show $X \subseteq A \cup (X \setminus A)$.

Consider $x \in X$. Since $A \subseteq X$, we have $(x \in A) \lor (x \not \in A)$. The case $(x \not \in A)$ combined with $x \in X$, which is true by hypothesis, gives us $(x \in X \setminus A)$. So we have

$$x \in X \implies (x \in A) \lor (x \in X \setminus A)$$

That is, $X \subseteq A \cup (X \setminus A)$. 

Having shown both $A \cup (X \setminus A) \subseteq X$, and  $X \subseteq A \cup (X \setminus A)$, we can conclude $A \cup (X \setminus A) = X$. $\square$

Now let's consider the second identity $A \cap (X \setminus A) = \emptyset$, and use Definition 3.1.22 of intersection,

$$x \in (A \cap (X \setminus A)) \iff (x \in A) \land (x \in X \setminus A)$$

So both $(x \in A)$ and $(x \in X \setminus A)$ must be true. However, Definition 3.1.26 for set difference tells us that $(x \in X \setminus A)$ means $(x \not \in A)$. The only solution to this apparent contradiction is if $x \in \emptyset$. 

So we have $A \cap (X \setminus A) = \emptyset$. $\square$

(h) De Morgan's Laws

We need to show $X \setminus (A \cup B)=(X \setminus A) \cap (X \setminus B)$ and $X \setminus (A \cap B)=(X \setminus A) \cup (X \setminus B)$.

Let's start with the first identity $X \setminus (A \cup B)=(X \setminus A) \cap (X \setminus B)$, and use the Definition 3.1.26 for set difference.

$$x \in (X \setminus (A \cup B)) \iff (x \in X) \land (x \not \in (A \cup B))$$

Both statements $(x \in X)$ and $(x \not \in (A \cup B))$ must be true. Let's consider the second statement.

$$\begin{align}(x \not \in (A \cup B)) &\iff \neg((x \in A) \lor (x \in B)) \\ &\iff (x \not \in A) \land (x \not \in B)\end{align}$$

This is because $\neg(P \lor Q) \equiv (\neg P) \land (\neg Q)$.

We can write these as two combined statements, both of which must be true.

• $(x \in X) \land (x \not \in A)$
• $(x \in X) \land (x \not \in B)$

Which is equivalent to $(X \setminus A) \cap (X \setminus B)$.

So we have shown $X \setminus (A \cup B)=(X \setminus A) \cap (X \setminus B)$. $\square$

Now let's consider the second identity $X \setminus (A \cap B)=(X \setminus A) \cup (X \setminus B)$, and use the Definition 3.1.26 for set difference.

$$x \in (X \setminus (A \cap B)) \iff (x \in X) \land (x \not \in (A \cap B))$$

Both statements $(x \in X)$ and $(x \not \in (A \cap B))$ must be true. Let's consider the second statement.

$$\begin{align}(x \not \in (A \cap B)) &\iff \neg((x \in A) \land (x \in B)) \\ &\iff (x \not \in A) \lor (x \not \in B)\end{align}$$

This is because $\neg(P \land Q) \equiv (\neg P) \lor (\neg Q)$.

We can write these as two combined statements, at least one of which must be true.

• $(x \in X) \land (x \not \in A)$
• $(x \in X) \land (x \not \in B)$

Which is equivalent to $(X \setminus A) \cup (X \setminus B)$.

So we have shown $X \setminus (A \cap B)=(X \setminus A) \cup (X \setminus B)$. $\square$

Tao Analysis I - 3.1.5

Exercise 3.1.5

Let A, B be sets. Show that the three statements $A \subseteq B$, $A \cup B=B$, $A \cap B=A$ are logically equivalent (any one of them implies the other two).

Approach

There are three statements we need to show are equivalent. 

• $S_1: A \subseteq B$
• $S_2: A \cup B=B$
• $S_3: A \cap B=A$

To show an equivalence between two statements $S_i \iff S_j$ we need to show $S_i \implies S_j$ and $S_j \implies S_i$. This would suggest showing six implications in total. However, we only need to show the following three implications:

• $S_1 \implies S_2$
• $S_2 \implies S_3$
• $S_3 \implies S_1$

This is equivalent to showing equivalence amongst all $S_1$, $S_2$ and $S_3$, because there is a chain of implications between any $S_i$ and $S_j$, and also $S_j$ and $S_i$. For example $S_1 \implies S_2$ and $S_2 \implies S_3 \implies S_1$.

Show $S_1 \implies S_2$

Using $A \subseteq B$, we need to show both $A \cup B \subseteq B$ and $B \subseteq A \cup B$.

Let's start with the definition of $A \cup B$

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

By hypothesis we have $A \subseteq B$, which is defined as

$$(A \subseteq B) \implies [(x \in A) \implies (x \in B)]$$

Or more simply, whenever we have $x \in A$, we can substitute $x \in B$.

So, substituting into the definition of union, we have

$$\begin{align}x \in (A \cup B) &\iff (x \in A) \lor (x \in B) \\ \\ &\implies (x \in B) \lor (x \in B) \\ \\ & \implies x \in B \end{align}$$

So $A \cup B \subseteq B$ if we're given $A \subseteq B$.

Now we need to show $B \subseteq A \cup B$. Let's consider

$$(x \in A) \implies (x \in A) \lor (x \in B)$$

This is true by definition of disjunction. In fact $(x \in A) \implies (x \in A) \lor (x \in C)$ for any $C$.

So $B \subseteq A \cup B$. Notice we didn't need to use $A \subseteq B$ here.

We have shown both $A \cup B \subseteq B$ and $B \subseteq A \cup B$, from which we conclude $A \cup B = B$. So $A \subseteq B \implies A \cup B=B$. $\square$

Show $S_2 \implies S_3$

Using $A \cup B=B$, we need to show $A \cap B = A$. To do this we need to show both $A \cap B \subseteq A$ and $A \subseteq A \cap B$.

Let's start with the definition of $A \cap B$.

$$\begin{align}x \in (A \cap B) &\iff (x \in A) \land (x \in B) \\ \\ &\implies (x \in A)\end{align}$$

Thus $A \cap B \subseteq A$.

Now let's show $A \subseteq A \cap B$.

Using the definition of disjunction, we have $A \subseteq A \cup B$. But by hypothesis, $A \cup B=B$, so we have recovered $S_1: A \subseteq B$.

Now let's consider the following which looks obvious,

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

Using  $S_1: A \subseteq B$, that is $(x \in A) \implies (x \in B)$, we can substitute $x \in B$ for $x \in A$,

$$(x \in A) \implies (x \in A) \land (x \in B)$$

That is, $A \subseteq A \cap B$.

We have shown both $A \cap B \subseteq A$, and $A \subseteq A \cap B$, from which we conclude $A \cap B = A$. $\square$

Show $S_3 \implies S_1$

Using $A \cap B=A$, we need to show $A \subseteq B$. This is not an equality so we don't need to show $B \subseteq A$, which is, in any case, false.

Using the hypotheses $A = A \cap B$, we immediately have

$$\begin{align}(x \in A) &\implies (x \in A) \land (x \in B) \\ \\ &\implies (x \in B)\end{align}$$

That is $A \subseteq B$. $\square$

Conclusion

We have shown the three implications, 

• $S_1 \implies S_2$
• $S_2 \implies S_3$
• $S_3 \implies S_1$

Thereby we have shown the three statements $A \subseteq B$, $A \cup B=B$, $A \cap B=A$ are logically equivalent. 

Tao Analysis I - 3.1.4

Exercise 3.1.4

Prove the remaining claims in Proposition 3.1.17

Let's write out Proposition 3.1.17.

Proposition 3.1.17 (Sets are partially ordered by set inclusion). Let $A$, $B$, $C$ be sets. If $A \subseteq B$ and $B \subseteq C$ then $A \subseteq C$. If $A \subseteq B$ and $B \subseteq A$, then $A = B$. Finally, if $A \subsetneq B$ and $B \subsetneq C$ then $A \subsetneq C$.

Note: the symbol $\subsetneq$ means proper subset, that is subset but not equal.

The textbook proofs the first claim. We'll prove the remaining two.

Show that if $A \subseteq B$ and $B \subseteq A$, then $A = B$

Let's write out the antecedent of this claim

$$(A \subseteq B) \land (B \subseteq A)$$

If $x \in A$ then by $(A \subseteq B)$ we have $x \in B$. Similarly, if $x \in B$ then by $(B \subseteq A)$ we have $x \in A$.

So we have the following

$$(x \in A \implies x \in B) \land (x \in B \implies x \in A)$$

That is,

$$x \in A \iff x \in B$$

This is simply stating that $A=B$ by Axiom 3.2 which defines equal sets. Thus we have shown that if $A \subseteq B$ and $B \subseteq A$, then $A = B$. $\square$

Show that if $A \subsetneq B$ and $B \subsetneq C$ then $A \subsetneq C$

To show $A \subsetneq C$ we need to show

• if $x \in A$ then $x \in C$, that is $A \subseteq C$
• but there exists a $y \in C$ that is not in $A$, that is $A \neq B$

Let's start with the first statement. If $x \in A$ then by $A \subsetneq B$ we have $x \in B$. Also, if $x \in B$ then by $B \subsetneq C$ we have $x \in C$. So $x \in A \implies x \in C$.

Now let's address the second statement. $B \subsetneq C$ tells us that there exists a $y \in C$ that is not in $B$. But $A \subsetneq B$ tells us every element $x \in A$ is also in $B$. So every $x \in A$ is in $B$ but not every $y \in C$ is in $B$. That is, there exists a $y \in C$ that is not in $A$.

We have shown  $A \subsetneq B$ and $B \subsetneq C$ then $A \subsetneq C$. $\square$

Tao Analysis I - 3.1.3

Exercise 3.1.3

Prove the remaining claims in Lemma 3.1.12.

Let's write out Lemma 3.1.12.

Lemma 3.1.12 If $a$ and $b$ are objects, then $\{a,b\}=\{a\} \cup \{b\}$. If $A$, $B$, $C$ are sets, then the union operation is commutative (i.e., $A \cup B = B \cup A$) and associative (i.e., $(A \cup B) \cup C = A \cup (B \cup C)$). Also, we have $A \cup A = A \cup \emptyset = \emptyset \cup A = A$.

The textbook provides a proof that union is associative. We'll prove the remaining claims.

Show $\{a,b\}=\{a\} \cup \{b\}$

Axiom 3.4 defining pair sets tells us that the only elements of $\{a,b\}$ are $a$ and $b$. That is

$$x \in \{a,b\} \iff (x=a \lor x=b)$$

Axiom 3.4 defining singletons tells us

$$\begin{align}x \in \{a\} &\iff x=a \\ \\ x \in \{b\} &\iff x=b\end{align}$$

Axiom 3.5 defines pairwise union as follows

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

Thus

$$x \in (\{a\} \cup \{b\}) \iff ((x \in \{a\}) \lor (x \in \{b\}))$$

This is equivalent to the following (Axiom 3.4),

$$x \in (\{a\} \cup \{b\}) \iff ((x = a) \lor (x=b))$$

And by Axiom 3.4 again,

$$x \in (\{a\} \cup \{b\}) \iff ((x = a) \lor (x=b)) \iff x \in \{a,b\}$$

We have shown $\{a,b\}=\{a\} \cup \{b\}$. $\square$

Union is Commutative $A \cup B = B \cup A$

We want to prove $A \cup B = B \cup A$.

By Axiom 3.5 which defines pairwise union we have

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

Because  logical disjunction $\lor$ is commutative, we have

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

By Axiom 3.5, we also have

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

These three statements give us

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

That is, $A \cup B = B \cup A$. $\square$

Show  $A \cup A = A \cup \emptyset = \emptyset \cup A = A$

We have already shown that pairwise union is commutative, so we don't need to show again that

$$A \cup \emptyset = \emptyset \cup A \; \square$$

Let's use Axiom 3.5 which defines union to write

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

We can simplify the RHS,

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

This is simply stating that

$$A \cup A = A \; \square$$

All that remains is to show $A \cup \emptyset = A$. Let's again use Axiom 3.5 which defines union to write

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

Since there is no $x \in \emptyset$ by Axiom 3.3 which defines the empty set, we can simplify the RHS,

$$x \in (A \cup \emptyset) \iff (x \in A)$$

This is simply stating that

$$A \cup \emptyset = A \; \square$$

Tao Analysis I - 3.1.2

Exercise 3.1.2

Using only Axiom 3.2, Axiom 3.1, Axiom 3.3, and Axiom 3.4, prove that the sets $\emptyset$, $\{ \emptyset \}$, $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$ are all distinct (i.e., no two of them are equal to each other).

Let's remind ourselves of Axioms 3.1-3.4,

• Axiom 3.1 (Sets are objects). If A is a set, then A is also an object.
• Axiom 3.2 (Equality of sets). Two sets $A$ and $B$ are equal, $A=B$, iff every element of $A$ is an element of $B$ and vice versa.
• Axiom 3.3 (Empty set). There exists a set $\emptyset$, known as the empty set, which contains no elements, i.e., for every object $x$ we have $x \not \in \emptyset$.
• 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\}$ iff $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\}$ iff $y = a$ or $y = b$; we refer to this set as the pair set formed by $a$ and $b$.

Show $\emptyset$ is different from $\{ \emptyset \}$, $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$.

Let's first show that $\emptyset$ is not equal to any of $\{ \emptyset \}$, $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$. 

Axiom 3.3 defines the empty set as having no members. That means no element of any other set can be a member of $\emptyset$.

The other sets do have members by Axiom 3.4. To be specific, $\emptyset \in \{ \emptyset \}$, $\{ \emptyset \} \in \{\{ \emptyset \}\}$ and $\emptyset \in \{ \emptyset, \{ \emptyset \} \}$. 

Axiom 3.2 on set equality requires equal sets to have all their members in common. So $\emptyset$ is different from all the others - because all the other sets have members, and $\emptyset$ has no members.

Having dealt with $\emptyset$, we can now remove it from the list and consider the remaining sets $\{ \emptyset \}$, $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$.

For the rest of this exercise we won't explicitly state that we're using Axiom 3.4 to say that a singleton set $\{a\}$ has a member $a$, and that a pair set $\{a,b\}$ has members $a$ and $b$.

Show $\{\emptyset\}$ is different from $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$.

Let's show that $\{\emptyset\}$ is not equal to any of $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$. 

The element $\{ \emptyset \}$ of $\{\{ \emptyset \}\}$ is not a member of $\{\emptyset\}$. Similarly, the element $\emptyset$ of $\{ \emptyset, \{ \emptyset \} \}$ is not a member of $\{ \emptyset \}$. So by Axiom 3.2, $\{\emptyset\}$ is not equal to any of $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$.

Having dealt with $\{\emptyset\}$, we can now remove it from the list and consider the remaining sets $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$.

Show $\{\{ \emptyset \}\}$ is different from $\{ \emptyset, \{ \emptyset \} \}$.

Let's show that $\{\{ \emptyset \}\}$ is not equal to $\{ \emptyset, \{ \emptyset \} \}$.

We could say the sets are not equal because their cardinalities are different. That is, $|\{\{ \emptyset \}\}|=1$ and $|\{ \emptyset, \{ \emptyset \} \}|=2$. However we haven't covered cardinality in the book yet so we must rely only on the Axioms 3.1-3.4, 

We can see the element $\emptyset$ of $\{ \emptyset, \{ \emptyset \} \}$ is not a member of $\{\{ \emptyset \}\}$. So by Axiom 3.2, $\{\{ \emptyset \}\}$ is not equal to $\{ \emptyset, \{ \emptyset \} \}$.

All the results above show that no two of the given sets are equal. $\square$

Tao Analysis I - 3.1.1

Exercise 3.1.1

Let $a$, $b$, $c$, $d$ be objects such that $\{a, b\} = \{c, d\}$. Show that at least one of the two
statements “$a = c$ and $b = d$” and “$a = d$ and $b = c$” hold.

Let's start with the definition of the equality of two sets.

Axiom 3.2 (Equality of sets).Two sets $A$ and $B$ are equal, $A=B$, iff every element of $A$ is an element of $B$ and vice versa.

Let's apply this definition our scenario:

1. $a$ is a member of $\{c,d\}$. That means $(a=c) \lor (a=d)$ is true.
2. $b$ is a member of $\{c,d\}$. That means $(b=c) \lor (b=d)$ is true.
3. $c$ is a member of $\{a,b\}$. That means $(c=a) \lor (c=b)$ is true.
4. $d$ is a member of $\{a,b\}$. That means $(d=a) \lor (d=b)$ is true.

The key to this exercise is recognising that all four statements must be true.

Let's start by considering the case $a=c$, which makes (1) true. It also makes (3) true. How we ensure (2) and (4) are also true? This is only possible when $b=d$. Thus the statement  “$a = c$ and $b = d$” satisfies the definition of set equality.

Let's consider the case $a=d$ which makes (1) true. It also makes (4) true. How do we ensure (2) and (3) are true? This is only possible when $b=c$. Thus the statement  “$a = d$ and $b = c$” satisfies the definition of set equality.

Can both statements be true at the same time? Let's start with $a=c$ from the first statement. The second statement gives us $b=c$. The first statement then gives us $b=d$. That is, $a=b=c=d$ also satisfies the equality of sets.

We have shown that the set equality $\{a, b\} = \{c, d\}$ means at least one of the statements “$a = c$ and $b = d$” and “$a = d$ and $b = c$” holds. $\square$