Proving that the Set of Rational Numbers is Countable

In mathematics, a set is considered countable if there exists a one-to-one correspondence between the elements of the set and the natural numbers. The set of rational numbers, , is one such set. In this blog post, we'll prove that the set of rational numbers is countable.

Definition of Rational Numbers

Rational numbers are numbers that can be expressed as the quotient of two integers, i.e.,

where denotes the set of integers.

Outline of the Proof

To show that is countable, we'll follow these steps:

1. Demonstrate that the set of integers, , is countable.
2. Demonstrate that the set of pairs of integers, , is countable.
3. Conclude that , being a subset of (with the restriction that the denominator is non-zero), is countable.

Step 1: The Set of Integers is Countable

First, we need to establish that the set of natural numbers, , is countable by definition. We can then show that the set of integers, , is countable by constructing a bijective function from to .

Consider the following function:

defined by

This function maps natural numbers to integers as follows:

• Even numbers are mapped to non-negative integers.
• Odd numbers are mapped to negative integers.

Since every integer is hit exactly once, this function is bijective, proving that is countable.

Step 2: The Set of Pairs of Integers is Countable

Next, we consider the set of all ordered pairs of integers, . We'll construct a bijective function from to .

We can list the pairs of integers in a sequence that will hit every pair exactly once. One common method is to use a diagonal argument, where we list the pairs in a diagonal fashion.

For example, we can arrange pairs as follows:

This method ensures every pair appears exactly once in the sequence, establishing a bijection between and .

Step 3: The Set of Rational Numbers is Countable

Finally, we note that each rational number can be represented as a pair of integers with . This set is a subset of . Since removing a finite number of elements from a countable set leaves it countable, the set is still countable.

Thus, we can conclude that the set of rational numbers, , is countable, as it is a subset of the countable set .

Conclusion

We've proven that the set of rational numbers is countable by demonstrating that it can be placed into a one-to-one correspondence with the natural numbers. This result is significant in the study of number theory and real analysis, highlighting the interesting structure and properties of rational numbers within the continuum of real numbers.