Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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


[The following was merged from an answer - ed.]

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.

share|improve this question
14  
If $x + x = 0$ and $y + y = 1$, then $x = x(y + y) = xy + xy = (x + x)y = 0$. –  Ashutosh Jan 20 '13 at 3:06
2  
Ashutosh, you should post that as an answer. –  Dan Petersen Jan 20 '13 at 9:54
5  
Dan, that's only the easy half of the answer, which Russell probably already knew. E1 says that 2 is a null divisor and O2 says that 2 is a unit, you can't have both but must you have one or the other? –  François G. Dorais Jan 20 '13 at 14:28
2  
@Russell Easterly: "I would be happy if someone comes up with an even infinite set." Fix an even hyperinteger $n$. Then the hyperintegers modulo $n$ are an infinite model. –  Ben Crowell Jan 21 '13 at 0:06
7  
And yes, complex numbers (and every other algebraically closed field of characteristic $0$, for that matter) are a model of MA. The induction schema is valid in $\mathbb C$ because it is a minimal structure: any definable (with parameters) subset of $\mathbb C$ is finite or cofinite. If $\mathbb C\models\phi(0)\land\forall x\,(\phi(x)\to\phi(x+1))$ (where $\phi$ may have parameters not shown), let $X$ be the set defined by $\phi$. By the assumption, $X$ is infinite, hence its complement is finite. Since the complement is closed under subtracting $1$, this can only happen if it is empty. –  Emil Jeřábek Jan 21 '13 at 12:55

3 Answers 3

up vote 17 down vote accepted

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.

share|improve this answer
    
Very nice, Emil! –  François G. Dorais Jan 23 '13 at 14:25
    
Thanks Emil! If induction holds in the 2-adic integers does this mean the four square theorem is true in this model? If so, how would I represent -1 (...111) as four squares? Would this be a model for MA2? –  Russell Easterly Jan 24 '13 at 1:03
2  
Since it is not known whether MA proves the four-square theorem, this does not by itself imply that the f-s t holds in the 2-adics. Nevertheless, the f-s t does hold in $\mathbb Z_2$ (and in every $\mathbb Z_p$; moreover, if $p\equiv1\pmod4$, then $\mathbb Z_p$ satisfies a “two-square theorem”). $-1=2^2+1^2+1^2+(-7)$, and $-7$ has a 2-adic square root by Hensel’s lemma. (In general, a nonzero $a\in\mathbb Z_2$ is a square iff it can be written as $4^kb$, where $b\equiv1\pmod8$; for odd $p$, $a$ is a square iff $a=p^{2k}b$, where the Legendre symbol $\genfrac(){}{}{b\bmod p}p=1$.) –  Emil Jeřábek Jan 24 '13 at 12:49
    
As I already mentioned, the only models of the second-order MA2 are the finite rings $\mathbb Z/n\mathbb Z$: if $M$ is any such model, let $f:\mathbb Z\to M$ be the unique ring homomorphism. Since $f(\mathbb N)$ contains $0$ and is closed under successor, it equals $M$ by induction, hence $f$ is surjective, and its kernel $I$ is nontrivial. Since $\mathbb Z$ is a PID, $I=n\mathbb Z$ for some $n>0$, and $M\simeq\mathbb Z/I$. –  Emil Jeřábek Jan 24 '13 at 13:00
    
Thanks again Emil. This has been very educational. –  Russell Easterly Jan 24 '13 at 19:11

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.

share|improve this answer
    
Sorry, I was working in 2nd-order PA. –  abo Jan 20 '13 at 21:58
2  
"Then $T$ induces the normal ordering $\lt$ on $A$" - what does that mean? –  François G. Dorais Jan 20 '13 at 22:00
    
In second-order PA, you can consider the ancestral of T, which gives you the normal ordering. The question, however, is confined to first-order PA, so this won't work. –  abo Jan 20 '13 at 22:12
    
OK, I fixed the proof so it works in first-order PA. –  abo Jan 20 '13 at 22:54
3  
The argument still doesn't work because $y=p$ is always a solution to $S(y+y)=p$. –  Eric Wofsey Jan 20 '13 at 23:14

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.

share|improve this answer
1  
How do you define addition in $A$ in general? This seems to be essentially the same difficulty as in abo's argument: you need to somehow be able to detect when a sum in $M$ "wraps around". If you could do that, you could as in abo's argument take the smallest $x$ such that the sum $x+x$ wraps around and conclude that $x+x$ is either $0$ or $1$. In any case, even if you could define addition in $A$, it's not obvious to me that $A$ would satisfy induction. –  Eric Wofsey Jan 21 '13 at 1:15
    
@Eric Wofsey: Thanks for your comments. I've tried to address the comments about verifying induction and defining addition. I'm afraid I don't follow your objection to abo's answer or how it would apply to mine. –  Ben Crowell Jan 21 '13 at 2:15
1  
I think the confusion is that you seem to be thinking about second-order theories rather than first-order theories. Addition and multiplication cannot be defined from $S$ in first-order arithmetic. In order to verify induction for $A$ as you argue, you need to know (for instance) that for any $i\in I$, the set of $m$ such that $(i,m)\in K$ is first-order definable in $M$. –  Eric Wofsey Jan 21 '13 at 2:32
    
I became interested in MA as a tool to prove PA is inconsistent. If my conjecture is provable I think I can show MA proves PA is inconsistent. I would show every possible subset must be even or odd and can't be a model of PA. Then I would have a consistent theory that proves PA is inconsistent. Just showing MA has recursive infinite models is problematic because of Tennenbaum's theorem. –  Russell Easterly Jan 21 '13 at 3:23
3  
I have no idea what you mean by saying “MA proves PA is inconsistent”, as MA lacks the expressive power to meaningfully express properties like formal provability and consistency. In any case, MA has recursive infinite models, such as the field of all algebraic numbers. –  Emil Jeřábek Jan 21 '13 at 14:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.