Modular Arithmetic vs Ring Theory

[RussellE]

I am trying to determine the differences between the
axioms of Ring Theory (RT) and Modular Arithmetic(MA).

Axioms of RT
http://www.aw-bc.com/chartrand/ch14.pdf

1) AxAy(x+y = y+x)
2) AxAyAz((x+y)+z = x+(y+z))
3) Ax(0+x = x)
4) AxEy(x+y = 0)
5) AxAyAz((x*y)*z = x*(y*z))
6a) AxAyAz(x*(y+z) = x*y+x*z)
6b) AxAyAz((x+y)*z) = x*z+y*z)

Axioms of MA without induction

1) Ex (S(x)=0)
2) Ax ((S(x)=S(y)) -> (x=y))
3) Ax (x+0=x)
4) AxAy (x+S(y)=S(x+y))
5) Ax (x*0=0)
6) AxAy (x*S(y)=x*y+x)

Both MA and RT define a constant, 0.
Both have the axiom Ax (x+0=x).
MA defines a successor function
which is not defined in RT.
I can remove the successor function
by defining a new constant, 1.

Ex (x+1=0)
Ax ((x+1)=(y+1) -> x=y)
Ax (x+0=x)
AxAy (x+(y+1)=(x+y)+1)
Ax (x*0=0)
AxAy (x*(y+1)=x*y+x)

Are there axioms for ring theory where 1 is a constant?

I thought Ex(x+1 = 0) would not be an theorem
of RT, but it seems it is easy to derive from the
axiom AxEy(x+y = 0). Let x=1.

Is there any axiom of MA that is not a
theorem of RT?


Russell
- 2 many 2 count

[David Hartley]

In message
<fce562d0-d52d-47dd...@s8g2000pbj.googlegroups.com>,
RussellE <reas...@gmail.com> writes

In general, a ring need not have a 1 (i.e. a multiplicative identity),
nor need multiplication be commutative.

You can of course define the theory of a ring with 1 by adding an
appropriate axiom. Any axiom of MA *without induction* will be a
theorem of that theory.

But induction is what makes MA interesting, and that is certainly not an
axiom (schema) in any general theory of rings. (Although it does seem to
hold in the case of the ring of complex numbers.)
--
David Hartley

[Ken Pledger]

In article
<fce562d0-d52d-47dd...@s8g2000pbj.googlegroups.com>,

RussellE <reas...@gmail.com> wrote:

> I am trying to determine the differences between the
> axioms of Ring Theory (RT) and Modular Arithmetic(MA).

> ....


Think about the field of order 4. It's a perfectly good ring, but
definitely not Z_4 in your "MA".

Ken Pledger.

[William Elliot]

For all x, 1x = x = x1.

[RussellE]

On Jan 22, 2:14 pm, David Hartley <m...@privacy.net> wrote:
> In message
> <fce562d0-d52d-47dd-bcb6-2eca4a3c3...@s8g2000pbj.googlegroups.com>,
> RussellE <reaste...@gmail.com> writes

I am still interested in which axioms of
MA are theorems of RT.
Ax (x+0=x) is the same in both theories.
Can Ax (x*0=0) be derived from RT?

MA defines a successor function which

isn't defined in RT. I defined 1=S0.

What would be a common axiom for defining 1 in RT?
What axiom(s) would limit RT to commutative rings?

> You can of course define the theory of a ring with 1 by adding an
> appropriate axiom.  Any axiom of MA *without induction* will be a
> theorem of that theory.
>
> But induction is what makes MA interesting, and that is certainly not an
> axiom (schema) in any general theory of rings. (Although it does seem to
> hold in the case of the ring of complex numbers.)

I am not sure MA needs induction.
I think induction is useless in finite models of MA.
I guess there could be finite structures that satisfy
the other axioms of MA and fail to satisfy induction.
I can't think of any such finite structures.

It is not even obvious induction is true
in finite structures. It might be possible
there is some sentence provable by induction
that fails in the finite structures we
think are models of MA.

Dave Libert has a form of induction that
doesn't include the predecessor of 0.
I used a similar system to show how it is
possible for a model of arithmetic to prove
Ax(Sx~=0) by induction as long as Ax
doesn't include the predecessor of 0.

A Consistent Theory of Arithmetic
Russell Easterly - May 30 2011
http://groups.google.com/group/sci.math/browse_thread/thread/5607577e869398c8/ec084d5969792c10

[RussellE]

This looks like the only additional axiom I need to
derive all of the axioms of MA from RT.

Ax (x*1 = x)

I am pretty sure PA can prove PA is commutative.
I am not sure which axioms are needed to prove this.
I have been assuming MA can prove MA is
commutative. Now, I am wondering if I need
induction or Ax(Sx~=0) to prove PA
is commutative. It could be the successor
function that makes PA commutative.

In MA, I can define 1 using just successor.
1 = S0
Is there a way to define 1 using only
addition in RT?

>
> > I thought Ex(x+1 = 0) would not be an theorem
> > of RT, but it seems it is easy to derive from the
> > axiom AxEy(x+y = 0). Let x=1.
>
> > Is there any axiom of MA that is not a
> > theorem of RT?

Russell

- Logic needs to be idiot proof

[Ken Pledger]

In article
<ken.pledger-AC4F...@news.eternal-september.org>,

> definitely not Z_4 in your "MA"....


You may be getting into unnecessarily deep water. The essential
issue is that in MA the additive group is cyclic, but in RT any Abelian
group will do. That's not easy to express in first-order language, so
here's a first-order formula which is valid in MA but not in RT (for
example, false in the field GF(4) mentioned above):

(for all x, y, z)((x + x = y + y = z + z) implies (x = y or x = z or
y = z).

Ken Pledger.

[RussellE]

On Jan 23, 12:13 am, RussellE <reaste...@gmail.com> wrote:
> On Jan 22, 7:37 pm, William Elliot <ma...@panix.com> wrote:
>
> I am pretty sure PA can prove PA is commutative.
> I am not sure which axioms are needed to prove this.
> I have been assuming MA can prove MA is
> commutative. Now, I am wondering if I need
> induction or Ax(Sx~=0) to prove PA
> is commutative. It could be the successor
> function that makes PA commutative.

I have looked at severals proofs that
PA is commutative and all of them use
induction. (The ones that don't use
the axioms of RT).

http://www.proofwiki.org/wiki/Natural_Number_Addition_is_Commutative


Russell
- Integers are an illusion

[RussellE]

On Jan 23, 2:43 pm, Ken Pledger <ken.pled...@vuw.ac.nz> wrote:
> In article
> <ken.pledger-AC4F49.11243323012...@news.eternal-september.org>,
>  Ken Pledger <ken.pled...@vuw.ac.nz> wrote:
>
> > In article
> > <fce562d0-d52d-47dd-bcb6-2eca4a3c3...@s8g2000pbj.googlegroups.com>,

> >  RussellE <reaste...@gmail.com> wrote:
>
> > > I am trying to determine the differences between the
> > > axioms of Ring Theory (RT) and Modular Arithmetic(MA).
> > > ....
>
> >    Think about the field of order 4.   It's a perfectly good ring, but
> > definitely not Z_4 in your "MA"....
>
>    You may be getting into unnecessarily deep water.  The essential
> issue is that in MA the additive group is cyclic, but in RT any Abelian
> group will do.  That's not easy to express in first-order language, so
> here's a first-order formula which is valid in MA but not in RT (for
> example, false in the field GF(4) mentioned above):
>
> (for all x, y, z)((x + x = y + y = z + z) implies (x = y  or  x = z  or
> y = z).
>
>       Ken Pledger.

I had to convince myself this statement is true
in the 0-model (trivial ring).

Any theorem of MA must be true in the trivial ring.
I've learned even simple statements can be independent of MA.

Ex(x ~= 0) and Ax(x ~= x+1) are false in the trivial ring.

Ex(x = x+x+1) is a theorem of MA. x = -1

[RussellE]

It looks like I need induction to prove
MA is commutative.

Robinson Arithmetic is PA without induction.
http://en.wikipedia.org/wiki/Robinson_arithmetic
RA can't prove RA is commutative.
RA can't prove x~=Sx
(MA can't either, even with induction.)

Presburger Arithmetic does have induction.
http://en.wikipedia.org/wiki/Presburger_arithmetic
PR does prove PR is commutative.
PR also proves AxEy(x=y+y or x=Sy+y) which is
becoming my favorite theorem of MA (with induction).

> I think induction is useless in finite models of MA.

Originally, I included an Omega Rule in MA:

P(0) and P(S0) and P(SS0) ... -> Ax P(x)

The omega rule works great if you know
there are only a finite number of elements
in the universe. An infinitely long omega
rule causes problems.

The omega rule in MA is inconsistent with
first order induction which means MA is
omega inconsistent.
http://en.wikipedia.org/wiki/%CE%A9-consistent_theory

MA has no infinite models if I replace
first order induction with the omega rule.

I am ranting on about induction because
my primary interest in MA is proving it
has no infinite models.

> I guess there could be finite structures that satisfy
> the other axioms of MA and fail to satisfy induction.
> I can't think of any such finite structures.
>
> It is not even obvious induction is true
> in finite structures. It might be possible
> there is some sentence provable by induction
> that fails in the finite structures we
> think are models of MA.
>
> Dave Libert has a form of induction that
> doesn't include the predecessor of 0.
> I used a similar system to show how it is
> possible for a model of arithmetic to prove
> Ax(Sx~=0) by induction as long as Ax
> doesn't include the predecessor of 0.
>
> A Consistent Theory of Arithmetic

> Russell Easterly - May 30 2011http://groups.google.com/group/sci.math/browse_thread/thread/5607577e...
>
> Russell
> - 2 many 2 count- Hide quoted text -
>
> - Show quoted text -

[RussellE]

On Jan 22, 7:37 pm, William Elliot <ma...@panix.com> wrote:

> On Sun, 22 Jan 2012, RussellE wrote:
> > I am trying to determine the differences between the
> > axioms of Ring Theory (RT) and Modular Arithmetic(MA).
>
> > Axioms of RT
> >http://www.aw-bc.com/chartrand/ch14.pdf
>
> > 1) AxAy(x+y = y+x)
> > 2) AxAyAz((x+y)+z = x+(y+z))
> > 3) Ax(0+x = x)
> > 4) AxEy(x+y = 0)
> > 5) AxAyAz((x*y)*z = x*(y*z))
> > 6a) AxAyAz(x*(y+z) = x*y+x*z)
> > 6b) AxAyAz((x+y)*z) = x*z+y*z)
>

> For all x, 1x = x = x1.

7a) Ax(x*1=x)
7b) Ax(1*x=x)

Adding these axioms gives me
commutative rings with unity.
Not all commutative rings with unity
are models of MA. What additional
axioms would I need to add to RT
to get only models of MA?

Do I have to add an induction axiom,
or is there something less than
induction that will do?