[FOM] 732: Large Cardinals and Emulations/27

Mon Nov 28 01:31:25 EST 2016

We continue with this outline from
http://www.cs.nyu.edu/pipermail/fom/2016-November/020170.html

EMULATION THEORY
OUTLINE

1. INTRODUCTION.
2. INFINITE EMULATION.
   2.1.  MAXIMAL EMULATION IN Q[0,1]^k.
http://www.cs.nyu.edu/pipermail/fom/2016-October/020107.html
      2.1.1. TRANSLATION.
http://www.cs.nyu.edu/pipermail/fom/2016-October/020107.html
      2.1.2. EMBEDDING.
http://www.cs.nyu.edu/pipermail/fom/2016-October/020137.html
   2.2. STEP MAXIMAL EMULATION IN Q^k.
http://www.cs.nyu.edu/pipermail/fom/2016-November/020170.html
3. EMULATION TOWERS OF FINITE SETS.
http://www.cs.nyu.edu/pipermail/fom/2016-November/020170.html
4. GREEDY EMULATION OF LINEARLY ORDERED DIGRAPHS.
   4.1. GREEDY EMULATION.
   4.2. UP GREEDY EMULATION.
here
5. GREEDY EMULATION TOWERS OF SETS OF NONNEGATIVE INTEGERS.
   5.1. INFINITE SETS.
   5.2. FINITE SETS.
6. GREEDY EMULATION TOWERS OF LINEARLY ORDERED DIGRAPHS.
   6.1. OMEGA-GRAPHS.
   6.2. FLODIGS - COUNTS.
   6.3. EMBEDDING.

NOTE: HUGE and beyond is achieved in 4.2, where we give extremely strong
implicitly Pi01. HUGE and beyond is achieved in 6.3 with explicitly
Pi01, but the present form of  6.3 does not meet
current standards. There is hope for simplification.

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

4. GREEDY EMULATION OF LINEARLY ORDERED DIGRAPHS.

We now use linearly ordered digraphs and a more incremental kind of
maximality for emulations than ordinary maximality in section 2 and
step maximality in section 3. These are called greedy r-emulations in
section 4.1, and the up greedy r-emlations in section 4.2. The the
statements call for an embedding of the greedy r-emulation of up
greedy r-emulation with certain properties.

4.1. GREEDY EMULATION.

DEFINITION 4.1.1. A digraph is a G = (V,E), where V = V(G) is the set
of vertices, and E = E(G) containedin V^2 is the set of edges. x,y are
adjacent in G if and only if (x,y) in E or (y,x) in E. A linearly
ordered graph is a G = (V,<,E), where (V,E) is a digraph and < is a
strict linear ordering on V. A clog (flog) G is a linearly ordered
graph with countably (finitely) many vertices.

DEFINITION 4.1.2. An isomorphism between clogs is a bijection between
their vertex sets which preserves the linear order and the edges. A
subclog of a clog (V,<,E) is a clog (V',<',E') where V',<',E' are
subsets of V,<,E, respectively. G' is an r-emulation of G if and only
if G' is a clog with the same <=r vertex subclogs up to isomorphism.

DEFINITION 4.1.3. G' is a greedy r-emulation of G if and only if G' is
an r-emulation of G with no r-emulation of G of the form
(V(G'),<,E(G')|<max(v,w) U. {(v,w)}). An embedding of G is a an h:V(G)
into V(G) such that v < w iff hv < hw and (v,w) in E(G) iff (hv,hw) in
E(G). A critical embedding is an embedding where there is a least v =
c(h) such that hv not= v. h is trivial if and only if h is not the
identity on V(G).

GEE/1. Every clog has a greedy r-emulation with a critical embedding.

THEOREM 4.1.1. GEE/1 is provably equivalent to Con(SRP) over WKL_0.

Note that the statement is obviously equivalent if we replace clog
with flog. It is then clear that GEE/1 is implicitly Pi01 via the
Goedel Completeness Theorem.

4.2. UP GREEDY EMULATION.

DEFINITION 4.2.1.  Let G,G' be clogs. G' is an up greedy r-emulation
of G if and only if G' is an r-emulation of G with no r-emulation of G
of the form (V(G'),<,E(G')|<max(v,w) U. {(v,w)}), v < w.

UGEE/1. Every clog has an up greedy r-emulation with a critical embedding.

UGEE/2. Every clog has an up greedy r-emulation with a nontrivial
embedding mapping each V|<v onto some E_w|<u.

THEOREM 4.2.1. UGEE/1 is provably equivalent to Con(SRP) over WKL_0.
UGEE/2 is provably equivalent to Con(HUGE) over WKL_0.

Note that the statement is obviously equivalent if we replace clog
with flog. It is then clear that UGEE/1, UGEE/2 are implicitly Pi01
via the Goedel Completeness Theorem.

************************************************************************
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 732nd 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-699 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/

700: Large Cardinals and Continuations/14  8/1/16  11:01AM
701: Extending Functions/1  8/10/16  10:02AM
702: Large Cardinals and Continuations/15  8/22/16  9:22PM
703: Large Cardinals and Continuations/16  8/26/16  12:03AM
704: Large Cardinals and Continuations/17  8/31/16  12:55AM
705: Large Cardinals and Continuations/18  8/31/16  11:47PM
706: Second Incompleteness/1  7/5/16  2:03AM
707: Second Incompleteness/2  9/8/16  3:37PM
708: Second Incompleteness/3  9/11/16  10:33PM
709: Large Cardinals and Continuations/19  9/13/16 4:17AM
710: Large Cardinals and Continuations/20  9/14/16  1:27AM
700: Large Cardinals and Continuations/14  8/1/16  11:01AM
701: Extending Functions/1  8/10/16  10:02AM
702: Large Cardinals and Continuations/15  8/22/16  9:22PM
703: Large Cardinals and Continuations/16  8/26/16  12:03AM
704: Large Cardinals and Continuations/17  8/31/16  12:55AM
705: Large Cardinals and Continuations/18  8/31/16  11:47PM
706: Second Incompleteness/1  7/5/16  2:03AM
707: Second Incompleteness/2  9/8/16  3:37PM
708: Second Incompleteness/3  9/11/16  10:33PM
709: Large Cardinals and Continuations/19  9/13/16 4:17AM
710: Large Cardinals and Continuations/20  9/14/16  1:27AM
711: Large Cardinals and Continuations/21  9/18/16 10:42AM
712: PA Incompleteness/1  9/2316  1:20AM
713: Foundations of Geometry/1  9/24/16  2:09PM
714: Foundations of Geometry/2  9/25/16  10:26PM
715: Foundations of Geometry/3  9/27/16  1:08AM
716: Foundations of Geometry/4  9/27/16  10:25PM
717: Foundations of Geometry/5  9/30/16  12:16AM
718: Foundations of Geometry/6  101/16  12:19PM
719: Large Cardinals and Emulations/22
720: Foundations of Geometry/7  10/2/16  1:59PM
721: Large Cardinals and Emulations//23  10/4/16  2:35AM
722: Large Cardinals and Emulations/24  10/616  1:59AM
723: Philosophical Geometry/8  10/816  1:47AM
724: Philosophical Geometry/9  10/10/16  9:36AM
725: Philosophical Geometry/10  10/14/16  10:16PM
726: Philosophical Geometry/11  Oct 17 16:04:26 EDT 2016
727: Large Cardinals and Emulations/25  10/20/16  1:37PM
728: Philosophical Geometry/12  10/24/16  3:35PM
729: Consistency of Mathematics/1  10/25/16  1:25PM
730: Consistency of Mathematics/2  11/17/16  9:50PM
731: Large Cardinals and Emulations/26  11/21/16  5:40PM

Harvey Friedman