This volume is a tribute by his peers, and by younger scholars of the next generation, to Harvey M. Friedman, perhaps the most profound foundationalist since Kurt Godel. Friedman's researches, beginning precociously in his mid-teens, have fundamentally shaped our contemporary understanding of set theory, recursion theory, model theory, proof theory and metamathematics. His achievements in concept formation and theory formulation have also renewed the standard set by Godel and Alfred Tarski for the general intellectual interest and importance (...) of technical work in foundations. Friedman pioneered the now well-established and flourishing field of Reverse Mathematics, whose aim is to calibrate the intrinsic logico-mathematical consistency-strength of all the important theorems of mathematics. He has relentlessly pursued the full extent of the incompleteness phenomena into which Godel provided the first revealing glimpse. The Godel--Friedman program, as it is now deservingly called, seeks to find simple, natural and elegant mathematical statements of a combinatorial nature, that can be proved to be independent of set theory even when extended by powerful large-cardinal existence axioms. (shrink)

Part of the ambiguity lies in the various points of view from which this question might be considered. The crudest di erence lies between the point of view of the working mathematician and that of the logician concerned with the foundations of mathematics. Now some of my fellow mathematical logicians might protest this distinction, since they consider themselves to be just more of those \working mathematicians". Certainly, modern logic has established itself as a very respectable branch of mathematics, and there (...) are quite a few highly technical journals in logic, such as The Journal of Sym-. (shrink)

Let ℜ be an o-minimal expansion of (ℝ, <+) and (φk)k∈ℕ be a sequence of positive real numbers such that limk→+∞f(φk)/φk+1=0 for every f:ℝ→ ℝ definable in ℜ. (Such sequences always exist under some reasonable extra assumptions on ℜ, in particular, if ℜ is exponentially bounded or if the language is countable.) Then (ℜ, (S)) is d-minimal, where S ranges over all subsets of cartesian powers of the range of φ.

We introduce a reducibility preordering between classes of countable structures, each class containing only structures of a given similarity type (which is allowed to vary from class to class). Though we sometimes work in a slightly larger context, we are principally concerned with the case where each class is an invariant Borel class (i.e. the class of all models, with underlying set $= \omega$, of an $L_{\omega_1\omega}$ sentence; from this point of view, the reducibility can be thought of as a (...) (rather weak) sort of $L_{\omega_1\omega}$-interpretability notion). We prove a number of general results about this notion, but our main thrust is to situate various mathematically natural classes with respect to the preordering, most notably classes of algebraic structures such as groups and fields. (shrink)

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)

Two countable well orderings are weakly comparable if there is an order preserving injection of one into the other. We say the well orderings are strongly comparable if the injection is an isomorphism between one ordering and an initial segment of the other. In [5], Friedman announced that the statement “any two countable well orderings are strongly comparable” is equivalent to ATR 0 . Simpson provides a detailed proof of this result in Chapter 5 of [13]. More recently, (...) class='Hi'>Friedman has proved that the statement “any two countable well orderings are weakly comparable” is equivalent to ATR 0 . The main goal of this paper is to give a detailed exposition of this result. (shrink)

We define a class of functions, the descent recursive functions, relative to an arbitrary elementary recursive system of ordinal notations. By means of these functions, we provide a general technique for measuring the proof-theoretic strength of a variety of systems of first-order arithmetic. We characterize the provable well-orderings and provably recursive functions of these systems, and derive various conservation and equiconsistency results.

Based on the relevant logic R, the system R# was proposed as a relevant Peano arithmetic. R# has many nice properties: the most conspicuous theorems of classical Peano arithmetic PA are readily provable therein; it is readily and effectively shown to be nontrivial; it incorporates both intuitionist and classical proof methods. But it is shown here that R# is properly weaker than PA, in the sense that there is a strictly positive theorem QRF of PA which is unprovable in R#. (...) The reason is interesting: if PA is slightly weakened to a subtheory P+, it admits the complex ring C as a model; thus QRF is chosen to be a theorem of PA but false in C. Inasmuch as all strictly positive theorems of R# are already theorems of P+, this nonconservativity result shows that QRF is also a nontheorem of R#. As a consequence, Ackermann's rule γ is inadmissible in R#. Accordingly, an extension of R# which retains its good features is desired. The system R##, got by adding an omega-rule, is such an extension. Central question: is there an effectively axiomatizable system intermediate between R# and R##, which does formalize arithmetic on relevant principles, but also admits γ in a natural way? (shrink)

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”.

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)

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 study the formalization within sybsystems of second-order arithmetic of theorems concerning periodic points in dynamical systems on the real line. We show that Sharkovsky's theorem is provable in WKL0. We show that, with an additional assumption, Sharkovsky's theorem is provable in RCA0. We show that the existence for all n of n-fold iterates of continuous mappings of the closed unit interval into itself is equivalent to the disjunction of Σ02 induction and weak König's lemma.

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.

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).

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)

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.

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)

This is the initial publication on Concept Calculus, which establishes mutual interpretability between formal systems based on informal commonsense concepts and formal systems for mathematics through abstract set theory. Here we work with axioms for "better than" and "much better than", and the Zermelo and Zermelo Frankel axioms for set theory.

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 subtle, almost ineffable, and ineffable cardinals were introduced in an unpublished 1971 manuscript of R. Jensen and K. Kunen. The concepts were extended to that of k-subtle, k-almost ineffable, and k-ineffable cardinals in 1975 by J. Baumgartner. In this paper we give a self contained treatment of the basic facts about this level of the large cardinal hierarchy, which were established by J. Baumgartner. In particular, we give a proof that the k-subtle, k-almost ineffable, and k-ineffable cardinals define three (...) properly intertwined hierarchies with the same limit, lying strictly above “total indescribability” and strictly below “arrowing ω”. The innovation here is presented in Section 2, where we take a distinctly minimalist approach. Here the subtle cardinal hierarchy is characterized by very elementary properties that do not mention closed unbounded or stationary sets. This development culminates in a characterization of the hierarchy by means of a striking universal second-order property of linear orderings. (shrink)

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.

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 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.

We show that “every countable algebra with a nonfinitely generated subalgebra has a maximal nonfinitely generated subalgebra” is provably equivalent to ’11-CA0 over..

We consider properties of sets in an intuitionistic setting corresponding to large cardinals in classical set theory. Adding such ‘large set axioms’ to intuitionistic ZF set theory does not violate well-know metamathematical properties of intuitionistic systems. Moreover, we consider statements in constructive analysis equivalent to the consistency of such ‘large set axioms’.

In a modal system of arithmetic, a theory S has the modal disjunction property if whenever $S \vdash \square\varphi \vee \square\psi$ , either $S \vdash \square\varphi$ or $S \vdash \square\psi. S$ has the modal numerical existence property if whenever $S \vdash \exists x\square\varphi(x)$ , there is some natural number n such that $S \vdash \square\varphi(\mathbf{n})$ . Under certain broadly applicable assumptions, these two properties are equivalent.

We consider a number of statements involving restrictions and extensions of algebras, and derive connections with large cardinal axioms.

by Harvey M. Friedman Department of Mathematics Ohio State University friedman@math.ohio-state.edu www.math.ohio-state.edu/~friedman/ April 5, 1997..

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.

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.

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).

Most of my intellectual efforts have focused around a single general question in the foundations of mathematics (f.o.m.). I became keenly aware of this question as a student at MIT around 40 years ago, and readily adopted it as the principal driving force behind my research.

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)

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.

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].

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.

“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 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.