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?
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.
You can't have more elements in the image of a set under a function then in the domain-that's basically the point of Gaston's post above. Here's another way to express it so that the proof is clearer: Consider the Cartesian product definition of a mapping from a countable set D into a set E where the image of f is a subset of E. (I know,duh-but when you're trying to understand in mathematics why something is true, it's worthwhile to state the obvious so you make sure you understand the definitions.) A function by definition is a set of ordered pairs where no 2 different ordered pairs have the same first member. So ask yourself something and the proof will be clear: Can you construct such a set of ordered pairs representing f:D ----> E if f(D) is uncountable?