What Does a Non-Standard Model of PA Look Like in ZFC?

[RussellE]

Supposedly, we can create a non-standard model of PA
using the standard natural numbers. How does one map
the standard natural numbers to non-standard natural numbers?
I would be interested in what the universal set of any
non-standard model looks like in ZFC.


Russell
- Zeno was right. Motion is impossible.

[David Libert]

We were through all this before. For a countable model, the order
type is isomorphic to a copy of omega above 0, and countably many
copies of Z ordered among themselves isomorphically to the rationals.

That picture so far can be arranged as isomorphic to a subset of
omega, or to all of omega by varous easy codings. These can be made
to be recursive fucntions and recursive sets.

+ and * are each non-recursive, by Tennembaum's theorem. So they
can't have a simple picture.



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

[William Elliot]

On Wed, 3 Nov 2011, David Libert wrote:

> RussellE (reas...@gmail.com) writes:
>> Supposedly, we can create a non-standard model of PA
>> using the standard natural numbers. How does one map
>> the standard natural numbers to non-standard natural numbers?
>> I would be interested in what the universal set of any
>> non-standard model looks like in ZFC.
>

> We were through all this before. For a countable model, the order
> type is isomorphic to a copy of omega above 0, and countably many
> copies of Z ordered among themselves isomorphically to the rationals.
>

What's omega above 0?

[Bill Taylor]

On Nov 3, 6:24 pm, ah...@FreeNet.Carleton.CA (David Libert) wrote:

>   + and * are each non-recursive, by Tennembaum's theorem.
>  So they can't have a simple picture.

Is that "So" in the last line known to be warranted?

Surely there are non-recursive functions which still have
"a simple picture", in some reasonable sense?

e.g. the indicator function of the set of codes
of halting Turing machines. I would call that a very simple
picture, though nowhere near a simple calculation.

I'm not suggesting that some nonstandard + and * would
be this simple, but they could at least be definable in
the same sense. Is that not still conceivable?

-- Tendentious Taylor

[David Libert]

William Elliot (ma...@rdrop.com) writes:
> On Wed, 3 Nov 2011, David Libert wrote:
>
>> RussellE (reas...@gmail.com) writes:
>>> Supposedly, we can create a non-standard model of PA
>>> using the standard natural numbers. How does one map
>>> the standard natural numbers to non-standard natural numbers?
>>> I would be interested in what the universal set of any
>>> non-standard model looks like in ZFC.
>>
>> We were through all this before. For a countable model, the order
>> type is isomorphic to a copy of omega above 0, and countably many
>> copies of Z ordered among themselves isomorphically to the rationals.
>>
> What's omega above 0?

PA defines its canonical linear ordering.

A countable nonstandard PA model has 0 at the base then the
standard integers above 0 forming an isomorphic copy of usual omega.
That's what I meant by omega above 0.

Then it has countably many copies of Z, ordered among themselves
like the rationals.

See:

[1] David Libert "Re: Modular Arithmetic is Uncomputable"
sci.logic, sci.math Oct 6, 2011
http://groups.google.com/group/sci.logic/msg/1dc74a9013dae889

>> That picture so far can be arranged as isomorphic to a subset of
>> omega, or to all of omega by varous easy codings. These can be made
>> to be recursive fucntions and recursive sets.
>>
>> + and * are each non-recursive, by Tennembaum's theorem. So they
>> can't have a simple picture.

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

[Aatu Koskensilta]

Bill Taylor <wfc.t...@gmail.com> writes:

> I'm not suggesting that some nonstandard + and * would be this simple,
> but they could at least be definable in the same sense. Is that not
> still conceivable?

It's perfectly conceivable. And indeed from the arithmetical
completeness theorem we know Peano arithmetic has Delta-2 models.

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

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

[Frederick Williams]

David Libert wrote:
>
> RussellE (reas...@gmail.com) writes:

> > I would be interested in what the universal set of any
> > non-standard model looks like in ZFC.

>

> We were through all this before. For a countable model, the order

> type is isomorphic to [...]

David, is anything known about uncountable models? The answer may be
"Yes, a lot.", but you are excused from reproducing that lot in a reply
here: a reference or two will do. I have Kaye's book somewhere, but I
cannot lay my hands on it at the moment.

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

[RussellE]

On Nov 2, 10:24 pm, ah...@FreeNet.Carleton.CA (David Libert) wrote:

> RussellE (reaste...@gmail.com) writes:
> > Supposedly, we can create a non-standard model of PA
> > using the standard natural numbers. How does one map
> > the standard natural numbers to non-standard natural numbers?
> > I would be interested in what the universal set of any
> > non-standard model looks like in ZFC.
>
> > Russell
> > - Zeno was right. Motion is impossible.
>
>   We were through all this before.  For a countable model, the order
> type is isomorphic to a copy of omega above 0, and countably many
> copies of Z ordered among themselves isomorphically to the rationals.

Yes, I know the "bird's eye" view of what a non-standard model looks
like.
I am interested in the nitty gritty details.

>   That picture so far can be arranged as isomorphic to a subset of
> omega, or to all of omega by varous easy codings.  These can be made
> to be recursive fucntions and recursive sets.

Can you give examples of these "easy codings"?
For example. assume we have a non-standard model
where we define a constant, "e" and add the axioms:

e > 0
e > S0
e > SS0
...

How would we map e to a standard natural number?
We know e/2, e/4, e/8, etc. must all be in different chains
(assuming e is divisible by powers of 2).
How would we map each of these chains?
Can we map them in a way that preserves order?
For example, can we tell from the coding that e/2
comes before e*2?

If these chains are ordered among themselves
isomorphically to the rationals, how would we
code the chain constaing 0 so this chain comes
before all of the other chains?

>   + and * are each non-recursive, by Tennembaum's theorem.  So they
> can't have a simple picture.

It is not obvious to me that successor can be recursive.


Russell
- The universe is one dimensional.

[William Elliot]

On Thu, 3 Nov 2011, David Libert wrote:
> William Elliot (ma...@rdrop.com) writes:
>> On Wed, 3 Nov 2011, David Libert wrote:
>>> RussellE (reas...@gmail.com) writes:

>>>> Supposedly, we can create a non-standard model of PA
>>>> using the standard natural numbers. How does one map
>>>> the standard natural numbers to non-standard natural numbers?
>>>> I would be interested in what the universal set of any
>>>> non-standard model looks like in ZFC.
>>>
>>> We were through all this before. For a countable model, the order
>>> type is isomorphic to a copy of omega above 0, and countably many
>>> copies of Z ordered among themselves isomorphically to the rationals.
>>>
>> What's omega above 0?
>
> PA defines its canonical linear ordering.
>
> A countable nonstandard PA model has 0 at the base then the
> standard integers above 0 forming an isomorphic copy of usual omega.
> That's what I meant by omega above 0.
>
> Then it has countably many copies of Z, ordered among themselves
> like the rationals.
>
> See:
>
> [1] David Libert "Re: Modular Arithmetic is Uncomputable"
> sci.logic, sci.math Oct 6, 2011
> http://groups.google.com/group/sci.logic/msg/1dc74a9013dae889
>

I understand nothing of what you write.
What is the set that's the colleciton of objects of your model?
How is the successor function defined for your model?

Why use the "less than" relation when there's no relation, only
a one place function in the axioms and language of PA?

[Frederick Williams]

RussellE wrote:

>
> It is not obvious to me that successor can be recursive.

What do you mean by recursive?

[Daryl McCullough]

>I understand nothing of what you write.
>What is the set that's the colleciton of objects of your model?
>How is the successor function defined for your model?
>
>Why use the "less than" relation when there's no relation, only
>a one place function in the axioms and language of PA?

The last question is easily answered: in arithmetic, x < y is
defined as Ez (x+z+1) = y.

As explained in the Wikipedia article on nonstandard models,
you can "construct" (in some sense of "construct") a nonstandard
model of arithmetic that is isomorphic to the set of pairs
(n,q) such that n is an integer, q is a positive rational,
and such that if q=0, then n >= 0.

The ordering relation on these object is pretty simple:
(n,q) < (m,r) <==> (q < r) or ((q=r) and (n < m))
where on the left side I'm defining < on pairs,
and on the right side I'm using the usual < on integers
and rationals.

The successor relation is also pretty simple:
S((n,q)) = (n+1,q)

The hard part is defining addition and multiplication.
We have the constraints:
(1) x+(0,0) = x
(2) x+(n+1,q) = S(x+(n,q))
(3) x*(0,0) = (0,0)
(4) x*(n+1,q) = x*(n,q) + x
(5) x < S(x+y)
but these constraints don't uniquely define the operations + and *
on pairs.

[Bill Taylor]

On Nov 4, 3:47 am, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:

> Bill Taylor <wfc.tay...@gmail.com> writes:
> > I'm not suggesting that some nonstandard + and * would be this simple,
> > but they could at least be definable in the same sense.  Is that not
> > still conceivable?
>
>   It's perfectly conceivable. And indeed from the arithmetical
> completeness theorem we know Peano arithmetic has Delta-2 models.

Aha, that's very good.

So how far are we on the road to, or is there any reasonable
hope of, getting such addition and multiplication functions
in the form of some explicit Delta-2 definitions?

(As always here, "explicit" being left to the good will of the
prover.)

-- Baffled Bill

[Aatu Koskensilta]

Bill Taylor <wfc.t...@gmail.com> writes:

> So how far are we on the road to, or is there any reasonable hope of,
> getting such addition and multiplication functions in the form of some
> explicit Delta-2 definitions?

We can read such definitions off from the arithmetized completeness
theorem. Fix a Delta-2 completion D of PA, and put [t] + [q] = [r] if "t
+ q = r" is in D, and similarly for multiplication. Here [t] is the
equivalence class {q | "q = t" in D} represented for instance by its
smallest (in terms of Gödel numbers) element.

[David Libert]

Daryl McCullough (stevend...@yahoo.com) writes:
>>I understand nothing of what you write.
>>What is the set that's the colleciton of objects of your model?
>>How is the successor function defined for your model?
>>
>>Why use the "less than" relation when there's no relation, only
>>a one place function in the axioms and language of PA?
>
> The last question is easily answered: in arithmetic, x < y is
> defined as Ez (x+z+1) = y.
>
> As explained in the Wikipedia article on nonstandard models,
> you can "construct" (in some sense of "construct") a nonstandard
> model of arithmetic that is isomorphic to the set of pairs
> (n,q) such that n is an integer, q is a positive rational,
> and such that if q=0, then n >= 0.
>
> The ordering relation on these object is pretty simple:
> (n,q) < (m,r) <==> (q < r) or ((q=r) and (n < m))
> where on the left side I'm defining < on pairs,
> and on the right side I'm using the usual < on integers
> and rationals.
>
> The successor relation is also pretty simple:
> S((n,q)) = (n+1,q)

Daryl just wrote out the definition of the canonical < I mentioned
in

[1] David Libert "Re: What Does a Non-Standard Model of PA Look Like in ZFC?"
sci.logic Nov 3, 2011
http://groups.google.com/group/sci.logic/msg/e2c043f831c9f303


My discussion, answering Russell's question, was what an arbitrary
nonstandard countable model of PA looks like. So I describe the
structure of such a model with respect to a fragment of its language:
S and the defined <. Those are easier to make an explicit description
than for +, *, as reasonable by Tennennaum's Theorem.

So regarding

>What is the set that's the colleciton of objects of your model?

the model was an abitrary nonstandard countable model of PA. I am
leading to a statement universally quantifying over all such
nonstandard countable models of PA. So the underlying set can be
whatever comes up in such quantifications, ie any denumerable set.

Though also later in my referenced article

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

sci.logic, sci.math Oct 6, 2011
http://groups.google.com/group/sci.logic/msg/1dc74a9013dae889

I made isomorphic copies of the S, < fragments of the model. Those
were on a subset of omega, or then in a second reindexed version, on
all of omega. Those are in the late parts of [2]. So that answers
your question for the late section.

>How is the successor function defined for your model?

Again, the early party of [2] is about an assumed model, so S from
that. The issue is how does such S relate to my description of < .

PA proves that S is the immediate successor in the defined <. Also
that everything above 0 has a unique predecessor.

So S would be the immediate successors up in omega chain or the Z
chains. Daryl also notes that above.

Apart from the < relation, we can define a structure of omega or Z
chains from S in model theory over the model. A similar point arose
in a previous thread descibing infinite models of Russell's MA
theory. MA does not readily define a linear ordering on its
universe. (In fact I presented a model with no linear ordering, and a
proof outline it satisfies MA.)

But in I had a discussion about Z chains in infinite MA models, just
defined in model theory from S. (MA only has Z chains, no omega chain
unlike PA.)

That MA discussion would have similarities to PA.

About predecessor and related - in MA, which would also apply to PA
except at 0:

[3] http://davesscribbles.wikispaces.com/modarithminus

About MA models and Z chains:

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

In case it wasn't clear from [2], the ordering relation was the
usual omega or Z ordering on each copy, omega chain below all Z
chains, and Z chains ordered as rationals.

>Why use the "less than" relation when there's no relation, only
>a one place function in the axioms and language of PA?

By Tennenbaum's Thoerem, + and * will be complicated and indeed I
don't know a simple description of them.

Even though + is difficult this way, I am able to make a simple
concrete description of < which is defined as Daryl did above from +.

So I tried to give as complete a description of the model as I
could, and hence included also a simple description of the defined
relation <. So just to make the description more complete.

If that offends you to include a description of a defined symbol not
from the signature, fine simplify my description from [2] to say there
is one omega chain and infinitely many Z chains, with S acting as
usual S on all those chains.



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

[David Libert]

Frederick Williams (freddyw...@btinternet.com) writes:
> RussellE wrote:
>
>>
>> It is not obvious to me that successor can be recursive.
>
> What do you mean by recursive?

This is like from the statement of Tennebaum's Theorem.

We consider a nonstandard PA model with underlying set omega.

So we are concerned with the interpretation of S in that model, some
unary function on omega to itself.

As in Tennenbaum's Theorem, we discuss if this is recursive or not
according to the usual recursivesness over omega, that is defined from
the usual + and * on omega, the underlying omega, not the + and *
interpetations from the model under discussion.

If we just interpreted recursiveness using the model's nonstandard +
* as underlying in the definition of recursiveness, then these
interpreted S, +, * would be trivially recursive.

This issue about the statement of Tennenbaum's Theorem came up in an
early article on it:

[1] David Libert The language of whatever (Was: Definable real numbers)
sci.logic Dec 6, 2002
http://groups.google.com/group/sci.logic/msg/13bd71be3291b9e4


[1] was catalogued in other general info on Tennenbaum's Theorem:


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



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

[RussellE]

On Nov 4, 4:01 am, Daryl McCullough <stevendaryl3...@yahoo.com> wrote:
> >I understand nothing of what you write.
> >What is the set that's the colleciton of objects of your model?
> >How is the successor function defined for your model?
>
> >Why use the "less than" relation when there's no relation, only
> >a one place function in the axioms and language of PA?
>
> The last question is easily answered: in arithmetic, x < y is
> defined as Ez (x+z+1) = y.
>
> As explained in the Wikipedia article on nonstandard models,
> you can "construct" (in some sense of "construct") a nonstandard
> model of arithmetic that is isomorphic to the set of pairs
> (n,q) such that n is an integer, q is a positive rational,
> and such that if q=0, then n >= 0.

Thanks! This is what I am looking for.
Integers and rationals are not standard natural numbers,
but we can define them using standard natural numbers.
Would you please post a link to the Wiki?

> The ordering relation on these object is pretty simple:
> (n,q) < (m,r) <==> (q < r) or ((q=r) and (n < m))
> where on the left side I'm defining < on pairs,
> and on the right side I'm using the usual < on integers
> and rationals.
>
> The successor relation is also pretty simple:
> S((n,q)) = (n+1,q)

This defines successor within a given chain.
It doesn't explain how successor would go
from one chain to the next.
This is the part I have been trying to figure out.

You define 0 as the ordered pair (0, 0.0).
Of course, (-1, 0.0) would not be a natural number in PA.

Assume we have defined a non-standard natural, e,
by axiom as I previously described.
Which rational number would I used for the chain
containing e? I could just randomly choose 0.5:

e = (0, 0.5)
Se = (1, 0.5)
Pe = (-1, 0.5)

where S is successor and P is predecessor.

Now, I want to define 2*e, which is in a different chain.
How would I choose which rational to use for this chain?
We also know 3*e can't be in the same chain as e or
in the same chain as 2*e. So, we have a series of chains:

e, 2*e, 3*e, 4*e, ...

Do I have to randomly choose a different rational
number for each of these chains? Do I need the
axiom of choice to even create a mapping?

I think I can even define polynomials based on e
and show each solution must be in a different chain:

x = a1*e + a2*e^2 + a3*e^3 + ... + an*e^n

where a1,a2,...,an are (standard?) natural numbers.

As you can see, we can define a lot of different chains.
How would we prove there are only a countable number?

> The hard part is defining addition and multiplication.
> We have the constraints:
> (1) x+(0,0) = x
> (2) x+(n+1,q) = S(x+(n,q))
> (3) x*(0,0) = (0,0)
> (4) x*(n+1,q) = x*(n,q) + x
> (5) x < S(x+y)
> but these constraints don't uniquely define the operations + and *
> on pairs.

Can our ordered pairs have "rational" numbers like e / Se ?
A non-standard model of PA can't tell the difference between
standard rationals and non-standard rationals.
I guess this is not a problem since the mapping is done in ZFC.


Russell
- 2 many 2 count

[George Greene]

On Nov 3, 8:39 pm, RussellE <reaste...@gmail.com> wrote:
> Yes, I know the "bird's eye" view of what a non-standard model looks like.

No, as you will prove later, you don't.

> I am interested in the nitty gritty details.

They are non-recursive so that's irrelevant.

> >   That picture so far can be arranged as isomorphic to a subset of
> > omega, or to all of omega by varous easy codings.  These can be made
> > to be recursive fucntions and recursive sets.
>
> Can you give examples of these "easy codings"?

This is NOT a "nitty gritty detail"! This is just a lame stupid
dovetailing permutation that ADDS NOTHING TO ANYBODY's understanding!

> For example. assume we have a non-standard model
> where we define a constant, "e" and add the axioms:

There is no reason for you to add ANY axioms about e because
e HAS ALREADY BEEN DEFINED, according to YOU!

> e > 0
> e > S0
> e > SS0

Why are you bothering to add infinitely many axioms???
It is possible to create a non-standard model by adding ONE axiom,
you know.
The infinitely many statements you are talking about above would then
all come out as THEOREMS, NOT axioms.

> How would we map e to a standard natural number?

THIS DOES *NOT* MATTER!! You do NOT CARE about this!
The mere fact that THE OVERALL SET IS COUNTABLE means
that there are MYRIAD DIFFERENT ways to map each and every element
of it to a natural number! NONE of them is IMPORTANT, or, at any
rate,
none of them is any MORE important THAN any OTHER!!

> We know e/2, e/4, e/8, etc. must all be in different chains

You DON'T know that!!

> (assuming e is divisible by powers of 2).

THEN WHAT ABOUT e+1, DUMBASS???
MOST of these numbers will NOT be infinitely divisible by powers of
2!!

> How would we map each of these chains?
> Can we map them in a way that preserves order?

The chains ALL ALREADY HAVE an order.
It DOES NOT MATTER what NATURAL number you map ANYthing in ANY chain
to,
beyond proving that it is recursive.

> For example, can we tell from the coding that e/2
> comes before e*2?

You can't tell that e/2 even exists in the model at all. In fact, if
e is odd, IT DOESN'T.

[George Greene]

On Nov 3, 6:38 am, Bill Taylor <wfc.tay...@gmail.com> wrote:
> On Nov 3, 6:24 pm, ah...@FreeNet.Carleton.CA (David Libert) wrote:
>
> >   + and * are each non-recursive, by Tennembaum's theorem.
> >  So they can't have a simple picture.
>
> Is that "So" in the last line known to be warranted?

Yes.

> Surely there are non-recursive functions which still have
> "a simple picture", in some reasonable sense?

Surely you are still less-educated about this than you would like to
be.

>
> e.g. the indicator function of the set of codes
> of halting Turing machines.  I would call that a very simple
> picture,

And you'd just be wrong.

[David Libert]

Aatu Koskensilta (aatu.kos...@uta.fi) writes:
> Bill Taylor <wfc.t...@gmail.com> writes:
>
>> So how far are we on the road to, or is there any reasonable hope of,
>> getting such addition and multiplication functions in the form of some
>> explicit Delta-2 definitions?
>
> We can read such definitions off from the arithmetized completeness
> theorem. Fix a Delta-2 completion D of PA, and put [t] + [q] = [r] if "t
> + q = r" is in D, and similarly for multiplication. Here [t] is the
> equivalence class {q | "q = t" in D} represented for instance by its
> smallest (in terms of Gödel numbers) element.

I had posted details of a construction as Aatu was just mentioning:

[1] David Libert "The language of whatever (Was: Definable real numbers)"

sci.logic Dec 8, 2002
http://groups.google.com/group/sci.logic/msg/f6bfd418e7ffe84c


Once you fix conventions such as coding choices for Godeling
numbering, [1] becomes an explicit definition.

Working in ZF, something similar can be done for theories ZF proves
consistent, such as analysis and Zermelo's theory (without
Replacement).

We can't make a definition and have ZF prove it consitructs a model
for higher theories like ZF or ZF + large cardinals, by Godel.

But by putting the minimal reasonable consistency assumptions into
the background theory, this can even be done for ZFC and ZFC + some
large cardinals.

For this see:

[2] David Libert "term models for ZFC and related theories"
sci.math Mar 31, 2009
http://groups.google.com/group/sci.math/msg/0a00af356a543488


and its followup:

[3] http://davesscribbles.wikispaces.com/Impredtermmodels



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

[RussellE]

On Nov 4, 6:06 pm, George Greene <gree...@email.unc.edu> wrote:
> On Nov 3, 8:39 pm, RussellE <reaste...@gmail.com> wrote:
>
> > Yes, I know the "bird's eye" view of what a non-standard model looks like.
>
> No, as you will prove later, you don't.
>
> > I am interested in the nitty gritty details.
>
> They are non-recursive so that's irrelevant.

Non-recursive as in "much hand waving"?

> > >   That picture so far can be arranged as isomorphic to a subset of
> > > omega, or to all of omega by varous easy codings.  These can be made
> > > to be recursive fucntions and recursive sets.
>
> > Can you give examples of these "easy codings"?
>
> This is NOT a "nitty gritty detail"!  This is just a lame stupid
> dovetailing permutation that ADDS NOTHING TO ANYBODY's understanding!

It would add to mine.

> > For example. assume we have a non-standard model
> > where we define a constant, "e" and add the axioms:
>
> There is no reason for you to add ANY axioms about e because
> e HAS ALREADY BEEN DEFINED, according to YOU!
>
> > e > 0
> > e > S0
> > e > SS0
>
> Why are you bothering to add infinitely many axioms???
> It is possible to create a non-standard model by adding ONE axiom,
> you know.

OK. I give.
How would I define e as a non-standard natural number
using one axiom in FOL?

> The infinitely many statements you are talking about above would then
> all come out as THEOREMS, NOT axioms.

Fewer axioms works for me.

> > How would we map e to a standard natural number?
>
> THIS DOES *NOT* MATTER!!  You do NOT CARE about this!
> The mere fact that THE OVERALL SET IS COUNTABLE means
> that there are MYRIAD DIFFERENT ways to map each and every element
> of it to a natural number!  NONE of them is IMPORTANT, or, at any
> rate,
> none of them is any MORE important THAN any OTHER!!

I know there are a lot of different ways to make such a mapping.
I just want to see one that works.

How do you know if the universe of a non-standard model of PA is
countable?

> > We know e/2, e/4, e/8, etc. must all be in different chains
>
> You DON'T know that!!

Yes, I do.

>> > (assuming e is divisible by powers of 2).
>
> THEN WHAT ABOUT e+1, DUMBASS???

e+n where n is "finite" (as defined in the meta theory, ZFC)
would be in the same chain as e.
Since e is "infinite" (as defined in ZFC), e+e can't be in
the same chain as e.

> MOST of these numbers will NOT be infinitely divisible by powers of
> 2!!
>

Define x as the largest natural number such that 2*x =< e.
Define y as the largest natural number such that 4*y =< e.
etc.

Each of these numbers have to be in different chains.

> > How would we map each of these chains?
> > Can we map them in a way that preserves order?
>
> The chains ALL ALREADY HAVE an order.

Can we map them to the standard natural numbers in
a way that preserves the order? Or at least be able
to tell from the coding for A and the coding for B
whether A<B or B<A?

> It DOES NOT MATTER what NATURAL number you map ANYthing in ANY chain
> to,
> beyond proving that it is recursive.

Earlier you said it wasn't recursive.

> > For example, can we tell from the coding that e/2
> > comes before e*2?
>
> You can't tell that e/2 even exists in the model at all.  In fact, if
> e is odd, IT DOESN'T.

OK. Given the mapping for e and the mapping for 2*e, would we
able to tell from the mapping that e < 2*e?

Here is a harder problem. Given the mapping for e,
can I recursively generate the mapping for e+e?


Russell
- Never never means never in set theory.

[David Libert]

Bill Taylor (wfc.t...@gmail.com) writes:
> On Nov 3, 6:24=A0pm, ah...@FreeNet.Carleton.CA (David Libert) wrote:
>
>> =A0 + and * are each non-recursive, by Tennembaum's theorem.
>> =A0So they can't have a simple picture.

>
> Is that "So" in the last line known to be warranted?
>
> Surely there are non-recursive functions which still have
> "a simple picture", in some reasonable sense?

The thread here was titled about what these models look like.

That language, "look like" is not a precisely defined mathematical
term, but is reasonable in informal math talk. I take it to be
something different than a mere existence proof. Otherwise there
would be no distinction between this language and merely asking for a
model.

So looking like, or as I said a simple picture. When I wrote we had
been through this before, I was referring to the previous article that
I cited in my followup to William Elliot:


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

sci.logic, sci.math Oct 6, 2011
http://groups.google.com/group/sci.logic/msg/1dc74a9013dae889

In [1], I wrote about how that description could be represented by a
picture on a blackboard.

And then I go on to say how to extract from that same description a
model of style contraditcing the phrasing of Tennebaum's theorem.

So all that is along the lines I meant above. The simple picture I
had in mind itself directly led to the sort of model Tennenbaum's
theorem rules out in cases + and *.

> e.g. the indicator function of the set of codes
> of halting Turing machines. I would call that a very simple
> picture, though nowhere near a simple calculation.

I could draw a picture of the even integers. I can't really draw
infinitely many such numbers. But I can make an initial segment big
enough to suggest a pattern and say and so on. Again this is
informal language.

I can similarly represent the set of integers divisible by 3.

For the halting Turing machines I would instead just draw in some
values scattered about randomly. But that would be the same picture I
would draw for any complicated or poorly known set. So my picture
wouldn't be a good individuated one of the set, unlike the
examples above with 2 or 3.

That had been my first reaction to the above. I thought more though
and realized, I could draw a horizontal line to be the integers. (The
other post a horizontal line was the rationals. So these pictures do
have some poetic license.)

Above various integers I could draw short vertical line segements of
varying lengths. Those are the running times of the Turiong machine
coded at that integer. Then among those I put a few vertical line
segments, alas still actually finite since my arm would get too tired
otherwise, but well longer than the others, and I explain these longer
ones are really infinite. Those are the Turing machines that don't
halt. So your set is those points on the line with the big lines
above them.

That I take to be a good picture of your example. So indeed, by
bringing into the picture side data from inside quantifiers in the
definition I can indeed get something into the picture.

But that is all by a quantifier over simple properties that
themselves can be reailty picturted: running times to be line
segments.

We get + and * by for example:


[2] David Libert "The language of whatever (Was: Definable real numbers)"

sci.logic Dec 8, 2002
http://groups.google.com/group/sci.logic/msg/f6bfd418e7ffe84c

I don't see how to represent this construction, which is inductive
and has some decisions setting a context for later decisions, in a
simple visial picture.

And I don't know any other way to represent specfic information
about these + and *.

And indeed, anything that I put into a picture should be a simple
pattern, where a finite drawing can represent an infinite pattern by
some kind of repertion or tiling.

And those would be the sort of simplicities ruled out by Tennenbaum.

> I'm not suggesting that some nonstandard + and * would
> be this simple, but they could at least be definable in
> the same sense. Is that not still conceivable?
>
> -- Tendentious Taylor

Definable yes. As in [2] and Aatu's post. But as above, I take
looks like and simple picture to be more restrictive than this.





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

[David Libert]

Frederick Williams (freddyw...@btinternet.com) writes:
> David Libert wrote:
>>
>> RussellE (reas...@gmail.com) writes:
>
>> > I would be interested in what the universal set of any
>> > non-standard model looks like in ZFC.
>
>>
>> We were through all this before. For a countable model, the order
>> type is isomorphic to [...]
>
> David, is anything known about uncountable models? The answer may be
> "Yes, a lot.", but you are excused from reproducing that lot in a reply
> here: a reference or two will do. I have Kaye's book somewhere, but I
> cannot lay my hands on it at the moment.

I had never known much about that topic, uncountable PA models.

One related result was in

[1] David Libert "Re: Modular Arithmetic Is Consistent"
sci.logic,sci.math July 9, 2011
http://groups.google.com/group/sci.logic/msg/212936720cb333d4


which noted over ZF that if every infinite set is
the carrier set of a PA model (a special case of L-S) then AC.

I found

[2]
http://mathoverflow.net/questions/48415/uncountable-nonstandard-models-of-pa

which mentioned that Kaye name that you did.

One point about these models is they will have certain homogenity
properties. For example, you can map x |-> x + a for a fixed a,
showing the entire model must have the same carinality as the part
above a.

Similarly other linear transformations to map between intervals.

In [2] they note by such easy proofs that the Z chains can't be
ordered like Q + R, ie copy of rationals followed by reals.

[2] also cites a deeper theorem that the Z chains can't be ordered
like R.

Hausdorff had linear orders called eta_alpha. They were a higher
order generalization of the rationals with higher order cardinality
versions of homogenity. They depended on GCH though. They were
unique up to isomorphism.

But from ZFC alone we get the PA models in every cardinality, so the
homogenity properites resulting from PA must be weaker than those.

[2] also cites a recent Shelah paper on arxiv.



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

[William Elliot]

On Fri, 4 Nov 2011, Daryl McCullough wrote:

>> What is the set that's the collection of objects of your model?

>> How is the successor function defined for your model?
>>
>> Why use the "less than" relation when there's no relation, only
>> a one place function in the axioms and language of PA?
>
> The last question is easily answered: in arithmetic, x < y is
> defined as Ez (x+z+1) = y.
>

For the non-negative integers.

> As explained in the Wikipedia article on nonstandard models,
> you can "construct" (in some sense of "construct") a nonstandard
> model of arithmetic that is isomorphic to the set of pairs
> (n,q) such that n is an integer, q is a positive rational,
> and such that if q=0, then n >= 0.
>

If the set is { (n,q) | n integer, q positive rational }
then there's no concern about (n,0). Do you mean
{ (n,q) | n integer, q non-negative integer } ?

> The ordering relation on these object is pretty simple:
> (n,q) < (m,r) <==> (q < r) or ((q=r) and (n < m))
> where on the left side I'm defining < on pairs,
> and on the right side I'm using the usual < on integers

i-r> and rationals.
>
By integers, do you mean the integers Z, non-negative integers Z+
or the positive integers N?

That's the lexigraphical order of ZxQ.

> The successor relation is also pretty simple:
> S((n,q)) = (n+1,q)
>
> The hard part is defining addition and multiplication.
> We have the constraints:
> (1) x+(0,0) = x
> (2) x+(n+1,q) = S(x+(n,q))
> (3) x*(0,0) = (0,0)
> (4) x*(n+1,q) = x*(n,q) + x
> (5) x < S(x+y)
> but these constraints don't uniquely define the operations + and *
> on pairs.
>

What are we modeling? Peano's axioms or addition and multiplication of
integers? I would expect the hard part would to be establish induction.

[Frederick Williams]

RussellE wrote:

> It doesn't explain how successor would go
> from one chain to the next.

There's a good reason for that.

[Frederick Williams]

RussellE wrote:
>
> On Nov 4, 6:06 pm, George Greene <gree...@email.unc.edu> wrote:
> > On Nov 3, 8:39 pm, RussellE <reaste...@gmail.com> wrote:
> >
> > > Yes, I know the "bird's eye" view of what a non-standard model looks like.
> >
> > No, as you will prove later, you don't.
> >
> > > I am interested in the nitty gritty details.
> >
> > They are non-recursive so that's irrelevant.
>
> Non-recursive as in "much hand waving"?

Elsewhere I asked you what you meant by successor being recursive. May
I ask what _your_ understanding of recursive/non-recursive is?

> > > > That picture so far can be arranged as isomorphic to a subset of
> > > > omega, or to all of omega by varous easy codings. These can be made
> > > > to be recursive fucntions and recursive sets.
> >
> > > Can you give examples of these "easy codings"?
> >
> > This is NOT a "nitty gritty detail"! This is just a lame stupid
> > dovetailing permutation that ADDS NOTHING TO ANYBODY's understanding!
>
> It would add to mine.
>
> > > For example. assume we have a non-standard model
> > > where we define a constant, "e" and add the axioms:
> >
> > There is no reason for you to add ANY axioms about e because
> > e HAS ALREADY BEEN DEFINED, according to YOU!
> >
> > > e > 0
> > > e > S0
> > > e > SS0
> >
> > Why are you bothering to add infinitely many axioms???
> > It is possible to create a non-standard model by adding ONE axiom,
> > you know.
>
> OK. I give.
> How would I define e as a non-standard natural number
> using one axiom in FOL?

(Ex)(Ay)(y < x)

select one such x and call it e.

>
> > The infinitely many statements you are talking about above would then
> > all come out as THEOREMS, NOT axioms.
>
> Fewer axioms works for me.
>
> > > How would we map e to a standard natural number?
> >
> > THIS DOES *NOT* MATTER!! You do NOT CARE about this!
> > The mere fact that THE OVERALL SET IS COUNTABLE means
> > that there are MYRIAD DIFFERENT ways to map each and every element
> > of it to a natural number! NONE of them is IMPORTANT, or, at any
> > rate,
> > none of them is any MORE important THAN any OTHER!!
>
> I know there are a lot of different ways to make such a mapping.
> I just want to see one that works.

"Works" how? What do you want the mapping to do?

> How do you know if the universe of a non-standard model of PA is
> countable?

George Greene is replying to your reply to David Libert. David Libert
began:

> We were through all this before. For a countable model...

So it seems to me that this corner of the thread is discussing countable
models. If you cook up a model of PA that is non-standard, then how you
show that the universe is countable (if it is so) will depend on the
recipe, won't it?

> > > We know e/2, e/4, e/8, etc. must all be in different chains
> >
> > You DON'T know that!!
>
> Yes, I do.
>
> >> > (assuming e is divisible by powers of 2).
> >
> > THEN WHAT ABOUT e+1, DUMBASS???
>
> e+n where n is "finite" (as defined in the meta theory, ZFC)
> would be in the same chain as e.
> Since e is "infinite" (as defined in ZFC), e+e can't be in
> the same chain as e.
>
> > MOST of these numbers will NOT be infinitely divisible by powers of
> > 2!!
> >
>
> Define x as the largest natural number such that 2*x =< e.
> Define y as the largest natural number such that 4*y =< e.
> etc.
>
> Each of these numbers have to be in different chains.
>
> > > How would we map each of these chains?
> > > Can we map them in a way that preserves order?
> >
> > The chains ALL ALREADY HAVE an order.
>
> Can we map them to the standard natural numbers in
> a way that preserves the order?

No. For every non-standard x, there are infinitely many standard y that
precede it. That isn't true of standard x's.

[Frederick Williams]

RussellE wrote:

>
> Define x as the largest natural number such that 2*x =< e.
> Define y as the largest natural number such that 4*y =< e.
> etc.

It won't do just to say "define such-and-such as so-and-so". You have
to prove that just one thing has the property so-and-so. Without that
you haven't (or, at least, you don't _know_ that you have) defined
anything.

[Also, why is all this going to comp.theory. Are they interested?]

[Frederick Williams]

George Greene wrote:
>
> On Nov 3, 8:39 pm, RussellE <reaste...@gmail.com> wrote:

>
> > e > 0
> > e > S0
> > e > SS0
>
> Why are you bothering to add infinitely many axioms???

Because many explanations of the fact that there are non-standard
natural numbers do just that. Russell is fond of just repeating stuff
parrot-fashion.

[Frederick Williams]

RussellE wrote:

>
> Yes, I know the "bird's eye" view of what a non-standard model looks
> like.

Really? There have been various posts (I made some myself I think)
giving the order type of the universe of a countable non-standard model;
but do you have a bird's eye view of the functions on that universe that
the model has? Recall, it has a function that (the language element) +
denotes, and ditto S and *.

[Aatu Koskensilta]

ah...@FreeNet.Carleton.CA (David Libert) writes:

> I had posted details of a construction as Aatu was just mentioning:
>
>
> [1] David Libert "The language of whatever (Was: Definable real numbers)"
> sci.logic Dec 8, 2002
> http://groups.google.com/group/sci.logic/msg/f6bfd418e7ffe84c
>
>
> Once you fix conventions such as coding choices for Godeling
> numbering, [1] becomes an explicit definition.

A small point. In [1] you add to PA infinitely many axioms, "c > n"
for a new constant c and each numeral n. This is unnecessary. Any model
resulting from a construction of this sort will automatically be
nonstandard. This follows from the fact that truth in the model is
Delta-2 -- or recursive in 0', as you put it -- but arithmetical truth
is not. (I seem to recall Kreisel in his first published paper made some
interesting use of observations like this...)

[Daryl McCullough]

On Saturday, November 5, 2011 5:37:45 AM UTC-4, William Elliot wrote:
> On Fri, 4 Nov 2011, Daryl McCullough wrote:
>
> >> What is the set that's the collection of objects of your model?
> >> How is the successor function defined for your model?
> >>
> >> Why use the "less than" relation when there's no relation, only
> >> a one place function in the axioms and language of PA?
> >
> > The last question is easily answered: in arithmetic, x < y is
> > defined as Ez (x+z+1) = y.
> >
> For the non-negative integers.

That's what we're talking about, a nonstandard model of the nonnegative

integers.

> > As explained in the Wikipedia article on nonstandard models,
> > you can "construct" (in some sense of "construct") a nonstandard
> > model of arithmetic that is isomorphic to the set of pairs
> > (n,q) such that n is an integer, q is a positive rational,
> > and such that if q=0, then n >= 0.
> >
> If the set is { (n,q) | n integer, q positive rational }
> then there's no concern about (n,0). Do you mean
> { (n,q) | n integer, q non-negative integer } ?

I meant q is a non-negative RATIONAL.

> > The ordering relation on these object is pretty simple:
> > (n,q) < (m,r) <==> (q < r) or ((q=r) and (n < m))
> > where on the left side I'm defining < on pairs,
> > and on the right side I'm using the usual < on integers

> > and rationals.
> >
> By integers, do you mean the integers Z, non-negative integers Z+
> or the positive integers N?

I mean Z. If e is nonstandard, then so is e-1, e-2, ... So you
can represent a nonstandard natural by picking an arbitrary
nonstandard natural, e, and representing it by (0,1/2) (for
example), and letting e+1 be represented by (1,1/2), and
e-1 be represented by (-1,1/2), etc.

> That's the lexigraphical order of ZxQ.

Yes, that's why I chose that representation.

> > The successor relation is also pretty simple:
> > S((n,q)) = (n+1,q)
> >
> > The hard part is defining addition and multiplication.
> > We have the constraints:
> > (1) x+(0,0) = x
> > (2) x+(n+1,q) = S(x+(n,q))
> > (3) x*(0,0) = (0,0)
> > (4) x*(n+1,q) = x*(n,q) + x
> > (5) x < S(x+y)
> > but these constraints don't uniquely define the operations + and *
> > on pairs.
> >
> What are we modeling? Peano's axioms

Yes.

> or addition and multiplication of integers? I would expect the
> hard part would to be establish induction.

You can't *represent* induction, you just have to make sure that
you satisfy it. Induction will be satisfied provided that any
statement in the language of arithmetic that is *provable* must
be true in your model. So for instance, we have statements such
as (x+1)*3 > (x+1)*2
x*3 = 3*x
x*(y+1) = x*y + x
etc.
They all have to be true of the nonstandard elements, as well.

[Daryl McCullough]

On Friday, November 4, 2011 8:59:21 PM UTC-4, RussellE wrote:

> On Nov 4, 4:01 am, Daryl McCullough <stevend...@yahoo.com> wrote:

> > The ordering relation on these object is pretty simple:
> > (n,q) < (m,r) <==> (q < r) or ((q=r) and (n < m))
> > where on the left side I'm defining < on pairs,
> > and on the right side I'm using the usual < on integers
> > and rationals.
> >
> > The successor relation is also pretty simple:
> > S((n,q)) = (n+1,q)
>
> This defines successor within a given chain.
> It doesn't explain how successor would go
> from one chain to the next.

It doesn't. There is no way to get from one chain to the next by
repeatedly applying the successor function. Successor only moves
you around in one chain.

> This is the part I have been trying to figure out.
>
> You define 0 as the ordered pair (0, 0.0).
> Of course, (-1, 0.0) would not be a natural number in PA.
>
> Assume we have defined a non-standard natural, e,
> by axiom as I previously described.
> Which rational number would I used for the chain
> containing e? I could just randomly choose 0.5:

Yes, it doesn't matter.

> e = (0, 0.5)
> Se = (1, 0.5)
> Pe = (-1, 0.5)
>
> where S is successor and P is predecessor.
>
> Now, I want to define 2*e, which is in a different chain.
> How would I choose which rational to use for this chain?

Again, it doesn't matter, except for the constraint that
2*e > e (if e > 0).

> We also know 3*e can't be in the same chain as e or
> in the same chain as 2*e. So, we have a series of chains:
>
> e, 2*e, 3*e, 4*e, ...
>
> Do I have to randomly choose a different rational
> number for each of these chains?

It doesn't have to be random. You can do it systematically.
The problem is that at every stage, you have more constraints
that you have to satisfy: 4*e > 3*e > 2*e.

> Do I need the axiom of choice to even create a mapping?

I don't think so, because the domain can be well-ordered
without choice, so whenever you have to make a "random"
choice, you can just pick the smallest element of the
domain that satisfies all the constraints.

> I think I can even define polynomials based on e
> and show each solution must be in a different chain:
>
> x = a1*e + a2*e^2 + a3*e^3 + ... + an*e^n
>
> where a1,a2,...,an are (standard?) natural numbers.
>
> As you can see, we can define a lot of different chains.
> How would we prove there are only a countable number?

The chains you've described are all terms in the extended
language of PA plus the constant e. There are only countably
many such terms.

> > The hard part is defining addition and multiplication.
> > We have the constraints:
> > (1) x+(0,0) = x
> > (2) x+(n+1,q) = S(x+(n,q))
> > (3) x*(0,0) = (0,0)
> > (4) x*(n+1,q) = x*(n,q) + x
> > (5) x < S(x+y)
> > but these constraints don't uniquely define the operations + and *
> > on pairs.
>
> Can our ordered pairs have "rational" numbers like e / Se ?

No. The model obeys all the theorems of PA. So in particular,
you can prove that there is no y such that y*Se = e.

[RussellE]

On Nov 5, 3:41 am, Frederick Williams <freddywilli...@btinternet.com>
wrote:

> RussellE wrote:
>
> > On Nov 4, 6:06 pm, George Greene <gree...@email.unc.edu> wrote:
> > > On Nov 3, 8:39 pm, RussellE <reaste...@gmail.com> wrote:
>
> > > > For example. assume we have a non-standard model
> > > > where we define a constant, "e" and add the axioms:
>
> > > There is no reason for you to add ANY axioms about e because
> > > e HAS ALREADY BEEN DEFINED, according to YOU!
>
> > > > e > 0
> > > > e > S0
> > > > e > SS0
>
> > > Why are you bothering to add infinitely many axioms???
> > > It is possible to create a non-standard model by adding ONE axiom,
> > > you know.
>
> > OK. I give.
> > How would I define e as a non-standard natural number
> > using one axiom in FOL?

>
> (Ex)(Ay)(y < x)

This won't work.
First, we have x<x.
Second, this means x is the largest element in the universe.
The universe of a model of PA has no largest element.

[RussellE]

On Nov 5, 3:46 am, Frederick Williams <freddywilli...@btinternet.com>
wrote:

> RussellE wrote:
>
> > Define x as the largest natural number such that 2*x =< e.
> > Define y as the largest natural number such that 4*y =< e.
> > etc.
>
> It won't do just to say "define such-and-such as so-and-so".  You have
> to prove that just one thing has the property so-and-so.  Without that
> you haven't (or, at least, you don't _know_ that you have) defined
> anything.

Ex (x+x >= e)
Let x1 be the least such x.
There can only be one "least" such x.
Earlier, I used "greatest" x where x+x =< e.

> [Also, why is all this going to comp.theory.  Are they interested?]

Hopefully, it is more interesting than the spam.
Computer science types are more interested in
foundations than you might think.
Floating point operations really suck.

[Frederick Williams]

RussellE wrote:
>
> On Nov 5, 3:41 am, Frederick Williams <freddywilli...@btinternet.com>
> wrote:

> > (Ex)(Ay)(y < x)
>
> This won't work.

Yes. Sorry. I don't know what I was thinking of.

[RussellE]

On Nov 5, 5:58 am, Daryl McCullough <stevendaryl3...@yahoo.com> wrote:
> On Friday, November 4, 2011 8:59:21 PM UTC-4, RussellE wrote:
> > On Nov 4, 4:01 am, Daryl McCullough <stevend...@yahoo.com> wrote:
>
> > > The ordering relation on these object is pretty simple:
> > > (n,q) < (m,r) <==> (q < r) or ((q=r) and (n < m))
> > > where on the left side I'm defining < on pairs,
> > > and on the right side I'm using the usual < on integers
> > > and rationals.
>
> > > The successor relation is also pretty simple:
> > > S((n,q)) = (n+1,q)
>
> > This defines successor within a given chain.
> > It doesn't explain how successor would go
> > from one chain to the next.
>
> It doesn't. There is no way to get from one chain to the next by
> repeatedly applying the successor function. Successor only moves
> you around in one chain.

Applying the successor function to 0 e times doesn't give me e?
e is just another natural number as far as the model is concerned.

> > This is the part I have been trying to figure out.
>
> > You define 0 as the ordered pair (0, 0.0).
> > Of course, (-1, 0.0) would not be a natural number in PA.
>
> > Assume we have defined a non-standard natural, e,
> > by axiom as I previously described.
> > Which rational number would I used for the chain
> > containing e? I could just randomly choose 0.5:
>
> Yes, it doesn't matter.
>
> > e = (0, 0.5)
> > Se = (1, 0.5)
> > Pe = (-1, 0.5)
>
> > where S is successor and P is predecessor.
>
> > Now, I want to define 2*e, which is in a different chain.
> > How would I choose which rational to use for this chain?
>
> Again, it doesn't matter, except for the constraint that
> 2*e > e (if e > 0).
>
> > We also know 3*e can't be in the same chain as e or
> > in the same chain as 2*e. So, we have a series of chains:
>
> > e, 2*e, 3*e, 4*e, ...
>
> > Do I have to randomly choose a different rational
> > number for each of these chains?
>
> It doesn't have to be random. You can do it systematically.
> The problem is that at every stage, you have more constraints
> that you have to satisfy: 4*e > 3*e > 2*e.

I can come up with a lot of constraints.

> > Do I need the axiom of choice to even create a mapping?
>
> I don't think so, because the domain can be well-ordered
> without choice, so whenever you have to make a "random"
> choice, you can just pick the smallest element of the
> domain that satisfies all the constraints.
>
> > I think I can even define polynomials based on e
> > and show each solution must be in a different chain:
>
> > x = a1*e + a2*e^2 + a3*e^3 + ... + an*e^n
>
> > where a1,a2,...,an are (standard?) natural numbers.
>
> > As you can see, we can define a lot of different chains.
> > How would we prove there are only a countable number?
>
> The chains you've described are all terms in the extended
> language of PA plus the constant e. There are only countably
> many such terms.

How do you know there are only countably many such terms?
We already have there are at least as many chains as there are
"finite" (in the meta-theory) subsets of the (standard?) natural
numbers.
And all these chains come after e's chain.
I haven't even started wokring on unique chains definable with
recursion.
For example, I think I can define another chain with:

x = e/2 + e/4 + e/8 + ...

(I probably have to replace e/2 with the least x such that x+x >= e).

> > > The hard part is defining addition and multiplication.
> > > We have the constraints:
> > > (1) x+(0,0) = x
> > > (2) x+(n+1,q) = S(x+(n,q))
> > > (3) x*(0,0) = (0,0)
> > > (4) x*(n+1,q) = x*(n,q) + x
> > > (5) x < S(x+y)
> > > but these constraints don't uniquely define the operations + and *
> > > on pairs.
>
> > Can our ordered pairs have "rational" numbers like e / Se ?
>
> No. The model obeys all the theorems of PA. So in particular,
> you can prove that there is no y such that y*Se = e.

I don't follow this. Let e=3. There is no integer y such that:

y*4 = 3

If you are assuming y is a rational then y = e/Se.


Russell
- Integers are an illusion.

[RussellE]

On Nov 5, 10:59 am, Frederick Williams <freddywilli...@btinternet.com>

wrote:
> RussellE wrote:
>
> > On Nov 5, 3:41 am, Frederick Williams <freddywilli...@btinternet.com>
> > wrote:
> > > (Ex)(Ay)(y < x)
>
> > This won't work.
>
> Yes.  Sorry.  I don't know what I was thinking of.

No problem.
I knew it was wrong because I posted
an axiom just like it once.

[Daryl McCullough]

On Saturday, November 5, 2011 2:02:51 PM UTC-4, RussellE wrote:

> On Nov 5, 5:58 am, Daryl McCullough <stevend...@yahoo.com> wrote:

> > > This defines successor within a given chain.
> > > It doesn't explain how successor would go
> > > from one chain to the next.
> >
> > It doesn't. There is no way to get from one chain to the next by
> > repeatedly applying the successor function. Successor only moves
> > you around in one chain.
>
> Applying the successor function to 0 e times doesn't give me e?

There is no meaning to the operation of applying a function infinitely
many times.

> e is just another natural number as far as the model is concerned.

The theory of naturals has operations +, *, and successor. There is
no operation "apply successor e times".

> > The chains you've described are all terms in the extended
> > language of PA plus the constant e. There are only countably
> > many such terms.
>
> How do you know there are only countably many such terms?

Every term is a finite string in the symbols
+, *, S, e. There are only countably many finite strings.

It's a standard theorem of model theory that every theory
with countably many axioms has a countable model.

> > No. The model obeys all the theorems of PA. So in particular,
> > you can prove that there is no y such that y*Se = e.
>
> I don't follow this. Let e=3. There is no integer y such that:
>
> y*4 = 3
>
> If you are assuming y is a rational then y = e/Se.

As I said, the model is a model of PA, so any theorem of PA is
true of the model. In particular, it's a theorem of PA that
there is no y such that y*4=3. So it's true in this model, as
well. PA is a theory of naturals, not rationals.

[RussellE]

On Nov 5, 11:27 am, Daryl McCullough <stevendaryl3...@yahoo.com>
wrote:

> On Saturday, November 5, 2011 2:02:51 PM UTC-4, RussellE wrote:
> > On Nov 5, 5:58 am, Daryl McCullough <stevend...@yahoo.com> wrote:
> > > > This defines successor within a given chain.
> > > > It doesn't explain how successor would go
> > > > from one chain to the next.
>
> > > It doesn't. There is no way to get from one chain to the next by
> > > repeatedly applying the successor function. Successor only moves
> > > you around in one chain.
>
> > Applying the successor function to 0 e times doesn't give me e?
>
> There is no meaning to the operation of applying a function infinitely
> many times.

I am not applying sucessor "infinitely" many times.
I apply it e times.

> > e is just another natural number as far as the model is concerned.
>
> The theory of naturals has operations +, *, and successor. There is
> no operation "apply successor e times".

I can't define "apply sucessor n times" for some n in PA?

> > > The chains you've described are all terms in the extended
> > > language of PA plus the constant e. There are only countably
> > > many such terms.
>
> > How do you know there are only countably many such terms?
>
> Every term is a finite string in the symbols
> +, *, S, e. There are only countably many finite strings.

Yes, there are only countably many finite strings.

I meant to ask how do you know there are only countably
many chains in a non-standard model of PA?
And, does "countable" mean countable in ZFC (the meta-theory)?
Doesn't every model of PA think its own unvierse is countable?

> It's a standard theorem of model theory that every theory
> with countably many axioms has a countable model.

So I have been told.

> > > No. The model obeys all the theorems of PA. So in particular,
> > > you can prove that there is no y such that y*Se = e.
>
> > I don't follow this. Let e=3. There is no integer y such that:
>
> > y*4 = 3
>
> > If you are assuming y is a rational then y = e/Se.
>
> As I said, the model is a model of PA, so any theorem of PA is
> true of the model. In particular, it's a theorem of PA that
> there is no y such that y*4=3. So it's true in this model, as
> well. PA is a theory of naturals, not rationals.

We can define rational numbers as ordered pairs
of standard natural numbers.

I see that <e,Se> would NOT be a rational number
in ZFC. I guess this answers my question.
<e,Se> can't be used in ZFC to map the standard
natural numbers to the universe of a non-standard model.

[Frederick Williams]

RussellE wrote:

> I am not applying sucessor "infinitely" many times.
> I apply it e times.

Isn't e a non-standard natural number, and therefore infinite?

> I can't define "apply sucessor n times" for some n in PA?

You can for each particular natural number n, but how does that help?

> We can define rational numbers as ordered pairs
> of standard natural numbers.

Not in the language of PA.

[RussellE]

On Nov 5, 2:06 pm, Frederick Williams <freddywilli...@btinternet.com>
wrote:

> RussellE wrote:
> > I am not applying sucessor "infinitely" many times.
> > I apply it e times.
>
> Isn't e a non-standard natural number, and therefore infinite?

It is infinite in the meta theory, ZFC.
It is just another natural number in the model.

> > I can't define "apply sucessor n times" for some n in PA?
>
> You can for each particular natural number n, but how does that help?

e is a natural number in the model.

> > We can define rational numbers as ordered pairs
> > of standard natural numbers.
>
> Not in the language of PA.

Not in PA. In the meta-theory, ZFC.
I am interested in how ZFC can map the

standard natural numbers to the universe

on a non-standard model of PA.

I should say "PA+e" because I want to
define a non-standard natural number
I can play with.

So far, the only mapping presented
is a set of ordered pairs <z, q> where
z is an integer and q is a rational number.

We can represent integers as ordered pairs,
<a,b>, where a is a standard natural number
and b is 0 or 1 telling us if this is a positive
or negative integer.

Rationals can also be represented as
ordered pairs, <c,d>, where c and d are
standard natural numbers.

This mapping is a 4-ary function of
standard natural numbers.
I am still not convinced this allows us to
map all of the chains in a non-standard model.


Russell

[RussellE]

On Nov 5, 11:02 am, RussellE <reaste...@gmail.com> wrote:
> On Nov 5, 5:58 am, Daryl McCullough <stevendaryl3...@yahoo.com> wrote:
>
> For example, I think I can define another chain with:
>
> x = e/2 + e/4 + e/8 + ...
>
> (I probably have to replace e/2 with the least x such that x+x >= e).

F(n) = x1 + x2 + x3 + ...
where x1 is the greatest x where x+x < n,
x2 is the greatest x where x+x < x1,
x3 is the greatest x where x+x < x2, etc.

F(e) would be an "infinite" series in ZFC,
but it would terminate in the model.

F(e) = x1 + x2 + ... + 0

I think we can prove F(e) < e.

Proving e-F(e) is not finite in the
meta theory might be tougher.
I would need to prove this to say
F(e) is in a different chain than e.

[William Elliot]

On Sat, 5 Nov 2011, Daryl McCullough wrote:
> On Saturday, November 5, 2011 5:37:45 AM UTC-4, William Elliot wrote:
>> On Fri, 4 Nov 2011, Daryl McCullough wrote:

>>> The last question is easily answered: in arithmetic, x < y is
>>> defined as Ez (x+z+1) = y.
>>>
>> For the non-negative integers.
>
> That's what we're talking about, a nonstandard model of the nonnegative
> integers.

The set of objects of this non-standard model of PA (non-negative version)
is Z x [0,oo)/\Q in lexigraphical order.

What's 0? (0,0)?

>>> The successor relation is also pretty simple:
>>> S((n,q)) = (n+1,q)

Clearly S(x) = S(y) implies x = y.

Are you sure you mean Z and not Z+ = [0,oo) /\ Z?
In that model S(-1,0) = 0 or have I missed guessed the constant 0?

>> What are we modeling? Peano's axioms
> Yes.
>

> You can't *represent* induction, you just have to make sure that
> you satisfy it. Induction will be satisfied provided that any
> statement in the language of arithmetic that is *provable* must
> be true in your model. So for instance, we have statements such
> as (x+1)*3 > (x+1)*2
> x*3 = 3*x
> x*(y+1) = x*y + x
> etc.

> They all have to be true of the nonstandard elements, as well.
>

In that model, if P(0) and for all x, (P(x) ==> P(S(x)))
then P holds for all non-standard integers of the form (n,0), n in Z+.

That however, isn't all of the nonj-standard integers.

[FredJeffries]

On Nov 5, 11:24 am, RussellE <reaste...@gmail.com> wrote:
> On Nov 5, 11:27 am, Daryl McCullough <stevendaryl3...@yahoo.com>
> wrote:
>
> > On Saturday, November 5, 2011 2:02:51 PM UTC-4, RussellE wrote:
> > > On Nov 5, 5:58 am, Daryl McCullough <stevend...@yahoo.com> wrote:
> > > > > This defines successor within a given chain.
> > > > > It doesn't explain how successor would go
> > > > > from one chain to the next.
>
> > > > It doesn't. There is no way to get from one chain to the next by
> > > > repeatedly applying the successor function. Successor only moves
> > > > you around in one chain.
>
> > > Applying the successor function to 0 e times doesn't give me e?
>
> > There is no meaning to the operation of applying a function infinitely
> > many times.
>
> I am not applying sucessor "infinitely" many times.
> I apply it e times.

But your e is not a number that you can apply something that many
times to something.

[FredJeffries]

On Nov 5, 11:24 am, RussellE <reaste...@gmail.com> wrote:
>

> I meant to ask how do you know there are only countably
> many chains in a non-standard model of PA?

Because you are only considering countable non-standard models of PA.
Uncountable models would have uncountably many chains, for instance
ordered by the Real numbers.

> And, does "countable" mean countable in ZFC (the meta-theory)?
> Doesn't every model of PA think its own unvierse is countable?

PA knows nothing of countable/uncountable or finite/infinite or ...

"Countable" means countable in the meta-theory.

[FredJeffries]

On Nov 6, 5:37 am, FredJeffries <fredjeffr...@gmail.com> wrote:
> On Nov 5, 11:24 am, RussellE <reaste...@gmail.com> wrote:
>
>
>
> > I meant to ask how do you know there are only countably
> > many chains in a non-standard model of PA?
>
> Because you are only considering countable non-standard models of PA.
> Uncountable models would have uncountably many chains, for instance
> ordered by the Real numbers.

Sorry, I am wrong about that. The chains cannot have the order type of
the reals, but there are legal uncountable order types.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.2873

See theorems 3.1 and 3.2

[David Libert]

FredJeffries (fredje...@gmail.com) writes:
> On Nov 5, 11:24=A0am, RussellE <reaste...@gmail.com> wrote:
>> On Nov 5, 11:27=A0am, Daryl McCullough <stevendaryl3...@yahoo.com>

>> wrote:
>>
>> > On Saturday, November 5, 2011 2:02:51 PM UTC-4, RussellE wrote:

>> > > On Nov 5, 5:58=A0am, Daryl McCullough <stevend...@yahoo.com> wrote:
>> > > > > This defines successor within a given chain.
>> > > > > It doesn't explain how successor would go
>> > > > > from one chain to the next.
>>
>> > > > It doesn't. There is no way to get from one chain to the next by
>> > > > repeatedly applying the successor function. Successor only moves
>> > > > you around in one chain.
>>
>> > > Applying the successor function to 0 e times doesn't give me e?
>>
>> > There is no meaning to the operation of applying a function infinitely
>> > many times.
>>
>> I am not applying sucessor "infinitely" many times.
>> I apply it e times.
>
> But your e is not a number that you can apply something that many
> times to something.

I was going to respond to earlier similar comments in this thread,
and will make that response here.

I think it is reasonable to say that PA has a formalization of the
notion of repeated applications of successor S.

It is called +.

e applications of S to number a is a + e.

Similarly PA can formalize e applications of additions of a to 0.

e applications of a to 0 is a * e.

And e applications of addition of b to a is a + b*e.

Similarly, PA can formalize e applications of any defined unary
function f to a.

We can define the primitive recursion g:

g(x,0) = x

g(x, S(y)) = f(g(x, y)) .

Godel shows us how to formalize that definition in PA using the beta
function.

Then e applications of the defined f on a is g(a, e).

This arose when Russell asked about how to go between Z chains with
S.

People correctly replied that S only maps within each Z chain, there
is no mapping hoping Z chains with S.

Pure logic lets us make real world (ie meta-theory) finite
iterations of primitive and defined functions, by appropriate terms or
formulas. So by pure logic we could indeed only make finite
iterations of the primitive S.

But PA provides extra function symbols and axioms to make a
reasonable formalization of iterations even to non-standard internal
integers.

But the point is those formalizations involve + or more, so they
still fall into a separate case from Russell's question, not functions
build purely from S.



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

[FredJeffries]

On Nov 5, 2:47 pm, RussellE <reaste...@gmail.com> wrote:
> On Nov 5, 11:02 am, RussellE <reaste...@gmail.com> wrote:
>
> > On Nov 5, 5:58 am, Daryl McCullough <stevendaryl3...@yahoo.com> wrote:
>
> > For example, I think I can define another chain with:
>
> > x = e/2 + e/4 + e/8 + ...
>
> > (I probably have to replace e/2 with the least x such that x+x >= e).
>
> F(n) = x1 + x2 + x3 + ...
> where x1 is the greatest x where x+x < n,
> x2 is the greatest x where x+x < x1,
> x3 is the greatest x where x+x < x2, etc.
>
> F(e) would be an "infinite" series in ZFC,
> but it would terminate in the model.

Assuming that we can make sense of "..." and "etc", F(e) is definitely
NOT an infinite series (yes, I noticed the quotes). There would be
infinitely many terms, but they are not arranged in the same order as
the infinite series we meet in calculus class, so that would be
nonsense to speak of convergence (Yes, I realize that you haven't.
Yet.)

[RussellE]

> Yet.)- Hide quoted text -
>
> - Show quoted text -

F(e) is the sum of a "finite" sequence of natural numbers.
I don't see why the order of the terms makes any difference.
Addition is still distributive in non-standard models.
I think it is also obvious the sum must "converge".
I can prove F(x) < x.

I do have a problem with "greatest".
Each natural number is encoded as a 4-tuple in ZFC.
Because of the way we are encoding the non-standard
naturals, there may not be a "greatest" encoding.
However, there will always be a "least" encoding.
This is a new function using "least":

G(n) = x1+x2+...+0 where

x1 is the least x where S(x+x) >= n,
x2 is the least x where S(x+x) >= x1,
x3 is the least x where S(x+x) >= x2,
etc.

Again, we can prove G(n)<n.
If n is a power of 2 then G(n) = n-1.

Consider the set of all infinite binary
strings in a standard model of PA.
The length of each string is omega
which is less than e.

Define a set of natural numbers in the
non-standard model as:

x1 is least x where S(x+x) >= e,
x2 is least x where S(x+x) >= x1,
x3 is least x where S(x+x) >= x2,
etc.

We can define a number in an unique chain
in our non-standard model for each "infinite"
binary string in the standard model.

y = b1*x1 + b2*x2 + b3*x3 + ...

where b1, b2, b3, etc are 0 or 1 depending
on the infinite binary string.

Godel proved there are an uncountable
number of infinite binary strings.
There must be an uncountable number
of chains in any non-standard model of PA.

[Frederick Williams]

RussellE wrote:

>
> Consider the set of all infinite binary
> strings in a standard model of PA.

The standard model of PA contains natural numbers and three functions on
them. What is a binary string in the standard model of PA?

> Godel proved there are an uncountable
> number of infinite binary strings.

Eh?

[Frederick Williams]

RussellE wrote:

> The length of each string is omega
> which is less than e.

If omega is the usual ordinal of that name, and e is some non-standard
natural number, how do you compare them?

[Frederick Williams]

RussellE wrote:

> F(e) is the sum of a "finite" sequence of natural numbers.
> I don't see why the order of the terms makes any difference.
> Addition is still distributive in non-standard models.

What does addition is distributive mean? And what is its relevance to
whether the order of terms makes a difference to a sum?

[FredJeffries]

On Nov 6, 12:08 pm, RussellE <reaste...@gmail.com> wrote:
> On Nov 6, 6:32 am, FredJeffries <fredjeffr...@gmail.com> wrote:
> > On Nov 5, 2:47 pm, RussellE <reaste...@gmail.com> wrote:
>
> > > On Nov 5, 11:02 am, RussellE <reaste...@gmail.com> wrote:
>
> > > > On Nov 5, 5:58 am, Daryl McCullough <stevendaryl3...@yahoo.com> wrote:
>
> > > > For example, I think I can define another chain with:
>
> > > > x = e/2 + e/4 + e/8 + ...
>
> > > > (I probably have to replace e/2 with the least x such that x+x >= e).
>
> > > F(n) = x1 + x2 + x3 + ...
> > > where x1 is the greatest x where x+x < n,
> > > x2 is the greatest x where x+x < x1,
> > > x3 is the greatest x where x+x < x2, etc.
>
> > > F(e) would be an "infinite" series in ZFC,
> > > but it would terminate in the model.
>
> > Assuming that we can make sense of "..." and "etc", F(e) is definitely
> > NOT an infinite series (yes, I noticed the quotes). There would be
> > infinitely many terms, but they are not arranged in the same order as
> > the infinite series we meet in calculus class, so that would be
> > nonsense to speak of convergence (Yes, I realize that you haven't.
> > Yet.)- Hide quoted text -
>
> > - Show quoted text -
>
> F(e) is the sum of a "finite" sequence of natural numbers.
> I don't see why the order of the terms makes any difference.

Then you don't understand the chains that you have been talking about.

You do not have an infinite series. You have what is known as a
hyperfinite sum. It is unfortunate that the same word "infinite" is
used for both. But an infinite series is not a hyperfinite sum and a
hyperfinite sum is not an infinite series and it is nonsense to speak
of convergence when considering a hyperfinite sum.

I do not like to sound harsh to someone who is obviously eager to
learn, but you must learn the basics.

[RussellE]

> learn, but you must learn the basics.- Hide quoted text -

>
> - Show quoted text -

Thanks fo pointing out my function is a hyperfinite sum.
I looked it up: http://en.wikipedia.org/wiki/Hyperfinite_set

The wiki says the sum of a hyperfinite set of real numbers
always exists. I assume the same will be true for a
hyperfinite set of natural numbers.

Since we are talking about a (hyper) finite sum,
I don't see why we need to speak about convergence.

[Ross A. Finlayson]

Uncountable models of the naturals (of Peano arithmetic, well-ordered)
and corresponding hyperfinite sums of reals? (The paper notes:
Corollary 7.5, Neither R nor Q is interpreted in uncountable models of
PA.) That would be an uncountable well-ordered set of reals in their
normal ordering.

What are these hyperfinite sums? Basically series couched in
Robinson's hyper-naturals/hyper-reals, the rationals and irrationals
are dense in the reals there, as would be their analogs in extensions
and embeddings.

[RussellE]

On Nov 6, 12:48 pm, Frederick Williams <freddywilli...@btinternet.com>
wrote:

> RussellE wrote:
>
> > Consider the set of all infinite binary
> > strings in a standard model of PA.
>
> The standard model of PA contains natural numbers and three functions on
> them.  What is a binary string in the standard model of PA?

I meant in ZFC. We can define binary sequences in ZFC
as sets of ordered pairs, (a,b), where a is a natural number
and b is either 0 or 1.

> > Godel proved there are an uncountable
> > number of infinite binary strings.
>
> Eh?

My mistake. I meant Cantor's diagonal proof:
http://en.wikipedia.org/wiki/Cantor's_diagonal_argument

My proof that all non-standard models of PA have
an uncountable number of chains seems quite
straight forward.

Assume we define a model of PA+e in ZFC.

Define the set of all binary sequences of length e.
{ {(0,0), (1,0), ..., (e,0)}, {0,0), (1,0), ..., (e,1)}, ... }

Consider the subset of these sequences where
any ordered pair, (x,y). in the sequence having x
equal to a non-standard natural number also has y=0.
Let S be this set of sequences.

The diagonal argument proves S is larger than the
universe of the standard model of PA.

Each sequence in S can be used to define an
unique natural number in our non-standard model.

y = b0*x0 + b1*x1 + ...

where
x0 is least x where S(x+x) >= e,
x1 is least x where S(x+x) >= x0,

x2 is least x where S(x+x) >= x1,

etc.

and b0, b1, ... are the second values of
of the ordered pairs in the sequence.

Let y_i and y_j be the natural numbers defined
by two different sequences.

y_i and y_j must differ by a nonstandard
natural number. This means y_i and y_j
must be in different chains.

Every sequence defines a y that must be in chain
unique from the chains define by other sequences.
There are an uncountable number of sequences.

I have to prove the set {x0, x1, ...} has at least
omega many non-standard elements.
I don't see any problem proving this.

Does anyone see an obvious error?

[Ross A. Finlayson]

Paris and Kirby purport that there is a nonstandard yet countable
model of the naturals, eg with the 1-point compactification point at
infinity, or, the naturals are compact in line with a Spinozan
continuum.

[FredJeffries]

On Nov 7, 6:27 pm, RussellE <reaste...@gmail.com> wrote:

You're mixing up infinite series with hyperfinite sums.

...111111 (where there is a 1 only at every standard index) is not a
nonstandard natural number any more than it is a standard natural
number.

[RussellE]

I think I see the difference.
Assume we have a function that adds one
for each element of a set. For example,
given the set {1,2,3} this function gives us
1+1+1 = 3

This function would be undefined for the set {1,2,3,...}.
The function would be defined for the hyper-finte set
{1,2,3,...,e-1,e}.

1+1+...+1 = e

The main reason I am interested in "infinite" sets is
because they are they only way I know of to prove
some set is uncountable.

For example, Cantor proved the set of all infinite
binary sequences is uncountable.

Can uncountable models of PA have uncountable
hyper-finite sets?

[FredJeffries]

On Nov 8, 6:25 pm, RussellE <reaste...@gmail.com> wrote:
> On Nov 8, 6:42 am, FredJeffries <fredjeffr...@gmail.com> wrote:
>
> > On Nov 7, 6:27 pm, RussellE <reaste...@gmail.com> wrote:
>
> > You're mixing up infinite series with hyperfinite sums.
>
> > ...111111 (where there is a 1 only at every standard index) is not a
> > nonstandard natural number any more than it is a standard natural
> > number.
>
> I think I see the difference.
> Assume we have a function that adds one
> for each element of a set. For example,
> given the set {1,2,3} this function gives us
> 1+1+1 = 3
>
> This function would be undefined for the set {1,2,3,...}.
> The function would be defined for the hyper-finte set
> {1,2,3,...,e-1,e}.
>
> 1+1+...+1 = e

Yes, that is correct

>
> The main reason I am interested in "infinite" sets is
> because they are they only way I know of to prove
> some set is uncountable.
>
> For example, Cantor proved the set of all infinite
> binary sequences is uncountable.
>
> Can uncountable models of PA have uncountable
> hyper-finite sets?

Yes. In an uncountable model, for any nonstandard number e the set

{1, 2, 3, ..., e-2, e-1, e}

is uncountable.

[Ross A. Finlayson]

Err... nonstandard means "not finite but representative of a successor
of 0 in the model", not necessarily uncountable.

Where e might be a limit ordinal (in natural/primitive form), its
predecessor isn't necessarily well-defined.

That's not to say that it isn't in line with Cantorian infinite sets
to count backward from infinity, in that in a variety of contexts he
used each of zero and infinity to reach toward each other. In the
classical post-Cantorian (of Russell, Zermelo, and Fraenkel) there's
no going back from limit ordinals, vis-a-vis some neo-post-
Cantorianism that looks at the infinite in terms of symmetries and
simple principles of conservation/preservation instead of necessarily
divergence.

[RussellE]

I think my argument still works.
I have to show there are upper and lower bounds
for the functions I define.

A binary sequence is a set of order pairs, (a,b),
where a is a natural number and b is 0 or 1.

Let S be the set of all binary sequences of length e.
Define T to be a subset of S.

s in S is a member of T if every non-standard
position of s is 0.

There is an obvious bijection between T and
the set of all "infinite" binary sequences Cantor
used in his proof. The diagonal argument proves
T does not have a bijection with the set of
standard natural number, N.

I define a form of integer division by 2.

H(n) = x where (x+x =< n) AND (S(x+x) >= n)

There can be only one such x for a given n.

Next, I define a base set, B.
b_0 = H(e)
b_i = H(b_i-1)

B is a hyper-finite set containing 0.
The sum of set B is less than e.

Notice, b_j is greater than the
sum of all b_k for k>j.

Finally, I define a function, F(s),
where s is a binary sequence.

F(s) = s_0*b_0 + s_1*b_1 + ... + s_k*0

where s_i is 0 or 1 as defined by the sequence.

Let t_1 and t_2 be sequences in T.

t_1 = 1000...00
t_2 = 0111...00

We can prove F(t_1) > F(t_2)
from the properties of B.
b_0 is greater than the sum
of all other b_i.

We can also prove F(t_1) - F(t_2) is not finite.
This means F(t_1) and F(t_2) must be
in different chains.

Any two sequences in T must differ at
some finite position by construction.

Since each F(t_i) must be in a distinct chain,
there must be an uncountable number of chains.

We can argue that F(t) can't be evaluated for
some t, but we can still put upper and lower
bounds on F(t). These bounds differ from all
other sequences proving F(t) defines a set of
distinct chains.

T is a hyper-finite set. Cantor's diagonal
argument works on finite sets, too.


Russell
- The universe is one dimensional.

[David Libert]

FredJeffries (fredje...@gmail.com) writes:
> On Nov 8, 6:25=A0pm, RussellE <reaste...@gmail.com> wrote:
>> On Nov 8, 6:42=A0am, FredJeffries <fredjeffr...@gmail.com> wrote:

>>
>> > On Nov 7, 6:27=A0pm, RussellE <reaste...@gmail.com> wrote:
>>
>> > You're mixing up infinite series with hyperfinite sums.
>>
>> > ...111111 (where there is a 1 only at every standard index) is not a
>> > nonstandard natural number any more than it is a standard natural
>> > number.
>>
>> I think I see the difference.
>> Assume we have a function that adds one
>> for each element of a set. For example,
>> given the set {1,2,3} this function gives us

>> 1+1+1 =3D 3

>>
>> This function would be undefined for the set {1,2,3,...}.
>> The function would be defined for the hyper-finte set
>> {1,2,3,...,e-1,e}.
>>

>> 1+1+...+1 =3D e

>
> Yes, that is correct
>
>>
>> The main reason I am interested in "infinite" sets is
>> because they are they only way I know of to prove
>> some set is uncountable.
>>
>> For example, Cantor proved the set of all infinite
>> binary sequences is uncountable.
>>
>> Can uncountable models of PA have uncountable
>> hyper-finite sets?
>
> Yes. In an uncountable model, for any nonstandard number e the set
>
> {1, 2, 3, ..., e-2, e-1, e}
>
> is uncountable.

Why is this? I think I have counterexamples, below.

I will be constructing models by the model-theoreitc method of
order indiscernibles. This method using Ramsey's theorem.

http://en.wikipedia.org/wiki/Indiscernibles

http://en.wikipedia.org/wiki/Ramsey%27s_theorem

There is a section on indiscernibles in Chang and Keisler
_Model Theory_ .

The method of indiscernbiles requires proving a theory with
indiscernibilty axioms is consistent. This is done by invoking
compactness to reduce to proving the consistency of finitely many
indiscernibility axioms, and then invoking Ramsey's theorem for that.

I will be needing some additional properties of the indicernibles
for my examples. So I will redo those style proofs as just noted,
also doing extra similar steps to get those extra properties.

Namely I form the theory in PA language with extra indiscernible
constants c_0, c_1, ... . I will have the usual axioms of PA, and
the usual order indiscernibilty axioms as the usual method. I take
this theory as Skolemized.

I will also have an extra schematum of axioms: for f an n-ary
Skolem function f(c_0, c_1 , ... , c_n-1) < c_n.

Finally, an additional axiom schemataum saying large indiscernibles
don't matter: for i < n and f n-ary Skolem function:

f(c_0, c_1, ... , c_n-1) < c_i ->

f(c_0, ... , c_n-1) =
f(c_0, ... , c_i-1 , c_n, c_n+1, ... , c_2n-i-1) .


That first schematum is not automatic for indiscernible theories
over PA. To see this, take a nonstandard model of PA. Skolemize it
in that model so some Skolem function takes on nonstandard value say
the formula x=x get nonstandard Skolem constant. Using truth of
these Skolemized functions in that model, do Ramsey's theorem on the
standard copy of omega in the model to make an indiscernibles theory.
So obtain an indiscernables theory with a Skolem constant bigger than
all indiscernables.

Anyway, I do what that property (small Skolem outputs) for my
theory, so will do extra work to obtain it.

I want to see that theory above is consistent. So by compactness
this is reduced to the consistency of Skolemized PA with finitely many
instance of the 3 schemata: indiscerniblity, small Skolem output, and
the independence from large indiscernibles.

So given such a finite subtheory, we seek to prove its conistency by
finding a model with the standard Skolemized PA, and a homegeneous set
to be the indiecernables, but for only finitely many instancs of the 3
schemata together.

Colour tuples by truth/falsity of the formulas from the finite
instances of indiscernility axioms. Find an infinite homogenous set
for these by Ramsey's theorem. This is like the usual proof of
consistency oin the method of indiscernibles.

Any infinite subset of that first homogenous set will give a set
still indiscernible with respect to the finitely many formulas we are
handling from the indiscernibilty schematum.

We will thin this set down more to get the other schemata. Doing
this will not lose the indiscerniblity we already had, by the last
observation about subsets.

We turn to thinning the homogenous set to get the last 2 schemata,
small Skolems and indepoendence from large indiscernibles.

We desigante the case of small Skolem
f(c_0, c_1 , ... , c_n-1) < c_n as primarily dependent on
c_0, ... , c_n-1 .

We designate the case of indeopendence axiom

f(c_0, c_1, ... , c_n-1) < c_i ->

f(c_0, ... , c_n-1) =
f(c_0, ... , c_i-1 , c_n, c_n+1, ... , c_2n-i-1) .

as primarily dependent on c_0, c1, ... , c_i-1 .

We will thin the homogenous set in stages, first to handle all those
axioms of the 2 schemata primarly dependent on c_0, then those
primailry dependent on c_0, c1 then on c_0, c1 , c2 etc. There
are only finitely many axioms so there are only finitely many such
steps.

So first to thin the homegenous set to get all axioms primarily
dependent on c_0.

This thinning step will not remove c_0. It will only thin beyond
c_0, ie replace the original homogenous set by a possibly smaller but
still infinite subset, but still containing c_0 as member.

For the smallness schemtatum: f(c_0) < c_1, for finitely many unary
Skolem functions, we simply move out in the infinite homogenous set
to a value larger than those finitely many f(c_0) ie, for various
choices of f from our finite fragement of the scehamtum.

Discard all memebers of the first homogenous set > c_0 but smaller
than that bound above the f(c_0). Keep all the rest of the
homegenous set, so still infinite.

Then any infinite subset of this infinite set which still has c_0 as
member will satisfy the finitely many instances of the smallness
axioms.

We will make sure that all later thinning steps don't discard this
c_0, so our final result will still retain this prooerty so far.

Next to get the c_0 primary version of the independence schematum:

f(c_0, c_1, ... , c_n-1) < c_0 ->

f(c_0, ... , c_n-1) =
f(c_0, ... , c_n+1, ... , c_2n-i-1) .

For each of the finitely many Skolem functions f in our finite
fragment of the schematum, we make a colouring function on increasing
n-1 tuples from the homegenopus so far - {c_0}.

(The homogenous set we are sorking with is the result of the
previous step to get the smallness schematum.)

Namely given increasing tuple x1 , ... x_n-1, we consider
f(c_0, x1, ... x_n-1). If this is < c_0 colour this as that
value < c_0.

If that f evaluation is >= c_0, colour that tuple as c_0, a
label to record the value was >= c_0.

This gives a finite cardinality <= c_0 colluring on tuples for each
of the finitely many f Skolem functions.

So make our final colouring be the finite Cartesian product over
these finitely many f of those colourings.

Do Ramsey's theorem on this coloring, to obtain an infinte
homogenous subset of our last homogenous set.

Our final homogenous set will be {c_0} union the last one above.

The new homogenity property guarantees all f on increasing tuples
over first c_0 are either uniformly >= c_0 or are the same
constant value < c_0.

We retain the first stage indiscernibolty properties, by being a
subset of that homogenous set. And we retain the the c_0 primary
work above on the smallness schematum by not having thrown away c_0
and by taking an infinite subset of that.

So we have all three schemata to primary c_0.

Next primary c_0, c_1. Do similar steps for f(c_0, C_1), and for
f(c_0, c_1, x,2 , ... , x_n-1). This c_1 is the 2nd element from the
last step. We thin down beyond c_1, retaining c_0, c_1.

Similarly, repeat for the finite steps, always thinning on the tail
over the fixed initial segment from the last step.

The final homogenous set produces satisfies our finite fragments of
the 3 schemata.

So by compactness, we have the consistency of the indiscenibility
theory.

Now make an indiscernible model for it, based on an uncountable
linear ordering with least element, i_0.

Then by the indepedence of large indiscernibles schematum, i_0 in the
resulting model has only countably many elements below it.

Taking e - i_0, this is a countereaxmple uncountably many below any
non-standard element.

We can make a more striking model. Take aleph_1 indiscernibles, ie
the linear ordering on indiscernibles is ordinal aleph_1.

Then each indiscernible has only countably many model elements below
it.

Also, by the smallness schematum, the indicernibles are cofinal in
the model.

So each element in the model has only countably many elements below.

The model is uncountable by including aleph_1 indiscernibles.

So it is poosisble to have an uncountable PA model with no elements
having uncountably many below themselves.

It is also possible to have in other models, an element e with
uncountably many below it as you said, by compactness.



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

[FredJeffries]

On Nov 10, 10:27 pm, ah...@FreeNet.Carleton.CA (David Libert) wrote:

> FredJeffries (fredjeffr...@gmail.com) writes:
>
> > Yes.  In an uncountable model, for any nonstandard number e the set
>
> > {1, 2, 3, ..., e-2, e-1, e}
>
> > is uncountable.
>
>   Why is this?  I think I have counterexamples, below.

Thank you very much for the clarification. I obviously was
misremembering.

[FredJeffries]

It seems to me that your function F is only well-defined at those
sequences which are 1 at only finitely many places. There are
countably many such sequences.

I am not clear what you mean by "putting upper and lower bounds of
F(t)".

I can agree that we could say that e is an upper bound and H(e) a
lower bound for F(t) for ant t where t has a 1 at the first position.
But those two chains have already been counted.

[David Libert]

FredJeffries (fredje...@gmail.com) writes:
> On Nov 8, 6:25=A0pm, RussellE <reaste...@gmail.com> wrote:
>> On Nov 8, 6:42=A0am, FredJeffries <fredjeffr...@gmail.com> wrote:

>>
>> > On Nov 7, 6:27=A0pm, RussellE <reaste...@gmail.com> wrote:
>>
>> > You're mixing up infinite series with hyperfinite sums.
>>
>> > ...111111 (where there is a 1 only at every standard index) is not a
>> > nonstandard natural number any more than it is a standard natural
>> > number.
>>
>> I think I see the difference.
>> Assume we have a function that adds one
>> for each element of a set. For example,
>> given the set {1,2,3} this function gives us

>> 1+1+1 =3D 3

>>
>> This function would be undefined for the set {1,2,3,...}.
>> The function would be defined for the hyper-finte set
>> {1,2,3,...,e-1,e}.
>>

>> 1+1+...+1 =3D e

>
> Yes, that is correct
>
>>
>> The main reason I am interested in "infinite" sets is
>> because they are they only way I know of to prove
>> some set is uncountable.
>>
>> For example, Cantor proved the set of all infinite
>> binary sequences is uncountable.
>>
>> Can uncountable models of PA have uncountable
>> hyper-finite sets?
>
> Yes. In an uncountable model, for any nonstandard number e the set
>
> {1, 2, 3, ..., e-2, e-1, e}
>
> is uncountable.

[1] David Libert "Re: What Does a Non-Standard Model of PA Look Like in ZFC?"
sci.logic Nov 11, 2011
http://groups.google.com/group/sci.logic/msg/ded93f54c7be5d7c


posted about uncountable PA models with some or all elements having
only countably many numbers below themselves.

I will just add now, there are other PA models which do act like you
were writing above, namely every nonstandard e has uncountably many
numbers below it.

We will construct such a model by making a theory extending
Skolemized PA with new constants and axioms. To start we add an
uncountable set of constants and pairwise ~= axioms which together say
all constants have distinct denotations.

This theory is constistent, by compactness. Extend this by Zorn to
a complete consistent theory.

For a next stage, for every Skolem term built by Skolem functions
and the first round of new constants, if the last complete theory
decided each standard numeral is < the Skolem term, we add a distinct
copy of the same cardinality of yet new constants, and pairwise
~= axioms saying these are all distinct denotations, and axioms
saying each of these new constants is < the Skolem term being
handled.

These new axioms just added are still consistent, since any finite
subset is. Each finite subset puts a finite lower bound on finitely
many Skolem terms, but those are Skolem terms which the previous
complete theory already decided as nonstandard by putting all standard
numerals below.

There are countably many Skolem functions, we have to take them over
all finite tuples of the first uncountable set of constants added.
This is cardinality aleph_0 * the cardinality of all finite tuples
from the first uncountable set of constants. With AC this is = the
cardinality of that first set of constants.

We extend this theory to a complete theory by Zorn.

For a third stage, we add a new distinct copy of the same
carrinality of still new contants, for each Skolem term built by any
Skolem function and all tuples of constants from the first two stages,
for Skolem terms which the last complete made nonstandard.

The first two stages are combined constants cardinality 2 * the base
uncountable set, with AC still that same caridnailty of the base set.

We add the similar axioms, each new batch of constants is distinct
and is < the associated Skoelm term.

By the same calculation as the previous stage, this new stage has
added that same uncountable cardinalty of new constants.

And as the previous stage, this theory is consistent.

And so we continue through omega stages, adding new constants to put
uncountably many elements below each previous Skolem term denoting a
nonstandard.

At every stage the cardinality of all constants is that same
uncountable cardinality.

We finally stop at stage omega, the union of all finite stages.
This has made omega * the base uncountable cardinality many
constants, ie omega stages, which by AC is the same base uncountabe
cardinality.

All Skolem terms over that combined set of constants is still same
cardinality by AC.

The resulting theory combining all constants and added axioms of the
omega stages is consistent, being an omega union of consistent
theories.

Every Skolem term in the omega'th theory comes from finitely many
new constants, so a bounded stage in the construction, so was handled
in the next stage of the constuction to get uncountably many below if
nonstandard.

From this Skolemized theory at omega'th stage we can build a term
model of only those constants and Skolem terms.

This model has cardinality our base uncountable cardinailty. And
every nonstandard element of this model has that same cardinailty of
elements below it.

So in any uncountable cardinality, with AC we can have a PA model of
that cardinailty, so that each nonstandard element e has uncountably
many, indeed the same uncountable cardinality has the entire model,
elements below it.



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

[RussellE]

On Nov 11, 12:24 pm, FredJeffries <fredjeffr...@gmail.com> wrote:
> On Nov 8, 11:23 pm, RussellE <reaste...@gmail.com> wrote:
>
> It seems to me that your function F is only well-defined at those
> sequences which are 1 at only finitely many places. There are
> countably many such sequences.

There are at least countably many sequences with finitely
many ones. What about sequences with a hyper-finite
number of 1's? F(t) has a value even if we can't
determine what the value is.

> I am not clear what you mean by "putting upper and lower bounds of
> F(t)".
>
> I can agree that we could say that e is an upper bound and H(e) a
> lower bound for F(t) for ant t where t has a 1 at the first position.
> But those two chains have already been counted.

Given two sequences in T, t_a and t_b, we can put bounds
on F(t_a) and F(t_b) that prove they differ by more than
a finite amount.

We know t_a and t_b differ at some finite position, k.
Assume t_a has a 1 at position k and t_b has a 0 at
position k. Even assuming that t_a has all 0's
for positions greater than k and t_b has all 1's for
positions greater than k, we can prove F(t_a) > F(t_b).
We can also prove:

F(t_a) - F(t_b) >= b_k - SUM(all b_m, m>k).

I can refine my argument to address the issues
you bring up. I need to redefine the sets B and T.
I will still use the integer divide by 2 function H(n).

b_0 = e * H(e)
b_i = e * H(b_i-1)

Now we have: e < SUM(B) < e*e

Let T be the set of all sequences wjth length |B|.
We can use the diagonal argument to prove
no list of sequnces with length |B| exhausts
all of the sequences of length |B|.
The powerset of B is larger than B.
We can also show B has at least omega
many terms.

Let t_a and t_b be sequences in T and
let F(t_a) > F(t_b). We can prove:

F(t_a) - F(t_b) >= e

We can prove this even when we can't
evaluate F(t_a) or F(t_b). All we need
to know is t_a and t_b differ at some
position.

[FredJeffries]

On Nov 12, 3:32 pm, RussellE <reaste...@gmail.com> wrote:
> On Nov 11, 12:24 pm, FredJeffries <fredjeffr...@gmail.com> wrote:
>
> > On Nov 8, 11:23 pm, RussellE <reaste...@gmail.com> wrote:
>
> > It seems to me that your function F is only well-defined at those
> > sequences which are 1 at only finitely many places. There are
> > countably many such sequences.
>
> There are at least countably many sequences with finitely
> many ones. What about sequences with a hyper-finite
> number of 1's? F(t) has a value even if we can't
> determine what the value is.

You were considering only sequences which are 0 at every nonstandard
index. Are you changing that qualification?

[FredJeffries]

On Nov 12, 3:32 pm, RussellE <reaste...@gmail.com> wrote:

But F(t_a) and F(t_b) don't necessarily exist. The situation seems
analogous to approximating irrational numbers by sequences of
rationals. Your F(t_a) and F(t_b) would (if they existed) fall in the
gaps.

[RussellE]

Yes. I don't need to only consider sequences where
non-standard positions are 0. I can prove the the
powerset of B is greater than B without this
assumption.

[RussellE]

> gaps.- Hide quoted text -

>
> - Show quoted text -

The values of F(t_a) and F(t_b) do exist.
They are hyper-finite sums.

We may not be able to evaluate them, but they do exist.
Since I am trying to prove there are an uncountable number
of distinct sums, my argument will look similar to proving
the irrationals are uncountable.

Unlike sequences of rationals, I can show the
hyper-finite sequences terminate.


Russell
- Integers are an illusion.

[FredJeffries]

No, actually they aren't for most "sequences"

>
> We may not be able to evaluate them, but they do exist.
> Since I am trying to prove there are an uncountable number
> of distinct sums, my argument will look similar to proving
> the irrationals are uncountable.
>
> Unlike sequences of rationals, I can show the
> hyper-finite sequences terminate.

Having them terminate is not enough. For instance, your "sequence"
with 1 at all standard positions and 0 at nonstandard positions
through e does not yield a hyperfinite sum.

Another example, consider a "sequence" with 1 at every position except
for one chain where it is 0 for each element of that chain. That
"sequence" also will not yield a hyperfinite sum.

[RussellE]

> "sequence" also will not yield a hyperfinite sum.- Hide quoted text -

>
> - Show quoted text -

Would you give examples of sequences that
do yield hyper-finite sums? For example,
would a sequence where every non-standard
position is "1" yield a sum?

Are you saying we can't evaluate the sum
or are you saying no sum exists?
I am certainly not an expert on hyper-finite
sums, but the wiki article said hyper-finite
sums always exist.

I think I can come up with a formula such
that every natural number, within a range,
is the sum of one particular sequence.
This probably requires making some
assumptions about e, like e is a power of 2.

[FredJeffries]

These "sequences" are of length e, right?

(1, 0, 1, 0, 1, ..., 0, 1, 0) (assuming e is even)

(1, 0, 0, 1, 1, 1, 0, 0, 0, 0, ..., 1)

All 1 up to H(e) and 0 thereafter.

If you can describe a sequence for standard e the same rule will work
for nonstandard e.

The problem comes when you try to change at a limit, such as o for
every standard, 1 for every non-standard. You've got to do the change-
over at a definite position. You can have infinitely many change=overs
but they have to occur at a definite place: at place n it is 0 and at
S(n) it is 1, or vice versa.

>
> Are you saying we can't evaluate the sum
> or are you saying no sum exists?

I am saying that they are not hyper-finite sums at all. They do not
satisfy the definition of hyper-finite sum.

> I am certainly not an expert on hyper-finite
> sums, but the wiki article said hyper-finite
> sums always exist.

It also says "A hyperfinite set has minimal and maximal elements". The
set of standard numbers has no maximum, so it is not a hyperfinite
set. A particular chain has no minimum nor maximum.

>
> I think I can come up with a formula such
> that every natural number, within a range,
> is the sum of one particular sequence.
> This probably requires making some
> assumptions about e, like e is a power of 2.

If it works for standard numbers, it will work.

[RussellE]

> If it works for standard numbers, it will work.- Hide quoted text -

>
> - Show quoted text -

Thanks for the explanation.
I think I can modify my proof so the sums of
hyper-finite sets in the proof are always defined.

Sorry to keep changing my proof.
Thanks for pointing my errors.

Let Q(n) be integer division by 4:

Q(n) = x
where ((x+x+x+x)=<n) and ((x+x+x+x+3)>=n)

Define the base set, B:

b_0 = Q(e)
b_i = Q(b_i-1)

B is a hyper-finite set containing

0 and (1 or 2 or 3).

SUM(B) < e.

b_k > SUM(all b_m, m>k)

Let b = |B|

Let S be the set of all binary
sequences of length b-1.
(I am ignoring the 0 in B).

Let x be a sequence in S and
define G(x):

G(x) = e*(x0+1)*b_0 +
e*(x1+1)*b_1 +
e*(x2+1)*b_2 +
...

where x0, x1, etc are the values, (0 or 1),
of the sequence at that position .

By adding 1 to each xi,
G(x) is the hyper-finite sum of b-1
non-zero natural numbers.

Let x and y be sequences in S and x != y.
We can determine if G(x) > G(y).

Assume G(x) > G(y).
By construction, G(x)-G(y) >= e.
Every G(x) must be in a chain distinct
from every other G(y).

Now, prove S is uncountable.
Let N be the set of all standard natural numbers.
Assume B and N have a bijection and
S and N have a bijection.

This means B has a bijection with S.
We know this is false from the diagonal argument.
N can not have a bijection with both B and S.

S is uncountable.


Russell
- Never never means never in set thoery.

[FredJeffries]

So you're changing 0 to 1 and 1 to 2. They still do not yield
hyperfinite sums.

The laws of arithmetic must still work, the usual associative,
commutative and distributive laws.

Take our "sequence" which has 1 for every standard and 0 otherwise.
Regroup so that we get all the x_i+1 = 1 together and all the x_i+1 =
2 together. You need to be able to add these "subsequences"
individually, but neither is a hyperfinite sum.

[Frederick Williams]

David Libert wrote:
>
> [...]

Thanks for the citations.

Kaye proves (Thm 6.4) that if M is a non-standard model of PA then the
reduct of M to the model with just the relation < is isomorphic to N +
Z.A where (A, <) is a dense linear order.

The second < is the first < restricted to A.

[Bill Taylor]

On Nov 17, 8:22 am, Frederick Williams <freddywilli...@btinternet.com>
wrote:

> Kaye proves (Thm 6.4) that if M is a non-standard model of PA then the
> reduct of M to the model with just the relation < is isomorphic to N +
> Z.A where (A, <) is a dense linear order.

Should that last phrase be
"dense linear order without first or last element"
or can we dispense with that restriction?

-- Wondering Willy

[Bill Taylor]

On Nov 17, 8:22 am, Frederick Williams <freddywilli...@btinternet.com>
wrote:

> Kaye proves (Thm 6.4) that if M is a non-standard model of PA then the
> reduct of M to the model with just the relation < is isomorphic to N +
> Z.A where (A, <) is a dense linear order.

Should that last phrase be

"dense linear order with no first or last element",

or can we dispense with that restriction?

-- Wondering Willy.

[Frederick Williams]

Bill Taylor wrote:
>
> On Nov 17, 8:22 am, Frederick Williams <freddywilli...@btinternet.com>
> wrote:
>
> > Kaye proves (Thm 6.4) that if M is a non-standard model of PA then the
> > reduct of M to the model with just the relation < is isomorphic to N +
> > Z.A where (A, <) is a dense linear order.
>
> Should that last phrase be
> "dense linear order without first or last element"

Yes, for Kaye a DLO is a DLO without first or last element.

> or can we dispense with that restriction?

Presumably not.

[David Libert]

Frederick Williams (freddyw...@btinternet.com) writes:
> Bill Taylor wrote:
>>
>> On Nov 17, 8:22 am, Frederick Williams <freddywilli...@btinternet.com>
>> wrote:
>>
>> > Kaye proves (Thm 6.4) that if M is a non-standard model of PA then the
>> > reduct of M to the model with just the relation < is isomorphic to N +
>> > Z.A where (A, <) is a dense linear order.
>>
>> Should that last phrase be
>> "dense linear order without first or last element"
>
> Yes, for Kaye a DLO is a DLO without first or last element.
>
>> or can we dispense with that restriction?
>
> Presumably not.

Agreed. A is provably without first or last element.

[1] David Libert "Re: Modular Arithmetic is Uncomputable"
sci.logic, sci.math Oct 6, 2011
http://groups.google.com/group/sci.logic/msg/1dc74a9013dae889

proved for countable PA models A is order isomorphic to the
rationals.

That proof did not invoke the premise of the model being countable
for the opening parts. Those opening parts proved the A arising from a
PA model, not using the countability assumption, is dense and with no
first or last element. (Though [1] phrased it in terms of Z copies
rather than A.)

The proof then invoked the countability premise and the above
claim to conclude the Z copies are ordered like the rationals.

Extracting trhe early section from [1] and noting it didn't use the
countability premise proves (rephrasing in A terms) that A is DLO
without first and last element.



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