FOM: 16:Logical Equations, etc.

[Harvey Friedman]

This is the 16th 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.
4:Simplicity  11/14/97  4:25PM
5:Constructions  11/15/97  5:24PM
6:Undefinability/Nonstandard Models   11/16/97  12:04AM
7.Undefinability/Nonstandard Models   11/17/97  12:31AM
8.Schemes 11/17/97    12:30AM
9:Nonstandard Arithmetic 11/18/97  11:53AM
10:Pathology   12/8/97   12:37AM
11:F.O.M. & Math Logic  12/14/97 5:47AM
12:Finite trees/large cardinals  3/11/98  11:36AM
13:Min recursion/Provably recursive functions  3/20/98  4:45AM
14:New characterizations of the provable ordinals  4/8/98  2:09AM
14':Errata  4/8/98  9:48AM
15:Structural Independence results and provable ordinals  4/16/98  10:53PM

A complete archiving of fom, message by message, is available at
http://www.math.psu.edu/simpson/fom/
Also, my series of positive postings (only) is archived at
http://www.math.ohio-state.edu/foundations/manuscripts.html

This posting supercedes postings 14, 14', and 15. Theorem 4 from 15 needs
some modification - it's false as it stands. Also, I have still been
experimenting with different ways of presenting this mode of
characterization of the provable ordinals. Consequently, there are enough
changes over earlier postings from 14 on, that it is best to give a
complete restatement.

*******

The provable ordinals of a theory T which contains RCA_0 is
defined as the ordinals alpha for which there is a presentation of a
primitive recursive relation on N of order type alpha such that T proves
that this presentation defines a well ordering on N.

This concept is very robust. For instance, we may consider arithmetically
defined relations instead of primitively recursively defined relations. If
T contains ACA_0 then we get the same provable ordinals. In fact, we can
use Sigma-1-1 defined relations, and if T contains ATR_0 then again we get
the same provable ordinals. We let o(T) be the sup of the provable ordinals
of T.

For "good" theories T, o(T) is a recursive ordinal. However, there are
consistent r.e. theories T containing RCA_0 for which every recursive
ordinal is a provable ordinal. The situation is clarified by the following:

THEOREM. Let T be a Sigma-1-1 theory containing ACA_0. Then o(T) is a
recursive ordinal if and only if every Pi-1-1 theorem of T is true.

It is well known that o(RCA_0) = omega^omega; o(ACA_0) = epsilon_0;
and o(ATR_0) = Gamma_0.

1. RELATIONAL EQUATIONS

Let R containedin A^2 and E containedin A. We write R[E] = {y: there exists
x such that R(x,y)}. Let (A,<) be a linear ordering. We write R_<[E] = {y:
there exists x < y such that R(x,y)}.

We wish to consider the relational equation E = A\R_<[E], where (A,<) is a
linear ordering and R containedin A^2.

THEOREM 1.1. Let (A,<) be a linear ordering. The following are equivalent.
	i) for all R contianedin A^2, E = A\R_<[E] has a solution;
	ii) for all R containedin A^2, E = A\R_<[E] has a unique solution;
	iii) (A,<) is a well ordering.

We also want to consider a multidimensional generalization of the
relational equations E = R_<[A\E]. Let (A,<) be a linear ordering and k,n
>= 1. For x,y in A^k, we write x < y if and only if max(x) < max(y). Let R
containedin A^2k and E containedin A^k. We write R[E] = {y in A^k: there
exists x such that R(x,y)}. We write R_<[E] = {y in A^k: there exists x < y
such that R(x,y)}.

We now consider relational equations E = R_<[A^k\E]. Here the dimensions
match: E is k-dimensional and R is 2k-dimensional.

THEOREM 1.2. Let (A,<) be a linear ordering and k >= 1. The following are
equiavlent.
	i) for all R contianedin A^2, E = R_<[A\E] has a solution;
	ii) for all R containedin A^2k, E = R_<[A^k\E] has a unique solution;
	iii) (A,<) is a well ordering.

2. LOGICAL EQUATIONS

For our purposes, a Boolean form is a propositional combination of
inequalities between variables, x_i < x_j. For this purpose, we use
variables x_1,x_2,..., the formal symbol <, and the usual logical
connectives &, v, not, -->. A Boolean form in {x_1,...,x_n} is a Boolean
form all of whose variables are among those shown.

The purpose of these Boolean forms is to specify a particular relation on
every linear ordering in a uniform way. Thus if R is a Boolean form in
x_1,...,x_k and (A,<) is a linear ordering, then we write R_A for
{(x_1,...,x_k) in A^k: R(x_1,...,x_k)}.

We can now consider logical equations of the form E = R_A<[A^k\E]. Here R
is a Boolean form in x_1,...,x_k, and A,E are unknowns. Strictly speaking,
we should write E =
(R_A)_<[A^k\E], but we omit the parentheses. This logical equation is said
to be k-ary.

Solutions to k-ary logical equations are linearly ordered relations; i.e.,
triples (A,<,E), where (A,<) is a linear ordering
and E containedin A^k.

An ordinal solution to a logical equation is a solution whose linear
ordering is an ordinal under epilson. The following result illustrates the
power of logical equations.

THEOREM 2.1. A set of ordinals is constructible if and only if it is a
cross section of an ordinal solution to some logical equation.

COROLLARY. V = L if and only if every set of ordinals is a cross section of
an ordinal solution to some logical equation.

3. SOME STRUCTURAL INDEPENDENCE RESULTS

We now consider assertions of the following form: every logical equation
has a (countable) solution with an automorphism of a certain kind. I.e., an
automorphism of (A,<,E) viewed as a relational structure.

We will consider only first order conditions on the automorphism. I.e., a
first order condition on (A,<,h), where h is an automorphism. Obviously, by
the downward Skolem Lowenheim theorem, the assertion is equivalent to the
assertion with "countable."

Also, clearly, every such assertion is provably equivalent to a Pi^0_1
sentence.

THEOREM 3.1. The following is provable in RCA_0 + WKL. "Every logical
equation has a (countable) solution with an automorphism whose fixed points
form a proper initial segment" if and only if Con(PA).

THEOREM 3.2. The following is provable in RCA_0 + WKL. "Every logical
equation has a (countable) solution with a limit point and an automorphism
whose fixed points form a proper initial segment" if and only if Con(ZFC).

We can also consider embeddings h of (A,<,R) into itself. A critical point
of h is a point x such that h is the identity below x and h(x) > x.

THEOREM 3.3. The following is provable in RCA_0 + WKL. "Every logical
equation has a (countable) solution with an embedding that has a critical
point" if and only if Con(ZFC + {there exists a k-subtle cardinal}_k).

With this approach, we should be handle the entire large cardinal
hierarchy. We'll report on this later.

4. LOGICAL CORES AND PROVABLE ORDINALS

A linearly ordering is said to be normal if and only if the natural numbers
form an initial segment under their usual ordering. A linearly ordered
relation is normal if and only if its linear ordering is normal.

If R is k-ary, and x in N^k-1, then we write R_x containedin N for the
cross section {y:R(x,y)}. By convention, N^0 is empty.

Let (A,<,R) be a normal k-ary linearly ordered relation. We define the
binary relation (A,<,R)* containedin N^k-1 x N^k-1 as follows.
(A,<,R)*(x,y) if and only if min(R^x) < min(R^y). Thus (A,<,R)*(x,y)
implies that min(R_x) and min(R_y) exist. If k = 1 then (A,<,R)* is taken
to be the empty relation.

Let X be a class of linearly ordered relations, and V be a logical
equation. We define the core of X with respect to V as the intersection of
all (A,<,R)*, where (A,<,R) is a normal solution to V that lies in X.

The logical cores of X are defined to be the cores of X with respect to
logical equations. Thus there are countably many logical cores of X.

Let X_1 be the class of all linearly ordered relations with a limit
point and an automorphism whose fixed points form a proper initial segment.

Let X_2 be the class of all linearly ordered relations with an embeedding
that has a critical point.

THEOREM 4.1. Assuming that every Sigma^1_2 sentence provable in ZFC is
true, the logical cores of X_1 are r.e. and well founded, and their
ordinals form an initial segment of ordinals that properly contains the
provable ordinals of ZFC and is properly included in the provable ordinals
of ZFC + "every Sigma^1_2 sentence provable in ZFC is true."

THEOREM 4.2. Assuming that every Sigma^1_2 sentence provable in ZFC +
{there exists a k-subtle cardinal}_k is true, the logical cores of X_2 are
r.e. and well founded, and their ordinals form an initial segment of
ordinals that properly contains the provable ordinals of T = ZFC + {there
exists a k-subtle cardinal}_k and is properly included in the provable
ordinals of T + "every Sigma-1-2 sentence provable in T is true."

The cardinality of a limit point in a linear ordering is defined to be the
cardinality of the set of its predecessors. We now define several classes
of linear orderings. Let kappa be an uncountable cardinal.

M_1(kappa): cardinality kappa, and with a countable limit point.
M_2(kappa): M_1(kappa) and every proper initial segment has cardinality <
kappa.
M_3(kappa): M_2(kappa) and there is a closed unbounded set of order type kappa.

The logical cores of a class M of linear orderings are defined to be the
logical cores of the class X of linearly ordered relations whose linear
ordering lies in M.

THEOREM 4.3. Define f_i(kappa) = the set of all ordinals of well founded
logical cores of M_i(kappa). The minimum f_1(kappa) = the minimum
f_2(kappa) = the minimum f_3(kappa), and lies strictly between the provable
ordinals of Z_2 and the provable ordinals of Z_2 + "every Sigma^1_2
sentence provable in Z_2 is true." The maximum f_1(kappa) lies strictly
between the provable ordinals of type theory and the provable ordinals of
type theory + "every Sigma^1_2 sentence provable in type theory is true."
Assuming that there is a cardinal that is simultaneously n-Mahlo for all n
>= 1, the
maximum f_2(kappa) lies strictly between the provable ordinals of T = ZFC +
{there exists an n-Mahlo cardinal}_n) and the provable ordinals of T +
"every Sigma^1_2 sentence provable in T is true." Assuming that there is a
cardinal that is simultaneously n-subtle for all n >= 1, the maximum
f_3(kappa) lies strictly between the provable ordinals of T' = ZFC + {there
exists an n-subtle cardinal}_n) and the provable ordinals of T' + "every
Sigma^1_2 sentence provable in T' is true."

THEOREM 4.4. The three min's in Theorem 3 are realized at and only at
kappa = omega_1. The first max in Theorem 3 is realized at any kappa >=
omega_omega. The second max in Theorem 3 is realized at any kappa that is
simultaneously n-Mahlo for all n >= 1. The third max in Theorem 3 is
realized at any kappa that is simultaneously n-subtle for all n >= 1. In
these cases, the relevant logical cores are all r.e. and well founded.