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 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.