[FOM] 552: Foundational Methodology 3/Maximality

[Harvey Friedman]

Where we left off from
http://www.cs.nyu.edu/pipermail/fom/2014-October/018228.html

THE STRONGEST STATEMENT, OVER ZF PLUS THE TRUE Pi01 SENTENCES, OF THE
FORM "SUCH AND SUCH (PURELY UNIVERESAL) SENTENCE IN PREDICATE CALCULUS
WITH EQUALITY HAS A MODEL ON EVERY INFINITE DOMAIN" IS PROVABLY
EQUIVALENT TO THE AXIOM OF CHOICE, OVER ZF PLUS THE TRUE Pi01
SENTENCES.

THE STRONGEST STATEMENT, OVER ZF PLUS THE TRUE Pi01 SENTENCES, OF THE
FORM "SUCH AND SUCH (PURELY UNIVERESAL) SENTENCE IN PREDICATE CALCULUS
WITH EQUALITY HAS A MODEL ON EVERY NONEMPTY DOMAIN" IS PROVABLY
EQUIVALENT TO THE AXIOM OF CHOICE, OVER ZF PLUS THE TRUE Pi01
SENTENCES.

The first statement above is straightforward using Goedel's
Completeness Theorem.

I now rework the proof of the second statement, as there were some
correctable flaws. It is quite easy to fall into the trap of assuming
that you have a cardinal lambda such that lambda+ is regular. The
uniformity in condition 4 must be exploited properly.

We use the universal sentence phi expressing

1. Equivalence relation E on a subset D' of the domain D. Define [x]
only for x in D', where [x] is a subset of D'.
3. Set S contained in D' 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' disjoint union 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.

We write D'/E for the set of equivalence classes of E on D'. We write
(D'/E)* for the set of equivalence classes of E on K = D' intersect
lambda+.

case 1. |S| >= lambda+. Then each [x] has at least lambda+
elements. Hence each [x], has at least one element from
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
applying the bijection between [x] and S, given by 4, to x. Thus we
have a one-one map
from D' into S x S. Hence D' is well ordered. By 5, D\D' is also well
ordered. Hence D is well ordered. In particular, B is well ordered.

case 2. |S| is not >= lambda+. Note that S has at most lambda elements
of lambda+. We have a bijection from D/E onto S. We have an embedding
from (D/E)* onto W contained in S. Clearly W is well ordered, and so
must have at most lambda elements. Hence we have an embedding from
(D/E)* into lambda. Using condition 4, we get a map that takes each u
in (D/E)* to a an embedding from u into S. Now every value of every
such map can be indexed by an element of (D/E)* and an element of K,
using that (D/E)* is well ordered. So we get a map that takes each u
in (D/E)* to an embedding from u into lambda. This together with
(D/E)* having at most lambda elements allows us to conclude that K has
at most lambda elements. Therefore lambda\D' has lambda+ elements. By
5, lambda+ is embeddable in D' disjoint union D'. Hence lambda+ is
embeddable in D'. The preimage under this embedding of B must have at
most lambda elements. Hence lambda+ is embeddable in K, which is a
contradiction.

QED

What is the status (especially equivalence with AxC) and relative
status in ZF of

There is a semigroup, group, abelian semigroup, abelian group,
divisible abelian group, free group, ring, commutative ring, field,
algebraically closed field, ordered field, ordered ring, discrete
ordered ring, linear ordering, dense linear ordering, model of
Presburger, on every infinite domain. And any other special cases that
you get interested in.

Next time, I will start talking again about 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 552nd 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
551: Foundational Methodology 2/Maximality  10/19/14 3:06AM

Harvey Friedman