# inclusion of sets -transitive?

show that if $A\subseteq B$ and $B\subseteq C$ then $A\subseteq C$

Can I do it with using injective functions?

$A\subseteq B$ means there exists an injective fcn $f:A\to B$

$B\subseteq C$ means there exists an injective fcn $g:B\to C$

then the composition $g\circ f:A\to C$ is also an injective function then $A\subseteq C$

in each case all the functions are identity functions

-
$A\subseteq B$ is not equivalent to the existence of an injective function from $A$ to $B$. It's just applying the definition: if $x\in A$, then $x\in B$ because of $A\subseteq B$; therefore $x\in C$ because of $A\subseteq C$. – egreg May 26 '13 at 12:31

Caution: The existence of an injection between $A$ and $C$ doesn't necessarily imply $A \subseteq C$.

For example, consider set $A$, the set of all even integers, and set $B$, the set of all odd integers. Certainly, there exists an injection: $f: A \to C$, $\;f(x) = x + 1\;$ (which is not only injective, but surjective, as well). But clearly, $\;A \nsubseteq C$.

The converse is true: if $A \subseteq C$, then an injection $h: A \to C$ exists.

But we can easily prove the inclusion $A \subseteq C$ by "element chasing:" a standard way to prove set inclusions, and/or set equivalencies.

We have $A \subseteq B$ and $B \subseteq C$. And we want to prove that this necessarily implies $A\subseteq C$.

• $(1)$ Suppose $x \in A\quad$ (Assumption)

• $(2)$ We know $A \subseteq B$ means $x \in A \implies x \in B.\;$ So given $(1)$, we have $x \in B$.

• $(3)$ We know $B \subseteq C$ means $x \in B \implies x \in C$. So given $(2)$, we have $x \in C$.

$(4)\;\;x \in A \implies x \in C$. $\quad[(1) - (3)]$

Therefore, $A \subseteq C$.

-
thank you, very nicely explained! – H.E May 26 '13 at 19:14
You're welcome, Heidi! – amWhy May 26 '13 at 19:16
@amWhy: I agree! You just own these! :-) +1 – Amzoti May 27 '13 at 1:04

No, you can't do so this way.

"A⊆B means there exists an injective function f:A→B" is false.

"A⊆B implies there exists an injective function f:A→B" is true.

"A⊆B means there exists an injective function f:A→B" would only come as true if both

(1) "A⊆B implies there exists an injective function f:A→B" and

(2) "the existence of an injective function f:A→B implies A⊆B" were true also. But, (2) is false, and thus "A⊆B means there exists an injective function f:A→B" is false.

-