$
\newcommand{\N}{\mathbb{N}}
$
Motivated by the question Hermis14, I tried to understand what being countable means through the following proposition.
Definitions:
$|A| \le |B|$ if there is an injection from $A$ into $B$;
$|A| \ge |B|$ if there is a surjection from $A$ onto $B$;
Though someone commented about the notation, $\ge$, that it is not good for some reason, for now, I decided to use it for consistency with my reference book (Folland, 1999) notation. I would appreciate any reference to the widely accepted versions of notation for this case.
Claim:
Let $|A| \le |\N|$ (countable). Then, $|A| \ge |B| \Rightarrow |B| \le |A|$ (without any weaker version of AC).
Attempt: There is an injection $f: A \to \N$. Therefore $c = f|^{f[A]}$ (corestriction) is a bijection from $A$ to $f[A]$, and $f[A] \subseteq \N$.
Since $|A| \ge |B|$, there is a surjection $g:A \to B$. $h = g \circ c^{-1}$ is a surjection from $f[A]$ to $B$. Since $h$ is subjective, for each $y \in B$, $h^{-1}[y] \subseteq f[A] \subseteq \N$ (inverse image) is nonempty. By well-ordering principle, the inverse image has a minimum; we can define a function $k: B \to f[A]$ such that
$$
\forall y \in Y: k(y) = \min h^{-1}[y]
$$
It can be easily shown that $k$ is injective. Finally, $c^{-1} \circ k: B \to A$ is injective, which means $|B| \le |A|$.
Is this a valid proof?
Best Answer
Maybe you can simplify your proof as: Let $f: A \to \mathbb{N}$ be an injection and $g \colon A \to B$ be a surjection. For each $b \in B$, $X_b:= f(g^{-1}(b)) \subset \mathbb{N}$ is non-empty. Let $n_b = \min X_b$. Then the map $h \colon B \to A$, $h(b) = f^{-1}(n_b)$ is an injection.