FOM: 75:Finite Reverse Mathematics
Harvey Friedman
friedman at math.ohio-state.edu
Tue Dec 28 13:21:46 EST 1999
We have renamed Reverse Arithmetic by Finite Reverse Mathematics. We could
have used the name Reverse Finite Mathematics, but that is grammatical
awkward, and names of potential subjects are just too critical for that.
1. AXIOMS FOR FINITE SETS OF INTEGERS/REVIEW.
The approach in #74 was to use basic axioms for integers, and basic axioms
for finite sets of integers. Everything was unimpeachable except possibly
the two axioms constructing A+B and A*B, for finite sets of integers A,B.
Now A+B is around. For example, there is the celebrated alphabeta theorem
of Mann (originally conjectured in 1931) discussed in
H.B. Mann, "A proof of the fundamental theorem on the density of sums of
sets of positive integers," Annals of Math. (2) 43, 523-527 (1942).
E. Artin and P. Scherk, "On the sums of two sets of integers," Annals of
Math. (2) 44, 138-142 (1943).
F.J. Dyson, "A theorem on the densities of sets of integers," Journal of
the London Math. Soc., 20, 8-14 (1945).
(References from Niven and Zuckerman, An Introduction to the Theory of
Numbers, Wiley, 1962.)
But what about A*B? It's probably around too, but the closest I have seen
in my personal library is the discussion in
Graham, Rothschild, Spencer, Ramsey Theory, Wiley, 1980, page 68,
where for sets S of positive integers, the set of all nontrivial products
of elements of S is discussed in connection with extensions of Folkman's
theorem. Some results are mentioned of the author's and Hindman involving
this construction.
So I said that one can get away with A+B and {1,4,9,16,...,n^2}. However,
that was not quite right: I left out that one needs scalar multiplication
n*A; i.e., {n*m: m in A}. But that is unimpeachable.
So in review, we can use the following from #74:
1. Additive identity. x+0 = x.
2. Additive commutativity. x+y = y+x.
3. Additive associativity. x+(y+z) = (x+y)+z.
4. Additive inverse. x+(-x) = 0.
5. Multiplicative identity. x*1 = x.
6. Multiplicative commutativity. x*y = y*x.
7. Multiplicative associativity. x*(y*z) = (x*y)*z.
8. Distributivity. x*(y+z) = (x*y)+(x*z).
9. Linearity. x = 0 or 0 < x or 0 < -x.
10. Additive positivity. (0 < x and 0 < y) implies 0 < x+y.
11. Multiplicative positivity. (0 < x and 0 < y) implies 0 < x*y.
12. Unit positivity. 0 < 1.
13. Irreflexivity. not(0 < 0).
14. Finite intervals. (therexists A)(forall x)(x epsilon A iff (y < x and x
< z)).
15. Boolean difference. (therexists C)(forall x)(x epsilon C iff (x epsilon
A and not(x epsilon B)).
16. Set addition. (therexists C)(forall x)(x epsilon C iff (therexists
y)(therexists z)(y epsilon A and z epsilon B and x = y+z)).
17. Least elements. (therexists x)(x epsilon A) implies (therexists x)(x
epsilon A and ((forall y)(y epsilon A implies not(y < x)).
18. Common multiples. (therexists x)(0 < x and (forall y)((y epsilon A and
0 < y) implies (therexists z)(x = y*z))).
19. Set multiplication. (therexists C)(forall x)(x epsilon C iff (therexists
y)(therexists z)(y epsilon A and z epsilon B and x = y*z)).
Or we can use the following modification of #74:
1. Additive identity. x+0 = x.
2. Additive commutativity. x+y = y+x.
3. Additive associativity. x+(y+z) = (x+y)+z.
4. Additive inverse. x+(-x) = 0.
5. Multiplicative identity. x*1 = x.
6. Multiplicative commutativity. x*y = y*x.
7. Multiplicative associativity. x*(y*z) = (x*y)*z.
8. Distributivity. x*(y+z) = (x*y)+(x*z).
9. Linearity. x = 0 or 0 < x or 0 < -x.
10. Additive positivity. (0 < x and 0 < y) implies 0 < x+y.
11. Multiplicative positivity. (0 < x and 0 < y) implies 0 < x*y.
12. Unit positivity. 0 < 1.
13. Irreflexivity. not(0 < 0).
14. Finite intervals. (therexists A)(forall x)(x epsilon A iff (y < x and x
< z)).
15. Boolean difference. (therexists C)(forall x)(x epsilon C iff (x epsilon
A and not(x epsilon B)).
16. Set addition. (therexists C)(forall x)(x epsilon C iff (therexists
y)(therexists z)(y epsilon A and z epsilon B and x = y+z)).
17. Least elements. (therexists x)(x epsilon A) implies (therexists x)(x
epsilon A and ((forall y)(y epsilon A implies not(y < x)).
18. Common multiples. (therexists x)(0 < x and (forall y)((y epsilon A and
0 < y) implies (therexists z)(x = y*z))).
19. Scalar set multiplication. (therexists B)(forall y)(x epsilon B iff
(therexists z)(z epsilon A and y = x*z)).
20. Squares. (therexists A)(forall y)(y in A iff (therexists z)(0 < z and z
< x and y = z*z)).
The two groups have the same first 18 axioms, and differ after that.
In the first group, Axioms 1-19 are equivalent to ISigma_0(exp) = EFA and
ISigma_0 is obtained by dropping axiom 18. In the second group, Axioms 1-20
are equivalent to ISigma_0(exp) = EFA and ISimga_0 is obtained by dropping
axiom 18.
Now jsut how unimpeachable is {1,4,9,...,n^2}? I said in posting #74 that I
was worried about it. But fortunately already in the same Niven and
Zuckerman book that I found the H.B. Mann stuff with A+B, I also found the
following on page 232 right after the definition of A+B:
"As an example let us take S to be the set of squares 0,1,4,9,... and I the
set of all nonnegative integers. Then by Theorem 5.6 we see that S + S + S
+ S = I."
Of course, strictly speaking, we cannot use the set of squares 0,1,4,9,...
for our purposes since this is infinite. However, this seems like a minor
objection.
Another minor objection is that Niven and Zuckerman only define A+B if A,B
are sets of nonnegative integers and 0 lies in both A and B. The natural
definition is for sets A,B of integers without restriction, and the
restrictions they place are merely an artifact of the fact that they are
developing a proof of Mann's theorem. Nevertheless, with a little care, one
can derive the existence of A+B for finite A,B containedin Z from the
existence of A+B for finite A,B containedin N with 0 in A,B, anyways -
using the existence of integer translates. And the existence of translates
is explicitly in a lot of places in the literature.
So in conclusion, both of these axiom systems are more or less
unimpeachable, with an edge perhaps given to the second system.
2. PRACTICAL PROPOSAL OF A BASE THEORY FOR FINITE REVERSE MATHEMATICS.
By practical, I mean
a) a program which is clearly doable to some extent, with a number of
initial results.
b) a program which has a number of open problems with various common themes.
c) the general flavor and structure of the program is the same as reverse
mathematics as presented in Simpson's book, with statements in finite
mathematics expected to be equivalent to a handful of systems.
d) just as in existing reverse mathematics, the formal systems are finitely
axiomatizable, though presented in terms of schemes.
Thus in this section, we do not concentrate on the major foundational
challenge of making the base theory consist of the most unimpeachably
essential universally used mathematical statements - which was addressed in
postings #73, #74, and in section 1 above. In fact, we follow the tradition
represented in Simpson's book by presenting formal systems in the most
efficient way for logicians, freely using schemes, obvious codings,
etcetera.
The (at present most practical) base theory of existing reverse mathematics
is RCA_0. The analogous practical base theory for finite reverse
mathematics is proposed to be FCA (finite comprehension axiom with
restricted induction).
Recall that RCA_0 is a two sorted system based on variables over
nonnegative integers, variables over sets of nonnegative integers,
0,S.+,*,<,= among nonnegative integers, and epsilon between nonnegative
integers and sets of nonnegative integers.
Here FCA is a two sorted system based on variables over nonnegative
integers, variables over finite sets of nonnegative integers, 0,S.+,*,<,=
among nonnegative integers, and epsilon between nonnegative integers and
finite sets of nonnegative integers.
The axioms of FCA are as follows.
1. x+0 = x.
2. x+Sy = S(x+y).
3. x*0 = 0.
4. x*Sy = x*y + x.
5. Sx not= 0.
6. Sx = Sy implies x = y.
7. not(x < 0).
8. x < Sy iff (x < y or x = y).
9. Finiteness. (therexists x)(forall y)(y in A implies y < x).
10. Every nonempty finite set has a least element.
11. Bounded comprehension. (therexists A)(forall y)(x in A iff (y < x and
phi)), where phi is strictly bounded and A is not free in phi.
In 11, by strictly bounded we mean that all quantifiers are over integers,
and are bounded to terms of either sort, and of course free variables are
allowed of either sort.
As an obvious consequence of FCA, we have
12. Strictly bounded induction. I.e., induction with respect to all
strictly bounded formulas.
We could make FCA a weak subsystem of RCA_0 by simply dropping axiom 9.
However, for the moment, we prefer to think of finite reverse mathematics
as a self contained autonomous subject, and leave 9 in.
NOTE: There is work of Buss, Krajicek, Takeuti, etc. in this direction. Was
this system considered by one or more of them? Note that we are presenting
this system in the context of a proposal for a new incarnation of reverse
mathematics, something that may not have been concerned with. END.
THEOREM 1. FCA is a conservative extension of ISigma_0. FCA is finitely
axiomatizable. FCA is equivalent to the two systems presented in section 1,
without their axiom of multiples, but with this axiom of finiteness added
(where we are converting from integers to nonnegative integers).
We believe that FCA is a practical base theory for finite reverse
mathematics. Just as in reverse mathematics, we can use the quadratic
pairing function on the natural numbers to code finite sequences of
nonnegative integers and finite functions of several variables.
Assuming we use FCA as the base theory, what should some of the principal
stronger theories be? We postpone discussion of this, and instead now
disucss the issues involved in using a weaker base theory than FCA.
3. THE CHALLENGE OF WEAKENING FCA_0 FOR FINITE REVERSE MATHEMATICS.
RCA_0 can be challenged as too strong a base theory for reverse
mathematics, because too much exciting mathematics with intricate logical
structure is already provable, and thus lost to reverse mathematics with
RCA_0 as the base theory. Work is under way to deal with this.
In fact, the whole enterprise of finite reverse mathematics can be viewed
as addressing a small corner of this issue. I say small corner because
RCA_0 can be challenged to be too strong not only in the realm of finite
mathematics, but also in the realm of infinite mathematics, and finite
reverse mathematics does not address the infinite context at all.
But the same criticism of RCA_0 can be made of FCA. So in this section, we
explore the possibility of weakening the base theory FCA.
Some obvious fragments of FCA are obtained in a couple of ways. Firstly, we
can get rid of sets entirely and work in arithmetic only. So we are looking
at fragments of ISigma_0. I.e., fragments of
1. x+0 = x.
2. x+Sy = S(x+y).
3. x*0 = 0.
4. x*Sy = x*y + x.
5. Sx not= 0.
6. Sx = Sy implies x = y.
7. not(x < 0).
8. x < Sy iff (x < y or x = y).
9. Induction for all bounded formulas in the language 0,S,+,*,<.
The most obvious fragments are what is called lE_i, i >= 0. This is
induction with respect to all bounded formulas in prenex form which are in
Sigma_k form in the obvious sense. Thus IE_0 is just what is called open
induction.
IE_0 has been seriously studied, but I do not know of any reasonable set of
mathematical theorems that are provably equivalent to IE_0.
So we might take IE_0 as a base theory. Then the question is whether we can
find any reasonable set of mathematical theorems that are provably
equivalent to IE_1 over IE_0?
Actually, it is not even clear (to me) whether these fragments IE_i are
finitely axiomatizable. If not, then one certainly is not going to get any
single or small group of theorems to bootstrap from one to the next.
So it seems to be quite difficult to preserve the reverse mathematics
spirit in this setup. It still could be the case that large groups of
theorems provable in ISigma_0 but not in IE_0 might themselves be provably
equivalent over IE_0 to each other, and there just might be a manageable
number of equivalence classes. And just what these appropriate fragements
of ISigma_0 are that might emerge are not clear to me.
It is perhaps somewhat easier to imagine the previous paragraph with IE_0
replaced by IE_1. Thus one would be looking at theorems of ISigma_0 that
are not theorems of IE_1, and then classify their status over IE_1 as the
base theory.
CAUTION: It is known that IE_1 proves more than IE_0, but it is not known
if IE_1 is equivalent to ISigma_0, although it is known that if the
polynomial time hierarchy does not collapse then IE_1 is weaker than
ISigma_0, and in fact the IE_i hierarchy does not collapse.
I think this might lead to some very interesting questions. Already IE_1 is
a pretty powerful fragment of ISigma_0. It proves the existence of gcd's
and lcm's, has no recursive nonstandard models, etc. Just what number
theory can be proved in IE_1 is an interesting question.
More generally, finding a good n for which various fundamental number
theory can be proved in IE_n is an interesting project. One could hope to
find the least n under some assumption that these systems don't collapse,
which I gather is an open question.
In complexity theory, one dodges the fundamental open question of whether
things collapse, and still get computational completeness at levels. The
question is to what extent this can be done here for finite reverse
mathematics.
However, the fact that the IE_i don't appear to be finitely axiomatizable
seems to be a problem. Perhaps one has to subdivide each IE_i into
subsclasses by counting the length of quantifier blocks and the degree of
the single polynomial used in the matrix.
There is another way of getting around the perhaps not finitely
axiomatizable issue in the context of arithmetic. And that is to introduce
variables over tuples of integers and talk directly about polynomials with
integer coefficients. There are a lot of possibilities here. Of course, it
would be more striking not to have to do this.
Now suppose that sets are used. We can start with the base theory
1. x+0 = x.
2. x+Sy = S(x+y).
3. x*0 = 0.
4. x*Sy = x*y + x.
5. Sx not= 0.
6. Sx = Sy implies x = y.
7. not(x < 0).
8. x < Sy iff (x < y or x = y).
9. Finiteness. (therexists x)(forall y)(y in A implies y < x).
10. Every nonempty finite set has a least element.
11. Open comprehension. (therexists A)(forall x)(x in A iff phi), where phi
is quantifier free and A is not in phi.
This is conservative over IE_0. If we allow phi to be bounded existential,
even with at most two quantifiers, then we get all of FCA because we get
closure under addition and subtraction and multiplication of sets. This is
strong enough to derive FCA even in the context of nonnegative integers,
not just in the context of integers.
So here we have a limited window of opportunity for a kind of finite
reverse mathematics. We could look at closure conditions on the finite sets
of natural numbers, and determine what kind of bounded comprehension those
statements are equivalent to over the above base theory.
Still, there are many unexplored ways where a finite reverse mathematics
may emerge if done just right that uses a base theory below FCA and where
lots of striking phenomena appear at or below FCA. I.e., where a large
number of theorems coalesce into a relatively small set of equivalence
classes under provable equivalence. It will need considerable
experimentation and perhaps some serious technical ideas.
4. DIGRESSION: ANTI FINITE REVERSE MATHEMATICS.
Anti (finite) reverse mathematics is simply the subject of showing that
various proposed base theories for (finite) reverse mathematics are
unsuitable. This is done by constructing various finite sets of
mathematical statements from the literature which form independent sets of
sentences over the proposed base theories, in the sense that no one in the
list is derivable from all of the others (or even that no nontrivial
Boolean combination of them can be derived).
This can be particularly convincing if there is an important mathematical
theorem of the form (forall n)(phi(n)) such that there is an infinite set
of sentences of the form phi(n-bar) which is an independent set of
sentences over the proposed base theory.
For example, suppose we took the axioms of discrete ordered rings as the
base theory. Look at the theorem
(for all integers n)(if n is the square of a rational then n is the square
of an integer).
For primes n, this forms an infinite independent set over discrete ordered
rings.
I think that we need a lot more anti reverse mathematics and anti finite
reverse mathematics, in order to clarify the boundary between workable base
theories and nonworkable base theories.
CAUTION: I am convinced that there are some good base theories for reverse
mathematics that are fragments of RCA_0. I am not as sure that there are
any good base theories for finite reverse mathematics that are fragments of
FCA.
5. FINITE POWER SET.
A proposed principal theory beyond the proposed base theory FCA is FPS,
given as follows.
1. FCA.
2. Finite power set. For every n there exists a finite binary relation
whose cross sections include every subset of [0,n].
A convenient consequence of this theory is bounded induction. Recall that
FCA uses strictly bounded induction; i.e., where all quantifiers are over
integers, and are bounded to terms of either sort, and of course free
variables are allowed of either sort.
In bounded induction, set quantifiers are allowed, but they must be
restricted to the subsets of some set. Or equivalently, they can be written
in the form
(forall x containedin [0,n])...
This system is equivalent to the two systems in section 1 in the
appropriate sense, and so is equivalent to ISigma_0(exp) = EFA in the
appropriate sense.
There are plenty of nice mathematical statements that are equivalent to FPS
over FCA; this follows the pattern of reverse mathematics. E.g.,
a. Every finite set of positive natural numbers has a positive common
multiple (or least positive common multiple).
b. Finite Ramsey theorem for 3-tuples with 2 colors. I.e., if n >> k then
any coloring of the unordered 3-tuples from [0,n] with 3 colors has a
monochromatic set of cardinality k.
c. Finite Ramsey theorem for 2-tuples with k colors. I.e., if n >> k then
any coloring of the unordered 2-tuples from [0,n] with k colors has a
monochromatic set of cardinality 3.
I don't know the status of the finite Ramsey theorem for 2-tuples with 2
colors (asking for a homogenous set of cardinality k) over FCA.
6. FINITE ITERATED POWER SET.
Another proposed principal theory beyond FPS is the system FIPS given as
follows.
1. FCA.
2. Finite iterated power set. For every k,n there exists a sequence
x_0,...,x_n of nonnegative integers of length n, where x_0 = k and for each
0 < i < n, there is a binary relation on [0,x_i+1] where every subset of
[0,x_i] is a cross section of that relation.
There are nice mathematical statements that are equivalent to FIPS over
FCA. E.g., the full finite Ramsey theorem.
7. STRONGER SYSTEMS.
Standard recursive defining equations for various natural functions,
including exponentiation and superexponentiation, can be interpreted as
Turing machine instructions for computing a function. The corresponding
axiom asserts that the computation is well defined - i.e., has a numerical
code - and halts at all inputs.
In this sense, we can define the theories FCA + exp, FCA + superexp, and we
can prove that these systems are equivallent to FPS and FIPS.
We also take a standard version of the Ackerman hierarchy, say unary
functions A_1,A_2,..., starting with A_1 = doubling, and define each FCA +
A_i in the obvious way. And we take a version of the binary Ackerman
function A(n,m), and form the system FCA + A.
We can carry out finite reverse mathematics for genuine strictly
mathematical theorems of finite mathematics in the same way that it is done
in reverse mathematics (see Simpson's book), by employing coding.
The coding of finite mathematical statements is much more straightforward
and much less problematic than it is for reverse mathematics, where, e.g.,
various kinds of subsets of complete separable metric spaces have to be
considered. There are even issues there about real numbers and sequences of
real numbers. They are appropriately coded in Simpson's book, but there are
still delicate issues as to just why, and what alternatives look like.
But here, it is comparatively unproblematic. I.e., sequences are coded as
finite functions, finite functions of several variables are coded as finite
sets of finite sequences, ordered pairs of integers are coded using the
quadratic pairing function, finite sets of finite sets are coded as finite
sets, etcetera.
THEOREM. The following statement is provably equivalent to FCA + A over
FCA. Let k >= 1 and x in Z+k. In every sufficiently long walk w in Z+k
starting at x there is a term w_i which points outward to a later term w_j
where w_j is at least twice as far as w_i from the origin.
See posting #34.
WIth some of the strong Pi-0-2 sentences, it is awkward and technical to
write down a defining equation. But with a little bit of care one can show
the following kind of result, which we just state for any of my finite
forms of Kruskal's theorem just to give an idea. Call them generically FKT.
THEOREM. FKT is equivalent to the 1-consistency of Pi-1-2-BI_0 over FCA.
Of course, if we are embarked on some sort of computationally sensitive
project - not finite reverse mathematics in the sense meant here - then we
may view these codings as problematic, or even outright inappropriate. But
that is another matter.
8. ELIMINATION OF CODING: SECTION 1 TREATMENT.
Even though for the purposes of the development of finite reverse
mathematics along the general lines of reverse mathematics in Simpson's
book, there are no problematic coding issues to worry about, we still would
like to also have a coding free development. This is particularly needed if
we want to carry out what we did in section 1 in order to show that high
proof theoretic strength exists among the unimpeachably mathematical.
For this purpose, we need a base theory that has more primitives than the
Section 1 systems, and is still a conservative extension of them, and above
all, is still made up of unimpeachable mathematical statements.
We will carry this out in a minimalistic manner for three examples of
theorems of relatively high strength.
a. The block subsequence theorem of postings #19 and #21.
b. A version of the walk theorem cited in section 7 above.
c. The 1998 finite form of Kruskal's theorem in postings #22 and #27.
d. Monotone shift theorem.
e. Paris/Harrington theorem.
Monotone shift theorem says the following.
Let n >> k,r and F:[0,n]^k into [0,n]^r. There exists 0 <= x_1 < ... <
x_k+1 <= n such that F(x_1,...,x_k) <= F(x_2,...,x_k+1).
Here <= means <= in each of the r coordinates. This has strength PA = Peano
Arithmetic like e.
But not in this posting. This is long enough. In a later posting.
9. INTERMEDIATE SYSTEMS.
Actually, there is a need for intermediate systems, especially between FCA
and FPS. This makes sense in light of the intense study in the formal
arithmetic community of systems between ISigma_0 and ISigma_0(exp).
In particular, FCA does not prove the pigeonhole principle "any one-one
function on an interval into itself is onto." This follows from work of
Ajtai, The Complexity of the Pigeonhole Principle, 29th Annual Symposium on
Foundations of Computer Science, 1988, 346-358.
Woods proved that there are infinitely many primes from the pigeonhole
principle. In Paris, Wilkie, Woods JSL 1988, there is a proof that there
are infinitely many primes using the existence of n^log(n), representing
yet another extension of FCA properly contained in FPS.
In particular, the status of "there are infinitely many primes" and "there
is a prime between every n and 2n" are open.
So there is a real question of whether there is an untameable mess between
FCA and FPS (for strictly mathematical theorems) from the finite reverse
mathematics point of view. We don't know yet.
**********
This is the 75th in a series of 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
16:Logical Equations, etc. 4/17/98 1:25PM
16':Errata 4/28/98 10:28AM
17:Very Strong Borel statements 4/26/98 8:06PM
18:Binary Functions and Large Cardinals 4/30/98 12:03PM
19:Long Sequences 7/31/98 9:42AM
20:Proof Theoretic Degrees 8/2/98 9:37PM
21:Long Sequences/Update 10/13/98 3:18AM
22:Finite Trees/Impredicativity 10/20/98 10:13AM
23:Q-Systems and Proof Theoretic Ordinals 11/6/98 3:01AM
24:Predicatively Unfeasible Integers 11/10/98 10:44PM
25:Long Walks 11/16/98 7:05AM
26:Optimized functions/Large Cardinals 1/13/99 12:53PM
27:Finite Trees/Impredicativity:Sketches 1/13/99 12:54PM
28:Optimized Functions/Large Cardinals:more 1/27/99 4:37AM
28':Restatement 1/28/99 5:49AM
29:Large Cardinals/where are we? I 2/22/99 6:11AM
30:Large Cardinals/where are we? II 2/23/99 6:15AM
31:First Free Sets/Large Cardinals 2/27/99 1:43AM
32:Greedy Constructions/Large Cardinals 3/2/99 11:21PM
33:A Variant 3/4/99 1:52PM
34:Walks in N^k 3/7/99 1:43PM
35:Special AE Sentences 3/18/99 4:56AM
35':Restatement 3/21/99 2:20PM
36:Adjacent Ramsey Theory 3/23/99 1:00AM
37:Adjacent Ramsey Theory/more 5:45AM 3/25/99
38:Existential Properties of Numerical Functions 3/26/99 2:21PM
39:Large Cardinals/synthesis 4/7/99 11:43AM
40:Enormous Integers in Algebraic Geometry 5/17/99 11:07AM
41:Strong Philosophical Indiscernibles
42:Mythical Trees 5/25/99 5:11PM
43:More Enormous Integers/AlgGeom 5/25/99 6:00PM
44:Indiscernible Primes 5/27/99 12:53 PM
45:Result #1/Program A 7/14/99 11:07AM
46:Tamism 7/14/99 11:25AM
47:Subalgebras/Reverse Math 7/14/99 11:36AM
48:Continuous Embeddings/Reverse Mathematics 7/15/99 12:24PM
49:Ulm Theory/Reverse Mathematics 7/17/99 3:21PM
50:Enormous Integers/Number Theory 7/17/99 11:39PN
51:Enormous Integers/Plane Geometry 7/18/99 3:16PM
52:Cardinals and Cones 7/18/99 3:33PM
53:Free Sets/Reverse Math 7/19/99 2:11PM
54:Recursion Theory/Dynamics 7/22/99 9:28PM
55:Term Rewriting/Proof Theory 8/27/99 3:00PM
56:Consistency of Algebra/Geometry 8/27/99 3:01PM
57:Fixpoints/Summation/Large Cardinals 9/10/99 3:47AM
57':Restatement 9/11/99 7:06AM
58:Program A/Conjectures 9/12/99 1:03AM
59:Restricted summation:Pi-0-1 sentences 9/17/99 10:41AM
60:Program A/Results 9/17/99 1:32PM
61:Finitist proofs of conservation 9/29/99 11:52AM
62:Approximate fixed points revisited 10/11/99 1:35AM
63:Disjoint Covers/Large Cardinals 10/11/99 1:36AM
64:Finite Posets/Large Cardinals 10/11/99 1:37AM
65:Simplicity of Axioms/Conjectures 10/19/99 9:54AM
66:PA/an approach 10/21/99 8:02PM
67:Nested Min Recursion/Large Cardinals 10/25/99 8:00AM
68:Bad to Worse/Conjectures 10/28/99 10:00PM
69:Baby Real Analysis 11/1/99 6:59AM
70:Efficient Formulas and Schemes 11/1/99 1:46PM
71:Ackerman/Algebraic Geometry/1 12/10/99 1:52PM
72:New finite forms/large cardinals 12/12/99 6:11AM
73:Hilbert's program wide open? 12/20/99 8:28PM
74:Reverse arithmetic beginnings 8:33AM 12/22/99
More information about the FOM
mailing list