# cardinality of sets

Prove if $|A| < |B|$ and $|B| \leq |C|$

then $|A| < |C|$

I know that $|A| < |B|$ means there is a one to one mapping of A onto a SUBSET of B but no one to one mapping from A to B.

I also know that $|B| \leq |C|$ means there is a one to one mapping of B onto C.

I am going to try to prove this, but I am fairly confident its going to be full of holes, please help!

since $|A| < |B|$ there is $Z \subseteq B$ such that $f(a)=z$ for all $a \in A$ and $z\in Z$

since $|B| \leq |C|$ we have $f(b)=c$ for all $b \in B$ and $c\in C$

since $Z \subseteq B$ we have $f(z)=y$ for all $z \in Z$ and $y \in Y$ where $Y$ is a subset of $C$

since $f$ is one to one, then the inverse exists.

therefore $z = f^{-1}(y)$ for $z \in Z$ and $y \in Y$

therefore $f(a) = f^{-1}(y)$

okay now i'm lost.

-

First, let's clarify something:

The notation $|A|<|B|$ means that:

1. There is a 1-1 function from $A$ into $B$.
2. There is no bijection from $A$ onto $B$.

Whereas the notation $|A|\leq|B|$ means only the first one. It may be that the second condition holds, or that it fails. For example $|\{0\}|\leq|\{0,1\}|$, and also $|\{1,2\}|\leq|\{0,1\}|$.

To show now that $|A|<|C|$ use the fact that there are two injections, $f\colon A\to B$ and $g\colon B\to C$ to come up with an injection $h\colon A\to C$. Next show that if there was a bijection from $A$ onto $C$ then there had to be one onto $B$ as well, which is absurd.

-
(+1) Skunked me by mere seconds! – Cameron Buie Jun 2 '13 at 16:40
@Cameron: And I'm writing on an annoying tablet keyboard dock, from a bus with unstable wi-fi. What's your excuse? :-) – Asaf Karagila Jun 2 '13 at 16:42
How do you get the final bijection onto $B$? Don't you need to use the fact that there is a surjection $C\to B$, and that if there is a bijection $A\to C$ you would get a surjection $A\to B$ which is absurd? – Denis Jun 2 '13 at 16:45
@dkuper: Unless one assumes the axiom of choice, surjections has no business in being involved here. It is consistent to have a surjection from a set onto a strictly larger set, when the axiom of choice fails. Secondly, you use the fact that if there was a bijection from $A$ onto $C$ then there was an injection from $B$ into $A$, and the Cantor-Bernstein theorem tells us that there is a bijection. – Asaf Karagila Jun 2 '13 at 16:46
Ah ok thanks! I didn't think we would need a nontrivial result like the Cantor-Bernstein to prove this transitivity result. And I didn't know this about axiom of choice and surjections :) – Denis Jun 2 '13 at 16:51

Here is a slightly different approach. The conceptually simplest definition of $|\cdot|<|\cdot|$ I know is $$|A|<|B| \;\equiv\; |A|\le|B| \land |B|\not\le|A|$$ Using this definition we can rewrite our demonstrandum as follows: \begin{align} & |A|<|B| \land |B|\le|C| \;\Rightarrow\; |A|<|C| \\ \equiv & \;\;\;\;\;\text{"definition of $|\cdot|<|\cdot|$, twice"} \\ & |A|\le|B| \land |B|\not\le|A| \land |B|\le|C| \;\Rightarrow\; |A|\le|C| \land |C|\not\le|A| \\ \equiv & \;\;\;\;\;\text{"split RHS of $\Rightarrow$"} \\ & (|A|\le|B| \land |B|\not\le|A| \land |B|\le|C| \;\Rightarrow\; |A|\le|C| ) \;\land \\ & (|A|\le|B| \land |B|\not\le|A| \land |B|\le|C| \;\Rightarrow\; |C|\not\le|A|) \\ \equiv & \;\;\;\;\;\text{"simplify second part using contraposition"} \\ & (|A|\le|B| \land |B|\not\le|A| \land |B|\le|C| \;\Rightarrow\; |A|\le|C| ) \;\land \\ & (|A|\le|B| \land |C|\le|A| \land |B|\le|C| \;\Rightarrow\; |B|\le|A|) \\ \Leftarrow & \;\;\;\;\;\text{"strengthen by weakening LHS of $\Rightarrow$, twice"} \\ & \;\;\;\;\;\phantom{\text{"}}\text{-- because the shape of these formulas suggest transitivity"} \\ & (|A|\le|B| \land |B|\le|C| \;\Rightarrow\; |A|\le|C| ) \;\land \\ & (|B|\le|C| \land |C|\le|A| \;\Rightarrow\; |B|\le|A|) \\ \end{align}

Therefore all that is left to do is to prove that $|\cdot|\le|\cdot|$ is transitive, which should be easy enough.

-