From 46905e173537fd1c9e8590beafd42b2dbf79612c Mon Sep 17 00:00:00 2001 From: Aaron Taylor Date: Sat, 8 May 2021 01:53:32 -0700 Subject: [PATCH] More updates to Chapter 1 notes exploring order and uniqueness. --- notes/chapter-1.tex | 157 ++++++++++++++++++++++---------------------- 1 file changed, 80 insertions(+), 77 deletions(-) diff --git a/notes/chapter-1.tex b/notes/chapter-1.tex index 1d7a06f..78834af 100644 --- a/notes/chapter-1.tex +++ b/notes/chapter-1.tex @@ -10,17 +10,15 @@ 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. +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}. +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 @@ -83,8 +81,9 @@ 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$. +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} @@ -169,7 +168,7 @@ Two numbers $x$ and $y$ are \emph{similar} iff, per Axiom \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 +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' @@ -237,20 +236,18 @@ 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{-1}{0} \similar \surreal{-1}{0,1} \similar \surreal{-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}{} \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, we introduce the following two -definitions (and theorems). - -% ================================================================================================== -% ================================================================================================== -% ================================================================================================== +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' = @@ -259,45 +256,28 @@ 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. +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} @@ -305,26 +285,49 @@ 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. +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} -- 2.20.1