[FOM] 701: Extending Functions/1

[Harvey Friedman]

Here is the link to my recent talk on Extending Functions.

66. Extending Functions, August 8, 2016, 13 pages. August 5, 2016 talk
at the workshop Model Theory: From fields to Hardy Fields, held at the
Fields Institute in Toronto in honor of Lou van den Dries 65th
birthday. http://u.osu.edu/friedman.8/foundational-adventures/downloadable-lecture-notes-2/

Many aspects of extending functions are discussed there, in varying
levels of detail. There are a number of questions that arise in moving
to create some sort of unified subject EXTENDING FUNCTIONS.

As is indicated in 66 above, I am trying to link up Extending
Functions with Continuation Theory. In Continuation Theory, so far I
am only continuing finite sets to finite sets and countable sets. It
looks like there is considerable promise in continuing finite
functions to finite functions and countable functions. But I won't go
deeper into this in this posting.

Here I want to take up just one aspect in this posting. Given infinite
f:A^k into A, find an elementary extension g:AB^k into B.

How nicely can be construct g from f?  The well known constructions of
g from f do not explicitly define g from f even if we allow arbitrary
explicit mathematical definitions. However, in

[KS1] V. Kanovei and S. Shelah. A definable nonstandard model of the
reals. Journal of Symbolic Logic, 69(1):159–164, 2004.

[KS2] V. Kanovei, Michael Reeken, S. Shelah, Fully saturated
extensions of standard universe, http://shelah.logic.at/files/E39.ps

my understanding is that we find that there is a 0-definable map H
from V into V such that for all infinite f:A^k into A, H(f) is a
proper elementary extension of f.

There are some limitations of just how "good" H can be, even for very
natural f.

But before getting to this, let us go back to basics.

*RECURSIVE f:N^k into N*

Here N is the set of all nonnegative integers, Z is the set of all integers.

THEOREM 1. Every recursive f:N^k into N has an elementary extension
g:Z^k into Z which is recursive in the (omega+1)-st Turing jump. Every
elementary extension g:Z^2 into Z of f:N^2 into N, f(n,m) = n^2 + m,
is of Turing degree at least the omega-th Turing jump.

Proof: Write down the usual complete diagram of f and a constant
symbol for a new element, and do the usual Henkin construction of a
model. This will establish the first claim. For the second claim, we
have to show that the elementary extensions g:Z^2 into Z are
essentially countable nonstandard models of the true sentences of
arithmetic. For this, we need to show that this f defines 0,+,x on N
without parameters.

0 is unique such that f(0,0) = 0. Hence 0 and n^2 are definable. Note
that n+m = r if and only if there exists a,b,c,d such that

i. a^2 + b^2 + c^2 + d^2 = n,
ii. a^2 + b^2 + c^2 + d^2 + m = r.

i. f(d,f(c,f(a,b^2))) = n.
ii. f(a,f(b,f(c,f(d,m)))) = r.

QED

QUESTION A. Can we reduce (omega+1)-th Turing jump to a degree
strictly between omega-th Turing jump and (omega+1)-st Turing jump? Is
this situation analogous with the Turing degrees of nonstandard models
of PA?

QUESTION B. Investigate this situation with elementary extension
replaced by elementary equivalence.

A favorite move of mine has been to consider weaker but very
mathematically naturally kinds of extensions using finite subsets.
I.e., "having the same finite subsets of isomorphism", and "having the
same finite subsets of isomorphism not moving any element of the model
being extended". From the math logic point of view, this is the same
as "universal elementary equivalence" and "universal elementary
extension".

QUESTiON C. Investigate this situation with universal elementary
equivalence and  universal elementary extension.

*(R,+,x,Z)*

Here R is the reals.

It is not at all obvious how to construct a proper elementary
extension of (R,+,x,Z) in OD. Nevertheless, this and much stronger
results come out of [KS1], [KS2] above.

However, there are some limitations on what can be done along these lines.

LEMMA 2. Let M be a proper elementary extension of (R,+,x,Z) and c > 0
be a new element. We can define a new integer from c and M. We can
define a non principal ultrafilter on N from c and M.

Proof: If c > R then take the floor of c in the sense of M. Otherwise,
let x be the largest real such that x <= c. Then take the floor of
1/(c-x in the sense of M.

Let d the new definable nonstandard integer. We can 0-define T
containedin R x N whose sections are all subsets of N. Let W be the
set of all subsets E of N such that for some real x, E = {n: T(x,n)},
and in M, T(x,d). Then W is a non principal ultrafilter on N. QED

THEOREM 3. ZFC does not prove the existence of an OD elementary
extension of (R,+,x,Z) with a new element that is OD.

Proof: We can define a non principal ultrafilter on N from the
elementary extension and any new c > 0 in Z. Let T(x,n) be (R,+,x,Z)
0-definable, where for all A containedin N there exists x such that
{n: T(x,n)} = A. Let W be the set of all A containedin N such that for
any A = {n: T(x,n)}, we have that in the elementary extension, T(x,c).
Then W is a non principal ultrafilter on N. QED

THEOREM 4. There is no proper elementary extension of (R,+,x,Z) which
is isomorphic to a projective structure.

Here projective is in the sense of the analytic hierarchy Pi-1-n, n >= 1.

TO BE CONTINUED.

***********************************************
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 701st 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
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/

700: Large Cardinals and Continuations/14

Harvey Friedman