If $X$ is finite and $f:X \rightarrow Y$ is a function, then $f(X)$ is a finite set with $|f(X)| \leq |X|$.

Question

If $X$ is finite and $f:X \rightarrow Y$ is a function, then $f(X)$ is a finite set with $|f(X)| \leq |X|$.

I have tried to prove this claim by contradiction.

Since $X$ is finite, we shall assign an arbitrary cardinality $n$ to $X$ and so there exists a bijection $h:X \rightarrow \mathbb{N_n}$. Now suppose that $f(X)$ has cardinality $m$ where $m >n$, then there exists a bijection $g:f(X) \rightarrow \mathbb{N_m}$, from this we can deduce that $\forall z \in \mathbb{N_m} \exists y \in f(X) \text{ s.t } g(y) = z$ in particular there must exist a $y \in f(X)$ such that $$g(y) = n+1 \implies g(f(x)) = n+1$$ $$\implies f(x) = g^{-1}(n+1)$$

I feel as though the next part of the "proof" is not correct

and so $f(x)$ is the image of $x \in X $ such that $f(x)$ is the $(n+1)th$ element of $f(X)$. Since there are only $n$ elements in $X$ it must be the case that at least one element $x \in X$ has been mapped to two or more different elements in $f(X)$. but in that case $f$ is not a function, by definition. Hence $m \leq n$

Now I have to show that if $f$ is injective then the inequality becomes equality. But I would like to make sure this guy is ok first.

Answer 1

The proof has a glitch, because the negation of being finite is being infinite, so you can't assume that $f(X)$ is in bijection with an initial segment of $\mathbb{N}$.

---

Consider the equivalence relation on $X$ defined by $f$; that is, for $a,b\in X$, define $a\sim b$ if and only if $f(a)=f(b)$. If $[a]$ denotes the equivalence class of $a\in X$, then the map $\tilde{f}\colon X/{\sim}\to Y$ defined by $$ \tilde{f}([a])=f(a) $$ is (well-defined and) injective; moreover $\tilde{f}$ has the same image as $f$. Now your task is to prove that $$ |X/{\sim}|\le |X| $$ (take a set of representative of each equivalence class and…).

If $f$ is injective, then the equivalence relation is…

Answer 2

1. When proving by contradiction, $f(X)$ is an infinite set or a finite set with $|f(X)|>|X|$. You cannot assume $f(X)$ to have a finite cardinality m. But there must be a subset $Z$ such that $Z\subseteq f(X),|Z|=n+1$

2. There exists a bijection $g:Z \rightarrow \mathbb{N}_{n+1}$, denoting $z_i=g^{-1}(i),i\in\mathbb{N}_{n+1}$

3. $\forall z\in Z, \exists x\in X, s.t. f(x)=z$. For each $i \in \mathbb{N}_{n+1},z_i=g^{-1}(i)\in Z$, suppose $f(x_i)=z_i$.

4. Consider the set $X_t=\{x_i | i\in\mathbb{N}_{n+1}\}$, $X_t\subseteq X$, there must be some $i,j\in\mathbb{N}_{n+1}, i\ne j$, that $x_i=x_j$, otherwise $|X_t|=|\mathbb{N}_{n+1}|=n+1>|X|$, which contradicted with $X_t\subseteq X$

Now we get some $i,j\in\mathbb{N}_{n+1},i\ne j$,that $x_i=x_j=x$, we have $$f(x)=g^{-1}(i), f(x)=g^{-1}(j), i\ne j$$ Since $g$ is a bijection, $g^{-1}(i)\ne g^{-1}(j)$ if $i\ne j$, thus we get 2 different images for the same $x$.