[FOM] 604: Finite Emulation Theory 2

[Harvey Friedman]

THIS POSTING IS SELF CONTAINED

First, a typo in http://www.cs.nyu.edu/pipermail/fom/2015-August/018917.html

I wrote:

Can T be written as a union of elements of K?

This should be

Can T be written as a union of pairwise disjoint elements of K?

Also, in one place I wrote Hindman's theorem, and in another place I
wrote Heinemann's theorem. The former is what I intended, the latter
referring to a British publishing house that I had never heard of.

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

DEFINITION 1. Z+ is the set of all positive integers. [n] = {1,...,n}.
We use k,n,m,r,s,t for positive integers. We use A,B,C,D,E for finite
sets of positive integers. We use X,Y,U,V,W for finite sets of tuples
of positive integers of a common length. A! = {n!: n in A}. For x in
Z+^k, A,B,C,D are rising below n if and only if their max's below n
are strictly increasing (empty max is 0).

DEFINITION 2. Let x,y in Z+^k and X,Y containedin Z+^k. x,y are order
equivalent if and only if for all 1 <= i,j <= k, x_i < x_j iff y_i <
y_j. Y is an emulation of X if and only iff for all x,y in Y there
exists z,w in X such that (x,y) and (z,w) are order equivalent
elements of Z+^2k.

DEFINITION 3. Let Y be an emulation of X. Y covers A by B if and only
if for all x in A^k\Y there exists y from B^k, max(y) < max(x), such
that {x,y} does
not emulate X.

THEOREM 1. Every X has an emulation covering [n]! by [n]!. It's
intersection with [n]! is unique. Here [n]! can be replaced by any finite A.

PROPOSITION 2. Every k dimensional X has an emulation covering [n]! by
some A by some B by [n!], the four rising below (8k)!!.

THEOREM 3. Proposition 2 is provably equivalent to Con(SMAH) over ACA.

SMAH = strongly Mahlo cardinals of finite order. ACA = arithmetic
comprehension with full induction.

Note that Proposition 2 is explicitly Pi01 since only integers <=
max(n!,(8k)!!) are relevant.

COMMENTS. Without the rising condition, it is provable. With the
rising condition but without B, it is provable. The rising condition
is very visual. We can additionally demand that the four sets form a
chain under inclusion. In any case, the rising condition is a very
basic vivid kind of feature of a series of sets of positive integers.
We can allow any such length r chain with the same first and last
terms (use (8kr)!!). If we weaken the statement so that n is a
function of k, then
we get various levels below SMAH. Iterated powers of 2 with k on top
yields statements corresponding to the simple impredicative theory of
types, or forms of Zermelo set theory. I should be able to hit ZFC on
the button here by using the Ackermann hierarchy.

************************************************************
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 604th 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

Harvey Friedman