858: Mathematical Representations of Ordinals/1

Thu Jun 18 03:30:06 EDT 2020

There is an underdeveloped direction for obtaining a certain kind of
independence result from systems in weak fragments of second order
arithmetic.

Define natural countable classes of functions on integers, rationals,
or reals, with a natural ordering of the functions, which generally is
the same as eventual dominance. Prove that the ordering of the
functions is well ordered or well founded or well quasi ordered. Aim
for the ordinal of the ordering to be a large proof theoretic ordinal.
Then we have the Pi11 independent statement in various forms:

in every infinite sequence of functions one is <= a later one
In every infinite sequence of functions one is <= the next one
there is no infinite sequence of functions each greater than the next

NOW HERE is the main point. There is also the arithmetic independence results

in every infinite recursive sequence of functions one is <= a later one
In every infinite recursive sequence of functions one is <= the next one
there is no infinite recursive sequence of functions each greater than the next

which are Pi03, and the Pi02 independence results In fact, these are
generally equivalent to 2-consistency, which asserts that every
provable 2 quantifier sentence is true.

n every infinite primitive (elementary) recursive sequence of
functions one is <= a later one
In every infinite primitive (elementary) recursive sequence of
functions one is <= the next one
there is no infinite primitive (elementary) recursive sequence of
functions each greater than the next

These Pi02 statements have obviously associated growth rates, namely
given a code for the nice infinite sequence, how long do we have to
wait. These are generally equivalent to 1-consistency, or every
provable one quantifier sentence is true.

THE FUSABLE NUMBERS approach has several advantages over this
approach. But this approach still has some advantages of its own.
Namely, I think we can already see how to get rather significant proof
theoretic strength this way, way beyond PA. I think that major
additional progress can be readily achieved by the proof theory
community.

Let's discuss the most basic example of this at the level of epsilaon_0 and PA.

We use the set of terms TM(0,x,x^) inductively defined as follows. 0,x
iare terms. If s,t are terms so are x^s and (s+t).

These terms have a very natural normal form which is based on the
commutative and associative laws for addition. Since we are not using
multiplication, there are no distributive laws to think about. Once we
have these unique normal forms, we can sensibly define a strict linear
order on these normal terms (reduced terms).this induces a quasi
linear ordering on all terms.

We can show that this forms a very effective quasi well ordering of
the terms of order type epsilon_0.

We then have the independence results as indicated above - no
effective descending sequence through these terms.

This setting is very compelling from a purely combinatorial point of
view. But it would be nice to know that it has a complete semantic
interpretation. It seems we have various such complete
interpretations. E.g.,

1. Interpret the terms as functions from N into N (nonnegative
integers) in the obvious way. Here <= is eventual dominance and < is
eventual strict dominance.
2. Same on the nonnegative real numbers, i.e., functions from
[0,infinity) into [-,infinity).
3. Ordinals with + as natural addition.

We can also add multiplication with the analogous development. Only
here we run into Tarski's high school problem,
https://pdfs.semanticscholar.org/23e6/38803b829220457ead43361d1aab33785f51.pdf?_ga=2.3675571.24546448.1592453176-755416620.1570806532
and the fix given at the beginning.

The point here is that there are a plethora of quasi well ordered
structures to consider, of large order type, with corresponding
independence results by considering various forms of effective well
foundedness. Proof theoretically these stand on their own regardless
of what the complete interpretations look like, or whether they are
even complete.

there is also the Independence results emanating from my work on Term
Rewriting. This goes all the way up to theta sub capital omega to the
little omega at 0. See
https://cpb-us-w2.wpmucdn.com/u.osu.edu/dist/1/1952/files/2014/01/TermRew110701-1b7ikdn.pdf
This is from my Downloadable Lecture Notes page which is distinct from
my usual Downloadable Manuscripts page. See
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-lecture-notes-2/
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/

At this point it is not so clear how to push this mathematical term
approach with completeness or at least very natural mathematical
interpretations, to much bigger proof theoretic ordinals, although I
would think that this is forthcoming.

So let's just take a baby step. We have used 0,x,+, and x^. Let's just
add a constant c for epailson_0. Proceed as expected. This would be a
set of notations for epsilon_1.

Already even in this baby step, we do not have any obvious
interpretation except using ordinals, with natural sum. But can be
define natural interpretations living in the rationals?

Perhaps we want to view the FUSABLE number approach as part of a
general method for giving rational number interpretations of these
term systems we are talking about here.

#######################################

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 858th 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-799 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/

800: Beyond Perfectly Natural/6  4/3/18  8:37PM
801: Big Foundational Issues/1  4/4/18  12:15AM
802: Systematic f.o.m./1  4/4/18  1:06AM
803: Perfectly Natural/7  4/11/18  1:02AM
804: Beyond Perfectly Natural/8  4/12/18  11:23PM
805: Beyond Perfectly Natural/9  4/20/18  10:47PM
806: Beyond Perfectly Natural/10  4/22/18  9:06PM
807: Beyond Perfectly Natural/11  4/29/18  9:19PM
808: Big Foundational Issues/2  5/1/18  12:24AM
809: Goedel's Second Reworked/1  5/20/18  3:47PM
810: Goedel's Second Reworked/2  5/23/18  10:59AM
811: Big Foundational Issues/3  5/23/18  10:06PM
812: Goedel's Second Reworked/3  5/24/18  9:57AM
813: Beyond Perfectly Natural/12  05/29/18  6:22AM
814: Beyond Perfectly Natural/13  6/3/18  2:05PM
815: Beyond Perfectly Natural/14  6/5/18  9:41PM
816: Beyond Perfectly Natural/15  6/8/18  1:20AM
817: Beyond Perfectly Natural/16  Jun 13 01:08:40
818: Beyond Perfectly Natural/17  6/13/18  4:16PM
819: Sugared ZFC Formalization/1  6/13/18  6:42PM
820: Sugared ZFC Formalization/2  6/14/18  6:45PM
821: Beyond Perfectly Natural/18  6/17/18  1:11AM
822: Tangible Incompleteness/1  7/14/18  10:56PM
823: Tangible Incompleteness/2  7/17/18  10:54PM
824: Tangible Incompleteness/3  7/18/18  11:13PM
825: Tangible Incompleteness/4  7/20/18  12:37AM
826: Tangible Incompleteness/5  7/26/18  11:37PM
827: Tangible Incompleteness Restarted/1  9/23/19  11:19PM
828: Tangible Incompleteness Restarted/2  9/23/19  11:19PM
829: Tangible Incompleteness Restarted/3  9/23/19  11:20PM
830: Tangible Incompleteness Restarted/4  9/26/19  1:17 PM
831: Tangible Incompleteness Restarted/5  9/29/19  2:54AM
832: Tangible Incompleteness Restarted/6  10/2/19  1:15PM
833: Tangible Incompleteness Restarted/7  10/5/19  2:34PM
834: Tangible Incompleteness Restarted/8  10/10/19  5:02PM
835: Tangible Incompleteness Restarted/9  10/13/19  4:50AM
836: Tangible Incompleteness Restarted/10  10/14/19  12:34PM
837: Tangible Incompleteness Restarted/11 10/18/20  02:58AM
838: New Tangible Incompleteness/1 1/11/20 1:04PM
839: New Tangible Incompleteness/2 1/13/20 1:10 PM
840: New Tangible Incompleteness/3 1/14/20 4:50PM
841: New Tangible Incompleteness/4 1/15/20 1:58PM
842: Gromov's "most powerful language" and set theory  2/8/20  2:53AM
843: Brand New Tangible Incompleteness/1 3/22/20 10:50PM
844: Brand New Tangible Incompleteness/2 3/24/20  12:37AM
845: Brand New Tangible Incompleteness/3 3/28/20 7:25AM
846: Brand New Tangible Incompleteness/4 4/1/20 12:32 AM
847: Brand New Tangible Incompleteness/5 4/9/20 1 34AM
848. Set Equation Theory/1 4/15 11:45PM
849. Set Equation Theory/2 4/16/20 4:50PM
850: Set Equation Theory/3 4/26/20 12:06AM
851: Product Inequality Theory/1 4/29/20 12:08AM
852: Order Theoretic Maximality/1 4/30/20 7:17PM
853: Embedded Maximality (revisited)/1 5/3/20 10:19PM
854: Lower R Invariant Maximal Sets/1:  5/14/20 11:32PM
855: Lower Equivalent and Stable Maximal Sets/1  5/17/20 4:25PM
856: Finite Increasing reducers/1 6/18/20 4 17PM :
857: Finite Increasing reducers/2 6/16/20 6:30PM

Harvey Friedman