# Prove that if there exists a bijection $f: X\to N$, where $N$ is finite, then $X$ is finite.

I was given that $X$ is finite if any function that maps $X$ to $X$ is surjective and injective. Also, the problem specifies the finite set $N$ as a set with $n$ elements.

Now, I only know that there exists one function that is surjective and injective from $X$ to $X$: Define $X_1=X_2$ and $f: X_1\to N$ and $g: X_2\to N$. Since the composition of two surjective function is surjective, $f-1(g(X_1))$ is surjective. Thus, there is one function from $X$ to $X$ that is both injective and surjective.

But how can I prove that for every function from $X$ to $X$ itself is both injective and surjective?

Can anyone help me with this problem? Any help would be appreciated. Thanks

• There's an identity map $\textrm{id}_M \,:\, M \to M \,:\, x \mapsto x$ for every set $M$, finite or not, and that map is obviously injective and surjective. So your proposition isn't true... – fgp Apr 7 '14 at 21:21
• Only the empty set and sets with 1 element has the property that all functions are bijective. All other sets (both finite and infinite) it is trvial to construct a non injective, non surjective constant function. – Q the Platypus Jan 2 '18 at 6:06

## 1 Answer

The proof of the title is logical. If there exists a bijection $f$ between $X$ and a finite set $F$, then we say that $\forall f\in F,\exists x\in X:f(x)=f$, and $\forall x\in X,\exists f\in F:f(x)=f$. Thus, there is a one to one correspondence between elements of $X$ and $F$. Therefore, if $F$ is finite, $X$ is finite, i.e., it has $n$ elements.

In axiomatic set theory, the existence of a bijection $X\to F$ is taken to be the definition of "same number of elements".

• Sorry, I did not state the definition very clearly. The definition says that if every function from X to X is injective and surjective, then X is finite set – user139950 Apr 7 '14 at 21:33
• @user139950 That's false. You can have an injective and surjective, i.e., bijective function, from $\mathbb{R}\to\mathbb{R}$. – user122283 Apr 7 '14 at 21:34
• So you mean that if I can find one bijjective function then I can prove it? – user139950 Apr 7 '14 at 21:47