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