Significant updates to Chapter 1 notes exploring order and uniqueness.

diff --git a/notes/chapter-1.tex b/notes/chapter-1.tex
index e340d75..1d7a06f 100644 (file)
--- a/notes/chapter-1.tex
+++ b/notes/chapter-1.tex
@@ -3,7 +3,24 @@
 
 \subsection{Review}
 
 
 \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 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
 
 \begin{axiom} \label{ax:number-definition}
 Every number corresponds to two sets of previously created numbers, such that


@@ -11,42 +28,122 @@ no member of the left set is greater than or equal to any member of the right
 set.
 \end{axiom}
 
 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}
 
 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$.
-
-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 establishing the
-following relation.
+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}
 
 
 $$-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}
 \begin{defi} \label{defi:generation}

-A \emph{generation} shall refer to the numbers generated by applying Axiom
+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}
 
 \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}
 

-Working by hand with Axiom \autoref{ax:number-definition}, generation-2
-contains the numbers shown below.
+\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}{}, \surreal{1}{}, \surreal{-1,0}{}, \surreal{0,1}{},$$
 $$\surreal{-1,1}{}, \surreal{-1,0,1}{}, \surreal{-1}{1}, \surreal{0}{1},$$


@@ -54,45 +151,180 @@ $$\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}$$
 
 $$\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}
 \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}
 
 \end{defi}
 

-Using this definition, the twenty numbers from generations 0-2 break down into
-no more than ten equivalence classes based on similarity, as shown below.
+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.

 
 

-$$\surreal{0}{} \similar \surreal{-1,0}{}$$
-$$\surreal{}{}$$
+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{}{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{}{} \similar \surreal{-1}{1}$$
+$$\surreal{0}{} \similar \surreal{-1,0}{} \similar \surreal{}{1}$$

 $$\surreal{0}{1} \similar \surreal{-1,0}{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{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).
+
+% ==================================================================================================
+% ==================================================================================================
+% ==================================================================================================

 
 

-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 since only the largest member of the left set and smallest
-member of the right set are important. This motivates the following definition.
+\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}
 
 \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}
 
 \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.
+\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}

 
 

-Note that the reduced form is not unique since $\surreal{-1}{1} \similar
-\surreal{}{}$.
+% ==================================================================================================
+% ==================================================================================================
+% ==================================================================================================
+
+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}
 
 
 \subsection{Conjecture}


@@ -110,23 +342,13 @@ 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.
 
 repetitions of our current process will end up building something vaguely like
 the dyadic rationals.
 

-I think some of our equivalence classes are similar. I suspect that the number
-line maintains symmetry with each generation. Since we have ten equivalence
-classes, an even number, symmetry is broken if none of the equivalence classes
-are similar. In fact, since it appears that $\surreal{-1}{1} \similar
-\surreal{}{}$, I'm sure that our equivalence classes can be collapsed further.
-
-I think I can use Definition \autoref{defi:generation} to start proving some
-surreal number properties inductively.
-
-I'm having a lot of problems inserting generation-n into the numberline
-containing generation-0 to generation-(n-1). Since Axiom
-\autoref{ax:leq-comparison} requires comparing against the number itself rather
-than just comparing the sets which define the number, it's hard to slot a new
-generation's number in. For example, how do I test \surreal{}{-1} and
-\surreal{}{1} without working the existing numberline from both ends? I'm
-tempted to note that no number can contain itself, and that the two sets must
-be `less than on the left' and `greater than on the right' to allow just
-comparing sets and finding the right spot on the numberline by working from
-both directions inward, rather than just left to right. Can I make that both
-rigorous and equivalent to Axiom \autoref{ax:leq-comparison}?
+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.