[FOM] 551: Foundational Methodology 2/Maximality

[Harvey Friedman]

This is a continuation of
http://www.cs.nyu.edu/pipermail/fom/2014-October/018219.html

In that previous posting, I indicated some important features of my
general f.o.m. methodology. I have started to apply it to a notion
that has been around for some time

*) intrinsic maximality of the set theoretic universe

as a way of generating or justifying axioms for set theory. It has
clearly not been appropriately elucidated, and the notion is also
under considerable attack these days.

In fact, there is folklore that it is a sound way of generating the
axioms of ZFC. That specifically is being questioned by some even with
regard to the AxC = axiom of choice.

Now the way I see it, informally "intrinsic maximality (of the set
theoreitc universe)" means something like this:

**) the set theoretic universe is as large as possible or imaginable -
consistent with the most elemental features of sets**

What elemental features of sets? Well, for this purpose, we take as a
working idea, first and foremost, extensionality = two sets are equal
if and only if they have the same elements. But what about foundation?
Well, I just don't know at this point what attitude we should take
toward foundation for present purposes.

Prima facie, it would appear that AxC follows from **). Say, given an
equivalence relation, we can certainly imagine the idea that we have
picked one element from each equivalence class. But how do we
systematize this?

I came up with the following more general idea. Instead of starting
with an equivalence relation, we can instead start with an arbitrary
set X. We can put "basic" conditions on a relation or function on X.
We then consider the sentence

#) for all sets X there exists a relation or function satisfying a
given condition.

Here are two of the simplest special cases.

For all X there exists a linear ordering on X.
For all X there is a one-one function from X to X that is not onto.
For all X there is a one-one function from X^2 into X.

Of course, the first is provable in ZFC. However, the other two are
refutable in ZFC.

So this suggests the following.

##) for all infinite sets X there exists a relation or function
satisfying a given condition.

Then consider these three examples.

For all infinite X there exists a linear ordering on X.
For all infinite X there is a one-one function from X to X that is not onto.
For all infinite X there is a one-one function from X^2 into X.

These are all provable in ZFC. The third is equivalent to AxC over a
weak fragment of ZF. The conjunction of the first two does not imply
AxC over ZF, and neither of the first two implies the other over ZF.

Thus it looks like we have stumbled onto a calculus that unifies a lot
of important work concerning forms of the axiom of choice in set
theory.

So now let's get it all together.

DEFINITION 1. K(infinity) is the set of all sentences of set theory of
the following form. For all infinite D there exists a model of phi
with domain D. Here phi is a sentence in first order predicate
calculus with equality. K(nonempty) is the set of all sentences of set
theory of the following form. For all nonempty D there exists a model
of phi with domain D.

But an important feature of the examples are that they are purely universal.

DEFINITION 2. K(infinity,pi) consists of "for all infinite D there
exists a model of phi with domain D" where phi is purely universal.
K(nonempty,pi) consists of "for all nonempty D there exists a model of
phi with domain D" where phi is purely universal.

It appears that every element of the K's, from the point of view of
ZF, has two orthogonal components - its arithmetic part and its set
theoretic part.

THEOREM 1. The following is provable in a weak fragment of ZFC. A
sentence lies in K(infinity) if and only if it is satisfiable in some
(every) infinite domain. A sentence lies in K(nonempty) if and only if
it is satisfiable in every domain if and only if it is satisfiable in
some (all) infinite domains and satisfiable in all nonempty finite
domains. Thus the set of all true sentences in K(inifnity) and
K(nonempty) are complete Pi01, respectively.

DEFINITION 3. Let ZFC* be ZFC together with the true Pi01 sentences.

THEOREM 2. Every element of K(infinity) and K(nonempty) is provable or
refutable in ZFC*. In fact, every such element is either provable in a
weak fragment of ZFC* or refutable in a weak fragment of ZF.

There are plenty of interesting special fragments of first order
predicate calculus with equality that where validity and validity for
infinite models are decidable - and demonstrably so in ZFC (even in a
weak fragment of ZF). For K(infinity) and K(nonempty) based on such
fragments, Theorem 2 will clearly hold with ZFC* replaced by ZFC. For
these fragments of K(nonempty) and K(infinity), we should be able to
get a particularly clear understanding of the status of the elements
over ZF.

the program is to understand the status and relative status of the
elements of K(nonempty) and K(infinity) over ZF*.

We have already seen that there is a variety of elements of
K(infinity,pi) over ZF*, some of which are provably equivalent to AxC
over a weak fragment of ZF*. However, what about elements of
K(nonempty) and K(nonempty,pi)?

THEOREM 3. There is an element of K(infinity,pi) and of
K(nonempty,pi), respectively, that is provably equivalent to AxC over
a weak fragment of ZF.

We have already seen that we can use "for every infinite D there is a
one-one f:D^2 into D". But about about K(nonemtpy,pi)?

We now show that

*The axiom of choice can be expressed as the assertion that some given
purely universal sentence is satisfiable in every nonempty domain.
Same with "infinite domain".

i looked into this more deeply than I did in posting #550. I think
that a good way of proving this is as follows.

The sentence phi asserts the following.

1. Equivalence relation E on D.
2. Set D' obtained by removing 0,1, or 2 elements from each
equivalence class of E on D, as long as you leave at least one element
after removal. Work with E on D'.
3. Set S which picks exactly one from each equivalence class of E on D'.
4. Map which, given x in D', produces a bijection between [x] and S,
depending only on [x].
5. D\D' is embeddable in D' x D'.

Note that phi has a model with domain any nonempty finite set.

Let D = B union lambda+, where lambda is an infinite cardinal, and
lambda cannot be embedded into B. We prove that B is well ordered.

case 1. |S| >= lambda+. Then each [x], x in D', has at least lambda+
elements. Hence each [x], x in D', has at least one element of
lambda+. Hence |S| = lambda+. For each x in D', we associate first the
unique element of S that is equivalent to x, and then the result of
the bijection between [x] and S given by 4. Thus we have a one-one map
from D' into S x S. Hence D' is well ordered. By 5, D\D' is well
ordered. Hence D is well ordered. In particular, B is well ordered.

case 2. |S| is not >= lambda+. Then no equivalence class has
cardinality >= lambda+. Hence every equivalence class of E on D' has
fewer than lambda+ elements of lambda+. Hence every equivalence class
of E on D has at most lambda elements of lambda+. Hence there are at
least lambda+ equivalence classes of E on D. Hence there are at least
lambda+ equivalence classes of E on D'. Hence every equivalence class
of E on D' has at least lambda+ elements. This is a contradiction.

QED

Next posting will start to engage with maximality.

************************************************************
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 551st 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-527 can be found at the FOM posting
http://www.cs.nyu.edu/pipermail/fom/2014-August/018092.html

528: More Perfect Pi01  8/16/14  5:19AM
529: Yet more Perfect Pi01 8/18/14  5:50AM
530: Friendlier Perfect Pi01
531: General Theory/Perfect Pi01  8/22/14  5:16PM
532: More General Theory/Perfect Pi01  8/23/14  7:32AM
533: Progress - General Theory/Perfect Pi01 8/25/14  1:17AM
534: Perfect Explicitly Pi01  8/27/14  10:40AM
535: Updated Perfect Explicitly Pi01  8/30/14  2:39PM
536: Pi01 Progress  9/1/14 11:31AM
537: Pi01/Flat Pics/Testing  9/6/14  12:49AM
538: Progress Pi01 9/6/14  11:31PM
539: Absolute Perfect Naturalness 9/7/14  9:00PM
540: SRM/Comparability  9/8/14  12:03AM
541: Master Templates  9/9/14  12:41AM
542: Templates/LC shadow  9/10/14  12:44AM
543: New Explicitly Pi01  9/10/14  11:17PM
544: Initial Maximality/HUGE  9/12/14  8:07PM
545: Set Theoretic Consistency/SRM/SRP  9/14/14  10:06PM
546: New Pi01/solving CH  9/26/14  12:05AM
547: Conservative Growth - Triples  9/29/14  11:34PM
548: New Explicitly Pi01  10/4/14  8:45PM
549: Conservative Growth - beyond triples  10/6/14  1:31AM
550: Foundational Methodology 1/Maximality  10/17/14  5:43AM

Harvey Friedman