Chapter  7, Infinite Sets
Section  7.2  Countable and Uncountable Sets
Summary
 Suppose A and B are countable sets. Then:
 is countable.
 is countable.
 The union of countably many countable sets is countable. In other words, if is a family of sets, is countable, and also every element of is countable, then is countable.
 Suppose is a set. A function , where is a natural number, is called a finite sequence of elements of , and is called the length of the sequence.
 Suppose is a countable set. Then the set of all finite sequences of elements of is also countable.
 Cantorâ€™s theorem: is uncountable.
 is uncountable.
Soln1
(a)
We know that from a theorem of previous section that is denumerable. Thus is countable. Suppose is countable. But by first theorem of this section, we know that if and are countable then is also countable. Thus in our case we can say that is also countable. Thus is countable. But is uncountable. Thus we have a contradiction. Thus is not countable.
(b)
We need to prove that .
Suppose . Clearly we can write a onetoone and onto function from . Thus .
Thus is denumerable. Also we know that is denumerable(using a theorem of this section).
Since and and , it follows that . Since ,
it follows that .
Now we shall try to use above theorems related to set operations of denumerable sets to prove the required theorem: . We can see that . Also . Thus clearly by first theorem of this section, it follows that . Thus .
Soln2

is onetoone:
Suppose and in such that . Thus . Thus either or .
Since , it follows that . Thus . Thus . Thus and . It follows that . Thus is onetoone. 
is onto:
Suppose . Thus is a length sequence. Thus . Suppose such that . Thus we can write . Let . Since , it follows that . Thus . Thus is a sequence of length. Thus . Thus . Thus is onto.
Soln3
Let . Suppose . Thus clearly we can check that .
Suppose . Thus is finite and . Thus we can also write a finite sequence for such that where . Thus is a set of finite sequences of the countable set . It follows from theorem7.2.4 that is countable.
Since is countable, it follows that either it is finite or denumerable. Suppose is finite. Thus we can choose some such that . Suppose such that . It follows from section7.1, Ex22 that there are sequences for the set . But all of these sequences are in set . Thus for each of this sequence say , there must be a unique in . Clearly this is not possible since . Thus is not finite. Thus must be denumerable.
Soln4
Suppose is an arbitrary function. Let . Now suppose is an arbitrary element. Thus we have following possible cases:

Case :
Thus . It follows that .

Case :
Thus . Since , it follows that .
Thus in both cases . Since is arbitrary, it follows that . Thus is onto. Since is arbitrary it follows that there is no onto function such that . Thus .
Soln5
Note: I skipped proofs for proving the defined relations are functions.
(a)
Suppose such that .

is onetoone:
Suppose and such that . Suppose and . Thus . Since , it follows that . It follows from the definition of that and . Thus and . Similarly we can prove that and . Thus and .

is onto:
Suppose . Thus . Let and . Clearly . Thus is onto.
(b)
Suppose such that .

is onetoone:
Suppose and such that . Suppose . Thus . It follows that . Thus and . Thus . Similarly it can be proved that . Thus . Thus . Thus is onetoone.

is onto:
Suppose . Thus . Let and . Let . Clearly . Thus is onto.
(c)
Suppose such that:
.

is onetoone:
Suppose such that . Suppose . It follows that . Thus . Thus by the definition of , it follows . Thus . Similarly it can be proved that . Thus . Thus is onetoone.

is onto:
Suppose . Thus . Suppose . Now we can see that . Thus is onto.
(d)
We need to prove .
We know from part(c) .
TODO.
Soln6
Suppose is denumerable. Thus we can represent elements of . Suppose is a family of sets such that p where (note to take care for a_1).
Clearly is a partition as it satisfies all the properties of partition:
 is satisfied.
 is pairwise disjoint. Note that every exist in exactly one of the sets.
 . Since is denumerable, This will be correct for all .
Now we shall prove that is denumerable.
Suppose such that . Clearly is onetoone function. Thus is countable. Now if we prove that is not finite, then it will complete the proof that is denumerable. Suppose . Clearly the prime number in the list or ordered primes will contradict with .
Now suppose . Suppose such that . Clearly is onetoone. Thus is countable. Clearly there are infinite multiples of such that is their lowest common divisor. It follows that is not finite. Thus is denumerable.
Soln7
Suppose such that .

is onetoone.
Suppose and such that . Thus . Since (given), it follows that . Similarly since , it follows . Thus . Thus is onetoone.

is onto.
Suppose . Suppose and . Clearly . Thus is onto.
Soln8
TODO
Soln9
Suppose and is countable. Since is countable, we can represent it as . Now consider function such that . Now we can easily check that .
Suppose . Clearly . Thus . Since is arbitrary, it follows that .
Soln10
Suppose is the set of all words in english. Clearly is finite. Thus is countable. Consider set of all finite sequences of . It follows from theorem7.2.4 that is countable.
Let is the set of all grammtical sentences. Since each grammatical sentence if a finite sequence of english words, it follows that . Since is countable, it follows that is also countable.
Thus either is finite or denumerable. Suppose is not denumerable. Thus is must be finite. Thus for some , . It follows that total number of sentences in english is . Clearly this is not correct as we can create a new grammatical sentence such that it is not in the sentences. Thus our assumption is not correct. Thus is denumerable.
Soln11
(a)
Suppose is the set of mathematical symbols defined by english sentence. Suppose is the set of english sentences. Lets define a function , such that such that is the grammatical sentence for the symbol . Clearly is onetoone. Since is denumerable, we can choose a onetoone function . It follows that is a onetoone function. Thus is denumerable.
(b)
We will prove this by contradiction. Suppose all real numbers can be defined by english sentences. Thus we can define a onetoone function . Since is denumerable, we can choose a onetoone function . Thus is a onetoone function. Thus by the theorem 7.1.5, it follows that is countable. But is not countable. Thus we have a contradiction and our assumption is wrong. Thus there exist some real numbers that can not be defined by english sentences.