X-Git-Url: https://git.subgeniuskitty.com/surreal-numbers/.git/blobdiff_plain/ef10cd2cd96c1f502a10212f08329d1566b9ebac..46905e173537fd1c9e8590beafd42b2dbf79612c:/notes/chapter-1.tex

diff --git a/notes/chapter-1.tex b/notes/chapter-1.tex
index 9a1e41c..78834af 100644
--- a/notes/chapter-1.tex
+++ b/notes/chapter-1.tex
@@ -3,7 +3,22 @@
 
 \subsection{Review}
 
-In the first chapter, Knuth provides two axioms.
+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
@@ -11,42 +26,123 @@ no member of the left set is greater than or equal to any member of the right
 set.
 \end{axiom}
 
-For example, if $x = \surreal{X_L}{X_R}$, then $\forall x_L \in X_L$, it must
-hold $\forall x_R \in X_R$ that $x_L \ngeq x_R$.
+Since this selection rule implies a binary relation, Knuth provides it.
 
-\begin{axiom} \label{ax:leq-comparison}
+\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}
 
-For example, the relation $\surreal{X_L}{X_R} = x \leq y = \surreal{Y_L}{Y_R}$
-holds true if and only if both $X_L \ngeq y$ and $Y_R \nleq x$.
+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}{}$$
 
-With no surreal numbers yet in our possession, we construct the first surreal
-number using the null set (or void set, as Knuth calls it) as both the left and
-right set. Although we have not yet examined its properties, Knuth names this
-number ``zero''. Thus, $\surreal{}{} = 0$.
 
-As his final trick, Knuth defines a second generation of surreal numbers using
-$0$ in the left and right set, naming them $1$ and $-1$ and claiming the
-following relation.
+\subsection{Exploration}
 
-$$-1 = \surreal{}{0} \leq 0 = \surreal{}{} \leq 1 = \surreal{0}{}$$
+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}
 
-\subsection{Exploration}
+\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 generated by applying Axiom
-\autoref{ax:number-definition} to all 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.
+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}
 
-Working by hand with Axiom \autoref{ax:number-definition}, generation-2
-contains the numbers shown below.
+\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},$$
@@ -54,44 +150,184 @@ $$\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-comparison}, $X \leq Y$ and $Y \leq X$. This is denoted by $X
-\similar Y$.
+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}
 
-From this point forward, we will refer to similar surreal numbers
-interchangeably.
+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$.
 
-Using this definition, the twenty numbers from generations 0-2 break down into
-ten equivalence classes based on similarity, as shown below.
+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.
 
-$$\surreal{0}{} \similar \surreal{-1,0}{}$$
-$$\surreal{}{}$$
+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}{}$$
-$$\surreal{1}{} \similar \surreal{0,1}{} \similar \surreal{-1,1}{} \similar \surreal{-1,0,1}{}$$
-$$\surreal{-1}{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{}{1}$$
-$$\surreal{-1}{0} \similar \surreal{-1}{0,1}$$
-$$\surreal{}{-1} \similar \surreal{}{-1,0} \similar \surreal{}{-1,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}{}$$
 
-From this we see that, since Axiom \autoref{ax:leq-comparison} makes its
-comparison element-wise, every surreal number generated by our current methods
-must be similar to a surreal number containing one or zero elements in its left
-and right sets. This motivates the following definition.
+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}
-The \emph{reduced form} for a surreal number $X = \surreal{X_L}{X_R}$ is
-defined as $\surreal{x_l}{x_r}$ where $x_l$ is the largest element of $X_L$ and
-$x_r$ is the smallest element of $X_R$. If either $X_R$ or $X_L$ are the empty
-set, then the corresponding $x_r$ or $x_l$ also become the empty set.
+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 we are guaranteed largest and smallest elements of the corresponding
-non-empty sets from Axiom \autoref{ax:leq-comparison} and our definition of
-similarity. We are only building a one-dimensional number line.
+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}
@@ -99,14 +335,23 @@ similarity. We are only building a one-dimensional number line.
 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$.
+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$?
+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}$.
 
-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.
+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.
