0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

Given a finite set as domain, I think your proof is OK.

$\endgroup$
  • $\begingroup$ thanks I was assuming finite case, but I will give thought to your continuous case. $\endgroup$ – user391925 Nov 22 '16 at 9:21
  • $\begingroup$ @Pieter21 $(0,1)$ and $(0,1/2)$ have the same cardinality so in that sense the statement still holds true in the infinite case. $\endgroup$ – dxiv Nov 22 '16 at 18:01
  • $\begingroup$ If your size is cardinality this is indeed true. This half length construct was just to demonstrate that we have to be careful of definitions and conditions in the question. $\endgroup$ – Pieter21 Nov 22 '16 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy