We address the general problem of determining the validity of boolean combinations of equalities and inequalities between real-valued expressions. In particular, we consider methods of establishing such assertions using only restricted forms of distributivity. At the same time, we explore ways in which “local'’ decision or heuristic procedures for fragments of the theory of the reals can be amalgamated into global ones. Let $Tadd[QQ]$ be the first-order theory of the real numbers in the language with symbols $0, 1, +, -.
We argue that the language of Zermelo Fraenkel set theory with definitions and partial functions provides the most promising bedrock semantics for communicating and sharing mathematical knowledge. We then describe a syntactic sugaring of that language that provides a way of writing remarkably readable assertions without straying far from the set-theoretic semantics. We illustrate with some examples of formalized textbook definitions from elementary set theory and point-set topology. We also present statistics concerning the complexity of these definitions, under various complexity (...) measures. (shrink)
ENTIRE BOOK, SINGLE FILE. BOOLEAN RELATION THEORY AND THE INCOMPLETENESS PHENOMENA. 10/30/07 version. Same as 10/01/07 version with Preface added. 568 pages without Appendix B. See above for Appendix B by Francoise Point.
We address the general problem of determining the validity of boolean combinations of equalities and inequalities between real-valued expressions. In particular, we consider methods of establishing such assertions using only restricted forms of distributivity. At the same time, we explore ways in which “local” decision or heuristic procedures for fragments of the theory of the reals can be amalgamated into global ones.
In the Foundational Life, philosophy is commonly used as a method for choosing and analyzing fundamental concepts, and mathematics is commonly used for rigorous development. The mathematics informs the philosophy and the philosophy informs the mathematics.
Here we take the view that LPC(=) is applicable to structures whose domain is too large to be a set. This is not just a matter of class theory versus set theory, although it can be interpreted as such, and this interpretation is discussed briefly at the end.
Since then we have been engaged in the development of such results of greater relevance to mathematical practice. In January, 1997 we presented some new results of this kind involving what we call “jump free” classes of finite functions. This Jump Free Theorem is treated in section 2.
Let k ≥ 2 and f:Nk Æ [1,k] and n ≥ 1 be such that there is no x1 < ... < xk+1 £ n such that f(x1,...,xk) = f(x1,...,xk+1). Then we want to find g:Nk+1 Æ [1,3] such that there is no x1 < ... < xk+2 £ n such that g(x1,...,xk+1) = g(x2,...,xk+2). This reducees adjacent Ramsey in k dimensions with k colors to adjacent Ramsey in k+1 dimensions with 3 colors.
The equation P = NP concerns algorithms for deciding membership in sets. The consensus is that P ≠ NP, although some prominent experts guess otherwise.
We show the algorithmic unsolvability of a number of decision procedures in ordinary two dimensional Euclidean geometry, involving lines and integer points. We also consider formulations involving integral domains of characteristic 0, and ordered rings. The main tool is the solution to Hilbert's Tenth Problem. The limited number of facts used from recursion theory are isolated at the beginning.
We begin by presenting the language L(N,℘N,℘℘N). This is the standard language for presenting third order sentences, using its intended interpretation.
It has been accepted since the early part of the Century that there is no problem formalizing mathematics in standard formal systems of axiomatic set theory. Most people feel that they know as much as they ever want to know about how one can reduce natural numbers, integers, rationals, reals, and complex numbers to sets, and prove all of their basic properties. Furthermore, that this can continue through more and more complicated material, and that there is never a real problem.
It turns out, time and time again, in order to make serious progress in f.o.m., we need to take actual reasoning and actual development into account at precisely the proper level. If we take these into account too much, then we are faced with information that is just too difficult to create an exact science around - at least at a given state of development of f.o.m. And if we take these into account too little, our findings will not have (...) the relevance to mathematical practice that could be achieved. (shrink)
This topic has been discussed earlier on the FOM email list in various guises. The common theme is: big numbers and long sequences associated with mathematical objects. See..
Russell’s way out of his paradox via the impredicative theory of types has roughly the same logical power as Zermelo set theory - which supplanted it as a far more flexible and workable axiomatic foundation for mathematics. We discuss some new formalisms that are conceptually close to Russell, yet simpler, and have the same logical power as higher set theory - as represented by the far more powerful Zermelo-Frankel set theory and beyond. END.
To prove this, we fix P(x) to be any polynomial of degree ≥ 1 with a positive and negative value. We define a critical interval to be any nonempty open interval on which P is strictly monotone and where P is not strictly monotone on any larger open interval. Here an open interval may not have endpoints in F, and may be infinite on the left or right or both sides. Obviously, the critical intervals are pairwise disjoint.
The use of x[y,z,w] rather than the more usual y Πx has many advantages for this work. One of them is that we have found a convenient way to eliminate any need for axiom schemes. All axioms considered are single sentences with clear meaning. (In one case only, the axiom is a conjunction of a manageable finite number of sentences).
C. To what extent, and in what sense, is the natural hierarchy of logical strengths rep resented by familiar systems ranging from exponential function arithmetic to ZF + j:V Æ V robust?
We have been particularly interested in the demonstrable unremovability of machinery, which is a theme that can be pursued systematically starting at the most elementary level - the use of binary notation to represent integers; the use of rational numbers to solve linear equations; the use of real and complex numbers to solve polynomial equations; and the use of transcendental functions to solve differential equations.
Let R Õ [1,n]3k ¥ [1,n]k. We define R = {y Œ [1,n]k:($xŒA3)(R(x,y))}. We say that R is strictly dominating if and only if for all x,yŒ[1,n]k, if R(x,y) then max(x) < max(y).
This is widely accepted, inside and outside philosophy, but one can spend an entire career clarifying, justifying, and amplifying on this statement. Certainly a graduate student career.
This distinction between logic and mathematics is subject to various criticisms and can be given various defenses. Nevertheless, the division seems natural enough and is commonly adopted in presentations of the standard foundations for mathematics.
We say that R is strictly dominating if and only if for all x,yŒ[1,n], if R(x,y) then max(x) 3k ¥ [1,n], there exists A Õ [1,n] such that R = A. Furthermore, A Õ [1,n] is unique.
i. Proofless text is based on a variant of ZFC with free logic. Here variables always denote, but not all terms denote. If a term denotes, then all subterms must denote. The sets are all in the usual extensional cumulative hierarchy of sets. There are no urelements.
We axiomatize EFA in strictly mathematical terms, involving only the ring operations, without extending the language by either exponentiation, finite sets of integers, or polynomials.
A lot of the well known impact of the Gödel phenomena is in the form of painful messages telling us that certain major mathematical programs cannot be completed as intended. This aspect of Gödel – the delivery of bad news –is not welcomed, and defensive measures are now in place.
The kind of unknowability I will discuss concerns the count of certain natural finite sets of objects. Even the situation with regard to our present strong formal systems is rather unclear. One can just profitably focus on that, putting aside issues of general unknowability.
The subtle, almost ineffable, and ineffable cardinals were introduced in an unpublished 1971 manuscript of R. Jensen and K. Kunen, and a number of basic facts were proved there. These concepts were extended to that of k-subtle, k-almost ineffable, and k-ineffable cardinals in [Ba75], where a highly developed theory is presented.
We present several selection theorems for Borel relations, involving only Borel sets and functions, all of which can be obtained as consequences of closely related theorems proved in [DSR 96,99,01,01X] involving coanalytic sets. The relevant proofs given there use substantial set theoretic methods, which were also shown to be necessary. We show that none of our Borel consequences can be proved without substantial set theoretic methods. The results are established for Baire space. We give equivalents of some of the main (...) results for the reals. (shrink)
NOTE: This is an expanded version of my lecture at the special session on reverse mathematics, delivered at the Special Session on Reverse Mathematics held at the Atlanta AMS meeting, on January 6, 2005.
Reflection, in the sense of [Fr03a] and [Fr03b], is based on the idea that a category of classes has a subclass that is “similar” to the category. Here we present axiomatizations based on the idea that a category of classes that does not form a class has extensionally different subclasses that are “similar”. We present two such similarity principles, which are shown to interpret and be interpretable in certain set theories with large cardinal axioms.
This paper was referred to in the Introduction in our paper [Fr97a], “The Axiomatization of Set Theory by Separation, Reducibility, and Comprehension.” In [Fr97a], all systems considered used the axiom of Extensionality. This is appropriate in a set theoretic context.
In fact, Godel gave an important model of pure predication, where he showed that restricted comprehension without parameters is valid, but where restricted comprehension with parameters is not (although this invalidity was not established until Cohen). This is the model based on ordinal definability in set theory.
1. Transfer principles from N to On. A. Mahlo cardinals. B. Weakly compact cardinals. C. Ineffable cardinals. D. Ramsey cardinals. E. Ineffably Ramsey cardinals. F. Subtle cardinals. G. From N to (...) 4. Decidability of statements on N. 5. Decidability of statements on shrink)
We now fix A ⊆ Q. We study a fundamental class of digraphs associated with A, which we call the A-digraphs. An A,kdigraph is a digraph (Ak,E), where E is an order invariant subset of A2k in the following sense. For all x,y ∈ A2k, if x,y have the same order type then x ∈ E ↔ y ∈ E.
In mathematics, we back up our discoveries with rigorous deductive proofs. Mathematicians develop a keen instinctive sense of what makes a proof rigorous. In logic, we strive for a *theory* of rigorous proofs.
We say that E is R-sparse if f(Ek) has no interior, for each k 2 N and f : Rk ! R de nable in R. (Throughout, \de nable" means \de nable without parameters".) In this note, we consider the extent to which basic metric and topological properties of subsets of R de nable in (R;E)# are determined by the corresponding properties of subsets of R de nable in (R;E), when R is an o-minimal expansion of (R;<;+;0;1) and E is (...) R-sparse. The precise statement of the main result is a bit complicated, but we can state some special cases now. (shrink)
We give a consistency proof within a weak fragment of arithmetic of elementary algebra and geometry. For this purpose, we use EFA (exponential function arithmetic), and various first order theories of algebraically closed fields and real closed fields.
Here we take the view that LPC(=) is applicable to structures whose domain is too large to be a set. This is not just a matter of class theory versus set theory, although it can be interpreted as such, and this interpretation is discussed briefly at the end.
Here we take the view that LPC(=) is applicable to structures whose domain is too large to be a set. This is not just a matter of class theory versus set theory, although it can be interpreted as such, and this interpretation is discussed briefly at the end.
Mathematical statements arising from program verification are believed to be much easier to deal with than statements coming from serious mathematics. At least this is true for “normal programming”.
I will look forward to your comments before I try to publish in this area. Or alternatively, you and your colleagues in software engineering may in fact stop me from publishing in this area! But I think that there are some merits in having someone in mathematical logic and the foundations of mathematics tackle crucial issues in software engineering from their own perspective, head on, with no fear, discarding all of the talk about their being no magic bullets, etcetera.
The space CS(R) has a unique “Borel structure” in the following sense. Note that there is a natural mapping from R¥ onto CS(R}; namely, taking ranges. We can combine this with any Borel bijection from R onto R¥ in order to get a “preferred” surjection F:R ® CS(R).
We discuss several axiomatizations of set theory in first order predicate calculus with epsilon and a constant symbol W, starting with the simple system K(W) which has a strong equivalence with ZF without Foundation. The other systems correspond to various extensions of ZF by certain large cardinal hypotheses. These axiomatizations are unusually simple and uncluttered, and are highly suggestive of underlying philosophical principles that generate higher set theory.
The Complete Theory of Everything (CTE) is based on certain axioms of indiscernibility. Such axioms of indiscernibility have been given a philosophical justification by Kit Fine. I want to report on an attempt to give strong indiscernibility axioms which might also be subject to such philosophical analysis, and which prove the consistency of set theory; i.e., ZFC or more. In this way, we might obtain a (new kind of) philosophical consistency proof for mathematics.
We present a way out of Russell’s paradox for sets in the form of a direct weakening of the usual inconsistent full comprehension axiom scheme, which, with no additional axioms, interprets ZFC. In fact, the resulting axiomatic theory 1) is a subsystem of ZFC + “there exists arbitrarily large subtle cardinals”, and 2) is mutually interpretable with ZFC + the scheme of subtlety.
The Borel reducibility theory of Polish equivalence relations, at least in its present form, was initiated independently in [FS89] and [HKL90]. There is now an extensive literature on this topic, including fundamental work on the Glimm-Effros dichotomy in [HKL90], on countable Borel equivalence relations in [DJK94], and on Polish group actions in [BK96].
We give a detailed extended abstract reflecting what we know about Boolean relation theory. We follow this by a proof sketch of the main instances of Boolean relation theory, from Mahlo cardinals of finite order, starting at section 19. The proof sketch has been used in lectures.
I. WKL0 is a conservative extension of PRA for ’-0-2 sentences. II. ACA0 is a conservative extension of PA for arithmetic sentences. III. ATR0 is a conservative extension of IR for arithmetic sentences. IV. ’-1-1-CA0 is a conservative extension of ID(
Certainty (and the lack thereof) is a major issue in mathematics and computer science. Mathematicians strongly believe in a special kind of certainty for their theorems.
PREFACE. We present a variety of basic theories involving fundamental concepts of naive thinking, of the sort that were common in "natural philosophy" before the dawn of physical science. The most extreme forms of infinity ever formulated are embodied in the branch of mathematics known as abstract set theory, which forms the accepted foundation for all of mathematics. Each of these theories embodies the most extreme forms of infinity ever formulated, in the following sense. ZFC, and even extensions of ZFC (...) with the so called large cardinal axioms, are mutually interpretable with these theories. This is an extended abstract. Proofs of the claims will appear elsewhere. (shrink)
It has been accepted since the early part of the Century that there is no problem formalizing mathematics in standard formal systems of axiomatic set theory. Most people feel that they know as much as they ever want to know about how one can reduce natural numbers, integers, rationals, reals, and complex numbers to sets, and prove all of their basic properties. Furthermore, that this can continue through more and more complicated material, and that there is never a real problem.
We can look at this model theoretically as follows. By the linearly ordered predicate calculus, we simply mean ordinary predicate calculus with equality and a special binary relation symbol <. It is required that in all interpretations, < be a linear ordering on the domain. Thus we have the usual completeness theorem provided we add the axioms that assert that < is a linear ordering.
An assignment is a function f that assigns subsets of N to some atoms. Then f is extended to f* which sends every formula A of HPC to a subset of S(A).
It is not yet clear just what the most illuminating ways of rigorously stating the Incompleteness Theorems are. This is particularly true of the Second. Also I believe that there are more illuminating proofs of the Second that have yet to be uncovered.
Let j:β → β, where β is an ordinal. Let R ⊆ α x α, where β ≤ α. We define j[R] = {(j(c),j(d)): R(c,d)}. We say that j is a nonidentity function if and only if j is not the..
An ideal in a commutative ring R with unit is a nonempty I Õ R such that for all x,y Œ I, z Œ R, we have x+y and xz Œ I. A set of generators for I is a subset of I such that I is the least ideal containing that subset.
A bi-infinite approximate fixed point of type (n,k) is an approximate fixed point of type (n,k) whose terms are biinfinite; i.e., contain infin-itely many positive and infinitely many negative elements.
We present a range of mathematical theorems whose proofs require unexpectedly strong logical methods, which in some cases go well beyond the usual axioms for mathematics.
Equational Boolean Relation Theory concerns the Boolean equations between sets and their forward images under multivariate functions. We study a particular instance of equational BRT involving two multivariate functions on the natural numbers and three infinite sets of natural numbers. We prove this instance from certain large cardinal axioms going far beyond the usual axioms of mathematics as formalized by ZFC. We show that this particular instance cannot be proved in ZFC, even with the addition of slightly weaker large cardinal (...) axioms, assuming the latter are consistent. (shrink)
This is an immediate conse-quence of a more general combinatorial theorem called Ramsey’s theorem, but it is much simpler to state. We call this adjacent Ramsey theory.
In 1995 we gave a new simple principle of combinatorial set theory and showed that it implies the existence of a nontrivial elementary embedding from a rank into itself, and follows from the existence of a nontrivial elementary embedding from V into M, where M contains the rank at the first fixed point above the critical point. We then gave a “diamondization” of this principle, and proved its relative consistency by means of a standard forcing argument.
The goal is to show that various exotic prefix classes can be "tamed by large cardinals". I.e., every statement in the class is either provable or refutable using presently formulated large cardinals. Some of these exotic prefix classes consist entirely of explicitly P01 sentences.
“Sentential reflection” in the sense of [Fr03] is based on reflecting down from a category of classes. “Elemental sentential reflection” is based on reflecting down from a category of elemental classes. We present various forms of elemental sentential reflection, which are shown to interpret and be interpretable in certain set theories with large cardinal axioms.
We present some formal systems in the language of linearly ordered rings with finite sets whose nonlogical axioms are strictly mathematical, which correspond to polynomially bounded arithmetic. With an additional strictly mathematical axiom, the systems correspond to exponentially bounded arithmetic.
Informal statements of Gödel's Second Incompleteness Theorem, referred to here as Informal Second Incompleteness, are simple and dramatic. However, current versions of Formal Second Incompleteness are complicated and awkward. We present new versions of Formal Second Incompleteness that are simple, and informally imply Informal Second Incompleteness. These results rest on the isolation of simple formal properties shared by consistency statements. Here we do not address any issues concerning proofs of Second Incompleteness.
We introduce insertion domains that support the placement of new, higher, vertices into finite trees. We prove that every nonincreasing insertion domain has an element with simple structural properties in the style of classical Ramsey theory. This result is proved using standard large cardinal axioms that go well beyond the usual axioms for mathematics. We also establish that this result cannot be proved without these large cardinal axioms. We also introduce insertion rules that specify the placement of new, higher, vertices (...) into finite trees. We prove that every insertion rule greedily generates a tree with these same structural properties; and every decreasing insertion rule generates (or admits) a tree with these same structural properties. It is also necessary and sufficient to use the same large cardinals (in the precise sense of Corollary D.25). The results suggest new areas of research in discrete mathematics called "Ramsey tree theory" and "greedy Ramsey theory" which demonstrably require more than the usual axioms for mathematics. (shrink)
Gödel's definitive results and his essays leave us with a rich legacy of philosophical programs that promise to be subject to mathematical treatment. After surveying some of these, we focus attention on the program of circumventing his demonstrated impossibility of a consistency proof for mathematics by means of extramathematical concepts.
Russell’s way out of his paradox via the impre-dicative theory of types has roughly the same logical power as Zermelo set theory - which supplanted it as a far more flexible and workable axiomatic foundation for mathematics. We discuss some new formalisms that are conceptually close to Russell, yet simpler, and have the same logical power as higher set theory - as represented by the far more powerful Zermelo-Frankel set theory and beyond. END.
The notion of interpretation is absolutely fundamental to mathematical logic and the foundations of mathematics. It is also crucial for the foundations and philosophy of science - although here some crucial conditions generally need to be imposed; e.g., “the interpretation leaves the mathematical concepts unchanged”.
STARTLING OBSERVATION. Any two natural theories S,T, known to interpret EFA, are known (with small numbers of exceptions) to have: S is interpretable in T or T is interpretable in S. The exceptions are believed to also have comparability.
Let k be a positive integer. There is a longest finite sequence x1,...,xn in k letters in which no consecutive block xi,...,x2i is a subsequence of any other consecutive block xj,...,x2j. Let n(k) be this longest length. We prove that n(1) = 3, n(2) = 11, and n(3) is incomprehensibly large. We give a lower bound for n(3) in terms of the familiar Ackerman hierarchy. We also give asymptotic upper and lower bounds for n(k). We view n(3) as a particularly (...) elemental description of an incomprehensibly large integer. Related problems involving binary sequences (two letters) are also addressed. We also report on some recent computer explorations of R. Dougherty which we use to raise the lower bound for n(3). (shrink)
This is an introduction to the most primitive form of the new Boolean relation theory, where we work with only one function and one set. We give eight complete classifications. The thin set theorem (along with a slight variant), and the complementation theorem are the only substantial cases that arise in these classifications.
The main powerful method for establishing termination of term rewriting systems was discovered by Nachum Dershowitz through the introduction of certain natural well founded orderings (lexicographic path orderings). This leads to natural decision problems which may be of the highest computational complexity of any decidable problems appearing in a natural established computer science context.
We discuss enormous integers and rates of growth after [PH77]. This breakthrough was based on a variant of the classical finite Ramsey theorem. Since then, examples have been given of greater relevance to a number of standard mathematical and computer science contexts, often involving even more enormous integers and rates of growth.
There are two kinds of such limiting results that must be carefully distinguished. Results of the first kind state the nonexistence of any algorithm for determining whether any statement among a given set of statements is true or false.
Gödel's legacy is still very much in evidence. We will not attempt to properly discuss the full impact of his work and all of the ongoing important research programs that it suggests. This would require a book length manuscript. Indeed, there are several books discussing the Gödel legacy from many points of view, including, for example, (Wang 1987, 1996), (Dawson 2005), and the historically comprehensive five volume set (Gödel 1986-2003).
We show that “every countable algebra with a nonfinitely generated subalgebra has a maximal nonfinitely generated subalgebra” is provably equivalent to ’11-CA0 over..
A number of comparability theorems have been investigated from the viewpoint of reverse mathematics. Among these are various comparability theorems between countable well orderings ([2],[8]), and between closed sets in metric spaces ([3],[5]). Here we investigate the reverse mathematics of a comparability theorem for countable metric spaces, countable linear orderings, and sets of rationals. The previous work on closed sets used a strengthened notion of continuous embedding. The usual weaker notion of continuous embedding is used here. As a byproduct, we (...) sharpen previous results of [3],[5]. (shrink)
The classical Ulm theory provides a complete set of invariants for countable abelian p-groups, and hence also for countable torsion abelian groups. These invariants involve countable ordinals. One can read off many simple structural properties of such groups directly from the Ulm theory. We carry out a reverse mathematics analysis of several such properties. In many cases, we reverse to ATR0, thereby demonstrating a kind of necessary use of Ulm theory.
S. Adams, W. Ambrose, A. Andretta, H. Becker, R. Camerlo, C. Champetier, J.P.R. Christensen, D.E. Cohen, A. Connes. C. Dellacherie, R. Dougherty, R.H. Farrell, F. Feldman, A. Furman, D. Gaboriau, S. Gao, V. Ya. Golodets, P. Hahn, P. de la Harpe, G. Hjorth, S. Jackson, S. Kahane, A.S. Kechris, A. Louveau,, R. Lyons, P.-A. Meyer, C.C. Moore, M.G. Nadkarni, C. Nebbia, A.L.T. Patterson, U. Krengel, A.J. Kuntz, J.-P. Serre, S.D. Sinel'shchikov, T. Slaman, Solecki, R. Spatzier, J. Steel, D. Sullivan, S. (...) Thomas, A. Valette, V.S. Varadarajan, B. Velickovic, B. Weiss, J.D.M. Wright, R.J. Zimmer. (shrink)
An o-minimal structure is any relational structure in any relational type in the first order predicate calculus with equality, where one symbol is reserved to be a dense linear ordering without endpoints, satisfying the following condition: that every first order definable subset of the domain is a finite union of intervals whose endpoints are in the domain or are ±•. First order definability always allows any parameters, unless explicitly indicated otherwise.
oris, 1986, 17-34, Seminarberichte 86, Humboldt University, Berlin, where, with G. Cherlin, we gave a detailed proof of a result of Alexei L. Semenov that the theory of (N, +, 2x) is decidable and admits quantifier elimination in an expansion of the language containing the Presburger..
All axiomatizations in sections 1,2,4-8 are in the language L(Î,W) with just Î and the constant symbol W standing for a Subworld. Think of W as yesterday's world, and think of the quantifiers in the theory as ranging over today's world. The philosophy is that since the universe cannot be completed, every time we reflect on the universe and what we have reflected on previously, we obtain a larger universe.
There are many familiar theorems whose proofs use methods which are in some appropriate sense substantially more "abstract" than its statement. Some particularly well known examples come from the use of complex variables in number theory. Sometimes such abstraction can be removed - for example by the "elementary proof of the prime number theorem" - and sometimes no appropriate removal is known. The interest in removing abstraction typically varies, with no agreed upon criteria for appropriateness. E.g., the removal might sacrifice (...) naturalness or intelligibility, or the result of the removal criticized as being merely a thinly disguised form of the original. (shrink)
For digraphs G, we write V(G) for the set of all vertices of G, and E(G) for the set of all edges of G. A digraph on a set E is a digraph G where V(G) = E.
We present some new decision and comparison problems of unusually high computational complexity. Most of the problems are strictly combinatorial in nature; others involve basic logical notions. Their complexities range from iterated exponential time completeness to (0 time completeness to ((((,0) time completeness to ((((,,0) time completeness. These three ordinals are well known ordinals from proof theory, and their associated com- plexity classes represent new levels of computational complexity for natural decision problems. Proofs will appear in an extended version of (...) this manuscript to be published elsewhere. (shrink)
NOTE: This is an edited version of my lecture at LC ‘06. It differs from my earlier lecture at the Gödel Centenary in Vienna, April 29, 2006 most notably in section 5, where “Finite Graph Theory” is replaced by “Order Calculus”.
We have been particularly interested in the demonstrable unremovability of machinery, which is a theme that can be pursued systematically starting at the most elementary level - the use of binary notation to represent integers; the use of rational numbers to solve linear equations; the use of real and complex numbers to solve polynomial equations; and the use of transcendental functions to solve differential equations.
We can equivalently present this by the recursion equations f1(n) = 2n, fk+1(1) = fk(1), fk+1(n+1) = fk(fk+1(n)), where k,n ≥ 1. We define A(k,n) = fk(n).
It has been accepted since the early part of the Century that there is no problem formalizing mathematics in standard formal systems of axiomatic set theory. Most people feel that they know as much as they ever want to know about how one can reduce natural numbers, integers, rationals, reals, and complex numbers to sets, and prove all of their basic properties. Furthermore, that this can continue through more and more complicated material, and that there is never a real problem.
An extreme kind of logic skeptic claims that "the present formal systems used for the foundations of mathematics are artificially strong, thereby causing unnecessary headaches such as the Gödel incompleteness phenomena". The skeptic continues by claiming that "logician's systems always contain overly general assertions, and/or assertions about overly general notions, that are not used in any significant way in normal mathematics. For example, induction for all statements, or even all statements of certain restricted forms, is far too general - mathematicians (...) only use induction for natural statements that actually arise. If logicians would tailor their formal systems to conform to the naturalness of normal mathematics, then various logical difficulties would disappear, and the story of the foundations of mathematics would look radically different than it does today. In particular, it should be possible to give a convincing model of actual mathematical practice that can be proved to be free of contradiction using methods that lie within what Hilbert had in mind in connection with his program”. Here we present some specific results in the direction of refuting this point of view, and introduce the Strict Reverse Mathematics (SRM) program. (shrink)
In fact, Godel gave an important model of pure predication, where he showed that restricted comprehension without parameters is valid, but where restricted comprehension with parameters is not (although this invalidity was not established until Cohen). This is the model based on ordinal definability in set theory.
Each of these theorems and concepts arose from very specific considerations of great general interest in the foundations of mathematics (f.o.m.). They each serve well defined purposes in f.o.m. Naturally, the preferred way to formulate them for mathe-matical logicians is in terms that are close to their roots in f.o.m.
