| 1 | \newpage |
| 2 | \section{Notes: Chapter 1} |
| 3 | |
| 4 | \subsection{Review} |
| 5 | |
| 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 |
| 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. |
| 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 |
| 21 | subset forms our \emph{universe}, also denoted $\mathbb{U}$. |
| 22 | |
| 23 | \begin{axiom} \label{ax:number-definition} |
| 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 | |
| 29 | Since this selection rule implies a binary relation, Knuth provides it. |
| 30 | |
| 31 | \begin{axiom} \label{ax:leq-relation} |
| 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 | |
| 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. |
| 43 | |
| 44 | $$-1 \equiv \surreal{}{0} \leq 0 \equiv \surreal{}{} \leq 1 \equiv \surreal{0}{}$$ |
| 45 | |
| 46 | |
| 47 | \subsection{Exploration} |
| 48 | |
| 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 | |
| 76 | \begin{defi} \label{defi:generation} |
| 77 | A \emph{generation} shall refer to the numbers created by applying Axiom |
| 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. |
| 81 | \end{defi} |
| 82 | |
| 83 | \begin{defi} \label{defi:generation-function} |
| 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$. |
| 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. |
| 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 | |
| 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 | |
| 164 | \begin{defi} \label{defi:similar} |
| 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$. |
| 168 | \end{defi} |
| 169 | |
| 170 | Applying this new definition to the twenty numbers from generations 0-2, we |
| 171 | find that they start to collapse into equivalency classes like the |
| 172 | aforementioned $\surreal{}{} \similar \surreal{-1}{1}$. More on this later. |
| 173 | |
| 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}$$ |
| 239 | $$\surreal{}{0} \similar \surreal{}{0,1}$$ |
| 240 | $$\surreal{-1}{0} \similar \surreal{-1}{0,1} \similar \surreal{-1}{}$$ |
| 241 | $$\surreal{}{} \similar \surreal{-1}{1}$$ |
| 242 | $$\surreal{0}{1} \similar \surreal{-1,0}{1}$$ |
| 243 | $$\surreal{0}{} \similar \surreal{-1,0}{} \similar \surreal{}{1}$$ |
| 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 |
| 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. |
| 251 | |
| 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} |
| 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. |
| 281 | \end{proof} |
| 282 | |
| 283 | \begin{defi} \label{defi:reduced-form} |
| 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$. |
| 286 | \end{defi} |
| 287 | |
| 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. |
| 331 | |
| 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 |
| 338 | number $n+1$ and similarly, \surreal{}{n} behaves like $n-1$. That seems to |
| 339 | build the integers. |
| 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 |
| 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 | |
| 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. |