[FOM] 620: Nonstandardism 2

[Harvey Friedman]

I want to focus some on nonstandard arithmetic, which is of course
less involved than nonstandard analysis.

First le me finally state properly that system of mine from my
undergraduate days at MIT, about 1966.

We have the usual language of PA with 0,S,+,x, and the unary predicate
ST (being standard).

1. The usual axioms for PA with 0,S,+,x.
2. Induction for the standard integers for all formulas in the
extended language.
3. There exists a nonstandard integer.
4. Transfer. If a formula with standard parameters has a witness, then
it has a standard witness.

I showed that this is conservative over PA.

The axioms imply that the standard integers form a proper initial
segment of the integers, which is also an elementary submodel of the
integers for all formulas not mentioning ST.

We can think of this in the Nelson matter, that the full universe is
the actual nonnegative integers, but we have a predicate for "standard
nonnegative integer", which is not of the usual mathematical world. We
can also think of the standard integers as the actual mathematical
integers, and there is some concept of "nonstandard or outer integer".

No matter how you look at this situation, you would want, ideally, for
there to be some serious robustness.

There are quite a number of things along these lines that you would
want. For example.

1. If we are thinking of the standard integers as the real integers,
then what choice of nonstandard integer system are we going to have?
If it is not going to be unique up to isomorphism, then can we at
least know that we can determine what the first order theory of the
full nonstandard integer system is with the predicate for being
standard? This leads to some precise questions of some interest.

2. If we are thinking of the entire system, including nonstandard
integers, as the true mathematical system, with the extra mathematical
notion of "standard", then in what way can we uniquely pick out the
standard integers? Or at least determine the first order theory of the
entire system, with the predicate for standard?

These two questions immediately suggest a number of theorems. Some of
these theorems go the wrong way, suggesting a lot of non robustness,
non uniqueness, etc. Others go the right way, suggesting a lot of
robustness and uniqueness.

Robust features are why I am interested in Nonstandardism in the first
place. I am highly skeptical, however, of a lot of Philosophy of
Nonstandism that I see, and will take this up in later postings.

1. INDUCTIVE ELEMENtARY EXTENSIONS

We can easily encapsulate the essence of my 1966 theory above,
thinking in the up direction. What we have is M,M", where

i. M is a model of PA.
ii. M' is a proper elementary extension of M.
iii. M satisfies induction for all first order properties of (M,M').

Obviously the induction in i follows immediately from the induction in
iii. But the reason we state this in this order, is that we are
thinking of the situation as: First we have a model M of PA, then we
look for an elementary end extension M' that won't destroy the M
induction.

We call such an M' an inductive elementary extension of M. It follows
easily that M is a proper initial segment of M'.

THEOREM 1.1. Every consistent extension of PA has models of every
infinite cardinality with an inductive elementary extension. Every
consistent extension of PA has models of every infinite cardinality
with no inductive elementary extension.

Let's move toward the issue of the robustness of inductive elementary
extensions. Here is a negative result.

THEOREM 1.2.  Every consistent extension of PA has a model M of any
infinite cardinality with two elementary inequivalent inductive
elementary extensions (M,M'), (M,M'').

We can go further and ask for a countable model M of PA such that all
of its inductive elementary extensions (M,M') are elementary
equivalent. We will leave this question for the reader.

Now let's go in the positive direction.

Let N be the standard model of PA. We have the obvious inductive
elementary extensions (N,N'), where N' is an ultra power of N using
any ultrafilter on N.

THEOREM 1.3. Any two (N,N') via a non principal ultrafilter on N are
elementarily equivalent.

Proof: I offer the proof because this is an area of classical model
theory I never worked in much, and may not be fully competent here. If
the continuum hypothesis holds then these N' and N'' are isomorphic
because of omega_1 saturation and elementary equivalence. Hence these
(N,N') and (N,N'') are isomorphic as required. So we can assume that
the continuum hypothesis fails, and assume we have (N,N') and (N,N'')
given by two non principal ultrafilters on N. Now we can force the CH
to hold by a generic extension using countable conditions, that does
not add any reals. In the generic extension, we still have that N',N''
are omega_1 saturated and elementary equivalent. Hence in the generic
extension, N' and N'' are isomorphic, and hence in the generic
extension (N,N') and (N,N'') are isomorphic. Hence in the generic
extension, (N,N') and (N,N'') are elementarily equivalent. Therefore
(n,N') and (N,N'') are elementarily equivalent in the universe, before
we did any forcing. QED

Assuming this is correct, we do have a preferred set of sentences of
nonstandard arithmetic with the ordered ring structure and "being
standard".

Can we "axiomatize" it?

It is easy to see that any axiomatization of it includes an
axiomatization of all true sentences of second order arithmetic.

However, that is not entirely discouraging on two counts.

1. We might have a nice axiomatization or characterization of the true
sentences of (N,N') that does use truth in second order arithmetic as
a good black box.
2. We can also look for interesting restricted sets of sentences of
(N,N') where truth does not depend on anything like second order
arithmetic, where we have a good axiomatization, or even a decision
procedure.

In fact, under the 2 route above, we might find that for the
interesting restricted sentences, truth depends only on the fact that
(N,N') is an elementary inductive extension of N. Furthermore, we
might find that the characterization or axiomatization is valid for
any (M,M'). where M' is an inductive elementary extension of M.

2. INDUCTIVE ELEMENTARY RESTRICTIONS

Now let's turn the situation around, like Nelson did to A. Robinson.
Let M be a model of PA. What we have is M,M", where

i. M is a model of PA.
ii. M* is a proper elementary extension of M.
iii. M* satisfies induction for all first order properties of (M,M').

It follows easily that M* is a proper initial segment of M.

 Every consistent extension of PA has models of every infinite
cardinality with an inductive elementary extension. Every consistent
extension of PA has models of every infinite cardinality with no
inductive elementary extension.

THEOREM 2.1. Every consistent extension of PA has models of every
infinite cardinality with an inductive elementary restriction. Every
consistent extension of PA has models of every infinite cardinality
with no inductive elementary restriction.

Of course, once again, we have the preferred pairs (M,N), where M is
an ultra power of N via a non principal ultrafilter on N. The first
order theory of (M,N) is unique as for the (N,M) in section 1.

**********************************************************
My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 620th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-599 can be found at the FOM posting
http://www.cs.nyu.edu/pipermail/fom/2015-August/018887.html

600: Removing Deep Pathology 1  8/15/15  10:37PM
601: Finite Emulation Theory 1/perfect?  8/22/15  1:17AM
602: Removing Deep Pathology 2  8/23/15  6:35PM
603: Removing Deep Pathology 3  8/25/15  10:24AM
604: Finite Emulation Theory 2  8/26/15  2:54PM
605: Integer and Real Functions  8/27/15  1:50PM
606: Simple Theory of Types  8/29/15  6:30PM
607: Hindman's Theorem  8/30/15  3:58PM
608: Integer and Real Functions 2  9/1/15  6:40AM
609. Finite Continuation Theory 17  9/315  1:17PM
610: Function Continuation Theory 1  9/4/15  3:40PM
611: Function Emulation/Continuation Theory 2  9/8/15  12:58AM
612: Binary Operation Emulation and Continuation 1  9/7/15  4:35PM
613: Optimal Function Theory 1  9/13/15  11:30AM
614: Adventures in Formalization 1  9/14/15  1:43PM
615: Adventures in Formalization 2  9/14/15  1:44PM
616: Adventures in Formalization 3  9/14/15  1:45PM
617: Removing Connectives 1  9/115/15  7:47AM
618: Adventures in Formalization 4  9/15/15  3:07PM
619: Nonstandardism 1  9/17/15  9:57AM

Harvey Friedman