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.
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 .