Commit | Line | Data |
---|---|---|
8484c2fd AT |
1 | \newpage |
2 | \section{Notes: Chapter 1} | |
3 | ||
420b0302 | 4 | \subsection{Review} |
cc0282e4 | 5 | |
420b0302 AT |
6 | In the first chapter, Knuth provides two axioms. |
7 | ||
8 | \begin{axiom} \label{ax:number-definition} | |
cc0282e4 AT |
9 | Every number corresponds to two sets of previously created numbers, such that |
10 | no member of the left set is greater than or equal to any member of the right | |
11 | set. | |
12 | \end{axiom} | |
13 | ||
14 | For example, if $x = \surreal{X_L}{X_R}$, then $\forall x_L \in X_L$, it must | |
15 | hold $\forall x_R \in X_R$ that $x_L \ngeq x_R$. | |
16 | ||
420b0302 | 17 | \begin{axiom} \label{ax:leq-comparison} |
cc0282e4 AT |
18 | One number is less than or equal to another number if and only if no member of |
19 | the first number's left set is greater than or equal to the second number, and | |
20 | no member of the second number's right set is less than or equal to the first | |
21 | number. | |
22 | \end{axiom} | |
23 | ||
24 | For example, the relation $\surreal{X_L}{X_R} = x \leq y = \surreal{Y_L}{Y_R}$ | |
25 | holds true if and only if both $X_L \ngeq y$ and $Y_R \nleq x$. | |
26 | ||
27 | With no surreal numbers yet in our possession, we construct the first surreal | |
28 | number using the null set (or void set, as Knuth calls it) as both the left and | |
29 | right set. Although we have not yet examined its properties, Knuth names this | |
30 | number ``zero''. Thus, $\surreal{}{} = 0$. | |
31 | ||
32 | As his final trick, Knuth defines a second generation of surreal numbers using | |
af665c3c | 33 | $0$ in the left and right set, naming them $1$ and $-1$ and establishing the |
cc0282e4 AT |
34 | following relation. |
35 | ||
af665c3c | 36 | $$-1 \equiv \surreal{}{0} \leq 0 \equiv \surreal{}{} \leq 1 \equiv \surreal{0}{}$$ |
cc0282e4 | 37 | |
420b0302 AT |
38 | |
39 | \subsection{Exploration} | |
40 | ||
41 | \begin{defi} \label{defi:generation} | |
42 | A \emph{generation} shall refer to the numbers generated by applying Axiom | |
af665c3c AT |
43 | \autoref{ax:number-definition} to all possible combinations of extant numbers. |
44 | Generations are numbered sequentially such that generation-0 consists of the | |
45 | number $0$, generation-1 consists of the numbers $-1$ and $1$, etc. | |
420b0302 AT |
46 | \end{defi} |
47 | ||
48 | Working by hand with Axiom \autoref{ax:number-definition}, generation-2 | |
49 | contains the numbers shown below. | |
50 | ||
51 | $$\surreal{-1}{}, \surreal{1}{}, \surreal{-1,0}{}, \surreal{0,1}{},$$ | |
52 | $$\surreal{-1,1}{}, \surreal{-1,0,1}{}, \surreal{-1}{1}, \surreal{0}{1},$$ | |
53 | $$\surreal{-1,0}{1}, \surreal{}{1}, \surreal{-1}{0}, \surreal{}{-1},$$ | |
54 | $$\surreal{-1}{0,1}, \surreal{}{0,1}, \surreal{}{-1,0}, \surreal{}{-1,1},$$ | |
55 | $$\surreal{}{-1,0,1}$$ | |
56 | ||
57 | \begin{defi} \label{defi:similar} | |
58 | Two numbers $X$ and $Y$ are \emph{similar} iff, per Axiom | |
59 | \autoref{ax:leq-comparison}, $X \leq Y$ and $Y \leq X$. This is denoted by $X | |
60 | \similar Y$. | |
61 | \end{defi} | |
62 | ||
420b0302 | 63 | Using this definition, the twenty numbers from generations 0-2 break down into |
af665c3c | 64 | no more than ten equivalence classes based on similarity, as shown below. |
420b0302 | 65 | |
ef10cd2c | 66 | $$\surreal{0}{} \similar \surreal{-1,0}{}$$ |
420b0302 | 67 | $$\surreal{}{}$$ |
ef10cd2c | 68 | $$\surreal{}{0} \similar \surreal{}{0,1}$$ |
420b0302 | 69 | $$\surreal{-1}{}$$ |
ef10cd2c | 70 | $$\surreal{1}{} \similar \surreal{0,1}{} \similar \surreal{-1,1}{} \similar \surreal{-1,0,1}{}$$ |
420b0302 | 71 | $$\surreal{-1}{1}$$ |
ef10cd2c | 72 | $$\surreal{0}{1} \similar \surreal{-1,0}{1}$$ |
420b0302 | 73 | $$\surreal{}{1}$$ |
ef10cd2c AT |
74 | $$\surreal{-1}{0} \similar \surreal{-1}{0,1}$$ |
75 | $$\surreal{}{-1} \similar \surreal{}{-1,0} \similar \surreal{}{-1,1} \similar \surreal{}{-1,0,1}$$ | |
420b0302 AT |
76 | |
77 | From this we see that, since Axiom \autoref{ax:leq-comparison} makes its | |
78 | comparison element-wise, every surreal number generated by our current methods | |
79 | must be similar to a surreal number containing one or zero elements in its left | |
af665c3c AT |
80 | and right sets since only the largest member of the left set and smallest |
81 | member of the right set are important. This motivates the following definition. | |
420b0302 AT |
82 | |
83 | \begin{defi} \label{defi:reduced-form} | |
84 | The \emph{reduced form} for a surreal number $X = \surreal{X_L}{X_R}$ is | |
85 | defined as $\surreal{x_l}{x_r}$ where $x_l$ is the largest element of $X_L$ and | |
86 | $x_r$ is the smallest element of $X_R$. If either $X_R$ or $X_L$ are the empty | |
87 | set, then the corresponding $x_r$ or $x_l$ also become the empty set. | |
88 | \end{defi} | |
89 | ||
90 | Note that we are guaranteed largest and smallest elements of the corresponding | |
91 | non-empty sets from Axiom \autoref{ax:leq-comparison} and our definition of | |
92 | similarity. We are only building a one-dimensional number line. | |
93 | ||
af665c3c AT |
94 | Note that the reduced form is not unique since $\surreal{-1}{1} \similar |
95 | \surreal{}{}$. | |
96 | ||
420b0302 AT |
97 | |
98 | \subsection{Conjecture} | |
99 | ||
100 | If we can build an addition operation which holds for $1 + (-1) = 0$, then we | |
101 | could start trying to assign meaningful names to some of the elements from | |
102 | generation-2. It appears that numbers of the form \surreal{n}{} behave like the | |
af665c3c AT |
103 | number $n+1$ and similarly, \surreal{}{n} behaves like $n-1$. That seems to |
104 | build the integers. | |
420b0302 AT |
105 | |
106 | If we write a program to generate a bunch of new surreal numbers and graph them | |
107 | as ``generation vs magnitude'', perhaps we can assign some meaning to numbers | |
108 | which don't fit the pattern mentioned in the previous paragraph. Maybe these | |
af665c3c AT |
109 | behave like $1/n$? It sort of feels like surreal numbers constructed via finite |
110 | repetitions of our current process will end up building something vaguely like | |
111 | the dyadic rationals. | |
112 | ||
113 | I think some of our equivalence classes are similar. I suspect that the number | |
114 | line maintains symmetry with each generation. Since we have ten equivalence | |
115 | classes, an even number, symmetry is broken if none of the equivalence classes | |
116 | are similar. In fact, since it appears that $\surreal{-1}{1} \similar | |
117 | \surreal{}{}$, I'm sure that our equivalence classes can be collapsed further. | |
118 | ||
119 | I think I can use Definition \autoref{defi:generation} to start proving some | |
120 | surreal number properties inductively. | |
121 | ||
122 | I'm having a lot of problems inserting generation-n into the numberline | |
123 | containing generation-0 to generation-(n-1). Since Axiom | |
124 | \autoref{ax:leq-comparison} requires comparing against the number itself rather | |
125 | than just comparing the sets which define the number, it's hard to slot a new | |
126 | generation's number in. For example, how do I test \surreal{}{-1} and | |
127 | \surreal{}{1} without working the existing numberline from both ends? I'm | |
128 | tempted to note that no number can contain itself, and that the two sets must | |
129 | be `less than on the left' and `greater than on the right' to allow just | |
130 | comparing sets and finding the right spot on the numberline by working from | |
131 | both directions inward, rather than just left to right. Can I make that both | |
132 | rigorous and equivalent to Axiom \autoref{ax:leq-comparison}? |