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.

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.

Please help!

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
(+1) Skunked me by mere seconds! –  Cameron Buie Jun 2 '13 at 16:40
2  
@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.

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.