Proving the Cardinality of Rational Numbers is the Same as Natural Numbers
In mathematical theory, it is intriguing to demonstrate that the set of rational numbers (mathbb{Q}) has the same cardinality as the set of natural numbers (mathbb{N}). This is achieved by constructing a bijection—a one-to-one and onto function—between these two sets. Let's delve into the steps and explanation behind this fascinating result.
Understanding the Structure of Rational Numbers
Rational numbers can be expressed as fractions (frac{p}{q}) where (p) is an integer and (q) is a non-zero integer. We represent each rational number as an ordered pair ((p, q)) with (q eq 0).
Countable Sets
Both the set of integers (mathbb{Z}) and the set of natural numbers (mathbb{N}) are countable sets. Integers can be enumerated as follows:
[mathbb{Z} {dots -3, -2, -1, 0, 1, 2, 3, dots}]
To show that (mathbb{Z}) is countable, we can create a bijection with (mathbb{N}). This is a crucial step as it establishes the foundation for understanding the countability of the rationals.
Create a List of Rational Numbers
The rational numbers can be organized in a two-dimensional grid where the rows correspond to integers (p) (numerator) and the columns correspond to positive integers (q) (denominator). The grid looks like this:
1 1 1 2 1 3 ...
- 2 1 2 2 2 3 ...
- 3 1 3 2 3 3 ...
By traversing this grid diagonally, we can generate a sequence that includes every rational number.
Diagonal Argument
To traverse the grid diagonally, we follow these steps:
Start at (1/1). Move to (1/2, 2/1). Then to (1/3, 2/2, 3/1), and so on.This traversal generates a sequence of rational numbers that can be indexed by natural numbers.
Since fractions can be equivalent (e.g., (1/2 2/4)), we need to ensure that each rational number is represented only once. This is achieved by considering only fractions in their simplest form where (p) and (q) are coprime, i.e., (gcd(p, q) 1).
Construct the Bijection
The traversal creates a sequence of rational numbers which can be indexed by natural numbers. We can define a function (f: mathbb{N} to mathbb{Q}) that maps each natural number to a unique rational number in the order determined by our diagonal traversal.
Conclusion
By establishing a way to list all rational numbers and pairing each one with a unique natural number, we have shown that there exists a bijection between (mathbb{Q}) and (mathbb{N}). This means that the cardinality of the set of rational numbers is the same as that of the natural numbers.
The result is that the set of rational numbers (mathbb{Q}) is countable and it has the same cardinality as the natural numbers (mathbb{N}), denoted as (mathbb{Q} mathbb{N}).