Even XOR Odd Infinities? - MathOverflow

Even XOR Odd Infinities?

2013-01-19T23:19:26Z

Modular Arithmetic (MA) has the same axioms as first order Peano Arithmetic (PA) except $\forall x (Sx \ne 0)$ is replaced with $\exists x(Sx = 0)$. (http://en.wikipedia.org/wiki/Peano_axioms#First-order_theory_of_arithmetic).

MA has arbitrarily large finite models based on modular arithmetic. All finite models of MA have either an even or odd number of elements. I call a model of MA "even" if it satisfies both of these two sentences:

E1) $\exists x(x \ne 0 \land x+x = 0)$

E2) $\forall x(x+x \ne S0)$

A model of MA is odd if it satisfies both of:

O1) $\forall x(x = 0 \lor x+x \ne 0)$

O2) $\exists x(x+x = S0)$

We can use compactness to prove MA has infinite "even" size models by adding the even definitions above as axioms. We can similarly prove there are infinite "odd" size models of MA. Some infinite sets, like the integers, are neither even nor odd. The integers are not the basis for a model of MA. For example, the four square theorem (every number is the sum of four squares) is a theorem of both MA and PA. The four square theorem is false in the integers. It has been conjectured the complex numbers are a basis for a model of MA. If so, the complex numbers would be an "odd" model of MA.

My question is whether every model of MA must be exclusively even or exclusively odd? Is this statement a theorem of MA?

$$\exists x(x \ne 0 \land x+x = 0) \ \overline{\vee}\ \exists x(x+x = S0)$$

I asked this question on stack exchange and got no answer.

http://math.stackexchange.com/questions/214018/even-xor-odd-infinities

Answer by abo for Even XOR Odd Infinities?

2013-01-20T21:37:20Z

NOTE: The first proof is wrong because it uses second-order induction. The second-proof is wrong as well per Wofsey's comment.

Ashutosh in the comments has shown that exclusion holds.

Here is a proof of existence.

Let A be the elements of the model. Let p be the predecessor of 0 in A. Let T = S \ {(p,0)}. Then T induces the normal ordering < on A, with p the maximal element. It can be shown that (1) x < Sy implies x <= y.

Clearly p + p <= p. Let x be the least element such that x + x <= x. We claim x + x = 0 or x + x = 1. Suppose not. Then there exists y such that Sy = x and v such that SSv = x + x and y < x and v < x + x. (y < x because otherwise x = 0, so x + x = 0, a contradiction.) But v = y + y, and v < x + x <= x. So v < Sy. By (1) v <= y, contradicting the leastness of x.

ABOVE assumed second-order induction. BELOW works using first-order induction (and is easier to boot...).

I claim: (x)(∃y(y+y=x v S(y+y)=x))

For this is true when x = 0 (take y = 0). Suppose true for k. If y+y=k, then S(y+y)=Sk. And if S(y+y)=k, then Sy+Sy =Sk. So if true for k, then true for Sk. By induction (first-order!!), the claim is true.

Let p be the predecessor of 0. Then by the claim y+y=p or S(y+y) = p for some y. In the first case Sy+Sy = 1, in the second Sy+Sy = 0.

Answer by Ben Crowell for Even XOR Odd Infinities?

2013-01-21T00:46:08Z

This is just a rough outline and may be wrong, but I thought I'd toss it out and see if I could learn something from my likely mistakes.

Let $I$ be a model of PA and $M$ a model of MA. Let $A=I\times M$ be the model of PA defined by taking the Cartesian product of the two sets and defining $S(i,m)=(i,S(m))$ if $S(m)\ne 0$, else $(S(i),0)$.

To check that $A$ is a model of PA as claimed, the main issue is the verification of induction. Suppose that the hypotheses of induction hold for some set K. If K includes $(i,0)$, then $(i,m)$ is included for all $m$ because induction is a hypothesis of MA. Also, if $(i,0)$ is in K, then so is $(i+1,0)$, since one of the axioms of MA is that there is an $m$ whose successor is 0, and we've already found that all $(i,m)$ are in K. This establishes that induction holds for $A$.

As with any model of PA, the definition of S implies uniquely defined operations of addition and multiplication. Under this definition of addition, any member $(i,m)$ of A can be written as $(i,0)+(0,m)$, and this form is unique. For any two elements of A, we then have $(i,m)+(i',m')=(i+i',0)+(0,m)+(0,m')$, which is of the form $(\ldots,m+m')$.

Suppose that Russell Easterly's conjecture fails, so there is no nonzero $m$ in $M$ such that $m+m=0$ or $m+m=1$. Then there is no nonzero $a$ in $A$ such that $a+a$ equals $(1,0)$ or $(1,1)$. But it's a theorem in PA that for any number $x$, either $x$ or $S(x)$ can be expressed as $y+y$, so we have a contradiction.

This establishes the "or" part, and Ashutosh's comment shows that it's not just or but xor.

I think this also leads to the fact that a model of MA is always isomorphic to a model of PA modulo one of its elements. Since nonstandard models of arithmetic are pretty thoroughly studied, I think that this also characterizes the possible nonstandard models of MA.

Answer by Russell Easterly for Even XOR Odd Infinities?

2013-01-22T07:12:33Z

This is too long for a comment so I am posting it as an answer.

Ashutosh's proof can be written as:

$\exists x\exists y( (x+x=0 \land y+y=1) \implies (x=0) )$

This answers my question when $\exists x(x+x=1)$ is true but it says nothing about when $\forall x(x+x \ne 1)$ is true. Emil and others have stated any algebraically closed field is a model of MA. Ashutosh's proof shows any algebraically closed field is odd because $\exists x(x+x=1)$ is true.

I want to accept Ben Crowell answer, but I have some reservations. The proof starts by showing how any model of MA can be expanded into a model of PA. I have made similar arguments and always assumed it would be easy to prove. My conjecture is true of all finite models of MA so we only need consider infinite models. MA is omega inconsistent and any infinite model must have non-standard elements. Tennebaum's theorem says addition is not recursive in non-standard models of PA. Can addition actually be recursive in $A$, the model of PA he constructs? It looks like he is assuming we can add non-standard numbers from the model of MA. I also wonder if he is assuming $I$ is a standard model of PA. I don't think it makes any difference, but it might.

Obo's proof is much simpler and similar to a proof I came up with. My proof had the same error as his. I think it is fixable. In the case where we have $S(y+y)=p$ we need to also prove $y \ne p$. $y \ne p$ can be true only in models with three or more elements.

This isn't a discussion group so I won't go into detail why I don't think the complex numbers are a model of MA. I don't think MA has any infinite models. I will point out MA proves a lot of interesting things about odd models. In an odd model the sum of all elements is 0. This can't be stated in first order. I think if we have a successor function defined on the complex numbers we can use it to order the reals. Just ignore numbers with a non-zero imaginary component.

I want to retract my statement that the Lagrange's four square theorem is a theorem of MA. I based my claim on Andrew Boucher's paper on General Arithmetic (GA). Boucher shows GA proves the four square theorem. I thought GA was a weak sub-theory of MA because GA has much weaker successor axioms. Rereading the paper I see Boucher says he is using 2nd order induction. He also says successor is second order.

Does MathOverflow have a discussion site?

Answer by Emil Jeřábek for Even XOR Odd Infinities?

2013-01-23T14:17:19Z

The answer is no. It is enough to find a model of MA which is an integral domain of characteristic $0$ (whence O1 is true and E1 false) such that $2$ is not invertible (whence E2 is true and O2 false).

One example of such a model is the ring of $2$-adic integers $\mathbb Z_2$. This is clearly a domain, and $2$ is not a unit, hence it suffices to show

Theorem: For any prime $p$, the ring $\mathbb Z_p$ is a model of MA.

Proof: The only problem is to verify that induction holds. Assume $\mathbb Z_p\models\phi(0)\land\forall x\,(\phi(x)\to\phi(x+1))$, where $\phi$ is an arithmetic formula with parameters from $\mathbb Z_p$, and put $\phi(\mathbb Z_p):=\{a\in\mathbb Z_p:\mathbb Z_p\models\phi(a)\}$.

Since $\phi(\mathbb Z_p)$ is definable in $\mathbb Z_p$, it is also definable in the field $\mathbb Q_p$ endowed with a unary predicate for $\mathbb Z_p$. Macintyre [1] proved that such structures admit a form of quantifier elimination, and as a corollary (Thm. 2 on p. 609), every infinite definable set has a nonempty interior. Thus, there is $a_0\in\phi(\mathbb Z_p)$ and $k\ge0$ such that $a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Let $a\in\mathbb Z_p$ be arbitrary, and let $b< p^k$ be a natural number such that $b\equiv a-a_0\pmod{p^k}$. Since $\phi(\mathbb Z_p)$ is closed under successor, we have $a\in b+a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$. Thus, $\phi(\mathbb Z_p)=\mathbb Z_p$, i.e., $\mathbb Z_p\models\forall x\,\phi(x)$. QED

I suspect the following may work as additional countermodels (they are domains where $2$ is not a unit, the issue is whether they satisfy induction):

The ring of algebraic integers $\tilde{\mathbb Z}$. A form of quantifier elimination for $\tilde{\mathbb Z}$ was proved by van den Dries [2] and Prestel and Schmid [3], but the basic formulas are somewhat messy, so it is not immediately clear to me whether this implies induction.
The localization of $\tilde{\mathbb Z}$ at a maximal ideal containing $2$. Elimination of quantifiers for this (and similar) rings is reported as Fact 3 in [2], where it is attributed to [4]. It seems it could imply induction by a similar argument as for $\mathbb Z_p$.

[1] Angus Macintyre, On definable subsets of $p$-adic fields, Journal of Symbolic Logic 41 (1976), no. 3, pp. 605–610.

[2] Lou van den Dries, Elimination theory for the ring of algebraic integers, Journal für die reine und angewandte Mathematik 388 (1988), pp. 189–205.

[3] A. Prestel and J. Schmid, Existentially closed domains with radical relations, Journal für die reine und angewandte Mathematik 407 (1990), pp. 178–201.

[4] Angus Macintyre, Kenneth McKenna, Lou van den Dries, Elimination of quantifiers in algebraic structures, Advances in Mathematics 47 (1983), no. 1, pp. 74–87.