A short proof that rationals are countable

An infinite set \(S\) is said to be countable if it has the same cardinality as that of the set of integers \(\mathbb{Z}\), or \(|S| = |\mathbb{Z}|\). For example, the two sets

\[ \{5,10,15,20,...\} \quad \{1,2,3,4,5,6,7,...\} \]

Have the same cardinality, or "number" of elements, despite there being larger gaps between the elements of the first set than there are elements of the second. This is because you can take any element \(a\) from the second set and map it directly to an element \(b\) in \(\mathbb{Z}\) by \(b=5a\).

Now, let's look at the set of rational numbers, or \(\mathbb{Q}\)

\[ \{1/2,1/3,1/4,2/3,2/5,2/7,...,1/8106832527,...,901/23,...\} \]

It's not immediately obvious that this would have the same cardinality as that of the integers. Surely, there have to be too many possible combinations of numbers to be able to map them all to the integers. However, there is a very clever way to do so with a method resembling Gödel's numbering scheme. First, note that any rational number can be written as a fraction, or \(p/q\). Since every rational number is uniquely defined by \(p\) and \(q\), this means that every element in the set of positive rational numbers can be indexed by these two numbers. Now, we can assign every element of \(\mathbb{Q}\) to an element of \(\mathbb{Z}\) through the following scheme:

\[ \mathbb{Q} \mapsto \mathbb{Z} \] \[ p/q \mapsto 2^{p}3^{q} \]

Where \(2\) and \(3\) were chosen because they are prime numbers, although you can replace them with any other pair of prime numbers. To extend this mapping to include both positive and negative elements of \(\mathbb{Q}\), simply append a third prime number with either \(0\) or \(1\) in its exponent to denote sign. This completes the proof that \(|\mathbb{Q}| = |\mathbb{Z}|\).

Note by Levi Adam Walker
2 weeks ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

Sort by:

Top Newest

Here's an interesting thought experiment: if the field of rational numbers is equally as large as the ring of integers, how do we explain the fact that there are elements of the rational number field that are not in the integer field? Algebraically and arithmetically, the idea you have presented would not make sense (especially to the ancients), and one could make the case that the logic behind all this is wrong. Obviously, we could talk about "levels of infinity", but how can we distinguish them when we can never objectively quantify them? I guess this is something that needs to be discussed and debated by the wider mathematics community.

Gennady Notowidigdo - 4 days, 23 hours ago

Log in to reply

It's an interesting thought for sure. Another consequence is that the set of all numbers is just as big as the set of all squares. That is, the set \( \{1,2,3,4,5,\cdots\} \) is just as large as the set \( \{1,4,9,16,25,\cdots\} \)! What saves some sensibility, though, is the concept of the density of a set: prime numbers, even numbers, multiples of 5 are all "dense" sets, while squares and twin primes aren't considered dense, despite the former having the same cardinality as the integers and the latter believed to (but not proven) to do so as well.

Levi Adam Walker - 4 days, 9 hours ago

Log in to reply

I am of the belief that there is only one such concept of infinity, and that attempts at "quantifying" infinity are not only futile but absolutely ridiculous. I do get a lot of heat for this point of view, but if such is to be believed, then the concept of an "infinite set" has to be questioned because, as pointed out in what you have written in the note, the existence of "infinite sets" would imply results that are not just non-intuitive but structurally false. To say that rational numbers and integers have the "same cardinality", which by implication means that they are structurally identical, would be ludicrous and stupid in my opinion. To take the example in your reply, if it is to be believed that "the set of all numbers" is "just as big" as "the set of all squares", then by implication it must be structurally identical (which it is obviously not; as a really rough example, think about closure under addition).

I must stress that this is just my opinion on what you have written, but this Cantorian way of thinking has so many flaws that they need to be brought up. If anyone is looking for an ad as to the flaws of Cantorian set theory, this is it.

Gennady Notowidigdo - 4 days, 2 hours ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...