Def : A set $X$ is finite if every injective map from $X$ to $X$ is surjective.
Using this, how can I prove that if $X$ is finite, then there exists a bijective map from $X$ to some natural number.
I was trying to prove by contrapositive statement:
Assume that there is no bijective map from $X$ to any natural number $n$. Then I have shown that if a map $f:X \rightarrow n$ is not bijective, then it can not be injective. Now, I want to show that there exists a family of surjective maps $\{f_n: X \rightarrow n\}$ such that $Dom(f_n)$ is properly contained in $Dom(f_{n+1})$ show that I construct a map $g$ from $X$ to $X$ which is injective but not surjective. But I am not able to show the existence of such a family.
Best Answer
Note that you need to use the axiom of choice at some point there. Otherwise the definition of "finite" which you are using (also known as Dedekind-finiteness) may include sets which are strictly larger than all the natural numbers, but not larger than $\Bbb N$.
So here you need to assume that if a set is infinite, then it has a countably infinite subset (which is precisely where you are using the axiom of choice). But this makes an easy way of finding an injection which is not surjective. Just note that we can find such function for $\Bbb N$.