My question is: Let $X$ be a finite set and let f be a function, $f: X \rightarrow Y$ show that $ \# f[X] \le \#X$.
Here is my attempt:
As X is a finite set, therefore there exist a bijective map $ g: X \rightarrow n$ where $ n \in \omega$. And for each $y \in f[X]$ we have a set $y':= \left\{ k \in n: (f\circ g^{-1}) (k) = y \right\}.$
We define the relation $h: f[X] \rightarrow n, \;\;y \mapsto min( y').$
(1) Functional: Let $\, y \in f[X]\,$, if $\,h(y) = k_{1}$ and $ h(y) = k_{2}$. So, we have $k_{1} = min( y')= k_{2}\;\; then\;\:k_{1}=k_{2}. $
(2) Injective: Let $\,z,w \in f[X], \;z \not= w$ we need to show that $h(z) \not= h(w)$. A sufficient condition is $ w' \cap z' = \emptyset $. Because, that implies $min (z') \not =min (w').$
For the sake of the contradiction suppose that $ w' \cap z' \not= \emptyset \;$ which means $ \exists k\in w' \cap z' $. $ k \in w' \leftrightarrow k\in n \wedge f(k) = w,\; $ and $\; k \in z' \leftrightarrow k\in n \wedge f(k) = z $, which implies $z = w$ (because $f$ is functional), a contradiction .
So, using a composition we have $ f[X] \preceq X$ , $\; \# f[X] \le \#X$ as desired.
The next question is: Show that if the map $f$ is one-to-one, therefore $\# f[X] = \#X$. For the second one I don't sure how can I argue in a formal way, I know is almost obvious the answer, but all my approaches are too verbose, some hint.
I have another question about other similar exercise, could I put it here after I'll work a little bit in it?
Thanks :)
The proof seems fine, I would add a short argument as to why $y'$ is not empty, otherwise $\min(y')$ is ill-defined. I may also change the definition of $h$. Using the notation $h\colon f[X]\to n$ already implies it is a function. I would write it explicitly: $$h=\{\langle y,\min(y')\rangle\mid y\in f[X]\}.$$
As for the second question. Note that $f\colon X\to f[X]$ is always a surjection. With the assumption that $f$ is injective we have that $f$ is a bijection between $X$ and $f[X]$, and therefore both sets have the same cardinality.