Real numbers are uncountable

1

Edited by Jason Gross, Eric B last updated 21st Oct 2016

Title

Tab title

Tab subtitle

We present a variant of Cantor's diagonalization argument to prove the real numbers are uncountable. This constructively proves that there exist uncountable sets ^[1].

We use the decimal representation of the real numbers. An overline (

\bar{\phantom{9}}

) is used to mean that the digit(s) under it are repeated forever. Note that (if ; otherwise, we need to continue carrying the one); . Furthermore, these are the only equivalences between decimal representations; there are no other real numbers with multiple representations, and these real numbers have only these two decimal representations.

Theorem The real numbers are uncountable.

Proof Suppose, for contradiction, that the real numbers are countable; suppose that

f: \mathbb Z^+ \twoheadrightarrow \mathbb R

is a surjection. Let denote the decimal digit of , so that the fractional part of is Then define a real number with so that is 5 if , and 6 if . Then there can be no such that since . Thus is not surjective, contradicting our assumption, and is uncountable.

Note that choosing 5 and 6 as our allowable digits for

r'

side-steps the issue that . %%

Summaries

You can edit summaries by clicking on them, reorder them by dragging, or add a new one (up to 3). By default you should avoid creating more than one summary unless the subject matter benefits substantially from multiple kinds of explanation.

Summary

The 'non-adversarial principle' states: By design, the human operators and the AGI should never come into conflict.

Since every event inside an AI is ultimately the causal result of choices by the human programmers, we should not choose so as to run computations that are searching for a way to hurt us. At the point the AI is even trying to outwit us, we've already screwed up the design; we've made a foolish use of computing power.

E.g., according to this principle, if the AI's server center has a switch that shuts off the electricity, our first thought should not be, "How do we have guards with guns defending this off-switch so the AI can't destroy it?" Our first thought should be, "How do we make sure the AI wants this off-switch to exist?"

Tab title

We present a variant of Cantor's diagonalization argument to prove the real numbers are uncountable. This constructively proves that there exist uncountable sets ^[1].

We use the decimal representation of the real numbers. An overline ( ) is used to mean that the digit(s) under it are repeated forever. Note that $a . b c d \dots z ¯ ¯ ¯ 9 = a . b c d \dots (z + 1) ¯ ¯ ¯ 0$ (if $z < 9$ ; otherwise, we need to continue carrying the one); $\sum_{i = k}^{\infty} 10^{- k} \cdot 9 = 1 \cdot 10^{- k + 1} + \sum_{i = k}^{\infty} 10^{- k} \cdot 0$ . Furthermore, these are the only equivalences between decimal representations; there are no other real numbers with multiple representations, and these real numbers have only these two decimal representations.

Theorem The real numbers are uncountable.

Proof Suppose, for contradiction, that the real numbers are countable; suppose that $f : Z^{+} ↠ R$ is a surjection. Let $r_{n}$ denote the $n^{th}$ decimal digit of $r$ , so that the fractional part of $r$ is $r_{1} r_{2} r_{3} r_{4} r_{5} \dots$ Then define a real number $r^{'}$ with $0 \leq r^{'} < 1$ so that $r_{n}^{'}$ is 5 if $(f (n))_{n} \neq 5$ , and 6 if $(f (n))_{n} = 5$ . Then there can be no $n$ such that $r^{'} = f (n)$ since $r_{n}^{'} \neq (f (n))_{n}$ . Thus $f$ is not surjective, contradicting our assumption, and $R$ is uncountable. $□$

Note that choosing 5 and 6 as our allowable digits for $r^{'}$ side-steps the issue that $0. ¯ ¯ ¯ 9 = 1. ¯ ¯ ¯ 0$ . %%

^{^︎}
Since the real numbers are an example of one.

Parents:

Real number

Uncountability