Do you know this Schroeder-BernsteinTheorem?
And another webpage.
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.
Do you know this Schroeder-BernsteinTheorem?
And another webpage.
Having just read the theorem, it states that if there is an injection A to B and an injection B to A, then there is a bijection between A and B and hence they have the same cardinality. I know there is an injection A to C in the question, so I must now show that there is an injection from C to A? Is this right?
Ok. So here is my corrected proof:
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?
Maybe we should discuss this question in detail.
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.
I was also confused about what the question wanted. This is the exact question: http://www.cl.cam.ac.uk/teaching/exa.../y2003p1q8.pdf. It's part c)i)
First, some remarks about suggested proofs.
The fact that there exists an a that is mapped to no c is not sufficiently justified.
From the fact that C is countable it does not follow that for all c there exists unique a such that f(a) = c. If f is not a surjection, this is not the case. But if this is true, then f is a bijection and there is no need to invoke the Bernstein's theorem, which says that there is some bijection.
In fact, I am not sure how to use Schroeder-Bernstein theorem for this problem.
If this is the definition, let B be the image of f. By definition, f : A -> B is a surjection and by assumption it is an injection. Therefore, f : A -> B is a bijection. Let g : C -> D where D ⊆ ℕ be a bijection, which exists since C is countable, and let g' be the restriction of g to B. Then g' is a bijection from B to some D' ⊆ D ⊆ ℕ. All in all, g' ∘ f is a bijection from A to D' ⊆ ℕ.
More simply put: A set is countable iff it is 1-1 with some subset of the set of natural numbers.
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.