I'm new to set theory, and recently I came across with a problem:
Prove transitivity on proper subsets, that is if $A \subset B$ and $B \subset C$, then $A \subset C$.
From what I've learned so far, proper subset, $A \subset B$ iff $(\forall x)(x \in A \Rightarrow x \in B) \land A \neq B$. In other words, if $A \subseteq B$ and $A \neq B$, then $A \subset B$.
From what's given, $(\forall x)(x \in A \Rightarrow x \in B)$ and $(\forall x)(x \in B \Rightarrow x \in C)$, I can prove $(\forall x)(x \in A \Rightarrow x \in C)$ with specialization, transitivity, and generalization. Thus $A \subseteq C$ is the conclusion. Only if I can prove $A \neq C$ from $A \neq B$ and $B \neq C$, together with $A \subseteq C$, I can prove $A \subset C$.
$A = B$ iff $(\forall x)(x \in A \Leftrightarrow x \in B)$ (axiom of extent), thus $A \neq B$ iff $\neg (\forall x)(x \in A \Leftrightarrow x \in B)$, iff $(\exists x)(\neg (x \in A \Leftrightarrow x \in B))$, iff $$(\exists x)((x \in A \land x \notin B) \lor (x \notin A \land x \in B)).$$
So this is where I got stuck, that is, given
$$(\exists x)((x \in A \land x \notin B) \lor (x \notin A \land x \in B))$$ and
$$(\exists x)((x \in B \land x \notin C) \lor (x \notin B \land x \in C)),$$ how to prove that
$$(\exists x)((x \in A \land x \notin C) \lor (x \notin A \land x \in C))?$$
Sorry if this is a really stupid question and thank in advance for any help! 🙂
Best Answer
When proving that $A\neq C$, you can't use just $A\neq B$ and $B\neq C$. Because from these two facts only, it is entirely possible that $A=C$. You have to include what you know about the set inclusions.
Because of $B\neq C$ and $B\subseteq C$ together, there must be some $c\in C$ such that $c\notin B$.
More specifically, look at your $$ (\exists x)((x \in B \land x \notin C) \lor (x \notin B \land x \in C)). $$ Let $c$ be one of the elements that the above sentence tells us exists. The inclusion $B\subseteq C$ means one of the terms in the disjunction, namely $c\in B\land c\notin C$, is false, so you may safely remove that without changing the truth of the statement. Thus we are left with $c\notin B\land c\in C$.
Since $A\subseteq B$ and $c\notin B$, we must also have $c\notin A$. This lets us conclude $A\neq C$.
(Note that we never used $A\neq B$ here, and indeed, $A\subseteq B$ and $B\subset C$ together do imply $A\subset C$, which is a marginally stronger result than what you were asked for. Similarly, we could have used $A\neq B$ instead to get a hold of our $c\notin A$, this time with $c\in B$, which would have yielded that $A\subset B$ and $B\subseteq C$ imply $A\subset C$.)