3. Countable and Uncountable Sets

So let us begin with the cardinality of finite sets first. If I ask you what is the cardinality of this set X which consists of the elements Ram, Sham, Gita, and Sita? You will say its cardinality is 4 because it has 4 elements. Another way to put it is as follows: We can say that the cardinality of the set X is 4 because there is a bijection between the set X and the set consisting of the elements 1, 2, 3, 4.

Cardinality is a way of measuring the size of a set. For finite sets, it’s simply the number of elements in the set. For example, if we have a set X with four names, namely Ram, Sham, Gita, and Sita, we determine its cardinality by counting these names, which gives us 4. Additionally, we can demonstrate this concept through bijections, where we can map elements of set X to a set of numbers like {1, 2, 3, 4}. This shows that both sets have the same size, or cardinality, because each name can be paired one-to-one with a number without any leftover or missing elements.

Think of a classroom where each student has a unique id number. If there are four students, we can assign them IDs 1 through 4. The cardinality of the class is 4, just like the cardinality of the set of ID numbers we’ve used.

How do we compare the cardinality of finite sets? If I am given set X and set Y, it is easy to see that the cardinality of set X is less than the cardinality of set Y if the number of elements in set X is less than those in set Y. This implies there is an injective function from set X to set Y.

To compare two sets, we look at their elements and see if we can create a function that maps elements from one set (say X) to another (Y) without overlap. If we can do this where every element in X is paired with a unique element in Y, then we can conclude that set X has a smaller cardinality than set Y. This is often symbolized as the cardinality of A less than or equal to B. If they are equal, there is a bijection between the two sets indicating equal cardinality.

Imagine a delivery service where X represents 3 packages and Y represents 5 delivery men. Since there are more delivery men than packages, each package can be assigned to a unique delivery man, confirming that the cardinality of packages is less than that of delivery men.

Now what are countable sets? A set A is countable if it satisfies one of the following two conditions: either it is finite, or it has the same cardinality as the set of non-negative integers. If a set doesn’t meet these conditions, it is called uncountable.

Countable sets can either contain a finite number of elements or have an infinite number of elements that align with the positive integers. Thus, if we can list the elements of those infinite sets as a sequence (1, 2, 3, ...), they are termed countably infinite. On the other hand, if a set cannot be listed in this manner, we define it as uncountable, indicating that it is a 'larger' type of infinity.

Think of counting fruits at a fruit market. If you have a few apples, they are countable since you can easily count them one by one. If you think of the total possibilities of numbers between 0 and 1 — like 0.1, 0.11, ... — it's uncountable because you can't list them all in a sequence.

If a set S is countably infinite, it can be represented by listing its elements in a sequence indexed by positive integers. This means that there’s a systematic way to enumerate the elements of S, ensuring no elements are left out.

For a set to be countable, especially if infinite, a key requirement is that there's a method to reference or list its elements systematically. If we can create such a list that goes through all elements without missing any, then we can say the set is countably infinite, meaning it has the same size as the set of positive integers.

Picture a library where every book represents an element in the set. If you can walk through the library and note down each book one by one, indexing them by a number, then that library is countably infinite. If the books disappear or are lost as you try to index them, then they are uncountable.

Let’s consider the set of odd positive integers, and let my claim be that this set is countable. By creating a bijection f(n) mapping each positive integer n to 2n-1, we can illustrate that there are as many odd positive integers as there are positive integers.

To show that the set of odd numbers is countable, we create a function f(n) = 2n - 1 that pairs every positive integer n with its corresponding odd integer. This creates a one-to-one mapping (bijection) that confirms they are equally sized in terms of cardinality: both sets (odd positive integers and positive integers) have infinite elements in a countable fashion, reinforcing the concept of countable infinity.

Imagine a friendship group where each friend is linked to a unique odd-numbered chair in a circle. Count each friend (1 to n) and pair them with chair numbers (1, 3, 5,...). Even though there are infinite chairs and friends, each friend can claim their unique seat, illustrating the concept of countability.

--