[FOM] 288:Discrete ordered rings and large cardinals

Thu Jun 1 11:28:06 EDT 2006

We first correct a typo in #287,
http://www.cs.nyu.edu/pipermail/fom/2006-May/010568.html

We wrote 

TEMPLATE 6. Let alpha(n,t,k,A,B) and beta(n,t,k,A,B) be elementary set terms
in numerical parameters n,t,k, and set parameters A,B. For all n,t >> k >= 1
and strictly dominating order invariant R containedin [1,n]^k x [1,n]^k,
there exists A containedin [1,n]^k such that alpha(n,r,k,A,RA) and
beta(n,r,k,A,RA) are order equivalent.

This should be 

TEMPLATE 6. Let alpha(n,t,k,A,B) and beta(n,t,k,A,B) be elementary set terms
in numerical parameters n,t,k, and set parameters A,B. For all n,t >> k >= 1
and strictly dominating order invariant R containedin [1,n]^k x [1,n]^k,
there exists A containedin [1,n]^k such that alpha(n,t,k,A,RA) and
beta(n,t,k,A,RA) are order equivalent.

We can present the Template more informally as follows:

INFORMAL TEMPLATE. For all n,t >> k >= 1 and strictly dominating order
invariant R containedin [1,n]^k x [1,n]^k, there exists A containedin
[1,n]^k such that two sets simply built from n,t,k,A,RA are order
equivalent. 

The idea is that some simple instances of the Template form Pi01 sentences
provably equivalent to Con(MAH) over EFA, and we conjecture that all
instances can be refuted in RCA0 or proved from large cardinals.

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

Here we shift gears and consider a statement asserting the existence of an
ordered ring and infinitely many distinguished elements, with a certain
property phrased in terms of polynomial images in the ring.

It is easy to see that the existence of such a ring with distinguished
elements is equivalent to the existence of a model of an explicitly given
set of sentences in predicate calculus with equality.

We therefore see that the existence of such a ring with distinguished
elements is provably equivalent, within a weak base theory, to a Pi01
sentence. 

If we formulate the existence in terms of countable ordered rings, then we
can take the base theory to be WKL_0.

So obviously this approach gives indirectly Pi01 sentences, and so there is
the question of to what extent they can be rephrased as explicitly Pi01
sentences, maintaining mathematical naturalness.

Now, the first order theory in question is logically simpler than general.
In fact, it is a set of A...AE...EA...AE...E sentences. The existence of a
model of a set of such sentences can be put into the form

"there is no finite obstruction of a certain kind".

We might well be able to talk about what "finite obstruction" means in a
sufficiently clear way so that it becomes compelling to talk in terms of the
existence of no finite obstruction as "being mathematically Pi01".

However, in this posting, we will not dwell on this issue.

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

1. REQUIRING INFINITELY MANY UNCOUNTABLE CARDINALS.

We work with discrete ordered rings R. We use the usual definition of
polynomial (in R), which maps some R^n into some R^m. We also use the usual
definition of an interval, where we require that the endpoints be elements
of R.

Let E containedin R. Polynomials (over R) are defined as usual, except that
we allow both the domain and the range to be any Cartesian powers of R. A
local polynomial range is the range of a polynomial on the Cartesian power
of an interval.   

A prime (in R) is defined as usual (greater than 1 and without a factor
strictly between 1 and the number).

Let E containedin R. An interval of E is the intersection of an interval (in
R) with E.

PROPOSITION A. There exists a discrete ordered ring R with positive elements
a_1 < a_2 < ... such that the intersection of any local polynomial range
with any [-a_i^r,a_i^r] is translatable onto an interval of the primes <
a_i+1.

THEOREM 1.1. Proposition A is provable in Zermelo set theory but not in
bounded Zermelo set theory, even with the axiom of choice. Proposition 1.1
is provably equivalent, over KP (Kripke Platek set theory), to the
consistency of bounded Zermelo set theory, and to the consistency of type
theory with infinity.

Proposition A (countable) is Proposition A with "countable" inserted in
front of "discrete".

THEOREM 1.2. Proposition A (countable) is provable in Zermelo set theory but
not in bounded Zermelo set theory, even with the axiom of choice.
Proposition A (countable) is provable in WKL0 + Con(bounded Z), and WKL0 +
Con(bype theory with infinity). Proposition A (countable) implies
Con(bounded Z) and Con(type theory with infinity), over RCA0.

If we just use finitely many a's, then the statement corresponds to finitely
many infinite cardinals. The more a's, the more infinite cardinals. We can
also get away with using polynomial ranges of small degree with a small
number of variables, but we will take this matter up at a later time.

2. REQUIRING AN EXTREME LARGE CARDINAL.

Let R be a discrete ordered ring. Let E containedin R^k. We say that V is a
subpower of E if and only if V containedin E has the form V = W^k. We say
that V is a maximal subpower of E if and only if V is a subpower of E that
is maximal with respect to inclusion.

Let E containedin [0,a]^k. An initial embedding of E is a strictly
increasing function h:[0,b] into [0,b], b <= a, which is not the identity,
such that for all x1,...,xk in [0,b], (x_1,...,x_k) in E iff (hx_1,...,hx_k)
in E.    

PROPOSITIONI B. There exists a discrete ordered ring R and positive elements
a_1 < a_2 < ... such that the intersection of any local polynomial range
with any [-a_i^r,a_i^r]^k has an initial embedding and a maximal subpower,
all three of which can be affinely bijected onto respective intervals of the
primes < a_i+1.

Recall these axioms from the standard set theory literature on large
cardinals, used in http://www.cs.nyu.edu/pipermail/fom/2006-May/010505.html

LCA1. There exists an elementary embedding j:V into M such that V(lambda)
containedin M, where lambda is the first fixed point above the critical
point.

LCA2. There is a nontrivial elementary embedding of some V(kappa) into
itself. 

THEOREM 2.1. Proposition B is provable in ZFC + LCA1 but not in ZFC + LCA2
(assuming the later is consistent). Proposition B is provable in KP +
Con(ZFC + LCA1) but not in ZFC + Con(ZFC LCA2), (assuming the later is
consistent). There is a Pi01 sentence phi such that Proposition B is
provably equivalent to phi over KP.

Proposition B (countable) is Proposition B with "countable" inserted in
front of "discrete".

THEOREM 2.2. Proposition B (countable) is provable in ZFC + LCA1 but not in
ZFC + LCA2 (assuming the later is consistent). Proposition B (countable) is
provable in WKL0 + Con(ZFC + LCA1). There is a Pi01 sentence phi such that
Proposition B (countable) is provably equivalent to phi over WKL0.

**********************************

I use http://www.math.ohio-state.edu/%7Efriedman/ for downloadable
manuscripts. This is the 288th 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-249 can be found at
http://www.cs.nyu.edu/pipermail/fom/2005-June/008999.html in the FOM
archives, 6/15/05, 9:18PM. NOTE: The title of #269 has been corrected from
the original.

250. Extreme Cardinals/Pi01  7/31/05  8:34PM
251. Embedding Axioms  8/1/05  10:40AM
252. Pi01 Revisited  10/25/05  10:35PM
253. Pi01 Progress  10/26/05  6:32AM
254. Pi01 Progress/more  11/10/05  4:37AM
255. Controlling Pi01  11/12  5:10PM
256. NAME:finite inclusion theory  11/21/05  2:34AM
257. FIT/more  11/22/05  5:34AM
258. Pi01/Simplification/Restatement  11/27/05  2:12AM
259. Pi01 pointer  11/30/05  10:36AM
260. Pi01/simplification  12/3/05  3:11PM
261. Pi01/nicer  12/5/05  2:26AM
262. Correction/Restatement  12/9/05  10:13AM
263. Pi01/digraphs 1  1/13/06  1:11AM
264. Pi01/digraphs 2  1/27/06  11:34AM
265. Pi01/digraphs 2/more  1/28/06  2:46PM
266. Pi01/digraphs/unifying 2/4/06  5:27AM
267. Pi01/digraphs/progress  2/8/06  2:44AM
268. Finite to Infinite 1  2/22/06  9:01AM
269. Pi01,Pi00/digraphs  2/25/06  3:09AM
270. Finite to Infinite/Restatement  2/25/06  8:25PM
271. Clarification of Smith Article  3/22/06  5:58PM
272. Sigma01/optimal  3/24/06  1:45PM
273: Sigma01/optimal/size  3/28/06  12:57PM
274: Subcubic Graph Numbers  4/1/06  11:23AM
275: Kruskal Theorem/Impredicativity  4/2/06  12:16PM
276: Higman/Kruskal/impredicativity  4/4/06  6:31AM
277: Strict Predicativity  4/5/06  1:58PM
278: Ultra/Strict/Predicativity/Higman  4/8/06  1:33AM
279: Subcubic graph numbers/restated  4/8/06  3:14AN
280: Generating large caridnals/self embedding axioms  5/2/06  4:55AM
281: Linear Self Embedding Axioms  5/5/06  2:32AM
282: Adventures in Pi01 Independence  5/7/06
283: A theory of indiscernibles  5/7/06  6:42PM
284: Godel's Second  5/9/06  10:02AM
285: Godel's Second/more  5/10/06  5:55PM
286: Godel's Second/still more  5/11/06  2:05PM
287: More Pi01 adventures  5/18/06  9:19AM

Harvey Friedman