Countability Question

Printable View

April 16th 2011, 11:54 AM
StaryNight

Countability Question

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.
April 16th 2011, 01:33 PM
Plato

Quote:

Originally Posted by StaryNight

Prove the following assumption:
If C is a countable set and f: A->C is an injection, then A is countable.

Do you know this Schroeder-BernsteinTheorem?

And another webpage.
April 16th 2011, 01:43 PM
StaryNight

Quote:

Originally Posted by Plato

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?
April 16th 2011, 01:51 PM
Plato

Quote:

Originally Posted by StaryNight

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?

That is an easy task. You almost did that in the OP.
Each c in C has at most one pre-image in A.
There is also a well known theorem: If there is an injection from A to B then there is a surjection from B to A.
April 16th 2011, 02:11 PM
StaryNight

Quote:

Originally Posted by Plato

That is an easy task. You almost did that in the OP.
Each c in C has at most one pre-image in A.
There is also a well known theorem: If there is an injection from A to B then there is a surjection from B to A.

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?
April 16th 2011, 02:56 PM
Plato

Quote:

Originally Posted by StaryNight

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.

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, $|A|\le |B|$ .
Then if there is a surjection from B to A, then $|B|\ge |A|$ .
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.
April 16th 2011, 03:08 PM
StaryNight

Quote:

Originally Posted by Plato

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, $|A|\le |B|$ .
Then if there is a surjection from B to A, then $|B|\ge |A|$ .
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)
April 16th 2011, 03:31 PM
Plato

Quote:

Originally Posted by StaryNight

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)

There is nothing confusing about the question in that link!
Had you posted it to begin with, time would have been saved.
April 16th 2011, 03:47 PM
StaryNight

Quote:

Originally Posted by Plato

There is nothing confusing about the question in that link!
Had you posted it to begin with, time would have been saved.

Apologies, but how do you think one should answer the question?
April 18th 2011, 01:33 AM
emakarov

First, some remarks about suggested proofs.

Quote:

Originally Posted by StaryNight

Assume A is uncountable. From the definition of an injection, for all a∈A there exists c∈C such that f(a) = c. This is true because f is a function from A to C, not necessarily an injection. But C is countable so there exists a mapped to no c, a contradiction. Hence A is countable.

The fact that there exists an a that is mapped to no c is not sufficiently justified.

Quote:

Originally Posted by StaryNight

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.

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.

Quote:

Originally Posted by StaryNight

I think the definition of countable is that a set has the same cardinality as a subset of the natural numbers.

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' ⊆ ℕ.
April 19th 2011, 06:16 AM
MoeBlee

Quote:

Originally Posted by StaryNight

I think the definition of countable is that a set has the same cardinality as a subset of the natural numbers.

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.