+\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 the 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}.
+
+\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(x)$ 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{-1}{0} \similar \surreal{-1}{0,1} \similar \surreal{-1}{}$$
+$$\surreal{}{0} \similar \surreal{}{0,1}$$
+$$\surreal{}{} \similar \surreal{-1}{1}$$
+$$\surreal{0}{} \similar \surreal{-1,0}{} \similar \surreal{}{1}$$
+$$\surreal{0}{1} \similar \surreal{-1,0}{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, we introduce the following two
+definitions (and theorems).
+
+% ==================================================================================================
+% ==================================================================================================
+% ==================================================================================================
+
+\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}
+TODO
+% 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$ is
+% also the empty set.
+%
+% Then, to show that $x \similar x'$, we apply Axiom \autoref{ax:leq-relation} in
+% both directions.
+%
+% In the forward direction, $x \leq x'$ means that, $\forall x_L \in X_L$, it
+% must hold that $x_L \leq x'$. Applying \autoref{thm:strong-self-relation}, we
+% conclude that $x_L \leq x'_L < x'$. (this isn't quite right. reconsider my
+% approach)
+%
+% ...
+%
+% By Axiom \autoref{ax:leq-relation} and \autoref{thm:weak-self-relation}, for
+% $x'_l \in X'_L$,
+%
+% ==================
+%
+% The current ten equivalence classes were created by noting that every number
+% with a left or right set containing more than one element is similar to another
+% number whose sets do NOT contain more than one element. Since similarity is
+% built atop the LEQ relation from Axiom \autoref{ax:leq-relation} which itself
+% is based upon element-wise comparisons, we see that the only elements of
+% importance to these relations are the largest element of the left set and the
+% smallest element of the right set. Of course, for such a statement to be
+% sensical, we must first prove that Axiom \autoref{ax:leq-relation} imposes a
+% total ordering, otherwise there might not be a largest or smallest element in a
+% set.
+%
+% From this we see that, since Axiom \autoref{ax:leq-relation} makes its
+% comparison element-wise, every surreal number generated by our current, finite
+% methods must be similar to a surreal number containing one or zero elements in
+% its left and right sets since only the largest member of the left set and
+% smallest member of the right set are important. This motivates the following
+% definition.
+\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}
+
+\begin{theorem} \label{thm:named-form}
+TODO: Without defining a named form, prove that it is unique.
+\end{theorem}
+
+\begin{proof}
+TODO
+\end{proof}
+
+\begin{defi} \label{defi:named-form}
+TODO: Define a named form as the oldest reduced form of an equivalence class determined by similarity.
+\end{defi}
+
+% ==================================================================================================
+% ==================================================================================================
+% ==================================================================================================
+
+Between \autoref{thm:strong-self-relation} and Definition
+\autoref{defi:named-form} which follows from \autoref{thm:named-form}, we
+finally possesss the tools necessary to finish our Go program and use it to
+generate and examine a surreal number line.
+
+
+\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.
projects / surreal-numbers / blobdiff