A Frege proof systemFis any standard system of prepositional calculus, e.g., a Hilbert style system based on finitely many axiom schemes and inference rules. An Extended Frege systemEFis obtained fromFas follows. AnEF-sequence is a sequence of formulas ψ1, …, ψκsuch that eachψiis either an axiom ofF, inferred from previous ψuand ψv by modus ponens or of the formq↔ φ, whereqis an atom occurring neither in φ nor in any of ψ1,…,ψi−1. Suchq↔ φ, is called an extension axiom andqa new extension (...) atom. AnEF-proof is anyEF-sequence whose last formula does not contain any extension atom. In [12], S. A. Cook and R. Reckhow proved that the pigeonhole principlePHPhas a simple polynomial sizeEF-proof and conjectured thatPHPdoes not admit polynomial sizeF-proof. In [5], S. R. Buss refuted this conjecture by furnishing polynomial sizeF-proof forPHP. Since then the important separation problem of polynomial sizeFand polynomial sizeEFhas not shown any progress.In [11], S. A. Cook introduced the systemPV, a free variable equational logic whose provable functional equalities are ‘polynomial time verifiable’ and showed that the metamathematics ofFandEFcan be developed inPVand the soundness ofEFproved inPV. In [3], S. R. Buss introduced the first order systemand showed thatis essentially a conservative extension ofPV. There he also introduced a second order system. (shrink)

A Frege proof systemFis any standard system of prepositional calculus, e.g., a Hilbert style system based on finitely many axiom schemes and inference rules. An Extended Frege systemEFis obtained fromFas follows. AnEF-sequence is a sequence of formulas ψ1, …, ψκsuch that eachψiis either an axiom ofF, inferred from previous ψuand ψv by modus ponens or of the formq↔ φ, whereqis an atom occurring neither in φ nor in any of ψ1,…,ψi−1. Suchq↔ φ, is called an extension axiom andqa new extension (...) atom. AnEF-proof is anyEF-sequence whose last formula does not contain any extension atom. In [12], S. A. Cook and R. Reckhow proved that the pigeonhole principlePHPhas a simple polynomial sizeEF-proof and conjectured thatPHPdoes not admit polynomial sizeF-proof. In [5], S. R. Buss refuted this conjecture by furnishing polynomial sizeF-proof forPHP. Since then the important separation problem of polynomial sizeFand polynomial sizeEFhas not shown any progress.In [11], S. A. Cook introduced the systemPV, a free variable equational logic whose provable functional equalities are ‘polynomial time verifiable’ and showed that the metamathematics ofFandEFcan be developed inPVand the soundness ofEFproved inPV. In [3], S. R. Buss introduced the first order systemand showed thatis essentially a conservative extension ofPV. There he also introduced a second order system. (shrink)

The geometric system of deduction called N-Graphs was introduced by de Oliveira in 2001. The proofs in this system are represented by means of digraphs and, while its derivations are mostly based on Gentzen's sequent calculus, the system gets its inspiration from geometrically based systems, such as the Kneales' tables of development, Statman's proofs-as-graphs, Buss' logical flow graphs, and Girard's proof-nets. Given that all these geometric systems appeal to the classical symmetry between premises and conclusions, providing an intuitionistic version of (...) any of these is an interesting exercise in extending the range of applicability of the geometric system in question. In this article we produce an intuitionistic version of N-Graphs, based on Maehara's LJ' system, as described by Takeuti. Recall that LJ' has multiple conclusions in all but the essential intuitionistic rules, e.g., implication right and negation right. We show soundness and completeness of our intuitionistic N-Graphs with respect to LJ'. We also discuss how we expect to extend this work to a version of N-Graphs corresponding to the intuitionistic logic system FIL (Full Intuitionistic Logic) of de Paiva and Pereira and sketch future developments. (shrink)

G. Genzten’s 1938 proof of the consistency of pure arithmetic was hailed as a success for finitism and constructivism, but his proof requires induction along ordinal notations in Cantor normal form up to the first epsilon number, ε0. This left the task of giving a finitisically acceptable proof of the well-ordering of those ordinal notations, without which Gentzen’s proof could hardly be seen as a success for finitism. In his seminal book Proof Theory G. Takeuti provides such a proof. After (...) a brief philosophical introduction, we provide a reconstruction of Takeuti’s proof including corrections, comments, re-organization and notational adjustments for the sake of clarity. The result is a much longer, but much more tractable proof of the well-ordering of ordinal notations in Cantor normal form less than ε0, that nevertheless follows Takeuti’s strategy closely. We end with some more general comments about that proof strategy and the notion of accessibility more generally. (shrink)

This comprehensive monograph is a cornerstone in the area of mathematical logic and related fields. Focusing on Gentzen-type proof theory, the book presents a detailed overview of creative works by the author and other 20th-century logicians that includes applications of proof theory to logic as well as other areas of mathematics. 1975 edition.

T i 2 = S i +1 2 implies ∑ p i +1 ⊆ Δ p i +1 ⧸poly. S 2 and IΔ 0 ƒ are not finitely axiomatizable. The main tool is a Herbrand-type witnessing theorem for ∃∀∃ П b i -formulas provable in T i 2 where the witnessing functions are □ p i +1.

Kant’s critique/doctrine distinction tracks the difference between a canon for the understanding’s proper use and an organon for its dialectical misuse. The latter reflects the dogmatic use of reason to attain a doctrine of knowledge with no antecedent critique. In the 1790s, Fichte collapses Kant’s distinction and redefines dogmatism. He argues that deriving a canon is essentially dialectical and thus yields an organon: critical idealism is properly a doctrine of science or Wissenschaftslehre. Criticism is furthermore said to refute dogmatism, by (...) which Fichte means Spinozism. Schelling repudiates Fichte’s position in his Philosophical Letters by reviving Kant’s distinction. First, ‘critique’ for Schelling names a canon that is valid for all systems—including Spinozism—and thus favours none—not even the Wissenschaftslehre. Second, Schelling coins ‘dogmaticism’ to refer to what Kant calls ‘dogmatism’: reason’s uncritical claim to doctrine. Hence, he says all systems—even Fichte’s—are susceptible to the ‘enthusiasm’ of mistaking themselves for doctrines or ‘objects of knowledge’, instead of subjectively valid ‘objects of freedom’. I reconstruct Schelling’s argument for reviving Kant’s distinction, while noting two consequences for German idealism. First, if criticism favours no system, a system’s origin cannot be an act of knowledge, e.g., intellectual intuition, but only an act of endorsement. Second, if dogmaticism entails enthusiasm, a system’s goal cannot be absolute knowledge, but only infinite striving. Hence, by retrieving Schelling’s notion of dogmaticism, we can both gain a better understanding of the Letters and register the impact of a core Kantian distinction on the German idealist project. (shrink)

Using set theory in the first part of his book, and proof theory in the second, Gaisi Takeuti gives us two examples of how mathematical logic can be used to obtain results previously derived in less elegant fashion by other mathematical techniques, especially analysis. In Part One, he applies Scott- Solovay's Boolean-valued models of set theory to analysis by means of complete Boolean algebras of projections. In Part Two, he develops classical analysis including complex analysis in Peano's arithmetic, showing that (...) any arithmetical theorem proved in analytic number theory is a theorem in Peano's arithmetic. In doing so, the author applies Gentzen's cut elimination theorem. Although the results of Part One may be regarded as straightforward consequences of the spectral theorem in function analysis, the use of Boolean- valued models makes explicit and precise analogies used by analysts to lift results from ordinary analysis to operators on a Hilbert space. Essentially expository in nature, Part Two yields a general method for showing that analytic proofs of theorems in number theory can be replaced by elementary proofs. Originally published in 1978. The Princeton Legacy Library uses the latest print-on-demand technology to again make available previously out-of-print books from the distinguished backlist of Princeton University Press. These paperback editions preserve the original texts of these important books while presenting them in durable paperback editions. The goal of the Princeton Legacy Library is to vastly increase access to the rich scholarly heritage found in the thousands of books published by Princeton University Press since its founding in 1905. (shrink)

Meillassoux seeks knowledge of transcendental reality, blaming Kant for the ‘correlationist’ proscription of independent access to either thought or being. For Meillassoux, correlationism blocks an account of the meaning of ‘ancestral statements’ regarding reality prior to humans. I examine three charges on which Meillassoux’s argument depends: (1) Kant distorts ancestral statements’ meaning; (2) Kant fallaciously infers causality’s necessity; (3) Kant’s transcendental idealism cannot grasp ‘the great outdoors’. I reject these charges: (1) imposes a Cartesian misreading, hence Meillassoux’s false assumption that, (...) for Kant, objects don’t exist without subjects; (2) misreads Kant, who infers causality’s necessity from the possibility of experience; (3) casts Kant’s idealism as subjective, ignoring his perspectival portrayal of it. (shrink)

A reduction rule is introduced as a transformation of proof figures in implicational classical logic. Proof figures are represented as typed terms in a -calculus with a new constant P (()). It is shown that all terms with the same type are equivalent with respect to -reduction augmented by this P-reduction rule. Hence all the proofs of the same implicational formula are equivalent. It is also shown that strong normalization fails for P-reduction. Weak normalization is shown for P-reduction with another (...) reduction rule which simplifies of (( ) ) into an atomic type. (shrink)

The foundations of mathematics are divided into proof theory and set theory. Proof theory tries to justify the world of infinite mind from the standpoint of finite mind. Set theory tries to know more and more of the world of the infinite mind. The development of two subjects are discussed including a new proof of the accessibility of ordinal diagrams. Finally the world of large cardinals appears when we go slightly beyond girard's categorical approach to proof theory.

In 1963, the first author introduced a course in set theory at the University of Illinois whose main objectives were to cover Godel's work on the con sistency of the Axiom of Choice (AC) and the Generalized Continuum Hypothesis (GCH), and Cohen's work on the independence of the AC and the GCH. Notes taken in 1963 by the second author were taught by him in 1966, revised extensively, and are presented here as an introduction to axiomatic set theory. Texts in (...) set theory frequently develop the subject rapidly moving from key result to key result and suppressing many details. Advocates of the fast development claim at least two advantages. First, key results are high lighted, and second, the student who wishes to master the subject is com pelled to develop the detail on his own. However, an instructor using a "fast development" text must devote much class time to assisting his students in their efforts to bridge gaps in the text. (shrink)