X-Git-Url: http://git.subgeniuskitty.com/surreal-numbers/.git/blobdiff_plain/8484c2fd2ad8d6a4bcc64f16142185ad71ffbd5f..46905e173537fd1c9e8590beafd42b2dbf79612c:/notes/chapter-1.tex

diff --git a/notes/chapter-1.tex b/notes/chapter-1.tex
index 265fd80..78834af 100644
--- a/notes/chapter-1.tex
+++ b/notes/chapter-1.tex
@@ -1,4 +1,357 @@
 \newpage
 \section{Notes: Chapter 1}
 
-Hello from chapter 1.
+\subsection{Review}
+
+In the first chapter, Knuth provides an algorithm for generating a set of
+symbols, a `little old ladies at the country club' rule for selecting a subset
+of those symbols, and a binary relation on that selected subset.
+
+\begin{axiom} \label{ax:symbol-generation}
+Every symbol is comprised of a left and right set of other symbols. The initial
+symbol is named $0$ and is comprised of the empty set for both its left and
+right sets. All further symbols are generated by repeatedly selecting
+(potentially empty) subsets of the set of all existing symbols, using these
+selections as left and right sets to define a new symbol, and then adding that
+symbol to the set of all existing symbols.
+\end{axiom}
+
+From this set of all symbols, growing with each iteration, we select the subset
+of symbols which satisfy the next axiom, calling them \emph{numbers}. This
+subset forms our \emph{universe}, also denoted $\mathbb{U}$.
+
+\begin{axiom} \label{ax:number-definition}
+Every number corresponds to two sets of previously created numbers, such that
+no member of the left set is greater than or equal to any member of the right
+set.
+\end{axiom}
+
+Since this selection rule implies a binary relation, Knuth provides it.
+
+\begin{axiom} \label{ax:leq-relation}
+One number is less than or equal to another number if and only if no member of
+the first number's left set is greater than or equal to the second number, and
+no member of the second number's right set is less than or equal to the first
+number.
+\end{axiom}
+
+As his final trick, Knuth applies the algorithm of Axiom
+\autoref{ax:symbol-generation} to the hand-crafted initial input ($0 \equiv
+\surreal{}{}$), retains only those symbols which are valid numbers per Axiom
+\autoref{ax:number-definition}, and applies Axiom \autoref{ax:leq-relation} to
+establish the following relation on the newly expanded universe.
+
+$$-1 \equiv \surreal{}{0} \leq 0 \equiv \surreal{}{} \leq 1 \equiv \surreal{0}{}$$
+
+
+\subsection{Exploration}
+
+I attempted to create a program which applies these axioms, generating numbers
+and organizing them by relation. Along the way I realized that I was assuming
+at least a total order and maybe a well order. If those assumptions are
+incorrect, the program's data types and visualization algorithms change
+significantly. Consequently, I began poking my new universe to see what type of
+order Axiom \autoref{ax:leq-relation} actually defines.
+
+\begin{framed}
+    \noindent Note that the following definitions and theorems only consider
+    the case of finite left and right sets.
+\end{framed}
+
+\begin{defi} \label{defi:number-in-number}
+Given two numbers $x$ and $y = \surreal{Y_L}{Y_R}$, we say that $x$ is
+\emph{in} $y$ iff $x \in Y_L \cup Y_R$. We also write this as $x \in y$.
+\end{defi}
+
+\begin{defi} \label{defi:ancestor}
+Given two numbers $x$ and $y$, we say that $x$ is an \emph{ancestor} of $y$ iff
+there exists a relationship $x = a_1 \in ... \in a_n = y$ with finite $n$.
+\end{defi}
+
+Although I think I can make everything work while only using the notion of
+`ancestor', generating numbers in a stream with no other age-based
+distinguishing attributes, I include the following definition to match Knuth's
+notion of generating new numbers in a day-by-day or power-set like fashion.
+
+\begin{defi} \label{defi:generation}
+A \emph{generation} shall refer to the numbers created by applying Axiom
+\autoref{ax:number-definition} to all possible combinations of extant numbers.
+Generations are numbered sequentially such that generation-0 consists of the
+number $0$, generation-1 consists of the numbers $-1$ and $1$, etc.
+\end{defi}
+
+\begin{defi} \label{defi:generation-function}
+For a surreal number $x$, the \emph{generation function} $g\colon \mathbb{U}
+\rightarrow\mathbb{N}$ returns the generation in which $x$ was created. For
+example, $g(0) = 0$ and $g(-1) = 1$.
+\end{defi}
+
+\begin{defi} \label{defi:younger}
+Given two sets of surreal numbers $X$ and $Y$ with equal cardinality, we say
+that $X$ is \emph{younger} than $Y$ iff, $\forall x_i \in X$ and $\forall y_j
+\in Y$ it holds that $\sum g(x_i) < \sum g(y_j)$. Similarly, we say that $Y$ is
+\emph{older} than $X$.
+\end{defi}
+
+With these definitions in place, let's start pursuing an order.
+
+\begin{theorem} \label{thm:transitive}
+Axiom \autoref{ax:leq-relation} is transitive. That is, if $x \leq y$ and $y
+\leq z$, then $x \leq z$.
+\end{theorem}
+
+\begin{proof}
+Seeking a contradiction, let $x = \surreal{X_L}{X_R}$, $y =
+\surreal{Y_L}{Y_R}$, and $z = \surreal{Z_L}{Z_R}$ be the youngest set of
+numbers satisfying $x \leq y$, $y \leq z$ and $x \nleq z$. Note by inspection
+that generation-0 and generation-1 obey transitivity.
+
+By Axiom \autoref{ax:leq-relation}, this creates two possible cases. There
+could exist an $x_L \in X_L$ such that $x_L \geq z$ or there could exist a $z_R
+\in Z_R$ such that $z_R \leq x$.
+
+In either case, we end up with a set of three numbers which do not obey
+transitivity, namely \set{y, z, x_L} or \set{z_R, x, y}. But, since $x_L
+\in X_L$ and $z_R \in Z_R$, we know that $g(x_L) < g(x)$ and $g(z_R) < g(z)$.
+In other words, if we consider the sum $g(x) + g(y) + g(z)$, it must be greater
+than both the sum $g(y) + g(z) + g(x_L)$ and the sum $g(z_R) + g(x) + g(y)$.
+
+Since this means a younger set of numbers exist for which transitivity fails,
+we have reached the desired contradiction.
+\end{proof}
+
+\begin{theorem} \label{thm:reflexive}
+Axiom \autoref{ax:leq-relation} is reflexive. That is, $x \leq x$.
+\end{theorem}
+
+\begin{proof}
+Let $x$ be the youngest number satisfying $x \nleq x$. Note that $0 \leq 0$ by
+inspection.
+
+By Axiom \autoref{ax:leq-relation}, this creates two possible cases. Either
+$\exists x_L \in X_L$ such that $x \leq x_L$ or $\exists x_R \in X_R$ such that
+$x_R \leq x$.
+
+In the first case, by Axiom \autoref{ax:leq-relation}, we find that $X_L \ngeq
+x_L$, implying that $x_L \ngeq x_L$, a contradiction since $x_L \in X_L$ from
+the start. We arrive at a similar contradiction for the second case.
+\end{proof}
+
+Per \autoref{thm:transitive} and \autoref{thm:reflexive}, we find that Axiom
+\autoref{ax:leq-relation} is at least a preorder on our universe. Normally we
+would move on to proving that Axiom \autoref{ax:leq-relation} is antisymmetric,
+however, there is a problem. Working by hand with Axioms
+\autoref{ax:symbol-generation} and \autoref{ax:number-definition}, generation-2
+contains the following numbers.
+
+$$\surreal{-1}{}, \surreal{1}{}, \surreal{-1,0}{}, \surreal{0,1}{},$$
+$$\surreal{-1,1}{}, \surreal{-1,0,1}{}, \surreal{-1}{1}, \surreal{0}{1},$$
+$$\surreal{-1,0}{1}, \surreal{}{1}, \surreal{-1}{0}, \surreal{}{-1},$$
+$$\surreal{-1}{0,1}, \surreal{}{0,1}, \surreal{}{-1,0}, \surreal{}{-1,1},$$
+$$\surreal{}{-1,0,1}$$
+
+By application of Axiom \autoref{ax:leq-relation}, note that $\surreal{}{} \leq
+\surreal{-1}{1}$ and also $\surreal{-1}{1} \leq \surreal{}{}$, yet clearly
+$\surreal{}{} \neq \surreal{-1}{1}$. It turns out that Axiom
+\autoref{ax:leq-relation} fails to define even a partial order.
+
+For now, let's simply define antisymmetry into existence, give it a special
+name and symbol so we know where we've strayed from Knuth, and move on with
+creating our program. Worst case, it'll turn out that we're generating
+something embedded in a larger space, like the linearly-ordered $\mathbb{R}$
+embedded in the not-linearly-ordered $\mathbb{C}$.
+
+\begin{defi} \label{defi:similar}
+Two numbers $x$ and $y$ are \emph{similar} iff, per Axiom
+\autoref{ax:leq-relation}, $x \leq y$ and $y \leq x$. This is denoted by $x
+\similar y$.
+\end{defi}
+
+Applying this new definition to the twenty numbers from generations 0-2, we
+find that they start to collapse into equivalency classes like the
+aforementioned $\surreal{}{} \similar \surreal{-1}{1}$. More on this later.
+
+Returning to our investigation of order, now that we have `proven'
+antisymmetry, our universe has a partial order. The only thing required to
+upgrade to a total order is proof that every number is comparable, but first a
+lemma.
+
+\begin{theorem} \label{thm:weak-self-relation}
+For $x = \surreal{X_L}{X_R}$, it holds that $X_L \leq x \leq X_R$.
+\end{theorem}
+
+\begin{proof}
+Seeking a contradiction, assume $\exists x_L \in X_L$ such that $x_L \nleq x$.
+
+By Axiom \autoref{ax:leq-relation}, this creates two possible cases. Either
+$\exists (x_L)_L \in (X_L)_L$ such that $(x_L)_L \geq x$ or $\exists x_R \in
+X_R$ such that $x_R \leq x_L$. By Axiom \autoref{ax:number-definition}, the
+latter case is impossible.
+
+We address the remaining case by inductively noting that $(x_L)_L \leq x_L$,
+thus $x \leq (x_L)_L$. However, since this means that $x \leq (x_L)_L \leq
+x_L$, by \autoref{thm:transitive}, $x \leq x_L$. By definition, this means $X_L
+\nleq x_L$, a contradiction since $x_L \in X_L$.
+
+The proof of $x \leq X_R$ follows similarly.
+\end{proof}
+
+\begin{theorem} \label{thm:all-comparable}
+For every $x$ and $y$ in the universe, if $y \nleq x$, then $x \leq y$.
+\end{theorem}
+
+\begin{proof}
+Seeking a contradiction, let $x$ and $y$ be numbers such that $y \nleq x$ and
+$x \nleq y$.
+
+By Axiom \autoref{ax:leq-relation}, this creates two possible cases. Either
+$\exists x_L \in X_L$ such that $x_L \geq y$ or $\exists y_R \in Y_R$ such that
+$x \geq y_R$. In the first case, by \autoref{thm:weak-self-relation}, $x_L \leq
+x$, so by \autoref{thm:transitive}, $y \leq x$, a contradiction. A similar
+contradiction is reached in the other case.
+\end{proof}
+
+Well, that's it. We have a total order, but we're no longer in the same
+universe as Knuth. We can even go one step further and note that, by only
+considering a finite number of generations, we are guaranteed to only generate
+a finite quantity of numbers, and a finite totally ordered set is automatically
+well ordered.
+
+With a total order in hand, we can strengthen $x \nleq y$ into $x > y$,
+motivating the following theorem.
+
+\begin{theorem} \label{thm:strong-self-relation}
+For any number $x = \surreal{X_L}{X_R}$, it holds that $X_L < x < X_R$.
+\end{theorem}
+
+\begin{proof}
+Simply recognize why `linear order' is a synonym for `total order'.
+\end{proof}
+
+Moving away from considering order, note that creating Definition
+\autoref{defi:similar} imposed order on our universe at the cost of some
+uniqueness. Let's examine that loss of uniqueness a bit further.
+
+The twenty numbers from generations 0-2 break down into seven similarity-based
+equivalence classes, as shown below.
+
+$$\surreal{}{-1} \similar \surreal{}{-1,0} \similar \surreal{}{-1,1} \similar \surreal{}{-1,0,1}$$
+$$\surreal{}{0} \similar \surreal{}{0,1}$$
+$$\surreal{-1}{0} \similar \surreal{-1}{0,1} \similar \surreal{-1}{}$$
+$$\surreal{}{} \similar \surreal{-1}{1}$$
+$$\surreal{0}{1} \similar \surreal{-1,0}{1}$$
+$$\surreal{0}{} \similar \surreal{-1,0}{} \similar \surreal{}{1}$$
+$$\surreal{1}{} \similar \surreal{0,1}{} \similar \surreal{-1,1}{} \similar \surreal{-1,0,1}{}$$
+
+Thus, whereas Knuth's universe has 20 numbers by generation-2, our universe
+only has seven numbers. For convenience when writing our program which creates
+a (finite set based) surreal numberline, we desire a unique representation for
+each equivalence class. Toward that end, we introduce the following 
+definition and theorem.
+
+\begin{theorem} \label{thm:reduced-form}
+Given an arbitrary number $x$, there exists a number $x' =
+\surreal{X'_L}{X'_R}$ which is similar to $x$ and has the property that the
+cardinality of both $X'_L$ and $X'_R$ are one or zero.
+\end{theorem}
+
+\begin{proof}
+Let $x = \surreal{X_L}{X_R}$. Since a finite, total ordered set contains a
+maximum and minimum element, it follows that we can define $X'_L$ as containing
+only the maximum element of $X_L$ and define $X'_R$ as containing only the
+minimum element of $X_R$. If either $X_L$ or $X_R$ are the empty set, the
+corresponding $X'_L$ or $X'_R$ are also the empty set.
+
+Use these two newly defined sets to construct $x' = \surreal{X'_L}{X'_R}$. This
+clearly satisfies Axiom \autoref{ax:number-definition} by inheritance.  Then,
+to show that $x \similar x'$, we apply Axiom \autoref{ax:leq-relation} in both
+directions.
+
+In the forward direction, $x \leq x'$ requires that, $\forall x_L \in X_L$, it
+must hold that $x_L \ngeq x'$. Indeed, from \autoref{thm:strong-self-relation},
+\autoref{thm:transitive}, and our explicit construction of $X'_L$ as the
+maximum element of $X_L$, the desired relation holds since $X_L \leq X'_L <
+x'$.
+
+Also in the forward direction, $x \leq x'$ requires that, $\forall x'_R \in
+X'_R$, it holds that $x'_R \nleq x$. By the same theorems/construction as
+before, the desired relation holds since $x < X_R \leq X'_R$.
+
+The reverse direction follows via a similar pair of arguments.
+\end{proof}
+
+\begin{defi} \label{defi:reduced-form}
+Given an arbitrary number $x$, the $x'$ guaranteed to exist by
+\autoref{thm:reduced-form} is termed the \emph{reduced form} of $x$.
+\end{defi}
+
+Note that reduced forms are not unique since $\surreal{}{} \similar
+\surreal{-1}{1}$ but $\surreal{}{} \neq \surreal{-1}{1}$.
+
+Note also that uniqueness is not trivially achieved by applying the generation
+function to an equivalence class. Although all elements are comparable, the set
+is finite, and the natural relation inherits the reflexive and transitive
+properties from $\mathbb{N}$, the relation is not antisymmetric since
+$\surreal{-1}{0} \neq \surreal{-1}{}$ and yet both are from generation-2. Thus,
+stealing well ordering from $\mathbb{N}$ and using it to define a unique
+element to represent the equivalence class turns out to be harder than I had
+hoped.
+
+I suspect the first time a reduced form number from a given equivalence class
+is generated, it will be alone. I base that on viewing the growing set as being
+comprised of two types of numbers, first a primary set forming a sparse line
+bookended by the empty set, making the set longer with every generation.
+
+$$\set{}$$
+$$\set{} < 0 < \set{}$$
+$$\set{} < -1 < 0 < 1 < \set{}$$
+
+Within this set a secondary set is forming, sitting directly in the middle
+between every existing number, making the set denser with every generation.
+Although harder to whip up in \LaTeX, I visualize this like a house of cards
+viewed end-on, a honeycomb lattice linking two parents to each child, adding a
+full spatial dimension to the honeycomb with each generation.
+
+If this visualization is true, then uniqueness of the reduced form representing
+an equivalence class in the first generation said class is encountered, follows
+naturally, even though this result doesn't hold for any following generations.
+
+Regardless, for the purpose of writing a program that generates numbers and
+orders them, the truth of this conjecture is irrelevant. We can simply identify
+the first number encountered in an equivalence class as the canonical
+representation of that class. The naturally serial nature of the program will
+serialize creation of numbers, adding a finer grained age relation and making
+it trivial to choose a `first' element to represent each class.
+
+All this started because I wanted a program to generate some numbers and
+investigate the relation. We finally have the requisite tools to return to that
+task, namely the strong self relation in \autoref{thm:strong-self-relation}
+which solves our comparison problem and the uniqueness of reduced forms in the
+subset of numbers(/equivalence classes) our program will actually generate.
+
+
+\subsection{Conjecture}
+
+If we can build an addition operation which holds for $1 + (-1) = 0$, then we
+could start trying to assign meaningful names to some of the elements from
+generation-2. It appears that numbers of the form \surreal{n}{} behave like the
+number $n+1$ and similarly, \surreal{}{n} behaves like $n-1$. That seems to
+build the integers.
+
+If we write a program to generate a bunch of new surreal numbers and graph them
+as ``generation vs magnitude'', perhaps we can assign some meaning to numbers
+which don't fit the pattern mentioned in the previous paragraph. Maybe these
+behave like $1/n$? It sort of feels like surreal numbers constructed via finite
+repetitions of our current process will end up building something vaguely like
+the dyadic rationals.
+
+Are numbers just the average of their left and right sets (in reduced form)?
+For example, $\surreal{-1}{1} \similar \surreal{}{}$. If so, then generation-2
+includes numbers like $\pm \frac{1}{2}$.
+
+If my suspicions about symmetry are correct, anytime the number of equivalence
+classes is even, there are at least two equivalence classes that are similar.
+
+Since the universe is growing in both direction, I don't think we can impose a
+useful well ordering on the whole set unless considering a finite number of
+generations.