User russell easterly - MathOverflow

Why Does Induction Prove Multiplication is Commutative?

2013-02-17T03:48:45Z

Andrew Boucher's General Arithmetic (GA2) is a weak sub-theory of second order Peano Axioms (PA2). GA has second order induction and a single successor axiom:

$$\forall x \forall y \forall z\bigr((Sx=y \land Sx=z)\to(y=z)\bigl)$$

Boucher proves multiplication is commutative in GA2. Why does induction prove multiplication is commutative? GA2 has many finite models. The rings $\mathbb Z/n\mathbb Z$ are models. If we remove induction from GA2 it is easy to see GA-Ind is sub-theory of Ring Theory (RT). RT has finite non-commutative models. Why aren't these finite non-commutative rings models of GA? Would a first order version of GA also prove multiplication is commutative?

I asked on stack exchange and got no answer. http://math.stackexchange.com/questions/287557

Edit: I am not looking for an inductive proof. This is a standard result and I am sure it can be done. I am more interested in something like abo's explanation. Can we prove induction fails in every non-commutative ring? Is it impossible to define a successor chain that visits every ring element using addition in a non-commutative ring?

Definitions for Oddness

2013-02-13T06:51:53Z

In the thread Even Xor Odd Infinities I defined odd models of Modular Arithmetic (MA) as models satisfying the axioms of MA and two first order statements. http://mathoverflow.net/questions/119375

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

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

MA has the same axioms as first order Peano Arithmetic (PA) except $\forall x(Sx \ne 0)$ is replaced with $\exists x(Sx=0)$.

Ashutosh proved $O2 \to O1$. Assume $x+x=0$ and $y+y=1$.

$x=x(y+y)=xy+xy=(x+x)y=0$.

Ashutosh's proof doesn't use induction or the axiom $\exists x(Sx=0)$. This means it works even in theories weaker than PA and MA. Emil Jerabek proved $O1$ does not imply $O2$ in MA by proving the 2-adic numbers are a counter example.

The standard models of MA are the rings $Z/nZ$. Any infinite model of MA must be non-standard. Several people have stated any algebraically closed field is a model of MA. If so, Ashutosh's proof shows algebraically closed fields are odd models of MA. The complex numbers satisfy every definition for odd I have been able to come up with. This seems to suggest there are an odd number of complex numbers.

I am looking for first order arithmetic statements true in rings $Z/nZ$ if and only if n is odd. Showing how the statement implies or is implied by other definitions of odd would be an added bonus. Finding a statement independent of others would be interesting. Finding a definition of oddness that is not true in the complex numbers would be even more interesting. Some examples:

$O3) \exists x(x+Sx=0)$

$O4) \forall x \exists y(x=y+y)$

$O5) \forall x \forall y(x=0 \lor y=0 \lor Sx \ne 0 \lor x*y \ne y)$

$O5$ is a complicated way of saying $\forall x(-x \ne x)$

All of these statements are independent of the axioms of MA and require the axiom $\forall x(Sx \ne 0)$ to prove (or disprove) in PA.

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 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 Russell Easterly for Does there exist a non-trivial Ultrafinitist set theory?

2012-09-25T07:40:44Z

I have been studying a theory I call Modular Arithmetic (MA). MA has the same axioms as first order Peano Arithmetic (PA) except Ax( ~S(x)=0 ) is replaced with Ex( S(x)=0 ). MA is consistent because it has arbitrarily large finite models base on modular arithmetic. The upward Löwenheim–Skolem theorem proves MA must have infinite models. MA can be made into an ultra-finite theory by adding an axiom like Ax( x=0 or x=S(0) or ... or x=Sn(0) ) where Sn(0) is some finite number of applications of successor to 0 (a numeral).

Coming up with a set theory based on MA is problematic. It is simple to show MA is omega inconsistent. The predecessor of 0 must be non-standard (not a numeral) in any infinite model of MA. If the predecessor of 0 is standard we can prove the model is finite using induction. This means Ax( ~S(x)=0 ) is true for all standard natural numbers in any infinite model. A set theory based on MA can't be well ordered or well founded, either. (x =< y) <-> Ez( x+z=y ) is trivially true for any x and y. Using S(x) = x U {x} as a definition of successor is inconsistent with the axioms of MA.

In ZF, even the Axiom of Pairing allows the construction of arbitrarily large sets. Assuming we could come up with a set theory for MA, it would have the properties you ask for. One way to do this would be to encode sets as binary expansions of natural numbers. Element x is a member of the set if the x'th bit of the expansion is true. This would allow us to have sets of size log2(n) where n is the size of the universe. We can equate 0 with the empty set. We can define singleton sets for "small" elements of the universe. We could also define sets with subsets. We could do a reasonable amount of arithmetic by choosing n large enough. We could have sets and do math on sets as large as 100 by having a universe of size 2^100.

Comment by Russell Easterly

2013-02-20T03:07:56Z

You are right. I am slow. And you are right these are not terribly interesting. We don't really get any new classes. We just can't assume all the statements in a given class are equivalent.

Comment by Russell Easterly

2013-02-20T02:19:49Z

$\forall x(Sx=x+S0)$ is a theorem of PA and weaker theories. I don't know if it is a theorem of GA2. I am interested in theories of arithmetic where induction fails. It looks like finite non-commutative rings are models of ring theory + Not(Ind) + $\forall x(Sx=x+1)$.

Comment by Russell Easterly

2013-02-19T04:07:55Z

Matrix addition and multiplication satisfy all of the axioms of Ring Theory (RT). Non-commutative rings are not models of RT+Ind where Ind is first order induction. Abo gives an example of a phi(x) we can prove using induction that is false in matrix arithmetic.

Comment by Russell Easterly

2013-02-18T09:20:35Z

This still satisfies the successor axiom. An element doesn't even have to have a successor in GA2.

Comment by Russell Easterly

2013-02-18T05:25:05Z

I think GA2 is strong enough to prove if x has a successor then $Sx = x+S0$. I know ring theory proves this. Once we call some element 0 and some element 1 we have no choice on how successor is defined. I know nothing about non-commutative rings, but I assume they satisfy GA2's very weak successor axiom using matrix addition.

Comment by Russell Easterly

2013-02-15T01:51:21Z

$O2 \land ( \forall x \exists y(y^2=x) \to 0=2)$ is false in PA yet is not equivalent to O2, O3, and O4. Doesn't this prove there must be more than two classes of definitions for oddness? I think a conjunction with any statement true in all finite models works.

Comment by Russell Easterly

2013-02-14T17:46:47Z

Thanks. So, all of the statements false in PA are equivalent and all the statements true in PA are equivalent. I am still curious if there are definitions of odd that aren't equivalent to one of these two classes. If not, then the complex numbers satisfy every definition of odd.

Comment by Russell Easterly

2013-01-26T23:29:35Z

I am not sure one can talk about lines and circles in an ultrafinite theory. The set of points equidistant from some point (using some measure) will always be a finite set. I have studied graphs where the number of points equidistant from the origin oscillates between 3*r and 4*r depending on the radius. It is easy to come up with graphs where the average ratio of equidistant points to radius approaches Pi for large r.

Comment by Russell Easterly

2013-01-24T19:11:54Z

Thanks again Emil. This has been very educational.

Comment by Russell Easterly

2013-01-24T01:03:28Z

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?

Comment by Russell Easterly

2013-01-21T03:23:44Z

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.

Comment by Russell Easterly

2013-01-21T01:22:52Z

I use to think so, too. I think we need successor to justify induction. For example, I don't think the complex numbers are a model of MA because it is impossible to define a consistent successor function. Just adding 1 to 0 will never reach a pure complex number like i.

Comment by Russell Easterly

2013-01-21T01:02:39Z

I ran into this problem, too. Most of my attempts start by assuming -1 is not 0 (I exclude the trivial ring).

Comment by Russell Easterly

2013-01-20T23:09:20Z

The main differences between MA and commutative ring theory are successor and induction. If my statement can be proven without induction I think it applies to all commutative rings. That would mean the integers are not a commutative ring.

Comment by Russell Easterly

2013-01-20T20:57:39Z

The smallest model of MA is the trivial ring which satisfies Ashutosh's formula. Let x,y=0. 0=1 is true in this model. We need to include the requirement that x is not 0. I would be happy if someone comes up with an even infinite set.