[FOM] 204:Finite Extrapolation

[Harvey Friedman]

Suppose we are told that a certain infinite set of positive integers begins
with 

1,2,3.

We are asked to make our best guess as to what it is. We naturally guess the
set of all positive integers. This appears to be the simplest extrapolation.

Suppose we are given the initial segment

2,4,6.

We guess the set of all even positive integers.

Suppose we are given the initial segment

1,4,9.

We guess the set of all positive squares.

It is perhaps somewhat less clear what we should answer in these three
cases: 

1.
2.
1,4.

Also we all see what to do with

2,5,8,11.

We also want to extrapolate *sequences* such as

1,2,1,2.

which we identify with the set of ordered pairs

{(1,1),(2,2),(3,1),(3,2)}.

In any case, we want a reasonable model which we can work with, and PROVE
correct answers to such extrapolation questions.

ABSTRACT PICTURE.

The general picture is as follows. We have a language L for defining (by
formulas) subsets of Z+, and also more generally, for describing relations
on Z+ of several variables  (i.e., sets of tuples of fixed length).

We put a complexity measure on L, which is a mapping from formulas into
positive integers. 

Let E be a finite set of positive integers. We look for the formula of least
complexity, with at most one free variable, which defines an infinite set of
positive integers with E as an initial segment. We then define the

simplest extrapolation of E

to be the set of all positive integers defined by that formula. If there is
more than one such formula, then there may be more than one simplest
extrapolation of E. So most generally, we seek the simplest extrapolations
of E.

We also adapt this to finite sequences of positive integers as follows. Let
a1,...,ak be a finite sequence of positive integers, k >= 1. Let phi be the
formula of least complexity, with at most two free variables, which defines
an infinite sequence of positive integers (as a binary relation) which
extends a1,...,ak. The simplest extrapolation of a1,...,ak is taken to be
the infinite sequence defined by this formula. Again, there may be more than
one simplest extrapolation.

There is a major variant that should be considered at some point. That is,
we do not require that the formula define an infinite set, or an infinite
sequence. Note that if the finite set or sequence that is to be extrapolated
is a bit complex, then probably the phi of least complexity will in fact
define an infinite set of infinite sequence; so this variant will not differ
from the official way we are doing things.

This picture can be extended to relations (finite sets of tuples), and
sequences of tuples, in straightforward ways. In the case of relations, we
need to state what we mean by "an initial segment". We can take this to mean
the set of all tuples in the relation whose maximum term is at most a given
positive integer. Or we can take initial segment to mean initial segment
under the lexicographic ordering, or some other favorite ordering.

ARBITRARY RELATIONAL STRUCTURES.

Continuing the abstract discussion, let us be given a relational structure
in a finite relational type, M = (D,...), where D is a nonempty set
containing the positive integers.

We will put the following complexity measure on all first order formulas in
the type of M. We will use

1. variables.
2. connectives not, and, or, if then, iff.
3. quantifiers forall x, therexists x, where x is a variable.
4. equality =.
4. constant, relation, and function symbols interpreted by M.

The complexity of a formula is obtained by counting the total number of
occurrences of variables, connectives, quantifiers, constants, relation
symbols, function symbols.

If we see (forall x), then this contributes 2 to the count. 1 for the
quantifier "forall", and 1 for the variable "x".

A PARTICULAR CASE.

An important particular case is that of the ordered ring of integers,
(Z,<,+,-,dot), where we have both unary and binary -.

For our purposes, it is more natural to beef up this structure in a
convenient way. Thus the official structure we want to focus on is

(Z,0,1,<,>,<=,>=,=,not=,+,unary -,binary -,dot,| |)

where | | is absolute value.

One can easily worry about why this particular complexity measure.
Responses:

a. We need to start with a reasonable one, in order to get this new subject
going.

b. There is robustness, in that other reasonable complexity measures should
give the same or similar results. But this requires careful investigation.
And hence a above. 

A PROPOSAL.

Determine, in the above official structure, what the simplest extrapolations
are, by infinite sets, of the following finite initial segments (in the
sense discussed earlier in this posting):

2,4.
1,3.
1,4.
1,4,9.
5,8,11.

Also, simplest extrapolations to infinite sequences, of these initial
segments (in the sense discussed earlier in this posting):

1,3,2.
1,3,2,4.
1,2,1,2.
1,2,3,1.
1,2,3,1,2,3.
5,8,11.

A BIGGER PICTURE.

Quite a number of my proposals and some of my recent published (or to
appear) research involves SIMPLICITY research. This is, in my opinion,
likely to become a principal paradigm for foundational research (in due
time). It demands a substantial rethinking of everything... Of course, I
recognize a certain kind of "dirtying of hands" needed to do significance
work along these lines. But I am convinced that it is well worth the effort.

*********************************************

I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 204th 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-149 can be found at
http://www.cs.nyu.edu/pipermail/fom/2003-May/006563.html  in the FOM
archives, 5/8/03 8:46AM. Previous ones counting from #150 are:

150:Finite obstruction/statistics  8:55AM  6/1/02
151:Finite forms by bounding  4:35AM  6/5/02
152:sin  10:35PM  6/8/02
153:Large cardinals as general algebra  1:21PM  6/17/02
154:Orderings on theories  5:28AM  6/25/02
155:A way out  8/13/02  6:56PM
156:Societies  8/13/02  6:56PM
157:Finite Societies  8/13/02  6:56PM
158:Sentential Reflection  3/31/03  12:17AM
159.Elemental Sentential Reflection  3/31/03  12:17AM
160.Similar Subclasses  3/31/03  12:17AM
161:Restrictions and Extensions  3/31/03  12:18AM
162:Two Quantifier Blocks  3/31/03  12:28PM
163:Ouch!  4/20/03  3:08AM
164:Foundations with (almost) no axioms, 4/22/0  5:31PM
165:Incompleteness Reformulated  4/29/03  1:42PM
166:Clean Godel Incompleteness  5/6/03  11:06AM
167:Incompleteness Reformulated/More  5/6/03  11:57AM
168:Incompleteness Reformulated/Again 5/8/03  12:30PM
169:New PA Independence  5:11PM  8:35PM
170:New Borel Independence  5/18/03  11:53PM
171:Coordinate Free Borel Statements  5/22/03  2:27PM
172:Ordered Fields/Countable DST/PD/Large Cardinals  5/34/03  1:55AM
173:Borel/DST/PD  5/25/03  2:11AM
174:Directly Honest Second Incompleteness  6/3/03  1:39PM
175:Maximal Principle/Hilbert's Program  6/8/03  11:59PM
176:Count Arithmetic  6/10/03  8:54AM
177:Strict Reverse Mathematics 1  6/10/03  8:27PM
178:Diophantine Shift Sequences  6/14/03  6:34PM
179:Polynomial Shift Sequences/Correction  6/15/03  2:24PM
180:Provable Functions of PA  6/16/03  12:42AM
181:Strict Reverse Mathematics 2:06/19/03  2:06AM
182:Ideas in Proof Checking 1  6/21/03 10:50PM
183:Ideas in Proof Checking 2  6/22/03  5:48PM
184:Ideas in Proof Checking 3  6/23/03  5:58PM
185:Ideas in Proof Checking 4  6/25/03  3:25AM
186:Grand Unification 1  7/2/03  10:39AM
187:Grand Unification 2 - saving human lives 7/2/03 10:39AM
188:Applications of Hilbert's 10-th 7/6/03  4:43AM
189:Some Model theoretic Pi-0-1 statements  9/25/03  11:04AM
190:Diagrammatic BRT 10/6/03  8:36PM
191:Boolean Roots 10/7/03  11:03 AM
192:Order Invariant Statement 10/27/03 10:05AM
193:Piecewise Linear Statement  11/2/03  4:42PM
194:PL Statement/clarification  11/2/03  8:10PM
195:The axiom of choice  11/3/03  1:11PM
196:Quantifier complexity in set theory  11/6/03  3:18AM
197:PL and primes 11/12/03  7:46AM
198:Strong Thematic Propositions 12/18/03 10:54AM
199:Radical Polynomial Behavior Theorems
200:Advances in Sentential Reflection 12/22/03 11:17PM
201:Algebraic Treatment of First Order Notions 1/11/04 11:26PM
202:Proof(?) of Church's Thesis 1/12/04 2:41PM
203:Proof(?) of Church's Thesis - Restatement 1/13/04 12:23AM