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$