notes/chapter-1.tex

\newpage
\section{Notes: 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.