[FOM] 647: General Incompleteness almost everywhere 1

[Harvey Friedman]

We offer a particularly natural setting for a fairly well known
General Incompleteness Phenomena. This is quite different from
Concrete Mathematical Incompleteness which involves very special
properties of fragments and extensions of ZFC, and specific single
independent statements.

What I particularly like about this is that it appears to be amenable
to some interesting finite estimates. I won't try to give any
estimates in this posting, but plan to give some estimates later.

An algebra consists of a nonempty domain D together with a finite list
of constants from D and functions of several variables from D into D.

An algebra is nontrivial if and only if its domain D has at least two elements.

A description of a nontrivial algebra A is a finite set of equations T
(with constants and variables), where A is the unique nontrivial
algebra satisfying T, up to isomorphism.

A k-algebra is a nontrivial algebra with a description that uses at
most k total occurrences of constants, functions, and variables.

Note that there are finitely many k-algebras up to isomorphism.

THEOREM 1. Let n >> k >> 1. "There is a k-algebra of cardinality n" is
independent of ZFC.

THEOREM 2. Let T be a consistent recursively axiomatized extension of
EFA. Let n >> k >> 1. "There is a k-algebra of cardinality n" is
independent of T.

There is a variant of the above for which we obtain the same results.

A description' of a nontrivial algebra A is a finite set of equations
T (with constants and variables), where A is the unique nontrivial
finite algebra satisfying T, up to isomorphism.

A k'-algebra is a nontrivial algebra with a description' that uses at
most k total occurrences of constants, functions, and variables.

THEOREM 3. Let n >> k >> 1. "There is a k'-algebra of cardinality n"
is independent of ZFC.

THEOREM 4. Let T be a consistent recursively axiomatized extension of
EFA. Let n >> k >> 1. "There is a k'-algebra of cardinality n" is
independent of T.

In Theorems 1,3, we believe that k can be taken to be very reasonable
not only for ZFC, but for any consistent extension of ZFC by standard
large cardinal axioms. We have not gone into this in detail, but here
is the kind of target statement we are looking for.

TARGET 1. Let n >> 1. "There is a 100-algebra of cardinality n" is
independent of ZFC. We can use any consistent extension of ZFC by
standard large cardinal axioms. We can also use 100'-algebras. Also
for 100'-algebras.

TARGET 2. Let n <= 100!. The probability that "there is a 100-algebra
of cardinality n" is decided in ZFC is < 10^-20. We can use any
consistent extension of ZFC by standard large cardinal axioms. We can
also use 100'-algebras. Also for 100'-algebras.

The above is aimed at showing that in some sense we have
Incompleteness "almost everywhere". But we can also focus attention on
particularly simple "Incompleteness Constants".

Let c be the least integer such that there is a set of equations T in
constants and variables and functions of several variables, with at
most 100 total occurrences of constants, variables, and functions,
such that "there is a nontrivial (finite) algebra satisfying T" is
independent of ZFC.

What upper and lower bounds can we give for c?

**********************************************************
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 647th 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
604: Finite Emulation Theory 2  8/26/15  2:54PM
605: Integer and Real Functions  8/27/15  1:50PM
606: Simple Theory of Types  8/29/15  6:30PM
607: Hindman's Theorem  8/30/15  3:58PM
608: Integer and Real Functions 2  9/1/15  6:40AM
609. Finite Continuation Theory 17  9/315  1:17PM
610: Function Continuation Theory 1  9/4/15  3:40PM
611: Function Emulation/Continuation Theory 2  9/8/15  12:58AM
612: Binary Operation Emulation and Continuation 1  9/7/15  4:35PM
613: Optimal Function Theory 1  9/13/15  11:30AM
614: Adventures in Formalization 1  9/14/15  1:43PM
615: Adventures in Formalization 2  9/14/15  1:44PM
616: Adventures in Formalization 3  9/14/15  1:45PM
617: Removing Connectives 1  9/115/15  7:47AM
618: Adventures in Formalization 4  9/15/15  3:07PM
619: Nonstandardism 1  9/17/15  9:57AM
620: Nonstandardism 2  9/18/15  2:12AM
621: Adventures in Formalization  5  9/18/15  12:54PM
622: Adventures in Formalization 6  9/29/15  3:33AM
623: Optimal Function Theory 2  9/22/15  12:02AM
624: Optimal Function Theory 3  9/22/15  11:18AM
625: Optimal Function Theory 4  9/23/15  10:16PM
626: Optimal Function Theory 5  9/2515  10:26PM
627: Optimal Function Theory 6  9/29/15  2:21AM
628: Optimal Function Theory 7  10/2/15  6:23PM
629: Boolean Algebra/Simplicity  10/3/15  9:41AM
630: Optimal Function Theory 8  10/3/15  6PM
631: Order Theoretic Optimization 1  10/1215  12:16AM
632: Rigorous Formalization of Mathematics 1  10/13/15  8:12PM
633: Constrained Function Theory 1  10/18/15 1AM
634: Fixed Point Minimization 1  10/20/15  11:47PM
635: Fixed Point Minimization 2  10/21/15  11:52PM
636: Fixed Point Minimization 3  10/22/15  5:49PM
637: Progress in Pi01 Incompleteness 1  10/25/15  8:45PM
638: Rigorous Formalization of Mathematics 2  10/25/15 10:47PM
639: Progress in Pi01 Incompleteness 2  10/27/15  10:38PM
640: Progress in Pi01 Incompleteness 3  10/30/15  2:30PM
641: Progress in Pi01 Incompleteness 4  10/31/15  8:12PM
642: Rigorous Formalization of Mathematics 3
643: Constrained Subsets of N, #1  11/3/15  11:57PM
644: Fixed Point Selectors 1  11/16/15  8:38AM
645: Fixed Point Minimizers #1  11/22/15  7:46PM
646: Philosophy of Incompleteness 1  Nov 24 17:19:46 EST 2015

Harvey Friedman