Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
$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

2 Answers 2

up vote 7 down vote accepted

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

share|improve this answer
    
thank you, very nicely explained! –  Heidi.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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.