Here is my thought.
Let A be the set. Then since A is countable, .
Let . can, at most, be equal to set A.
Prove: A subset of a countable set is countable.
I began the proof saying we will assume a set B which is a subset of A where A is countable. By the following proposition, which says,
" the nonempty set A is countable if and only if there exists a surjection N --> A ",
there exists a surjection N --> A
Then I think there exists a surjection from N --> B, which would mean B is countable as well, but I am not sure how to justify this statement. Any help with this proof would be appreciated!
A "surjection" From N to X is a function such that, for all x in X, there exist n such that f(n)= x.
Let x be a member of B. Since B is a subset of A, x is a member of A. Since A is countable, there exist a surjection, f, from N to A, so there exist some n such that f(n)= x. Since this is true for all x in B, there exist a surjection from N to B.
Every subset of is countable.
Proof of the lemma:
Let . If is finite, it is obvious that is countable.
If is infinite, we will find bijection , with that we will show that is countable.
For every , set of elements of that are smaller than is finite.
Let us now define the function :
For every , will be the number of elements that are smaller than .
(Proof) If and are elements of and , each element of that smaller than is smaller also than , and himself isn't smaller that , but smaller that . Hence , so that .
(Proof) We will prove that for every have an origin.
Proving by induction on .
is infinite, hence isn't empty, therefor has first element- , it's obvious that .
Suppose that there is origin for , and we prove that there is origin to , let be origin for . is infinite, set of elements of that less than is finite, hence set of elements of that greater from is not empty. Let the first such element. Elements of that are smaller than they are elements of that are smaller than adding , so we get that , hence has an origin. We proved that is onto.
is bijective, therefor , hence countable.
Noe back to the original theorem:
Subset of a countable set is countable.
Let be countable set. If A is finite, every subset of is also finite, and therefor countable.
If is infinite, . Let be a subset of , and we will prove that is countable. Let be a bijection, so , and therefor it countable.
The function , so that for all , is bijection, therefor , the conclusion is that countable.