Prove the following assumption:
If C is a countable set and f: A->C is an injection, then A is countable.
I'm stuck on how to prove this, as I originally learnt it as the very definition of a countable set. Actually, I think the definition of countable is that a set has the same cardinality as a subset of the natural numbers.
How is this for a proof? I feel that it is just stating the obvious and not formal enough.
Assume A is uncountable. From the definition of an injection, for all a∈A there exists c∈C such that f(a) = c. But C is countable so there exists a mapped to no c, a contradiction. Hence A is countable.
Thanks in advance.
Theorem: If C is a countable set and f: A->C is an injection, then A is countable.
Proof: Assume A is infinite (if it is not infinite it is by definition countable). For all a∈A there exists a unique c such that f(a) = c. Now C is countable, so for all c there exists unique a such that f(a) = c. Hence there is a bijection from A to C and by Bernstein's theorem this implies they have the same cardinality. C is countable and therefore so is A.
Does this sound right?
When I first read it, I dismissed it as some authorís effort to construct a question to get at a fundamental property of cardinality.
These are really matters of definitions.
If there is an injection from A to B, then the cardinality if A, .
Then if there is a surjection from B to A, then .
In terms of this particular question, any subset of a countable set is countable.
It just seems to me that this question almost answers itself.
http://www.cl.cam.ac.uk/teaching/exa.../y2003p1q8.pdf. It's part c)i)
First, some remarks about suggested proofs.
In fact, I am not sure how to use Schroeder-Bernstein theorem for this problem.
We have that C is 1-1 with some subset S of the natural numbers. So let g be a 1-1 function from C onto S. So fog (the composition of functions f and g) is a 1-1 function from A onto some subset T of S. And since T is a subset of S is a subset of the set of natural numbers, we have that T is a subset of the set of natural numbers. So A is 1-1 with a subset of the set of natural numbers.