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=\mathrm{\varnothing }$. 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⟺(x\in A)\vee (x\in B)$$

and also the meaning of $A\cap B=\mathrm{\varnothing }$,

$$\mathrm{\neg }\mathrm{\exists }x[(x\in A)\wedge (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⟹x\notin B$$

$$x\in B⟹x\notin A$$

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

$$x\in A⟹x\in X$$

And we already have

$$x\in A⟹x\notin B$$

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

$$x\in A⟹(a\in X)\wedge (x\notin 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)\wedge (x\notin B)$$

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

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

The first case gives us

$$\begin{array}{rl}(x\in X)\wedge (x\notin B)& ⟹(x\in A)\wedge (x\notin B)\\ \\ & ⟹(x\in A)\end{array}$$

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

The second case gives us

$$(x\in X)\wedge (x\notin B)⟹(x\in B)\wedge (x\notin 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$. $◻$

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

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))⟺(x\in A)\wedge ((x\in A)\vee (x\in B))$$

This tells us the following two statements are both true:

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

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

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

$$x\in A⟹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⟹(x\in A)\wedge (x\in A\cup B)$$

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

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

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))⟺(x\in A)\vee ((x\in A)\wedge (x\in B))$$

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

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

These become two cases to consider. 

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

In the second case, $(x\in A)\wedge (x\in B)⟹$(x \in A)$,soagain$A \cup (A \cap B) \implies A$.

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

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

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

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))⟺(x\in A)\wedge ((x\in A)\vee (x\in B))$$

This tells us the following two statements are both true:

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

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

$$(x\in A)\wedge ((x\in A)\vee (x\in B))⟺(x\in A)$$

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

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)⟺(x\in A)\wedge (x\in B)$$

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

$$\begin{array}{rl}x\in (A\cap B)& ⟹(x\in A)\\ \\ x\in (A\cap B)& ⟹(x\in B)\end{array}$$

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

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{array}{rl}(x\in C)& ⟹(x\in A)\\ \\ (x\in C)& ⟹(x\in B)\end{array}$$

Both of these statements are true, so we have

$$(x\in C)⟹(x\in A)\wedge (x\in B)$$

This gives us $(C\subseteq A)\wedge (C\subseteq B)⟹C\subseteq (A\cap B)$.

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

$$\begin{array}{rl}x\in C& ⟹x\in (A\cap B)\\ \\ & ⟹(x\in A)\wedge (x\in B)\end{array}$$

This gives us two statements which are true,

$$\begin{array}{rl}(x\in C)& ⟹(x\in A)\\ \\ (x\in C)& ⟹(x\in B)\end{array}$$

This is equivalent to $C\subseteq (A\cap B)⟹(C\subseteq A)\wedge (C\subseteq B)$.

Having shown both

$$(C\subseteq A)\wedge (C\subseteq B)⟹C\subseteq (A\cap B)$$

and

$$C\subseteq (A\cap B)⟹(C\subseteq A)\wedge (C\subseteq B)$$

we can conclude 

$$(C\subseteq A)\wedge (C\subseteq B)⟺C\subseteq (A\cap B)◻$$

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⟹x\in (X\cup Y)$ for any $Y$. 

So we have

$$\begin{array}{rl}x\in A& ⟹x\in (A\cup B)\\ \\ x\in B& ⟹x\in (A\cup B)\end{array}$$

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

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{array}{rl}(x\in A)& ⟹(x\in C)\\ \\ (x\in B)& ⟹(x\in C)\end{array}$$

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

$$(x\in A)\vee (x\in B)⟹(x\in C)$$

This is equivalent to $(A\subseteq C)\vee (B\subseteq C)⟹(A\cup B\subseteq C)$.

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

$$(x\in A)\vee (x\in B)⟹x\in C$$

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

Having shown both

$$(A\subseteq C)\vee (B\subseteq C)⟹(A\cup B\subseteq C)$$

and

$$(A\cup B\subseteq C)⟹(A\subseteq C)\vee (B\subseteq C)$$

we can conclude

$$A\subseteq C\wedge B\subseteq C⟺A\cup B\subseteq C◻$$

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 \mathrm{\varnothing }=A$ and $A\cap \mathrm{\varnothing }=\mathrm{\varnothing }$.

(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)=\mathrm{\varnothing }$.

(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 \mathrm{\varnothing }=A$ and $A\cap \mathrm{\varnothing }=\mathrm{\varnothing }$.

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

$$x\in (A\cup \mathrm{\varnothing })⟺(x\in A)\vee (x\in \mathrm{\varnothing })$$

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

$$x\in (A\cup \mathrm{\varnothing })⟺(x\in A)$$

Thus $A\cup \mathrm{\varnothing }=A$. $◻$

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

$$x\in (A\cap \mathrm{\varnothing })⟺(x\in A)\wedge (x\in \mathrm{\varnothing })$$

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

Thus $A\cap \mathrm{\varnothing }=\mathrm{\varnothing }$. $◻$

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

(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{array}{rl}x\in (A\cup A)& ⟺(x\in A)\vee (x\in A)\\ \\ & ⟺(x\in A)\end{array}$$

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

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

$$\begin{array}{rl}x\in (A\cap A)& ⟺(x\in A)\wedge (x\in A)\\ \\ & ⟺(x\in A)\end{array}$$

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

(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{array}{rl}x\in (A\cup B)& ⟺(x\in A)\vee (x\in B)\\ \\ & ⟺(x\in B)\vee (x\in A)\end{array}$$

The second line is justified because logical disjunction is commutative.

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

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

$$\begin{array}{rl}x\in (A\cup B)& ⟺(x\in A)\wedge (x\in B)\\ \\ & ⟺(x\in B)\wedge (x\in A)\end{array}$$

The second line is justified because logical conjunction is commutative.

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

(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⟺(x\in A\cap B)\wedge (x\in C)$$

This gives us $x\in C$.

Considering $(A\cap B)$,

$$x\in (A\cap B)⟺(x\in A)\wedge (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)\wedge (x\in C)⟺x\in (B\cap C)$$

And using $x\in A$,

$$(x\in A)\wedge (x\in B\cap C)⟺x\in A\cap (B\cap C)$$

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

(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))⟺(x\in A)\wedge (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)⟺(x\in B)\vee (x\in C)$$

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

• $(x\in A)\wedge (x\in B)$
• $(x\in A)\wedge (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))⟺(x\in A\wedge x\in B)\vee (x\in A\wedge x\in C)$$

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

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))⟺(x\in (A\cup B))\wedge (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\vee x\in B$
• $x\in A\vee x\in C$

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

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

(g) Partition

We need to show $A\cup (X\setminus A)=X$ and $A\cap (X\setminus A)=\mathrm{\varnothing }$.

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))⟺(x\in A)\vee (x\in X\setminus A)$$

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

$$\begin{array}{rl}x\in (A\cup (X\setminus A))& ⟹(x\in X)\vee (x\in X\setminus A)\\ \\ & ⟹x\in X\end{array}$$

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)\vee (x\notin A)$. The case $(x\notin A)$ combined with $x\in X$, which is true by hypothesis, gives us $(x\in X\setminus A)$. So we have

$$x\in X⟹(x\in A)\vee (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$. $◻$

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

$$x\in (A\cap (X\setminus A))⟺(x\in A)\wedge (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\notin A)$. The only solution to this apparent contradiction is if $x\in \mathrm{\varnothing }$. 

So we have $A\cap (X\setminus A)=\mathrm{\varnothing }$. $◻$

(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))⟺(x\in X)\wedge (x\notin (A\cup B))$$

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

$$\begin{array}{rl}(x\notin (A\cup B))& ⟺\mathrm{\neg }((x\in A)\vee (x\in B))\\ & ⟺(x\notin A)\wedge (x\notin B)\end{array}$$

This is because $\mathrm{\neg }(P\vee Q)\equiv (\mathrm{\neg }P)\wedge (\mathrm{\neg }Q)$.

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

• $(x\in X)\wedge (x\notin A)$
• $(x\in X)\wedge (x\notin 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)$. $◻$

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))⟺(x\in X)\wedge (x\notin (A\cap B))$$

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

$$\begin{array}{rl}(x\notin (A\cap B))& ⟺\mathrm{\neg }((x\in A)\wedge (x\in B))\\ & ⟺(x\notin A)\vee (x\notin B)\end{array}$$

This is because $\mathrm{\neg }(P\wedge Q)\equiv (\mathrm{\neg }P)\vee (\mathrm{\neg }Q)$.

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

• $(x\in X)\wedge (x\notin A)$
• $(x\in X)\wedge (x\notin 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)$. $◻$

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⟺S_j$ we need to show $S_i⟹S_j$ and $S_j⟹S_i$. This would suggest showing six implications in total. However, we only need to show the following three implications:

• $S_1⟹S_2$
• $S_2⟹S_3$
• $S_3⟹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⟹S_2$ and $S_2⟹S_3⟹S_1$.

Show $S_1⟹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)⟺(x\in A)\vee (x\in B)$$

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

$$(A\subseteq B)⟹[(x\in A)⟹(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{array}{rl}x\in (A\cup B)& ⟺(x\in A)\vee (x\in B)\\ \\ & ⟹(x\in B)\vee (x\in B)\\ \\ & ⟹x\in B\end{array}$$

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)⟹(x\in A)\vee (x\in B)$$

This is true by definition of disjunction. In fact $(x\in A)⟹(x\in A)\vee (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⟹A\cup B=B$. $◻$

Show $S_2⟹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{array}{rl}x\in (A\cap B)& ⟺(x\in A)\wedge (x\in B)\\ \\ & ⟹(x\in A)\end{array}$$

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)⟺(x\in A)\wedge (x\in A)$$

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

$$(x\in A)⟹(x\in A)\wedge (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$. $◻$

Show $S_3⟹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{array}{rl}(x\in A)& ⟹(x\in A)\wedge (x\in B)\\ \\ & ⟹(x\in B)\end{array}$$

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

Conclusion

We have shown the three implications, 

• $S_1⟹S_2$
• $S_2⟹S_3$
• $S_3⟹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⊊B$ and $B⊊C$ then $A⊊C$.

Note: the symbol $⊊$ 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)\wedge (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⟹x\in B)\wedge (x\in B⟹x\in A)$$

That is,

$$x\in A⟺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$. $◻$

Show that if $A⊊B$ and $B⊊C$ then $A⊊C$

To show $A⊊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\ne B$

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

Now let's address the second statement. $B⊊C$ tells us that there exists a $y\in C$ that is not in $B$. But $A⊊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⊊B$ and $B⊊C$ then $A⊊C$. $◻$

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 \mathrm{\varnothing }=\mathrm{\varnothing }\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\}⟺(x=a\vee x=b)$$

Axiom 3.4 defining singletons tells us

$$\begin{array}{rl}x\in \{a\}& ⟺x=a\\ \\ x\in \{b\}& ⟺x=b\end{array}$$

Axiom 3.5 defines pairwise union as follows

$$x\in (A\cup B)⟺((x\in A)\vee (x\in B))$$

Thus

$$x\in (\{a\}\cup \{b\})⟺((x\in \{a\})\vee (x\in \{b\}))$$

This is equivalent to the following (Axiom 3.4),

$$x\in (\{a\}\cup \{b\})⟺((x=a)\vee (x=b))$$

And by Axiom 3.4 again,

$$x\in (\{a\}\cup \{b\})⟺((x=a)\vee (x=b))⟺x\in \{a,b\}$$

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

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)⟺((x\in A)\vee (x\in B))$$

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

$$((x\in A)\vee (x\in B))⟺((x\in B)\vee (x\in A))$$

By Axiom 3.5, we also have

$$x\in (B\cup A)⟺((x\in B)\vee (x\in A))$$

These three statements give us

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

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

Show  $A\cup A=A\cup \mathrm{\varnothing }=\mathrm{\varnothing }\cup A=A$

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

$$A\cup \mathrm{\varnothing }=\mathrm{\varnothing }\cup A◻$$

Let's use Axiom 3.5 which defines union to write

$$x\in (A\cup A)⟺((x\in A)\vee (x\in A))$$

We can simplify the RHS,

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

This is simply stating that

$$A\cup A=A◻$$

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

$$x\in (A\cup \mathrm{\varnothing })⟺((x\in A)\vee (x\in \mathrm{\varnothing }))$$

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

$$x\in (A\cup \mathrm{\varnothing })⟺(x\in A)$$

This is simply stating that

$$A\cup \mathrm{\varnothing }=A◻$$

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 $\mathrm{\varnothing }$, $\{\mathrm{\varnothing }\}$, $\{\{\mathrm{\varnothing }\}\}$ and $\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$ 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 $\mathrm{\varnothing }$, known as the empty set, which contains no elements, i.e., for every object $x$ we have $x\notin \mathrm{\varnothing }$.
• 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 $\mathrm{\varnothing }$ is different from $\{\mathrm{\varnothing }\}$, $\{\{\mathrm{\varnothing }\}\}$ and $\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$.

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

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

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

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

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

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 $\{\mathrm{\varnothing }\}$ is different from $\{\{\mathrm{\varnothing }\}\}$ and $\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$.

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

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

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

Show $\{\{\mathrm{\varnothing }\}\}$ is different from $\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$.

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

We could say the sets are not equal because their cardinalities are different. That is, $|\{\{\mathrm{\varnothing }\}\}|=1$ and $|\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}|=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 $\mathrm{\varnothing }$ of $\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$ is not a member of $\{\{\mathrm{\varnothing }\}\}$. So by Axiom 3.2, $\{\{\mathrm{\varnothing }\}\}$ is not equal to $\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$.

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

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)\vee (a=d)$ is true.
2. $b$ is a member of $\{c,d\}$. That means $(b=c)\vee (b=d)$ is true.
3. $c$ is a member of $\{a,b\}$. That means $(c=a)\vee (c=b)$ is true.
4. $d$ is a member of $\{a,b\}$. That means $(d=a)\vee (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. $◻$