4.1.2. Examples of Countably Infinite Sets

Hello everyone welcome to this lecture on examples of countably infinite sets.

(Refer Slide Time 00:27) So just to recap in the last lecture we introduced the notion of 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. So the plan for this lecture is as follows. We will see several examples of countably infinite sets and we will also discuss some properties of countable sets specifically in the context of infinite sets.

In this opening section, the lecturer introduces the topic of countably infinite sets. Countable sets are defined as those that can be matched one-to-one with the set of positive integers. This means that such sets either have a finite number of elements or can be arranged in a sequence that extends indefinitely, akin to the counting numbers (1, 2, 3, ...). The goal of the lecture is to explore various examples of these sets and delve into their properties, particularly how they exist within the realm of infinite sets.

Think of countable sets like rows of chairs in an infinitely long auditorium. Each chair represents an element, and you can count them one by one, just like you can count natural numbers. Even if the auditorium has an infinite number of chairs, you can still label each one with a number (1st, 2nd, 3rd, etc.), demonstrating that the chairs can be counted—a key characteristic of countable sets.

So we first prove that the Cartesian product of the set of integers is a countable set. So again this might look non-intuitive, you have many elements in the Cartesian product of the set of integers compared to the set of integers itself because when I say that Cartesian product 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. But what this theorem says is that the number of elements in the set ℤ x ℤ is same as the number of elements in the set of positive integers.

The lecturer starts with the Cartesian product of the integers (ℤ) to demonstrate that it is countable. The Cartesian product ℤ x ℤ consists of all possible ordered pairs (i, j) where both i and j are integers. Intuitively, it seems there are more elements in ℤ x ℤ than in ℤ itself, but the lecturer will show that there exists a way to enumerate all these ordered pairs such that they can be matched one-to-one with the positive integers.

Imagine a city grid where each intersection represents a pair of coordinates (i, j). Though there are infinitely many intersections, we can systematically explore each one by moving in patterns, much like counting the intersections sequentially. This shows that even though there are infinitely many pairs, we can still arrange them in a countable way, similar to how we count the streets in a city.

So we are going to prove that. So remember in the last lecture we proved that whenever you want to prove that an infinite set is countable either you gave an explicit bijection between that set and the set of positive integers. Or you give a well-defined sequence or a rule according to which you specify or list down the elements of the given set which you want to prove to be countably infinite. And argue that every element in that set will appear in the sequence that you are specifying.

To prove the countability of ℤ x ℤ, the lecturer emphasizes the need for a well-defined enumeration process. This means creating a list or a rule that allows us to systematically capture every element (pair) in ℤ x ℤ without missing any. Such enumeration could involve establishing a sequence where each element corresponds uniquely to a positive integer, thus illustrating that ℤ x ℤ can be counted like the integers.

Think of it like a library containing infinite shelves, where each shelf has an infinite number of books arranged in a specific order. To ensure you can access every book, you create a method to count through them systematically, ensuring not a single book gets overlooked—a logical approach to demonstrating that the library's collection is countable.

So the idea is very clever here what we do is... so I will make this whole trip again. So what was the trip? I started with (0, 0) go right go up go left left down down and then I will again make this circular rotation. So what I will do is from my current point I will go right 1 unit again right 1 unit again right 1 unit. And then go up up. and then continue this process.

The lecturer describes a clever method to enumerate the elements of the Cartesian product of integers visually on a two-dimensional plane. Starting from the origin (0, 0), the process involves moving through the plane in a spiral-like manner: right, up, left, down, ensuring that every point is visited. This systematic traversal guarantees that every possible ordered pair will eventually appear in the enumeration, proving that the set is countable.

Picture a firefighter mapping out a burning building. They start from a corner and systematically check each room in a spiral pattern, ensuring that no room is left unchecked. Just like the firefighter's method ensures every area is inspected, this enumeration ensures that every point in the plane is reached and counted.

Now, we will see next whether the set of rational numbers which I denote by this ℚ notation is countable or not. Now intuitively it might look the answer is no because definitely rational numbers is a super set of the set of the integers. And looks like there is no way of sequencing because the fundamental fact about rational numbers is that you take any 2 rational numbers there are infinitely many more rational numbers between the same 2 rational numbers.

The instructor now addresses the set of rational numbers (ℚ). At first glance, it may seem that since rational numbers consist of fractions made from integers, and there are infinitely many between any two fractions, they could be uncountable. However, the lecturer indicates that despite this intuition, there exists a clever way to enumerate rational numbers, similar to how they enumerated the Cartesian product of integers.

Imagine trying to fit infinitely many grains of sand between two rocks on a beach. It seems impossible to count them all. However, if you systematically gather them piece by piece and note down each fraction of sand filled between the rocks, you find you can indeed make a list, demonstrating that even infinite quantities can be sorted into a countable sequence.

Now if I apply the rule on (0, 0) so if I start with (0, 0) so my p is 0 and q is 0. So my rule says that if q is 0 do not do anything go to the next element. And my next (p, q) is (1, 0) and again q is 0. So my rule says do not do anything.

The lecturer outlines a systematic approach for enumerating the rational numbers based on the previously discussed enumeration of ordered pairs. By examining each pair (p, q) from the integer plane, they apply rules to skip over pairs where q equals zero (as those do not correspond to valid rational numbers) and note only the valid ones. This methodical approach guarantees all possible rational numbers can be listed without omissions.

Think of this as a chef carefully selecting ingredients from a pantry of infinite shelves. The chef chooses only those items that fit their recipe (valid pairs), discarding any that don't fit (q = 0). By doing so in a systematic order, they ensure that every ingredient needed for a perfect dish (all rational numbers) is eventually selected.

Now let us consider the set of binary strings of finite length. What exactly that means? ... So it should be now clear that each subset Π(i) is finite.

The lecturer now discusses binary strings of finite length, denoted as Π*, which are combinations of the digits 0 and 1. Each set Π(i) contains all binary strings of a specific length i, resulting in a finite number of strings for any given length. When all finite sets of binary strings are combined, they create an infinite set of all possible binary strings of limited length—demonstrating that this larger set is also countable.

Consider the process of building a Lego structure using only 0s and 1s as bricks. You create all possible structures of legos (strings) that can be built with a given number of blocks (length), but as you increase the number of blocks, you find there are infinitely many patterns to build. However, each pattern uses a finite amount of bricks, showing that even infinite possibilities can be categorized.

So the answer is yes we can prove that the set Π* is indeed countably infinite. And what we will do is to prove this theorem we will show a possible valid listing of the elements of Π*.

The instructor establishes that the set of binary strings (Π*) can be enumerated countably. Starting from the simplest case (the empty string), the lecturer explains that an increasing number of binary strings can be organized by their length and listed in binary order. As each length is processed systematically, every possible string can be generated and will appear in the enumeration, showcasing countability.

Think of a vending machine that can dispense snacks in binary combinations (e.g., 0s for snack A, 1s for snack B). As you build up to larger combinations (more blocks), each unique combination corresponds to a string of varying length. The vending machine ensures that every combination eventually appears, much like how we can count all possible binary strings.

--