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

  • $\begingroup$ 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... $\endgroup$ – fgp Apr 7 '14 at 21:21
  • $\begingroup$ 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. $\endgroup$ – Q the Platypus Jan 2 '18 at 6:06

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

  • $\begingroup$ 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 $\endgroup$ – user139950 Apr 7 '14 at 21:33
  • $\begingroup$ @user139950 That's false. You can have an injective and surjective, i.e., bijective function, from $\mathbb{R}\to\mathbb{R}$. $\endgroup$ – user122283 Apr 7 '14 at 21:34
  • $\begingroup$ So you mean that if I can find one bijjective function then I can prove it? $\endgroup$ – user139950 Apr 7 '14 at 21:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.