Statement
Let and be sets with . Prove that there is an injective function from into .
Solution
Define by (each subset of viewed as a subset of ).
It is well defined: if then ; since , by transitivity , i.e. .
It is injective: if then as sets, trivially. So is injective.
Therefore embeds into .