4.2. Countable and Uncountable Sets

Countable sets are those sets whose cardinality is either finite or whose cardinality is same as the set of positive integers.

Countable sets have a size that can be matched with the set of positive integers. This means either they have a limited number of elements (finite) or they can be paired up with every positive integer (infinite). For example, the set of all even numbers is infinite but can be matched with the set of all natural numbers by pairing each even number with its half, thus showing it's countable.

Think of countable sets like a group of students who can be numbered. If there are 5 students, they simply have labels 1 to 5. But even if the group is large and has no end, like one student per every two seconds, you can still assign a number (1, 2, 3...) to each student, showing that the group is countable.

We first prove that the Cartesian product of the set of integers is a countable set. It is going to consist of all ordered pairs of the form (i, j) where i can be any integer, j can be any integer.

The Cartesian product of integers (ℤ x ℤ) includes all possible pairs of integers. To show that this set is countable, we need a method to organize or 'enumerate' these pairs so that every possible pair can eventually be listed. This means creating a systematic way to count each pair without missing any, even though there are infinitely many pairs.

Imagine you're organizing a dance party where each pair on the dance floor is represented by unique dance moves. Each person's move can be combined with every other person’s move, creating unique pairings. Just as you can keep track of all dance pairs without losing count, you can also track all ordered pairs of integers.

The idea is to enumerate all the points in that infinite plane such that the enumeration should be well defined and we do not miss any point in the enumeration process.

To achieve enumeration of points in the Cartesian product ℤ x ℤ effectively, we start from the origin (0, 0) and move outwards in a spiral pattern. This method ensures that we cover every possible coordinate systematically without repeating any points. By following this pattern, every possible pair is eventually listed, confirming that ℤ x ℤ is countable.

Picture a treasure map where you start digging for treasure at the center. Instead of just digging in random spots, you choose to spiral outwards, ensuring every area gets checked. This is how we systematically locate and list all points in our grid.

Next, we will see whether the set of rational numbers which I denote by this ℚ notation is countable or not.

Though it may seem impossible to list all rational numbers due to their density (there are infinitely many between any two), we can still find a method to enumerate them by using ordered pairs from ℤ x ℤ. Each rational number can be expressed as a fraction p/q, where p and q are integers. By traversing the integer pairs in a specific order, we can ensure that every rational number gets counted without missing any.

Imagine a huge library filled with every book that has ever existed, but the books are so tightly packed that it seems impossible to know what’s inside. What if you had a guide detailing how to navigate through each shelf systematically? This way, even if it seems overwhelming, you can find every book (or rational number) without missing any.

Let us consider the set of binary strings of finite length. Imagine a set Π consisting of 2 elements namely the element 0 and 1.

The set of binary strings consists of all strings that can be formed using 0s and 1s. This set, denoted as Π*, is obtained by taking all combinations of binary strings of varying lengths, including the empty string. Because finite binary strings can be listed based on length, we can show that this set is also countable.

Imagine a telephone directory; each entry can be thought of as a binary string. The first entry is like the empty string, the next has one digit, and the next has two, and so on. As each entry builds on the previous, you can create a complete list of codes in an organized way.

If you have 2 sets A and B and if they are countable then their union is also countable.

This is an important result concerning the union of countable sets. If both sets A and B can be counted or are finite, their union can also be counted. It provides a foundational property of countable sets that broadens our understanding of how to combine them while maintaining countability.

Think about two toy boxes: one filled with red toys and the other with blue toys. If you count them both separately (and they each have finite toys or ways to be organized), you can easily count the total number of toys by just combining both totals. This remains true no matter how many toys are in each box.

--