Commit | Line | Data |
---|---|---|
8484c2fd AT |
1 | \newpage |
2 | \section{Notes: Chapter 1} | |
3 | ||
420b0302 | 4 | \subsection{Review} |
cc0282e4 | 5 | |
a7ed1bc8 AT |
6 | In the first chapter, Knuth provides an algorithm for generating a set of |
7 | symbols, a `little old ladies at the country club' rule for selecting a subset | |
8 | of those symbols, and a binary relation on that selected subset. | |
9 | ||
10 | \begin{axiom} \label{ax:symbol-generation} | |
11 | Every symbol is comprised of a left and right set of other symbols. The initial | |
12 | symbol is named $0$ and is comprised of the empty set for both its left and | |
46905e17 AT |
13 | right sets. All further symbols are generated by repeatedly selecting |
14 | (potentially empty) subsets of the set of all existing symbols, using these | |
15 | selections as left and right sets to define a new symbol, and then adding that | |
16 | symbol to the set of all existing symbols. | |
a7ed1bc8 AT |
17 | \end{axiom} |
18 | ||
19 | From this set of all symbols, growing with each iteration, we select the subset | |
20 | of symbols which satisfy the next axiom, calling them \emph{numbers}. This | |
46905e17 | 21 | subset forms our \emph{universe}, also denoted $\mathbb{U}$. |
420b0302 AT |
22 | |
23 | \begin{axiom} \label{ax:number-definition} | |
cc0282e4 AT |
24 | Every number corresponds to two sets of previously created numbers, such that |
25 | no member of the left set is greater than or equal to any member of the right | |
26 | set. | |
27 | \end{axiom} | |
28 | ||
a7ed1bc8 | 29 | Since this selection rule implies a binary relation, Knuth provides it. |
cc0282e4 | 30 | |
a7ed1bc8 | 31 | \begin{axiom} \label{ax:leq-relation} |
cc0282e4 AT |
32 | One number is less than or equal to another number if and only if no member of |
33 | the first number's left set is greater than or equal to the second number, and | |
34 | no member of the second number's right set is less than or equal to the first | |
35 | number. | |
36 | \end{axiom} | |
37 | ||
a7ed1bc8 AT |
38 | As his final trick, Knuth applies the algorithm of Axiom |
39 | \autoref{ax:symbol-generation} to the hand-crafted initial input ($0 \equiv | |
40 | \surreal{}{}$), retains only those symbols which are valid numbers per Axiom | |
41 | \autoref{ax:number-definition}, and applies Axiom \autoref{ax:leq-relation} to | |
42 | establish the following relation on the newly expanded universe. | |
cc0282e4 | 43 | |
af665c3c | 44 | $$-1 \equiv \surreal{}{0} \leq 0 \equiv \surreal{}{} \leq 1 \equiv \surreal{0}{}$$ |
cc0282e4 | 45 | |
420b0302 AT |
46 | |
47 | \subsection{Exploration} | |
48 | ||
a7ed1bc8 AT |
49 | I attempted to create a program which applies these axioms, generating numbers |
50 | and organizing them by relation. Along the way I realized that I was assuming | |
51 | at least a total order and maybe a well order. If those assumptions are | |
52 | incorrect, the program's data types and visualization algorithms change | |
53 | significantly. Consequently, I began poking my new universe to see what type of | |
54 | order Axiom \autoref{ax:leq-relation} actually defines. | |
55 | ||
56 | \begin{framed} | |
57 | \noindent Note that the following definitions and theorems only consider | |
58 | the case of finite left and right sets. | |
59 | \end{framed} | |
60 | ||
61 | \begin{defi} \label{defi:number-in-number} | |
62 | Given two numbers $x$ and $y = \surreal{Y_L}{Y_R}$, we say that $x$ is | |
63 | \emph{in} $y$ iff $x \in Y_L \cup Y_R$. We also write this as $x \in y$. | |
64 | \end{defi} | |
65 | ||
66 | \begin{defi} \label{defi:ancestor} | |
67 | Given two numbers $x$ and $y$, we say that $x$ is an \emph{ancestor} of $y$ iff | |
68 | there exists a relationship $x = a_1 \in ... \in a_n = y$ with finite $n$. | |
69 | \end{defi} | |
70 | ||
71 | Although I think I can make everything work while only using the notion of | |
72 | `ancestor', generating numbers in a stream with no other age-based | |
73 | distinguishing attributes, I include the following definition to match Knuth's | |
74 | notion of generating new numbers in a day-by-day or power-set like fashion. | |
75 | ||
420b0302 | 76 | \begin{defi} \label{defi:generation} |
a7ed1bc8 | 77 | A \emph{generation} shall refer to the numbers created by applying Axiom |
af665c3c AT |
78 | \autoref{ax:number-definition} to all possible combinations of extant numbers. |
79 | Generations are numbered sequentially such that generation-0 consists of the | |
80 | number $0$, generation-1 consists of the numbers $-1$ and $1$, etc. | |
420b0302 AT |
81 | \end{defi} |
82 | ||
a7ed1bc8 | 83 | \begin{defi} \label{defi:generation-function} |
46905e17 AT |
84 | For a surreal number $x$, the \emph{generation function} $g\colon \mathbb{U} |
85 | \rightarrow\mathbb{N}$ returns the generation in which $x$ was created. For | |
86 | example, $g(0) = 0$ and $g(-1) = 1$. | |
a7ed1bc8 AT |
87 | \end{defi} |
88 | ||
89 | \begin{defi} \label{defi:younger} | |
90 | Given two sets of surreal numbers $X$ and $Y$ with equal cardinality, we say | |
91 | that $X$ is \emph{younger} than $Y$ iff, $\forall x_i \in X$ and $\forall y_j | |
92 | \in Y$ it holds that $\sum g(x_i) < \sum g(y_j)$. Similarly, we say that $Y$ is | |
93 | \emph{older} than $X$. | |
94 | \end{defi} | |
95 | ||
96 | With these definitions in place, let's start pursuing an order. | |
97 | ||
98 | \begin{theorem} \label{thm:transitive} | |
99 | Axiom \autoref{ax:leq-relation} is transitive. That is, if $x \leq y$ and $y | |
100 | \leq z$, then $x \leq z$. | |
101 | \end{theorem} | |
102 | ||
103 | \begin{proof} | |
104 | Seeking a contradiction, let $x = \surreal{X_L}{X_R}$, $y = | |
105 | \surreal{Y_L}{Y_R}$, and $z = \surreal{Z_L}{Z_R}$ be the youngest set of | |
106 | numbers satisfying $x \leq y$, $y \leq z$ and $x \nleq z$. Note by inspection | |
107 | that generation-0 and generation-1 obey transitivity. | |
108 | ||
109 | By Axiom \autoref{ax:leq-relation}, this creates two possible cases. There | |
110 | could exist an $x_L \in X_L$ such that $x_L \geq z$ or there could exist a $z_R | |
111 | \in Z_R$ such that $z_R \leq x$. | |
112 | ||
113 | In either case, we end up with a set of three numbers which do not obey | |
114 | transitivity, namely \set{y, z, x_L} or \set{z_R, x, y}. But, since $x_L | |
115 | \in X_L$ and $z_R \in Z_R$, we know that $g(x_L) < g(x)$ and $g(z_R) < g(z)$. | |
116 | In other words, if we consider the sum $g(x) + g(y) + g(z)$, it must be greater | |
117 | than both the sum $g(y) + g(z) + g(x_L)$ and the sum $g(z_R) + g(x) + g(y)$. | |
118 | ||
119 | Since this means a younger set of numbers exist for which transitivity fails, | |
120 | we have reached the desired contradiction. | |
121 | \end{proof} | |
122 | ||
123 | \begin{theorem} \label{thm:reflexive} | |
124 | Axiom \autoref{ax:leq-relation} is reflexive. That is, $x \leq x$. | |
125 | \end{theorem} | |
126 | ||
127 | \begin{proof} | |
128 | Let $x$ be the youngest number satisfying $x \nleq x$. Note that $0 \leq 0$ by | |
129 | inspection. | |
130 | ||
131 | By Axiom \autoref{ax:leq-relation}, this creates two possible cases. Either | |
132 | $\exists x_L \in X_L$ such that $x \leq x_L$ or $\exists x_R \in X_R$ such that | |
133 | $x_R \leq x$. | |
134 | ||
135 | In the first case, by Axiom \autoref{ax:leq-relation}, we find that $X_L \ngeq | |
136 | x_L$, implying that $x_L \ngeq x_L$, a contradiction since $x_L \in X_L$ from | |
137 | the start. We arrive at a similar contradiction for the second case. | |
138 | \end{proof} | |
139 | ||
140 | Per \autoref{thm:transitive} and \autoref{thm:reflexive}, we find that Axiom | |
141 | \autoref{ax:leq-relation} is at least a preorder on our universe. Normally we | |
142 | would move on to proving that Axiom \autoref{ax:leq-relation} is antisymmetric, | |
143 | however, there is a problem. Working by hand with Axioms | |
144 | \autoref{ax:symbol-generation} and \autoref{ax:number-definition}, generation-2 | |
145 | contains the following numbers. | |
420b0302 AT |
146 | |
147 | $$\surreal{-1}{}, \surreal{1}{}, \surreal{-1,0}{}, \surreal{0,1}{},$$ | |
148 | $$\surreal{-1,1}{}, \surreal{-1,0,1}{}, \surreal{-1}{1}, \surreal{0}{1},$$ | |
149 | $$\surreal{-1,0}{1}, \surreal{}{1}, \surreal{-1}{0}, \surreal{}{-1},$$ | |
150 | $$\surreal{-1}{0,1}, \surreal{}{0,1}, \surreal{}{-1,0}, \surreal{}{-1,1},$$ | |
151 | $$\surreal{}{-1,0,1}$$ | |
152 | ||
a7ed1bc8 AT |
153 | By application of Axiom \autoref{ax:leq-relation}, note that $\surreal{}{} \leq |
154 | \surreal{-1}{1}$ and also $\surreal{-1}{1} \leq \surreal{}{}$, yet clearly | |
155 | $\surreal{}{} \neq \surreal{-1}{1}$. It turns out that Axiom | |
156 | \autoref{ax:leq-relation} fails to define even a partial order. | |
157 | ||
158 | For now, let's simply define antisymmetry into existence, give it a special | |
159 | name and symbol so we know where we've strayed from Knuth, and move on with | |
160 | creating our program. Worst case, it'll turn out that we're generating | |
161 | something embedded in a larger space, like the linearly-ordered $\mathbb{R}$ | |
162 | embedded in the not-linearly-ordered $\mathbb{C}$. | |
163 | ||
420b0302 | 164 | \begin{defi} \label{defi:similar} |
a7ed1bc8 AT |
165 | Two numbers $x$ and $y$ are \emph{similar} iff, per Axiom |
166 | \autoref{ax:leq-relation}, $x \leq y$ and $y \leq x$. This is denoted by $x | |
167 | \similar y$. | |
420b0302 AT |
168 | \end{defi} |
169 | ||
a7ed1bc8 | 170 | Applying this new definition to the twenty numbers from generations 0-2, we |
46905e17 | 171 | find that they start to collapse into equivalency classes like the |
a7ed1bc8 | 172 | aforementioned $\surreal{}{} \similar \surreal{-1}{1}$. More on this later. |
420b0302 | 173 | |
a7ed1bc8 AT |
174 | Returning to our investigation of order, now that we have `proven' |
175 | antisymmetry, our universe has a partial order. The only thing required to | |
176 | upgrade to a total order is proof that every number is comparable, but first a | |
177 | lemma. | |
178 | ||
179 | \begin{theorem} \label{thm:weak-self-relation} | |
180 | For $x = \surreal{X_L}{X_R}$, it holds that $X_L \leq x \leq X_R$. | |
181 | \end{theorem} | |
182 | ||
183 | \begin{proof} | |
184 | Seeking a contradiction, assume $\exists x_L \in X_L$ such that $x_L \nleq x$. | |
185 | ||
186 | By Axiom \autoref{ax:leq-relation}, this creates two possible cases. Either | |
187 | $\exists (x_L)_L \in (X_L)_L$ such that $(x_L)_L \geq x$ or $\exists x_R \in | |
188 | X_R$ such that $x_R \leq x_L$. By Axiom \autoref{ax:number-definition}, the | |
189 | latter case is impossible. | |
190 | ||
191 | We address the remaining case by inductively noting that $(x_L)_L \leq x_L$, | |
192 | thus $x \leq (x_L)_L$. However, since this means that $x \leq (x_L)_L \leq | |
193 | x_L$, by \autoref{thm:transitive}, $x \leq x_L$. By definition, this means $X_L | |
194 | \nleq x_L$, a contradiction since $x_L \in X_L$. | |
195 | ||
196 | The proof of $x \leq X_R$ follows similarly. | |
197 | \end{proof} | |
198 | ||
199 | \begin{theorem} \label{thm:all-comparable} | |
200 | For every $x$ and $y$ in the universe, if $y \nleq x$, then $x \leq y$. | |
201 | \end{theorem} | |
202 | ||
203 | \begin{proof} | |
204 | Seeking a contradiction, let $x$ and $y$ be numbers such that $y \nleq x$ and | |
205 | $x \nleq y$. | |
206 | ||
207 | By Axiom \autoref{ax:leq-relation}, this creates two possible cases. Either | |
208 | $\exists x_L \in X_L$ such that $x_L \geq y$ or $\exists y_R \in Y_R$ such that | |
209 | $x \geq y_R$. In the first case, by \autoref{thm:weak-self-relation}, $x_L \leq | |
210 | x$, so by \autoref{thm:transitive}, $y \leq x$, a contradiction. A similar | |
211 | contradiction is reached in the other case. | |
212 | \end{proof} | |
213 | ||
214 | Well, that's it. We have a total order, but we're no longer in the same | |
215 | universe as Knuth. We can even go one step further and note that, by only | |
216 | considering a finite number of generations, we are guaranteed to only generate | |
217 | a finite quantity of numbers, and a finite totally ordered set is automatically | |
218 | well ordered. | |
219 | ||
220 | With a total order in hand, we can strengthen $x \nleq y$ into $x > y$, | |
221 | motivating the following theorem. | |
222 | ||
223 | \begin{theorem} \label{thm:strong-self-relation} | |
224 | For any number $x = \surreal{X_L}{X_R}$, it holds that $X_L < x < X_R$. | |
225 | \end{theorem} | |
226 | ||
227 | \begin{proof} | |
228 | Simply recognize why `linear order' is a synonym for `total order'. | |
229 | \end{proof} | |
230 | ||
231 | Moving away from considering order, note that creating Definition | |
232 | \autoref{defi:similar} imposed order on our universe at the cost of some | |
233 | uniqueness. Let's examine that loss of uniqueness a bit further. | |
234 | ||
235 | The twenty numbers from generations 0-2 break down into seven similarity-based | |
236 | equivalence classes, as shown below. | |
237 | ||
238 | $$\surreal{}{-1} \similar \surreal{}{-1,0} \similar \surreal{}{-1,1} \similar \surreal{}{-1,0,1}$$ | |
ef10cd2c | 239 | $$\surreal{}{0} \similar \surreal{}{0,1}$$ |
46905e17 | 240 | $$\surreal{-1}{0} \similar \surreal{-1}{0,1} \similar \surreal{-1}{}$$ |
a7ed1bc8 | 241 | $$\surreal{}{} \similar \surreal{-1}{1}$$ |
ef10cd2c | 242 | $$\surreal{0}{1} \similar \surreal{-1,0}{1}$$ |
46905e17 | 243 | $$\surreal{0}{} \similar \surreal{-1,0}{} \similar \surreal{}{1}$$ |
a7ed1bc8 AT |
244 | $$\surreal{1}{} \similar \surreal{0,1}{} \similar \surreal{-1,1}{} \similar \surreal{-1,0,1}{}$$ |
245 | ||
246 | Thus, whereas Knuth's universe has 20 numbers by generation-2, our universe | |
46905e17 AT |
247 | only has seven numbers. For convenience when writing our program which creates |
248 | a (finite set based) surreal numberline, we desire a unique representation for | |
249 | each equivalence class. Toward that end, we introduce the following | |
250 | definition and theorem. | |
420b0302 | 251 | |
a7ed1bc8 AT |
252 | \begin{theorem} \label{thm:reduced-form} |
253 | Given an arbitrary number $x$, there exists a number $x' = | |
254 | \surreal{X'_L}{X'_R}$ which is similar to $x$ and has the property that the | |
255 | cardinality of both $X'_L$ and $X'_R$ are one or zero. | |
256 | \end{theorem} | |
257 | ||
258 | \begin{proof} | |
46905e17 AT |
259 | Let $x = \surreal{X_L}{X_R}$. Since a finite, total ordered set contains a |
260 | maximum and minimum element, it follows that we can define $X'_L$ as containing | |
261 | only the maximum element of $X_L$ and define $X'_R$ as containing only the | |
262 | minimum element of $X_R$. If either $X_L$ or $X_R$ are the empty set, the | |
263 | corresponding $X'_L$ or $X'_R$ are also the empty set. | |
264 | ||
265 | Use these two newly defined sets to construct $x' = \surreal{X'_L}{X'_R}$. This | |
266 | clearly satisfies Axiom \autoref{ax:number-definition} by inheritance. Then, | |
267 | to show that $x \similar x'$, we apply Axiom \autoref{ax:leq-relation} in both | |
268 | directions. | |
269 | ||
270 | In the forward direction, $x \leq x'$ requires that, $\forall x_L \in X_L$, it | |
271 | must hold that $x_L \ngeq x'$. Indeed, from \autoref{thm:strong-self-relation}, | |
272 | \autoref{thm:transitive}, and our explicit construction of $X'_L$ as the | |
273 | maximum element of $X_L$, the desired relation holds since $X_L \leq X'_L < | |
274 | x'$. | |
275 | ||
276 | Also in the forward direction, $x \leq x'$ requires that, $\forall x'_R \in | |
277 | X'_R$, it holds that $x'_R \nleq x$. By the same theorems/construction as | |
278 | before, the desired relation holds since $x < X_R \leq X'_R$. | |
279 | ||
280 | The reverse direction follows via a similar pair of arguments. | |
a7ed1bc8 | 281 | \end{proof} |
420b0302 AT |
282 | |
283 | \begin{defi} \label{defi:reduced-form} | |
a7ed1bc8 AT |
284 | Given an arbitrary number $x$, the $x'$ guaranteed to exist by |
285 | \autoref{thm:reduced-form} is termed the \emph{reduced form} of $x$. | |
420b0302 AT |
286 | \end{defi} |
287 | ||
46905e17 AT |
288 | Note that reduced forms are not unique since $\surreal{}{} \similar |
289 | \surreal{-1}{1}$ but $\surreal{}{} \neq \surreal{-1}{1}$. | |
290 | ||
291 | Note also that uniqueness is not trivially achieved by applying the generation | |
292 | function to an equivalence class. Although all elements are comparable, the set | |
293 | is finite, and the natural relation inherits the reflexive and transitive | |
294 | properties from $\mathbb{N}$, the relation is not antisymmetric since | |
295 | $\surreal{-1}{0} \neq \surreal{-1}{}$ and yet both are from generation-2. Thus, | |
296 | stealing well ordering from $\mathbb{N}$ and using it to define a unique | |
297 | element to represent the equivalence class turns out to be harder than I had | |
298 | hoped. | |
299 | ||
300 | I suspect the first time a reduced form number from a given equivalence class | |
301 | is generated, it will be alone. I base that on viewing the growing set as being | |
302 | comprised of two types of numbers, first a primary set forming a sparse line | |
303 | bookended by the empty set, making the set longer with every generation. | |
304 | ||
305 | $$\set{}$$ | |
306 | $$\set{} < 0 < \set{}$$ | |
307 | $$\set{} < -1 < 0 < 1 < \set{}$$ | |
308 | ||
309 | Within this set a secondary set is forming, sitting directly in the middle | |
310 | between every existing number, making the set denser with every generation. | |
311 | Although harder to whip up in \LaTeX, I visualize this like a house of cards | |
312 | viewed end-on, a honeycomb lattice linking two parents to each child, adding a | |
313 | full spatial dimension to the honeycomb with each generation. | |
314 | ||
315 | If this visualization is true, then uniqueness of the reduced form representing | |
316 | an equivalence class in the first generation said class is encountered, follows | |
317 | naturally, even though this result doesn't hold for any following generations. | |
318 | ||
319 | Regardless, for the purpose of writing a program that generates numbers and | |
320 | orders them, the truth of this conjecture is irrelevant. We can simply identify | |
321 | the first number encountered in an equivalence class as the canonical | |
322 | representation of that class. The naturally serial nature of the program will | |
323 | serialize creation of numbers, adding a finer grained age relation and making | |
324 | it trivial to choose a `first' element to represent each class. | |
325 | ||
326 | All this started because I wanted a program to generate some numbers and | |
327 | investigate the relation. We finally have the requisite tools to return to that | |
328 | task, namely the strong self relation in \autoref{thm:strong-self-relation} | |
329 | which solves our comparison problem and the uniqueness of reduced forms in the | |
330 | subset of numbers(/equivalence classes) our program will actually generate. | |
af665c3c | 331 | |
420b0302 AT |
332 | |
333 | \subsection{Conjecture} | |
334 | ||
335 | If we can build an addition operation which holds for $1 + (-1) = 0$, then we | |
336 | could start trying to assign meaningful names to some of the elements from | |
337 | generation-2. It appears that numbers of the form \surreal{n}{} behave like the | |
af665c3c AT |
338 | number $n+1$ and similarly, \surreal{}{n} behaves like $n-1$. That seems to |
339 | build the integers. | |
420b0302 AT |
340 | |
341 | If we write a program to generate a bunch of new surreal numbers and graph them | |
342 | as ``generation vs magnitude'', perhaps we can assign some meaning to numbers | |
343 | which don't fit the pattern mentioned in the previous paragraph. Maybe these | |
af665c3c AT |
344 | behave like $1/n$? It sort of feels like surreal numbers constructed via finite |
345 | repetitions of our current process will end up building something vaguely like | |
346 | the dyadic rationals. | |
347 | ||
a7ed1bc8 AT |
348 | Are numbers just the average of their left and right sets (in reduced form)? |
349 | For example, $\surreal{-1}{1} \similar \surreal{}{}$. If so, then generation-2 | |
350 | includes numbers like $\pm \frac{1}{2}$. | |
351 | ||
352 | If my suspicions about symmetry are correct, anytime the number of equivalence | |
353 | classes is even, there are at least two equivalence classes that are similar. | |
354 | ||
355 | Since the universe is growing in both direction, I don't think we can impose a | |
356 | useful well ordering on the whole set unless considering a finite number of | |
357 | generations. |