So, today we're going to play a bit more with nimbers - in particular, we're
going to take the basic nimbers and operations over nimbers that we defined last time, and
take a look at their formal properties. This can lead to some simpler definitions, and
it can make clear some of the stranger properties that nimbers have.
The first thing we did with nimbers was define nimber addition. The way that we did it was iterative: take a set of existing nimbers that exist at ordinal stage N, and use a simple procedure to try to create as many nimbers as we could by adding pairs of stage-N nimbers. Then we ran out, of new numbers we could create, we'd move to the next ordinal by figuring out the smallest number that hadn't yet been included into the nimbers - and then we'd repeat the generation of the stage N+1 nimbers by addition within the set.
So - being formal, and distinct from that process, we'll repeat the definition of nimber addition:
α+β = the least ordinal distinct from all α'+β and α+β'
where α'<α and β'<β.
What odd properties does addition have in nimbers? Well, the most obvious odd
property we've already seen: for any nimber N, N+N=0. That's pretty strange. Why does that make sense?
Remember that nimbers are related to the game of nim. In nim, you've got a set of piles of stones. In each move, a player can remove any number of stones from one pile. The first player who can't pick up any stones because there are none left loses. Each nimber is, essentially, a model of a game with a certain sized pile of stones. So given a single nimber N, it's a model for game of nim with a single pile of N stones. The addition expression using nimbers N amd M, N+M is a model of a game of Nim with two piles: one of size N, and one of size M. Doing the addition is basically asking what's the nimber that models a single pile game that has exactly the same winners (assuming perfect players) as the two-pile game N+M?
So suppose you've got a game of nim with two piles of size N - the game N+N. If the player who moves second plays well, they're guaranteed to win. Why? because all they need to do is mimic the first player. If the player one takes X stones from pile 1, then player two takes X stones from pile 2. If they just continue to mimic player one using the opposite pile, then they're guaranteed to win - because eventually player one will have to take the last stone from one pile; and then player two will take the last stone from the other pile, which will leave player one with no move: player two wins.
So it's the same outcome as a gave that started with no stones at all: player one can't move, so player 2 wins.
To get to the next interesting bit, we need to toss in another definition. In the definition of addition, we used α' to refer to nimbers smaller than α. We need another similar notion. We've define the number building process, and the meaning of addition in terms of the minimum excluded ordinal or mex. Similarly to the way that we define α' in terms of addition, we can define α* in terms of pure mex: if we've got a set of nimbers, S, and we know that the nimber α is the minimum excluded ordinal of S - that is, α=mex(S), then we'll define α* as a variable that ranges over the members of S. So α* can represent any nimber in a set which has α as its mex. The difference between α* and α' is that α' is by definition less than α - but α* can be larger than α - it just needs to be part of an ordinal set that excludes α
Ok. So - addition obviously needs to satisfy the field axioms, because the whole point of nimbers is that they're a new kind of number field. So we know that α+β=α+γ if and only if β=γ - that's just standard field stuff. But also, in the nimbers, this means that α+β = mex(α*+β ∪ α+β*). This is a major break from our intuitive idea of addition. The α' based definition is nice, because it
builds on the intuitive idea that you can add two big things by breaking them into pieces, and then adding up the pieces. But now, we're saying that we can define the addition of two small numbers by somehow mashing together to big numbers. It's a strange idea - but once you've absorbed the notion that for two numbers α and β both larger than zero, α+β is not necessarily larger than α then it should make sense. And once you have that new definition of addition, then some more field axioms - like associativity - just fall right out.
This is getting long, so I think I'll stop here. Next time, we'll look in more detail at nimber multiplication.
- Log in to post comments
Over at the Online Encyclopedia of Integer Sequences there are 115 related sequences, most with additional references.
A003987 Table of n XOR m (or Nim-sum of n and m) read by antidiagonals, i.e. with entries in the order (n,m) = (0,0),(0,1),(1,0),(0,2),(1,1),(2,0),...
A004520 Generalized nim sum n + n in base 10.
A051775 Table T(n,m) = Nim-product of n and m, read by antidiagonals, for n >= 0, m >= 0.
A054016 a(n) = smallest nonnegative integer not the Nim sum of at most 4 earlier terms.
A080593 Consider the standard game of Nim with 3 heaps and make a list of the losing positions (x,y,z) with x <= y <= z in reverse lexicographic order; sequence gives x values.
and so forth...
Go to OEIS and eneter "nim" in the search engine...
No, that is too weak, after all there are only two options for who wins in a single game. What I think you mean is: what's the nimber such that a single pile of that size can replace a pair of N and M piles in any other Nim game, without changing the outcome.
Hmm, do the nimbers as defined actually form a field? I've only ever seen nimbers as defined in relation to the game nim, i.e., as binary strings with a certain kind of "xor" addition.
But with your definition it looks like the collection of all nimbers form a proper class, not a set, and fields are defined over sets. What implications does this have?
1 - John Conway, ONAG, 2ed, 2001, first dicusses Nim addition and multiplication in chapter 6: 'The Curious Field On2'. The game Nim is discussed in chapter 11: 'Impartial Games and the Game of Nim'.
2 - Nature v446, 26 April 2007 has two topics that relate to computing and game theory:
a - p 1053, RD MacPherson & DJ Srolovitz, 'The von Neumann relation generalized to coarsening of three-dimensional microstructues'. Editor's Summary:
http://www.nature.com/nature/journal/v446/n7139/edsumm/e070426-09.html
Although I may be reading to much into this article, this may be a means to link the von Neumann algebra of physics with the von Neumann MiniMax Theorem which is the foundation of mathematical game theory?
b - p 992, Bernard Chazelle. 'The security of knowing nothing' discusses work of Barak and Sahai by using an example of NP-complete problem. I think this is the paper 'How to Play ANY Mental Game Over the Net: Concurrently composable secure computation without setup assumptions'.
http://www.math.ias.edu/~boaz/Papers/conc-comp.pdf
A field is really a structure in first-order logic, with axioms that speak about elements and operations, and don't use any real set theory. Therefore, the convention that the whole field is a set and not a class is trivial to ignore.
Mathematical logic and model theory aren't my strong suits, but it's still not clear me to me that the difference is "trivial."
Sure, ok, the nimbers are a model of a first-order theory, but is everything we might be proving about those nimbers expressable in first-order logic?
I am not saying that the difference between set and class is trivial for nimbers in general, but that it is trivial for the field properties.
I'm not trying to be difficult but I don't see how we're justified in skipping over this. Yes, I understand that the nimbers are a model of a first-order theory, but so are the reals. However, most of the "interesting" properties of the reals are not expressible in first-order logic, e.g., the LUB property (I could be wrong about this, like I said, model theory isn't my strong suit).
So, what do we lose by restricting ourselves to proofs about the nimbers which only involve first-order constructs? Anything?
As Harvey Friedman (friedman at math.ohio-state.edu) wrote, almost exactly a year ago:
Here we continue to refine the self embedding axiom discussed in
http://www.cs.nyu.edu/pipermail/fom/2006-May/010492.html
The results here grew out of the results claimed in
[1] `Combinatorial set theoretic statements of great logical strength', 1995, 4 pages, abstract.
at http://www.math.ohio-state.edu/%7Efriedman/ paper 2 under downloadable
manuscripts.
LSEA (linear self embedding axiom) is a candidate for the mathematically cleanest statement corresponding to the extreme end of the large cardinal hypotheses over ZFC. It is naturally formulated over ZC.
###########################
Over NBGC = NBG plus global choice, we state
ORDINAL SELF EMBEDDING AXIOM (class). Every binary relation with field On has a self embeddable initial segment.
Over ZFC, we state
ORDINAL SELF EMBEDDING AXIOM (set). Every binary relation whose field is a sufficiently large ordinal, has a self embeddable initial segment.
Before continuing, we clarify any ambiguities in these two statements.
In class theory, a binary relation is a class of ordered pairs. In set theory, a binary relation is a set of ordered pairs. The field of a binary relation is the class of all coordinates of its elements.
Let R be a binary relation whose field is a class, which is also given a linear ordering. This includes the case where the field is On or an ordinal.
An initial segment of R is the restriction of R to some subclass A of its domain which is downward closed. Thus initial segments of R are also binary relations whose field is a set with a linear ordering.
Note that intiial segments may or may not be proper.
Let R be a binary relation. A self embedding of R is a one-one function
h:fld(R) into fld(R) such that
R(x,y) implies R(hx,hy).
A stronger notion is that
R(x,y) iff R(hx,hy), and
x < y iff hx < hy.
We say that R is self embeddable if and only if R has a self embedding that is not the identity. A stronger notion is that R has a self embedding whose range is a proper subclass of fld(R).
The three statements above use the weakest versions of the relevant notions.
We can give sharpened versions as follows.
ORDINAL SELF EMBEDDING AXIOM' (class). Every binary relation with field On has a self embeddable proper initial segment. (The self embedding uses iff
with < as above, and its range is a proper subset of the field).
ORDINAL SELF EMBEDDING AXIOM' (set). Every binary relation whose field is a sufficiently large ordinal, has a self embeddable proper initial segment.
(The self embedding uses iff with < as above, and its range is a proper
subset of the field).
Here is essentially the results from [1], going back to 1995.
LCA1. There is a nontrivial elementary embedding of V ® M such that V(a) à M, where a is the first fixed point above the critical point.
LCA2. There is a nontrivial elementary embedding of some V(kappa) into itself.
Yet stronger than LCA1 is
LCA3. There is a nontrivial elementary embedding of some V(kappa + 1) into itself.
THEOREM 1. In NBGC, OSEA (class), OSEA' (class) follow from LCA1 and imply LCA2. In ZFC, ODEA (set), OSEA' (set) follow from LCA1 and imply LCA2.
In order to make the axioms more mathematically natural, it is best to use a
linear ordering rather than the ordinals.
The idea of stating axioms in the form:
there exists a linear ordering obeying a natural combinatorial property
was already well exploited in my paper
[2] Subtle Cardinals and Linear Orderings, Annals of Pure and Applied
Logic 107 (2001), 1-34.
There is much more to do along these lines.
Over ZC (Zermelo set theory with choice) we state
LINEAR SELF EMBEDDING AXIOM (lsea). There is a linear ordering (X,<) such
that every f:X^2 into X has a self embeddable initial segment.
Here an initial segment of f:X^2 into X is a restriction f:Y^2 into Y, where
Y is a subset of X that is downward closed. We say that h is a self
embedding of f:Y^2 into Y if and only if h is a one-one map from Y into Y,
where
f(x,y) = z implies f(hx,hy) = hz.
A stronger notion is obtained by requiring that
x < y iff hx < hy.
We say that f:Y into Y is self embeddable if and only if f has a self
embedding that is not the identity.
A stronger notion is obtained by requiring that the range of f is a proper
subset of Y.
We can sharpen this as follows.
LINEAR SELF EMBEDDING AXIOM' (lsea). There is a linear ordering (X,<) such
that every f:X^2 into X has a self embeddable proper initial segment. (The
self embedding uses iff with < as above, and its range is a proper subset of
its field).
THEOREM 2. In ZFC, LSEA, LSEA' follow from LCA1 and imply LCA2. ZC + LSEA,
ZC + LSEA interpret LCA2 and are interpretable in LCA1. The interpretations
are "set theoretically good".
Of course, we can also use binary functions for OSEA (set), OSEA' (set),
OSEA (class), OSEA' (class), with the same results.
The proofs show that the least cardinality of such a linear ordering is much
greater than the least kappa with an elementary embedding from V(kappa) into
V(kappa), and much smaller than any critical point of a j according to LCA1.
I'm submitting this again, as the it never appeared the first time.
As Harvey Friedman (friedman at math.ohio-state.edu) wrote, almost exactly a year ago:
Here we continue to refine the self embedding axiom discussed in
http://www.cs.nyu.edu/pipermail/fom/2006-May/010492.html
The results here grew out of the results claimed in
[1] `Combinatorial set theoretic statements of great logical strength', 1995, 4 pages, abstract.
at http://www.math.ohio-state.edu/%7Efriedman/ paper 2 under downloadable
manuscripts.
LSEA (linear self embedding axiom) is a candidate for the mathematically cleanest statement corresponding to the extreme end of the large cardinal hypotheses over ZFC. It is naturally formulated over ZC.
###########################
Over NBGC = NBG plus global choice, we state
ORDINAL SELF EMBEDDING AXIOM (class). Every binary relation with field On has a self embeddable initial segment.
Over ZFC, we state
ORDINAL SELF EMBEDDING AXIOM (set). Every binary relation whose field is a sufficiently large ordinal, has a self embeddable initial segment.
Before continuing, we clarify any ambiguities in these two statements.
In class theory, a binary relation is a class of ordered pairs. In set theory, a binary relation is a set of ordered pairs. The field of a binary relation is the class of all coordinates of its elements.
Let R be a binary relation whose field is a class, which is also given a linear ordering. This includes the case where the field is On or an ordinal.
An initial segment of R is the restriction of R to some subclass A of its domain which is downward closed. Thus initial segments of R are also binary relations whose field is a set with a linear ordering.
Note that intiial segments may or may not be proper.
Let R be a binary relation. A self embedding of R is a one-one function
h:fld(R) into fld(R) such that
R(x,y) implies R(hx,hy).
A stronger notion is that
R(x,y) iff R(hx,hy), and
x < y iff hx < hy.
We say that R is self embeddable if and only if R has a self embedding that is not the identity. A stronger notion is that R has a self embedding whose range is a proper subclass of fld(R).
The three statements above use the weakest versions of the relevant notions.
We can give sharpened versions as follows.
ORDINAL SELF EMBEDDING AXIOM' (class). Every binary relation with field On has a self embeddable proper initial segment. (The self embedding uses iff
with < as above, and its range is a proper subset of the field).
ORDINAL SELF EMBEDDING AXIOM' (set). Every binary relation whose field is a sufficiently large ordinal, has a self embeddable proper initial segment.
(The self embedding uses iff with < as above, and its range is a proper
subset of the field).
Here is essentially the results from [1], going back to 1995.
LCA1. There is a nontrivial elementary embedding of V ® M such that V(a) à M, where a is the first fixed point above the critical point.
LCA2. There is a nontrivial elementary embedding of some V(kappa) into itself.
Yet stronger than LCA1 is
LCA3. There is a nontrivial elementary embedding of some V(kappa + 1) into itself.
THEOREM 1. In NBGC, OSEA (class), OSEA' (class) follow from LCA1 and imply LCA2. In ZFC, ODEA (set), OSEA' (set) follow from LCA1 and imply LCA2.
In order to make the axioms more mathematically natural, it is best to use a
linear ordering rather than the ordinals.
The idea of stating axioms in the form:
there exists a linear ordering obeying a natural combinatorial property
was already well exploited in my paper
[2] Subtle Cardinals and Linear Orderings, Annals of Pure and Applied
Logic 107 (2001), 1-34.
There is much more to do along these lines.
Over ZC (Zermelo set theory with choice) we state
LINEAR SELF EMBEDDING AXIOM (lsea). There is a linear ordering (X,<) such
that every f:X^2 into X has a self embeddable initial segment.
Here an initial segment of f:X^2 into X is a restriction f:Y^2 into Y, where
Y is a subset of X that is downward closed. We say that h is a self
embedding of f:Y^2 into Y if and only if h is a one-one map from Y into Y,
where
f(x,y) = z implies f(hx,hy) = hz.
A stronger notion is obtained by requiring that
x < y iff hx < hy.
We say that f:Y into Y is self embeddable if and only if f has a self
embedding that is not the identity.
A stronger notion is obtained by requiring that the range of f is a proper
subset of Y.
We can sharpen this as follows.
LINEAR SELF EMBEDDING AXIOM' (lsea). There is a linear ordering (X,<) such
that every f:X^2 into X has a self embeddable proper initial segment. (The
self embedding uses iff with < as above, and its range is a proper subset of
its field).
THEOREM 2. In ZFC, LSEA, LSEA' follow from LCA1 and imply LCA2. ZC + LSEA,
ZC + LSEA interpret LCA2 and are interpretable in LCA1. The interpretations
are "set theoretically good".
Of course, we can also use binary functions for OSEA (set), OSEA' (set),
OSEA (class), OSEA' (class), with the same results.
The proofs show that the least cardinality of such a linear ordering is much
greater than the least kappa with an elementary embedding from V(kappa) into
V(kappa), and much smaller than any critical point of a j according to LCA1.
Posted by: Jonathan Vos Post | May 7, 2007 04:05 PM
I'm submitting this again, and on this other thread, as the it never appeared the first time, and the discussion has now included large cardinals, as I'd anticipated.
As Harvey Friedman (friedman at math.ohio-state.edu) wrote, almost exactly a year ago:
Here we continue to refine the self embedding axiom discussed in
http://www.cs.nyu.edu/pipermail/fom/2006-May/010492.html
The results here grew out of the results claimed in
[1] `Combinatorial set theoretic statements of great logical strength', 1995, 4 pages, abstract.
at http://www.math.ohio-state.edu/%7Efriedman/ paper 2 under downloadable
manuscripts.
LSEA (linear self embedding axiom) is a candidate for the mathematically cleanest statement corresponding to the extreme end of the large cardinal hypotheses over ZFC. It is naturally formulated over ZC.
###########################
Over NBGC = NBG plus global choice, we state
ORDINAL SELF EMBEDDING AXIOM (class). Every binary relation with field On has a self embeddable initial segment.
Over ZFC, we state
ORDINAL SELF EMBEDDING AXIOM (set). Every binary relation whose field is a sufficiently large ordinal, has a self embeddable initial segment.
Before continuing, we clarify any ambiguities in these two statements.
In class theory, a binary relation is a class of ordered pairs. In set theory, a binary relation is a set of ordered pairs. The field of a binary relation is the class of all coordinates of its elements.
Let R be a binary relation whose field is a class, which is also given a linear ordering. This includes the case where the field is On or an ordinal.
An initial segment of R is the restriction of R to some subclass A of its domain which is downward closed. Thus initial segments of R are also binary relations whose field is a set with a linear ordering.
Note that intiial segments may or may not be proper.
Let R be a binary relation. A self embedding of R is a one-one function
h:fld(R) into fld(R) such that
R(x,y) implies R(hx,hy).
A stronger notion is that
R(x,y) iff R(hx,hy), and
x
We say that R is self embeddable if and only if R has a self embedding that is not the identity. A stronger notion is that R has a self embedding whose range is a proper subclass of fld(R).
The three statements above use the weakest versions of the relevant notions.
We can give sharpened versions as follows.
ORDINAL SELF EMBEDDING AXIOM' (class). Every binary relation with field On has a self embeddable proper initial segment. (The self embedding uses iff
with
ORDINAL SELF EMBEDDING AXIOM' (set). Every binary relation whose field is a sufficiently large ordinal, has a self embeddable proper initial segment.
(The self embedding uses iff with subset of the field).
Here is essentially the results from [1], going back to 1995.
LCA1. There is a nontrivial elementary embedding of V ® M such that V(a) à M, where a is the first fixed point above the critical point.
LCA2. There is a nontrivial elementary embedding of some V(kappa) into itself.
Yet stronger than LCA1 is
LCA3. There is a nontrivial elementary embedding of some V(kappa + 1) into itself.
THEOREM 1. In NBGC, OSEA (class), OSEA' (class) follow from LCA1 and imply LCA2. In ZFC, ODEA (set), OSEA' (set) follow from LCA1 and imply LCA2.
In order to make the axioms more mathematically natural, it is best to use a
linear ordering rather than the ordinals.
The idea of stating axioms in the form:
there exists a linear ordering obeying a natural combinatorial property
was already well exploited in my paper
[2] Subtle Cardinals and Linear Orderings, Annals of Pure and Applied
Logic 107 (2001), 1-34.
There is much more to do along these lines.
Over ZC (Zermelo set theory with choice) we state
LINEAR SELF EMBEDDING AXIOM (lsea). There is a linear ordering (X, that every f:X^2 into X has a self embeddable initial segment.
Here an initial segment of f:X^2 into X is a restriction f:Y^2 into Y, where
Y is a subset of X that is downward closed. We say that h is a self
embedding of f:Y^2 into Y if and only if h is a one-one map from Y into Y,
where
f(x,y) = z implies f(hx,hy) = hz.
A stronger notion is obtained by requiring that
x
We say that f:Y into Y is self embeddable if and only if f has a self
embedding that is not the identity.
A stronger notion is obtained by requiring that the range of f is a proper
subset of Y.
We can sharpen this as follows.
LINEAR SELF EMBEDDING AXIOM' (lsea). There is a linear ordering (X, that every f:X^2 into X has a self embeddable proper initial segment. (The
self embedding uses iff with its field).
THEOREM 2. In ZFC, LSEA, LSEA' follow from LCA1 and imply LCA2. ZC + LSEA,
ZC + LSEA interpret LCA2 and are interpretable in LCA1. The interpretations
are "set theoretically good".
Of course, we can also use binary functions for OSEA (set), OSEA' (set),
OSEA (class), OSEA' (class), with the same results.
The proofs show that the least cardinality of such a linear ordering is much
greater than the least kappa with an elementary embedding from V(kappa) into
V(kappa), and much smaller than any critical point of a j according to LCA1.
Posted by: Jonathan Vos Post | May 7, 2007 04:05 PM
Posted by: Jonathan Vos Post | May 8, 2007 07:02 AM