Even and Odd Infinities

[RussellE]

Modular Arithmetic (MA) has the same axioms as
first order Peano Arithmetic (PA) except Ax(S(x)~=0)
is replaced with Ex(S(x)=0).

If ZFC is consistent then MA has an infinite model.

MA has models with finite universal sets and these
universal sets can have an even or odd number
of elements. This means MA must have infinite
models where the universe is even and infinite
models where the universe is odd.

It is easy to come up with first order statements
that are true in odd sized models of MA and false
in even sized models.

AxEy(x=y+y) is true in odd sized models of MA.

For example, let the universal set be {0,1,2,3,4}.

0 = 0+0
1 = 3+3
2 = 1+1
3 = 4+4
4 = 2+2

Notice that every natural number is a multiple
of two in an odd sized model of MA.

Negating the expression above:
ExAy(x~=y+y) is true in even sized models of MA.
This statement is also true in all models of PA.

Another example:

Ex(x~=0 and x+x=0) is true in even models of MA.
Ax(x=0 or x+x~=0) is true in odd models of MA and
all models of PA.

I find it interesting that AxEy(x=y+y) is
independent of the axioms of MA, but is
provably false in PA. I assume we can
prove ExAy(x~=y+y) from the axioms of PA.

MA thinks any model of PA must have a
universe with both an even and odd number
of elements. MA proves PA is inconsistent.


Russell
- Integers are an illusion

[MoeBlee]

On Dec 28, 12:04 am, RussellE <reaste...@gmail.com> wrote:

> MA must have infinite
> models where the universe is even and infinite
> models where the universe is odd.

In set theory:

x is even <-> (x is a natural number & Ey(y is a natural number &
x=2*y))

x is odd <-> (x is a natural number & ~Ey(y is a natural number &
x=2*y))

So in what sense are you claiming x is even or x is odd when x is not
a natural number and moreover x is infinite?

MoeBlee

[Rupert]

On Dec 28, 7:04 am, RussellE <reaste...@gmail.com> wrote:
> Modular Arithmetic (MA) has the same axioms as
> first order Peano Arithmetic (PA) except Ax(S(x)~=0)
> is replaced with Ex(S(x)=0).
>
> If ZFC is consistent then MA has an infinite model.
>

What's the model?

[Uergil]

In article
<8bc60df3-84ab-4f74...@l16g2000prg.googlegroups.com>,

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

> Modular Arithmetic (MA) has the same axioms as
> first order Peano Arithmetic (PA) except Ax(S(x)~=0)
> is replaced with Ex(S(x)=0).
>
> If ZFC is consistent then MA has an infinite model.

Not proven!

>
> MA has models with finite universal sets and these
> universal sets can have an even or odd number
> of elements. This means MA must have infinite
> models where the universe is even and infinite
> models where the universe is odd.

Not proven!


And until those two claims are both proved the rest is silence.
--
"Ignorance is preferable to error, and he is less
remote from the- truth who believes nothing than
he who believes what is wrong.
Thomas Jefferson

[RussellE]

On Dec 28, 12:31 pm, Uergil <Uer...@uer.net> wrote:
> In article
> <8bc60df3-84ab-4f74-b7a7-0827abcd8...@l16g2000prg.googlegroups.com>,

>
>  RussellE <reaste...@gmail.com> wrote:
> > Modular Arithmetic (MA) has the same axioms as
> > first order Peano Arithmetic (PA) except Ax(S(x)~=0)
> > is replaced with Ex(S(x)=0).
>
> > If ZFC is consistent then MA has an infinite model.
>
> Not proven!
>

MA has arbitrarily large finite models.
Compactness and Löwenheim–Skolem are theorems of ZFC.
http://en.wikipedia.org/wiki/Compactness_theorem
Any first order theory with arbitrarily large finite models
has an infinite model.

>
> > MA has models with finite universal sets and these
> > universal sets can have an even or odd number
> > of elements. This means MA must have infinite
> > models where the universe is even and infinite
> > models where the universe is odd.
>
> Not proven!

MA has arbitrarily large finite models where the
universe has an odd number of elements.
It also has arbitrarily large finite models where
the universe is even.

Given the axioms of MA and adding the axiom
AxEy (x=y+y), I can show this theory has arbitrarily
large finite models. By compactness, there exists
an infinite model that satisfies the axioms of MA
and AxEy (x=y+y).


Russell
- 2 many 2 count

[quasi]

On Wed, 28 Dec 2011 14:31:06 -0800 (PST), RussellE
<reas...@gmail.com> wrote:

>MA has arbitrarily large finite models.
>Compactness and Löwenheim–Skolem are theorems of ZFC.
>http://en.wikipedia.org/wiki/Compactness_theorem
>Any first order theory with arbitrarily large finite models
>has an infinite model.

How is MA a first order theory?

Can you give the axiomatization?

quasi

[RussellE]

I define the universe of a model of MA to be odd
if it satisfies AxEy(x=y+y) and I define the universe
of a model of MA to be even if it satisfies
Ex(x~=0 and x+x=0).

Both AxEy(x=y+y) and Ex(x~=0 and x+x=0) are
independent of the other axioms of MA.
I am curious if these statements are independent
of the axioms of PA.

[RussellE]

I don't think MA has an infinite model.
Of course, I also think ZFC is inconsistent.

If MA does have an infinite model we know such
a model must be non-standard, probably can't
be well ordered or well founded, may not have
any primes, and addition in the model has to be
non-recursive.

Modular Arithmetic is Consistent
http://groups.google.com/group/sci.logic/browse_thread/thread/cc493bc66033c9f/77a8b95554b551fd

Modular Arithmetic is Uncomputable
http://groups.google.com/group/sci.math/browse_thread/thread/d2ff42472483aaf2/ad87fde7e81de052

Modular Arithmetic Can't be Well Founded
http://groups.google.com/group/sci.logic/browse_thread/thread/d9af05319afa7dc5/f89ebb3be8ed88ed


Russell
- Zeno was right. Motion is impossible.

[RussellE]

On Dec 28, 2:57 pm, quasi <qu...@null.set> wrote:
> On Wed, 28 Dec 2011 14:31:06 -0800 (PST), RussellE
>

> <reaste...@gmail.com> wrote:
> >MA has arbitrarily large finite models.
> >Compactness and Löwenheim–Skolem are theorems of ZFC.
> >http://en.wikipedia.org/wiki/Compactness_theorem
> >Any first order theory with arbitrarily large finite models
> >has an infinite model.
>
> How is MA a first order theory?
>
> Can you give the axiomatization?

These are the axioms of MA:

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

MA also has the first order induction schema:
http://en.wikipedia.org/wiki/Peano_axioms#First-order_theory_of_arithmetic


Russell
- Never never means never in set theory.

[FredJeffries]

Aren't they both false in PA?

[FredJeffries]

On Dec 28, 2:47 pm, RussellE <reaste...@gmail.com> wrote:
> On Dec 28, 12:12 am, Rupert <rupertmccal...@yahoo.com> wrote:
>
> > On Dec 28, 7:04 am, RussellE <reaste...@gmail.com> wrote:
>
> > > Modular Arithmetic (MA) has the same axioms as
> > > first order Peano Arithmetic (PA) except Ax(S(x)~=0)
> > > is replaced with Ex(S(x)=0).
>
> > > If ZFC is consistent then MA has an infinite model.
>
> > What's the model?
>

Let H be a nonstandard natural number. The "cyclic group of order H"
is a model.

[Tim Little]

On 2011-12-28, quasi <qu...@null.set> wrote:
> How is MA a first order theory?
>
> Can you give the axiomatization?

From two posts ago: 1st-order PA with one axiom replaced. Granted
there is some slight ambiguity about *exactly which* version of
1st-order PA to use, but I'd say it's clear enough.


--
Tim

[quasi]

But quoting from Wikipedia:

"In mathematical logic, the compactness theorem states that a
set of first-order sentences has a model if and only if every
finite subset of it has a model. This theorem is an important
tool in model theory, as it provides a useful method for
constructing models of any set of sentences that is finitely
consistent."

It's not clear to me that the above implies what you
claimed, as quoted below:

"A first order theory with arbitrarily large finite models
has an infinite model."

Can you explain your claim?

quasi

[Tim Little]

On 2011-12-28, RussellE <reas...@gmail.com> wrote:
> I define the universe of a model of MA to be odd if it satisfies
> AxEy(x=y+y) and I define the universe of a model of MA to be even if
> it satisfies Ex(x~=0 and x+x=0).

Can a model satisfy both?

In any model of PA, neither holds. Is there a model of MA in which
neither holds?


--
Tim

[Tim Little]

On 2011-12-29, quasi <qu...@null.set> wrote:
> But quoting from Wikipedia:
>
> "In mathematical logic, the compactness theorem states that a
> set of first-order sentences has a model if and only if every
> finite subset of it has a model. This theorem is an important
> tool in model theory, as it provides a useful method for
> constructing models of any set of sentences that is finitely
> consistent."
>
> It's not clear to me that the above implies what you
> claimed, as quoted below:
>
> "A first order theory with arbitrarily large finite models
> has an infinite model."

Further on the same page:

"A second application of the compactness theorem shows that any
theory that has arbitrarily large finite models, or a single
infinite model, has models of arbitrary large cardinality (this is
the Upward Löwenheim–Skolem theorem)"


--
Tim

[RussellE]

Does a countably infinite "even" model of MA have the
same cardinality as a countably infinite "odd" model of MA?
If so, wouldn't this mean there exists a bijection between
an even number and an odd number?

[RussellE]

On Dec 28, 5:16 pm, Tim Little <t...@little-possums.net> wrote:

> On 2011-12-28, RussellE <reaste...@gmail.com> wrote:
>
> > I define the universe of a model of MA to be odd if it satisfies
> > AxEy(x=y+y) and I define the universe of a model of MA to be even if
> > it satisfies Ex(x~=0 and x+x=0).
>
> Can a model satisfy both?

I don't think so.
I think I can use the pigeonhole principle
to show if there is more than one x
such that x+x=0 (0+0=0 is a theorem
of both MA and PA), then AxEy(x=y+y)
must be false.

I can come up with tautologies that must
be true in any model of MA or PA:

AxEy(x=y+y) or ExAy(x~=y+y)

Ex(x~=0 and x+x=0) or Ax(x=0 or x+x~=0)

> In any model of PA, neither holds.

Is this actually provable from the axioms
of first order PA?

>  Is there a model of MA in which
> neither holds?

Again, I don't think so.
I think the pigeonhole principle proves:

AxEy(x=y+y) -> Ax(x=0 or x+x~=0)


Russell
- The universe is one dimensional

[MoeBlee]

On Dec 28, 5:01 pm, RussellE <reaste...@gmail.com> wrote:

> I define the universe of a model of MA to be odd
> if it satisfies AxEy(x=y+y) and I define the universe
> of a model of MA to be even if it satisfies
> Ex(x~=0 and x+x=0).

Okay, that's a clear definition.

> Both AxEy(x=y+y) and Ex(x~=0 and x+x=0) are
> independent of the other axioms of MA.

Below are some of the assertions you made for which I'd lie to see
proof (and if you use anyting other than ZF for your proof, please
state what additional axioms or alernative logic system you are
using):

(1) If ZFC is consistent then MA has an infinite model. [Note: For
purpose of discussion we might as well take "ZFC is consistent" as a
working assumption so that we don't have to mention it each time. That
does not deny you the prerogative to doubt or dispute (for whatever
your reasons) that ZFC is consistent; rather, we're just using "ZFC is
consistent" as a tacitly understood antecedent for the whole
conversatin.]

(2) MA has finite models of both even and odd cardinality.

(3) MA has an infinite odd model. [Note that MA has an infinite model
does not follow from (2) since (2) does not say that MA has models of
arbitrarily large finite cardinality.]

(4) MA has an infinite even model. [Note that MA has an infinite model
does not follow from (2) since (2) does not say that MA has models of
arbitrarily large finite cardinality.]

(5) AxEy(x=y+y) is independent of MA.

(6) Ex(x~=0 and x+x=0) is independent of MA.

If those have been proven elsewhere or the proofs are obvious, please
excuse me as I merely trying to quickly and in one place get your
claims lined up here.

> I am curious if these statements ["AxEy(x=y+y)" and "Ex(x~=0 and x+x=0)"] are independent
> of the axioms of PA.

They're not, since PA proves the negation of both of them.

That's so obvious that I wonder whether you're even thinking about
what you're typing.

MoeBlee

[RussellE]

On Dec 28, 7:14 pm, MoeBlee <modem...@gmail.com> wrote:
> On Dec 28, 5:01 pm, RussellE <reaste...@gmail.com> wrote:
>
> > I define the universe of a model of MA to be odd
> > if it satisfies AxEy(x=y+y) and I define the universe
> > of a model of MA to be even if it satisfies
> > Ex(x~=0 and x+x=0).
>
> Okay, that's a clear definition.
>
> > Both AxEy(x=y+y) and Ex(x~=0 and x+x=0) are
> > independent of the other axioms of MA.
>
> Below are some of the assertions you made for which I'd lie to see
> proof (and if you use anyting other than ZF for your proof, please
> state what additional axioms or alernative logic system you are
> using):
>
> (1) If ZFC is consistent then MA has an infinite model. [Note: For
> purpose of discussion we might as well take "ZFC is consistent" as a
> working assumption so that we don't have to mention it each time. That
> does not deny you the prerogative to doubt or dispute (for whatever
> your reasons) that ZFC is consistent; rather, we're just using "ZFC is
> consistent" as a tacitly understood antecedent for the whole
> conversatin.]

I can't say I have actually seen the Compactness theorem
proven in ZFC, but, I assume it is possible.
If so, we can prove MA has an infinite model
using the compactness theorem.

> (2) MA has finite models of both even and odd cardinality.

Odd sized model:
U = {0}
S(0)=0
0+0=0
0*0=0

Even sized model:
U = {0,1}
S(0)=1, S(1)=0
0+0=0, 0+1=1, 1+0=1, 1+1=0
0*0=0, 0*1=0, 1*0=0, 1*1=1

> (3) MA has an infinite odd model. [Note that MA has an infinite model
> does not follow from (2) since (2) does not say that MA has models of
> arbitrarily large finite cardinality.]

Let MA-Odd have the same axioms as MA
and add AxEy(x=y+y) as an axiom.
There are arbitrarily large finite models of
MA-Odd. All of these finite models have
an odd number of elements in their
universe. By compactness, there is
an inifinite model of MA-Odd.

> (4) MA has an infinite even model. [Note that MA has an infinite model
> does not follow from (2) since (2) does not say that MA has models of
> arbitrarily large finite cardinality.]

Define MA-Even as MA with the axiom
Ex(x~=0 and x+x=0)

> (5) AxEy(x=y+y) is independent of MA.

There are finite models where the statement
is true and finite models where it is false.

> (6) Ex(x~=0 and x+x=0) is independent of MA.

Ditto

> If those have been proven elsewhere or the proofs are obvious, please
> excuse me as I merely trying to quickly and in one place get your
> claims lined up here.
>
> > I am curious if these statements ["AxEy(x=y+y)" and "Ex(x~=0 and x+x=0)"] are independent
> > of the axioms of PA.
>
> They're not, since PA proves the negation of both of them.
>
> That's so obvious that I wonder whether you're even thinking about
> what you're typing.

I am just curious how a statement can be independent
of the axioms of MA yet be false in the axioms of PA.
This means Ax(S(x)~=0) has to be used to prove
these statements are false.

[Tim Little]

On 2011-12-29, MoeBlee <mode...@gmail.com> wrote:
> Below are some of the assertions you made for which I'd lie to see
> proof (and if you use anyting other than ZF for your proof, please
> state what additional axioms or alernative logic system you are
> using):
>
> (1) If ZFC is consistent then MA has an infinite model.

A weaker system than ZFC will suffice; it just requires the upward
Lowenheim-Skolem theorem and (2).

> (2) MA has finite models of both even and odd cardinality.

For every positive integer n, Z_n (with the natural interpretations)
is a model for MA.

> (3) MA has an infinite odd model.

Follows from uLS and (2).

> (4) MA has an infinite even model.

As with (3).

> (5) AxEy(x=y+y) is independent of MA.

Per (2), there exist models of MA that do not satisfy it, and those
that do.

> (6) Ex(x~=0 and x+x=0) is independent of MA.

As with 5.


--
Tim

[David Libert]

MoeBlee (mode...@gmail.com) writes:

> On Dec 28, 5:01=A0pm, RussellE <reaste...@gmail.com> wrote:
>
>> I define the universe of a model of MA to be odd

>> if it satisfies AxEy(x=3Dy+y) and I define the universe

>> of a model of MA to be even if it satisfies

>> Ex(x~=3D0 and x+x=3D0).

>
> Okay, that's a clear definition.
>

>> Both AxEy(x=3Dy+y) and Ex(x~=3D0 and x+x=3D0) are

>> independent of the other axioms of MA.
>
> Below are some of the assertions you made for which I'd lie to see
> proof (and if you use anyting other than ZF for your proof, please
> state what additional axioms or alernative logic system you are
> using):
>
> (1) If ZFC is consistent then MA has an infinite model. [Note: For
> purpose of discussion we might as well take "ZFC is consistent" as a
> working assumption so that we don't have to mention it each time. That
> does not deny you the prerogative to doubt or dispute (for whatever
> your reasons) that ZFC is consistent; rather, we're just using "ZFC is
> consistent" as a tacitly understood antecedent for the whole
> conversatin.]

[1] David Libert "Re: A Contradiction in Terms"
sci.logic, sci.math June 16, 2011
http://groups.google.com/group/sci.logic/msg/9bd08626f435b6a1



[2] David Libert "Re: A Contradiction in Terms"
sci.logic June 16, 2011
http://groups.google.com/group/sci.logic/msg/1eaa9cd91bbe5d6e

> (2) MA has finite models of both even and odd cardinality.

That is, MA has finite models of even cardinality and MA has finite
models of odd cardinality.


[3] David Libert "Re: Modular Arithmetic Is Consistent"
sci.logic, sci.math Jul 14. 2011
http://groups.google.com/group/sci.math/msg/54edc6be1a5f0782


wrote:

> In MA define a number x to be even if E y x = y + y .
>
> MA proves by induction All x x is even or S(x) is even .
>
> It is possible for S(0) to be even: in any Z/n for n odd.
>
> Ie, n is odd in integers, so in integers n+1 is even so there is an integer
> m so n+1 = m+m in integers, so in Z/n, the equivalence class of m
> [m]_n adds to itself to get [n+1]_n = [1]_n.


Note Z/n for any positive integer satisfies MA. This was
discussed in [1].

For k even in integers and n positive if k = m + m i integers
then [k]_n = [m]_n + [m]_n and [k]_n is even in Z/n.

For k odd in integers and n odd positive, by a similar argument to the k = 1
quoted above from [3], [k]_n is also even in Z/n.

So for n positive odd, Z/n satisfies Russell's definition of being
a odd mode.

For n positive even in integers, say n = m + m, [m]_n ~= [0]_n
and [m]_n + [m]_n [00_n, so Z/n satisfies Russell's definition of
being an odd model.

> (3) MA has an infinite odd model. [Note that MA has an infinite model
> does not follow from (2) since (2) does not say that MA has models of
> arbitrarily large finite cardinality.]
>
> (4) MA has an infinite even model. [Note that MA has an infinite model
> does not follow from (2) since (2) does not say that MA has models of
> arbitrarily large finite cardinality.]

(3) and (4) as from [3]. Or just from the last section, getting
arbitrarily large finite models of each type.



> (5) AxEy(x=3Dy+y) is independent of MA.
>
> (6) Ex(x~=3D0 and x+x=3D0) is independent of MA.


For (5) and (6), see the further discussion in [3] about even and
odd elements in MA models. That proved either every element is even,
or else every second element is even, and furthermore each of these
cases arises by the answers from (3) and (4).

These show the independence as (5) and (6),

> If those have been proven elsewhere or the proofs are obvious, please
> excuse me as I merely trying to quickly and in one place get your
> claims lined up here.
>

>> I am curious if these statements ["AxEy(x=3Dy+y)" and "Ex(x~=3D0 and x+x=
> =3D0)"] are independent

>> of the axioms of PA.
>
> They're not, since PA proves the negation of both of them.
>
> That's so obvious that I wonder whether you're even thinking about
> what you're typing.
>
> MoeBlee

--
David Libert ah...@FreeNet.Carleton.CA

[David Libert]

David Libert (ah...@FreeNet.Carleton.CA) writes:
> MoeBlee (mode...@gmail.com) writes:


[...]

>> (5) AxEy(x=3Dy+y) is independent of MA.
>>
>> (6) Ex(x~=3D0 and x+x=3D0) is independent of MA.
>
>
> For (5) and (6), see the further discussion in [3] about even and
> odd elements in MA models. That proved either every element is even,
> or else every second element is even, and furthermore each of these
> cases arises by the answers from (3) and (4).
>
> These show the independence as (5) and (6),

After posting I remebered that [3] had never discussed Russell's
property an even model.

So the [3] discussion shows the independence as (5), but not (6).

For (6) just analyse the finite models.



--
David Libert ah...@FreeNet.Carleton.CA
--
David Libert ah...@FreeNet.Carleton.CA

[quasi]

On Wed, 28 Dec 2011 14:47:24 -0800 (PST), RussellE
<reas...@gmail.com> wrote:
>On Dec 28, 12:12 am, Rupert <rupertmccal...@yahoo.com> wrote:
>> On Dec 28, 7:04 am, RussellE <reaste...@gmail.com> wrote:
>>
>> > Modular Arithmetic (MA) has the same axioms as
>> > first order Peano Arithmetic (PA) except Ax(S(x)~=0)
>> > is replaced with Ex(S(x)=0).
>>
>> > If ZFC is consistent then MA has an infinite model.
>>
>> What's the model?
>
>I don't think MA has an infinite model.
>Of course, I also think ZFC is inconsistent.

In thinking through the axiomatization of MA, I kept
wondering about the need for induction.

So here's my question ...

For the theory of MA, is induction actually required?

An answer of no would mean that any theorem of MA which can
be proved using (instances of) induction can also be proved
without it.

quasi

[Rupert]

On Dec 28, 11:47 pm, RussellE <reaste...@gmail.com> wrote:
> On Dec 28, 12:12 am, Rupert <rupertmccal...@yahoo.com> wrote:
>
> > On Dec 28, 7:04 am, RussellE <reaste...@gmail.com> wrote:
>
> > > Modular Arithmetic (MA) has the same axioms as
> > > first order Peano Arithmetic (PA) except Ax(S(x)~=0)
> > > is replaced with Ex(S(x)=0).
>
> > > If ZFC is consistent then MA has an infinite model.
>
> > What's the model?
>
> I don't think MA has an infinite model.
> Of course, I also think ZFC is inconsistent.
>
> If MA does have an infinite model we know such
> a model must be non-standard, probably can't
> be well ordered or well founded, may not have
> any primes, and addition in the model has to be
> non-recursive.
>

> Modular Arithmetic is Consistenthttp://groups.google.com/group/sci.logic/browse_thread/thread/cc493bc...
>
> Modular Arithmetic is Uncomputablehttp://groups.google.com/group/sci.math/browse_thread/thread/d2ff4247...
>
> Modular Arithmetic Can't be Well Foundedhttp://groups.google.com/group/sci.logic/browse_thread/thread/d9af053...

>
> Russell
> - Zeno was right. Motion is impossible.

Okay, so prove on the assumption that ZFC is consistent that MA has an
infinite model.

[quasi]

Let Z denote the set of integers.

Question:

Is Z is a model of MA?

In other words, is there any theorem of MA which is false
in Z? If so, what would be an example of such a theorem?

quasi

[RussellE]

On Dec 28, 9:29 pm, quasi <qu...@null.set> wrote:
> On Wed, 28 Dec 2011 14:47:24 -0800 (PST), RussellE
>

> <reaste...@gmail.com> wrote:
> >On Dec 28, 12:12 am, Rupert <rupertmccal...@yahoo.com> wrote:
> >> On Dec 28, 7:04 am, RussellE <reaste...@gmail.com> wrote:
>
> >> > Modular Arithmetic (MA) has the same axioms as
> >> > first order Peano Arithmetic (PA) except Ax(S(x)~=0)
> >> > is replaced with Ex(S(x)=0).
>
> >> > If ZFC is consistent then MA has an infinite model.
>
> >> What's the model?
>
> >I don't think MA has an infinite model.
> >Of course, I also think ZFC is inconsistent.
>
> In thinking through the axiomatization of MA, I kept
> wondering about the need for induction.
>
> So here's my question ...
>
>    For the theory of MA, is induction actually required?

Only if MA has infinite models.

> An answer of no would mean that any theorem of MA which can
> be proved using (instances of) induction can also be proved
> without it.

This is true in finite models of MA.

[quasi]

On Wed, 28 Dec 2011 23:43:23 -0800 (PST), RussellE
<reas...@gmail.com> wrote:

>On Dec 28, 9:29 pm, quasi <qu...@null.set> wrote:
>> On Wed, 28 Dec 2011 14:47:24 -0800 (PST), RussellE
>>
>> <reaste...@gmail.com> wrote:
>> >On Dec 28, 12:12 am, Rupert <rupertmccal...@yahoo.com> wrote:
>> >> On Dec 28, 7:04 am, RussellE <reaste...@gmail.com> wrote:
>>
>> >> > Modular Arithmetic (MA) has the same axioms as
>> >> > first order Peano Arithmetic (PA) except Ax(S(x)~=0)
>> >> > is replaced with Ex(S(x)=0).
>>
>> >> > If ZFC is consistent then MA has an infinite model.
>>
>> >> What's the model?
>>
>> >I don't think MA has an infinite model.
>> >Of course, I also think ZFC is inconsistent.
>>
>> In thinking through the axiomatization of MA, I kept
>> wondering about the need for induction.
>>
>> So here's my question ...
>>
>>    For the theory of MA, is induction actually required?
>
>Only if MA has infinite models.

I don't see how the existence of an infinite model changes the
_theory_, that is, changes what can be _proved_.

So here's my challenge:

State a theorem of MA which you think _requires_ induction --
that is, can't be proved in MA without it.

>> An answer of no would mean that any theorem of MA which can
>> be proved using (instances of) induction can also be proved
>> without it.
>
>This is true in finite models of MA.

I could be wrong, but as far as I can see, it's true in _all_
models of MA. To convince me otherwise, take up the challenge
I posed above -- find a statement provable in MA for which
the proof can't be done without using induction.

quasi

[MoeBlee]

quasi is asking how you know that the induction schema is independent
of the rest of the axioms of MA. One answer would be a proof of the
independence of the induction schema from the rest of the axioms of
MA.

I don't understand how your responses about models answers the
question.

MoeBlee

[MoeBlee]

Thanks to Messrs. Libert and Little for the notes. I haven't gone
through those details, but for now I'm taking on trust that we have
proved:

(3) MA has an infinite model that satisfies AxEy(x=y+y).

(4) MA has an infinite model that satisfies Ex(~x=0 and x+x=0).

(5) AxEy(x=y+y) is independent of MA.

(6) Ex(~x=0 and x+x=0) is independent of MA.

And am I correct to surmise that those are the pertinent results now
toward whatever Easterly is trying to finally prove?

Easterly says that MA proves that PA is inconsistent.

Does he mean that there is a formula P in the language of MA (= the
language of PA) that encodes "PA is inconsistent" and such that MA |-
P ?

If not, then what exactly does he mean?

Moreover, he writes, "MA thinks any model of PA must have a universe
with both an even and odd number of elements. MA proves PA is
inconsistent."

But "MA thinks" is impressionistic, so the above passage needs to be
formulated as an exact mathematical statement.

Finally, after making precise what he means by "MA proves PA is
inconsistent", Easterly needs to prove it.

Two notes:

Easterly's first post and certain posts by other people would have
been more clear if it were clearly stated first that it has been
proven that MA has arbitrarily large finite models and that that is
the basis for concluding that MA has infinite models.

Tim: As far as I can tell the argument here is by compactness not
upward Lowenheim-Skolem. As you know, upward Lowenheim-Skolem is, in
brief that if a theory has an infinite model then it also has models
in all greater cardinalities; and compactness is, in brief, that if a
theory has arbitrarily large models then it has an infinite models.
And, if I follow the discussion correctly, the conclusion that MA has
an infinite model came from the result that MA has arbitrarily large
finite models. Am I missing something?

MoeBlee

[Tim Little]

On 2011-12-29, MoeBlee <mode...@gmail.com> wrote:

> Tim: As far as I can tell the argument here is by compactness not
> upward Lowenheim-Skolem.

Either/both. The modern formulation of upward Lowenheim-Skolem
typically includes this result (proved via compactness), despite it
being a separate result originally.


--
Tim

[Tim Little]

On 2011-12-29, quasi <qu...@null.set> wrote:

> Let Z denote the set of integers.
>
> Question:
>
> Is Z is a model of MA?

No. The problem is exactly that axiom schema of induction you were
wondering about.

For example, take as a predicate P(n) = "n is a sum of four squares".
One of the instances of the induction schema states:
(P(0) and An(P(n) -> P(n+1))) -> An P(n).

The antecedent is true in Z, since both P(0) is true, and P(n+1) is
true for every n where P(n) is true. But the consequent is false,
since no negative integer is a sum of four squares.


--
Tim

[quasi]

On 29 Dec 2011 11:52:39 GMT, Tim Little <t...@little-possums.net>
wrote:

>On 2011-12-29, quasi <qu...@null.set> wrote:
>>
>> Let Z denote the set of integers.
>>
>> Question:
>>
>> Is Z is a model of MA?
>
>No. The problem is exactly that axiom schema of induction
>you were wondering about.
>
>For example, take as a predicate
>
> P(n) = "n is a sum of four squares".
>
>One of the instances of the induction schema states:
>
> (P(0) and An(P(n) -> P(n+1))) -> An P(n).

I had already considered the sum-of-4-squares statement
as a possible counterexample, but I'm not convinced that
it's provable in MA. I understand that you have the axiom
schema of induction, but as far as I can see, you can't
actually _prove_ the inductive step P(n) -> P(n+1) in MA.

>The antecedent is true in Z, since both P(0) is true,
>and P(n+1) is true for every n where P(n) is true.

No, the fact that in Z, P(n+1) is true for every n where
P(n) is true is not a _proof_ in the theory MA of the
statement P(n) -> P(n+1).

The proof of sum-of-4-squares theorem can be proved in the
theory PA, but that doesn't translate to a proof of the same
theorem in MA.

It's a subtle point, I think.

The proof of the sum-of-4-squares theorem in PA depends,
I'm fairly sure, on the statement

Ax (S(x) != 0)

which is an axiom of PA (but always false in MA).

Thus, what I'm asserting is that the sum-of-4-squares theorem
is _independent_ of the axioms of MA. Of course it's true in
all finite models of MA, but I believe it fails in some (but
not all) infinite models.

In particular if Z is a model of MA, then Z is one of the
infinite models of MA for which the sum-of-4-squares theorem
fails. And for now, as anti-intuitive as it may seem, I
actually believe that Z is a model of MA.

>But the consequent is false,
>since no negative integer is a sum of four squares.

Sure, the consequent is false, but the antecedent is
unprovable in MA, at least that's my contention.

quasi

[Rupert]

Don't worry about it. I can see how to prove in WKL_0 that MA has an
infinite model.

So what do you mean by the domain of discourse of a model of MA having
an "odd" or "even" number of elements if it is infinite? I think
someone already asked you this.

[Frederick Williams]

melba wrote:

> Easterly says that MA proves that PA is inconsistent.
>
> Does he mean that there is a formula P in the language of MA (= the
> language of PA) that encodes "PA is inconsistent" and such that MA |-
> P ?
>
> If not, then what exactly does he mean?

I have pressed him on this point more than once to no avail.

--
When a true genius appears in the world, you may know him by
this sign, that the dunces are all in confederacy against him.
Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting

[Frederick Williams]

quasi wrote:
>
> [...] for now, as anti-intuitive as it may seem, I

> actually believe that Z is a model of MA.

That it is so has been mentioned in other threads on MA.

[Nam Nguyen]

On 29/12/2011 6:39 AM, Frederick Williams wrote:
> quasi wrote:
>>
>> [...] for now, as anti-intuitive as it may seem, I
>> actually believe that Z is a model of MA.
>
> That it is so has been mentioned in other threads on MA.

Which I don't believe that would be the case because there
are properties that are supposed to hold only for non-negative
integers but would be true for all integers by Induction axioms.

--
----------------------------------------------------
There is no remainder in the mathematics of infinity.

NYOGEN SENZAKI
----------------------------------------------------

[quasi]

On Thu, 29 Dec 2011 10:01:11 -0700, Nam Nguyen <namduc...@shaw.ca>
wrote:

>On 29/12/2011 6:39 AM, Frederick Williams wrote:
>> quasi wrote:
>>>
>>> [...] for now, as anti-intuitive as it may seem, I
>>> actually believe that Z is a model of MA.
>>
>> That it is so has been mentioned in other threads on MA.
>
>Which I don't believe that would be the case because there
>are properties that are supposed to hold only for

>non-negativeintegers but would be true for all integers by
>Induction axioms.

Name such a property.

For any such property P, make sure the induction axioms of MA
actually prove P. Thus, it's not sufficient to show that the
statement P(n) -> P(n+1) is true in Z. Rather, you need to
show that the statement P(n) -> P(n+1) can be _proved_ in MA.

Don't confuse truth with provability.

quasi

[Nam Nguyen]

On 29/12/2011 10:36 AM, quasi wrote:
> On Thu, 29 Dec 2011 10:01:11 -0700, Nam Nguyen<namduc...@shaw.ca>
> wrote:
>
>> On 29/12/2011 6:39 AM, Frederick Williams wrote:
>>> quasi wrote:
>>>>
>>>> [...] for now, as anti-intuitive as it may seem, I
>>>> actually believe that Z is a model of MA.
>>>
>>> That it is so has been mentioned in other threads on MA.
>>
>> Which I don't believe that would be the case because there
>> are properties that are supposed to hold only for
>> non-negativeintegers but would be true for all integers by
>> Induction axioms.
>
> Name such a property.

P(x) <-> (0=x \/ 0<x)

>
> For any such property P, make sure the induction axioms of MA
> actually prove P. Thus, it's not sufficient to show that the
> statement P(n) -> P(n+1) is true in Z. Rather, you need to
> show that the statement P(n) -> P(n+1) can be _proved_ in MA.

Note "induction axioms of MA" is really induction axioms of PA",
by your own definition of MA.

>
> Don't confuse truth with provability.

I don't think I do.

[MoeBlee]

On Dec 29, 7:22 am, Rupert <rupertmccal...@yahoo.com> wrote:
> what do you [RussellE] mean by the domain of discourse of a model of MA having

> an "odd" or "even" number of elements if it is infinite?

He wrote, "I define the universe of a model of MA to be odd if it
satisfies AxEy(x=y+y) and I define the universe of a model of MA to be
even if it satisfies Ex(x~=0 and x+x=0)."

So when he says, "MA must have infinite models where the universe is
even and infinite models where the universe is odd," t take that to
mean:

3) MA has an infinite model that satisfies AxEy(x=y+y).

and

(4) MA has an infinite model that satisfies Ex(~x=0 and x+x=0).

MoeBlee











I think
> someone already asked you this.- Hide quoted text -
>
> - Show quoted text -

[MoeBlee]

On Dec 29, 5:13 am, Tim Little <t...@little-possums.net> wrote:
> The modern formulation of upward Lowenheim-Skolem
> typically includes this result (proved via compactness), despite it
> being a separate result originally.

I don't recall having seen that in the books I've happened to come
across, as indeed I find that authors like to list Big Three as
separate statements: Lowenheim-Skolem, compactness, and completness.

But okay with me if that's what you meant.

MoeBlee

[MoeBlee]

On Dec 29, 7:35 am, Frederick Williams <freddywilli...@btinternet.com>
wrote:
> melba wrote:

"melba"? Where did that come from?

> > Easterly says that MA proves that PA is inconsistent.
>
> > Does he mean that there is a formula P in the language of MA (= the
> > language of PA) that encodes "PA is inconsistent" and such that MA |-
> > P ?
>
> > If not, then what exactly does he mean?
>
> I have pressed him on this point more than once to no avail.

Then we should press him more.

MoeBlee

[Rupert]

Okay, well I agree with that, that can be proved in WKL_0. Now I want
to see a proof for his assertion that "MA proves PA is inconsistent".

[David Libert]

MoeBlee (mode...@gmail.com) writes:
> On Dec 29, 7:35=A0am, Frederick Williams <freddywilli...@btinternet.com>

> wrote:
>> melba wrote:
>
> "melba"? Where did that come from?
>
>> > Easterly says that MA proves that PA is inconsistent.
>>

>> > Does he mean that there is a formula P in the language of MA (=3D the

>> > language of PA) that encodes "PA is inconsistent" and such that MA |-
>> > P ?
>>
>> > If not, then what exactly does he mean?
>>
>> I have pressed him on this point more than once to no avail.
>
> Then we should press him more.
>
> MoeBlee

I had posted about what the statement con(PA) could be in MA,
namely just the usual arithmetization into PA:

[1] David Libert "Re: Modular Arithmetic Is Consistent"
sci.logic July 11, 2011
http://groups.google.com/group/sci.logic/msg/46be504b4c260751


I had various posts discussing that, but in the end retracted them.
My retraction below explicitly referenced [1]:


[2] David Libert "Re: Modular Arithmetic is Uncomputable"
sci.logic, sci.math Sep 27, 2011
http://groups.google.com/group/sci.logic/msg/376f1f35a0996018


The retraction was for the claimed results. The reading of what
con(PA) is from [1] can still stand.



--
David Libert ah...@FreeNet.Carleton.CA

[David Libert]

We want to show Z is not a model of MA. To do this we want to show
an instance of the induction schamtum fails in Z, ie the sentence in
question is false in the model Z.

To check the truth value of that implication in model Z, we check
the truth of the antecedent and tjhe consequent.

Not MA provabliltiy of the antecent. Truth in model Z.

Lagrange's theorem about 4 squares is true in model Z. So the
antecedent evaluates as true in model Z, by model theoretic truth.

So the overall implication evaluates as false in model Z.

Which is exactly what is needed to show a structure Z negates an
axiom from a theory MA.



--
David Libert ah...@FreeNet.Carleton.CA

[MoeBlee]

On Dec 29, 1:43 pm, ah...@FreeNet.Carleton.CA (David Libert) wrote:

> I had posted about what the statement  con(PA) could be in MA,
> namely just the usual arithmetization into PA:

And that's what RussellE means too? As I asked, "Does [RussellE] mean
that there is a formula P in the language of MA (= the language of PA)

that encodes "PA is inconsistent" and such that MA |- P ?"

And if so, where's his proof that, for said P, we have MA |- P ?

Further, even with such a proof, how would that contribute to proving
that PA is inconsistent (as, if I gather correctly, RussellE's main
goal is to prove that PA (thus also ZF) is inconsistent?

More simply: What is the point of the various exercises we're doing
here if RussellE doesn't give a clear statement of his target claim
and a proof of it?

MoeBlee

[RussellE]

On Dec 29, 4:43 am, quasi <qu...@null.set> wrote:
> On 29 Dec 2011 11:52:39 GMT, Tim Little <t...@little-possums.net>
> wrote:
>
> >On 2011-12-29, quasi <qu...@null.set> wrote:
>
> >> Let Z denote the set of integers.
>
> >> Question:
>
> >>    Is Z is a model of MA?
>
> >No.  The problem is exactly that axiom schema of induction
> >you were wondering about.
>
> >For example, take as a predicate
>
> >   P(n) = "n is a sum of four squares".
>
> >One of the instances of the induction schema states:
>
> > (P(0) and An(P(n) -> P(n+1))) -> An P(n).
>
> I had already considered the sum-of-4-squares statement
> as a possible counterexample, but I'm not convinced that
> it's provable in MA.

I have wondered about the provability of the 4-squares
theorem in MA, too. I have given a different proof that
shows Z is not a model of MA:

A Counterexample to Löwenheim–Skolem Options
http://groups.google.com/group/sci.math/browse_thread/thread/a3b026aa99ca4bf3/32235b2d40655ed7

Let F(x) = 0-x.
I show Ex( x=F(x) or S(x)=F(x) ) is a theorem of MA.

Subtraction isn't defined in MA so I actually prove:

Let F(x) = e*x where e is the predecessor of 0.
Ex( x=F(x) or S(x)=F(x) )

In Z, e = -1.

Ex (x = -x or S(x) = -x)

This is true in Z for 0.

Ex( x ~= 0 and ( x=F(x) or S(x)=F(x) ) is true
in every model of MA except the 0-model
(the model where the only element is 0).

Ex( x ~= 0 and ( x=F(x) or S(x)=F(x) )
is false in Z.

[RussellE]

On Dec 29, 10:54 am, MoeBlee <modem...@gmail.com> wrote:
> On Dec 29, 7:22 am, Rupert <rupertmccal...@yahoo.com> wrote:
>
> > what do you [RussellE] mean by the domain of discourse of a model of MA having
> > an "odd" or "even" number of elements if it is infinite?
>
> He wrote, "I define the universe of a model of MA to be odd if it
> satisfies AxEy(x=y+y) and I define the universe of a model of MA to be
> even if it satisfies Ex(x~=0 and x+x=0)."
>
> So when he says, "MA must have infinite models where the universe is
> even and infinite models where the universe is odd," t take that to
> mean:
>
> 3) MA has an infinite model that satisfies AxEy(x=y+y).
>
> and
>
> (4) MA has an infinite model that satisfies Ex(~x=0 and x+x=0).

Yes.

I actually have two definitions for even and odd.
The two definitions are not equivalent as far
as PA is concerned.

MA + AxEy(x=y+y) has infinite "odd1" models.
MA + ExAy(x~=y+y) has infinite "even1" models

MA+Ax(x=0 or x+x~=0) has infinite "odd2" models.
MA+Ex(x~=0 and x+x=0) has infinite "even2" models.

In MA, every odd1 model is also an odd2 model.
In PA, ExAy(x~=y+y) and Ax(x=0 or x+x~=0) are true.

If I can show:

Ax(x=0 or x+x~=0) -> AxEy(x=y+y)
or
ExAy(x~=y+y) -> Ex(x~=0 and x+x=0)

then PA is inconsistent.
I am pretty sure these statements are true in MA.
The proofs almost certainly use Ex(S(x)=0).


Russell
- Never never means never in set theory

[RussellE]

On Dec 29, 12:41 am, quasi <qu...@null.set> wrote:
> On Wed, 28 Dec 2011 23:43:23 -0800 (PST), RussellE

> <reaste...@gmail.com> wrote:
> >On Dec 28, 9:29 pm, quasi <qu...@null.set> wrote:
> >> On Wed, 28 Dec 2011 14:47:24 -0800 (PST), RussellE
> >> <reaste...@gmail.com> wrote:
> >> >On Dec 28, 12:12 am, Rupert <rupertmccal...@yahoo.com> wrote:
> >> >> On Dec 28, 7:04 am, RussellE <reaste...@gmail.com> wrote:
>
> >> In thinking through the axiomatization of MA, I kept
> >> wondering about the need for induction.
>
> >> So here's my question ...
>
> >>    For the theory of MA, is induction actually required?
>
> >Only if MA has infinite models.
>
> I don't see how the existence of an infinite model changes the
> _theory_, that is, changes what can be _proved_.
>
> So here's my challenge:
>
> State a theorem of MA which you think _requires_ induction --
> that is, can't be proved in MA without it.

Induction was discussed quite a bit in the tread:

Modular Arithmetic is Consistent
http://groups.google.com/group/sci.logic/browse_thread/thread/cc493bc66033c9f/77a8b95554b551fd

Induction is the only rule that allows us to prove
statements of the form Ax P(x).

I originally included an omega rule with MA.
http://en.wikipedia.org/wiki/%CE%A9-consistent_theory

P(0) & P(S0) & P(SS0) ... & P(S...S0) -> Ax P(x)

The omega rule and induction are equivalent in
finite models of MA. They are not equivalent
in infinite models. In fact, the omega rule
proves MA is an omega inconsistent theory.
We can prove MA+Omega Rule has no
infinite models.

In particular, the omega rule proves
Ax(S(x)~=0) is true in any infinite
universe.

[quasi]

David Libert wrote:
>quasi wrote:
>>Tim Little wrote:

> We want to show Z is not a model of MA. To do this we want
>to show an instance of the induction schamtum fails in Z, ie
>the sentence in question is false in the model Z.
>
> To check the truth value of that implication in model Z, we
>check the truth of the antecedent and tjhe consequent.
>
> Not MA provabliltiy of the antecent. Truth in model Z.

Hmmm ...

I see the light.

That was very clear -- thanks.

And thanks also to Tim Little for the counterexample.

In my confusion, I thought that Tim was effectively asserting
that the sum-of-4-squares theorem is a theorem of MA, and
hence, since Z doesn't satisfy that theorem, that Z is not
a model of MA.

I realize now (thanks to David) that Tim wasn't claiming that
the sum-of-4-squares theorem is a theorem of MA, but rather that
one of the axioms of MA must fail in Z otherwise the Z _would_
satisfy the sum-of-4-squares theorem, and of course, that
theorem is obviously false in Z.

> Lagrange's theorem about 4 squares is true in model Z.

In the above sentence I hope you meant "false", not "true".

If that was a typo, no problem, otherwise I'm still confused.

>antecedent evaluates as true in model Z, by model theoretic
>truth.
>
> So the overall implication evaluates as false in model Z.
>
> Which is exactly what is needed to show a structure Z negates an
>axiom from a theory MA.

Yes, I follow.

Thanks.

Thus, Z is definitely _not_ a model of MA.

So this leaves open the question of whether the
sum-of-4-squares theorem is a theorem of MA.

It's clear that the sum-of-4-squares theorem is satisfied
in all models of the form Z/nZ, hence it must also hold in
some infinite models of MA.

But that doesn't mean that the sum-of-4-squares theorem is
actually provable in MA.

Can the standard proof of the sum-of-4-squares theorem in
PA be adapted to work as a proof in MA? I doubt it, but I'm
not sure. My intuition suggests that the sum-of-4-squares
theorem is unprovable in MA, and that would imply that the
sum-of-4-squares theorem fails in some model of MA,
necessarily an infinite model.

So the question remains:

Is the sum-of-4-squares theorem a theorem of MA?

quasi

[quasi]

Nam Nguyen wrote:
>quasi wrote:

>>Nam Nguyen wrote:
>>>Frederick Williams wrote:
>>>> quasi wrote:
>>>>>
>>>>> [...] for now, as anti-intuitive as it may seem, I
>>>>> actually believe that Z is a model of MA.
>>>>
>>>> That it is so has been mentioned in other threads on MA.
>>>
>>> Which I don't believe that would be the case because there
>>> are properties that are supposed to hold only for
>>> non-negativeintegers but would be true for all integers by
>>> Induction axioms.
>>
>> Name such a property.
>
>P(x) <-> (0=x \/ 0<x)

How do you define 0<x in MA?

>> For any such property P, make sure the induction axioms
>> of MA actually prove P. Thus, it's not sufficient to show
>> that the statement P(n) -> P(n+1) is true in Z. Rather,
>> you need to show that the statement P(n) -> P(n+1) can
>> be _proved_ in MA.
>
>Note "induction axioms of MA" is really "induction axioms of
>PA", by your own definition of MA.
>
>> Don't confuse truth with provability.
>
>I don't think I do.

Ok, I'll admit that _I_ was the one who had those two things
confused, but I'm over that now (I hope).

quasi

[Nam Nguyen]

On 29/12/2011 3:46 PM, quasi wrote:
> Nam Nguyen wrote:
>> quasi wrote:
>>> Nam Nguyen wrote:
>>>> Frederick Williams wrote:
>>>>> quasi wrote:
>>>>>>
>>>>>> [...] for now, as anti-intuitive as it may seem, I
>>>>>> actually believe that Z is a model of MA.
>>>>>
>>>>> That it is so has been mentioned in other threads on MA.
>>>>
>>>> Which I don't believe that would be the case because there
>>>> are properties that are supposed to hold only for
>>>> non-negativeintegers but would be true for all integers by
>>>> Induction axioms.
>>>
>>> Name such a property.
>>
>> P(x)<-> (0=x \/ 0<x)
>
> How do you define 0<x in MA?

It's part of L(MA) = L(PA), as well as part of PA's non-induction
axioms.

>>> For any such property P, make sure the induction axioms
>>> of MA actually prove P. Thus, it's not sufficient to show
>>> that the statement P(n) -> P(n+1) is true in Z. Rather,
>>> you need to show that the statement P(n) -> P(n+1) can
>>> be _proved_ in MA.
>>
>> Note "induction axioms of MA" is really "induction axioms of
>> PA", by your own definition of MA.
>>
>>> Don't confuse truth with provability.
>>
>> I don't think I do.
>
> Ok, I'll admit that _I_ was the one who had those two things
> confused, but I'm over that now (I hope).

I didn't have time to reflect on it much yet but I think if you
want to "tweak" PA to convert it into Z, you might have to do
more than just that one axiom.

[RussellE]

On Dec 29, 6:21 pm, Nam Nguyen <namducngu...@shaw.ca> wrote:
> On 29/12/2011 3:46 PM, quasi wrote:
>
> >>> Name such a property.
>
> >> P(x)<->  (0=x \/ 0<x)
>
> > How do you define 0<x in MA?
>
> It's part of L(MA) = L(PA), as well as part of PA's non-induction
> axioms.

One of the standard definitions of "=<" fails in MA.

(x =< y) -> (Ez(x+z=y))

The problem is Ez(x+z=y) is true for
any combination of x and y in MA.
Ez(x+z=y) doesn't order a model of MA.

It is not obvious that models of MA can be
well ordered without additional axioms.
Ax(x=0 or x>0) wouild be such an axiom.

[Transfer Principle]

On Dec 28, 12:31 pm, Uergil <Uer...@uer.net> wrote:
> In article
> <8bc60df3-84ab-4f74-b7a7-0827abcd8...@l16g2000prg.googlegroups.com>,

> > If ZFC is consistent then MA has an infinite model.

> Not proven!
> > MA has models with finite universal sets and these
> > universal sets can have an even or odd number
> > of elements. This means MA must have infinite

> > models where the universe is even and infinite

> > models where the universe is odd.
> Not proven!
> And until those two claims are both proved the rest is silence.

And here we go again with several posters -- not just Virgil --
giving RE the third degree, claiming that statements that have
been established in previous MA threads are "not proven!" But
what else should I expect from the posters with whom I disagree?

It's been established in previous threads that for each natural
number n>0, the ring Z/nZ (with '+' and '*' being mapped to ring
addition and multiplication respectively, and 'S' being mapped
to addition with 1) is a model of MA. Indeed, these are the
_intended_ models of MA.

It's also been established in previous threads that ZFC proves
that if a first order theory has finite models of cardinality n
for arbitrarily large n, then it has an infinite model.

Therefore, we conclude that ZFC |- MA has an infinite model.

And yet posters in this thread keep insisting that RE prove this
already established fact over and over again.

Since the posters with whom I disagree are so fond of giving
their opponents the third degree, let's turn the tables and let
me give RE's opponents the third degree: To anyone skeptical
that MA lacks models of arbitrarily large cardinality, please
name the natural number n>0 such that Z/nZ isn't a model of MA.

[Transfer Principle]

On Dec 28, 7:14 pm, MoeBlee <modem...@gmail.com> wrote:
> On Dec 28, 5:01 pm, RussellE <reaste...@gmail.com> wrote:
> > Both AxEy(x=y+y) and Ex(x~=0 and x+x=0) are
> > independent of the other axioms of MA.
> Below are some of the assertions you made for which I'd lie to see
> proof (and if you use anyting other than ZF for your proof, please
> state what additional axioms or alernative logic system you are
> using):

I don't know why I even bother responding to this post, in which
MoeBlee gives RE the third degree. If he won't accept RE's responses
to these, then he probably won't accept mine either.

> (1) If ZFC is consistent then MA has an infinite model.

We see that Z/nZ is a model of MA for every natural number n>0, and
so MA has a model of cardinality n for every natural number n>0. So
by Lowenheim-Skolem -- as already established in previous threads --

MA has an infinite model.

> (2) MA has finite models of both even and odd cardinality.

Model of MA of even cardinality: Z/2Z.
Model of MA of odd cardinality: Z/3Z.

Of course, these models map '+' and '*' to the corresponding ring
operations and 'S' to addition with 1.

> (3) MA has an infinite odd model. [Note that MA has an infinite model
> does not follow from (2) since (2) does not say that MA has models of
> arbitrarily large finite cardinality.]

But (1) says that MA has models of arbitrarily large finite
cardinality.

> (4) MA has an infinite even model. [Note that MA has an infinite model
> does not follow from (2) since (2) does not say that MA has models of
> arbitrarily large finite cardinality.]

But (1) says that MA has models of arbitrarily large finite
cardinality.

> (5) AxEy(x=y+y) is independent of MA.

There exists a model (Z/3Z) in which it's true, and another model (Z/
2Z)
in which it's false.

> (6) Ex(x~=0 and x+x=0) is independent of MA.

There exists a model (Z/2Z) in which it's true, and another model (Z/
3Z)
in which it's false.

Will MoeBlee accept these answers? Of course not, since he didn't
accept
similar answers from RE in previous threads. Let's see what excuses
the
posters of this thread will give for rejecting my answers and
continuing
to give us the third degree.

[Rupert]

On Dec 29, 10:48 pm, RussellE <reaste...@gmail.com> wrote:
> On Dec 29, 10:54 am, MoeBlee <modem...@gmail.com> wrote:
>
>
>
>
>
>
>
>
>
> > On Dec 29, 7:22 am, Rupert <rupertmccal...@yahoo.com> wrote:
>
> > > what do you [RussellE] mean by the domain of discourse of a model of MA having
> > > an "odd" or "even" number of elements if it is infinite?
>
> > He wrote, "I define the universe of a model of MA to be odd if it
> > satisfies AxEy(x=y+y) and I define the universe of a model of MA to be
> > even if it satisfies Ex(x~=0 and x+x=0)."
>
> > So when he says, "MA must have infinite models where the universe is
> > even and infinite models where the universe is odd," t take that to
> > mean:
>
> > 3) MA has an infinite model that satisfies AxEy(x=y+y).
>
> > and
>
> > (4) MA has an infinite model that satisfies Ex(~x=0 and x+x=0).
>
> Yes.
>
> I actually have two definitions for even and odd.
> The two definitions are not equivalent as far
> as PA is concerned.
>
> MA + AxEy(x=y+y) has infinite "odd1" models.
> MA + ExAy(x~=y+y) has infinite "even1" models
>
> MA+Ax(x=0 or x+x~=0) has infinite "odd2" models.
> MA+Ex(x~=0 and x+x=0) has infinite "even2" models.
>
> In MA, every odd1 model is also an odd2 model.

Can you prove that?

> In PA, ExAy(x~=y+y) and Ax(x=0 or x+x~=0) are true.
>
> If I can show:
>
> Ax(x=0 or x+x~=0) -> AxEy(x=y+y)
> or
> ExAy(x~=y+y) -> Ex(x~=0 and x+x=0)
>
> then PA is inconsistent.

If you could prove it in first-order logic, or even in PA, yes that
would follow.

> I am pretty sure these statements are true in MA.
> The proofs almost certainly use Ex(S(x)=0).
>

Why is that interesting?

[quasi]

quasi wrote:

>So the question remains:
>
>Is the sum-of-4-squares theorem a theorem of MA?

Along these lines, consider the fact that, for any prime p,
the finite field Z/pZ is a model of MA, and moreover, Z/pZ
satisfies the sum-of-4-squares theorem (s4s).

So let's consider models of the theory

T = MA + field + s4s

In other words, consider all fields K having a successor
function satisfying the axioms of MA and such that the
sum-of-4-squares theorem holds in K.

Since the finite fields Z/pZ with successor function

S(x) = x + 1

are models of T, it follows that T has an infinite model.

Of course, such a field can't be a subfield of R, since in
that case, s4s would fail.

So let's consider some candidate fields.

Let C be the field of complex numbers with successor function

S(x) = x + 1

and let A be the subfield of algebraic numbers, using the same
successor function.

Questions:

(1) Is A a model of MA?

(2) Is C a model of MA?

If not, what axiom or theorem of MA fails?

quasi

[MoeBlee]

On Dec 30, 12:10 am, Transfer Principle <david.l.wal...@lausd.net>
wrote:

> MoeBlee gives RE the third degree.

Yeah, asking for definitions and proofs is "giving the third degree."

> Will MoeBlee accept these answers? Of course not,

You're an ass for presuming to predict me. Look at the actual posts in
this thread instead.

MoeBlee

[MoeBlee]

P.P.S. to Transfer Principle:

Regarding INSULTS, you insult me when you characterize my asking for
proofs as "the third degree" and you insult me again by claiming that
I will not accept given proofs.

MoeBlee

[MoeBlee]

On Dec 29, 3:48 pm, RussellE <reaste...@gmail.com> wrote:
> On Dec 29, 10:54 am, MoeBlee <modem...@gmail.com> wrote:

> > 3) MA has an infinite model that satisfies AxEy(x=y+y).
>
> > and
>
> > (4) MA has an infinite model that satisfies Ex(~x=0 and x+x=0).
>
> Yes.
>
> I actually have two definitions for even and odd.

> The two definitions are not equivalent as far
> as PA is concerned.

I asked you for the definition, you gave it, I said "okay, I
understand", but now you tell me there is another non-equivalent
version, but you don't even state it.

> MA + AxEy(x=y+y) has infinite "odd1" models.
> MA + ExAy(x~=y+y) has infinite "even1" models
>
> MA+Ax(x=0 or x+x~=0) has infinite "odd2" models.
> MA+Ex(x~=0 and x+x=0) has infinite "even2" models.
>
> In MA, every odd1 model is also an odd2 model.
> In PA, ExAy(x~=y+y) and Ax(x=0 or x+x~=0) are true.

Since I don't know your definitions of 'odd1', 'odd2', 'even1', and
'even2', I have no way of knowing how to regard the above.

Here's what's considered proven:

(3) MA has an infinite model that satisfies AxEy(x=y+y).

(4) MA has an infinite model that satisfies Ex(~x=0 and x+x=0).

(5) AxEy(x=y+y) is independent of MA.

(6) Ex(~x=0 and x+x=0) is independent of MA.

And you're objective is to show PA is inconsistent.

> If I can show:
>
> Ax(x=0 or x+x~=0) -> AxEy(x=y+y)
> or
> ExAy(x~=y+y) -> Ex(x~=0 and x+x=0)
>
> then PA is inconsistent.

If you can show, in PA, either of those conditionals, then PA is
inconsistent.

But there's nothing to suggest that either of those conditionals can
be shown in PA.

So when you say "if I can show", do you mean "if, in PA, I can show"
or do you mean "if, in MA, I can show"? If neither, then when you say
"show", in what system do you mean?

> I am pretty sure these statements are true in MA.

You mean they're theorems of MA?

> The proofs almost certainly use Ex(S(x)=0).

If they are theorems of MA then the proofs must use Ex Sx=0.

Now that these various exercises have been done, would you PLEASE
state your argurment that PA is inconsistent?

MoeBlee

[quasi]

On Fri, 30 Dec 2011 00:36:40 -0800 (PST), MoeBlee wrote:

>
>On Dec 30, 12:10 am, Transfer Principle wrote:
>>
>> MoeBlee gives RE the third degree.
>
>Yeah, asking for definitions and proofs is "giving the
>third degree."

Well, since you didn't called RE a crank, TP had to work
a little harder to find something to complain about.

>> Will MoeBlee accept these answers? Of course not,
>
>You're an ass for presuming to predict me. Look at the
>actual posts in this thread instead.

Typical of TP's style -- he asks a question of a sci.math
participant, but rather then wait for an answer, he asserts
in advance what their answer is actually going to be, and
then argues against it.

quasi

[MoeBlee]

On Dec 30, 12:10 am, Transfer Principle <david.l.wal...@lausd.net>
wrote:

You're lying about me again.

Or, please name a single instance in which RussellE, or ANY poster,
gave an actually correct proof but I denied that it was correct.

MoeBlee

[MoeBlee]

Not only that, but his claim that I wouldn't accept proofs is false IN
THIS VERY THREAD, since, after Libert and Little replied with various
notes, I even POSTED that for purposes of this discussion I'll take it
for granted that the items had been proven. So his "Of course not" is
a lie.

And then he goes on to lie about me more, as he says that I have
previously refused to accept actual proofs, though he cannot cite a
single instance in which a poster gave an actually correct proof but I
denied the proof.

Transfer Principle is an insulting ass. And, yeah, that is is an
insult - one that he deserves.

MoeBlee

[MoeBlee]

P.S. to Transfer Principle:

I stated that I take it as given that these have been proven:

(3) MA has an infinite model that satisfies AxEy(x=y+y).

(4) MA has an infinite model that satisfies Ex(~x=0 and x+x=0).

(5) AxEy(x=y+y) is independent of MA.

(6) Ex(~x=0 and x+x=0) is independent of MA.

And RussellE claims that this contributes somehow to proving that PA
is inconsistent.

So let's see the argument that PA is inconsistent. Would either you or
him PLEASE give the argument that PA is inconsistent?

MoeBlee

[quasi]

More generally, is there _any_ field which, using the
successor function S(x) = x + 1, is not a model of MA?

How about Q?

Or R?

Note, while it might seem anti-intuitive that a field of
characteristic zero could be a model of MA, the fact that
for all primes p, the field Z/pZ is a model of MA implies,
by The Compactness Theorem, the existence of fields of
characteristic zero which are models of MA.

How about finite fields other than those of the form Z/pZ?

Remark:

Regarding RussellE's parity concepts ...

If K is a field of charateristic 2, and if K is a model of
MA, then K is "even" in the sense that 1 + 1 = 0.

If K is a field of any characteristic other than 2, and if
K is a model of MA, then K is "odd" in the sense that for
all y in K, there exists x in K such that y = x + x.

quasi

[MoeBlee]

And one more:

Transfer Principle said I gave "the third degree", but what I actually
said:

"I'd li[k]e to see proofs" and "If those have been proven elsewhere or
the proofs are obvious, please excuse me as I merely trying to quickly
and in one place get your
claims lined up here. "

Yeah, "I'd like to see proofs" and "please excuse me if [the proofs
were already posted elsehwere" is really giving the "third degree"!

MoeBlee

[quasi]

Not all fields are models of MA -- see below.

>How about Q?
>
>Or R?

Neither of Q or R is a model of MA.

Let S = {x in Q | x is a sum of 4 squares from Q}

The sum-of-4-squares theorem for N implies that

S = {x in Q | x >= 0}.

Since 0 is in S and (x in S => x+1 in S), it follows that
if Q was a model of MA, the by induction we could infer
S = Q, contrary to the fact that S contains only the
nonnegative elements of Q.

Therefore Q is not a model of MA.

The proof for R can be done in the same way, but for R we
can simplify the proof by using only one square, not 4. Thus,
let S be defined by

S = {x in R | x = y^2 for some y in R}

Clearly S = {x in R | x >= 0}, but once again, if R was in MA,
induction would imply that S = R, contradiction.

Therefore R is not a model of MA.

It's possible that some subfield K of R is a model of MA,
but if so, it will have to be the case that for every m in N,
there exists at least one nonnegative element of K which is
not a sum of m squares in K. Does such a subfield of R exist?
I'm not sure.

>Note, while it might seem anti-intuitive that a field of
>characteristic zero could be a model of MA, the fact that
>for all primes p, the field Z/pZ is a model of MA implies,
>by The Compactness Theorem, the existence of fields of
>characteristic zero which are models of MA.
>
>How about finite fields other than those of the form Z/pZ?

>Remark:
>
>Regarding RussellE's parity concepts ...
>
>If K is a field of charateristic 2, and if K is a model of
>MA, then K is "even" in the sense that 1 + 1 = 0.
>
>If K is a field of any characteristic other than 2, and if
>K is a model of MA, then K is "odd" in the sense that for
>all y in K, there exists x in K such that y = x + x.

To recap, the following questions are unresolved:

Using the successor function S(x) = x + 1,

(1) Is the field A of algebraic numbers a model of MA?

(2) Is C a model of MA?

(3) Is every finite field a model of MA?

(4) Is any subfield of R a model of MA?

quasi

[quasi]

I can answer (3).

Proposition:

A field of nonzero characteristic is a model of MA iff K
is isomorphic to Z/pZ for some prime p.

proof:

It's clear that for all primes p, the field Z/pZ is a
model of MA.

For the converse, let p be a prime and suppose K is a field
of characteristic p which is a model of MA. Let F be the
prime subfield of K. Then F is isomorphic to Z/pZ.

Our goal is to show K = F.

The set of solutions in K to the equation

x^(p-1) = 1

is precisely the (p-1)-element set F \ 0.

Now consider the statement Q(x):

x = 0 or x^(p-1) = 1.

By induction Q(x) is true for all x in K.

It follows that K = F, as claimed, which completes the proof.

Corollary (1):

If a finite field K is a model of MA, then K is isomorphic
to Z/pZ for some prime p.

Proof:

Since K is finite, char(K) = p for some prime p, hence
by the proposition, K is isomorphic to Z/pZ.

Corollary (2):

If K is an infinite field which is a model of MA, then
K has characteristic zero.

Proof:

Assume instead that char(K) is nonzero. Then char(K) = p for
some prime p. Then by the proposition, K is isomorphic to
Z/pZ, which implies K is finite, contradiction.

quasi

[RussellE]

On Dec 29, 10:47 pm, Rupert <rupertmccal...@yahoo.com> wrote:
> On Dec 29, 10:48 pm, RussellE <reaste...@gmail.com> wrote:
>
> > MA + AxEy(x=y+y) has infinite "odd1" models.
> > MA + ExAy(x~=y+y) has infinite "even1" models
>
> > MA+Ax(x=0 or x+x~=0) has infinite "odd2" models.
> > MA+Ex(x~=0 and x+x=0) has infinite "even2" models.
>
> > In MA, every odd1 model is also an odd2 model.
>
> Can you prove that?

I can prove AxEy(x=y+y) -> Ax(x=0 or x+x~=0)
for finite models of MA.

AxEy(x=y+y) says there is a bijection between
U={0,1,2,...,e) and V={0+0,1+1,...,e+e)
Since 0+0=0 is a therorem of MA we know
0 is paired with 0+0 in this bijection.

We can now come up with a proof by
contradiction using the pigeonhole problem.

Assume Ex(x~=0 and x+x=0).
Let U be our n pigeons and V be our n-1 holes.
The pigeonhole problem for n pigeons and
n-1 holes can be written as a Boolean
expression. Using FOL we can derive a
contradiction and prove

AxEy(x=y+y) -> ~(Ex(x~=0 and x+x=0))

Proving the pigeonhole principle holds for
infinite sets will be much harder.

> > In PA, ExAy(x~=y+y) and Ax(x=0 or x+x~=0) are true.
>
> > If I can show:
>
> > Ax(x=0 or x+x~=0) -> AxEy(x=y+y)
> > or
> > ExAy(x~=y+y) -> Ex(x~=0 and x+x=0)
>
> > then PA is inconsistent.
>
> If you could prove it in first-order logic, or even in PA, yes that
> would follow.
>
> > I am pretty sure these statements are true in MA.
> > The proofs almost certainly use Ex(S(x)=0).
>
> Why is that interesting?

The pigeonhole proof doesn't use Ex(S(x)=0).

I have a simple proof that no model of MA
can define a Dedekind inifinite set.
http://en.wikipedia.org/wiki/Dedekind-infinite_set

Assume we have an infinite model of MA and
M is the universal set of this model.
In previous threads it was proven any infinite
model of MA must have non-standard naturals.

Assume we also have a non-standard model
of PA where N is the universal set of this model
and M is a proper subset of N.

Assume S is a proper subset of M and there
exists a bijection between M and S.
In our model of PA we know |S| < |M|.

If there is a bijection between M and S in
our model of MA, the same bijection exists
in our model of PA. This means PA can
prove there is a bijection between two
different natural numbers.

We know this not true from Skolem's paradox.
No model of MA can define a Dedekind
infinite set.

[RussellE]

On Dec 30, 5:14 am, quasi <qu...@null.set> wrote:

> quasi wrote:
>
> To recap, the following questions are unresolved:
>
> Using the successor function S(x) = x + 1,
>
>    (1) Is the field A of algebraic numbers a model of MA?
>
>    (2) Is C a model of MA?
>
>    (3) Is every finite field a model of MA?
>
>    (4) Is any subfield of R a model of MA?

In previous threads it was proven that in
any infinite model of MA the predeccessor
of 0 must be a non-standard natural number.

I have read that countable non-standard models
of PA can only have one order type. It is a rather
complicated order type.
http://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic

Do any of the models you propose have this order type?

So far, no one has described the order type
of an infinite model of MA. It can't be the same
as the order type of non-standard models of PA.

[Rupert]

On Dec 30, 10:19 pm, RussellE <reaste...@gmail.com> wrote:
> On Dec 29, 10:47 pm, Rupert <rupertmccal...@yahoo.com> wrote:
>
> > On Dec 29, 10:48 pm, RussellE <reaste...@gmail.com> wrote:
>
> > > MA + AxEy(x=y+y) has infinite "odd1" models.
> > > MA + ExAy(x~=y+y) has infinite "even1" models
>
> > > MA+Ax(x=0 or x+x~=0) has infinite "odd2" models.
> > > MA+Ex(x~=0 and x+x=0) has infinite "even2" models.
>
> > > In MA, every odd1 model is also an odd2 model.
>
> > Can you prove that?
>
> I can prove AxEy(x=y+y) -> Ax(x=0 or x+x~=0)
> for finite models of MA.
>

Yes, I agree with that.

> AxEy(x=y+y) says there is a bijection between
> U={0,1,2,...,e) and V={0+0,1+1,...,e+e)

What's e, and how do you know it's a bijection?

> Since 0+0=0 is a therorem of MA we know
> 0 is paired with 0+0 in this bijection.
>
> We can now come up with a proof by
> contradiction using the pigeonhole problem.
>
> Assume Ex(x~=0 and x+x=0).
> Let U be our n pigeons and V be our n-1 holes.
> The pigeonhole problem for n pigeons and
> n-1 holes can be written as a Boolean
> expression. Using FOL we can derive a
> contradiction and prove
>
> AxEy(x=y+y) -> ~(Ex(x~=0 and x+x=0))
>
> Proving the pigeonhole principle holds for
> infinite sets will be much harder.
>

It looks as though you can't prove your statement.

>
>
>
>
>
>
>
>
> > > In PA, ExAy(x~=y+y) and Ax(x=0 or x+x~=0) are true.
>
> > > If I can show:
>
> > > Ax(x=0 or x+x~=0) -> AxEy(x=y+y)
> > > or
> > > ExAy(x~=y+y) -> Ex(x~=0 and x+x=0)
>
> > > then PA is inconsistent.
>
> > If you could prove it in first-order logic, or even in PA, yes that
> > would follow.
>
> > > I am pretty sure these statements are true in MA.
> > > The proofs almost certainly use Ex(S(x)=0).
>
> > Why is that interesting?
>
> The pigeonhole proof doesn't use Ex(S(x)=0).
>

That's not a proof in MA, that's a proof in your metatheory about
properties of finite models of MA, and I wasn't really convinced that
it was rigorous.

> I have a simple proof that no model of MA

> can define a Dedekind inifinite set.http://en.wikipedia.org/wiki/Dedekind-infinite_set

>
> Assume we have an infinite model of MA and
> M is the universal set of this model.
> In previous threads it was proven any infinite
> model of MA must have non-standard naturals.
>

What does that mean?

> Assume we also have a non-standard model
> of PA where N is the universal set of this model
> and M is a proper subset of N.
>

It's not possible for a model of MA to be a proper subset of a model
of PA.

> Assume S is a proper subset of M and there
> exists a bijection between M and S.
> In our model of PA we know |S| < |M|.
>

What does that mean?

> If there is a bijection between M and S in
> our model of MA, the same bijection exists
> in our model of PA.

This doesn't mean anything. We're not talking about a model for the
language of set theory. The property of a bijection existing between
the two sets is not something that is true or not true "in the model".

> This means PA can
> prove there is a bijection between two
> different natural numbers.
>

How do you talk about bijections in the language of PA?

> We know this not true from Skolem's paradox.

No, Skolem's paradox has nothing to do with it.

> No model of MA can define a Dedekind
> infinite set.
>

This proof is seriously flawed.

[Frederick Williams]

RussellE wrote:

> We can now come up with a proof by
> contradiction using the pigeonhole problem.

How do you prove the pigeonhole principal in MA?

--
When a true genius appears in the world, you may know him by
this sign, that the dunces are all in confederacy against him.
Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting

[quasi]

RussellE wrote:

>quasi wrote:
>> quasi wrote:
>>
>> To recap, the following questions are unresolved:
>>
>> Using the successor function S(x) = x + 1,
>>
>>    (1) Is the field A of algebraic numbers a model of MA?
>>
>>    (2) Is C a model of MA?
>>
>>    (3) Is every finite field a model of MA?
>>
>>    (4) Is any subfield of R a model of MA?
>
>In previous threads it was proven that in any infinite model
>of MA the predeccessor of 0 must be a non-standard natural
>number.

Can you give a link to the proof?

I appear to have proved something quite different. Of course,
my proof may be flawed, but thought I showed that there exist
infinite fields with S(x) = x + 1 which are models of MA.

In a field with S(x) = x + 1, the predecessor of 0 is -1, thus
no need to invoke non-standard concepts.

I'll sketch again the proof of the existence of infinite
fields with S(x) = x + 1 which are models of MA.

Let "FIELD" denote the field axioms, and consider the theory

T = MA + FIELD

together with the axiom S(x) = x + 1

Then T has models, namely Z/pZ for any prime p.

Since T has arbitrarily large finite models, the compactness
theorem implies that T has an infinite model, end of proof.

Ok, I'm a novice at this game, so I wouldn't be surprised if
my proof is irreparably flawed, but if it's flawed, can someone
please point out an error?

quasi

[RussellE]

On Dec 30, 1:30 am, quasi <qu...@null.set> wrote:
> On Fri, 30 Dec 2011 00:36:40 -0800 (PST), MoeBlee wrote:
>
> >On Dec 30, 12:10 am, Transfer Principle wrote:
>
> >> MoeBlee gives RE the third degree.
>
> >Yeah, asking for definitions and proofs is "giving the
> >third degree."
>
> Well, since you didn't called RE a crank, TP had to work
> a little harder to find something to complain about.

I have to agree. MoeBlee has been remarkably
well behaved for MoeBlee. MoeBlee's questions
have been reasonable.

[RussellE]

On Dec 30, 2:25 pm, Rupert <rupertmccal...@yahoo.com> wrote:
> On Dec 30, 10:19 pm, RussellE <reaste...@gmail.com> wrote:
>
> > I can prove AxEy(x=y+y) -> Ax(x=0 or x+x~=0)
> > for finite models of MA.
>
> Yes, I agree with that.
>
> > AxEy(x=y+y) says there is a bijection between
> > U={0,1,2,...,e) and V={0+0,1+1,...,e+e)
>
> What's e, and how do you know it's a bijection?

e is the predecessor of 0.
For every x in U there is x+x in V.
I have to prove every x+x is unique.

>
> > Since 0+0=0 is a therorem of MA we know
> > 0 is paired with 0+0 in this bijection.
>
> > We can now come up with a proof by
> > contradiction using the pigeonhole problem.
>
> > Assume Ex(x~=0 and x+x=0).
> > Let U be our n pigeons and V be our n-1 holes.
> > The pigeonhole problem for n pigeons and
> > n-1 holes can be written as a Boolean
> > expression. Using FOL we can derive a
> > contradiction and prove
>
> > AxEy(x=y+y) -> ~(Ex(x~=0 and x+x=0))
>
> > Proving the pigeonhole principle holds for
> > infinite sets will be much harder.
>
> It looks as though you can't prove your statement.

No. I also haven't been able to prove:

Axioms of PA -> ExAy(x~=y+y) and Ax(x=0 or x+x~=0)

I think you agree AxEy(x=y+y) -> Ax(x=0 or x+x~=0)
is true for arbitrarily large finite models of MA.

Let T = MA + AxEy(x=y+y) -> Ax(x=0 or x+x~=0)

Doesn't compactness prove T has a
countably infinite model?

[Nam Nguyen]

On 30/12/2011 8:02 PM, RussellE wrote:
> On Dec 30, 2:25 pm, Rupert<rupertmccal...@yahoo.com> wrote:
>> On Dec 30, 10:19 pm, RussellE<reaste...@gmail.com> wrote:
>>
>>> I can prove AxEy(x=y+y) -> Ax(x=0 or x+x~=0)
>>> for finite models of MA.
>>
>> Yes, I agree with that.
>>
>>> AxEy(x=y+y) says there is a bijection between
>>> U={0,1,2,...,e) and V={0+0,1+1,...,e+e)
>>
>> What's e, and how do you know it's a bijection?
>
> e is the predecessor of 0.

Why not _a_ predecessor of 0?

[Rupert]

On Dec 31, 4:02 am, RussellE <reaste...@gmail.com> wrote:
> On Dec 30, 2:25 pm, Rupert <rupertmccal...@yahoo.com> wrote:
>
> > On Dec 30, 10:19 pm, RussellE <reaste...@gmail.com> wrote:
>
> > > I can prove AxEy(x=y+y) -> Ax(x=0 or x+x~=0)
> > > for finite models of MA.
>
> > Yes, I agree with that.
>
> > > AxEy(x=y+y) says there is a bijection between
> > > U={0,1,2,...,e) and V={0+0,1+1,...,e+e)
>
> > What's e, and how do you know it's a bijection?
>
> e is the predecessor of 0.

Can you prove 0 has a unique predecessor?

> For every x in U there is x+x in V.
> I have to prove every x+x is unique.
>

That's obvious; what you have to prove is that the function is
injective.

>
>
>
>
>
>
>
>
>
>
> > > Since 0+0=0 is a therorem of MA we know
> > > 0 is paired with 0+0 in this bijection.
>
> > > We can now come up with a proof by
> > > contradiction using the pigeonhole problem.
>
> > > Assume Ex(x~=0 and x+x=0).
> > > Let U be our n pigeons and V be our n-1 holes.
> > > The pigeonhole problem for n pigeons and
> > > n-1 holes can be written as a Boolean
> > > expression. Using FOL we can derive a
> > > contradiction and prove
>
> > > AxEy(x=y+y) -> ~(Ex(x~=0 and x+x=0))
>
> > > Proving the pigeonhole principle holds for
> > > infinite sets will be much harder.
>
> > It looks as though you can't prove your statement.
>
> No. I also haven't been able to prove:
>
> Axioms of PA -> ExAy(x~=y+y) and Ax(x=0 or x+x~=0)
>

That seems very easy to prove to me. One can easily prove that 1 is
not an even number, and that if x>0 then x+x>0.

> I think you agree AxEy(x=y+y) -> Ax(x=0 or x+x~=0)
> is true for arbitrarily large finite models of MA.
>
> Let T = MA + AxEy(x=y+y) -> Ax(x=0 or x+x~=0)
>
> Doesn't compactness prove T has a
> countably infinite model?
>

Yes.

[RussellE]

On Dec 30, 9:43 pm, Rupert <rupertmccal...@yahoo.com> wrote:
> On Dec 31, 4:02 am, RussellE <reaste...@gmail.com> wrote:
>
> Can you prove 0 has a unique predecessor?
>

Yes. First prove successor is unique.
No other number can have 0 as a successor.

[Uergil]

In article
<205b0dec-4fcb-4bfd...@n22g2000prh.googlegroups.com>,

But you cannot prove uniqueness until you establish existence, which you
do not seem to have done.
--
"Ignorance is preferable to error, and he is less
remote from the- truth who believes nothing than
he who believes what is wrong.
Thomas Jefferson

[RussellE]

On Dec 31, 1:34 am, Uergil <Uer...@uer.net> wrote:
> In article
> <205b0dec-4fcb-4bfd-8dbd-7622bb09f...@n22g2000prh.googlegroups.com>,

>
>  RussellE <reaste...@gmail.com> wrote:
> > On Dec 30, 9:43 pm, Rupert <rupertmccal...@yahoo.com> wrote:
> > > On Dec 31, 4:02 am, RussellE <reaste...@gmail.com> wrote:
>
> > > Can you prove 0 has a unique predecessor?
>
> > Yes. First prove successor is unique.
> > No other number can have 0 as a successor.
>
> But you cannot prove uniqueness until you establish existence, which you
> do not seem to have done.

I have the axiom Ex(S(x)=0).

[Frederick Williams]

RussellE wrote:

> Induction is the only rule that allows us to prove
> statements of the form Ax P(x).

How would you prove Ax x = x ?

[Jesse F. Hughes]

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

> Induction is the only rule that allows us to prove
> statements of the form Ax P(x).

Er, sure. Right. No other way to prove a universal statement.

In fact, the only way you can prove, for instance,

(Ax)(x = 0 v x != 0)

is by induction. So think about all those theories in which induction
is not an axiom. In each and every one of those theories, there is no
theorem of the form (Ax)Px. Not a one.

Because induction is the only way to prove (Ax)Px.

You are so insightful!

--
"Humanity is still a primitive species. I seem to have been born out
of my time, maybe centuries ahead, and I guess I'll just have to get
used to it. In ways, it's not so bad. Mostly it's boring though."
-- James S. Harris has problems beyond you and me.

[Gus Gassmann]

On Dec 28, 2:04 am, RussellE <reaste...@gmail.com> wrote:
> Modular Arithmetic (MA) has the same axioms as
> first order Peano Arithmetic (PA) except Ax(S(x)~=0)
> is replaced with Ex(S(x)=0).
>
> If ZFC is consistent then MA has an infinite model.
>
> MA has models with finite universal sets and these
> universal sets can have an even or odd number
> of elements. This means MA must have infinite
> models where the universe is even and infinite
> models where the universe is odd.

I do not believe this is true. If all you have is Ex(S(x)=0), then all
you can say is that the finite models (of which there are infinitely
many) imply the existence of *an* infinite model. Convince me that
this infinite model is not (isomorphic to) Z.

[RussellE]

On Dec 31, 10:29 am, "Jesse F. Hughes" <je...@phiwumbda.org> wrote:

> RussellE <reaste...@gmail.com> writes:
> > Induction is the only rule that allows us to prove
> > statements of the form Ax P(x).
>
> Er, sure.  Right.  No other way to prove a universal statement.

As Frederick Williams points out, we can prove
statements of the form Ax P(x) using the axioms
of equality. If our theory has axioms of the form
Ax Q(x) and we can prove Q(x)=P(x) then we can
use equality to prove Ax P(x).

[RussellE]

On Dec 31, 10:21 am, Frederick Williams

<freddywilli...@btinternet.com> wrote:
> RussellE wrote:
> > Induction is the only rule that allows us to prove
> > statements of the form Ax P(x).
>
> How would you prove Ax x = x ?

You need the axioms of equality.
In particular, Ax x=x is the axiom of reflexivity.
http://en.wikipedia.org/wiki/First-order_logic#Equality_and_its_axioms

I assume MA includes the axioms of equality.

[Transfer Principle]

On Dec 30, 1:30 am, quasi <qu...@null.set> wrote:

OK, I accept this as a valid criticism of me.

I need to get into the habit of using the phrase "I'd be
surprised if ..." Thus, I should've written:

"I'd be surprised if MoeBlee accepts this answer, because ..."

followed by whatever reason I planned on giving.

Notice that the statement I made can be falsified and hence
labeled a lie. But the statement:

"I'd be surprised if MoeBlee accepts this answer, because ..."

can't be falsified, since it's actually a statement about my
own feelings. A statement of the form "I'd be surprised if P
occurs" isn't a lie, not even if P occurs.

Note that at this point, I no longer make any claim about what
MoeBlee will say or surprise over what he will say, due to
subsequent responses in this thread. I do have something to say
about another poster, but I'll write that in my next post,
directed to that particular poster.

[Transfer Principle]

On Dec 31, 1:08 pm, Gus Gassmann <horand.gassm...@googlemail.com>
wrote:

But Little already proved this. See his posts about sums of four
squares, starting on the 29th at just before noon Greenwich.

Also, note that MA has arbitrarily large finite models where the
universe is even (cf. Z/(2n)Z) and arbitrarily large finite models
where the universe is odd (cf. Z(2n+1)Z). Otherwise (and I admit
that I'm giving Gassmann the third degree here), name the natural
number n>1 such that Z/(2n)Z isn't an even model of MA, or maybe
n>1 such that Z/(2n+1)Z isn't an odd model of MA.

[Transfer Principle]

And since not even RE has a problem with MoeBlee's questions,
neither do I anymore.

And now the thread has evolved from merely discussing infinite
models of MA to attempting to prove PA inconsistent. But I'd be
surprised if a consideration of infinite models of MA actually
leads to an e.r. proof of ~Con(PA). (I prefer Ed Nelson's proof
attempt of ~Con(PA), btw.)

Given a choice between calling RE "wrong" and simply leaving
the thread, I strongly prefer the latter.

And so I must bid this thread adieu.

[Tonico]

On Jan 1, 1:09 am, Transfer Principle <david.l.wal...@lausd.net>
wrote:

> On Dec 30, 1:30 am, quasi <qu...@null.set> wrote:
>
> > On Fri, 30 Dec 2011 00:36:40 -0800 (PST), MoeBlee wrote:
> > >You're an ass for presuming to predict me. Look at the
> > >actual posts in this thread instead.
> > Typical of TP's style -- he asks a question of a sci.math
> > participant, but rather then wait for an answer, he asserts
> > in advance what their answer is actually going to be, and
> > then argues against it.
>
> OK, I accept this as a valid criticism of me.
>
> I need to get into the habit of using the phrase "I'd be
> surprised if ..." Thus, I should've written:
>
> "I'd be surprised if MoeBlee accepts this answer, because ..."
>
> followed by whatever reason I planned on giving.

*** Or, making a huge step toward human comprehension and tolerance,
you could wait for Moeblee to ACTUALLY write his own view before even
comment on it before hand...

I know the above would be a serious leap of faith for you, mom: what
if evil Moeblee, or anyone else for that matter, won't react as you'd
not be surprised he would and squashes the reason you planned to give
WITHOUT EVEN WANTING TO?

The world is full with such evil individuals, you know...

Tonio

[Jesse F. Hughes]

Q(x) = P(x) is not a well-formed formula, since equality (in standard
FOL=) is a relation between terms, not formulas.

Moreover, you silly person, you can prove many, many universal
statements without using axioms of equality *or* induction. Think, now:
don't you suppose that (Ax)(Px v ~Px) is a theorem of FOL?

--
Jesse F. Hughes

"OFF TOPIC: Christopher Columbus never existed either."
-- A post on the 9/11 conspiracy theorist site "LetsRollForums.com"

[Jesse F. Hughes]

Er.

Hm.

Not to put too fine a point on it, but you regularly announce that
you're leaving a thread because otherwise you'd have to declare one of
the downtrodden wrong. Seems to me that such announcements amount to
declaring that humble mathematical revolutionary wrong.

So, you've just pretty explicitly said that RE is wrong. Oh, dear!
This *is* a quandary.

Perhaps you should simply announce that you won't give an explanation
why you're leaving the thread, because if you explained why, you would
effectively be calling RE (or whoever) wrong and you don't want to do
that.


--
"Am I am [sic] misanthrope? I would say no, for honestly I never heard
of this word until about 1994 or thereabouts on the Internet reading a
post from someone who called someone a misanthrope."
-- Archimedes Plutonium

[spunselerlangen]

Jesse F. Hughes write:

> effectively ... want to do ...

Hey Jesses! Happy New Year!

(Was just looking a bit around - so I found you in sci.math 1012...)

boink! ;)

[Spunsel Erlangen]

Spunsel Erlangen schrieb:

Oooooooooooops, typo, I meant 2012 it is...

[quasi]

Transfer Principle wrote:

>quasi wrote:
>> MoeBlee wrote:
>> >
>> >You're an ass for presuming to predict me. Look at the
>> >actual posts in this thread instead.
>>
>> Typical of TP's style -- he asks a question of a sci.math
>> participant, but rather then wait for an answer, he asserts
>> in advance what their answer is actually going to be, and
>> then argues against it.
>
>OK, I accept this as a valid criticism of me.
>
>I need to get into the habit of using the phrase "I'd be
>surprised if ..." Thus, I should've written:
>
>"I'd be surprised if MoeBlee accepts this answer, because ..."

The above is just as bad.

Either way you are then arguing about a hypothetical answer
that the other person never gave, since you never bothered
to wait for a response. After all, you know them so well
that you can answer for them, right?

It's presumptuous and disrespectful.

quasi

[quasi]

quasi wrote:
>RussellE wrote:
>>quasi wrote:
>>> quasi wrote:
>>>
>>> To recap, the following questions are unresolved:
>>>
>>> Using the successor function S(x) = x + 1,
>>>
>>>    (1) Is the field A of algebraic numbers a model of MA?
>>>
>>>    (2) Is C a model of MA?
>>>
>>>    (3) Is every finite field a model of MA?
>>>
>>>    (4) Is any subfield of R a model of MA?
>>
>>In previous threads it was proven that in any infinite model
>>of MA the predeccessor of 0 must be a non-standard natural
>>number.
>
>Can you give a link to the proof?

Russell?

I'm waiting for you to back up your claim.

Can you (or anyone else) give a link and/or sketch the proof
of the claim that the predecessor of 0 in an infinite model of
MA must be a non-standard natural number?

Alternatively, can someone directly answer the question I posed
as to whether the field C of complex numbers with S(x) defined
by S(x)=x+1 is a model of MA? If C is not a model of MA, what
is an example of a theorem of MA which is not satisfied in C?

quasi

[quasi]

On Thu, 29 Dec 2011 13:10:08 -0800 (PST), RussellE
<reas...@gmail.com> wrote:

>Ex( x ~= 0 and ( x=F(x) or S(x)=F(x) ) is true
>in every model of MA except the 0-model
>(the model where the only element is 0).

I don't believe the above is a theorem of MA.

You claim to have proved it. Let's see a proof.

quasi

[quasi]

On Wed, 28 Dec 2011 17:44:40 -0800 (PST), RussellE
<reas...@gmail.com> wrote:

>Does a countably infinite "even" model of MA have the
>same cardinality as a countably infinite "odd" model of MA?

Are really asking whether two countably infinite sets must
have the same cardinality?

You can't be serious.

>If so, wouldn't this mean there exists a bijection between
>an even number and an odd number?

Don't be ridiculous. You don't have a "number". What you have
are two sets with the same cardinality (both countably
infinite) one of which has a property that you call "even" and
the other has a property that you call "odd".

As an analogy, let A be the set of even integers and let B be
the set of odd integers. It's easy to exhibit a bijection from
A onto B, but such a bijection is _not_ "a bijection between
an even number and an odd number".

quasi

[quasi]

RussellE wrote:
>Tim Little wrote:
>>RussellE wrote:
>> >
>> > I define the universe of a model of MA to be odd if
>> > it satisfies AxEy(x=y+y) and I define the universe
>> > of a model of MA to be even if it satisfies Ex(x~=0
>> > and x+x=0).
>>
>> Can a model satisfy both?
>
>I don't think so.
>
>I think I can use the pigeonhole principle
>to show
>
>if there is more than one x
>such that x+x=0 (0+0=0 is a theorem
>of both MA and PA), then AxEy(x=y+y)
>must be false.

I'd like to see you prove the above claim.

>I can come up with tautologies that must
>be true in any model of MA or PA:
>
>AxEy(x=y+y) or ExAy(x~=y+y)

The above is kind of trivial -- what's your point?

>Ex(x~=0 and x+x=0) or Ax(x=0 or x+x~=0)

The above is also trivial.

I don't see what you are getting at.

>>  Is there a model of MA in which neither holds?
>> [A model which is neither even nor odd]
>
>Again, I don't think so.
>
>I think the pigeonhole principle proves:

>
>AxEy(x=y+y) -> Ax(x=0 or x+x~=0)

The pigeonhole principle proves it? Or you?

If it's you, let's see a proof.

quasi

[quasi]

RussellE wrote:
>
>I actually have two definitions for even and odd.
>The two definitions are not equivalent as far
>as PA is concerned.
>
>MA + AxEy(x=y+y) has infinite "odd1" models.
>MA + ExAy(x~=y+y) has infinite "even1" models
>
>MA+Ax(x=0 or x+x~=0) has infinite "odd2" models.
>MA+Ex(x~=0 and x+x=0) has infinite "even2" models.
>
>In MA, every odd1 model is also an odd2 model.

You make so many claims, but I don't see any proofs.

Can you actually prove your claim that "odd1" => "odd2"?

Or are they just conjectures?

If they are conjectures, that's fine, but then at least
label them as conjectures, not as claimed results.

>In PA, ExAy(x~=y+y) and Ax(x=0 or x+x~=0) are true.
>
>If I can show:
>
>Ax(x=0 or x+x~=0) -> AxEy(x=y+y)
>or
>ExAy(x~=y+y) -> Ex(x~=0 and x+x=0)
>
>then PA is inconsistent.

Dream on.

>I am pretty sure these statements are true in MA.
>The proofs almost certainly use Ex(S(x)=0).

As far as I can see by browsing this thread, you're running
quite a deficit of claimed results versus posted proofs.

quasi

[RussellE]

On Dec 31 2011, 5:00 pm, quasi <qu...@null.set> wrote:
> quasi wrote:
> >RussellE wrote:
> >>quasi wrote:
> >>> quasi wrote:
>
> >>> To recap, the following questions are unresolved:
>
> >>> Using the successor function S(x) = x + 1,
>
> >>>    (1) Is the field A of algebraic numbers a model of MA?
>
> >>>    (2) Is C a model of MA?
>
> >>>    (3) Is every finite field a model of MA?
>
> >>>    (4) Is any subfield of R a model of MA?
>
> >>In previous threads it was proven that in any infinite model
> >>of MA the predeccessor of 0 must be a non-standard natural
> >>number.
>
> >Can you give a link to the proof?
>
> Russell?
>
> I'm waiting for you to back up your claim.
>
> Can you (or anyone else) give a link and/or sketch the proof
> of the claim that the predecessor of 0 in an infinite model of
> MA must be a non-standard natural number?

Assume the predecessor of 0 is a standard natural number, z.
We know:

Ax( x =< z)

Since z is a standard natural number, the set of standard
natural numbers less than or equal to z must be finite.
If the predecessor of 0 is a standard natural number,
the model must be finite.

We can prove this with induction.

Let P(x) = ( (S0=0) -> x=0 )

P(0) is true in any model of MA and
Ax( P(x) -> P(S(x)) ) is true in any model.
By induction:

Ax( (S0=0) -> x=0 )
=
(S0=0) -> Ax(x=0)

Let P'(x) = ( (SS0=0) -> (x=0 or x=S0) )
Again, by induction:

(SS0=0) -> Ax( x=0 or x=S0 )

If the predecessor of 0 is a "numeral",
there exists a finite length proof that
the universe of the model is finite.
A numeral is a finite length term in MA
with the form SSS..S0.

> Alternatively, can someone directly answer the question I posed
> as to whether the field C of complex numbers with S(x) defined
> by S(x)=x+1 is a model of MA? If C is not a model of MA, what
> is an example of a theorem of MA which is not satisfied in C?

I don't know if complex numbers are a model of MA.
I think Dave Libert came up with a model of MA based
on complex numbers. I think he said his model could
not be well ordered.

[RussellE]

On Jan 1, 1:22 am, quasi <qu...@null.set> wrote:
> On Wed, 28 Dec 2011 17:44:40 -0800 (PST), RussellE
>

> <reaste...@gmail.com> wrote:
> >Does a countably infinite "even" model of MA have the
> >same cardinality as a countably infinite "odd" model of MA?
>
> Are really asking whether two countably infinite sets must
> have the same cardinality?

Yes.

> You can't be serious.

Question About Bijections
http://groups.google.com/group/sci.logic/browse_thread/thread/8b016e85a11ecf9/9cd1f247d0e13d35

Assume we have a countable non-standard model of PA.

Let X = {0,1,2,...,x-1} and Y={0,1,2,...,y-1}
where x and y are non-standard natural numbers
and x ~= y.

Is there a bijection between the sets X and Y?

If ZFC, both sets are countably infinite and there
is a bijection between them. If our non-standard
model of PA can prove there is a bijection between
X and Y then PA is inconsistent.

> >If so, wouldn't this mean there exists a bijection between
> >an even number and an odd number?
>
> Don't be ridiculous. You don't have a "number".

Yes I do. I can talk about the predecessor of 0.
If the predecessor of 0 is even then the model is odd.

> What you have
> are two sets with the same cardinality (both countably
> infinite) one of which has a property that you call "even" and
> the other has a property that you call "odd".
>
> As an analogy, let A be the set of even integers and let B be
> the set of odd integers.

Does set A have an even or odd number of elements?

> It's easy to exhibit a bijection from
> A onto B, but such a bijection is _not_ "a bijection between
> an even number and an odd number".

This only proves if A has an even number of elements
then B must also have an even number of elements.

We can use this as yet another definition of even and odd.
If A and B are disjoint and there is a bijection between them
then the set A union B has even cardinality.


Russell
- Zeno was right. Motion is impossible.