Let $B$ be a non-empty set. Then the following are equivalent:
(1) $B$ is finite.
(2) There is a surjective funtion $f:\{1,…,n\}\rightarrow B$ for some $n\in \mathbb{N}$
(3) There is an injective function $g:B \rightarrow \{1,…,n\}$ for some $n\in \mathbb{N}$
My attempt:
(1) $\Rightarrow$ (2)
Since, $B$ is a non-empty finite set, there exists a bijective function $h:B \rightarrow \{1,…,n\} $ for some $n\in \mathbb{N}$.
So, there exists a bijective inverse function $h^{-1}:\{1,…,n\}\rightarrow B$. for some $n\in \mathbb{N}$.
$\therefore$ There exists a surjective function $f:\{1,…,n\}\rightarrow B$ for some $n\in \mathbb{N}$.
I'm not sure if my above proof is valid.
Also, can someone please help me with the proofs for (2)$\Rightarrow$ (3) and (3)$\Rightarrow$ (1) ??
Best Answer
Your proof seems ok. For the others
(2) => (3)
Let $f$ be your surjection $\{1,\dots,n\} \to B$.
Define $g$ as $$g(b) = \min \{i \in \{1,\dots,n\} \mid f(i) = b\}.$$ This is well defined because $f$ is surjective, hence the set is never empty, and always finite.
Then, let $x,y\in B$ such that $g(x) = g(y)$. By definition, $f(g(x)) = x$ and $f(g(y)) = y$, and $f(g(x)) = f (g(y)$, thus $x=y$.
(3) => (1)
Let $g$ be your injection $B\to \{1,\dots,n\}$. Then $h:B \to Im(g)$ defined by $h(x) = g(x)$ is a bijection, and $Im(g) \subseteq \{1,\dots,n\}$ which is finite.You have then a bijection between $B$ and a finite set, thus $B$ is finite.