# Suppose that $A$ is finite and that $f:A \to B$ is surjective. Then $B$ is finite and $\vert{B}\vert \leq \vert{A}\vert$

Please check my below proof. My proof is somewhere messy since I don't know how to organize and present ideas efficiently. I'm happy to receive any suggestion to have a shorter, more concise, and more elegant proof :)

Theorem:

Suppose that $$A$$ is finite and that $$f:A \to B$$ is surjective. Then $$B$$ is finite and $$\vert{B}\vert \leq \vert{A}\vert$$, the equality holds $$\iff f$$ is bijective.

Proof:

$$A$$ is finite $$\implies$$ there exists a bijection $$t:I_n \to A$$ where $$I_n$$ is an initial segment of $$\mathbb{N}$$.

$$\implies f\circ t:I_n \to B$$ is a surjection.

Let $$g:B \to I_n$$ s.t $$g(b)=\min(f\circ t)^{-1} \{b\}$$.

If $$g(b)=g(c)$$, then $$\min(f\circ t)^{-1} \{b\}=\min(f\circ t)^{-1} \{c\}$$. This implies there exists $$m$$ s.t $$f\circ t (m)=b$$ and $$f\circ t (m)=c$$. Thus $$b=c$$. So $$g$$ is injective.

$$\implies g:B \to g[B]$$ is bijective. $$g[B] \subseteq I_n \implies$$ g[B] is finite.

As a result, $$B$$ is finite.

$$g[B] \subseteq I_n \implies \vert{B}\vert \leq \vert{I_n}\vert=\vert{A}\vert \implies \vert{B}\vert \leq \vert{A}\vert$$. The equality holds $$\iff g[B] = I_n \iff g:B \to I_n$$ is bijective.

Now we prove ($$g:B \to I_n$$ is bijective) $$\iff (f$$ is bijective). It is easy to show that $$(g:B \to I_n$$ is bijective) $$\Leftarrow (f$$ is bijective). So our task is to prove $$(g:B \to I_n$$ is bijective) $$\implies (f$$ is bijective).

Assume that $$f(a_1)=f(a_2)=b$$. Then $$\exists x_1,x_2 \in I_n$$ s.t $$f \circ t(x_1)=f \circ t(x_2)=b \implies x_1,x_2 \in \{m \in \mathbb{N} \mid f\circ t (m)=b\}$$.

Assume $$x_1 \neq x_2$$. Without loss for generality, we assume $$x_1 < x_2$$. This implies $$x_2 \neq \min(f\circ t)^{-1} \{b\} \implies \not \exists b \in B$$ s.t $$g(b)=x_2 \implies g$$ is not surjective (CONTRADICTION).

Thus $$x_1=x_2$$ or equivelently $$a_1=a_2$$.

To sum up, $$f(a_1)=f(a_2)=b \implies a_1=a_2$$. As a result, $$f$$ is injective $$\implies f$$ is bijective.

• In your definition of $g$ you could say that $\min (f t)^{-1}\{b\}$ is a non-empty subset of the well-ordered set $\Bbb N$ so it has a least member $g(b)$. Although $\inf=\min$ when $\min$ exists, in this context it is probably better style to use $\min.$ – DanielWainfleet Apr 6 '18 at 11:14
• It may be shorter, and easier on the notation, to initially prove that any subset of an initial segment of $\Bbb N$ is finite. Then any functional image $B= h(I)$ of an initial segment $I$ of $\Bbb N$ is finite because $S= \{\min h^{-1}\{b\};b\in B\}\subset I$ so $S$ is the bijective image $j(J)$ of an initial segment $J$ of $\Bbb N ,$ and $(j\cdot h|_S): J\to B$ is a bijection.... So if $I$ is an initial segment of $\Bbb N$ and $t:I\to A$ is a bijection and $f:A\to B$ is a surjection then with $ft=h$ we have:$\;B=h(I)$ is a functional image of $I$ so $B$ is finite. – DanielWainfleet Apr 6 '18 at 11:41
• Thank you @DanielWainfleet, I have edited my proof. I'm now ok with "$B$ is finite". Please check the part "$(\vert{B}\vert \leq \vert{A}\vert$, equality holds $\iff f$ is bijective)". – MadnessFor MATH Apr 6 '18 at 12:14
• The second part looks good to me. As a matter of personal style, I would have written $i_1,i_2$ for $t_1,t_2$ as the letter $t$ is already in use. But technically it's fine. – DanielWainfleet Apr 6 '18 at 18:18
• I am often surprised at how long it takes to prove such "obvious" properties of finite sets. – DanielWainfleet Apr 6 '18 at 18:20

Let f' = $f^{-1}.$
Since f is a surjection, for all b in B, some a_b in f'(b).
As A' = { a_b : b in B } subset A, A' is finite.
Show f restricted to  A' is a bijection onto B.

• I got your approach. It's very important for me to know if my proof is correct or not, so please check if it is fine! – MadnessFor MATH Apr 7 '18 at 2:41

Suppose that $$A$$ is finite and that $$f:A\to B$$ is surjective. Then $$B$$ is finite and $$|B|\le|A|$$, the equality holds $$\iff$$ $$f$$ is bijective.

I found that my previous proof is ambiguous at important arguments. So I decided to rewrite it here.

Let $$I_n=\{i\in\Bbb N\mid i\le n\}$$. Since $$A$$ is finite, there is a bijection $$g:I_n\to A$$. Thus $$f\circ g: I_n\to B$$ is surjective. We define a mapping $$h:B\to I_n$$ by $$h(b)=\min\{i\in\Bbb N\mid f\circ g(i)=b\}$$.

For $$b_1,b_2\in B$$, $$h(b_1)=h(b_2) \implies \min\{i\in\Bbb N\mid f\circ g(i)=b_1\}=\min\{i\in\Bbb N\mid f\circ g(i)=b_2\}=\bar i$$ $$\implies f\circ g(\bar i)=b_1$$ and $$f\circ g(\bar i)=b_2 \implies b_1=b_2$$. Thus $$h$$ is injective and consequently $$h:B\to h[B]$$ is bijective. Moreover, $$h[B] \subseteq I_n$$ and $$I_n$$ is finite. Hence $$B$$ is finite. We have $$|B|=|h[B]|\le |I_n|=|A|$$, then $$|B|\le |A|$$.

The equality holds $$\iff |B| = |A| \iff h[B]=I_n \iff h:B \to I_n$$ is bijective. So our task is to prove $$h$$ is bijective $$\iff f$$ is bijective. As $$h$$ is already injective and $$f$$ is already surjective, our task is to prove $$h$$ is surjective $$\iff f$$ is injective.

a. $$h$$ is surjective $$\implies f$$ is injective

For $$a_1,a_2\in A$$ and $$f(a_1)=f(a_2)=b$$. Since $$a_1,a_2\in A$$, there exist $$i_1,i_2\in I_n$$ such that $$g(i_1)=a_1$$ and $$g(i_2)=a_2$$. Then $$f\circ g(i_1)=f\circ g(i_2)=b$$. Then $$i_1,i_2\in \{i\in\Bbb N\mid f\circ g(i)=b\}$$. Assume $$i_2>i_1$$, then $$i_2>i_1\ge \min\{i\in\Bbb N\mid f\circ g(i)=b\} =h(b)$$ and consequently $$i_2 \neq h(b)$$. $$f\circ g(i_2)=b\neq b'$$ for all $$b'\in B$$ and $$b'\neq b$$. Then $$i_2 \notin \{i\in\Bbb N\mid f\circ g(i)=b'\}$$ for all $$b'\in B$$ and $$b'\neq b$$. Then $$i_2 \neq \min\{i\in\Bbb N\mid f\circ g(i)=b'\}$$ for all $$b'\in B$$ and $$b'\neq b$$. Then $$i_2 \neq h(b')$$ for all $$b'\in B$$ and $$b'\neq b$$. To sum up, $$i_2 \neq h(b')$$ for all $$b'\in B$$. Thus $$i_2 \notin \operatorname{ran}h$$. This contradicts the surjectivity of $$h$$. It follows that $$i_1=i_2$$, then $$g(i_1)=g(i_2)$$, then $$a_1=a_2$$. Hence $$f$$ is injective.

b. $$f$$ is injective $$\implies h$$ is surjective

For $$m\in I_n$$, if $$f\circ g(k)=f\circ g(m)$$, then $$g(k)=g(m)$$ by the fact that $$f$$ is injective. Then $$k=m$$ by the fact that $$g$$ is bijective. Hence $$m=\min\{i\in\Bbb N\mid f\circ g(i)=f\circ g(m)\}$$. Thus $$h(f\circ g(m))=m$$ where $$f\circ g(m)\in B$$. It follows that $$h$$ is surjective.