How to prove that if $D$ is countable, then $f(D)$ is either finite or countable?

Is there anybody who can help me to prove that if $D$ is countable, and $f$ is a function whose domain is $D$, then $f(D)$ is either finite or countable?

Solution 1:

Recall that $f$ is a collection of ordered pairs such that if $\langle a,b\rangle$ and $\langle a,c\rangle$ are both in $f$ then $b=c$.

Furthermore, $f(D)=\{b\mid\exists a\in D:\langle a,b\rangle\in f\}$. Since for every $a\in D$ there is at most one ordered pair in $f$ in which $a$ appears in the left coordinate, we can define an injective function from $f(D)$ into $D$.

Suppose $D=\{d_n\mid n\in\mathbb N\}$, then for $b\in f(D)$ define $\pi(b)=d_n$ where $n=\min\{k\in\mathbb N\mid f(d_k)=b\}$. You should verify that this is indeed an injective function.

Recall that if we have an injective function from $A$ into $B$ then $|A|\leq |B|$ and if $|B|$ is countable then $A$ must be countable (or finite). From here the proof is about done.

In fact this depends on your definition of countable or finite: If your definition of countable or finite is "has an injection from $A$ into $\mathbb N$" you can prove that this is equivalent to "there is a surjection from $\mathbb N$ onto $A$" via a similar argument to what I wrote above.

Using the second definition you can simply argue:

Since $D$ is countable (or finite) there is some $g\colon\mathbb N\to D$ which is a surjection, therefore $f\circ g\colon\mathbb N\to f(D)$ is a surjecitve function and therefore $f(D)$ is countable (or finite).

A complete account of the proof of the equivalent definitions of countability can be found here.