857: Finite Increasing Reducers/2

Tue Jun 16 18:30:09 EDT 2020

The second part of posting 856: Finite Increasing Reducers/1 was in
the right spirit but wasn't general enough even to include the fusable
numbers as a special case. This posting will fix this.

THEOREM A. (well known in certain circles) Let K be a finite set of
partial functions from various Q^k into Q each of which are increasing
and dominating. I.e., if x <= y coordinatewise and are in the domain,
then the value at x is at most the value at y, and the value at x is
at least max(x). Then the numbers generated by K and any finite set of
numbers to start, is a well ordered set of rationals. Furthermore, the
ordinals that you can get in this way is the set of proper initial
segments of the Kruskal ordinal, theta sub capital omega to the little
omega at 0.

Now let's look at the fusables, which are generate by 0 and the single
function F::Q^2 into Q,  (x+y+1)/2 provided |x-y| < 1. Here ::
indicates partial function. It is clear that the fusables are
nonnegative rationals, and so they are generated by the single
function F'::Q^2 into Q, (x+y+1)/2 provided |x-y| <1 and x,y >= 0.

LEMMA. This fusible generating function F'::Q^2 into Q is increasing
and dominating. In fact, strictly increasing and strictly dominating.

Proof: Suppose |x-y| < 1 and x,y >= 0. Then (x+y+1)/2 > x because
x+y+1 > 2x because y+1 > x because 1 > x-y. And (x+y+1)/2 > y by
symmetry. Also the strictly increasing part is obvious by looking at
(x+y+1)/2. QED

LEMMA. Suppose x1,...,xk are nonnegative and of distance < 1/(k-1)
from each other, Then (x1 + ... + xk + 1)/k > x1.

Proof: Need x1 + ... + xk + 1 > k x1. I.e., x1 + ... + xk + 1 > x1 +
x1 + ... + x1. Comparing x2 + ... + xk and x1 +... + x1, we can only
be raising by less than (k-1) times (1/(k-10) = 1. QED

So we can define k-fusable numbers as the least set of numbers
containing 0, where if x1,...,xk are k-fusable and of distance less
than 1/k-1 from each other, then (x1 + ... + xk + 1)/k is k-fusable.

THEOREM B. The set of k-fusable numbers is a well ordered set of
nonnegative rationals.

CONJECTURE. Theorem B is equivalent to "theta sub capital omega to the
little omega at 0", is well ordered.

CONJECTURE. One can read off a nice Pi02 sentence and a nice algorithm
associated with the set of k-fusable numbers that are
equivalent to my finite form of Kruskal's theorem.

Harvey Friedman

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

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

Harvey Friedman