Let $n \in \omega$. Suppose $f:n \to A$ is onto $A$. Prove that $A$ is finite.

I have: Let $I_a = \{i \in n:f(i)=a\}$ for $a \in A$. Since $f$ is onto $A$, $I_a$ is nonempty, and by the well-ordering principle, it has a least element $l$. I know I'm to prove by induction, by I'm a bit stuck. Any help is appreciated.

  • $\begingroup$ What definition of infinite (or finite) are you using? $\endgroup$ – Robert Shore Mar 18 at 21:37
  • $\begingroup$ A set $X$ is finite iff there is a one-to-one function $f:X\to n$ for some natural number $n$. $\endgroup$ – George W Kush Mar 18 at 21:47
  • 2
    $\begingroup$ Let $N$ be the smallest natural number such that $\exists f:N \rightarrow A$ with $f$ onto. Such a smallest $N$ must exist by induction. Prove that $f$ must be one-to-one and then show that $f^{-1}$ gets you where you need to be. $\endgroup$ – Robert Shore Mar 18 at 21:54
  • $\begingroup$ Actually, if all you need is a $1-1$ function into (as opposed to onto) a natural number, you're almost done. Just define $g(a)$ as the least element of $I_a$ using your construction and prove that $g$ is $1-1$. $\endgroup$ – Robert Shore Mar 18 at 23:18

Since $f $ is surjective, it has a section $g:A\to n $, that's $f\circ g=\mathrm {is} $ Then $g $ is injective hence induce a bijection onto its image, that's $A\cong g [A] $. Since $g [A]\subseteq n$, it is finite, hence $A$ is finite as well.


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.