Jump to content

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.

Basic definitions

[edit]

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 XL and XR respectively. The normal notation is to say that X = {XL | XR}, 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 between two surreal numbers as:

Comparison Rule
For a surreal number x = { XL | XR } and y = { YL | YR } it holds that xy if and only if y is less than or equal to no member of XL, and no member of YR is less than or equal to x.

Additionally, if but then we say that .

We restrict the construction of surreal numbers using the 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.

Properties of

[edit]

Our first priority is to show that 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 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:

Lemma: 0 0

[edit]

Proof: Since 0L and 0R are both empty, it follows that and . Therefore by definition

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

Reflexivity

[edit]

Theorem: For all surreal numbers X,

Proof by induction:

(Base) We proved above that

(Induction) Let surreal number X be given and assume that for all . Then we wish to show that .

  1. Assume for the moment that . Then by definition . But by the inductive assumption and . Therefore by contradiction .
  2. Now assume that . Then by definition . But by the inductive assumption and . Therefore by contradiction .

Thus combining 1) and 2) above we derive that and . So by definition .


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

Left side < X and X < right side

[edit]

Theorem For all

Proof by induction:

(Base case) and are empty so the theorem is vacuously true.

(Induction) Assume that for all that .

Let . We want to show that .

Assume . But since and by definition of right/left . So by contradiction .

Now assume . Then by the inductive assumption . But since it follows , and so since , we find that . Thus by contradiction .

Therefore since and by definition .


Theorem For all

Proof by induction:

(Base case) and are empty so the theorem is vacuously true.

(Induction) Assume that for all that

Let . We want to show that .

Assume . But since and by definition of right/left . So by contradiction .

Now assume . Then by the inductive assumption . But since it follows , and so since , we find that . Thus by contradiction .

Therefore since and by definition .

Thus the above theorems show that, as expected, members of are lower bounds of , while members of are upper bounds of .

Lemma For all surreal numbers and

Proof: Assume . Then since it follows that . But since , it follows by definition that . So by contradiction

Now assume . Then since it follows that . But since , it follows by definition that . So by contradiction .


In fact, we can show that everything on the left is and everything on the right is .

Theorem For all

Proof: Let and assume . Then . But and so by contradiction . Therefore since and by definition .

Theorem For all

Proof: Let and assume . Then . But and so by contradiction . Therefore since and by definition .


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.

Totality

[edit]

Theorem For all surreals and either or

Proof by induction:

(Base)

(Induction) Assume that for all that either or . Then let . We want to show that either or .

1) Assume . Then since is reflexive .
2) Assume . Then
3) Assume . Then .

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

Transitivity

[edit]

Theorem: If and then

Proof by induction: (Base)

(Induction) Assume that that if and then . Then we want to show the same transitive property holds for and . There are three possible cases to consider to show transitivity.

1) Assume and . Since and it follows that because . Because and , . And therefore .
2) Assume and . Since it follows that because . Because and , . And therefore .
3) Assume and . Since it follows that . And since it follows that . Because is total, either or . But by the definition of construction since and it follows that . Thus .


We have now established that 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.

Constructing the first few surreal numbers

[edit]

The initial base surreal number will be , which we've dealt with above.

Now we begin constructing the surreal numbers inductively. At each step of the induction, we'll define and to be the set of surreals directly constructed from subsets of .

So . Note that is not a valid surreal number because .

Since it follows that . Likewise since it follows that . Thus these three numbers are an ordered sequence which we will label as and . With that labelling we can write this simply as .

So far so good. Let's move on to . One of the surreal numbers generated is . Similarly, we can generate . Notice though that and . Thus we can see that 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:

if and only if and

and work with the equivalence classes implied by that relation. We write to mean the equivalence class of all surreal numbers equivalent to X. For example, within we have that includes .

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

Eliminating excess lower and upper bounds

[edit]

Theorem For a surreal number , if and then

Proof

Let a, b and X be given such that and , and let . We want to show and .

1a)Let be given. Since it follows that and thus .
1b)Let be given. Then , so . Therefore by 1a and 1b, .
2a)Let be given. Since , and therefore .
2b)Let be given. Then either or . If then . If then by our initial assumption and . Assume . Then since by transitivity . But because it follows that . So therefore by contradiction . And so by 2a and 2b .

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 . 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 , if and then

Proof Let a, b and X be given such that and , and let . We want to show and .

1a)Let be given. Since it follows that and thus .
1b)Let be given. Then , so . Therefore by 1a and 1b, .
2a)Let be given. Since , and therefore .
2b)Let be given. Then either or . If then . If then by our initial assumption and . Assume . Then since by transitivity . But because it follows that . So therefore by contradiction . And so by 2a and 2b .

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


Labelling surreal numbers

[edit]

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 . So and so on.

We also have labelled . 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 for any integers m and n. So let's get to it....

Addition, Negation and Multiplication

[edit]

Conway defines addition, negation and multiplication as follows:

Addition

where for a set A and number x and

Negation

where for a set

Multiplication

where

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

0 is the additive identity

[edit]

Theorem

Proof by induction:

(base)

And since both and are empty,

(induction) Let surreal number x be given and assume that for all . We want to show that

Since both and are empty, it follows that


By our inductive assumption above so


and since and are empty

Commutativity of addition

[edit]

Theorem for all surreal numbers x and y

Proof by induction:

Let surreal numbers x and y be given.

(Base) and

(Induction) Assume that for all that and . Then we want to show that

so by our inductive assumption,


Associativity of addition

[edit]

Theorem For all surreal numbers

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

(base) Since addition is commutative,

(induction) Assume for all that:

Then we want to show that


And by our inductive assumptions, the above equals

Addition is order preserving

[edit]

Theorem: For all surreal numbers x, y and z if then

Proof by induction:

(base) and .

(induction) Let surreal numbers x, y and z be given and assume that for all that if then . Then we want to show that if then .

1) First assume that and let be given such that . Then so either or .

a) Let be given such that . Then . Since , that implies that so . And therefore since by our inductive assumption it follows that , and thus . ...

Closure of negation

[edit]

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

Lemma:

Proof by induction:

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

(Induction) Let surreal number x be given and assume that for all


Lemma: If then

Proof by induction:

(Base) and

(Induction) Let x and y be given such that and assume that for all that if then . We want to show that .

1)Let be given such that . Then so . So by our inductive assumption .

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 . Then let be given.

It follows from the definition of negation that and . So and and therefore .

Additive inverse

[edit]

Theorem:

Proof by induction:

(Base)

(Induction) Assume that for all . Then we want to show that , ie. that and .


1) Assume . Then by our inductive assumption , so and hence . But since , it follows that and therefore . So by contradiction .

2) Assume . Then by our inductive assumption and so . However since it follows that since , and thus . Therefore by contradiction .

So by 1) and 2) above . And since is empty, we have that , and therefore .

3) Assume . Then by our inductive assumption , so and hence . But since , it follows that and therefore . So by contradiction .

4) Assume . Then by our inductive assumption and so . However since it follows that since , and thus . Therefore by contradiction .

So by 3) and 4) above . And since is empty, we have that , and therefore and hence .

Closure of addition

[edit]

Theorem For all surreal numbers and is also a surreal number

Proof by induction:

(base) , which is a surreal number.

(induction) Assume that for all that are all surreal numbers. Then we want to show that is also a surreal number.

1) Assume ...

Distributivity of multiplication over addition

[edit]

1 is the multiplicative identity

[edit]