User:Dugwiki/Surreal numbers

From Wikipedia, the free encyclopedia

This page is intended to hold proofs I'm working on of theorems related to Surreal numbers. I was curious about the topic and noticed a lack of online versions of proofs of theorems and statements in the article itself. For now the work is just a personal indulgence, but if it turns out to be interesting I may see about transferring it to Wikibooks as a supplemental article for people who read the Surreal numbers article and want some additional detail.

[edit] Basic definitions

To review the basic definitions, a surreal number X is an object that consists of a (possibly empty) pair of collections of other surreal numbers called "X left" and "X right", denoted as X_L and X_R respectively. The normal notation is to say that X = {X_L | X_R}, and as we proceed it will be shown that the two sides are essentially sets of lower and upper bounds for X.

We also define the relation $\le$ between two surreal numbers as:

Comparison Rule: For a surreal number x = { X_L | X_R } and y = { Y_L | Y_R } it holds that x ≤ y if and only if y is less than or equal to no member of X_L, and no member of Y_R is less than or equal to x.

Additionally, if $x \le y$ but $y \not\le x$ then we say that $x < y\,$ .

We restrict the construction of surreal numbers using the $\le$ relation as follows:

Construction Rule: If L and R are two sets of surreal numbers and no member of R is less than or equal to any member of L then { L | R } is a surreal number.

Finally, we define a base surreal number, 0 = { | }, with empty left and right boundaries. With 0 defined, we now have a basis from which to inductively construct and prove theorems about surreal numbers.

[edit] Properties of $\le$

Our first priority is to show that $\le$ will be able to help form an ordering on the surreal numbers analogous to the like relation on the real numbers. To begin, we will need to prove that $\le$ is a total preorder on the surreal numbers, meaning that it is both total and transitive.

Since many of the proofs here will be by induction, we'll start with a simple basic lemma:

[edit] Lemma: 0 $\le$ 0

Proof: Since 0_L and 0_R are both empty, it follows that $\not\exists x \in 0_L\ s.t.\ 0 \le x$ and $\not\exists x \in 0_R\ s.t.\ x \le 0$ . Therefore by definition $0 \le 0\; _\Box$

With the above proven, we can now proceed to start showing certain general properties of $\le$ by induction.

[edit] Reflexivity

Theorem: For all surreal numbers X, $X \le X$

Proof by induction:

(Base) We proved above that $0 \le 0$

(Induction) Let surreal number X be given and assume that for all $a \in X_L \cup X_R \;, a \le a$ . Then we wish to show that $X \le X$ .

Assume for the moment that $\exists a \in X_L \;s.t. \; X \le a$ . Then by definition $\not\exists b \in X_L \;s.t. \; a \le b$ . But by the inductive assumption $a \in X_L$ and $a \le a$ . Therefore by contradiction $\not\exists a \in X_L \;s.t. \; X \le a$ .
Now assume that $\exists a \in X_R \;s.t. \; a \le X$ . Then by definition $\not\exists b \in X_R \;s.t. \; b \le a$ . But by the inductive assumption $a \in X_R$ and $a \le a$ . Therefore by contradiction $\not\exists a \in X_R \;s.t. \; a \le X$ .

Thus combining 1) and 2) above we derive that $\not\exists a \in X_L \;s.t. \; X \le a$ and $\not\exists a \in X_R \;s.t. \; a \le X$ . So by definition $X \le X$ . $_\Box$

Now that we've proven reflexivity, we'll proceed with some intermediary results.

[edit] Left side < X and X < right side

Theorem For all $a \in X_L \; a \le X$

Proof by induction:

(Base case) $0_L\;$ and $0_R\;$ are empty so the theorem is vacuously true.

(Induction) Assume that for all $a \in X_L$ that $\forall b \in a_L \; b \le a$ .

Let $a \in X_L$ . We want to show that $a \le X$ .

Assume $\exists b \in X_R \; b \le a$ . But since $b \in X_R$ and $a \in X_L$ by definition of right/left $b \not\le a$ . So by contradiction $\not\exists b \in X_R \; b \le a$ .

Now assume $\exists b \in a_L \; X \le b$ . Then by the inductive assumption $b \le a$ . But since $X \le b$ it follows $\not\exists y \in X_L \; b \le y$ , and so since $a \in X_L$ , we find that $b \not\le a$ . Thus by contradiction $\not\exists b \in a_L \; X \le b$ .

Therefore since $\not\exists b \in X_R \; b \le a$ and $\not\exists b \in a_L \; X \le b$ by definition $a \le X$ . $_\Box$

Theorem For all $a \in X_R \; X \le a$

Proof by induction:

(Base case) $0_L\;$ and $0_R\;$ are empty so the theorem is vacuously true.

(Induction) Assume that for all $a \in X_R$ that $\forall b \in a_R \; a \le b$

Let $a \in X_R$ . We want to show that $X \le a$ .

Assume $\exists b \in X_L \; a \le b$ . But since $a \in X_R$ and $b \in X_L$ by definition of right/left $a \not\le b$ . So by contradiction $\not\exists b \in X_L \; a \le b$ .

Now assume $\exists b \in a_R \; b \le X$ . Then by the inductive assumption $a \le b$ . But since $b \le X$ it follows $\not\exists y \in X_R \; y \le b$ , and so since $a \in X_R$ , we find that $a \not\le b$ . Thus by contradiction $\not\exists b \in a_R \; b \le X$ .

Therefore since $\not\exists b \in X_L \; a \le b$ and $\not\exists b \in a_R \; b \le X$ by definition $X \le a$ . $_\Box$

Thus the above theorems show that, as expected, members of $X_L\;$ are lower bounds of $X\;$ , while members of $X_R\;$ are upper bounds of $X\;$ .

Lemma For all surreal numbers $X, X \not\in X_L$ and $X \not\in X_R$

Proof: Assume $X \in X_L$ . Then since $X \le X$ it follows that $\exist a \in X_L \; X \le a$ . But since $X \le X$ , it follows by definition that $\not\exist a \in X_L \; X \le a$ . So by contradiction $X \not\in X_L$

Now assume $X \in X_R$ . Then since $X \le X$ it follows that $\exist a \in X_R \; a \le X$ . But since $X \le X$ , it follows by definition that $\not\exist a \in X_R \; a \le X$ . So by contradiction $X \not\in X_R$ . $_\Box$

In fact, we can show that everything on the left is $< X$ and everything on the right is $> X$ .

Theorem For all $a \in X_L\; a < X$

Proof: Let $a \in X_L$ and assume $X \le a$ . Then $\not\exists y \in X_L\; a \le y$ . But $a \in X_L$ and $a \le a$ so by contradiction $X \not\le a$ . Therefore since $a \le X$ and $X \not\le a$ by definition $a < X\;$ . $_\Box$

Theorem For all $a \in X_R\; X < a$

Proof: Let $a \in X_R$ and assume $a \le X$ . Then $\not\exists y \in X_R\; X \le a$ . But $a \in X_R$ and $a \le a$ so by contradiction $a \not\le X$ . Therefore since $X \le a$ and $a \not\le X$ by definition $X < a\;$ . $_\Box$

Thus everything included in the left side can be considered a strict lowerbound less than X, and everything in the right side is a strict upperbound on X. Now to show totality.

[edit] Totality

Theorem For all surreals $X\;$ and $Y\;$ either $X \le Y$ or $Y \le X$

Proof by induction:

(Base) $0 \le 0$

(Induction) Assume that for all $a,b \in X_L \cup X_R$ that either $a \le b$ or $b \le a$ . Then let $a \in X_L \cup X_R \cup \{X\}$ . We want to show that either $a \le X$ or $X \le a$ .

1) Assume $a = X\;$ . Then since $\le$ is reflexive $a \le a$ .

2) Assume $a \in X_L$ . Then $a \le X$

3) Assume $a \in X_R$ . Then $X \le a$ . $_\Box$

An immediate corollary is that for all surreal numbers x and y if x is not equivalent to y, then either x < y or y < x.

With totality in hand, we'll now show that $\le$ is transitive.

[edit] Transitivity

Theorem: If $X \le Y$ and $Y \le Z$ then $X \le Z$

Proof by induction: (Base) $0 \le 0$

(Induction) Assume that $\forall a,b,c \in X_L \cup X_R$ that if $a \le b$ and $b \le c$ then $a \le c$ . Then we want to show the same transitive property holds for $a,b \in X_L \cup X_R$ and $X\;$ . There are three possible cases to consider to show transitivity.

1) Assume $a \le b$ and $b \le X$ . Since $b \le X$ and $b \in X_L \cup X_R$ it follows that $b \in X_L$ because $\forall y \in X_R y \not\le X$ . Because $a \le b$ and $\not\exists y \in X_R\; y \le b$ , $a \in X_L$ . And therefore $a \le X$ .

2) Assume $X \le a$ and $a \le b$ . Since $X \le a$ it follows that $a \in X_R$ because $\forall y \in X_L X \not\le y$ . Because $a \le b$ and $\not\exists y \in X_L\; a \le y$ , $b \in X_R$ . And therefore $X \le b$ .

3) Assume $a \le X$ and $X \le b$ . Since $a \le X$ it follows that $a \in X_L$ . And since $X \le b$ it follows that $b \in X_R$ . Because $\le$ is total, either $a \le b$ or $b \le a$ . But by the definition of construction since $b \in X_R$ and $a \in X_L$ it follows that $b \not\le a$ . Thus $a \le b$ . $_\Box$

We have now established that $\le$ is a total preorder on the surreal numbers. We'll see momentarily that it is, in fact, not antisymmetric, but first let's construct a few surreal numbers to help see how they operate.

[edit] Constructing the first few surreal numbers

The initial base surreal number will be $0 = \{\;|\;\}$ , which we've dealt with above.

Now we begin constructing the surreal numbers inductively. At each step of the induction, we'll define $S_0 = \{0\}\;$ and $S_{n+1}\;$ to be the set of surreals directly constructed from subsets of $S_n\;$ .

So $S_1 = \{\{0|\},\{|0\}\}\;$ . Note that $\{0|0\}\;$ is not a valid surreal number because $0 \le 0\;$ .

Since $0 \in \{|0\}_R$ it follows that $\{|0\} < 0\;$ . Likewise since $0 \in \{0|\}_L$ it follows that $0 < \{0|\}\;$ . Thus these three numbers are an ordered sequence which we will label as $-1 = \{|0\}\;$ and $1 = \{0|\}\;$ . With that labelling we can write this simply as $-1 < 0 < 1\;$ .

So far so good. Let's move on to $S_2\;$ . One of the surreal numbers generated is $\{|-1\} < -1\;$ . Similarly, we can generate $\{|-1,0\} < -1\;$ . Notice though that $\{|-1\} \le \{|-1,0\}$ and $\{|-1,0\} \le \{|-1\}$ . Thus we can see that $\le$ is not a total order but is rather a total preorder. To adjust things so we can work with a total order, we'll use the equivalence relation implied by the total preorder:

$a == b\;$ if and only if $a \le b$ and $b \le a$

and work with the equivalence classes implied by that relation. We write $[X]\;$ to mean the equivalence class of all surreal numbers equivalent to X. For example, within $S_1\;$ we have that $[0]\;$ includes $0,\{-1|\},\{-1|1\},\{|1\}\;$ .

Completing $S_1\;$ we have seven distinct equivalence classes, labelled -2, -1, -1/2, 0, 1/2, 1 and 2 respectively:

[-2] contains {|-1} (which we'll call -2) == {|-1,0} == {|-1,1} == {-1,0,1} <

[-1] contains -1 == {|0,1} <

[-1/2] contains {-1|0} (which we'll call -1/2) == {-1|0,1} <

[0] contains 0 == {-1|} == {-1|1} == {|1} <

[1/2] contains {0|1} (which we'll call 1/2) == {-1,0|1} <

[1] contains 1 == {-1,0|} <

[2] contains {1|} (which we'll call 2) == {0,1|} == {-1,1|} == {-1,0,1|}

At this point it would be useful to have a way to simplify how to tell when two surreal numbers are equivalent. The following theorems should prove handy in that regard.

[edit] Eliminating excess lower and upper bounds

Theorem For a surreal number $X\;$ , if $b \in X_L$ and $a \le b$ then $X == \{X_L \cup \{a\} | X_R\}$

Proof

Let a, b and X be given such that $b \in X_L$ and $a \le b$ , and let $Y = \{X_L \cup \{a\} | X_R\}$ . We want to show $X \le Y$ and $Y \le X$ .

1a)Let $c \in Y_R$ be given. Since $Y_R = X_R\;$ it follows that $c \in X_R$ and thus $c \not\le X$ .

1b)Let $c \in X_L$ be given. Then $c \in X_L \cup \{a\} = Y_L$ , so $Y \not\le c$ . Therefore by 1a and 1b, $X \le Y$ .

2a)Let $c \in X_R$ be given. Since $X_R = Y_R\;$ , $c \in Y_R$ and therefore $c \not\le Y$ .

2b)Let $c \in Y_L$ be given. Then either $c \in X_L\;$ or $c = a\;$ . If $c \in X_L$ then $X \not\le c$ . If $c=a\;$ then by our initial assumption $c \le b$ and $b \in X_L$ . Assume $X \le c$ . Then since $c \le b$ by transitivity $X \le b$ . But because $b \in X_L$ it follows that $X \not\le b$ . So therefore by contradiction $X \not\le c$ . And so by 2a and 2b $Y \le X$ . $_\Box$

The upshot of the above theorem is that, when it comes to equivalence, you can ignore lower bounds less than the maximal lower bound. So for example $\{0|1\} == \{-1,0|1\} == \{-2,0|1\} == \{-2,1,0|1\}\;$ . Since the right hand sides are equal only the maximal lower bound 0 matters for purposes of equivalence.

A similar theorem exists for upper bounds.

Theorem For a surreal number $X\;$ , if $b \in X_R$ and $b \le a$ then $X == \{X_L | X_R \cup \{a\}\}$

Proof Let a, b and X be given such that $b \in X_R$ and $b \le a$ , and let $Y = \{X_L | X_R \cup \{a\} \}$ . We want to show $X \le Y$ and $Y \le X$ .

1a)Let $c \in Y_L$ be given. Since $Y_L = X_L\;$ it follows that $c \in X_L$ and thus $X \not\le c$ .

1b)Let $c \in X_R$ be given. Then $c \in X_R \cup \{a\} = Y_R$ , so $c \not\le Y$ . Therefore by 1a and 1b, $Y \le X$ .

2a)Let $c \in X_L$ be given. Since $X_L = Y_L\;$ , $c \in Y_L$ and therefore $Y \not\le c$ .

2b)Let $c \in Y_R$ be given. Then either $c \in X_R\;$ or $c = a\;$ . If $c \in X_R$ then $c \not\le X$ . If $c=a\;$ then by our initial assumption $b \le c$ and $b \in X_R$ . Assume $c \le X$ . Then since $b \le c$ by transitivity $b \le X$ . But because $b \in X_R$ it follows that $b \not\le X$ . So therefore by contradiction $c \not\le X$ . And so by 2a and 2b $X \le Y$ . $_\Box$

Therefore, if maximal lower bounds exist or minimal upper bounds exist, you can ignore anything but those when determining equivalence.

[edit] Labelling surreal numbers

Above we talked above about labelling certain surreal numbers to correspond to various real numbers. We need to choose these labels such that the total ordering of the equivalence classes is isomorphic to the ordering of the reals. We also, as will be discussed later, want to choose our labels so that we can imbed the surreal numbers with the arithmetic operations of addition, negation and multiplication, and do it in such a way that it is naturally isomorphic to the corresponding operations in the reals. So if we perform an operation on two real numbers, the same operation on the corresponding surreal numbers gives the expected result.

We already defined 0 as a base case. Inductively, we can generate all the positive integer surreals by saying the successor to the number labelled n is $\{n|\}\;$ . So $1 = \{0|\}, 2 = \{1|\}\;$ and so on.

We also have labelled $\{0|1\} = 1/2\;$ . With that plus the integers, once we develop operations for addition, negation and multiplication we will be able to identify equivalence classes of surreals with any real number of the form $m / 2 n$ for any integers m and n. So let's get to it....

[edit] Addition, Negation and Multiplication

Conway defines addition, negation and multiplication as follows:

Addition

$x + y = \{X_L + y \cup x + Y_L | X_R + y \cup x + Y_R\}$ where for a set A and number x $A + x = \{a + x|a \in A\}$ and $x + A = \{x + a|a \in A\}$

Negation

$-x = \{-X_R|-X_L\}\;$ where for a set $A, -A = \{-a|a \in A\}$

Multiplication

$xy = \{(X_Ly + xY_L - X_LY_L) \cup (X_Ry + xY_R - X_RY_R) | (X_Ly + xY_R - X_LY_R) \cup (X_Ry + xY_L - X_RY_L)\}$ where $XY = \{xy | x \in X, y \in Y\}, Xy = X\{y\}, xY = \{x\}Y$

The intent is that these operations should, together with $\le$ , form an ordered field in the surreal numbers.

[edit] 0 is the additive identity

Theorem $x + 0 = 0 + x = x\;$

Proof by induction:

(base)

$\begin{align} 0 + 0 &= \{0_L + 0 \cup 0 + 0_L | 0_R + 0 \cup 0 + 0_R \} \\ &= \{\{a + 0 | a \in 0_L\} \cup \{0 + a|a \in 0_L\} | \{a + 0 | a \in 0_R\} \cup \{0 + a | a \in 0_R \} \} \\ \end{align}$

And since both $0_L\;$ and $0_R\;$ are empty, $\begin{align} 0 + 0 &= \{ \; | \; \} = 0 \end{align}$

(induction) Let surreal number x be given and assume that for all $z \in X_L \cup X_R \; 0 + z = z + 0 = z$ . We want to show that $x + 0 = 0 + x = x \;$

Since both $0_L\;$ and $0_R\;$ are empty, it follows that

$\begin{align} x + 0 &= \{X_L + 0 \cup x + 0_L | X_R + 0 \cup x + 0_R\} \\ &= \{X_L + 0 \cup \{x + a|a \in 0_L \} | X_R + 0 \cup \{x + a | a \in 0_R \}\} \\ &= \{X_L + 0 | X_R + 0 \} \\ &= \{\{a + 0 | a \in X_L\} | \{a + 0 | a \in X_R \}\} \\ \end{align}$

By our inductive assumption above $a + 0 = 0 + a = a\;$ so

$\begin{align} x + 0 &= \{\{0 + a | a \in X_L\} | \{0 + a | a \in X_R \}\} \\ &= \{\{a | a \in X_L\} | \{a | a \in X_R \}\} \\ &= \{X_L | X_R\} = x \end{align}$

and since $0_L\;$ and $0_R\;$ are empty

$\begin{align} x + 0 &= \{0 + X_L | 0 + X_R \} \\ &= \{\{a + x | a \in 0_L\} \cup 0 + X_L | \{a + x | a \in 0_R\} \cup 0 + X_R \} \\ &= \{0_L + x \cup 0 + X_L | 0_R + x \cup 0 + X_R \} \\ &= 0 + x \\ \end{align} _\Box$

[edit] Commutativity of addition

Theorem $x + y = y + x\;$ for all surreal numbers x and y

Proof by induction:

Let surreal numbers x and y be given.

(Base) $x + 0 = 0 + x = x\;$ and $y + 0 = 0 + y = y\;$

(Induction) Assume that for all $z \in X_L \cup X_R \cup Y_L \cup Y_R\;$ that $x+z = z+x\;$ and $y+z = z+y\;$ . Then we want to show that $x+y = y+x\;$

$\begin{align} x + y & = \{X_L + y \cup x + Y_L | X_R + y \cup x + Y_R\} \\ & = \{x + Y_L \cup X_L + y| x + Y_R \cup X_R + y\} \\ & = \{\{x + a|a \in Y_L\} \cup \{a + y | a \in X_L\} | \{x + a|a \in Y_R\} \cup \{a + y | a \in X_R\}\} \\ \end{align}$

so by our inductive assumption,

$\begin{align} x + y & = \{\{a + x|a \in Y_L\} \cup \{y + a | a \in X_L\} | \{a + x|a \in Y_R\} \cup \{y + a | a \in X_R\}\} \\ & = \{Y_L + x \cup y + X_L | Y_R + x \cup y + X_R \} \\ & = y + x \; _\Box \end{align}$

[edit] Associativity of addition

Theorem For all surreal numbers $x,y,z \; x+(y+z) = (x+y)+z$

Proof: Let surreal numbers x,y and z be given

(base) Since addition is commutative, $0 + (0 + 0) = (0 + 0) + 0\;$

(induction) Assume for all $a \in X_L \cup X_R \cup Y_L \cup Y_R \cup Z_L \cup Z_R$ that:

$a + (x + y) = (a + x) + y$
$a + (y + z) = (a + y) + z$
$a + (x + z) = (a + x) + z$
$x + (a + y) = (x + a) + y$
$x + (a + z) = (x + a) + z$
$y + (a + z) = (y + a) + z$
$x + (y + a) = (x + y) + a$
$x + (z + a) = (x + z) + a$
$y + (z + a) = (y + z) + a$

Then we want to show that $x+(y+z) = (x+y)+z\;$

$\begin{align} x+(y+z) &= \{X_L + (y+z) \cup x + (y+z)_L | X_R + (y+z) \cup x + (y+z)_R \} \\ &= \{\{a + (y+z) | a \in X_L \} \cup \{x + a | a \in (y+z)_L\} | \{a + (y+z) | a \in X_R \} \cup \{x + a | a \in (y+z)_R\} \} \\ &= \{\{a + (y+z) | a \in X_L \} \cup \{x + a | a \in \{Y_L + z \cup y + Z_L \} \} | \{a + (y+z) | a \in X_R \} \cup \{x + a | a \in \{Y_R + z \cup y + Z_R \} \} \} \\ &= \{\{a + (y+z) | a \in X_L \} \cup \{x + a | a \in Y_L + z\} \cup \{x + a | a \in y + Z_L \} | \{a + (y+z) | a \in X_R \} \cup \{x + a | a \in Y_R + z\} \cup \{x + a | a \in y + Z_R \} \} \\ &= \{\{a + (y+z) | a \in X_L \} \cup \{x + (a + z) | a \in Y_L \} \cup \{x + (y + a)| a \in Z_L \} | \{a + (y+z) | a \in X_R \} \cup \{x + (a + z) | a \in Y_R \} \cup \{x + (y + a)| a \in Z_R \} \} \\ \end{align}$

And by our inductive assumptions, the above equals

$\begin{align} \dots &= \{ \{(a + y) + z | a \in X_L \} \cup \{(x+a) + z | a \in Y_L\} \cup \{ (x+y) + a | a \in Z_L \} | \{(a + y) + z | a \in X_R \} \cup \{(x+a) + z | a \in Y_R\} \cup \{ (x+y) + a | a \in Z_R \} \} \\ &= \{ \{a + z | a \in X_L+y \} \cup \{a + z | a \in x+Y_L\} \cup \{ (x+y) + a | a \in Z_L \} | \{a + z | a \in X_R+y \} \cup \{a + z | a \in x+Y_R\} \cup \{ (x+y) + a | a \in Z_R \} \} \\ &= \{ \{a + z | a \in X_L+y \cup x+Y_L\} \cup \{ (x+y) + a | a \in Z_L \} | \{a + z | a \in X_R+y \cup x+Y_R\} \cup \{ (x+y) + a | a \in Z_R \} \\ &= \{ \{a + z | a \in (x+y)_L \} \cup \{ (x+y) + a | a \in Z_L \} | \{a + z | a \in (x+y)_R \} \cup \{ (x+y) + a | a \in Z_R \} \} \\ &= \{(x+y)_L + z \cup (x+y) + Z_L | (x+y)_R + z \cup (x+y) + Z_R \} \\ &= (x + y) + z \\ _\Box \end{align}$

[edit] Addition is order preserving

Theorem: For all surreal numbers x, y and z if $x \le y\;$ then $x + z \le y + z\;$

Proof by induction:

(base) $0 \le 0 \;$ and $0 + 0 \le 0 + 0 \;$ .

(induction) Let surreal numbers x, y and z be given and assume that for all $a, b \in X_L \cup X_R \cup Y_L \cup Y_R \cup Z_L \cup Z_R \;$ that if $a \le b\;$ then $a + z \le b + z \;$ . Then we want to show that if $x \le y$ then $x + z \le y + z$ .

1) First assume that $x \le y$ and let $a \in (y+z)_R\;$ be given such that $a \le x + z$ . Then $a \in Y_R + z \cup y + Z_R$ so either $\exists b \in Y_R \; a = b+z$ or $\exists b \in Z_R \; a = y + b$ .

a) Let $b \in Y_R \;$ be given such that $a = b+z\;$ . Then $b+z \le x + z$ . Since $b \in Y_R$ , that implies that $y \le b$ so $x \le y \le b$ . And therefore since $x \le b$ by our inductive assumption it follows that $x + z \le b + z$ , and thus $x+z == b+z\;$ . ...

[edit] Closure of negation

We'll just need to prove two quick lemmas to proceed...

Lemma: $-(-x) = x \;$

Proof by induction:

(Base) -(-0) = -0 = 0

(Induction) Let surreal number x be given and assume that for all $a \in X_L \cup X_R \; -(-a) = a$

$\begin{align} -(-x) &= \{-(-X)_R | -(-X)_L \} \\ &= \{ \{-a | a \in (-X)_R \} | \{-a | a \in (-X)_L \} \} \\ &= \{ \{-a | a \in -X_L \} | \{-a | a \in -X_R \} \} \\ &= \{ \{-(-a) | a \in X_L \} | \{-(-a) | a \in X_R \} \} \\ &= \{ \{a | a \in X_L \} | \{a | a \in X_R \} \} \\ &= \{X_L | X_R \} = X _\Box \end{align}$

Lemma: If $x \le y$ then $-y \le -x$

Proof by induction:

(Base) $0 \le 0$ and $-0 \le -0$

(Induction) Let x and y be given such that $x \le y$ and assume that for all $a \in X_L \cup X_R$ that if $a \le y$ then $-y \le -a$ . We want to show that $-y \le -x$ .

1)Let $a \in (-X)_R$ be given such that $a \le -y$ . Then $-a \in X_L$ so $-a \le x \le y$ . So by our inductive assumption $-y \le a$ .

Theorem For all surreal numbers x, -x is also a surreal number

Proof by induction

(base) -0 = 0

(induction) Let x be given and assume for all $a \in X_L \cup X_R \; \not\exists y \in (-A)_L z \in (-A)_R \; z \le y$ . Then let $a \in (-X)_L \; b \in (-X)_R$ be given.

It follows from the definition of negation that $a \in -X_R$ and $b \in -X_L$ . So $-a \in X_R$ and $-b \in X_L$ and therefore $-b \le -a$ .

[edit] Additive inverse

Theorem: $x + (-x) == 0\;$

Proof by induction:

(Base) $0 + (-0) = (-0) = \{ | \} = 0 \;$

(Induction) Assume that for all $z \in X_L \cup X_R \cup -X_L \cup -X_R \; z + (-z) == 0$ . Then we want to show that $x + (-x) == 0\;$ , ie. that $(x + (-x)) \le 0$ and $0 \le (x + (-x))$ .

$\begin{align} x + (-x) &= \{ X_L + (-x) \cup x + (-x)_L | X_R + (-x) \cup x + (-x)_R \} \\ &= \{ X_L + (-x) \cup x + (-X_R) | X_R + (-x) \cup x + (-X_L) \} \\ \end{align}$

1) Assume $\exists a \in X_R \; a + (-x) \le 0$ . Then by our inductive assumption $(-a + a) + (-x) \le -a + 0$ , so $0 + (-x) \le -a$ and hence $-x \le -a$ . But since $a \in X_R$ , it follows that $-a \in -X_L$ and therefore $-x \not\le -a$ . So by contradiction $\not\exists a \in X_R \; a + (-x) \le 0$ .

2) Assume $\exists a \in -X_L \; x + a \le 0$ . Then by our inductive assumption $x + a + (-a) \le -a$ and so $x \le -a$ . However since $a \in -X_L$ it follows that $-a \in X_L$ since $- ( - a) = a$ , and thus $x \not\le -a$ . Therefore by contradiction $\not\exists a \in -X_L \; x + a \le 0$ .

So by 1) and 2) above $\not\exists a \in (x + (-x))_R \; a \le 0$ . And since $0_L\;$ is empty, we have that $\not\exists a \in 0_L \; (x + (-x)) \le a$ , and therefore $(x + (-x)) \le 0$ .

3) Assume $\exists a \in X_L \; 0 \le a + (-x)$ . Then by our inductive assumption $-a + 0 \le (-a + a) + (-x)$ , so $-a \le 0 + (-x)$ and hence $-a \le -x$ . But since $a \in X_L$ , it follows that $-a \in -X_R$ and therefore $-a \not\le -x$ . So by contradiction $\not\exists a \in X_L \; 0 \le a + (-x)$ .

4) Assume $\exists a \in -X_R \; 0 \le x + a$ . Then by our inductive assumption $-a \le x + a + (-a)$ and so $-a \le x$ . However since $a \in -X_R$ it follows that $-a \in X_R$ since $-(-a) = a \;$ , and thus $-a \not\le x$ . Therefore by contradiction $\not\exists a \in -X_R \; 0 \le x + a$ .

So by 3) and 4) above $\not\exists a \in (x + (-x))_L \; 0 \le a$ . And since $0_R\;$ is empty, we have that $\not\exists a \in 0_R \; a \le (x + (-x))$ , and therefore $0 \le (x + (-x))$ and hence $0 == (x + (-x))\; _\Box$ .

[edit] Closure of addition

Theorem For all surreal numbers $x\;$ and $y\;$ $x+y\;$ is also a surreal number

Proof by induction:

(base) $0 + 0 = 0 \;$ , which is a surreal number.

(induction) Assume that for all $a,b \in X_L \cup X_R \cup Y_L \cup Y_R$ that $a+b, a+x, a+y\;$ are all surreal numbers. Then we want to show that $x + y\;$ is also a surreal number.

$\begin{align} x + y &= \{X_L + y \cup x + Y_L | X_R + y \cup x + Y_R \} \end{align}$

1) Assume $\exists a \in X_R b \in X_L \; a + y \le b + y$ ...

User:Dugwiki/Surreal numbers

From Wikipedia, the free encyclopedia

Contents

[edit] Basic definitions

[edit] Properties of $\le$

[edit] Lemma: 0 $\le$ 0

[edit] Reflexivity

[edit] Left side < X and X < right side

[edit] Totality

[edit] Transitivity

[edit] Constructing the first few surreal numbers

[edit] Eliminating excess lower and upper bounds

[edit] Labelling surreal numbers

[edit] Addition, Negation and Multiplication

[edit] 0 is the additive identity

[edit] Commutativity of addition

[edit] Associativity of addition

[edit] Addition is order preserving

[edit] Closure of negation

[edit] Additive inverse

[edit] Closure of addition

[edit] Distributivity of multiplication over addition

[edit] 1 is the multiplicative identity

Views

Navigation

Interaction

Search

User:Dugwiki/Surreal numbers

From Wikipedia, the free encyclopedia

Contents

[edit] Basic definitions

[edit] Properties of

[edit] Lemma: 0 0

[edit] Reflexivity

[edit] Left side < X and X < right side

[edit] Totality

[edit] Transitivity

[edit] Constructing the first few surreal numbers

[edit] Eliminating excess lower and upper bounds

[edit] Labelling surreal numbers

[edit] Addition, Negation and Multiplication

[edit] 0 is the additive identity

[edit] Commutativity of addition

[edit] Associativity of addition

[edit] Addition is order preserving

[edit] Closure of negation

[edit] Additive inverse

[edit] Closure of addition

[edit] Distributivity of multiplication over addition

[edit] 1 is the multiplicative identity

Views

Navigation

Interaction

Search

[edit] Properties of $\le$

[edit] Lemma: 0 $\le$ 0