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

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.

• What definition of infinite (or finite) are you using? – Robert Shore Mar 18 at 21:37
• A set $X$ is finite iff there is a one-to-one function $f:X\to n$ for some natural number $n$. – George W Kush Mar 18 at 21:47
• 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. – Robert Shore Mar 18 at 21:54
• 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$. – 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.