Proof verification for no bijection between a finite set and a proper subset of it.

686 Views Asked by At

Can someone please check my proof? I'm new to math formalism, so any advice is a huge help.


Theorem: There is no bijection between a finite set and a proper subset of it.

Observations:

I want to prove that $\nexists$ $g:A \rightarrow B$, when B is finite and A $\subset B$ and $g$ is a bijection.

Theorem (*): If $A\subset I_n$, is a proper subset, there is no bijection $h:A\rightarrow I_n$.

Since I've already proved the theorem above, I'll use it in my proof.


My Proof:

Let B be some finite set and A a proper subset of B.

Since B is a finite set, $\exists$ $f : I_n \rightarrow B$, where $I_n = \{1,2...,n\}$.

Let's define $I_m$ as $f^{-1}(A)$. By that definition we can see that $I_m \subset I_n$, since $A\subset B$.

I'll call $f_a :I_m \rightarrow A$, that is the bijection obtained with a restriction of $f$ by $I_m$.

If there was the bijection $g:A\rightarrow B$, I would be able to compose functions to get $f^{-1} \circ g \circ f_a:A\rightarrow I_n$, and the theorem (*) says that that's impossible, therefore it is not possible to have a bijection between a finite set and a proper set of it.