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}|$ .

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
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"

Math

Appears 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}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered 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"

Math	Appears 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

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.

A Former Brilliant Member - 2 years, 7 months ago

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 Walker - 2 years, 7 months ago

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.

Math	Appears 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}$