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.