Modular Arithmetic is Uncomputable

RussellE

unread,

Sep 20, 2011, 10:17:50 PM9/20/11

to

Modular Arithmetic is Uncomputable

I have previously posted about Modular Arithmetic (MA).
http://groups.google.com/group/sci.logic/browse_thread/thread/cc493bc66033c9f/77a8b95554b551fd
MA has the same axioms as Peano Arithmetic (PA) except
the axiom Ax (S(x) ~= 0) is replaced with Ex (S(x) = 0).
http://en.wikipedia.org/wiki/Peano_axioms#First-order_theory_of_arithmetic

These are some of the things that have been proven about MA:

MA and PA differ by one axiom. Anything provable in PA
that does not use the axiom Ax (S(x) ~= 0) can also be
proven in MA.

We can prove MA has arbitrarily large finite models
using FOL with equality. It is easy to see MA has
finite models based on modular arithmetic.
http://en.wikipedia.org/wiki/Modular_arithmetic

The simplest model of MA is the 0-model:

U: {0}
S: {<0,0>} (S(0)=0)
+: {<0,0,0>} (0+0=0)
*: {<0,0,0>} (0*0=0)

The Compactness theorem says MA must have an
infinite model.
http://en.wikipedia.org/wiki/Compactness_theorem

The integers are not a model of MA.
For example, Lagrange's four square theorem can be
derived in both MA and PA. A negative number
can not be the sum of four squares.
http://en.wikipedia.org/wiki/Lagrange's_four-square_theorem

There are numerous theorems which are true of the
natural numbers but not true of the integers.
The Binomial theorem is another example.
http://en.wikipedia.org/wiki/Binomial_theorem

The universal set of any model of MA where z
is a standard natural number and S(z)=0 must
have a finite number of elements.

This can be proven with first order induction.
The following are theorems of both MA and PA:

[(0=0) and Ax(x=0 -> S(x)=0)]
-> Ax(x=0)

[(0=0 or 0=S(0)) and Ax((x=0 or x=S(0)) -> (S(x)=0) or S(x)=S(0))]
-> Ax(x=0 or x=S(0))

[(0=0 or 0=S(0) or 0=S(S(0))) and Ax(x=0 or ...)]
-> Ax(x=0 or x=S(0) or x=S(S(0)))

...

This proves any infinite model of MA is omega inconsistent.
http://en.wikipedia.org/wiki/%CE%A9-consistent_theory
Any infinite model of MA can prove Ax (S(x) ~= 0) when x is
limited to standard natural numbers.

Interpreting MA in a set theory like ZF is problematic.
Surprisingly, the axiom of infinity is not a problem in MA.
The univeral set of any model of MA contains 0 and
is closed under the successor function.

Defining successor is a problem. A standard definition
for successor in ZF is S(x) = x U {x}.
It is also standard to let the empty set represent 0
and ordinals represent natural numbers.
Substituting this interpretation into Ex (S(x) = 0)
gives us Ex (xU{x} = {}) which is inconsistent.

Any model of MA must have a "largest" natural number.
This is a serious problem for things like Godel numbering.

In fact, the natural numbers in a model of MA can't
be well ordered without additional axioms.

The standard definition of "<" does not work in MA.
(x < y) -> Ez (z~=0 and x+z = y)

Consider a model of MA with 4 elements: {0,1,2,3}.
We have 1 < 3 because 1+2=3 and 3 < 1 because 3+2=1.

Unlike PA, we can't use the successor function or
addition to order the natural numbers in MA.
This also means no model of MA is well founded.
http://mathworld.wolfram.com/AxiomofFoundation.html

If MA has an infinite model, such a model must have
a non-standard natural number, e, and S(e)=0.

http://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic
"Any countable nonstandard model of arithmetic has order type w + (w*
+ w) x n,
where w is the order type of the standard natural numbers, w* is the
dual order
(an infinite decreasing sequence) and n is the order type of the
rational numbers.
In other words, a countable nonstandard model begins with an infinite
increasing
sequence (the standard elements of the model). This is followed by a
collection
of "blocks," each of order type w* + w, the order type of the
integers.
These blocks are in turn densely ordered with the order type of the
rationals."

Tennenbaum's Theorem says no non-standard model
of arithmetic can be recursive.
http://philosophyandcomputation.wordpress.com/category/tennenbaums-theorem/

I am having a problem with Tennenbaum's Theorem.
Assume we have an infinite model of MA and this
model has a non-standard natural number, e,
and S(e) = 0.

How can addition for e be uncomputable?

By axiom we have e+S(e) = S(e+e) = e+0 = e.
We can prove in MA that every natural number has
a predecessor. This means I can prove addition
is computable for every predecessor of e.

What is the order type of an infinite model of MA?
We can no longer assume the "initial" sequence is
the standard natural numbers. The "initial" sequence
of any infinite model of MA is both descending and
ascending. And it can't be just the "initial" sequence.
It has to be the "terminating" sequence as well.
Which infinite "block" of order type (w* + w) are
0 and e members of?

What does inducion mean in an infinite model of MA?
We certainly can't talk about induction on omega.
We can't even define omega in MA.

A standard definition of omega is the intersection
of all inductive sets. An inductive set is defined
as having 0 as an element and being closed under
successor.
http://en.wikipedia.org/wiki/Inductive_set_(axiom_of_infinity)

The natural numbers in any model of MA contain 0
and are closed under successor. The intersection
of all inductive sets in MA is {0}.

The downward Löwenheim–Skolem Theorem says MA
must have an elementary substructure of size omega.
http://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem
What would this sub-structure look like?
It certainly can't have an order type of omega.

Internal Set Theory (IST) is designed to talk about
non-standard models of arithmetic. IST defines a new
predicate, st(x), which is true if and only if
x is a standard natural number.
st() can't be defined "internally".
http://en.wikipedia.org/wiki/Internal_set_theory

I define a new theory:
Standard Modular Arithmetic (SMA).
SMA has the same axioms as first order Peano Arithmetic
except Ax(S(x) ~= 0) is replaced with:

Ex (st(x) and S(x)=0)

where st(x) is true if and only if x is
a standard natural number.

Like MA, SMA has arbitrarily large finite models.
It is obvious SMA can not have an infinite model.
We already have a proof if st(z) and S(z)=0 then
the model has a finite number of natural numbers.

Consider the negation of the axiom above:

Ax (~st(x) or S(x) ~= 0)

It is easy to see this sentence must be true
in any infinite structure that might be a model
of MA or SMA.

Despite all of the problems with using ZF
as a meta-theory to talk about models of MA,
ZF proves MA and SMA both have infinite models.

Russell
- Zeno was right. Motion is impossible.

William Elliot

unread,

Sep 21, 2011, 4:44:13 AM9/21/11

to

On Tue, 20 Sep 2011, RussellE wrote:
> Modular Arithmetic is Uncomputable
>
> I have previously posted about Modular Arithmetic (MA).

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

> These are some of the things that have been proven about MA:
>
> MA and PA differ by one axiom. Anything provable in PA
> that does not use the axiom Ax (S(x) ~= 0) can also be
> proven in MA.
>
> We can prove MA has arbitrarily large finite models
> using FOL with equality. It is easy to see MA has
> finite models based on modular arithmetic.
>

> The simplest model of MA is the 0-model:
>
> U: {0}
> S: {<0,0>} (S(0)=0)
> +: {<0,0,0>} (0+0=0)
> *: {<0,0,0>} (0*0=0)
>
> The Compactness theorem says MA must have an infinite model.
>

> The integers are not a model of MA.

The non-negative integers are an infinite model of MA.

> For example, Lagrange's four square theorem can be
> derived in both MA and PA. A negative number
> can not be the sum of four squares.
>

> The universal set of any model of MA where z
> is a standard natural number and S(z)=0 must
> have a finite number of elements.
>
> This can be proven with first order induction.
> The following are theorems of both MA and PA:
>
> [(0=0) and Ax(x=0 -> S(x)=0)]
> -> Ax(x=0)
>

That is false in PA and can't be proven in MA, though you
may find a model of PA that satisfies that statement.

> [(0=0 or 0=S(0)) and Ax((x=0 or x=S(0)) -> (S(x)=0) or S(x)=S(0))]
> -> Ax(x=0 or x=S(0))
>

That is false in PA and can't be proven in MA, though you
may find a model of PA that satisfies that statement.

> [(0=0 or 0=S(0) or 0=S(S(0))) and Ax(x=0 or ...)]
> -> Ax(x=0 or x=S(0) or x=S(S(0)))
>

That is false in PA and can't be proven in MA, though you
may find a model of PA that satisfies that statement.

> This proves any infinite model of MA is omega inconsistent.

You have proved naught but ignorance.

> Any infinite model of MA can prove Ax (S(x) ~= 0) when x is
> limited to standard natural numbers.
>

There is a difference between proving and satisfying.

> Interpreting MA in a set theory like ZF is problematic.

No problem at all. Just use the axiom of infinity to construct
the finite ordinals and then in the usual fashion the integers
and finally subgroups of integers..

> Surprisingly, the axiom of infinity is not a problem in MA.

> The universal set of any model of MA contains 0 and

> is closed under the successor function.
>

How could it be otherwise?

> Defining successor is a problem. A standard definition
> for successor in ZF is S(x) = x U {x}.
> It is also standard to let the empty set represent 0
> and ordinals represent natural numbers.
> Substituting this interpretation into Ex (S(x) = 0)
> gives us Ex (xU{x} = {}) which is inconsistent.
>

You'll have to take a different approach.

> Any model of MA must have a "largest" natural number.

False, the finite ordinals are a model of MA.

> This is a serious problem for things like Godel numbering.
>

You take yourself too seriously. [snip]

Frederick Williams

unread,

Sep 21, 2011, 5:31:06 AM9/21/11

to

RussellE wrote:

>
> This proves any infinite model of MA is omega inconsistent.

What is an omega inconsistent model...

> http://en.wikipedia.org/wiki/%CE%A9-consistent_theory

... and what has that got to do with it?

> Any infinite model of MA can prove Ax (S(x) ~= 0)

A model can prove?

> when x is
> limited to standard natural numbers.

Confusions about theories and models abound in what is snipped.

--
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

David Libert

unread,

Sep 21, 2011, 3:50:07 PM9/21/11

to

RussellE (reas...@gmail.com) writes:

[Deletion]

>Any model of MA must have a "largest" natural number.
>This is a serious problem for things like Godel numbering.
>
>In fact, the natural numbers in a model of MA can't
>be well ordered without additional axioms.
>
>The standard definition of "<" does not work in MA.
>(x < y) -> Ez (z~=0 and x+z = y)
>
>Consider a model of MA with 4 elements: {0,1,2,3}.
>We have 1 < 3 because 1+2=3 and 3 < 1 because 3+2=1.
>
>Unlike PA, we can't use the successor function or
>addition to order the natural numbers in MA.

For linear orderings on MA models, we could consider just an
arbitrary set=theoretic linear ordering, or else one interacting with
the ring structure of the MA model:

[1] http://en.wikipedia.org/wiki/Ordered_ring

[1] writes:

>In abstract algebra, an ordered ring is a commutative ring R with
> a total order <=ค such that for all a, b, and c in R:
>
>if a <=ค b then a + c<=โค b + c.
>if 0 <=ค a and 0<=โค b then <= โค ab.

The one element MA models carries a ordered ring ordering, and this
is definable in the language of MA.

As in [1], no finite ring of size > 1 can have have an ordered ring
structure. For our MA models for 1 = S(0) : 1 = 1^2 so 1 > 0 so
an iteration of 1 additions make 0 > 0.

A finite MA model has a set theoretic linear ordering and this is
definable by enumeration on finitely many numerals, so in the
language of MA.

This settles orders of each sort and definability in finite MA
models.

Regarding infinite MA models I don't know. As you point out, the
obvious try at a definition doesn't work.

With AC in the background math, every set can be linearly ordered.
I don't know if all or some or none of infinite MA models can have a
ordering structure with an ordering.

Regarding set theoretic orders on an inifnite MA model, as above
these exist with AC.

What about a set theoretic ordering being definable in MA language?

Again, I can't rule out any of all, some or none.

One thing I have, from the background to the old articles about MA
models inside ZF models. An example such articles was

[2] David Libert "Re: Modular Arithmetic Is Consistent"
sci.logic Aug 3, 2011
http://groups.google.com/group/sci.logic/msg/a4e09154fff30b71

I never wrote about this next point in old articles, but I had it in
mind backing some of the claims I wrote then.

Suppose we have a model of ZFA, ZF with atoms, where the axioms we
add say the atoms are an MA model. S, +, * are in the language on
atoms and are allowed in ZFA's separation and replacement axioms.

Suppose also the inductions axioms of MA are strengthened to allow
also epsilon and quantifiers over sets, as well as the usual MA.

Then this theory, using the set theory part, can define a linear
ordering on the MA part of atoms.

That is not trivial. ZFA in general, with AC left off as it says,
can't prove there is a linear ordering on the atoms (if ZF is
consistent).

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

David Libert

unread,

Sep 21, 2011, 6:41:27 PM9/21/11

to

I just posted about orderings on MA models, set or ring theortic,
and definablilty in MA language or in set theory above MA.

Suppose we have a ordered ring, as

[1] http://en.wikipedia.org/wiki/Ordered_ring

The the psoitive elements by those axioms are closed under addition
of 1. So the non-negative elements satify the indunction premise, so
by MA induction are everything.

This contradicting properties of ordered rindsa of size > 1 from
[1].

So in all MA models of size > 1, no ordered ring ordering is
definable in MA language.

My parent article claimed this for finite models of size > 1, and
didn't settle infinite models as I do now (negatively).

Similarly, for MA models with full set theoretic induction inside ZF
models, there is no combined MA _ ZF definition of a ring ordering.
In fact, the MA induction can use a set theoretic parameter, so that
is an outright proof there is no ordered ring ordering on any
inductive MA model of size > 1.

(The set theoretic language can qantify over all possible ring
orderings so can state and prove such a claim. Over MA language
there is only the definable version.)

The parent article

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

already noted ZF over inductive MA defines set theoretic linear
ordering.

So ZF over inductive MA case is completely settled: set theoretic
and ring theoretic orders.

Just as [2], I still know nothing about MA definable set theoretic
orders over infinite models. As in [2], I still can't rule out any

of: all, some or none.

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

RussellE

unread,

Sep 21, 2011, 11:17:04 PM9/21/11

to

On Sep 21, 2:31 am, Frederick Williams <freddywilli...@btinternet.com>
wrote:

> RussellE wrote:
>
> > This proves any infinite model of MA is omega inconsistent.
>
> What is an omega inconsistent model...

I should have said MA is an omega inconsistent theory.

> >http://en.wikipedia.org/wiki/%CE%A9-consistent_theory
>
> ... and what has that got to do with it?
>
> > Any infinite model of MA can prove Ax (S(x) ~= 0)
>
> A model can prove?

Using ZF as a meta theory we can prove any infinite
structure satisfying the axioms of MA has the property
Ax (~st(x) or S(x)~=0)

where st(x) is true iff x is standard.

> > when x is
> > limited to standard natural numbers.

Russell
- 2 many 2 count

RussellE

unread,

Sep 22, 2011, 12:26:40 AM9/22/11

to

On Sep 21, 3:41 pm, ah...@FreeNet.Carleton.CA (David Libert) wrote:
> I just posted about orderings on MA models, set or ring theortic,
> and definablilty in MA language or in set theory above MA.
>
> Suppose we have a ordered ring, as
>
> [1] http://en.wikipedia.org/wiki/Ordered_ring
>
> The the psoitive elements by those axioms are closed under addition
> of 1. So the non-negative elements satify the indunction premise, so
> by MA induction are everything.
>
> This contradicting properties of ordered rindsa of size > 1 from
> [1].
>
> So in all MA models of size > 1, no ordered ring ordering is
> definable in MA language.
>
> My parent article claimed this for finite models of size > 1, and
> didn't settle infinite models as I do now (negatively).
>
> Similarly, for MA models with full set theoretic induction inside ZF
> models, there is no combined MA _ ZF definition of a ring ordering.
> In fact, the MA induction can use a set theoretic parameter, so that
> is an outright proof there is no ordered ring ordering on any
> inductive MA model of size > 1.
>
> (The set theoretic language can qantify over all possible ring
> orderings so can state and prove such a claim. Over MA language
> there is only the definable version.)

I think MA puts limits on how many ordering there can be.
Any finite model only has a finite number of order types.

> The parent article
>
> [2] David Libert "Re: Modular Arithmetic is Uncomputable"
> sci.logic, sci.math Sep 21, 2011
> http://groups.google.com/group/sci.logic/msg/8ade6712c2442c50
>
> already noted ZF over inductive MA defines set theoretic linear
> ordering.
>
> So ZF over inductive MA case is completely settled: set theoretic
> and ring theoretic orders.
>
> Just as [2], I still know nothing about MA definable set theoretic
> orders over infinite models. As in [2], I still can't rule out any
> of: all, some or none.
>
> --
> David Libert ah...@FreeNet.Carleton.CA

MA and PA differ by one axiom.

I find it interesting we lose well ordering just
by assuming the natural numbers are a ring.
This means we lose foundation too.

There was an interesting article in arxiv:
http://arxiv.org/PS_cache/arxiv/pdf/1109/1109.3103v1.pdf

I don't pretend to understand it, but it made me
realize many of the coding tricks that work in PA
won't work in MA. For example, MA places limits
on how we can encode sets of natural numbers.

What is the weakest theory that proves the
Compactness theorem?

William Elliot

unread,

Sep 22, 2011, 4:17:28 AM9/22/11

to

On Wed, 21 Sep 2011, RussellE wrote:

> What is the weakest theory that proves the
> Compactness theorem?

The propositional calculus.

unread,

Sep 22, 2011, 1:38:58 PM9/22/11

to

RussellE wrote:

> For example, Lagrange's four square theorem can be
> derived in both MA and PA.

Please derive Lagrange's four square theorem in MA. (I'd be impressed
to see you derive Lagrange's four square theorem in PA.)

MoeBlee

unread,

Sep 22, 2011, 2:43:24 PM9/22/11

to

On Sep 21, 11:26 pm, RussellE <reaste...@gmail.com> wrote:

> What is the weakest theory that proves the
> Compactness theorem?

Suppose we're concerned with the compactness theorem formulated in the
language of set theory.

Then the weakest theory to prove it is the theory whose only non-
logical axiom is the compactness theorem itself.

MoeBlee

MoeBlee

unread,

Sep 22, 2011, 2:38:30 PM9/22/11

to

On Sep 20, 9:17 pm, RussellE <reaste...@gmail.com> wrote:

> [(0=0) and Ax(x=0 -> S(x)=0)]
> -> Ax(x=0)

You might as well just write

S(0)=0 -> Ax x=0.

> Interpreting MA in a set theory like ZF is problematic.
> Surprisingly, the axiom of infinity is not a problem in MA.

What do you mean by "not a problem" here?

> The univeral set of any model of MA contains 0

WRONG. There are models of MA in which 0 is not a member of the
universe.

> and
> is closed under the successor function.

WRONG. There are models of MA in which the universe is not closed
under the successor function.

> Defining successor is a problem. A standard definition
> for successor in ZF is S(x) = x U {x}.
> It is also standard to let the empty set represent 0

> Any model of MA must have a "largest" natural number.

There are models of MA in which the universe has no natural numbers at
all.

> IST defines a new
> predicate, st(x), which is true if and only if
> x is a standard natural number.

IST takes 'st' as a PRIMITIVE, not defined.

And 'st' applies to objects in general, not just natural numbers.

Also, truth is semantical, not specified by a THEORY but rather by
model. All theorems of a theory are true in any model of the theory.
But the theory itself doesn't specify the interpretation of a
predicate symbol.

> I define a new theory:
> Standard Modular Arithmetic (SMA).
> SMA has the same axioms as first order Peano Arithmetic
> except Ax(S(x) ~= 0) is replaced with:
>
> Ex (st(x) and S(x)=0)
>
> where st(x) is true if and only if x is
> a standard natural number.

That part about 'true' is not part of a definition of a theory. It
pertains to the semantics for a language.

The specification of a theory with a primitive predicate symbol 'st'
does not itself dictate the interpretationof 'st'. The interpretation
"true if and only if x is a standard natural number" is not part of
the theory. Moreover, PA does not define 'is a natural number'.

MoeBlee

unread,

Sep 22, 2011, 2:41:02 PM9/22/11

to

On Sep 21, 10:17 pm, RussellE <reaste...@gmail.com> wrote:

> Using ZF as a meta theory we can prove any infinite
> structure satisfying the axioms of MA has the property
> Ax (~st(x) or S(x)~=0)
>
> where st(x) is true iff x is standard.

No, we can't, because ZF doesn't have a predicate 'st' or 'standard'.
(Unless you specify in this context your definitions of those from the
language of ZF.)

MoeBlee

RussellE

unread,

Sep 22, 2011, 11:52:58 PM9/22/11

to

On Sep 22, 5:29 am, Frederick Williams <freddywilli...@btinternet.com>
wrote:

> Aatu Koskensilta wrote:
>
> > William Elliot <ma...@rdrop.com> writes:
>
> > > On Wed, 21 Sep 2011, RussellE wrote:
>
> > >> What is the weakest theory that proves the
> > >> Compactness theorem?
>
> > > The propositional calculus.
>
> > Why do you think the compactness theorem is a propositional tautology?
>
> He doesn't. There is just a confusion between compactness being true of
> T, and T' proving that compactness is true of T.

I didn't post the part about predicate calculus.

> Whether Russell wants to know what the weakest T is, or (given that T)
> what the weakest T' is, I don't know.

I want to know the weakest theory that can prove
the compactness theorem.
I think compactness requires epsilon induction.
http://en.wikipedia.org/wiki/Epsilon-induction

I am pretty sure MA doesn't allow epsilon induction.

RussellE

unread,

Sep 23, 2011, 12:02:38 AM9/23/11

to

On Sep 22, 5:26 am, Frederick Williams <freddywilli...@btinternet.com>
wrote:

> RussellE wrote:
> > There was an interesting article in arxiv:
> >http://arxiv.org/PS_cache/arxiv/pdf/1109/1109.3103v1.pdf
>
> > I don't pretend to understand it, but it made me
> > realize many of the coding tricks that work in PA
> > won't work in MA. For example, MA places limits
> > on how we can encode sets of natural numbers.
>
> On many, many occasions I challenged you to show how you could
> G\"odelize in MA.

Godel numbering fails in MA.
MA proves there are a finite number of primes.
Even in an infinite model of MA, the number
of primes would be equal to some natural number.
It might be a non-standard natural number.

RussellE

unread,

Sep 23, 2011, 1:23:04 AM9/23/11

to

On Sep 22, 11:38 am, MoeBlee <modem...@gmail.com> wrote:
> On Sep 20, 9:17 pm, RussellE <reaste...@gmail.com> wrote:
>
> > [(0=0) and Ax(x=0 -> S(x)=0)]
> > -> Ax(x=0)
>
> You might as well just write
>
> S(0)=0 -> Ax x=0.

This is based on the first order induction schema.

[P(0) and Ax( P(x) -> P(S(x))] -> Ax P(x)

where P(x) is some predicate.

In the expression above, P(x) is defined as x=0.
MA has a model where Ax x=0 is true and models
where it is false.

MA and PA have the same induction axiom schema.

> > Interpreting MA in a set theory like ZF is problematic.
> > Surprisingly, the axiom of infinity is not a problem in MA.
>
> What do you mean by "not a problem" here?
>
> > The univeral set of any model of MA contains 0
>
> WRONG. There are models of MA in which 0 is not a member of the
> universe.

The universe could be piles of grapes, but the model
has to define which pile of grapes represents the
constant 0.

> > and
> > is closed under the successor function.
>
> WRONG. There are models of MA in which the universe is not closed
> under the successor function.

Your model doesn't define a successor function?

> > Defining successor is a problem. A standard definition
> > for successor in ZF is S(x) = x U {x}.
> > It is also standard to let the empty set represent 0
> > Any model of MA must have a "largest" natural number.
>
> There are models of MA in which the universe has no natural numbers at
> all.
>
> > IST defines a new
> > predicate, st(x), which is true if and only if
> > x is a standard natural number.
>
> IST takes 'st' as a PRIMITIVE, not defined.

Yes. I assume st(x) is a predicate that is defined
as part of the model.

> And 'st' applies to objects in general, not just natural numbers.

Any object in the universal set represents a natural number
by definition.

> Also, truth is semantical, not specified by a THEORY but rather by
> model. All theorems of a theory are true in any model of the theory.
> But the theory itself doesn't specify the interpretation of a
> predicate symbol.

Yes.

> > I define a new theory:
> > Standard Modular Arithmetic (SMA).
> > SMA has the same axioms as first order Peano Arithmetic
> > except Ax(S(x) ~= 0) is replaced with:
>
> > Ex (st(x) and S(x)=0)
>
> > where st(x) is true if and only if x is
> > a standard natural number.
>
> That part about 'true' is not part of a definition of a theory. It
> pertains to the semantics for a language.

I assume st(x) is a predicate defined as part of the model.

> The specification of a theory with a primitive predicate symbol 'st'
> does not itself dictate the interpretationof 'st'. The interpretation
> "true if and only if x is a standard natural number" is not part of
> the theory. Moreover, PA does not define 'is a natural number'.

It doesn't have to. Every object in the universal set represents
a natural number by definition.
PA doesn't define "is a standard natural number".

Russell
- The universe is one dimensional

Frederick Williams

unread,

Sep 23, 2011, 6:40:26 AM9/23/11

to

RussellE wrote:
>
> On Sep 22, 11:38 am, MoeBlee <modem...@gmail.com> wrote:
> > On Sep 20, 9:17 pm, RussellE <reaste...@gmail.com> wrote:
> >
> > > [(0=0) and Ax(x=0 -> S(x)=0)]
> > > -> Ax(x=0)
> >
> > You might as well just write
> >
> > S(0)=0 -> Ax x=0.
>
> This is based on the first order induction schema.
>
> [P(0) and Ax( P(x) -> P(S(x))] -> Ax P(x)
>
> where P(x) is some predicate.
>
> In the expression above, P(x) is defined as x=0.

MoeBlee means

[(0=0) and Ax(x=0 -> S(x)=0)] -> Ax(x=0)

<->

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

by FOL. Induction not required.

> MA has a model where Ax x=0 is true and models
> where it is false.

Frederick Williams

unread,

Sep 23, 2011, 6:42:38 AM9/23/11

to

RussellE wrote:
>
> On Sep 22, 5:29 am, Frederick Williams <freddywilli...@btinternet.com>
> wrote:
> > Aatu Koskensilta wrote:
> >
> > > William Elliot <ma...@rdrop.com> writes:
> >
> > > > On Wed, 21 Sep 2011, RussellE wrote:
> >
> > > >> What is the weakest theory that proves the
> > > >> Compactness theorem?
> >
> > > > The propositional calculus.
> >
> > > Why do you think the compactness theorem is a propositional tautology?
> >
> > He doesn't. There is just a confusion between compactness being true of
> > T, and T' proving that compactness is true of T.
>
> I didn't post the part about predicate calculus.
>
> > Whether Russell wants to know what the weakest T is, or (given that T)
> > what the weakest T' is, I don't know.
>
> I want to know the weakest theory that can prove
> the compactness theorem.

The compactness theorem _of what_? Various deductive systems are
compact: propositional calculus, fol.

> I think compactness requires epsilon induction.

Why?

Frederick Williams

unread,

Sep 23, 2011, 6:45:34 AM9/23/11

to

RussellE wrote:
>
> On Sep 22, 5:26 am, Frederick Williams <freddywilli...@btinternet.com>
> wrote:
> > RussellE wrote:
> > > There was an interesting article in arxiv:
> > >http://arxiv.org/PS_cache/arxiv/pdf/1109/1109.3103v1.pdf
> >
> > > I don't pretend to understand it, but it made me
> > > realize many of the coding tricks that work in PA
> > > won't work in MA. For example, MA places limits
> > > on how we can encode sets of natural numbers.
> >
> > On many, many occasions I challenged you to show how you could
> > G\"odelize in MA.
>
> Godel numbering fails in MA.
> MA proves there are a finite number of primes.

It proves a falsehood?

> Even in an infinite model of MA, the number
> of primes would be equal to some natural number.
> It might be a non-standard natural number.

The non-standard natural numbers (in PA, I don't know about others) are
infinite.

Jesse F. Hughes

unread,

Sep 23, 2011, 8:25:48 AM9/23/11

to

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

> On Sep 22, 5:26 am, Frederick Williams <freddywilli...@btinternet.com>
> wrote:
>> RussellE wrote:
>> > There was an interesting article in arxiv:
>> >http://arxiv.org/PS_cache/arxiv/pdf/1109/1109.3103v1.pdf
>>
>> > I don't pretend to understand it, but it made me
>> > realize many of the coding tricks that work in PA
>> > won't work in MA. For example, MA places limits
>> > on how we can encode sets of natural numbers.
>>
>> On many, many occasions I challenged you to show how you could
>> G\"odelize in MA.
>
> Godel numbering fails in MA.
> MA proves there are a finite number of primes.

Show us that proof.

> Even in an infinite model of MA, the number
> of primes would be equal to some natural number.
> It might be a non-standard natural number.

--
Jesse F. Hughes
"She moaned, in pain and pleasure, as, in a confused whirlwind, she
glimpsed an image of Saint Sebastian riddled with arrows, crucified
and impaled." --Mario Vargas Llosa on category theory

MoeBlee

unread,

Sep 23, 2011, 10:40:04 AM9/23/11

to

On Sep 23, 12:23 am, RussellE <reaste...@gmail.com> wrote:
> On Sep 22, 11:38 am, MoeBlee <modem...@gmail.com> wrote:
>
> > On Sep 20, 9:17 pm, RussellE <reaste...@gmail.com> wrote:
>
> > > [(0=0) and Ax(x=0 -> S(x)=0)]
> > > -> Ax(x=0)
>
> > You might as well just write
>
> > S(0)=0 -> Ax x=0.
>
> This is based on the first order induction schema.

My point is that your formula is unnecssarily long. Mine is equivalent
to yours but without the unnecessary clauses.

> > > Interpreting MA in a set theory like ZF is problematic.
> > > Surprisingly, the axiom of infinity is not a problem in MA.
>
> > What do you mean by "not a problem" here?

No answer from you.

> > > The univeral set of any model of MA contains 0
>
> > WRONG. There are models of MA in which 0 is not a member of the
> > universe.
>
> The universe could be piles of grapes, but the model
> has to define which pile of grapes represents the
> constant 0.

The model maps the constant to some element of the universe. It is
wrong to say the ANY universe has 0 as a member. Rather, the universe
has some member that is mapped to by the constant '0' and that member
might or might not be 0 itself, depending on the model.

> > > and
> > > is closed under the successor function.
>
> > WRONG. There are models of MA in which the universe is not closed
> > under the successor function.
>
> Your model doesn't define a successor function?

The symbols of the language map to relations or functions (as the case
may be) on the universe of the model. It is not required that an
arbitrary model map a given symbol to the actual successor function on
the universe of the model.

> > > Defining successor is a problem. A standard definition
> > > for successor in ZF is S(x) = x U {x}.
> > > It is also standard to let the empty set represent 0
> > > Any model of MA must have a "largest" natural number.
>
> > There are models of MA in which the universe has no natural numbers at
> > all.

No answer from you.

> > > IST defines a new
> > > predicate, st(x), which is true if and only if
> > > x is a standard natural number.
>
> > IST takes 'st' as a PRIMITIVE, not defined.
>
> Yes. I assume st(x) is a predicate that is defined
> as part of the model.

Again, the SYMBOL 'st' is a primitive 1-place predicate SYMBOL of the
language for IST. A given model for the language maps the symbol 'st'
to some 1-place predicate on the universe of said model.

> > And 'st' applies to objects in general, not just natural numbers.
>
> Any object in the universal set represents a natural number
> by definition.

No, you're confused. You still don't know what a model is (nor what a
formal language is, for that matter) and your notion of "represents"
is only making it worse for you.

MoeBlee

unread,

Sep 23, 2011, 10:42:04 AM9/23/11

to

On Sep 22, 10:52 pm, RussellE <reaste...@gmail.com> wrote:

> I want to know the weakest theory that can prove
> the compactness theorem.

I told you what it is. It's the theory whose only non-logical axiom is

David Libert

unread,

Sep 23, 2011, 5:48:51 PM9/23/11

to

Previously in this thread I posted

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

[2] had followup:

[3] David Libert "Re: Modular Arithmetic is Uncomputable"

sci.logic, sci.math Sep 21, 2011

http://groups.google.com/group/sci.logic/msg/a4710efb8a0c2e61

This current article is a followup to [3], but will also reference
from [2].

In [2] I wrote:

> Suppose we have a model of ZFA, ZF with atoms, where the axioms we
>add say the atoms are an MA model. S, +, * are in the language on
>atoms and are allowed in ZFA's separation and replacement axioms.
>
> Suppose also the inductions axioms of MA are strengthened to allow
>also epsilon and quantifiers over sets, as well as the usual MA.
>
> Then this theory, using the set theory part, can define a linear
>ordering on the MA part of atoms.
>
> That is not trivial. ZFA in general, with AC left off as it says,
>can't prove there is a linear ordering on the atoms (if ZF is
>consistent).

[2] was unable to answer about such an ordering being definable just
in the MA model.

[3] noted the same question was still unanswered:

> Just as [2], I still know nothing about MA definable set theoretic
>orders over infinite models. As in [2], I still can't rule out any
>of: all, some or none.

I think I have just seen a solution. It defines the same ordering
from [2], but only uses the language of MA. It works in all MA
models. So it a theorem of MA, that this defines a linear ordering of
the MA universe.

Namely, we will be using Godel's beta function, just as Godel did
for PA.

[4] http://en.wikipedia.org/wiki/G%C3%B6del%27s_%CE%B2_function

The short version of the proof is Godel's proof didn't rest heavily
on the PA axiom 0 has no predecessor, and what Godel did for PA more
or less works for MA.

So we redo Godel's proof. (Big hand wave coming). and everything
is ok.

So we define a <= b iff there is a beta function coding of a finite
sequence with first element a, with each inside element of the
sequence the S of the one before it, with last element of the sequence
b, and with 0 not listed at any sequence element strictly intermediate
between the first and last postions.

Induction in MA proves this is a linear ordering, 0 is the smallest
element, every element x has immediate successor in the linear
ordering S(x), the predecessor of 0 ie the last element, and MA
supports foroofs by indutcion (by successor clause S) on this
ordering.

That is the same ordering I had defined in [2] with set theory if
set theory was available. The new trick here is to use Godel's beta
function to get the equivalent definition, and so work just from MA.

We can redo course of values primitive recusion on this ordering.
That is the successor clause of the deinftiion is allowed to use its
own function not merely on the immediate predecessor but any smaller
values.

A technicality to doing this:

I had previously posted about trying to define the zigzag 0-1-0-1
function, and what if you were in am MA model Z/n n odd:

[4] David Libert "Re: Modular Arithmetic Is Consistent"
sci.logic, sci.math July 12, 2011
http://groups.google.com/group/sci.logic1a1e6f9bacb14a5e/

[4] typoed that as n odd, I corrected later in the to odd.

[4] was noting what looked like a definition by primitive recursion
would have no such functions.

So instead make a modfied version of definition by primitive
recursion. We now say the inductive clause defines S(x) provided
S(x) ~= 0. We only require the inductive clause to apply to all x not
the predecessor of 0.

With this modified form we can do definitions by course of values
primitive recursion in MA.

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

RussellE

unread,

Sep 23, 2011, 10:11:39 PM9/23/11

to

I think we can get well ordering in MA by assuming 0
is the smallest natural number and using successor.
This would be an additional axiom.

Assuming 0 is not "intermediate" seems very close
to assuming 0 is the smallest natural number.
It is like you are including an assumption in
the definition of "<=".

> Induction in MA proves this is a linear ordering, 0 is the smallest
> element, every element x has immediate successor in the linear
> ordering S(x), the predecessor of 0 ie the last element, and MA
> supports foroofs by indutcion (by successor clause S) on this
> ordering.

I don't see how this works in an infinite model.
(Assuming MA has an infinite model.)
How are you defining 0 <= e where e is a
non-standard natural number?

> That is the same ordering I had defined in [2] with set theory if
> set theory was available. The new trick here is to use Godel's beta
> function to get the equivalent definition, and so work just from MA.
>
> We can redo course of values primitive recusion on this ordering.
> That is the successor clause of the deinftiion is allowed to use its
> own function not merely on the immediate predecessor but any smaller
> values.
>
> A technicality to doing this:
>
> I had previously posted about trying to define the zigzag 0-1-0-1
> function, and what if you were in am MA model Z/n n odd:
>
> [4] David Libert "Re: Modular Arithmetic Is Consistent"
> sci.logic, sci.math July 12, 2011
> http://groups.google.com/group/sci.logic1a1e6f9bacb14a5e/
>
> [4] typoed that as n odd, I corrected later in the to odd.
>
> [4] was noting what looked like a definition by primitive recursion
> would have no such functions.
>
> So instead make a modfied version of definition by primitive
> recursion. We now say the inductive clause defines S(x) provided
> S(x) ~= 0. We only require the inductive clause to apply to all x not
> the predecessor of 0.
>
> With this modified form we can do definitions by course of values
> primitive recursion in MA.
>
> --
> David Libert ah...@FreeNet.Carleton.CA

Russell
- Never never means never in set theory

Frederick Williams

unread,

Sep 24, 2011, 5:12:43 AM9/24/11

to

RussellE wrote:

> I think we can get well ordering in MA by assuming 0
> is the smallest natural number and using successor.
> This would be an additional axiom.

Do you mean that a/some/all model(s) of MA are well ordered?

> How are you defining 0 <= e where e is a
> non-standard natural number?

What does it mean: to define 0 <= e? Do you mean defining <=?

Sep 25, 2011, 7:16:26 AM9/25/11

to

RussellE wrote:
>
> On Sep 23, 5:25 am, "Jesse F. Hughes" <je...@phiwumbda.org> wrote:
> > RussellE <reaste...@gmail.com> writes:

> > > MA proves there are a finite number of primes.
> >
> > Show us that proof.
>
> First, we would have to define "prime number" in MA.
> Then we could prove "there are an infinite number of primes"
> is NOT a theorem of MA.

Depending who "we" is, yes, but that would be a meta-theorem, and it has
no relevance to your claim.

> [...]

>
> Even in PA I think we can prove the number
> of primes is less than or equal to the number
> of natural numbers.

Prove it then.

David Libert

unread,

Sep 25, 2011, 9:42:38 AM9/25/11

to

RussellE (reas...@gmail.com) writes:

> On Sep 23, 5:25=A0am, "Jesse F. Hughes" <je...@phiwumbda.org> wrote:
>> RussellE <reaste...@gmail.com> writes:

>> > On Sep 22, 5:26=A0am, Frederick Williams <freddywilli...@btinternet.com=

>>
>> > wrote:
>> >> RussellE wrote:
>> >> > There was an interesting article in arxiv:
>> >> >http://arxiv.org/PS_cache/arxiv/pdf/1109/1109.3103v1.pdf
>>
>> >> > I don't pretend to understand it, but it made me
>> >> > realize many of the coding tricks that work in PA
>> >> > won't work in MA. For example, MA places limits
>> >> > on how we can encode sets of natural numbers.
>>
>> >> On many, many occasions I challenged you to show how you could
>> >> G\"odelize in MA.
>>
>> > Godel numbering fails in MA.
>> > MA proves there are a finite number of primes.
>>
>> Show us that proof.
>
> First, we would have to define "prime number" in MA.
> Then we could prove "there are an infinite number of primes"
> is NOT a theorem of MA. A theorem of MA must be true
> in all models of MA. Consider the 0-model.

> We can prove S(0) -> Ax x=3D0. Since the 0-model

> has a finite number of elements, it can't have an
> infinite number of primes.
> (Assuming we require primes to be natural numbers)

In PA we define a prime p is a number with only itself and 1 as
factors.

To generallize this definition to Z, we must also mention -1, -p as
factors.

In a general ring, x is defined to be a unit iff exists y x*y = 1.

In Z the only units are 1 and -1, and to define p prime we need
only list factors as only those units and p and -p = p * the other unit.

In general rings, there can be more units than 1, -1.

So in general rings standard definitions are more general than
similar definitions of prime in PA or in Z.

I wrote about this in an old JSH thread, where similar points came
up:

[1] David Libert "Re: FLT Proof: Simple analogy"
sci.math Sep 19, 2000
http://groups.google.com/group/sci.math/msg/fde172d0ff8b8f0b

In [1] I wrote:

> We will be working now in commutative rings with unit element 1.
>These definitions come from Hungerford _Alegebra_ .
>
>Def: An element of such a ring is defined to be a unit iff it has a
>multiplicative inverse (ie something that multiplies by it to give 1).
>
>Def: An element a is defined to be irreducible iff
>a != 0 & a is not a unit &
> for all b,c if a = b*c then b is a unit or c is a unit
>
>Def: for a,b elements a|b ("a divides b") iff
>a != 0 & there exists c s.t. b = a*c
>
>Def: An element a is defined to be prime iff
>a != 0 & a is not a unit &
> for all b,c a|(b*c) -> a|b or a|c
>
> In Z, the ring of integers, an integer is prime <-> it is
>irreducible.
>
> In elementary number theory, the common definition of the word "prime"
>is closest to the ring theory definition of irreducible. But this is
>not too significant in view of the last equivalence.
>
> The Z equivalence of irreducible to prime breaks down in other rings.
>I cite examples from Hungerford.
>
> In Z/(6) (Z mod 6) 2 (or more accurately [2]), is prime but
>not irreducible. (Ie: not irreducible: 2 = 2*4 and neither of these
>are units).
>
> The next example is the important one for the point of this article
>about James' proof.
>
> This comes from an exercise in Hungerford. Consider R = Z[sqrt(10)].
>Hungerford's excercise includes that in R 2, 3, 4+sqrt(10), 4-sqrt(10)
>are each irreducible. On the other hand
>2*3 = 6 = (4+sqrt(10)) * (4-sqrt(10)) and this suffices for showing
>each of 2, 3, 4+sqrt(10), 4-sqrt(10) nonprime.
>(Ie, for example 2| ((4+sqrt(10)) * (4-sqrt(10))) and then also verify
>2 doesn't divide either of these factors. Similarly for showing the
>other three nonprime.)

Define a sequence of rings R_n for n in omega:
R_n = Z/(2*3^n - 1).

Let c be a new individual constant. In R_n let c denote 3^n.

In R_n, 2*3^n -2 is "-1", For n = 1, 2*3^1 -2 = 5. As n>1
2*3^n -2 only gets bigger. So for n>1 "2" in R_n is never "1" or
'-1".

For n >= 1, 3^n > 2, so 2^3^n -2 > 3^n. So for n > 1
c in R_n "3^n" is never "-1" .

Also 3^n < 2*3^n -2 for n > 1, so "3^" is never "1" in
R_n, so n >= 1.

So for R_n, n> 1, "2" and "c" are each ~= "1", "-1".

In all R_n "2" * "c" = 1. Ie R_n = Z/(2*3^ -1).

So for n>1, R_n satisfies "2", "c" are not "1", "-1" and
"2" * "c" = "1", ie 2 and c are both units.

So the theory of rings with new constant c and axioms "2" * c = 1
and "2", c are each ~= 1, -1 has abritrarily large finite modes
(R_n, n >= 1).

So by compactness there is an infinite MA model with 2, c each not
1, -1 but both units.

The definition of prime in Z was simple because 1, -1 were the only
units.

We just saw infinite MA models can have other units.

So let us continue with the general ring definitions of prime and
irredecible above:

>Def: An element a is defined to be irreducible iff
>a != 0 & a is not a unit &
> for all b,c if a = b*c then b is a unit or c is a unit

>Def: An element a is defined to be prime iff
>a != 0 & a is not a unit &
> for all b,c a|(b*c) -> a|b or a|c

As noted above prime and irreducible are equivalent in Z.
Or indeed any UFD (unique factorization domain).

[2] http://en.wikipedia.org/wiki/Unique_factorization_domain

Suppose p is prime in Z in the usual sense in Z, and p|n in Z.

Then in Z/n : p is irredible:

Suppose in Z/n, [p] = [a] * [b]. So there is i in Z so
p = a*b + i*n .

Since p|n, from last p| a*b in Z. So by p prime in Z, p|a or
p|b in Z.

Suppose without loss of generality p|a, let p = m * a' in Z.

So in Z/p, [p] = [a]*[b] = [m]*[a']*[b], so [a']*[b] = [1],
so [b] is a unit.

So [p]= [a]*[b] implies [b] is a unit, oor [a] is similarly a
unit if instead we assume p|b in Z.

So [p] is irredicible in Z/n as requred.

So next connsider rings R_n (new definition of R-n than above)
R_n = Z/2^(n+1). Let constant c be 2^n in R_n.

Then by the above in each R_n, [2] is irreducible.

Consider the theory MA and c is a new constant and 2 is
irreducible a schematum of axioms 2^m | c, each m > 1 and a
schematum of axioms there are at least m numbers in the universe.

This theory is finitely satisfiable by satisisfiable by R_n, n
greater than finitely many m's.

So it has a model, with 2 irredicible and all m m 2^m | c.

In a UFD, all finite powers of an irreducible can't divide the same
element c.

So some infinite MA models are not UFD.

So in the discussion below I will use both definitions prime and
irreducbible, since some infinite MA models are not UFD.

I argued above if p prime in usual sense in Z and p|n in Z
then [p] is irredicible in Z/n.

I claim under these hypothesis [p] is prime in Z/n:

Suppose [p] | [a]*[b] in Z/n. So there is i in Z so
p | (a*b + i*n).

But p|n, so p|a*b, so by usual primeness of p, p|a or p\b
in Z, so [p]|[a] or [p]|[b] in Z/n.

Now define a new sequence of rings R_n, n >=1. Let p1,p2, ...
enumerate ethe usual primes in Z.

Let R_n = Z/p1*p2* ... * pn.

Then for n<m, [pi] is prime and irreducible in R_n by above.

So the theory MA + the schematum "pi" is both prime and
irreducbible and the shematum "pi" ~= "pj" forr i ~= j
is finiteley satisfiable.

So there is an inifinite MA model where all "pi" are ~= and each is
both irreducible and prime.

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

RussellE

unread,

Sep 26, 2011, 12:18:02 AM9/26/11

to

On Sep 24, 6:06 pm, "Jesse F. Hughes" <je...@phiwumbda.org> wrote:
>
> >> > MA proves there are a finite number of primes.
>
> >> Show us that proof.
>
> > First, we would have to define "prime number" in MA.
> > Then we could prove "there are an infinite number of primes"
> > is NOT a theorem of MA.
>
> Oh, I'm sure "there are an infinite number of primes" is not a theorem
> of MA. But that's not what you said.
>
> You said that "There are a finite number of primes" *is* a theorem of MA.

I can't define "finite" in MA or PA.
I meant the number of primes is equal to some natural number.

> > A theorem of MA must be true
> > in all models of MA. Consider the 0-model.
> > We can prove S(0) -> Ax x=0. Since the 0-model
> > has a finite number of elements, it can't have an
> > infinite number of primes.
> > (Assuming we require primes to be natural numbers)
>
> > Even in PA I think we can prove the number
> > of primes is less than or equal to the number
> > of natural numbers.
>
> So, you're not going to show that MA proves there are a finite number of
> primes?

I will start by showing some models of MA having no primes.

I define Prime(z) as z~=S(0) and AxAy (x=S(0) or y=S(0) or x*y~=z).
Notice, S(0) can't be prime in this definition.

Consider the model of MA with 7 elements: {0,1,2,3,4,5,6}.
Prime(z) is false for every natural number in this model.

0=0*0 mod 7
1=S(0)
2=4*4 mod 7
3=2*5 mod 7
4=2*2 mod 7
5=2*6 mod 7
6=4*5 mod 7

This model has no primes.
I am pretty sure there are "infinite" models of MA with no primes.

Russell
- Zeno was right. Motion is impossible.

David Libert

unread,

Sep 26, 2011, 11:31:50 PM9/26/11

to

RussellE (reas...@gmail.com) writes:
> On Sep 24, 6:06=A0pm, "Jesse F. Hughes" <je...@phiwumbda.org> wrote:

[Deletion]

>> You said that "There are a finite number of primes" *is* a theorem of MA.
>
>
>I can't define "finite" in MA or PA.
>I meant the number of primes is equal to some natural number.

See my post

[1] David Libert "Re: Modular Arithmetic is Uncomputable"
sci.logic, sci.math Sep 25, 2011
http://groups.google.com/group/sci.logic/msg/88c840a0506ca226

[Deletion]

>I will start by showing some models of MA having no primes.
>
>I define Prime(z) as z~=S(0) and AxAy (x=S(0) or y=S(0) or x*y~=z).
>Notice, S(0) can't be prime in this definition.
>
>Consider the model of MA with 7 elements: {0,1,2,3,4,5,6}.
>Prime(z) is false for every natural number in this model.
>
>0=0*0 mod 7
>1=S(0)
>2=4*4 mod 7
>3=2*5 mod 7
>4=2*2 mod 7
>5=2*6 mod 7
>6=4*5 mod 7
>
>This model has no primes.
>I am pretty sure there are "infinite" models of MA with no primes.

Yes. Any positive prime integer p has no common factors with the
numbers 1, 3, ... , p-1. So Each of these has GCD of 1 with p.

There is the Euclidean algorithm, to express the GCD of 2 integers
as an integer linear combination of those 2 numbers:

[2] http://en.wikipedia.org/wiki/Euclidean_algorithm

So for i in 1, ... , p-1, there are integers a, b such
that:

1 = a*i + b*p.

So in Z/p, [1] = [a]*[i].

Ie each element [i] of Z/p has a multilpicative inverse [a].

This proves the well known fact, fpr p prime in integers, Z/p
is a field.

Writing [j]^-1 as the multipicative inverse in Z/p, each [i] in
Z/p can be factored:

[i] = [i*j] * [j]^-1 in Z/p for p-1 choices of j ~= 0.

Z/p being a field [i*j] are ~= for different j values.

For p > 2 [1] and [-1] are not equal.

As j varies over p-1 values, there are 4 cases where one of
[i*j] or [i] is one of [1] or [-1]. These 4 cases are distinct
for [i] ~= [1] or [-1].

(Ie: if [1] ~= 1 or -1, then if one of the 2 factors is [1] or
[-1], the other can't be either [1] or [-1], otherwise the factors
would multiply to [1] or [-1] and not be [i] by assumption.)

So if p > 5, then p-1 > 4, and there is some pair of factors
[i*j], [j]^-1 multipyling to [i] ~= [1], [-1], with neither factor
[1] or [-1].

Also for such a pair of factors, since each facotor is not [1] or
[-1], the other factor is not [i] or [-1].

So for each [i] not [1] or [-1], we found a factoring for it
showing [i] is not prime. Ie a factoring where no factor is any of
[i], [-i], [1], or [-1].

This shows by the usual definition of primes like in Z, these Z/p
for p prime > 5 have no prime factors.

Also as above, these are all fields, so the quadratic equation
x^2 - 1 = 0 has at most 2 roots, which are [1] and [-1]. So there
are no other units besides [1] and [-1], so each [i] is not
irreducible by the ring theory defintion as from [1].

You noted this property for Z/7. I have been claiming it also holds
for Z/p for any prime p >= 7. And also the stronger proerty of having
no irreducibles.

So the theory MA + there are no irredicibles has arbitrarily large
finite models (Z/p for p prime > 5),

So by compactness it has an infinite model. An infinite MA model
with no irrducibles. As you conjectured above for primes. This is
even stronger.

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

RussellE

unread,

Sep 27, 2011, 3:30:24 AM9/27/11

to

On Sep 26, 8:31 pm, ah...@FreeNet.Carleton.CA (David Libert) wrote:

> David Libert ah...@FreeNet.Carleton.CA- Hide quoted text -

>
> - Show quoted text -

Thanks!
I guess Godel numbering isn't going to work in
a model with no primes. Can MA prove its
own consistency without being inconsistent?

I have been wondering about the cardinality of these
infinite models of MA. We have been discussing
countably infinite models though I think we are
abusing the word "countable".
MA must also have uncountable models.
I don't see how MA can even define the
real numbers. What would an uncountable
model of MA look like?

I don't think the carrier set of any model of MA
bijects with the carrier set of any other size model.
This is certainly true for finite models and I don't
see why it isn't also true for infinite models.
For example, can I biject a model with no primes
into a model with lots of primes?

Wouldn't this mean every model
of MA has a different cardinality,
even the infinite models?

Frederick Williams

unread,

Sep 27, 2011, 3:45:08 AM9/27/11

to

RussellE wrote:
>
> [...] Can MA prove its

> own consistency without being inconsistent?

MA cannot even express "MA is consistent".

Frederick Williams

unread,

Sep 27, 2011, 4:01:14 AM9/27/11

to

RussellE wrote:
>
> [...]

> For example, can I biject a model with no primes
> into a model with lots of primes?

What do you mean by biject? To me, "bijection" means that structure is
preserved. Does your "biject"-ing preserve structure, and if so, what?

Tim Golden BandTech.com

unread,

Sep 27, 2011, 10:00:50 AM9/27/11

to

On Sep 20, 10:17 pm, RussellE <reaste...@gmail.com> wrote:
snip

> Defining successor is a problem. A standard definition
> for successor in ZF is S(x) = x U {x}.
> It is also standard to let the empty set represent 0

> and ordinals represent natural numbers.
> Substituting this interpretation into Ex (S(x) = 0)
> gives us Ex (xU{x} = {}) which is inconsistent.

>
> Any model of MA must have a "largest" natural number.

> This is a serious problem for things like Godel numbering.
>
> In fact, the natural numbers in a model of MA can't
> be well ordered without additional axioms.
>
> The standard definition of "<" does not work in MA.
> (x < y) -> Ez (z~=0 and x+z = y)
snip

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

The usage of the '<' operator is likwise problematic for
multidimensional spaces. Why should we enforce any universal order of
the cartesian instance
( 1, 2, 3 ) < ( 3, 1, 2 ) ?
where these values are real and orthogonal so that the representation
is a familiar 3D comparison of these positions in space. Neither are
these positions equal, and so the desire to maintain a one dimensional
ordering on elements which are not one dimensional, but which do have
some natural order, is not sensible. Thus you are essentially
admitting that the modulo numbers do not carry any dimensional
meaning. There is nothing wrong with that. They are actually a tool
that is useful in constructing dimensional meaning. For instance the +
and - signs of the real number carry on a modulo two relationship, and
we readily take the real number as one dimensional. As I am sure most
of you know there do exist three-signed numbers (P3) whose dimension
is one higher than the two-signed reals, and are a natural build of
the complex numbers, though in a new format:
http://bandtech.com/polysigned
So the MA construction does not have to remain solo in its usages. By
marrying the modulo numbers to other forms we get into new situations
that are more meaningful, and in that many of these applications will
be multidimensional then the inequality will not be useful except when
arbitrarily imposed, which I believe you do have the option to do
within MA. Particularly with regard to operators there do exist
identity elements within MA and these unique values form group
generators for the entire set or string as addition or multiplication
operators. Within polysign the signed product of two values
( s1 x1 )( s2 x2 ) = ( s1 + s2 ) x1 x2
exposes the blurry relationship, where s are the modulo sign
components and x is magnitude. The product is the sum within this
modulo interpretation.

To me the most relevant symbolism that I believe needs to be
introduced to your MA construction is the breakage of the successor
sequence such as
0, 1, 2, 0, 1, 2, 0, 1, 2, ...
to the more efficient
; 0, 1, 2 :
or some such notation which implies the loop connection. It's a pity
that the term 'ring' was stolen already, whose meaning does not ring
at all. This is much more a ring expression than abstract algebra will
ever have with its nauseating polynomials of infinite length but
finitely so... so wrong is the modern view and here you are studying
the base of its replacement. The finite form is all that is necessary
and to attempt to construct low dimension systems from infinite
dimension will never ring so well as your MA basis does.

- Tim

David Libert

unread,

Sep 27, 2011, 4:07:37 PM9/27/11

to

I posted here

[1] David Libert "Re: Modular Arithmetic is Uncomputable"

sci.logic, sci.math Sep 26, 2011
http://groups.google.com/group/sci.logic/msg/c8f157ba5e6e421b

This will add comments about [1]. This is a followup to [1].

In [1] I wrote:

> So the theory MA + there are no irredicibles has arbitrarily large
>finite models (Z/p for p prime > 5),
>
> So by compactness it has an infinite model. An infinite MA model
>with no irrducibles. As you conjectured above for primes. This is
>even stronger.

I realized later, all those Z/p are fields, so there is no obvious
argument to rule out the constructed infinite MA model above is a
field.

We could add to the base theory that it is field, and explicitly
construct the resulting infinite MA model to be a field.

In a field, everything is a unit.

So in a field example as above of an infinite MA model with no
irreducibles, everything is irreducible by virute of the trivial
excape clause of being a unit. Rather than the other possibility of
having a non-trivial factoring.

The construction literally does what I claimed, but for a trivial
reason.

It is still an example as you asked, no primes in your definition of
prime.

Can we get an infinite MA model with no irreducibles and some
non-units?

Any Z/p model produces only units as above.

Suppose we try a Z/p*c model, ie with modular p*c a composite
number with prime factor p.

I argued in [1] that if p|n then p is irreducicble in Z/n.
Actually I only checked the factoring clause.

In Z/p*c if [p]*[k] = [1], then p*k + j*p*c = 1 for some j.

But p | LS and ~ p | RS in Z.

So [p] is not a unit in Z/p*c.

[1] had previously checked the factoring property of [p] in Z/p*c.

So for p prime and c > 1, [p] is not a unit and doesn't factor
non-trivially ie as in [1], so [p] is irredicible.

So any composite n has Z/n with irreducibles.

So every finite MA model is either a field, or has no irreducibles.

My method in all articles so far has been to produce arbitrarily
large finite models of theories and apply compactness.

That method can't work to get an infinite MA model with non-units but no
irreducibles.

All the inifite MA models we saw before now were contructed by
compactness over finite models.

If every infinite MA model could be realized by a compacntess
argument over finite models, the observation above would show every
infinite MA model with units has irreducibles.

A similar construction, but more general, than compactness over
finite models is ultraproducts over finite models. Every construction
of an infinite model by compactness over finitie models can be
converted to a ultraproduct over finite models.

I have a new constructuction of an infinite MA model which is not
isomorphic to any ultraproduct over finite models.

This is based on a construction behind an old post of mine. My old
post only claimed results and didn't write out proofs.

I did later write some proof details in

[2] http://davesscribbles.wikispaces.com/matozfdetails

I don't know if there are any infinite MA models with non-units and
no irreducibles. Above is the blocks I faced to construct such a
model, or prove none exists.

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

David Libert

unread,

Sep 27, 2011, 8:35:34 PM9/27/11

to

I am posting this to retract some of my previous writing.

I will specify more fully below, but for the most part I can't
actually refute the old claims I made. It is instead that I see new
problems in the proofs I had in mind before.

So for the most part I am going from previously claiming something as
proved to saying I now don't definitely know yes or no: ie neihter
known proved nor refuted.

There are 3 older articles to mention.

The oldest one was

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

[1] discussed the issue of reconsidering the con() predicate as
usually defined in PA, just copy that predicate into MA and see what
happens in MA with this on various things.

[1] claimed to prove the 1 element MA model satisfies
~con(propositional logic) in this sense.

A later article, the one I wanted to mention next, was

[2] David Libert "Re: Modular Arithmetic Is Consistent"
sci.logic July 18, 2011
http://groups.google.com/group/sci.logic/msg/65cb85f7a4cb1776

I had had several articles about the con() question in MA, using
con() as Godel about PA. I don't mention them all now, but mention
[2] because it was my strongest claimed result along these lines.

I still mentioned [1] above, an earlier such article, because it lay
the groundwork for the later ones.

[2] claimed to prove that MA proves ~con(propositional logic).

[1] and [2] and all my articles about such con() questions used
Godel's beta functions, and the Godel style coding of sequences as
in PA. I thought and claimed there were no big problems copying this
sequence coding based on the beta function from PA to MA.

My last to mention here was earlier in this thread:

[3] David Libert "Re: Modular Arithmetic is Uncomputable"

sci.logic, sci.math Sep 23, 2011
http://groups.google.com/group/sci.logic/msg/f7fee80e3a9dc8c8

I am posting this as a followup to [3].

[3] claimed to define a linear ordering on the MA universe in MA.

[3] also used sequence coding based on the beta function.

I thought such sequence coding worked in MA like in PA. So my
proofs in [1]-[3] and the other con() articles built on that.

I now think it's a lot trickier, and the beta function acts weird in
MA.

I have thought some about the con() questions from [1]-[2], and am
now suspecting they may go these other way: MA proves con(PA), con(MA)
and con(prop). Just that in the chaos of the beta function going off
the rails that's the way everything lands. But I should state this as
a conjecture instead of a proof.

Regarding MA being able to define a linear ordering, I do not know.

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

RussellE

unread,

Sep 27, 2011, 9:50:22 PM9/27/11

to

I noticed your site had a page on Tennenbaum's theorem:
http://en.wikipedia.org/wiki/Tennenbaum's_theorem

I have been looking at Tennenbaum's_theorem and it
was the reason for the title of this post.
Tennenbaum's_theorem says addition and multiplication
can not be recursive in a non-standard model.
Basically it says addition and multiplication are
uncomputable in infinite models of MA.

I have been trying to prove some things using just MA
and FOL with equality. I think I can show MA has only
one model of any finite cardinality.

These are some theorems I can derive:

(S(0)=0) -> Ax (x=0) and (0+0 = 0) and (0*0 = 0)

This is enough to completely define the 0-model.
I have shown how we can prove this structure satisfies
the axioms of MA using only FOL w/= in:
http://groups.google.com/group/sci.logic/browse_thread/thread/cc493bc66033c9f/335591c2c560fc81

Consider a two element model.

(SS(0)=0) -> Ax (x=0 or x=S(0))
S(0)+0 = 0
S(0)*0 = 0

Again, these statements are axioms of MA (and PA).

We only need to define S(0)+S(0) and S(0)*S(0) to
completely define the two element structure.
Again, we can do this with theorems.

AxAy (x+S(y) = S(x+y))
let y=0
Ax (x+S(0) = S(x+0)=S(x))
Ax (x+S(0) = S(x))

Now I can derive:

(SS(0)=0) -> (S(0)+S(0) = SS(0) = 0)

A similar derivation proves
(SS(0)=0) -> (S(0)*S(0) = 0)

There is only one structure with two
elements satisfying the axioms of MA.
Since this can be done for any numeral,
there can only be one model for any
given numeral.

Obviously, addition is recursive in
all of these finite models. Doesn't
this mean compactness proves
there is an infinite model of MA
where addition is recursive?

If Compactness and Tennenbaum are
both theorems of ZFC then ZFC is
inconsistent.

Notice Wikipedia's proof of Tennenbaum's
theorem is a proof by contradiction.

RussellE

unread,

Sep 28, 2011, 3:04:27 AM9/28/11

to

> the axioms of MA using only FOL w/= in:http://groups.google.com/group/sci.logic/browse_thread/thread/cc493bc...

>
> Consider a two element model.
>
> (SS(0)=0) -> Ax (x=0 or x=S(0))
> S(0)+0 = 0
> S(0)*0 = 0

(SS(0)=0) -> Ax (x=0 or x=S(0))

S(0)+0 = S(0)

S(0)*0 = 0

>
> Again, these statements are axioms of MA (and PA).

These are theorems.

>
> We only need to define S(0)+S(0) and S(0)*S(0) to
> completely define the two element structure.
> Again, we can do this with theorems.
>
> AxAy (x+S(y) = S(x+y))
> let y=0
> Ax (x+S(0) = S(x+0)=S(x))
> Ax (x+S(0) = S(x))
>
> Now I can derive:
>
> (SS(0)=0) -> (S(0)+S(0) = SS(0) = 0)
>
> A similar derivation proves
> (SS(0)=0) -> (S(0)*S(0) = 0)

(SS(0)=0) -> (S(0)*S(0) = S(0))

>
> There is only one structure with two
> elements satisfying the axioms of MA.
> Since this can be done for any numeral,
> there can only be one model for any
> given numeral.
>
> Obviously, addition is recursive in
> all of these finite models. Doesn't
> this mean compactness proves
> there is an infinite model of MA
> where addition is recursive?
>
> If Compactness and Tennenbaum are
> both theorems of ZFC then ZFC is
> inconsistent.
>
> Notice Wikipedia's proof of Tennenbaum's
> theorem is a proof by contradiction.
>
> Russell

> - 2 many 2 count- Hide quoted text -

Frederick Williams

unread,

Sep 28, 2011, 7:00:23 AM9/28/11

to

RussellE wrote:

> Basically it [Tennenbaum's theorem] says addition and multiplication are

> uncomputable in infinite models of MA.

No it doesn't. Tennenbaum's theorem is about models of arithmetic.

> [...]

>
> If Compactness and Tennenbaum are
> both theorems of ZFC then ZFC is
> inconsistent.

Do you mean theorem _of_, or theorem _about_?

> Notice Wikipedia's proof of Tennenbaum's
> theorem is a proof by contradiction.

What? http://en.wikipedia.org/wiki/Tennenbaum%27s_theorem doesn't offer
a proof.

Tim Golden BandTech.com

unread,

Sep 28, 2011, 8:17:20 AM9/28/11

to

On Sep 27, 10:00 am, "Tim Golden BandTech.com" <tttppp...@yahoo.com>
wrote:

> On Sep 20, 10:17 pm, RussellE <reaste...@gmail.com> wrote:
> snip

Also the existence of the Predecessor function P() allows for a
familiar operator type of theory so that S() and P() are duals, but
these are Increment and Decrement type behaviors. In that Increment
and Decrement (S and P) are well behaved on any finite set of
elements, such as the four element set
; a, b, c, d :
where this notation implies the modular(modulo) behavior.

This is not such a bad instance of something that is close by to the
wavelet if we give ourselves the freedom to construct a real valued
finite set such as
; 1.23, 3.45, -5.2, 0.52 :
so that the positions are married now to values. These are the sorts
of constructions that I believe the modular arithmetic has its
strongest consequences upon. Of course I always seek physics in math
so I am not so puritanical as the language of MA wants us to be.
Extensions are of importance. The MA math is consistent and we use it
every day when we turn on our computers. These tend to be in terms of
8, 16, 32, or 64 bits of value representation, which within their
representations are using modulo two. Modular Arithmetic is plenty
computable.

- Tim

RussellE

unread,

Sep 29, 2011, 1:23:05 AM9/29/11

to

On Sep 28, 4:00 am, Frederick Williams <freddywilli...@btinternet.com>
wrote:

> RussellE wrote:
> > Basically it [Tennenbaum's theorem] says addition and multiplication are
> > uncomputable in infinite models of MA.
>
> No it doesn't. Tennenbaum's theorem is about models of arithmetic.

Its about non-standard models of arithmetic.
We know any infinite model of modular arithemetic
must have non-standard natural numbers.

> > [...]
>
> > If Compactness and Tennenbaum are
> > both theorems of ZFC then ZFC is
> > inconsistent.
>
> Do you mean theorem _of_, or theorem _about_?

Using ZFC as a meta-theory, if ZFC proves MA
has an infinite model where addition is recursive
and ZFC can prove Tennenbuam's theorem
then ZFC is inconsistent.

It is easy to show MA has arbitrarily large
finite models where addition is recursive.

> > Notice Wikipedia's proof of Tennenbaum's
> > theorem is a proof by contradiction.
>
> What? http://en.wikipedia.org/wiki/Tennenbaum%27s_theoremdoesn't offer
> a proof.

My mistake.
This is a link you posted a couple of years ago:
http://web.mat.bham.ac.uk/R.W.Kaye/papers/tennenbaum/tennenbaum.pdf

I don't pretend to understand the proof.
I see it talks about an initial segment of
a non-standard model of PA.
Any such initial segment could be used
as the carrier set for an infinite model of MA.

Frederick Williams

unread,

Sep 29, 2011, 7:03:14 AM9/29/11

to

RussellE wrote:
>
> On Sep 28, 4:00 am, Frederick Williams <freddywilli...@btinternet.com>
> wrote:
> > RussellE wrote:
> > > Basically it [Tennenbaum's theorem] says addition and multiplication are
> > > uncomputable in infinite models of MA.
> >
> > No it doesn't. Tennenbaum's theorem is about models of arithmetic.
>
> Its about non-standard models of arithmetic.
> We know any infinite model of modular arithemetic
> must have non-standard natural numbers.

Clearly you don't know what arithmetic is in the context of mathematical
logic. It is the theory of the natural number under various operations
and relations, _not_ the theory of equivalence classes of integers
modulo some integer under etc.

> > > [...]
> >
> > > If Compactness and Tennenbaum are
> > > both theorems of ZFC then ZFC is
> > > inconsistent.
> >
> > Do you mean theorem _of_, or theorem _about_?
>
> Using ZFC as a meta-theory, if ZFC proves MA
> has an infinite model where addition is recursive
> and ZFC can prove Tennenbuam's theorem

Tennenbaum's theorem is about models of arithmetic as described above,
it is not about models of MA. If (a version of) Tennenbaum's theorem is
true of models of MA, then the onus is on you to state and prove it.

> then ZFC is inconsistent.
>
> It is easy to show MA has arbitrarily large
> finite models where addition is recursive.
>
> > > Notice Wikipedia's proof of Tennenbaum's
> > > theorem is a proof by contradiction.
> >
> > What? http://en.wikipedia.org/wiki/Tennenbaum%27s_theoremdoesn't offer
> > a proof.
>
> My mistake.
> This is a link you posted a couple of years ago:
> http://web.mat.bham.ac.uk/R.W.Kaye/papers/tennenbaum/tennenbaum.pdf
>
> I don't pretend to understand the proof.
> I see it talks about an initial segment of
> a non-standard model of PA.
> Any such initial segment could be used
> as the carrier set for an infinite model of MA.

That doesn't show that Tennenbaum's theorem is true of MA (whatever
Tennenbaum's theorem might _be_ in that case).

Frederick Williams

unread,

Sep 29, 2011, 9:54:59 AM9/29/11

to

Frederick Williams wrote:
>
> [...] If (a version of) Tennenbaum's theorem is

> true of models of MA, then the onus is on you to state and prove it.

Sorry, that is unjustified. Something like this is what I should have
written:

If (a version of) Tennenbaum's theorem is true of models of MA, and if
you claim as much, then the onus is on you to state and prove it.

Tim Golden BandTech.com

unread,

Sep 29, 2011, 11:00:12 AM9/29/11

to

On Sep 28, 8:17 am, "Tim Golden BandTech.com" <tttppp...@yahoo.com>

wrote:
> On Sep 27, 10:00 am, "Tim Golden BandTech.com" <tttppp...@yahoo.com>
> wrote:
>
> > On Sep 20, 10:17 pm, RussellE <reaste...@gmail.com> wrote:
> > snip
>
> Also the existence of the Predecessor function P() allows for a
> familiar operator type of theory so that S() and P() are duals, but
> these are Increment and Decrement type behaviors. In that Increment
> and Decrement (S and P) are well behaved on any finite set of
> elements, such as the four element set
> ; a, b, c, d :
> where this notation implies the modular(modulo) behavior.

The rotational nature of these representations can be taken on the
unit circle within the 2D cartesian context, there being n nodes on
this circle. This is essentially a discrete loop context. The 2D
nature of the system is not actually necessary since theta is a
sufficient mapping, which is one dimensional or less, if we constrain
theta to non-negative values. This is of course within the standard
real valued type of analysis. Under this method an ordering does
exist, but the ordering can be labeled 'arbitrary' I believe.

It seems that if we engage a full characterization of operations on
particles within such a structure that we should entertain the winding
count, which is essentially a radix opportunity. As to how to
construct this, well, it takes many forms, and the old conundrums of
whether the identity element is rotating one full turn or zero turns
is a fine instance of choice.

Could there be another axiom of choice concept here?
If two options as this do exist then should they both be included
within the final theory? Under a unified principle I can see this
would be affirmed, and this is like saying that the zero sign as well
as the high identity sign do both exist within the system. This is
roughly how polysign are built now; there is no conflict with the
usage of both the '@' symbol (sign zero) and the '*' symbol (sign
three) within a P3 representation. They are not unique, yet under the
winding principle they could take on uniqueness in an outer context.
Here is an opportunity perhaps for a structure which seems arbitrary,
but if a pattern can be invoked upon it then maybe not so.

For instance within the P3 context we might consider
: @, -, +, * :
as the proper loop representation within the semi-traditional
sequence, the loop now attaching in a closed manner. The '@' and '*'
are redundant, but this same option exists in every modulo
representation. The rotational intent though is that '@' rotates zero
rotations, whereas '*' rotates one full rotation. This can only take
meaning within the outer context, which has not been constructed here
yet.

The natural spacetime representation
P1 P2 P3 | P4 P5 ...
where the '|' symbol denotes a natural breakpoint behavior of product
within the polysign numbers should reemerge hopefully from this new
construction, and nicely enough this poses the higher dimensions as
temporary, for we already know that they are not stable and will
decompose (dimensional collapse) at unique positions under product.
Still, this is merely a lead for a desirable behavior of a highly
structured math, and yet a math that will imply emergent spacetime
with unidirectional time.

It's a bit of a sidetrack to go into all of that here but back in the
loop context we see the traditional way of working into arbitrarily
large systems without the worry of confusion. Still, nobody ever has
worked successfully with infinity as a computable. I'm still for the
calculus sense of infinity, but on the loop this constructs a
continuum. Then in a traditional sense we are merely discussing
whether zero is equal to two pi.

- Tim http://bandtech.com/polysigned

MoeBlee

unread,

Sep 29, 2011, 11:44:27 AM9/29/11

to

On Sep 29, 12:23 am, RussellE <reaste...@gmail.com> wrote:

> We know any infinite model of modular arithemetic
> must have non-standard natural numbers.

Given any consistent theory whatsoever, there are models of that
theory such that the universe for the model has no natural numbers in
it and no non-standard natural numbers in it.

Moreover, given any theory that has an infinite model, given ANY
infinite set whatsoever, that set is the universe of some model of the
theory.

MoeBlee

RussellE

unread,

Sep 30, 2011, 12:05:32 AM9/30/11

to

On Sep 29, 6:54 am, Frederick Williams <freddywilli...@btinternet.com>
wrote:

> Frederick Williams wrote:
>
> If (a version of) Tennenbaum's theorem is true of models of MA, and if
> you claim as much, then the onus is on you to state and prove it.

Luckily, the consistency of PA doesn't depend on my
ability to prove Tennenbaum's theorem in MA.
This is a simpler description of the theorem:
http://www.logicmatters.net/resources/pdfs/TennenbaumTheorem.pdf

As you point out, it is not obvious Tennenbaum's theorem
even applies to models of MA. The proof in the link
requires two disjoint recursively enumerable sets
of natural numbers that are "recursively inseparable".
Only infinite sets can be recursively inseparable.

The proof also requires encoding sets of natural numbers
using primes. We have already seen the type of
problems we can encounter with primes in MA.

Tennenbaums theorem proves the standard
model of PA is the only model of PA where
addition is recursive.

The standard model of PA can not be
a model for MA.

If MA has an infinite model where addition is
recursive then this model is the initial sequence
of some non-standard model of PA.

Assume we have an infinite model of MA where
addition is recursive. For Tennebaums theorem
to apply, I would have to show there exists some
non-standard natural number that encodes a set
of natural numbers that "separates" a recursively
inseparable set.

I won't pretend I can show how to do this,
but I certainly have a lot of non-standard
natural numbers to choose from.

RussellE

unread,

Sep 30, 2011, 12:14:00 AM9/30/11

to

On Sep 29, 8:44 am, MoeBlee <modem...@gmail.com> wrote:
> On Sep 29, 12:23 am, RussellE <reaste...@gmail.com> wrote:
>
> > We know any infinite model of modular arithemetic
> > must have non-standard natural numbers.
>
> Given any consistent theory whatsoever, there are models of that
> theory such that the universe for the model has no natural numbers in
> it and no non-standard natural numbers in it.

I don't understand your point.
Yes, the universe can consist of bunches of bananas.
I agree bananas are not natural numbers.

Would you give examples of what you are talking about.

> Moreover, given any theory that has an infinite model, given ANY
> infinite set whatsoever, that set is the universe of some model of the
> theory.

The standard model of PA is also an infinite model of MA?

RussellE

unread,

Sep 30, 2011, 12:50:45 AM9/30/11

to

Maybe we can code sets of numbers in MA.
Instead of using primes we can use powers of two.
Let A and B be recursively enumberable sets
of standard natural numbers.

We can encode x e A as the sum of 2^x.
Next we have to show this sum is less than
the largest element in our model of MA.

I think this can be done with a rank argument.

Every x in A is a standard natural number.
In our model of MA, the standard natural
numbers are followed by an infinite number
of copies of the "integers" followed by
a copy of the negative "integers".

Any sum of natural numbers should be
fairly small compared to the huge number
of infinities in our infinite model of MA.

Frederick Williams

unread,

Sep 30, 2011, 5:54:23 AM9/30/11

to

RussellE wrote:
>
> [...]

>
> If MA has an infinite model where addition is
> recursive then this model is the initial sequence
> of some non-standard model of PA.

Surely _an_ initial sequence (supposing that I understand "initial
sequence") of _any_ model of PA is 0,1,2,...,x for x natural or omega.
Such a thing cannot be (the carrier of) a model of MA because 0 is not
the successor of anything.

Frederick Williams

unread,

Sep 30, 2011, 6:17:06 AM9/30/11

to

RussellE wrote:
>
> On Sep 29, 8:44 am, MoeBlee <modem...@gmail.com> wrote:
> > On Sep 29, 12:23 am, RussellE <reaste...@gmail.com> wrote:
> >
> > > We know any infinite model of modular arithemetic
> > > must have non-standard natural numbers.
> >
> > Given any consistent theory whatsoever, there are models of that
> > theory such that the universe for the model has no natural numbers in
> > it and no non-standard natural numbers in it.
>
> I don't understand your point.
> Yes, the universe can consist of bunches of bananas.
> I agree bananas are not natural numbers.
>
> Would you give examples of what you are talking about.

You've already done so yourself: since a bunch of bananas isn't a
natural number, it isn't a non-standard natural number. So your claim
at the top of this post is false.

> > Moreover, given any theory that has an infinite model, given ANY
> > infinite set whatsoever, that set is the universe of some model of the
> > theory.
>
> The standard model of PA is also an infinite model of MA?

You're confusing sets and models. Take an infinite set of bananas. Lay
them out in a line: put the first one in front of you, the next to its
right, the next to _its_ right, and so on. Let the first one model the
numeral 0, let the one to its right model s(0), let the one to _its_
right model s(s(0)), and so on.

You could take, in place of bananas, the elements of the underlying set
of the standard model of PA; but you would not necessarily be taking the
_structure_ of the standard model of PA. For example

number 10 might model numeral 0
" 4 " " " s(0)
" 11 " " " s(s(0))
and so on in some crazy fashion.

So to say that the underlying set of the standard model of PA (not "is"
but) maybe the underlying set of an infinite model of MA; is not the
same as saying the standard model of PA is also an infinite model of MA.

Ever thought of reading a book on model theory?

Frederick Williams

unread,

Sep 30, 2011, 9:37:43 AM9/30/11

to

Frederick Williams wrote:

> but) maybe the underlying set of an infinite model of MA; is not the

Pretend that "maybe" is may be" and that the semicolon isn't there.

MoeBlee

unread,

Sep 30, 2011, 12:38:56 PM9/30/11

to

On Sep 29, 11:14 pm, RussellE <reaste...@gmail.com> wrote:
> On Sep 29, 8:44 am, MoeBlee <modem...@gmail.com> wrote:
>
> > On Sep 29, 12:23 am, RussellE <reaste...@gmail.com> wrote:
>
> > > We know any infinite model of modular arithemetic
> > > must have non-standard natural numbers.
>
> > Given any consistent theory whatsoever, there are models of that
> > theory such that the universe for the model has no natural numbers in
> > it and no non-standard natural numbers in it.
>
> I don't understand your point.

My point is that your statement "We know any infinite model of modular
arithemetic must have non-standard natural numbers" is incorrect. Now,
there may be some context, some other tacit assumptions I'm not taking
into account, so that your statement would be okay in that context.
But, my point is merely that, for the record, your statement is
incorrect without some other qualification to it.

> Would you give examples of what you are talking about.

I'll give you the general prinicple, and every instance of that
priniciple is an example of it:

If a theory has an infinite model, then it has a model where there
universe is the set of natural numbers.

There are no non-standard naturals in the set of natural numbers.

Moreover, if a theory has an infinite model, then for ANY infinite
cardinality, the theory has a model with a universe of that
cardinality.

Moreover, if a theory has a model with cardinality k, then ANY set
with cardinality k is also the universe of a model of the theory.

So, if a theory has an infinite model, then ANY infinite set is the
universe of a model of the theory.

> > Moreover, given any theory that has an infinite model, given ANY
> > infinite set whatsoever, that set is the universe of some model of the
> > theory.
>
> The standard model of PA is also an infinite model of MA?

I didn't say that or anything equivalent to that. Read what I said
EXACTLY.

I'll put it to you again:

If you have a model M of a theory T, and M has an infinite universe,
then, for any infinite set S whatsoever, there is a model J of the
theory T in which S is the universe for J.

MoeBlee

RussellE

unread,

Sep 30, 2011, 7:12:41 PM9/30/11

to

Let MA be the theory. MA has an infinite model by compactness.
Let N be the set of all standard natural numbers.
There is a model of MA where N is the universal set?
An inifinte model of MA?

I would be very interested in which theorems
prove such a result.

Russell
- The universe is one dimensional.

RussellE

unread,

Sep 30, 2011, 9:31:53 PM9/30/11

to

On Sep 30, 2:54 am, Frederick Williams <freddywilli...@btinternet.com>
wrote:

RussellE

Oct 2, 2011, 10:38:27 PM10/2/11

to

[1] David Libert "Re: Modular Arithmetic is Uncomputable"

sci.logic, sci.math Oct 2, 2011
http://groups.google.com/group/sci.logic/msg/dec382ea29439809

posted the complex numbers C as a claimed MA model.

If [1] is correct we can make another example of an MA model, namely
the algebraic closure of countably many transcendentals.

C itself is the algebraic closure of a continuum size transcendence
base.

The new model is isomorphic to a submodel of C by taking the
algebraic closure of a countable subset of the trancendence base for
C.

That is an elementary substructure of C, so is still an MA model if
C was as claimed in [1].

I think this structure is isomorphic to a recursive structure as in
Tennebaum's theorem.

If so, this would be a counterexample to Tennebaum's theorem in
application to MA.

Define a formula in PA language to be Sigma_n (n > 0 in omega)
iff it is in prenex form with <= n blocks of alternating quatntofiers,
leading block existential quantifiers and matrix inside tose
unbounded quantifiers of bounded quantifiers of any amount and type.
No restriction on number of unbounded quantifiers repeated of same
type (existential, universal) quantifiers in a uniform
block, but total of at most n alternations.

Define Sigma_n PA to be PA with induction axioms on Sigma_n
formulas only.

Then any model of Sigma_n PA for any n can take modulus of any of
its members to define an MA model.

For nonstandard models of Sigma_n PA, if you take modulus on a
non-standard number, the MA model produced is an infinite MA model.

For each n > 0, there is an MA model produced this way as modulus
inside a Sigma_n PA model, which is not isomorphic to any modulus
model produced by a Sigma_m PA model for m > n, nor by a models model
of any PA model.

All MA models produced by compactness or ultraproducts on finite
structures are isomorphic to a modulus model from a PA model.

So by decreasing n we get new infinite MA models.

I think Tennebaum's theorem works for Sigma_1 PA.

If all above is ok, the newest model is an infinite MA model not
isomorphic to any modulus from any Sigma_1 PA model.

So that would be a yet newer one than the Sigma_n 's got over the PA
bsed models.

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

RussellE

unread,

Oct 3, 2011, 1:32:19 AM10/3/11

to

Yes, you are right. You can define a successor function as follows:
n = 2*n' if n is 0 or even
n = 2*n'-1 if n is odd
where n' is the number is the standard order and n is the number in MA
ordering.

This is order type w+w* where w is the standard
ordering of the non-negative integers and w*
is the order type of the negative integers.

And we can even have an infinite number
of copies of (w+w*) dense in the integers
and this can all be mapped to the standard
natural numbers.

Frederick Williams

unread,

Oct 3, 2011, 7:15:25 AM10/3/11

to

RussellE wrote:

>
> Yes, you are right. You can define a successor function as follows:
> n = 2*n' if n is 0 or even
> n = 2*n'-1 if n is odd
> where n' is the number is the standard order and n is the number in MA
> ordering.
>
> This is order type w+w* where w is the standard
> ordering of the non-negative integers and w*
> is the order type of the negative integers.

You define a function, and then you say "this is order type...". I
cannot follow a lot of your posts.

> And we can even have an infinite number
> of copies of (w+w*) dense in the integers

Please explain "dense in the integers".

> and this can all be mapped to the standard
> natural numbers.
>
> Russell
> - 2 many 2 count

RussellE

unread,

Oct 3, 2011, 9:31:05 PM10/3/11

to

On Oct 3, 4:15 am, Frederick Williams <freddywilli...@btinternet.com>
wrote:

> RussellE wrote:
>
> > Yes, you are right. You can define a successor function as follows:
> > n = 2*n' if n is 0 or even
> > n = 2*n'-1 if n is odd
> > where n' is the number is the standard order and n is the number in MA
> > ordering.
>
> > This is order type w+w* where w is the standard
> > ordering of the non-negative integers and w*
> > is the order type of the negative integers.
>
> You define a function, and then you say "this is order type...". I
> cannot follow a lot of your posts.
>
> > And we can even have an infinite number
> > of copies of (w+w*) dense in the integers
>
> Please explain "dense in the integers".

I shouldn't post late at night.
I meant "dense in the rationals" which is a quote
from the Wikipedia article on non-standard arithmetic:
http://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic

Even though we are assuming the standard natural numbers
are the universe of some model of MA, we can still prove
the predecessor of 0 can't be a numeral in the language of MA.
This is the reason I was confused about having the
standard natural numbers as an universe of MA.

I understand why the predecessor of any non-standard
natural number can't be a standard natural number.
If some predesseccor is a standard natural number
then we can prove the non-standard actually is standard.

I don't understand why a non-standard model needs
infinitely many copies of the integers "dense in the
rationals". I assume it has something to do with various
theorems of PA causing a contradiction if the model
were any simpler. Maybe Dave Libert or someone
could offer some explanations.

Even if the mapping I gave probably won't work
in MA, I want to at least define the mapping
properly. Let Sn mean applying the successor
function to 0 n times. Let Pn mean applying
the predecessor function to 0 n times.

Sn = 2n when n is even.
Pn = 2*n-1 when n is odd.

This maps the "non-negative integers" (in MA)
to even naturals (in PA) and the "negative
integers" (in MA) to the odd naturals (in PA).

I have been having fun with adding up all of
the natural numbers in a model of MA. Unlike PA,
some "infinite" sums can well defined in MA.
Start with the following observation:

P0+S0 = 0
P1+S1 = 0
P2+S2 = 0
...
Pn+Sn = 0

There are only two ways this progression can end:

Sx = Px which means the number of elements
in the universe is even and the sum of all natural
numbers is Sx.

Or, Sx=Px+1 which means the universe has
an odd number of elements and the sum is 0.

Neither of these two cases are possible
using the mapping above. We know all
Px are odd (in PA) and all Sx are even (in PA).
We can't have Sx=Px becuase such a
number would have to be both even and odd.
We can't have Sx=Px+1 because this means
the successor of some even number (in PA)
is an odd number (in PA).

I guess this means the universe of any infinite
model of MA using such a mapping must have
an odd number of elements. We can prove the
sum of all natural numbers in such a model is 0.

My original interest in MA was as a method to
prove PA is inconsistent. Now, I think MA could
be the basis for an Ultrafinite theory. MA doesn't
seem well suited for set theory, but maybe there
are ways to adapt set theory to suit MA.

Maybe not if Dave Libert is right and MA has
an infinite model that can't be linearly ordered.
The idea of an ill founded, unorderable, uncountable
set theory makes my head hurt.

Frederick Williams

unread,

Oct 4, 2011, 10:45:31 AM10/4/11

to

RussellE wrote:

> I meant "dense in the rationals" which is a quote
> from the Wikipedia article on non-standard arithmetic:
> http://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic

No it isn't. The phrase "dense in the rationals" does not appear in
that article. Any countable non-standard model of PA consists of a copy
of the non-negative integers followed by a number of copies of the
integers. That collection of copies of the integers is itself ordered
like the rationals. Of course the rationals are densely ordered, but
there are no rationals in the model.

Let it be noted that by "a copy of X" I mean a thing order isomorphic to
X.

> My original interest in MA was as a method to
> prove PA is inconsistent.

Since PA is consistent, you would seem to be wasting your time.

> Now, I think MA could
> be the basis for an Ultrafinite theory. MA doesn't
> seem well suited for set theory,

True, MA makes no mention of sets. There are no symbols for sets in its
language, and one cannot defined.

> but maybe there
> are ways to adapt set theory to suit MA.

Note that (if ZF, say, is consistent, and MA is consistent then) ZF + MA
is consistent.

> Maybe not if Dave Libert is right and MA has
> an infinite model that can't be linearly ordered.
> The idea of an ill founded, unorderable, uncountable
> set theory makes my head hurt.

There is no reason why a set theory in which MA's model theory is
discussed should be ill founded. What is an unorderable set theory?
One the universe of which cannot be ordered? Or one which cannot define
an order on its universe? What kind of order? What is an uncountable
set theory? A theory of infinite cardinality X is one with X-many
symbols for individuals (at least I think so, and if it isn't someone
will correct me). Do you mean one the universe of which is
uncountable? You could, I suppose, do your model theory in a theory of
sets with a finite universe; but why would you hobble yourself in that
way?

Aatu Koskensilta

unread,

Oct 4, 2011, 10:49:50 AM10/4/11

to

Frederick Williams <freddyw...@btinternet.com> writes:

> Note that (if ZF, say, is consistent, and MA is consistent then) ZF +
> MA is consistent.

Since the languages of ZF and MA have no symbols in common this holds
trivially. Did you perhaps have something more interesting in mind?

--
Aatu Koskensilta (aatu.kos...@uta.fi)

"Wovon man nicht sprechen kann, darüber muss man schweigen."
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

Frederick Williams

unread,

Oct 4, 2011, 10:58:12 AM10/4/11

to

Aatu Koskensilta wrote:
>
> Frederick Williams <freddyw...@btinternet.com> writes:
>
> > Note that (if ZF, say, is consistent, and MA is consistent then) ZF +
> > MA is consistent.
>
> Since the languages of ZF and MA have no symbols in common this holds
> trivially.

I know.

> Did you perhaps have something more interesting in mind?

No. I was responding to Russell's

but maybe there
are ways to adapt set theory to suit MA.

which I took to mean that he thought MA needed some special set theory
"to suit" it. I took "suiting" to mean--at the very least--joint
consistency. So I pointed out that ZF would do just fine.

But thank you for your quick response, because it now occurs to me that
really I have no good idea what "suiting" is in this context. Perhaps
Russell will enlighten us?

Frederick Williams

unread,

Oct 4, 2011, 11:17:11 AM10/4/11

to

Frederick Williams wrote:

> You could, I suppose, do your model theory in a theory of
> sets with a finite universe; but why would you hobble yourself in that
> way?

I surely meant

> You could, I suppose, do your model theory in a theory of

> sets with a _countable_ universe; but why would you hobble yourself in that

RussellE

unread,

Oct 4, 2011, 11:10:01 PM10/4/11

to

On Oct 4, 7:58 am, Frederick Williams <freddywilli...@btinternet.com>
wrote:
> Aatu Koskensilta wrote:

>
> > Frederick Williams <freddywilli...@btinternet.com> writes:
>
> > > Note that (if ZF, say, is consistent, and MA is consistent then) ZF +
> > > MA is consistent.
>
> > Since the languages of ZF and MA have no symbols in common this holds
> > trivially.
>
> I know.
>
> > Did you perhaps have something more interesting in mind?
>
> No. I was responding to Russell's
>
> but maybe there
> are ways to adapt set theory to suit MA.
>
> which I took to mean that he thought MA needed some special set theory
> "to suit" it. I took "suiting" to mean--at the very least--joint
> consistency. So I pointed out that ZF would do just fine.
>
> But thank you for your quick response, because it now occurs to me that
> really I have no good idea what "suiting" is in this context. Perhaps
> Russell will enlighten us?

My point is ZFC, and many other set theories, pretty much assume
PA is consistent. ZFC has the axiom of infinity, and the axioms of
union, pairing, powerset, etc, allow the creation of arbitrarily large
sets.

Why would I assume PA is consistent when we know PA is
inconsistent if PA proves PA has a model? MA can prove
MA has finite models. I have a lot more faith in the consistency
of MA than I do in the consistency of PA.

I don't see how anyone can even say the consistency of PA
is "obvious". Assuming PA is consistent means assuming
non-standard models of PA exists. It is one thing to say
the standard natural numbers exist. It is another to say these
monstrous non-standard structures exist.

Frederick Williams

unread,

Oct 5, 2011, 3:07:52 AM10/5/11

to

RussellE wrote:
>
> [...] MA can prove
> MA has finite models.

MA can't even express "MA has finite models". A model is (among other
things) an ordered n-tuple. You can't define "X is an ordered n-tuple"
in the language of MA. You can't define "X is finite" in MA.

> I don't see how anyone can even say the consistency of PA
> is "obvious". Assuming PA is consistent means assuming
> non-standard models of PA exists. It is one thing to say
> the standard natural numbers exist. It is another to say these
> monstrous non-standard structures exist.

MA has non-standard models too, that is to say models the universes of
which aren't a set of integers modulo an integer.

Frederick Williams

unread,

Oct 5, 2011, 4:13:22 AM10/5/11

to

RussellE wrote:

> This sum will be 2^w - 1 where
> w is omega. This looks like a
> big number, but it is not.

Is that ordinal or cardinal arithmetic in "2^w - 1"?

Frederick Williams

unread,

Oct 5, 2011, 4:14:53 AM10/5/11

to

RussellE wrote:

> Assume we have an infinte model of MA
> where addition is recursive.

Are you justified in that assumption? Please exhibit an infinite model
of MA, along with a recursive definition of addition in it.

MoeBlee

unread,

Oct 5, 2011, 10:39:07 AM10/5/11

to

On Oct 4, 10:10 pm, RussellE <reaste...@gmail.com> wrote:

> My point is ZFC, and many other set theories, pretty much assume
> PA is consistent.

Wrong. The consistency of PA is not an assumption (axiom) of ZFC.
ZFC proves the consistency of PA.

> ZFC has the axiom of infinity, and the axioms of
> union, pairing, powerset, etc, allow the creation of arbitrarily large
> sets.

So?

> Why would I assume PA is consistent when we know PA is
> inconsistent if PA proves PA has a model?

I don't know whether 'PA has a model' can be formulated in the
language of PA; but, yes, if PA proves 'PA is consistent' then PA is
inconsistent.

That doesn't contradict that PA is consistent.

> MA can prove
> MA has finite models.

Was that proven earlier? So 'MA has finite models' can be expressed in
the language of MA?

> I have a lot more faith in the consistency
> of MA than I do in the consistency of PA.

Okay. But that doesn't refute any reason for thinking that PA is
consistent.

> I don't see how anyone can even say the consistency of PA
> is "obvious". Assuming PA is consistent means assuming
> non-standard models of PA exists. It is one thing to say
> the standard natural numbers exist. It is another to say these
> monstrous non-standard structures exist.

Merely characterizing a mathematical object as "monstrous" is not much
of an argument. In any case, ANY theory that has a model has many
different models (many of them seemingly "odd"). That's not a reason
to think those theories are inconsistent.

Does MA have an infnite model? If so, then it has models of every
infinite cardinality. And it has lots and lots of very odd looking
models.

By the way, since you've shown that you're essentially ignorant and
confused about what a model is and about the basics of this subject,
I'm wondering whether you've given any thought to getting a textbook
in the subject so that you can inform yourself about it, though, I
suppose, it gives you more satisfaction just to keep compounding your
own ignorance and confusion.

MoeBlee

David Libert

unread,

Oct 6, 2011, 2:38:03 AM10/6/11

to

RussellE (reas...@gmail.com) writes:

[...]

>I shouldn't post late at night.
>I meant "dense in the rationals" which is a quote
>from the Wikipedia article on non-standard arithmetic:
>http://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic
>
>Even though we are assuming the standard natural numbers
>are the universe of some model of MA, we can still prove
>the predecessor of 0 can't be a numeral in the language of MA.
>This is the reason I was confused about having the
>standard natural numbers as an universe of MA.
>
>I understand why the predecessor of any non-standard
>natural number can't be a standard natural number.
>If some predesseccor is a standard natural number
>then we can prove the non-standard actually is standard.
>
>I don't understand why a non-standard model needs
>infinitely many copies of the integers "dense in the
>rationals". I assume it has something to do with various
>theorems of PA causing a contradiction if the model
>were any simpler. Maybe Dave Libert or someone
>could offer some explanations.

Those copies of the integers are what similar to what I was calling
Z-chains (my own made up term) in the old posts about infinite MA
models.

Note these are copies of the integers for the successor and
predecessor realtions. The + and * interpretations in the infinite MA
will not act like the familzr Z + and * on these copies.

The Wikipedia you mentioned notes a countable non-standard PA model
begins with a copy like omega on successors, then has a collection of
Z copies of integers for successor and predecessor ordered like the
rationals.

That is what you are asking above, why those copies of the integers
come ordered among themselves like the rationals.

I will prove that now.

PA defines the lonear ordering on its universe, so we have that in
our non-standard PA model.

In PA language it is not first order definable for a number to be
standard. But we are doing model theory above the PA model, so in
there we can define standard using the background notion of
finiteness. My proof is in the model theory above the model, and will
use that notion of standardness.

As a claim in such background above the model theory, I claim that
for all x < y memeber of the non-standard model, x, y are in the
same copy of Z <-> y-x is standard.

To see this: if x,y are in the same copy of Z, then there is a
finite interation (real finite, not just according to the model)
iteration of successors to get from x to y.

Then y-x = this finite iteration of S on 0, so y-x is standard.

And if y-x is standard, then y = x + (y - x) would be a finite
iteration of succesors above x and in the same Z copy.

If x < y and they are in different Z copies, then y - x is
non-standard. On the other hand, every x' in the same Z copy as x
with x < x' had x' - x standard, and so < non-standard y - x.

So x' is a shorter distance above x than y is. So x' < y.

Obviously any x' in the same Z copy as y with x' < x has
x' < y (transitivity).

So if x and y are in different Z copies, and you compared them and
found x < y, you would have gotten the similar answer x' < y
if you had picked any other x' instead of x from that Z copy with x.

Similarly, x < y means also x < y' for any altrernative pick to
y in the Z copy that had y.

So you can induce a linear ordering on Z copies, defined by the
smaller Z copy has eacjh of its memebers smaller than each member of
the larger Z copy.

This means to work with copies of Z and compare them, we can pick
which represetative examples to work with and use the order
realtions we get there.

PA proves by induction
all x exist y x = y + y or S(x) = y + y.

So now suppose we have 2 distinct Z copies. Pick a from the
smaller copy and b from the larger copty, so a < b.

I also want b - a = m + m for some m.

So if you picked a first choice b so there is no such m, replace
your b by new b = S(old b), this still represents the larger Z copy
but now has b - a = m + m for some m.

So one way or another we have a < b in the 2 Z copies, and
b - a = m + m for some m.

Could m be standard? If m were standard, then m + m would be
standard, so b - a would be standard, contrary to them coming from
different Z copies as assumed.

So m is non-standard.

So (a + m) - a = m is non-standard, and a + m is from
a different Z copy than a, indeed a larger Z copy than a's, since
a + m > a.

Also b - (a + m) = m is non-standard, so a + m and b are
from different Z copies, and again with b in the larger Z copy.

So the Z copy containing a and the Z copy containing b, have
between them the Z copy containing a + m, with that intermediate Z
copy wioth a + m distiinct from both original Z copies.

So every 2 Z copies have a third different Z copy lying strictly
between them.

Now consider a Z copy, containing a.

This is not the omeaga copy of finite succssors of 0, so a is
nonstandard.

I want to have a number m s.t. a = m + m.

If the first a we picked from our Z copy has no such m, repalce that
a by S(a).

So we end up with a in our Z copy and there is m so a = m + m.

If m were standard then m + m would be standard, contrary to a not
standard.

So m is not standard. So m is not contained in the omega copy
including 0, but in a Z copy.

m in this smaller Z copty and a in the arger one have a - m = m
non-standard.

So m and a are in different Z copies.

So every Z copy (ie one contaiing a) has a smaller Z copy below it
(one containing m).

Also given any Z copy containing a, consider the Z copy containing
a + a.

a was in a Z copy, so a was non-standard, so (a + a) - a = a
is non-satandard, so a and a + a are in different Z copies.

So every Z copy, ie containing a, has a different Z copy
(containing a + a), above it.

So we have shown above the Z copies are a linear ordering which is
dense (each distinct pair of Z copies has another Z copy strictly
between) and has no end points : no smallest Z copy and no largest
Z copy.

This is funny now. So much in these threads disses Cantor. Yet now
we bump up against another of his theorems. (By the way, I don't diss
Cantor, I have high respect for Cantor).

Cantor proves that any countable dense linear ordering without
endpoints is order isomorphic to the rationals.

So that's just what the doctor ordered to finish off our proof.

By the way, this proof so far is a nice example to help understand
better Tennebaum's theorem.

You were talking about these nonstandard PA models as being
complicated, by haviung a rational ordering of Z copies.

But to me that does not seem complicated. I think I understand the
rationals pretty well. So all this is realized as an easy to describe
construction.

You can draw an easy picture of it. Make a horizontal line on the
blackboard, with an abrupt clear left end, but the right end fades off
as you lifted the chalk away drawing it.

You have to explain this line is the rationals, not the reals that
someone couldn't tell by only looking. So as I say a picture.

Now draw a vertical line up over the left end point. That is the
omega copy above 0, and the left endpoint, under the vertical line
and left of all the points in the horizontal line, is 0.

Now draw a bunch of vertical lines interesecting the horizontal one.
Alas we can only actually draw in finitely many, but put in a bunch so
they look like a lot, and say that is actually infinitely many, one
for each rational number. The other vertical lines extend both up
and down by Z oredering instead of omega.

And the ordering is zigzag up those lines then shift sideways.

So the usual problems for a finite drawing to represent infinite
things. But this shows geomtrically and pictorially the chief
relation among the parts.

And we can also reconsider this more symbolically on integers.

Do pairing functions, so an integer codes a pair of integers.
Represent a rational number as a pair of integers in lowest terms.
So the rationals in the base can be a certain subset of omega.

Then we want to form the cartesian product, because the final model
was 2 d: vertical lines arranged horizontally.

Do another paring function on codes for the rationals as jujst said
and codes for integers into omega like in your post.

We can end up treating this model as on a certain subset of omega.

And in fact a recursive subset. But recursive subset we can biject
with all of omega by a reucrsive function.

We can reindex that way, so mkae the defined model be on all of
omega not just a subset.

To do that, we end up reindxing how PA's S function works. But
just reindxing over a rcurove function from omega onto our subset.

So the final version of "S" for the model we get is itself
recursive.

We have just redone that model into the form that Tennenbaum's
theorem said we can't do.

The difference is Tennenbaum's theorem was about "+" and "*"
interpreting as non-recursive functions.

I have not discussed that part above, only how to interpret "S".

But above says we can make simple recursive models for the "S" part.
Its only when we try to jazz up that model to "+" or "*" that the real
Tennenbaum's theorem kicks in.

So that is another measure of how this construction can be viewed as
simple.

Wikipedia above about non-standard models makes a similar point
about Tennenbaums theorem versus the simplicitky of "S".

Well, also our model is interepting the defined symbol "<" as well
in this recursive way.

And our discussion above showed every countable non-standard model
has an ismorphic form as above in recursive version for "S" and "<",
not merely some countable models.

We used Cantor's theorem about the rationals, and we also used
pairing functions on omega, which were also an invention of Canrtor.

You see how useful it is to have bijections. You could say that's
what Cantor was studying, these theorems of his are various ways to
work with bijections.

So he studied them systematically, getting many constructive
theorems on how to build them up.

And on the flip side when he couldn't find certain bijections he
gave proofs that none exist.

If those bijections are a useful tool to do things, as we just did
above, skirting on the edges of Tennenbaum's theorem, then it is also
useful to know the limits of those tools: to know when those methods
will break down.

Which information Cantor gave us too.

Too bad that Cantor's reward for such diligent work is to have a
chorus of voices in these news groups having a hissy fit.

Anyway, all this makes it very interesting, to see those two sides
in juxtapostion, the simplae model analysis for S, < versus
Tennenbaum's theorem on +, *.

It makes both sides more interesting, to see how they meet at that
boundary.

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

RussellE

unread,

Oct 6, 2011, 7:28:21 PM10/6/11

to

On Oct 5, 11:38 pm, ah...@FreeNet.Carleton.CA (David Libert) wrote:

> ...
>
> read more »- Hide quoted text -
>
> - Show quoted text -

Thank you! I think I understand this now.
For the record, I don't "diss" Cantor.
At least, I haven't for many years.
He was obviously a brilliant person.

I like concrete examples.
Assume we have a non-standard model of PA.
Let e be some non-standard natural number.
Let 1=S(0). We have 1 < e.

We also have AxEy ((x=y+y) or (x=S(y+y))).
You say this is a theorem of PA.
This means it could also be a theorem of MA.
From this we can derive:

(e-1 = m+m) or (e-1 = S(m+m))

Assume m is a standard natural number.
Then m+m+1=e proving e is standard.
Assume m is in the same chain as e.
Then e-m-m=1 proving 1 is in the same chain as e.
Therefore, m must be in a chain larger
than 1's chain and less than e's chain.

RussellE

unread,

Oct 6, 2011, 7:47:58 PM10/6/11

to

Dave Libert carefully proved if x < y and
x and y are in the same chain, then y-x
is "finite" (in the meta theory) meaning
SS...S(x) = y for some "finite" interation
of the successor function.

This is a necessary part of the proof
I forgot to include.

Russell
- Zeno was right. Motion is impossible.

RussellE

unread,

Oct 7, 2011, 12:03:03 AM10/7/11

to

On Oct 5, 11:38 pm, ah...@FreeNet.Carleton.CA (David Libert) wrote:

> RussellE (reaste...@gmail.com) writes:
>
> But above says we can make simple recursive models for the "S" part.
> Its only when we try to jazz up that model to "+" or "*" that the real
> Tennenbaum's theorem kicks in.
>
> So that is another measure of how this construction can be viewed as
> simple.
>
> Wikipedia above about non-standard models makes a similar point
> about Tennenbaums theorem versus the simplicitky of "S".

I think we can prove successor can't be
recursive in infinite models of MA.

Define a recursive mapping
of numbers in an infinite model of MA
to the numbers in a standard PA model:

Let F(x) = 0-x

n' = 2^n
F(n') = 3^n

where n' is a numeral in MA and
n is the equivalent numeral in PA.
This mapping allows us to define
an infinite number of new chains
using p^n where p is prime (in PA).

The actual mapping doesn't matter.
What is important is the numbers (in PA)
we use to define n' must be disjoint
from the numbers we use to define F(n').
We can never have 2^x = 3^y for any x or y.
(except x=y=0)

We can show:

Ax (x+F(x) = 0)

Dave Libert has said the following is a theorem of PA:

AxEy ((x=y+y) or (S(x)=y+y))

This is also a theorem of MA unless the
theorem depends on Ax(S(x)~=0).
I will assume this is an theorem of MA.

Let e be a non-standard number in an
infinite model of MA and S(e)=0.

Assume e is "even" and we have e=m+m.
Then m+S(m)=0. Since m+F(m)=0 we have:
F(m)=S(m).

This is impossible given our coding.
We can't have 3^x=2^y for any x or y.
Adding more chains doesn't help us.
We can't encode F(x) the same way we
encode S(x).

A similar argument works for the
predecessor of e if we assume e is "odd".

RussellE

unread,

Oct 7, 2011, 7:32:19 PM10/7/11

to

On Oct 6, 9:03 pm, RussellE <reaste...@gmail.com> wrote:

> Assume e is "even" and we have e=m+m.
> Then m+S(m)=0. Since m+F(m)=0 we have:
> F(m)=S(m).
>
> This is impossible given our coding.
> We can't have 3^x=2^y for any x or y.
> Adding more chains doesn't help us.
> We can't encode F(x) the same way we
> encode S(x).

I should explain this better.

The natural numbers in PA are an
"ascending chain". We have been
talking about "z-chains" or copies
of the integers, but these are actually
two chains, one ascending and one
descending.

We have problems when an ascending
chain runs into a descending chain.
I use F(x) to indicate a descending
chain and x to indicate an ascending chain.
F(x) = 0-x

Using the coding I described previously:
F(x') = 3^x
x' = 2^x

Assume we have n'=F(n').
This means we have encoded the
same number twice. In the ascending
chain the encoding is 2^n. In the
descending chain we have 3^n.

By definition, n', and therefore n, are finite.
This also means F(n') has descended a
finite number of steps.

Both the ascending chain and the descending
chain are of finite length. The entire chain
must be of finite length because we can apply
successor n times to n and transverse the
entire chain.

It doesn't matter which chain we prove is
finite length. Even if we assume there is
a chain for every rational number, we can
still prove one of the chains is of finite length
if we can prove F(x)=x or F(x)=S(x).