# there does not exist an injective function whose codomain is smaller than its domain

I encountered this theorem on Wiki "there does not exist an injective function whose codomain is smaller than its domain". Here is my attempt to prove it, can you please have a look if this proof is OK?

Proof: Let's say we have: $f:A\to B$ where $|A| = N$ and $|B| = M$. Let's take all elements from $A$:

$a_1,\cdots ,a_N$ and by mapping them, we get:

$f(a_1),\cdots , f(a_N)$.

There can't exist two same elements in latter list (according to injection). Which means there need to be at least N distinct elements in B. This can't hold if $M < N$.

The continuous case is not true, $f(x) = x/2$ for $0\le x\le 1$, so you really need the assumption that the domain is a finite set.
• @Pieter21 $(0,1)$ and $(0,1/2)$ have the same cardinality so in that sense the statement still holds true in the infinite case. – dxiv Nov 22 '16 at 18:01