Axiomatizing Provable <Emphasis Type="Italic">n</Emphasis>-Provability

The set of all formulas whose n-provability in a given arithmetical theory S is provable in another arithmetical theory T is a recursively enumerable extension of S. We prove that such extensions can be naturally axiomatized in terms of transfinite progressions of iterated local reflection schemata over S. Specifically, the set of all provably 1-provable sentences in Peano arithmetic PA can be axiomatized by an ε₀-times iterated local reflection schema over PA. The resulting characterizations provide additional information on the proof-theoretic strength of these theories and on the complexity of their axiomatization.     

Theories and Theories of Truth

Formal theories, as in logic and mathematics, are sets of sentences closed under logical consequence. Philosophical theories, like scientific theories, are often far less formal. There are many axiomatic theories of the truth predicate for certain formal languages; on analogy with these, some philosophers (most notably Paul Horwich) have proposed axiomatic theories of the property of truth. Though in many ways similar to logical theories, axiomatic theories of truth must be different in several nontrivial ways. I explore what an axiomatic theory of truth would look like. Because Horwich’s is the most prominent, I examine his theory and argue that it fails as a theory of truth. Such a theory is adequate if, given a suitable base theory, every fact about truth is a consequence of the axioms of the theory. I show, using an argument analogous to Gödel’s incompleteness proofs, that no axiomatic theory of truth could ever be adequate. I also argue that a certain class of generalizations cannot be consequences of the theory.     

Finite axiomatizability of local set theory

The need for modifying axiomatic set theories was caused, in particular, by the development of category theory. The ZF and NBG axiomatic theories turned out to be unsuitable for defining the notion of a model of category theory. The point is that there are constructions such as the category of categories in naïve category theory, while constructions like the set of sets are strongly restricted in the ZF and NBG axiomatic theories. Thus, it was required, on the one hand, to restrict constructions similar to the category of categories and, on the other hand, adapt axiomatic set theory in order to give a definition of a category which survives restricted construction similar to the category of categories. This task was accomplished by promptly inventing the axiom of universality (AU) asserting that each set is an element of a universal set closed under all NBG constructions. Unfortunately, in the theories ZF + AU and NBG + AU, there are toomany universal sets (as many as the number of all ordinals), whereas to solve the problem stated above, a countable collection of universal sets would suffice. For this reason, in 2005, the first-named author introduced local-minimal set theory, which preserves the axiom AU of universality and has an at most countable collection of universal sets. This was achieved at the expense of rejecting the global replacement axiom and using the local replacement axiom for each universal class instead. Local-minimal set theory has 14 axioms and one axiom scheme (of comprehension). It is shown that this axiom scheme can be replaced by finitely many axioms that are special cases of the comprehension scheme. The proof follows Bernays’ scheme with significant modifications required by the presence of the restricted predicativity condition on the formula in the comprehension axiom scheme.     

A feasible theory of truth over combinatory algebra

We define an applicative theory of truth _TPT${\mathsf{T}}_{\mathsf{PT}}$ which proves totality exactly for the polynomial time computable functions. _TPT${\mathsf{T}}_{\mathsf{PT}}$ has natural and simple axioms since nearly all its truth axioms are standard for truth theories over an applicative framework. The only exception is the axiom dealing with the word predicate. The truth predicate can only reflect elementhood in the words for terms that have smaller length than a given word. This makes it possible to achieve the very low proof-theoretic strength. Truth induction can be allowed without any constraints. For these reasons the system _TPT${\mathsf{T}}_{\mathsf{PT}}$ has the high expressive power one expects from truth theories. It allows embeddings of feasible systems of explicit mathematics and bounded arithmetic.     

A note on the theory of positive induction, {{\rm ID}^*_1}

The article shows a simple way of calibrating the strength of the theory of positive induction, ID^*₁{{\rm ID}^{*}_{1}} . Crucially the proof exploits the equivalence of S¹₁{\Sigma^{1}_{1}} dependent choice and ω-model reflection for P¹₂{\Pi^{1}_{2}} formulae over ACA ₀. Unbeknown to the authors, D. Probst had already determined the proof-theoretic strength of ID^*₁{{\rm ID}^{*}_{1}} in Probst, J Symb Log, 71, 721–746, 2006.     

The strength of Martin-Löf type theory with a superuniverse. Part I

Universes of types were introduced into constructive type theory by Martin-L?f [12]. The idea of forming universes in type theory is to introduce a universe as a set closed under a certain specified ensemble of set constructors, say . The universe then “reflects”. This is the first part of a paper which addresses the exact logical strength of a particular such universe construction, the so-called superuniverse due to Palmgren (cf. [16, 18, 19]). It is proved that Martin-L?f type theory with a superuniverse, termed MLS, is a system whose proof-theoretic ordinal resides strictly above the Feferman-Schütte ordinal but well below the Bachmann-Howard ordinal. Not many theories of strength between and the Bachmann-Howard ordinal have arisen. MLS provides a natural example for such a theory. Received: 14 October 1997     

The strength of some Martin-Löf type theories

One objective of this paper is the determination of the proof-theoretic strength of Martin-Löf's type theory with a universe and the type of well-founded trees. It is shown that this type system comprehends the consistency of a rather strong classical subsystem of second order arithmetic, namely the one with ₂ ¹ comprehension and bar induction. As Martin-Löf intended to formulate a system of constructive (intuitionistic) mathematics that has a sound philosophical basis, this yields a constructive consistency proof of a strong classical theory. Also the proof-theoretic strength of other inductive types like Aczel's type of iterative sets is investigated in various contexts.Further, we study metamathematical relations between type theories and other frameworks for formalizing constructive mathematics, e.g. Aczel's set theories and theories of operations and classes as developed by Feferman.The second author would like to thank the National Science Foundation of the USA for support by grant DMS-9203443This article was processed by the author using the LATEX style filepljour1 from Spinger-Verlag.     

Some axioms for constructive analysis

This note explores the common core of constructive, intuitionistic, recursive and classical analysis from an axiomatic standpoint. In addition to clarifying the relation between Kleene’s and Troelstra’s minimal formal theories of numbers and number-theoretic sequences, we propose some modified choice principles and other function existence axioms which may be of use in reverse constructive analysis. Specifically, we consider the function comprehension principles assumed by the two minimal theories EL and M, introduce an axiom schema CF_d asserting that every decidable property of numbers has a characteristic function, and use it to describe a precise relationship between the minimal theories. We show that the axiom schema AC₀₀ of countable choice can be decomposed into a monotone choice schema AC ₀₀ ^m (which guarantees that every Cauchy sequence has a modulus) and a bounded choice schema BC₀₀. We relate various (classically correct) axiom schemas of continuous choice to versions of the bar and fan theorems, suggest a constructive choice schema AC_1/2,0 (which incidentally guarantees that every continuous function has a modulus of continuity), and observe a constructive equivalence between restricted versions of the fan theorem and correspondingly restricted bounding axioms ${AB_{1/2,0}^{2^{\mathbb{N}}}}$ . We also introduce a version WKL!! of Weak K?nig’s Lemma with uniqueness which is intermediate in strength between WKL and the decidable fan theorem FT_d.     

Universes in metapredicative analysis

 In this paper we introduce theories of universes in analysis. We discuss a non-uniform, a uniform and a minimal variant. An analysis of the proof-theoretic bounds of these systems is given, using only methods of predicative proof-theory. It turns out that all introduced theories are of proof-theoretic strength between Γ₀ and ϕ1ɛ₀0. Received: 24 November 2000 / Revised Version: 14 June 2002 Published online: 10 October 2002 This paper is a part of the author's Ph.D. dissertation     

The strength of Martin-Löf type theory with a superuniverse. Part II

Universes of types were introduced into constructive type theory by Martin-L?f [3]. The idea of forming universes in type theory is to introduce a universe as a set closed under a certain specified ensemble of set constructors, say ?. The universe then “reflects”?. This is the second part of a paper which addresses the exact logical strength of a particular such universe construction, the so-called superuniverse due to Palmgren (cf.[4–6]). It is proved that Martin-L?f type theory with a superuniverse, termed MLS, is a system whose proof-theoretic ordinal resides strictly above the Feferman-Schütte ordinal Γ₀ but well below the Bachmann-Howard ordinal. Not many theories of strength between Γ₀ and the Bachmann-Howard ordinal have arisen. MLS provides a natural example for such a theory. In this second part of the paper the concern is with the with upper bounds. Received: 8 December 1998 / Published online: 21 March 2001     

The metamathematics of scattered linear orderings

Pursuing the proof-theoretic program of Friedman and Simpson, we begin the study of the metamathematics of countable linear orderings by proving two main results. Over the weak base system consisting of arithmetic comprehension, II ₁ ¹ -CA₀ is equivalent to Hausdorff's theorem concerning the canonical decomposition of countable linear orderings into a sum over a dense or singleton set of scattered linear orderings. Over the same base system, ATR₀ is equivalent to a version of the Continuum Hypothesis for linear orderings, which states that every countable linear ordering either has countably many or continuum many Dedekind cuts.Research partially supported by NSF grant # DCR-8606165. AMS Subject Classification 03F35, 03F15, 03D55     

Reverse Mathematics and parameter-free Transfer

Recently, conservative extensions of Peano and Heyting arithmetic in the spirit of Nelson's axiomatic approach to Nonstandard Analysis, have been proposed. In this paper, we study the Transfer axiom of Nonstandard Analysis restricted to formulas without parameters. Based on this axiom, we formulate a base theory for the Reverse Mathematics of Nonstandard Analysis and prove some natural reversals, and show that most of these equivalences do not hold in the absence of parameter-free Transfer.     

Smoke and mirrors: Combinatorial properties of small cardinals equiconsistent with huge cardinals

Since the work of Godel and Cohen many questions in infinite combinatorics have been shown to be independent of the usual axioms for mathematics, Zermelo Frankel Set Theory with the Axiom of Choice (ZFC). Attempts to strengthen the axioms to settle these problems have converged on a system of principles collectively known as Large Cardinal Axioms.These principles are linearly ordered in terms of consistency strength. As far as is currently known, all natural independent combinatorial statements are equiconsistent with some large cardinal axiom. The standard techniques for showing this use forcing in one direction and inner model theory in the other direction.The conspicuous open problems that remain are suspected to involve combinatorial principles much stronger than the large cardinals for which there is a current fine-structural inner model theory for.The main results in this paper show that many standard constructions give objects with combinatorial properties that are, in turn, strong enough to show the existence of models with large cardinals are larger than any cardinal for which there is a standard inner model theory.     

Fragments of arithmetic

We establish by elementary proof-theoretic means the conservativeness of two subsystems of analysis over primitive recursive arithmetic. The one subsystem was introduced by Friedman [6], the other is a strengthened version of a theory of Minc [14]; each has been shown to be of considerable interest for both mathematical practice and metamathematical investigations. The foundational significance of such conservation results is clear: they provide a direct finitist justification of the part of mathematical practice formalizable in these subsystems.The results are generalized to relate a hierarchy of subsystems, all contained in the theory of arithmetic properties, to a corresponding hierarchy of fragments of arithmetic. The proof theoretic tools employed there are used to re-establish in a uniform, elementary way relationships between various fragments of arithmetic due to Parsons, Paris and Kirby, and Friedman.     

Fusion and large cardinal preservation

In this paper we introduce some fusion properties of forcing notions which guarantee that an iteration with supports of size ?κ   not only does not collapse κ⁺${\kappa }^{+}$ but also preserves the strength of κ (after a suitable preparatory forcing). This provides a general theory covering the known cases of tree iterations which preserve large cardinals (cf. Dobrinen and Friedman (2010) [3], Friedman and Halilovi? (2011) [5], Friedman and Honzik (2008) [6], Friedman and Magidor (2009) [8], Friedman and Zdomskyy (2010) [10], Honzik (2010) [12]).     

Two axiomatic approaches to decision making using possibility theory

This paper proposes a utility theory for decision making under uncertainty that is described by possibility theory. We show that our approach is a natural generalization of the two axiomatic systems that correspond to pessimistic and optimistic decision criteria proposed by Dubois et al. The generalization is achieved by removing axioms that are supposed to reflect attitudes toward uncertainty, namely, pessimism and optimism. In their place we adopt an axiom that imposes an order on a class of canonical lotteries that realize either in the best or in the worst prize. We prove an expected utility theorem for the generalized axiomatic system based on the newly introduced concept of binary utility.     

The Wholeness Axioms and V=HOD

If the Wholeness Axiom wa is itself consistent, then it is consistent with v=hod. A consequence of the proof is that the various Wholeness Axioms are not all equivalent. Additionally, the theory zfc+wa is finitely axiomatizable. Received: 16 February 1999 / Revised version: 1 June 1999     

Taylor's theorem for a function of several variablesClassroom notes

In this note the measure problem for the Lebesgue measure is discussed in terms of metric space theory. It is illuminated that under the axiom of choice most of the subsets of [0, 1) with positive outer measure are non‐Lebesgue measurable. This fact is adequate to emphasize the significance of Lebesgue measurability as well as the essentiality of the axiom of choice.     

Theories in Classical Propositional Logic and the Converse of Substitution

We study theories based on the classical propositional logic. As follows from the Sushko lemma, for any classical propositional theory T and any substitution ε (where formulas stand in place of propositional variables), the set ε−1(T) is also a classical propositional theory. In this paper, we strengthen this assertion, namely, we prove that for any consistent finitely axiomatizable classical propositional theory T there exists a substitution e such that T is the inverse image of the set of all tautologies under ε. We propose an algorithm for constructing such a substitution for a given axiom of the theory.     

Sequential topological conditions in ℝ in the absence of the axiom of choice

It is known that – assuming the axiom of choice – for subsets A of ? the following hold: (a) A is compact iff it is sequentially compact, (b) A is complete iff it is closed in ?, (c) ? is a sequential space. We will show that these assertions are not provable in the absence of the axiom of choice, and that they are equivalent to each