If $A \subsetneq B$ and $B \subsetneq C$, then $A\subsetneq C$.

183 Views Asked by At

This has already been asked here, but I used an argument via contradiction as it seemed fitting in the context of the full proposition that needed to be proven.

Definition $3.1.14$ (Subsets). Let $A$, $B$ be sets. We say that $A$ is a subset of $B$, denoted $A ⊆ B$, iff every element of $A$ is also an element of $B$, i.e., For any object $x$, $x ∈ A \implies x ∈ B$.

We say that $A$ is a proper subset of $B$, denoted $A \subsetneq B$, iff $A ⊆ B$ and $A \neq B$.

This is from Tao's Analysis I. The definition of a proper subset has an "if" instead of the "iff" but I used the latter because of the errata.

The proposition in full says:

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

Having already proven these two previous results, my proof went as follows.

Proof. Assume $A\subsetneq B$ and $B \subsetneq C$. By definition, $A \subsetneq B \implies (A \subseteq B)\land (A\neq B)$. Similarly, $B \subsetneq C \implies (B \subseteq C)\land (B\neq C)$. By the proposition we already know that $A \subseteq C$ so we only need to prove that $A\neq C$ to get the full result. Suppose for the sake of contradiction that $A=C$. Then, every element of $C$ is also an element of $A$, i.e., $C\subseteq A$. Also, $A \subseteq B$ so by proposition, $C \subseteq B$. So we have both $C\subseteq B$ and $C \subseteq B$, then by proposition, $B=C$, a contradiction. So $A\neq C$, which together with $A\subseteq C$ closes the proof.

Is this correct? Do you think this is the solution Tao had in mind?

2

There are 2 best solutions below

1
On

The last proposition has a simple proof: just choose $b \in B$ such that $b \notin A$. By assumption $b \in C$ and we get $A \neq C$. This holds even when $B=C$ so that the condition $B \neq C$ is unnecessary.

0
On

Assume $A\subsetneq B$ and $B \subsetneq C$.

Since $A \subsetneq B,$ it follows that $A \subseteq B.$ Since $B\subsetneq C,$ it follows that $B \subseteq C.$

In the previous part of the proposition, you showed that, therefore, $A \subseteq C.$

Next, since $A\subsetneq B,\ $ it follows that $A\neq B.$ This implies either $\exists\ a\in A $ such that $a\not\in B,\ $ or $\exists\ b\in B $ such that $b\not\in A.$ The former cannot be true due to the definition of $A\subseteq B.$ Therefore there exists $b\in B$ such that $b\not\in A.$ Since $B\subseteq C,\ b$ is also in $C.$ Thus we have shown there exists a member of $C$ that is not in $A.$ Therefore, $A\neq C.$

Since $A\subseteq C$ and $A\neq C,$ we conclude that $A\subsetneq C.$