Problem 47 - Discrete Mathematics with Applications

Question

Prove. The set \(Q^{+}\) of positive rational numbers is countable.

Step-by-Step Solution

Answer

To prove that the set of positive rational numbers, \(Q^{+}\), is countable, we can construct a bijection between \(Q^{+}\) and natural numbers, \(\mathbb{N}\). We arrange the positive rational numbers in a table, and then list them in a diagonal sequence. This sequence gives us a bijection \(f : \mathbb{N} \to Q^{+}\), mapping each positive rational number to a unique natural number. Since there is a bijection between \(Q^{+}\) and \(\mathbb{N}\), the set of positive rational numbers is countable.

Step 1: Define the positive rational numbers set

Denote the set of positive rational numbers as \(Q^{+}\). A positive rational number can be represented as a fraction \(\frac{m}{n}\), where m and n are positive integers. Thus, \[Q^{+} = \Big\{ \frac{m}{n} \Big | m, n \in \mathbb{N} \Big\}\]

Step 2: Arrange the positive rational numbers in a table

Now we will setup a table with the rows and columns representing the positive integers. We will place the positive rational number \(\frac{m}{n}\) in the cell in row m and column n of the table. In each cell, we will only place reduced fractions with numerator m and denominator n. Here's the beginning of such a table: ``` 1 2 3 4 5 ... --------+-------+-------+-------+------- 1 | 1/1 | 1/2 | 1/3 | 1/4 | 1/5 | ... --------+-------+-------+-------+------- 2 | 2/1 | | 2/3 | | 2/5 | ... --------+-------+-------+-------+------- 3 | 3/1 | 3/2 | | 3/4 | | ... --------+-------+-------+-------+------- 4 | 4/1 | | 4/3 | | 4/5 | ... --------+-------+-------+-------+------- 5 | 5/1 | 5/2 | | 5/4 | | ... --------+-------+-------+-------+------- ... ```

Step 3: Arrange the positive rational numbers in a sequence

We can now list all of the positive rational numbers in a diagonal sequence that moves across the table, as follows: ``` 1 2 3 4 5 ... 1 | (1)1/1 | (2)1/2 | (6)1/3 | (12)1/4 | (20)1/5 | ... --------+-------+-------+-------+------- 2 | (3)2/1 | (5)2/3 | (9)2/5 | (15)2/7 | ... --------+-------+-------+-------+------- 3 | (4)3/1 | (8)3/2 | (13)3/4 | ... --------+-------+-------+-------+------- 4 | (7)4/1 | (11)4/3 | ... --------+-------+-------+------- 5 | (10)5/1 | (16)5/2 | ... --------+-------+-------+------- ```

Step 4: Define a bijection between positive rational numbers and natural numbers

The diagonal sequence defined in Step 3 gives us a bijection \(f : \mathbb{N} \to Q^{+}\), which maps each positive rational number \(\frac{m}{n}\) in the table to a unique natural number. This bijection is defined by the position of the positive rational number in the sequence. For example, \(f(1) = 1/1\), \(f(2) = 1/2\), \(f(3) = 2/1\), and so on.

Step 5: Conclude that the set of positive rational numbers is countable

Since we've shown that there is a bijection between the set of positive rational numbers and the set of natural numbers, we can conclude that the set of positive rational numbers, \(Q^{+}\), is countable.

Key Concepts

Positive Rational Numbers

Positive rational numbers are numbers that can be expressed as a fraction \( \frac{m}{n} \) where \( m \) and \( n \) are both positive integers and \( m \) is in the numerator, and \( n \) is in the denominator. For example, \( \frac{1}{2} \) and \( \frac{3}{4} \) are positive rational numbers. These fractions represent points on the number line between whole numbers.
It's important to note that positive rational numbers exclude zero and all negative fractions.
The reason they can be expressed this way is because of their position between integers, creating infinite possibilities for fractional values.

Bijection

A bijection is a one-to-one correspondence between the elements of two sets. In simpler terms, every element from one set is paired with only one unique element from another set, and vice versa.
In our case, we are creating a bijection between the set of positive rational numbers \( Q^{+} \) and the natural numbers set \( \mathbb{N} \). This means each positive rational number corresponds to one natural number, and this correspondence covers every positive rational number.
This is crucial for demonstrating countability because it shows that despite the infiniteness of \( Q^{+} \), it can still be systematically arranged in a sequence, much like the sequence of natural numbers.

Natural Numbers

Natural numbers are the basic building blocks of mathematics. They are the set of positive integers beginning from 1, which typically include \(1, 2, 3, \ldots\).
Natural numbers are simple yet powerful tools used to count objects, order them, and establish basic mathematical concepts.
In the context of counting infinite sets, like positive rational numbers, natural numbers serve as a reference point or a baseline to establish whether a set is countable.
This is because each element in an infinite set can potentially pair directly with a specific natural number, creating a clear, continuous list.

Diagonal Argument

The diagonal argument is a clever method to systematically arrange items in an infinite grid. It allows us to traverse through every element without missing any.
In this exercise, the diagonal argument is used to list all positive rational numbers, effectively demonstrating a way they can be matched with natural numbers.
By setting up a grid with row and column indices representing positive integers, we construct this table where each cell \(\frac{m}{n}\) holds a positive rational number. By moving diagonally across the grid, we ensure each positive rational number is paired with a unique natural number.

• Start at \(1/1\), move diagonally down and to the right.
• Visit \(1/2, 2/1, 3/1, 2/2\), and so on.

This process confirms that no fraction in this setup is forgotten, proving the effective correspondence between the sets.