(No, these will not turn into a daily occurrence, but if you all like hearing about vaguely CP-related things then I'll keep writing them occasionally. Anyway.)↵
↵
You've probably heard a "proof" that $0.99\overline{9} = 1$ that looks something like this:↵
↵
- $\frac{1}{3} = 0.33\overline{3},$ (This first step is already non-rigorous, because you're already using circular reasoning to say "yeah, if a repeating decimal is not an approximation, then it is not an approximation")↵
- $1 = \frac{3}{3} = 0.99\overline{9}.$↵
↵
Or this:↵
↵
- $x = 0.99\overline{9},$ (Okay, this is fine so far...)↵
- $10x = 9.99\overline{9},$ (How are you allowed to multiply these?)↵
- $9x = 9.99\overline{9} - 0.99\overline{9} = 9,$ (Is this true? Sure, the limiting behavior does approach $9$, but that's different from being identically equal.)↵
- $x = 1$.↵
↵
So let's formalize this, starting with:↵
↵
What is a real number?↵
==================↵
↵
Before we do this, let's lay out what we're allowed to take for granted. Everything else we have to prove from first principles.↵
↵
- Integers and rational numbers exist.↵
- We can perform basic arithmetic (addition, multiplication, division, etc.) on integers and rationals.↵
↵
There are two equivalent definitions.↵
↵
Dedekind Cut↵
------------------↵
↵
A real number $r$ is defined by its set $A$ of rationals, where:↵
↵
- $A$ consists of all rational numbers strictly less than $r$.↵
- The above implies that $A$ has to be "closed downwards": if $x \in A$, and $y < x$, then $y$ must also be in $A$.↵
- There's a bonus requirement that $A$ does not contain a maximum element (it's to prevent there from being 2 representations for a rational number), but that's not important to us here.↵
↵
Two real numbers $x$ and $y$ are equal if and only if their $A$-sets $A_x$ and $A_y$ are the same.↵
↵
For example, $\sqrt{2}$ can be defined as $A_{\sqrt{2}}$ containing every rational number $q$ s.t. $q^2 < 2$.↵
↵
Infinite Cauchy Sequences↵
------------------↵
↵
We define a real number as the number that an infinite Cauchy sequence of rationals approximates.↵
↵
Loosely speaking, a sequence $a_1, a_2, ...$ is Cauchy if it converges. More formally speaking, given any $\epsilon > 0$, we can find a critical point $c$ such that for all $i > c, j > c$, we have $|a_i - a_j| < \epsilon$. In words, given any $\epsilon$, past a certain point $c$, all the elements of the sequence are close to each other within $\epsilon$.↵
↵
Then, a real number can be identified by a Cauchy sequence.↵
↵
The same real number can be identified by multiple Cauchy sequences — two Cauchy sequences $a_1, a_2, ...$ and $b_1, b_2, ...$ identify the same real number if and only if $\lim_{i \rightarrow \infty} a_i - b_i = 0$.↵
↵
For example, $\sqrt{2}$ can be defined by a Cauchy sequence of its decimal approximation: $1.4, 1.41, 1.414, 1.4142, ...$ (Technically, a decimal approximation is a nebulous term. More formally, we'll say that $a_i = \frac{k}{10^i}$, where $k$ is the highest number where $a_i^2 < 2$ still holds,)↵
↵
You can notice that $1.45, 1.415, 1.4145, 1.41425, ...$ is a different Cauchy sequence but it intuitively identifies the same $\sqrt{2}$, and formally you can see that the limit $a_i - b_i$ becomes arbitrarily small.↵
↵
Defining a repeating decimal↵
==================↵
↵
Let's formally define a repeating decimal $0.\overline{d_1 d_2 d_3 ... d_k}$.↵
↵
Let's also define the sequence $a$ as $0.d_1, 0.d_1 d_2, 0.d_1 d_2 d_3, ...$↵
↵
Under Dedekind cuts↵
------------------↵
↵
We will construct the set $A$ as follows: $q$ is in $A$ if and only if there exists some $i$ where $q < a_i$. In other words, there must exist a certain point where the successive finite decimal representations outnumber us.↵
↵
Let's take $2/3 = 0.\overline{6}$. The rational number $0.662$ is in $A$ because $0.662 < a_3 = 0.666$.↵
↵
Under Cauchy sequences↵
------------------↵
↵
This one is easier. It's literally just the sequence $a$ of the successive finite decimal representations.↵
↵
Finally showing $0.\overline{9} = 1$↵
==================↵
↵
Dedekind cuts↵
------------------↵
↵
We'll show that $A_{0.\overline{9}}$ and $A_{1}$ are the same set by showing both are subsets of each other.↵
↵
$q \in A_{0.\overline{9}} \rightarrow q \in A_{1}$↵
↵
- $a_i < 1$ for all $a_i$ in the finite representations of $0.\overline{9}$, so if $q \in A_{0.\overline{9}}$, then for some $i$, we have $q < a_i < 1$ and $q \in A_{1}$.↵
↵
$q \in A_{1} \rightarrow q \in A_{0.\overline{9}}$↵
↵
- Take any $q < 1$. It must have a difference $d = 1 - q > 0$. Then, $q < a_i$ is equivalent to $d > 1 - a_i$. We have $a_i = 0.999...9_{\textit{i nines}}$, or $1 - a_i = 10^{-i}$, so we only need to show that there exists some $i$ where $d > 10^{-i}$. Clearly, $10^{-i}$ can be arbitrarily small, so choosing a high enough $i$ proves that $q \in A_{0.\overline{9}}$.↵
↵
Therefore, both $A$-sets are the same, and these are the same real number.↵
↵
Cauchy sequences↵
------------------↵
↵
The sequence for $0.\overline{9}$ is $a_i = 1 - 10^{-i}$: $0.9, 0.99, 0.999, ...$↵
↵
The sequence for $1$ is $b_i = 1$: $1, 1, 1, ...$↵
↵
So we have $|a_i - b_i| = 10^{-i}$, and this clearly approaches $0$ as $i \rightarrow \infty$.↵
↵
Therefore, these are the same real number.↵
↵
Bonus: defining arithmetic with real numbers↵
==================↵
↵
Dedekind cuts↵
------------------↵
↵
Given $x: A_a$ and $y: A_b$, define $A_{x+y}$ as the set containing all $q$ where $q=\le cd, c \in A_a, d \in A_b$.↵
↵
Multiplication can be defined the same way.↵
↵
Cauchy sequences↵
------------------↵
↵
Given $x: [x_1, x_2, ...]$ and $y: [y_1, y_2, ...]$, define $z = x+y$ as $[z_i = x_i + y_i]$.↵
↵
Multiplication can again be defined the same way.
↵
You've probably heard a "proof" that $0.99\overline{9} = 1$ that looks something like this:↵
↵
- $\frac{1}{3} = 0.33\overline{3},$ (This first step is already non-rigorous, because you're already using circular reasoning to say "yeah, if a repeating decimal is not an approximation, then it is not an approximation")↵
- $1 = \frac{3}{3} = 0.99\overline{9}.$↵
↵
Or this:↵
↵
- $x = 0.99\overline{9},$ (Okay, this is fine so far...)↵
- $10x = 9.99\overline{9},$ (How are you allowed to multiply these?)↵
- $9x = 9.99\overline{9} - 0.99\overline{9} = 9,$ (Is this true? Sure, the limiting behavior does approach $9$, but that's different from being identically equal.)↵
- $x = 1$.↵
↵
So let's formalize this, starting with:↵
↵
What is a real number?↵
==================↵
↵
Before we do this, let's lay out what we're allowed to take for granted. Everything else we have to prove from first principles.↵
↵
- Integers and rational numbers exist.↵
- We can perform basic arithmetic (addition, multiplication, division, etc.) on integers and rationals.↵
↵
There are two equivalent definitions.↵
↵
Dedekind Cut↵
------------------↵
↵
A real number $r$ is defined by its set $A$ of rationals, where:↵
↵
- $A$ consists of all rational numbers strictly less than $r$.↵
- The above implies that $A$ has to be "closed downwards": if $x \in A$, and $y < x$, then $y$ must also be in $A$.↵
- There's a bonus requirement that $A$ does not contain a maximum element (it's to prevent there from being 2 representations for a rational number), but that's not important to us here.↵
↵
Two real numbers $x$ and $y$ are equal if and only if their $A$-sets $A_x$ and $A_y$ are the same.↵
↵
For example, $\sqrt{2}$ can be defined as $A_{\sqrt{2}}$ containing every rational number $q$ s.t. $q^2 < 2$.↵
↵
Infinite Cauchy Sequences↵
------------------↵
↵
We define a real number as the number that an infinite Cauchy sequence of rationals approximates.↵
↵
Loosely speaking, a sequence $a_1, a_2, ...$ is Cauchy if it converges. More formally speaking, given any $\epsilon > 0$, we can find a critical point $c$ such that for all $i > c, j > c$, we have $|a_i - a_j| < \epsilon$. In words, given any $\epsilon$, past a certain point $c$, all the elements of the sequence are close to each other within $\epsilon$.↵
↵
Then, a real number can be identified by a Cauchy sequence.↵
↵
The same real number can be identified by multiple Cauchy sequences — two Cauchy sequences $a_1, a_2, ...$ and $b_1, b_2, ...$ identify the same real number if and only if $\lim_{i \rightarrow \infty} a_i - b_i = 0$.↵
↵
For example, $\sqrt{2}$ can be defined by a Cauchy sequence of its decimal approximation: $1.4, 1.41, 1.414, 1.4142, ...$ (Technically, a decimal approximation is a nebulous term. More formally, we'll say that $a_i = \frac{k}{10^i}$, where $k$ is the highest number where $a_i^2 < 2$ still holds,)↵
↵
You can notice that $1.45, 1.415, 1.4145, 1.41425, ...$ is a different Cauchy sequence but it intuitively identifies the same $\sqrt{2}$, and formally you can see that the limit $a_i - b_i$ becomes arbitrarily small.↵
↵
Defining a repeating decimal↵
==================↵
↵
Let's formally define a repeating decimal $0.\overline{d_1 d_2 d_3 ... d_k}$.↵
↵
Let's also define the sequence $a$ as $0.d_1, 0.d_1 d_2, 0.d_1 d_2 d_3, ...$↵
↵
Under Dedekind cuts↵
------------------↵
↵
We will construct the set $A$ as follows: $q$ is in $A$ if and only if there exists some $i$ where $q < a_i$. In other words, there must exist a certain point where the successive finite decimal representations outnumber us.↵
↵
Let's take $2/3 = 0.\overline{6}$. The rational number $0.662$ is in $A$ because $0.662 < a_3 = 0.666$.↵
↵
Under Cauchy sequences↵
------------------↵
↵
This one is easier. It's literally just the sequence $a$ of the successive finite decimal representations.↵
↵
Finally showing $0.\overline{9} = 1$↵
==================↵
↵
Dedekind cuts↵
------------------↵
↵
We'll show that $A_{0.\overline{9}}$ and $A_{1}$ are the same set by showing both are subsets of each other.↵
↵
$q \in A_{0.\overline{9}} \rightarrow q \in A_{1}$↵
↵
- $a_i < 1$ for all $a_i$ in the finite representations of $0.\overline{9}$, so if $q \in A_{0.\overline{9}}$, then for some $i$, we have $q < a_i < 1$ and $q \in A_{1}$.↵
↵
$q \in A_{1} \rightarrow q \in A_{0.\overline{9}}$↵
↵
- Take any $q < 1$. It must have a difference $d = 1 - q > 0$. Then, $q < a_i$ is equivalent to $d > 1 - a_i$. We have $a_i = 0.999...9_{\textit{i nines}}$, or $1 - a_i = 10^{-i}$, so we only need to show that there exists some $i$ where $d > 10^{-i}$. Clearly, $10^{-i}$ can be arbitrarily small, so choosing a high enough $i$ proves that $q \in A_{0.\overline{9}}$.↵
↵
Therefore, both $A$-sets are the same, and these are the same real number.↵
↵
Cauchy sequences↵
------------------↵
↵
The sequence for $0.\overline{9}$ is $a_i = 1 - 10^{-i}$: $0.9, 0.99, 0.999, ...$↵
↵
The sequence for $1$ is $b_i = 1$: $1, 1, 1, ...$↵
↵
So we have $|a_i - b_i| = 10^{-i}$, and this clearly approaches $0$ as $i \rightarrow \infty$.↵
↵
Therefore, these are the same real number.↵
↵
Bonus: defining arithmetic with real numbers↵
==================↵
↵
Dedekind cuts↵
------------------↵
↵
Given $x: A_a$ and $y: A_b$, define $A_{x+y}$ as the set containing all $q$ where $q
↵
Multiplication can be defined the same way.↵
↵
Cauchy sequences↵
------------------↵
↵
Given $x: [x_1, x_2, ...]$ and $y: [y_1, y_2, ...]$, define $z = x+y$ as $[z_i = x_i + y_i]$.↵
↵
Multiplication can again be defined the same way.
