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 one-to-one 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 one-to-one:

    Suppose and in such that . Thus . Thus either or .
    Since , it follows that . Thus . Thus . Thus and . It follows that . Thus is one-to-one.

  • 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 theorem-7.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 section-7.1, Ex-22 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 one-to-one:

    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 one-to-one:

    Suppose and such that . Suppose . Thus . It follows that . Thus and . Thus . Similarly it can be proved that . Thus . Thus . Thus is one-to-one.

  • is onto:

    Suppose . Thus . Let and . Let . Clearly . Thus is onto.

(c)

Suppose such that:
.

  • is one-to-one:

    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 one-to-one.

  • 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 one-to-one 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 one-to-one. 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 one-to-one.

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

  • 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 theorem-7.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 one-to-one. Since is denumerable, we can choose a one-to-one function . It follows that is a one-to-one 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 one-to-one function . Since is denumerable, we can choose a one-to-one function . Thus is a one-to-one 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.