FOM: 4:Simplicity

[Harvey Friedman]

This is the fourth in a series of positive self contained postings to fom
covering a wide range of topics in f.o.m. Previous ones are:

1:Foundational Completeness   11/3/97, 10:13AM, 10:26AM.
2:Axioms  11/6/97.
3:Simplicity  11/14/97 10:10AM.

Actually, this posting is more in the way of a brief followup to 3, and
also a followup to something from 2.

I noticed that the basic looking language described in 3 does allow you to
define inclusion among subsets of R. Also one can say a lot more cardinal
arithmetic than just 2^w = w_n.  It may be possible to characterize exactly
which set theoretic statements - up to provable equivalence in ZFC - are
stateable in this language, perhaps with certain prenex combinations, or
other syntactic restrictions. AE, AEA, EAE AEAE look particularly
interesting, allowing or not allowing blocks of quantifiers.  CH (continuum
hypothesis) is in  class AE even without blocks.

What other independent statements from ZFC could be amenable to such an
investigation? Things like "every set of cardinality w_1 is measurable"
come to mind.  This suggests adding a predicate for "being measurable." One
could also expect to investigate statements like "the union of fewer than c
sets of measure zero is of measure zero," etcetera, in this way.

On a different front, recall the very brief remarks I made about PA in
2:Axioms  11/6/97.

If you formulate PA in the standard way in the language 0,S,+,x, with a
free monadic letter R used as a place marker in the induction scheme, one
sees that every axiom (scheme) has at most 5 occurrences of variables.  In
fact, they all have at most 5 occurrences of variables/constants. I.e., we
count the total number of occurrences of variables and constants (in this
case the only constant is 0).

Here are some conjectures.

1. The set of all universally true formulas without R with at most 5
occurrences of variables/constants is decidable. There is a simple
axiomatization.
2. The set of all universally true formulas with (or without) the free
monadic letter R with at most 5 occurrences of variables/constants is
decidable in two senses. Firstly, that all arithmetic interpretations of R
are used. Secondly, that all interpretations of R (i.e., using all monadic
relations on N) are used. And one gets the same universally true formulas
in either case. Furthermore, if one considers the set of all such
universally true formulas, and interprets this as an axiomatization of
arithmetic with schemes, then one gets a system that is logically
equivalent to PA.

Now don't get me wrong: I am not asserrting that this count is the right
way to do complexity here. We are just trying to get our feet wet with some
new brands of f.o.m. research.  F.o.m. has a nice red-blooded experimental
nature to it, which flows rather freely. If one's intuition is sufficiently
good to ask a more or less right question, then this is bound to lead to
even better right questions, and then to discoveries of obviously permanent
value.