Thread: Finite function question

Suppose that f : X --> Y is given.

If X is finite, show that f(X) is also finite. Similarly, if X is countable,
show that f(X) is also countable.

Hello,

Originally Posted by flaming

Suppose that f : X --> Y is given.

If X is finite, show that f(X) is also finite. Similarly, if X is countable,
show that f(X) is also countable.

(talking about Y is an extraneous information)

The solution lies in the definition of



For any , there is at least one element such that

It also means that for any , there is at least one such that
You can see that this sentence is exactly the definition of a surjection.

Hence is a surjection. By Cantor-Bernstein theorem (I think it's this one), we have

If X is finite, then . So we have . Thus f(X) is finite.

If X is countable, then , etc...


If you see any mistake, tell me, I'm learning this stuff too

Here are some remarks to clear up some questions raised by the above posts.
DEFINITION: is an injection

Here is a most important theorem in many texts that deal with this material.
There is an injection if and only if there exists a surjection .
As noted above there is a surjection .
So by that theorem we must have an injection
Now apply the definition.

BTW: I do not see how the Cantor-Schroder-Bernstein theorem applies

Also recall that a function is simply a subset of .
Where is the set of all first terms of the pairs and is the set of second terms in the pairs.
So there is a natural expectation that the .