0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $ $\endgroup$ – DanielWainfleet Apr 6 '18 at 11:14
  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Apr 6 '18 at 11:41
  • $\begingroup$ 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)". $\endgroup$ – MadnessFor MATH Apr 6 '18 at 12:14
  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Apr 6 '18 at 18:18
  • $\begingroup$ I am often surprised at how long it takes to prove such "obvious" properties of finite sets. $\endgroup$ – DanielWainfleet Apr 6 '18 at 18:20
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – MadnessFor MATH Apr 7 '18 at 2:41
0
$\begingroup$

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.

$\endgroup$

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.