I really need some help please!
I would really appreciate it if anyone can help out:
(i)Decide and state whether any subset of a countable set is itself countable.Explain your answer in your own words.
Hope someone can help!Thank in advance!
This is what I wrote:
A set is countable if it is finite, or it can be placed in 1-1 correspondence with the positive integers. A set is countably infinite if it is countable and infinite, just like the positive integers.
The non negative integers are countable, as shown by the bijection f(n) = n+1.
The even numbers are countable, map n to n/2.
The integers are countable. Map n to 2n for n ≥ 0, and map n to 1-2n for n < 0.
Any set that can be listed in order, or enumerated, is countable. Thus the prime numbers are countable, and so on.
Ordered pairs of positive integers are countable. List them this way:
1/1 2/1 1/2 3/1 2/2 1/3 4/1 3/2 2/3 1/4 5/1 4/2 3/3 2/4 1/5 …
Since fractions are ordered pairs of integers, the rational numbers are countable.
The cross product (i.e. ordered pairs) of countable sets is countable. Use this fact again and again to show that the n-tuples of integers are countable. The integer points, or even the rational points in n space are countable.
All finite ordered tuples of the integers, or any other countable set for that matter, are countable.
As a corollary, the finite sets of integers are countable, as these are all represented, perhaps many times, by various ordered tuples. The set (1,2,3) appears six times when order is significant. Since the ordered tuples over count the unordered subsets, and the tuples are countable, the finite subsets are also countable.
Since the tuples are countable, the polynomials are countable. Of course the coefficients can be drawn from any countable set, so the polynomials over the rationals are countable.
The polynomials over x and y are the polynomials in y, whose coefficients are polynomials in x. The polynomials in x are countable, and since these act as coefficients, the polynomials in x and y are countable. This extends to polynomials in x y z, and so on.
So is this the answer to my question???
Thank you guys for your help!
What you wrote was a correct exposition of what "countable" means and some countable sets. But it does not at all answer the question!
Suppose a countable set, A, had an uncountable subset. What would that say about the "one-to-one mapping" of A onto the natural numbers?