Surreal number/Counting

■ Surreal number/Counting introduces concepts involving infinity that are necessary for any student wishing to learn about surreal numbers. No claim is made that this prerequisite material is sufficient. This introduction begins with Cantor's diagonal argument. This introduction makes no attempt to the leave the reader with the rigorous understanding of surreal numbers.(Visit Surreal number/Counting for more details.)

"Counting" the dyadic rationals

Dyadic rationals are fractions where the denominators are powers of 2, i.e., is a is an integer and n is a positive integer, as shown in figure 2.

For reasons to be explained later, the counting is done in groups known as "birthays" (or simply days when each dyadic rational is "born".)

$0$ is born on day 0. On day 1, two numbers are born: $-1$, and $1$) are born on day 1. Note that $2^{0}=1$ and $2^{1}=2$, so that on day 2 we have $2^{2}=$ four new numbers: $-2$, $-{\tfrac {1}{2}}$, ${\tfrac {1}{2}}$, and $2.$) Each day the the count doubles, so that on day 3, we obtain eight numbers: $-3$, $-1{\tfrac {1}{2}}$, $-2{\tfrac {1}{4}}$, $-2{\tfrac {1}{2}}$, $2{\tfrac {1}{4}}$, $2{\tfrac {1}{2}}$, $2{\tfrac {3}{4}}$, $3$.

The rules for creating new positive numbers are as follows:

1. Each day a new positive integer is created by adding 1 to the previous day's new positive integer.
2. All other new numbers are dyadic fractions created as the midpoint between the fractions created on the previous day.
3. The negative numbers are created in a symmetric fashion. On the same day that p/q is created, −p/q is also created.

It is impossible to create all of the $2^{n}$ surreal numbers created on day $n$ until all $2^{n-1}$ surreal numbers had been created on on day $n-1.$ But after the previous day's numbers were created, the next day's numbers can be created in any order.

What does it mean to count numbers?

Fig. 3: Counting rational numbers

By definition, "counting" doesn't mean you finish, but that you can create a list that includes every item if you count long enough. Stating a formal definition of "countability" is not a trivial task. But figure 3 illustrate a well-known countable infinity.

The rational numbers are countable

0	.	9	3	3	2	4	7	0	2	0	...
0	.	6	3	7	4	9	3	3	6	1	...
0	.	2	7	7	5	5	2	4	6	6	...
0	.	4	7	5	5	6	8	2	9	7	...
0	.	8	3	8	1	4	2	2	4	9	...
0	.	2	5	2	3	5	2	5	7	6	...
0	.	8	4	4	2	2	1	1	4	1	...
0	.	6	8	6	2	1	5	1	8	3	...
0	.	1	7	8	6	6	2	8	1	5	...
⋮	.	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋱
Fig. 4: Failed attempt to count real numbers

Figure 3 shows you can count all fractions of the form $p/q$ where $p$ and $q$ are integers. Simply follow the arrows. You should be able to convince yourself that if $X$ is larger than both $p$ and $q$, then you will reach $p/q$ in no more than $X^{2}$ steps. This fact is essential to the formal proof that the rational numbers are countable.

Real numbers are not countable

Figure 4 establishes that the real numbers are uncountable. To prove this, imagine that a list of all numbers between 0 and 1 has been created, as shown in the table to the right. It is possible to find an irrational number that is not on this list as follows:

• The first number on the list is 0.9332... . Change the first digit after the decimal point from 9 to 0.
• On the second number (0.6374...), change the second digit from 3 to 4
• On the third number, change the third digit (7) to 8.

You have to do this to infinity, but when you are "done", you will have a number not on your original list. Therefore it is impossible to make an infinite list that contains all the irrational numbers in the interval (0,1). This argument can be found on a website found on Carnegie Mellon University, and it seems to contradict two ideas essential to the construction of surreal numbers:

1. Fractions are countable, while the real numbers are not.
2. The real numbers can be represented by a sequence of (dyadic) fractions.

The resolution of this faux-paradox is to note that irrational numbers and fractions like 1/3 can only be defined as surreal numbers using a sequence of didactic numbers:

$1/3=\lim _{n\to \infty }a_{n},$

where $a_{n}$ is the n-th element a sequence such as,

$1/4=0.25,\quad 1/2=0.50,\quad 3/8=0.378,\quad 11/32=0.34375,\quad \ldots$

Each of these dycactic fractions can be labeled with a unique integer on the day of its birth. But the sequence can only be defined as an infinite collection of integers. For that reason, counting the real numbers is impossible for the same reason that real numbers in decimal form cannot be counted.