$
\newcommand{\N}{\mathbb{N}}
$
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$;
$|A| = |B|$ if there is a bijection from $A$ onto $B$.
Theorem 1:
Assuming AC, for any set $A$ and $B$, $|A| \ge |B| \Rightarrow |B| \le |A|$.
I am trying to show the following:
Claim:
For each nonempty set $X$ and any function $f: X \to Y$, if $A$ is a subset of $X$,
$$
|A| < |\N| \Rightarrow |f[A]| < |\N|
$$
That is, the image of a finite set is finite.
Attempt:
Assume $|A| < |\N|$. Since $f$ is a function, $f|_A\to {f[A]}$ is a surjection, that is, $|A| \ge |f[A]|$.
-
By Theorem 1, we have $|f[A]| \le |A|$. Because the composition of injections is an injection, $|f[A]| \le |A| \le |\N|$.
-
Now, suppose that $|f[A]| = |\N|$ aiming for contradiction. Since the composition of a bijection and surjection is a surjection, $|A| \ge |f[A]| \ge |\N|$. Hence, by Theorem 1, we have $|\N| \le |A|$, and by Schroeder-Bernstein theorem, $|A| = |\N|$, which is a contradiction.
Finally, $|f[A]| \le |\N| \land |f[A]| \neq |\N|$.
Questions:
- Is this valid proof?
- Do I really need AC to prove the proposition? Since I am dealing with finite sets, it seems that invoking AC is overkill.
This question is continued in Hermis14.
Thank you.
Best Answer
Yes, I don’t think you used any invalid reasoning in the proof, but as you suspect, it is overkill for the finite case and no AC is necessary. Actually, it is not required in the more general circumstance where $A$ is well-orderable, since you can choose the least preimage of each point in $f(A)$ according to some well-ordering of $A$ to get an injective mapping $f(A)\to A.$