Peter Linz Edition 5 Exercise 11.1 Question 16 (Page No. 284)

Question

Let $S_1$ be a countable set, $S_2$ a set that is not countable, and $S_1 \subset S_2$. Show that $S_2$ must then contain an infinite number of elements that are not in $S_1$.

Answer 1

Not countable set S2 will compulsorily have infinite objects. For S1, there are 2 possibilities:

 

S1 has limited number of objects. For this automatically proved that S2 - S1 = |infinite| no of objects.

S1 has infinite number of objects. First consider an example: Set of  integers and real numbers. If you remove the integers from the real numbers, you still get infinite terms. Same will happen if we remove all the rational numbers(countable) from the set of real numbers. This happens because irrational numbers remain in the set.

 

A combined explanation:

For a countable set , its elements can be represented by using Cantor diagonalization . Such is not possible for uncountable sets because most likely elements in the set are present that are between the terms represented in the diagonalization. In case of irrational numbers there are infinite of them between every two rational numbers. Example:

 

3.144444....... and 3.155555......

a famous irrational number pi is of value 3.14159... add .1 to it, .2 to it, .01 to it .02 to it; add 0.000..(100)1 to it, similarly we have infinite number of irrational numbers between 3.1444... and 3.1555....

 

Hopefully sufficient to understand why S2-S1 will have infinite number of elements.