868: Structural Mapping Theory/6

Mon Feb 15 21:45:39 EST 2021

SMAT (structural mapping theory) continues to clarify and evolve. The
starting point that generates the excitement is
[1]  https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
 #113
especially section 3.

1. Special Role of Set Theoretic Foundations - Ultimate Foundations
https://cs.nyu.edu/pipermail/fom/2021-February/022480.html
2. Many sorted structures.
https://cs.nyu.edu/pipermail/fom/2021-February/022480.html
3. Categories as many sorted structures -
https://cs.nyu.edu/pipermail/fom/2021-February/022483.html
4. Semigroups of Functions -
https://cs.nyu.edu/pipermail/fom/2021-February/022483.html
https://cs.nyu.edu/pipermail/fom/2021-February/022488.html
5. Function Systems - here
6. Categories of sets - next posting

5. FUNCTION SYSTEMS

A function system is a (D,K_1,K_2,...),where D is a set (or class),
and for each n >= 1, K_n is a set (or family) of functions of
functions f:D^n into D. This is naturally viewed as a many sorted
structure with sorts D, K_1, K_2,..., with application functions
A_1:K_1 x D into D, A_2:K_2 x D x D into D, ... . You are allowed to
use only some of these sorts and duplicate sorts with the same
arities.

NOTE: I have allowed infinitely many sorts. That is something I said I
wasn't going to allow in section 2. I may live to regret having said
that.

We look at mappings j of function systems into themselves. These are j
= j_0,j_1,j_2,..., where j_0:D into D and each j_n:K_n into K_n.
Nonsurectivity simply means that the range of j_0 is a proper subset
of D.

The simplest enormous supply of function systems is of course just
given by sentences phi_1(F_1), phi_2(F_2), ..., where the F_i are
i-ary function symbols interpreted over D, where we take K_n = {F_n:
phi_n(F_n)}. Of course, typically we may just use only K_1 or only
K_2. Of course maybe more, typically K_1 and K_2 and maybe only those.

Once again we can restrict considerably the kind of sentences phi_n
that we use. For example, finite set of equations only.

We ask for equation preserving, and solvable equation preserving, and
so forth. Here the equations are the s = t where s,t are terms
denoting elements of D, with variables over the sorts. For solvable
equation preserving, parameters are allowed for any sorts, and
solvability means existence of values for the variables of any sorts.

No matter what phi's are used, from I2 we get the existence of some D
such that there is a non surjective solvable equation preserving
mapping. The question is: what can we say about the strength of this
statement as phi's vary?

For the case of taking each K_n to be the set of all f:D^n into D, and
even with only K_1, we get the same results as in our [1], and also
the class theoretic versions discussed in section 4. Namely, the
existence of D such that there is a non surjective solvable equation
preserving mapping is equivalent to I2.

Similar for elementary embeddings and I1. And under the Berkeley Axiom
(wildly inconsistent under AxC) , we have such elementary embeddings
for all sufficiently large D.

What can we say about the phi so that for all sufficiently large D or
maybe even all infinite D, we have a non surjective solvable equation
preserving or even elementary embedding mapping simply provable in ZF
or ZFC?

We can ask for the recursion theoretic complexity of the set of all
phi's for which these various things take place, both set theoretic
and metamathematical. We can ask about actual cardinals that arise
here for the various phi's. And so forth. We may want to focus on phi
being a finite set of equations, or even maybe a single equation.

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

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 868th 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
858: Mathematical Representations of Ordinals/1 6/18/20 3:30AM
859. Incompleteness by Effectivization/1  6/19/20 1132PM :
860: Unary Regressive Growth/1  8/120  9:50PM
861: Simplified Axioms for Class Theory  9/16/20  9:17PM
862: Symmetric Semigroups  2/2/21  9:11 PM
863: Structural Mapping Theory/1  2/4/21  11:36PM
864: Structural Mapping Theory/2  2/7/21  1:07AM
865: Structural Mapping Theory/3  2/10/21  11:57PM
866: Structural Mapping Theory/4  2/13/21  12:47AM
867: Structural Mapping Theory/5  2/14/21  11:27PM

Harvey Friedman