Commit | Line | Data |
---|---|---|
8484c2fd AT |
1 | \newpage |
2 | \section{Notes: Chapter 1} | |
3 | ||
420b0302 | 4 | \subsection{Review} |
cc0282e4 | 5 | |
a7ed1bc8 AT |
6 | In the first chapter, Knuth provides an algorithm for generating a set of |
7 | symbols, a `little old ladies at the country club' rule for selecting a subset | |
8 | of those symbols, and a binary relation on that selected subset. | |
9 | ||
10 | \begin{axiom} \label{ax:symbol-generation} | |
11 | Every symbol is comprised of a left and right set of other symbols. The initial | |
12 | symbol is named $0$ and is comprised of the empty set for both its left and | |
13 | right sets. | |
14 | ||
15 | All further symbols are generated by repeatedly selecting (potentially empty) | |
16 | subsets of the set of all existing symbols, using these selections as left and | |
17 | right sets to define a new symbol, and then adding that symbol the the set of | |
18 | all existing symbols. | |
19 | \end{axiom} | |
20 | ||
21 | From this set of all symbols, growing with each iteration, we select the subset | |
22 | of symbols which satisfy the next axiom, calling them \emph{numbers}. This | |
23 | subset forms our \emph{universe}. | |
420b0302 AT |
24 | |
25 | \begin{axiom} \label{ax:number-definition} | |
cc0282e4 AT |
26 | Every number corresponds to two sets of previously created numbers, such that |
27 | no member of the left set is greater than or equal to any member of the right | |
28 | set. | |
29 | \end{axiom} | |
30 | ||
a7ed1bc8 | 31 | Since this selection rule implies a binary relation, Knuth provides it. |
cc0282e4 | 32 | |
a7ed1bc8 | 33 | \begin{axiom} \label{ax:leq-relation} |
cc0282e4 AT |
34 | One number is less than or equal to another number if and only if no member of |
35 | the first number's left set is greater than or equal to the second number, and | |
36 | no member of the second number's right set is less than or equal to the first | |
37 | number. | |
38 | \end{axiom} | |
39 | ||
a7ed1bc8 AT |
40 | As his final trick, Knuth applies the algorithm of Axiom |
41 | \autoref{ax:symbol-generation} to the hand-crafted initial input ($0 \equiv | |
42 | \surreal{}{}$), retains only those symbols which are valid numbers per Axiom | |
43 | \autoref{ax:number-definition}, and applies Axiom \autoref{ax:leq-relation} to | |
44 | establish the following relation on the newly expanded universe. | |
cc0282e4 | 45 | |
af665c3c | 46 | $$-1 \equiv \surreal{}{0} \leq 0 \equiv \surreal{}{} \leq 1 \equiv \surreal{0}{}$$ |
cc0282e4 | 47 | |
420b0302 AT |
48 | |
49 | \subsection{Exploration} | |
50 | ||
a7ed1bc8 AT |
51 | I attempted to create a program which applies these axioms, generating numbers |
52 | and organizing them by relation. Along the way I realized that I was assuming | |
53 | at least a total order and maybe a well order. If those assumptions are | |
54 | incorrect, the program's data types and visualization algorithms change | |
55 | significantly. Consequently, I began poking my new universe to see what type of | |
56 | order Axiom \autoref{ax:leq-relation} actually defines. | |
57 | ||
58 | \begin{framed} | |
59 | \noindent Note that the following definitions and theorems only consider | |
60 | the case of finite left and right sets. | |
61 | \end{framed} | |
62 | ||
63 | \begin{defi} \label{defi:number-in-number} | |
64 | Given two numbers $x$ and $y = \surreal{Y_L}{Y_R}$, we say that $x$ is | |
65 | \emph{in} $y$ iff $x \in Y_L \cup Y_R$. We also write this as $x \in y$. | |
66 | \end{defi} | |
67 | ||
68 | \begin{defi} \label{defi:ancestor} | |
69 | Given two numbers $x$ and $y$, we say that $x$ is an \emph{ancestor} of $y$ iff | |
70 | there exists a relationship $x = a_1 \in ... \in a_n = y$ with finite $n$. | |
71 | \end{defi} | |
72 | ||
73 | Although I think I can make everything work while only using the notion of | |
74 | `ancestor', generating numbers in a stream with no other age-based | |
75 | distinguishing attributes, I include the following definition to match Knuth's | |
76 | notion of generating new numbers in a day-by-day or power-set like fashion. | |
77 | ||
420b0302 | 78 | \begin{defi} \label{defi:generation} |
a7ed1bc8 | 79 | A \emph{generation} shall refer to the numbers created by applying Axiom |
af665c3c AT |
80 | \autoref{ax:number-definition} to all possible combinations of extant numbers. |
81 | Generations are numbered sequentially such that generation-0 consists of the | |
82 | number $0$, generation-1 consists of the numbers $-1$ and $1$, etc. | |
420b0302 AT |
83 | \end{defi} |
84 | ||
a7ed1bc8 AT |
85 | \begin{defi} \label{defi:generation-function} |
86 | For a surreal number $x$, the \emph{generation function} $g(x)$ returns the | |
87 | generation in which $x$ was created. For example, $g(0) = 0$ and $g(-1) = 1$. | |
88 | \end{defi} | |
89 | ||
90 | \begin{defi} \label{defi:younger} | |
91 | Given two sets of surreal numbers $X$ and $Y$ with equal cardinality, we say | |
92 | that $X$ is \emph{younger} than $Y$ iff, $\forall x_i \in X$ and $\forall y_j | |
93 | \in Y$ it holds that $\sum g(x_i) < \sum g(y_j)$. Similarly, we say that $Y$ is | |
94 | \emph{older} than $X$. | |
95 | \end{defi} | |
96 | ||
97 | With these definitions in place, let's start pursuing an order. | |
98 | ||
99 | \begin{theorem} \label{thm:transitive} | |
100 | Axiom \autoref{ax:leq-relation} is transitive. That is, if $x \leq y$ and $y | |
101 | \leq z$, then $x \leq z$. | |
102 | \end{theorem} | |
103 | ||
104 | \begin{proof} | |
105 | Seeking a contradiction, let $x = \surreal{X_L}{X_R}$, $y = | |
106 | \surreal{Y_L}{Y_R}$, and $z = \surreal{Z_L}{Z_R}$ be the youngest set of | |
107 | numbers satisfying $x \leq y$, $y \leq z$ and $x \nleq z$. Note by inspection | |
108 | that generation-0 and generation-1 obey transitivity. | |
109 | ||
110 | By Axiom \autoref{ax:leq-relation}, this creates two possible cases. There | |
111 | could exist an $x_L \in X_L$ such that $x_L \geq z$ or there could exist a $z_R | |
112 | \in Z_R$ such that $z_R \leq x$. | |
113 | ||
114 | In either case, we end up with a set of three numbers which do not obey | |
115 | transitivity, namely \set{y, z, x_L} or \set{z_R, x, y}. But, since $x_L | |
116 | \in X_L$ and $z_R \in Z_R$, we know that $g(x_L) < g(x)$ and $g(z_R) < g(z)$. | |
117 | In other words, if we consider the sum $g(x) + g(y) + g(z)$, it must be greater | |
118 | than both the sum $g(y) + g(z) + g(x_L)$ and the sum $g(z_R) + g(x) + g(y)$. | |
119 | ||
120 | Since this means a younger set of numbers exist for which transitivity fails, | |
121 | we have reached the desired contradiction. | |
122 | \end{proof} | |
123 | ||
124 | \begin{theorem} \label{thm:reflexive} | |
125 | Axiom \autoref{ax:leq-relation} is reflexive. That is, $x \leq x$. | |
126 | \end{theorem} | |
127 | ||
128 | \begin{proof} | |
129 | Let $x$ be the youngest number satisfying $x \nleq x$. Note that $0 \leq 0$ by | |
130 | inspection. | |
131 | ||
132 | By Axiom \autoref{ax:leq-relation}, this creates two possible cases. Either | |
133 | $\exists x_L \in X_L$ such that $x \leq x_L$ or $\exists x_R \in X_R$ such that | |
134 | $x_R \leq x$. | |
135 | ||
136 | In the first case, by Axiom \autoref{ax:leq-relation}, we find that $X_L \ngeq | |
137 | x_L$, implying that $x_L \ngeq x_L$, a contradiction since $x_L \in X_L$ from | |
138 | the start. We arrive at a similar contradiction for the second case. | |
139 | \end{proof} | |
140 | ||
141 | Per \autoref{thm:transitive} and \autoref{thm:reflexive}, we find that Axiom | |
142 | \autoref{ax:leq-relation} is at least a preorder on our universe. Normally we | |
143 | would move on to proving that Axiom \autoref{ax:leq-relation} is antisymmetric, | |
144 | however, there is a problem. Working by hand with Axioms | |
145 | \autoref{ax:symbol-generation} and \autoref{ax:number-definition}, generation-2 | |
146 | contains the following numbers. | |
420b0302 AT |
147 | |
148 | $$\surreal{-1}{}, \surreal{1}{}, \surreal{-1,0}{}, \surreal{0,1}{},$$ | |
149 | $$\surreal{-1,1}{}, \surreal{-1,0,1}{}, \surreal{-1}{1}, \surreal{0}{1},$$ | |
150 | $$\surreal{-1,0}{1}, \surreal{}{1}, \surreal{-1}{0}, \surreal{}{-1},$$ | |
151 | $$\surreal{-1}{0,1}, \surreal{}{0,1}, \surreal{}{-1,0}, \surreal{}{-1,1},$$ | |
152 | $$\surreal{}{-1,0,1}$$ | |
153 | ||
a7ed1bc8 AT |
154 | By application of Axiom \autoref{ax:leq-relation}, note that $\surreal{}{} \leq |
155 | \surreal{-1}{1}$ and also $\surreal{-1}{1} \leq \surreal{}{}$, yet clearly | |
156 | $\surreal{}{} \neq \surreal{-1}{1}$. It turns out that Axiom | |
157 | \autoref{ax:leq-relation} fails to define even a partial order. | |
158 | ||
159 | For now, let's simply define antisymmetry into existence, give it a special | |
160 | name and symbol so we know where we've strayed from Knuth, and move on with | |
161 | creating our program. Worst case, it'll turn out that we're generating | |
162 | something embedded in a larger space, like the linearly-ordered $\mathbb{R}$ | |
163 | embedded in the not-linearly-ordered $\mathbb{C}$. | |
164 | ||
420b0302 | 165 | \begin{defi} \label{defi:similar} |
a7ed1bc8 AT |
166 | Two numbers $x$ and $y$ are \emph{similar} iff, per Axiom |
167 | \autoref{ax:leq-relation}, $x \leq y$ and $y \leq x$. This is denoted by $x | |
168 | \similar y$. | |
420b0302 AT |
169 | \end{defi} |
170 | ||
a7ed1bc8 AT |
171 | Applying this new definition to the twenty numbers from generations 0-2, we |
172 | find that they start to collapse into equivalency classes, like the | |
173 | aforementioned $\surreal{}{} \similar \surreal{-1}{1}$. More on this later. | |
420b0302 | 174 | |
a7ed1bc8 AT |
175 | Returning to our investigation of order, now that we have `proven' |
176 | antisymmetry, our universe has a partial order. The only thing required to | |
177 | upgrade to a total order is proof that every number is comparable, but first a | |
178 | lemma. | |
179 | ||
180 | \begin{theorem} \label{thm:weak-self-relation} | |
181 | For $x = \surreal{X_L}{X_R}$, it holds that $X_L \leq x \leq X_R$. | |
182 | \end{theorem} | |
183 | ||
184 | \begin{proof} | |
185 | Seeking a contradiction, assume $\exists x_L \in X_L$ such that $x_L \nleq x$. | |
186 | ||
187 | By Axiom \autoref{ax:leq-relation}, this creates two possible cases. Either | |
188 | $\exists (x_L)_L \in (X_L)_L$ such that $(x_L)_L \geq x$ or $\exists x_R \in | |
189 | X_R$ such that $x_R \leq x_L$. By Axiom \autoref{ax:number-definition}, the | |
190 | latter case is impossible. | |
191 | ||
192 | We address the remaining case by inductively noting that $(x_L)_L \leq x_L$, | |
193 | thus $x \leq (x_L)_L$. However, since this means that $x \leq (x_L)_L \leq | |
194 | x_L$, by \autoref{thm:transitive}, $x \leq x_L$. By definition, this means $X_L | |
195 | \nleq x_L$, a contradiction since $x_L \in X_L$. | |
196 | ||
197 | The proof of $x \leq X_R$ follows similarly. | |
198 | \end{proof} | |
199 | ||
200 | \begin{theorem} \label{thm:all-comparable} | |
201 | For every $x$ and $y$ in the universe, if $y \nleq x$, then $x \leq y$. | |
202 | \end{theorem} | |
203 | ||
204 | \begin{proof} | |
205 | Seeking a contradiction, let $x$ and $y$ be numbers such that $y \nleq x$ and | |
206 | $x \nleq y$. | |
207 | ||
208 | By Axiom \autoref{ax:leq-relation}, this creates two possible cases. Either | |
209 | $\exists x_L \in X_L$ such that $x_L \geq y$ or $\exists y_R \in Y_R$ such that | |
210 | $x \geq y_R$. In the first case, by \autoref{thm:weak-self-relation}, $x_L \leq | |
211 | x$, so by \autoref{thm:transitive}, $y \leq x$, a contradiction. A similar | |
212 | contradiction is reached in the other case. | |
213 | \end{proof} | |
214 | ||
215 | Well, that's it. We have a total order, but we're no longer in the same | |
216 | universe as Knuth. We can even go one step further and note that, by only | |
217 | considering a finite number of generations, we are guaranteed to only generate | |
218 | a finite quantity of numbers, and a finite totally ordered set is automatically | |
219 | well ordered. | |
220 | ||
221 | With a total order in hand, we can strengthen $x \nleq y$ into $x > y$, | |
222 | motivating the following theorem. | |
223 | ||
224 | \begin{theorem} \label{thm:strong-self-relation} | |
225 | For any number $x = \surreal{X_L}{X_R}$, it holds that $X_L < x < X_R$. | |
226 | \end{theorem} | |
227 | ||
228 | \begin{proof} | |
229 | Simply recognize why `linear order' is a synonym for `total order'. | |
230 | \end{proof} | |
231 | ||
232 | Moving away from considering order, note that creating Definition | |
233 | \autoref{defi:similar} imposed order on our universe at the cost of some | |
234 | uniqueness. Let's examine that loss of uniqueness a bit further. | |
235 | ||
236 | The twenty numbers from generations 0-2 break down into seven similarity-based | |
237 | equivalence classes, as shown below. | |
238 | ||
239 | $$\surreal{}{-1} \similar \surreal{}{-1,0} \similar \surreal{}{-1,1} \similar \surreal{}{-1,0,1}$$ | |
240 | $$\surreal{-1}{0} \similar \surreal{-1}{0,1} \similar \surreal{-1}{}$$ | |
ef10cd2c | 241 | $$\surreal{}{0} \similar \surreal{}{0,1}$$ |
a7ed1bc8 AT |
242 | $$\surreal{}{} \similar \surreal{-1}{1}$$ |
243 | $$\surreal{0}{} \similar \surreal{-1,0}{} \similar \surreal{}{1}$$ | |
ef10cd2c | 244 | $$\surreal{0}{1} \similar \surreal{-1,0}{1}$$ |
a7ed1bc8 AT |
245 | $$\surreal{1}{} \similar \surreal{0,1}{} \similar \surreal{-1,1}{} \similar \surreal{-1,0,1}{}$$ |
246 | ||
247 | Thus, whereas Knuth's universe has 20 numbers by generation-2, our universe | |
248 | only has seven numbers. For convenience, we introduce the following two | |
249 | definitions (and theorems). | |
250 | ||
251 | % ================================================================================================== | |
252 | % ================================================================================================== | |
253 | % ================================================================================================== | |
420b0302 | 254 | |
a7ed1bc8 AT |
255 | \begin{theorem} \label{thm:reduced-form} |
256 | Given an arbitrary number $x$, there exists a number $x' = | |
257 | \surreal{X'_L}{X'_R}$ which is similar to $x$ and has the property that the | |
258 | cardinality of both $X'_L$ and $X'_R$ are one or zero. | |
259 | \end{theorem} | |
260 | ||
261 | \begin{proof} | |
262 | TODO | |
263 | % Since a finite, total ordered set contains a maximum and minimum element, it | |
264 | % follows that we can define $X'_L$ as containing only the maximum element of | |
265 | % $X_L$ and define $X'_R$ as containing only the minimum element of $X_R$. If | |
266 | % either $X_L$ or $X_R$ are the empty set, the corresponding $X'_L$ or $X'_R$ is | |
267 | % also the empty set. | |
268 | % | |
269 | % Then, to show that $x \similar x'$, we apply Axiom \autoref{ax:leq-relation} in | |
270 | % both directions. | |
271 | % | |
272 | % In the forward direction, $x \leq x'$ means that, $\forall x_L \in X_L$, it | |
273 | % must hold that $x_L \leq x'$. Applying \autoref{thm:strong-self-relation}, we | |
274 | % conclude that $x_L \leq x'_L < x'$. (this isn't quite right. reconsider my | |
275 | % approach) | |
276 | % | |
277 | % ... | |
278 | % | |
279 | % By Axiom \autoref{ax:leq-relation} and \autoref{thm:weak-self-relation}, for | |
280 | % $x'_l \in X'_L$, | |
281 | % | |
282 | % ================== | |
283 | % | |
284 | % The current ten equivalence classes were created by noting that every number | |
285 | % with a left or right set containing more than one element is similar to another | |
286 | % number whose sets do NOT contain more than one element. Since similarity is | |
287 | % built atop the LEQ relation from Axiom \autoref{ax:leq-relation} which itself | |
288 | % is based upon element-wise comparisons, we see that the only elements of | |
289 | % importance to these relations are the largest element of the left set and the | |
290 | % smallest element of the right set. Of course, for such a statement to be | |
291 | % sensical, we must first prove that Axiom \autoref{ax:leq-relation} imposes a | |
292 | % total ordering, otherwise there might not be a largest or smallest element in a | |
293 | % set. | |
294 | % | |
295 | % From this we see that, since Axiom \autoref{ax:leq-relation} makes its | |
296 | % comparison element-wise, every surreal number generated by our current, finite | |
297 | % methods must be similar to a surreal number containing one or zero elements in | |
298 | % its left and right sets since only the largest member of the left set and | |
299 | % smallest member of the right set are important. This motivates the following | |
300 | % definition. | |
301 | \end{proof} | |
420b0302 AT |
302 | |
303 | \begin{defi} \label{defi:reduced-form} | |
a7ed1bc8 AT |
304 | Given an arbitrary number $x$, the $x'$ guaranteed to exist by |
305 | \autoref{thm:reduced-form} is termed the \emph{reduced form} of $x$. | |
420b0302 AT |
306 | \end{defi} |
307 | ||
a7ed1bc8 AT |
308 | \begin{theorem} \label{thm:named-form} |
309 | TODO: Without defining a named form, prove that it is unique. | |
310 | \end{theorem} | |
311 | ||
312 | \begin{proof} | |
313 | TODO | |
314 | \end{proof} | |
315 | ||
316 | \begin{defi} \label{defi:named-form} | |
317 | TODO: Define a named form as the oldest reduced form of an equivalence class determined by similarity. | |
318 | \end{defi} | |
420b0302 | 319 | |
a7ed1bc8 AT |
320 | % ================================================================================================== |
321 | % ================================================================================================== | |
322 | % ================================================================================================== | |
323 | ||
324 | Between \autoref{thm:strong-self-relation} and Definition | |
325 | \autoref{defi:named-form} which follows from \autoref{thm:named-form}, we | |
326 | finally possesss the tools necessary to finish our Go program and use it to | |
327 | generate and examine a surreal number line. | |
af665c3c | 328 | |
420b0302 AT |
329 | |
330 | \subsection{Conjecture} | |
331 | ||
332 | If we can build an addition operation which holds for $1 + (-1) = 0$, then we | |
333 | could start trying to assign meaningful names to some of the elements from | |
334 | generation-2. It appears that numbers of the form \surreal{n}{} behave like the | |
af665c3c AT |
335 | number $n+1$ and similarly, \surreal{}{n} behaves like $n-1$. That seems to |
336 | build the integers. | |
420b0302 AT |
337 | |
338 | If we write a program to generate a bunch of new surreal numbers and graph them | |
339 | as ``generation vs magnitude'', perhaps we can assign some meaning to numbers | |
340 | which don't fit the pattern mentioned in the previous paragraph. Maybe these | |
af665c3c AT |
341 | behave like $1/n$? It sort of feels like surreal numbers constructed via finite |
342 | repetitions of our current process will end up building something vaguely like | |
343 | the dyadic rationals. | |
344 | ||
a7ed1bc8 AT |
345 | Are numbers just the average of their left and right sets (in reduced form)? |
346 | For example, $\surreal{-1}{1} \similar \surreal{}{}$. If so, then generation-2 | |
347 | includes numbers like $\pm \frac{1}{2}$. | |
348 | ||
349 | If my suspicions about symmetry are correct, anytime the number of equivalence | |
350 | classes is even, there are at least two equivalence classes that are similar. | |
351 | ||
352 | Since the universe is growing in both direction, I don't think we can impose a | |
353 | useful well ordering on the whole set unless considering a finite number of | |
354 | generations. |