In this paper, we provide a general setting under which results of normalization of proof trees such as, for instance, the logicality result in equational reasoning and the cut-elimination property in sequent or natural deduction calculi, can be unified and generalized. This is achieved by giving simple conditions which are sufficient to ensure that such normalization results hold, and which can be automatically checked since they are syntactical. These conditions are based on basic properties of elementary combinations of inference (...) rules which ensure that the induced global proof tree transformation processes do terminate. (shrink)

This paper studies the complexity of constant depth propositional proofs in the cedent and sequent calculus. We discuss the relationships between the size of tree-like proofs, the size of dag-like proofs, and the heights of proofs. The main result is to correct a proof construction in an earlier paper about transformations from proofs with polylogarithmic height and constantly many formulas per cedent.

The method of Socratic proofs (SP-method) simulates the solving of logical problem by pure questioning. An outcome of an application of the SP-method is a sequence of questions, called a Socratic transformation. Our aim is to give a method of translation of Socratic transformations into trees. We address this issue both conceptually and by providing certain algorithms. We show that the trees which correspond to successful Socratic transformations—that is, to Socratic proofs—may be regarded, after a slight modification, as Gentzen-style (...) proofs. Thus proof-search for some Gentzen-style calculi can be performed by means of the SP-method. At the same time the method seems promising as a foundation for automated deduction. (shrink)

We present sound and complete sequent calculi for the modal mu-calculus with converse modalities, aka two-way modal mu-calculus. Notably, we introduce a cyclic proof system wherein proofs can be represented as finite trees with back-edges, i.e., finite graphs. The sequent calculi incorporate ordinal annotations and structural rules for managing them. Soundness is proved with relative ease as is the case for the modal mu-calculus with explicit ordinals. The main ingredients in the proof of completeness are isolating a class (...) of non-wellfounded proofs with sequents of bounded size, called slim proofs, and a counter-model construction that shows slimness suffices to capture all validities. Slim proofs are further transformed into cyclic proofs by means of re-assigning ordinal annotations. (shrink)

A structure which generalizes formulas by including substitution terms is used to represent proofs in classical logic. These structures, called expansion trees, can be most easily understood as describing a tautologous substitution instance of a theorem. They also provide a computationally useful representation of classical proofs as first-class values. As values they are compact and can easily be manipulated and transformed. For example, we present an explicit transformations between expansion tree proofs and cut-free sequential proofs. A theorem prover which (...) represents proofs using expansion trees can use this transformation to present its proofs in more human-readable form. Also a very simple computation on expansion trees can transform them into Craig-style linear reasoning and into interpolants when they exist. We have chosen a sublogic of the Simple Theory of Types for our classical logic because it elegantly represents substitutions at all finite types through the use of the typed -calculus. Since all the proof-theoretic results we shall study depend heavily on properties of substitutions, using this logic has allowed us to strengthen and extend prior results: we are able to prove a strengthen form of the firstorder interpolation theorem as well as provide a correct description of Skolem functions and the Herbrand Universe. The latter are not straightforward generalization of their first-order definitions. (shrink)

We introduce new proof systems for propositional logic, simple deduction Frege systems, general deduction Frege systems, and nested deduction Frege systems, which augment Frege systems with variants of the deduction rule. We give upper bounds on the lengths of proofs in Frege proof systems compared to lengths in these new systems. As applications we give near-linear simulations of the propositional Gentzen sequent calculus and the natural deduction calculus by Frege proofs. The length of a proof is the (...) number of lines in the proof. A general deduction Frege proof system provides at most quadratic speedup over Frege proof systems. A nested deduction Frege proof system provides at most a nearly linear speedup over Frege system where by "nearly linear" is meant the ratio of proof lengths is O) where α is the inverse Ackermann function. A nested deduction Frege system can linearly simulate the propositional sequent calculus, the tree-like general deduction Frege calculus, and the natural deduction calculus. Hence a Frege proof system can simulate all those proof systems with proof lengths bounded by O). Also we show that a Frege proof of n lines can be transformed into a tree-like Frege proof of O lines and of height O. As a corollary of this fact we can prove that natural deduction and sequent calculus tree-like systems simulate Frege systems with proof lengths bounded by O. (shrink)

We describe a categorial system (PPTS) based on partial proof trees(PPTs) as the building blocks of the system. The PPTs are obtained byunfolding the arguments of the type that would be associated with a lexicalitem in a simple categorial grammar. The PPTs are the basic types in thesystem and a derivation proceeds by combining PPTs together. We describe theconstruction of the finite set of basic PPTs and the operations forcombining them. PPTS can be viewed as a categorial system incorporating (...) someof the key insights of lexicalized tree adjoining grammar, namely the notionof an extended domain of locality and the consequent factoring of recursionfrom the domain of dependencies. PPTS therefore inherits the linguistic andcomputational properties of that system, and so can be viewed as a middleground between a categorial grammar and a phrase structure grammar. We alsodiscuss the relationship between PPTS, natural deduction, and linear logicproof-nets, and argue that natural deduction rather than a proof-net systemis more appropriate for the construction of the PPTs. We also discuss howthe use of PPTs allows us to localize the management of resources, therebyfreeing us from this management as the PPTs are combined. (shrink)

We describe a categorial system (PPTS) based on partial proof trees(PPTs) as the building blocks of the system. The PPTs are obtained byunfolding the arguments of the type that would be associated with a lexicalitem in a simple categorial grammar. The PPTs are the basic types in thesystem and a derivation proceeds by combining PPTs together. We describe theconstruction of the finite set of basic PPTs and the operations forcombining them. PPTS can be viewed as a categorial system incorporating (...) someof the key insights of lexicalized tree adjoining grammar, namely the notionof an extended domain of locality and the consequent factoring of recursionfrom the domain of dependencies. PPTS therefore inherits the linguistic andcomputational properties of that system, and so can be viewed as a ’middleground‘ between a categorial grammar and a phrase structure grammar. We alsodiscuss the relationship between PPTS, natural deduction, and linear logicproof-nets, and argue that natural deduction rather than a proof-net systemis more appropriate for the construction of the PPTs. We also discuss howthe use of PPTs allows us to ’localize‘ the management of resources, therebyfreeing us from this management as the PPTs are combined. (shrink)

This paper proves exponential separations between depth d-LK and depth -LK for every utilizing the order induction principle. As a consequence, we obtain an exponential separation between depth d-LK and depth -LK for . We investigate the relationship between the sequence-size, tree-size and height of depth d-LK-derivations for , and describe transformations between them. We define a general method to lift principles requiring exponential tree-size -LK-refutations for to principles requiring exponential sequence-size d-LK-refutations, which will be described for the (...) Ramsey principle and d=0. From this we also deduce width lower bounds for resolution refutations of the Ramsey principle. (shrink)

According to Iris Murdoch, the chief experience in morality is the recognition of others, and this is the experience of loving attention. Love is an independent source of moral authority, distinct from the authority of reason. It is independent because it can be attained through moral experiences that are not certified by reason and cannot be achieved by rational deliberation. This view of love calls into question a cluster of concepts, such as rational agency and principled action, which figure prominently (...) in the Kantian characterization of the moral experience and resound through Kant’s account of virtue as an endured but never-ending struggle. But it would be a mistake to conclude that Murdoch’s philosophical project opposes Kant’s without further qualifications. In this chapter, I illustrate some convergence between Kant and Murdoch at the methodological level, in their polemic against reductivism. They both oppose reductivist empiricism on epistemological and moral grounds, because they define the standard of proof in relation to the experience of morality. In Murdoch’s words, the philosophical proof, if there is one, is the same as the moral proof (Murdoch 1997: 361). This is where Kant and Murdoch part ways. While Kant argues that the moral experience is the experience of the impact of reason, which provides self-discipline by constraint, Murdoch holds that the moral standard of proof is love. The transformative power of love allows us to engage with reality and recognize others for what they are, that in which consists the primal moral experience. Murdoch’s argument against Kant’s appeal to principles brings to the fore a crucial issue, which concerns the source of moral authority and the possibility of practical reason. Some of her most popular arguments against Kant are based on an oversimplified view of the impact of reason in moral life, and perhaps they owe part of their fortune to this oversimplification. I shall argue that such arguments miss their intended target, but I also hope to show that Murdoch sketches a distinctive model of the moral proof, which establishes a genuine alternative both to theories of practical reason and to reductivist accounts of the mind and its activities. (shrink)

According to Iris Murdoch, the chief experience in morality is loving attention. Her view calls into question the Kantian account of the standard of moral authority, and ultimately denies that reason might provide moral discernment, validate moral experience or drive us toward moral progress. Like Kant, Murdoch defines the moral experience as the subjective experience of freedom, which resists any reductivist approach. Unlike Kant, she thinks that this free agency is unprincipled. Some of her arguments are based on an oversimplified (...) account of Kant’s theory of reflective agency and discount the discipline of reason, thereby nullifying its practical import. However, Murdoch’s work offers a distinctive view of the standard of proof as a ‘moral proof’, which rehabilitates the transformative power of love and represents a genuine alternative to theories of practical reason as well as to reductivist empiricist views of the mind. (shrink)

The main goal of this paper is to provide an abstract framework for constructing proof systems for various many-valued logics. Using the framework it is possible to generate strongly complete proof systems with respect to any finitely valued deterministic and non-deterministic logic. I provide a couple of examples of proof systems for well-known many-valued logics and prove the completeness of proof systems generated by the framework.

In the period 1893–1897 Charles Dodgson, writing as Lewis Carroll, published two books and two articles on logic topics. Manuscript material first published in 1977 together with letters and diary entries provide evidence that he was working toward a visual proof system for complex syllogistic propositional logic based on a mechanical tree method that he devised.

This paper presents a tree method for testing the validity of inferences, including syllogisms, in a simple term logic. The method is given in the form of an algorithm and is shown to be sound and complete with respect to the obvious denotational semantics. The primitive logical constants of the system, which is indebted to the logical works of Jevons, Brentano and Lewis Carroll, are term negation, polyadic term conjunction, and functors affirming and denying existence, and use is also (...) made of a metalinguistic concept of formal synonymy. It is indicated briefly how the method may be extended to other systems. (shrink)

In this paper it is exactly proved that the standard transformations of the three-dimensional (3D) vectors of the electric and magnetic fields E and B are not relativistically correct transformations. Thence the 3D vectors E and B are not well-defined quantities in the 4D space-time and, contrary to the general belief, the usual Maxwell equations with the 3D E and B are not in agreement with the special relativity. The 4-vectors E a and B a , as well-defined 4D quantities, (...) are introduced instead of ill-defined 3D E and B. The proof is given in the tensor and the Clifford algebra formalisms. (shrink)

In this paper the PA-completeness of modal logic is studied by syntactical and constructive methods. The main results are theorems on the structure of the PA-proofs of suitable arithmetical interpretationsS of a modal sequentS, which allow the transformation of PA-proofs ofS into proof-trees similar to modal proof-trees. As an application of such theorems, a proof of Solovay's theorem on arithmetical completeness of the modal system G is presented for the class of modal sequents of Boolean combinations (...) of formulas of the form p i,m i=0, 1, 2, ... The paper is the preliminary step for a forthcoming global syntactical resolution of the PA-completeness problem for modal logic. (shrink)

Venerable tradition allies the Torah with Wisdom, a “tree of life.”2 The tree of life is an ancient mythic symbol of the earth mother. This essay demonstrates the capacity of the Torah to facilitate a reintegrative return to the mother when, as now, the religious narratives falter that once seemed to ensure the unity of man made in the image of God conceived only as the Father. Participating in the process of this return one discovers beneath the Torah's (...) fractured narrative surface a reduplicative pattern based on the logic of the unconscious, which is founded on the repressed prelinguistic bond with all life formed at the maternal breast. This pattern reflects the recombinant properties that the unconscious shares with the earth, which breaks down and regenerates dead matter as the unconscious breaks down and regenerates the meaning of words. Folded into rhetorical tropes as into a single letter, the Torah's regenerative pattern repeatedly recalls to man what it means to be human, unique among but also one with all the diverse life of the earth. (shrink)

In this paper the Lorentz transformations (LT) and the standard transformations (ST) of the usual Maxwell equations (ME) with the three-dimensional (3D) vectors of the electric and magnetic fields, E and B, respectively, are examined using both the geometric algebra and tensor formalisms. Different 4D algebraic objects are used to represent the usual observer dependent and the new observer independent electric and magnetic fields. It is found that the ST of the ME differ from their LT and consequently that the (...) ME with the 3D E and B are not covariant upon the LT but upon the ST. The obtained results do not depend on the character of the 4D algebraic objects used to represent the electric and magnetic fields. The Lorentz invariant field equations are presented with 1-vectors E and B, bivectors EHv and BHv and the abstract tensors, the 4-vectors Ea and Ba. All these quantities are defined without reference frames, i.e., as absolute quantities. When some basis has been introduced, they are represented as coordinate-based geometric quantities comprising both components and a basis. It is explicitly shown that this geometric approach agrees with experiments, e.g., the Faraday disk, in all relatively moving inertial frames of reference, which is not the case with the usual approach with the 3D bf E and B and their ST. (shrink)

Wilfred Sieg and Stanley S. Wainer. Program Transformation and Proof Transformation.

Urban street trees (USTs) have a range of values – some of which are easier to quantify than others. Focusing specifically on the UK context and using the Sheffield Tree Protests (2012–) as a case study, whilst confirming existing research as to the variety of values associated with their specifically ‘cultural’ services, the article argues that USTs have an additional potential form – what I call ‘civic-transformative value’. This form of value has at least three key characteristics. Firstly, it (...) is place-based and communal; second, its form is ‘relational’; and finally, as intrinsically contingent, it is pluralistic in the sense that its civic-transformative potential is dependent on successfully integrating a range of other values. The article emphasises both the possibility and necessity of ‘convergence’ – that is, a pluralistic and pragmatic alliance of values which might help protect not only USTs, but other embattled sites of nature. (shrink)

We give a new proof of a theorem of Shelah which states that for every family of labeled trees, if the cardinality κ of the family is much larger (in the sense of large cardinals) than the cardinality λ of the set of labels, more precisely if the partition relation holds, then there is a homomorphism from one labeled tree in the family to another. Our proof uses a characterization of such homomorphisms in terms of games.

We shall give a direct proof of the independence result of a Buchholz style-Hydra Game on labeled finite trees. We shall show that Takeuti-Arai's cut-elimination procedure of $(\Pi^{1}_{1}-CA) + BI$ and of the iterated inductive definition systems can be directly expressed by the reduction rules of Buchholz's Hydra Game. As a direct corollary the independence result of the Hydra Game follows.

I argue that we do not intentionally and rationally shape our character and values in major ways. I base this argument on the nature of transformative experiences, that is, those experiences which are transformative from personal and epistemological points of view. The argument is roughly this. First, someone who undergoes major changes in her character or values thereby undergoes a transformative experience. Second, if she undergoes such an experience, her reasons for changing in a major way are inaccessible to her (...) beforehand. Third, if such reasons are inaccessible beforehand, she cannot act on them and thus cannot rationally and intentionally shape her character or values. I also explore some consequences of my argument, especially those related to control and responsibility. (shrink)

In this paper we introduce a Gentzen calculus for (a functionally complete variant of) Belnap's logic in which establishing the provability of a sequent in general requires \emph{two} proof trees, one establishing that whenever all premises are true some conclusion is true and one that guarantees the falsity of at least one premise if all conclusions are false. The calculus can also be put to use in proving that one statement \emph{necessarily approximates} another, where necessary approximation is a natural (...) dual of entailment. The calculus, and its tableau variant, not only capture the classical connectives, but also the `information' connectives of four-valued Belnap logics. This answers a question by Avron. (shrink)

We present two proof systems for first-order logic with identity and without function symbols. The first one is an extension of the Rasiowa-Sikorski system with the rules for identity. This system is a validity checker. The rules of this system preserve and reflect validity of disjunctions of their premises and conclusions. The other is a Tableau system, which is an unsatisfiability checker. Its rules preserve and reflect unsatisfiability of conjunctions of their premises and conclusions. We show that the two (...) systems are dual to each other. The duality is expressed in a formal way which enables us to define a transformation of proofs in one of the systems into the proofs of the other. (shrink)

According to Iris Murdoch, the chief experience in morality is loving attention. Her view calls into question the Kantian account of the standard of moral authority, and ultimately denies that reason might provide moral discernment, validate moral experience, or drive us toward moral progress. Like Kant, Murdoch defines the moral experience as the subjective experience of freedom, which resists any reductivist approach. Unlike Kant, she thinks that this free agency is unprincipled. Some of her arguments are based on an oversimplified (...) account of Kant’s theory of reflective agency and discount the discipline of reason, thereby nullifying its practical import. However, Murdoch’s work offers a distinctive view of the standard of proof as a “moral proof”, which rehabilitates the transformative power of love and represents a genuine alternative to theories of practical reason as well as to reductivist empiricist views of the mind. (shrink)

There is an exponential speed-up in the number of lines of the quantified propositional sequent calculus over Substitution Frege Systems, if one considers proofs as trees. Whether this is true also for the number of symbols, is still an open problem.

Proofs and countermodels are the two sides of completeness proofs, but, in general, failure to find one does not automatically give the other. The limitation is encountered also for decidable non-classical logics in traditional completeness proofs based on Henkin’s method of maximal consistent sets of formulas. A method is presented that makes it possible to establish completeness in a direct way: For any given sequent either a proof in the given logical system or a countermodel in the corresponding frame (...) class is found. The method is a synthesis of a generation of calculi with internalized relational semantics, a Tait–Schütte–Takeuti style completeness proof, and procedures to finitize the countermodel construction. Finitizations for intuitionistic propositional logic are obtained through the search for a minimal derivation, through pruning of infinite branches in search trees by means of a suitable syntactic counterpart of semantic filtration, or through a proof-theoretic embedding into an appropriate provability logic. A number of examples illustrates the method, its subtleties, challenges, and present scope. (shrink)

Interest in philosophical anthropology in the early twelfth century was limited to the logical question of how to think and speak about dead humans. This question was prompted by the logic of living and dead humans based on the doctrine of substance found in Aristotle’s Categories and in the division of substance, as outlined by Porphyry to exemplify the logic of genus and species relations in the Isagoge. Abelard held the view that there is no such thing as a dead (...) human, and this provoked an intense response from his contemporaries. Abelard’s contemporaries, including Alberic of Paris and other anonymous authors, mounted a number of arguments against Abelard’s views. The stakes were high for them: as realists about species and genera, Abelard’s denial that there are dead humans threatened their entire interpretation of the structure of species and genera, and thereby their theory of universals. (shrink)

An important technique in large cardinal set theory is that of extending an elementary embedding j: M → N between inner models to an elementary embedding j*: M[G] → N[G*] between generic extensions of them. This technique is crucial both in the study of large cardinal preservation and of internal consistency. In easy cases, such as when forcing to make the GCH hold while preserving a measurable cardinal (via a reverse Easton iteration of α-Cohen forcing for successor cardinals α), the (...) generic G* is simply generated by the image of G. But in difficult cases, such as in Woodin's proof that a hypermeasurable is sufficient to obtain a failure of the GCH at a measurable, a preliminary version of G* must be constructed (possibly in a further generic extension of M[G]) and then modified to provide the required G*. In this article we use perfect trees to reduce some difficult cases to easy ones, using fusion as a substitute for distributivity. We apply our technique to provide a new proof of Woodin's theorem as well as the new result that global domination at inaccessibles (the statement that d (κ) is less than 2κ for inaccessible κ, where d (κ) is the dominating number at κ) is internally consistent, given the existence of 0#. (shrink)

Evolutionary and organismal biology have become inundated with data. At the same rate, we are experiencing a surge in broader evolutionary and ecological syntheses for which tree-thinking is the staple for a variety of post-tree analyses. To fully take advantage of this wealth of data to discover and understand large-scale evolutionary and ecological patterns, computational data integration, i.e., the use of machines to link data at large scale, is crucial. The most common shared entity by which evolutionary and (...) ecological data need to be linked is the taxon to which they belong. We propose a set of requirements that a system for defining such taxa should meet for computational data science: taxon definitions should maintain conceptual consistency, be reproducible via a known algorithm, be computationally automatable, and be applicable across the Tree of Life. We argue that Linnaean names, the most prevalent means of linking data to taxa, fail to meet these requirements due to fundamental theoretical and practical shortfalls. We argue that for the purposes of data-integration we should instead use phylogenetic definitions transformed into formal logic expressions. We call such expressions “phyloreferences”, and argue that, unlike Linnaean names, they meet all requirements for effective data-integration. (shrink)

Second-order abstract categorial grammars (de Groote in Association for computational linguistics, 39th annual meeting and 10th conference of the European chapter, proceedings of the conference, pp. 148–155, 2001) and hyperedge replacement grammars (Bauderon and Courcelle in Math Syst Theory 20:83–127, 1987; Habel and Kreowski in STACS 87: 4th Annual symposium on theoretical aspects of computer science. Lecture notes in computer science, vol 247, Springer, Berlin, pp 207–219, 1987) are two natural ways of generalizing “context-free” grammar formalisms for string and (...) class='Hi'>tree languages. It is known that the string generating power of both formalisms is equivalent to (non-erasing) multiple context-free grammars (Seki et al. in Theor Comput Sci 88:191–229, 1991) or linear context-free rewriting systems (Weir in Characterizing mildly context-sensitive grammar formalisms, University of Pennsylvania, 1988). In this paper, we give a simple, direct proof of the fact that second-order ACGs are simulated by hyperedge replacement grammars, which implies that the string and tree generating power of the former is included in that of the latter. The normal form for tree-generating hyperedge replacement grammars given by Engelfriet and Maneth (Graph transformation. Lecture notes in computer science, vol 1764. Springer, Berlin, pp 15–29, 2000) can then be used to show that the tree generating power of second-order ACGs is exactly the same as that of hyperedge replacement grammars. (shrink)

We upgrade [3] to a complete proof of the conjecture NP = PSPACE that is known as one of the fundamental open problems in the mathematical theory of computational complexity; this proof is based on [2]. Since minimal propositional logic is known to be PSPACE complete, while PSPACE to include NP, it suffices to show that every valid purely implicational formula ρ has a proof whose weight and time complexity of the provability involved are both polynomial in (...) the weight of ρ. As is [3], we use proof theoretic approach. Recall that in [3] we considered any valid ρ in question that had a “short” tree-like proof π in the Hudelmaier-style cutfree sequent calculus for minimal logic. The “shortness” means that the height of π and the total weight of different formulas occurring in it are both polynomial in the weight of ρ. However, the size, and hence also the weight, of π could be exponential in that of ρ. To overcome this trouble we embedded π into Prawitz’s proof system of natural deductions containing single formulas, instead of sequents. As in π, the height and the total weight of different formulas of the resulting tree-like natural deduction ∂1 were polynomial, although the size of ∂1 still could be exponential, in the weight of ρ. In our next, crucial move, ∂1 was deterministically compressed into a “small”, although multipremise, dag-like deduction ∂ whose horizontal levels contained only mutually different formulas, which made the whole weight polynomial in that of ρ. However, ∂ required a more complicated verification of the underlying provability of ρ. In this paper we present a nondeterministic compression of ∂ into a desired standard dag-like deduction ∂0 that deterministically proves ρ in time and space polynomial in the weight of ρ.2 Together with [3] this completes the proof of NP = PSPACE.Natural deductions are essential for our proof. Tree-to-dag horizontal compression of π merging equal sequents, instead of formulas, is not sufficient, since the total number of different sequents in π might be exponential in the weight of ρ – even assuming that all formulas occurring in sequents are subformulas of ρ. On the other hand, we need Hudelmaier’s cutfree sequent calculus in order to control both the height and total weight of different formulas of the initial tree-like proof π, since standard Prawitz’s normalization although providing natural deductions with the subformula property does not preserve polynomial heights. It is not clear yet if we can omit references to π even in the proof of the weaker result NP = coNP. (shrink)

We present an alternative proof that from large cardinals, we can force the tree property at $\kappa ^+$ and $\kappa ^{++}$ simultaneously for a singular strong limit cardinal $\kappa $. The advantage of our method is that the proof of the tree property at the double successor is simpler than in the existing literature. This new approach also works to establish the result for $\kappa =\aleph _{\omega ^2}$.

We give definitions that distinguish between two notions of indiscernibility for a set {aη∣η∈ω>ω}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\{a_{\eta} \mid \eta \in ^{\omega>}\omega\}}$$\end{document} that saw original use in Shelah [Classification theory and the number of non-isomorphic models. North-Holland, Amsterdam, 1990], which we name s- and str−indiscernibility. Using these definitions and detailed proofs, we prove s- and str-modeling theorems and give applications of these theorems. In particular, we verify a step in the argument that TP is equivalent (...) to TP1 or TP2 that has not seen explication in the literature. In the Appendix, we exposit the proofs of Shelah [Classification theory and the number of non-isomorphic models. North-Holland, Amsterdam, 1990, App. 2.6, 2.7], expanding on the details. (shrink)

In this paper we present and study a categorical formulation of the W-types of Martin-Löf. These are essentially free term algebras where the operations may have finite or infinite arity. It is shown that W-types are preserved under the construction of sheaves and Artin gluing. In the proofs we avoid using impredicative or nonconstructive principles.

This paper is the second part of the syntactic demonstration of the Arithmetical Completeness of the modal system G, the first part of which is presented in [9]. Given a sequent S so that ⊢GL-LIN S, ⊬G S, and given its characteristic formula H = char(S), which expresses the non G-provability of S, we construct a canonical proof-tree T of ~ H in GL-LIN, the height of which is the distance d(S, G) of S from G. T is (...) the syntactic countermodel of S with respect to Gand is a tool of general interest in Provability Logic, that allows some classification in the set of the arithmetical interpretations. (shrink)

This paper is the first of a series of three articles that present the syntactic proof of the PA-completeness of the modal system G, by introducing suitable proof-theoretic objects, which also have an independent interest. We start from the syntactic PA-completeness of modal system GL-LIN, previously obtained in [7], [8], and so we assume to be working on modal sequents S which are GL-LIN-theorems. If S is not a G-theorem we define here a notion of syntactic metric d(S, (...) G): we calculate a canonical characteristic fomula H of S (char(S)) so that ⊢G ∼ H → (∼S) and ⊢GL-LIN ∼ H, and the complexity σ of ∼ H gives the distance d(S, G) of S from G. Then, in order to produce the whole completeness proof as an induction on this d(S, G), we introduce the tree-interpretation of a modal sequent Q into PA, that sends the letters of Q into PA-formulas describing the properties of a GL-LIN-proof P of Q: It is also a d(*, G)-metric linked interpretation, since it will be applied to a proof-tree T of ∼ H with H = char(S) and σ(∼ H) = d(S, G). (shrink)

This paper is the final part of the syntactic demonstration of the Arithmetical Completeness of the modal system G; in the preceding parts [9] and [10] the tools for the proof were defined, in particular the notion of syntactic countermodel. Our strategy is: PA-completeness of G as a search for interpretations which force the distance between G and a GL-LIN-theorem to zero. If the GL-LIN-theorem S is not a G-theorem, we construct a formula H expressing the non G-provability of (...) S, so that ⊢GL-LIN ∼ H and so that a canonical proof T of ∼ H in GL-LIN is a syntactic countermodel for S with respect to G, which has the height θ(T) equal to the distance d(S, G) of S from G. Then we define the interpretation ξ of S which represents the proof-tree T in PA. By induction on θ(T), we prove that ⊢PA Sξ and d(S, G) > 0 imply the inconsistency of PA. (shrink)

We show that MRP + MA implies that ITP(λ, ω 2 ) holds for all cardinal λ ≥ ω 2 . This generalizes a result by Weiß who showed that PFA implies that ITP(λ, ω 2 ) holds for all cardinal λ ≥ ω 2 . Consequently any of the known methods to prove MRP + MA consistent relative to some large cardinal hypothesis requires the existence of a strongly compact cardinal. Moreover if one wants to force MRP + MA (...) with a proper forcing, it requires at least a supercompact cardinal. We also study the relationship between MRP and some weak versions of square. We show that MRP implies the failure of □(λ, ω) for all λ ≥ ω 2 and we give a direct proof that MRP + MA implies the failure of □(λ, ω 1 ) for all λ ≥ ω 2. (shrink)

Gentzen's original proof of the Hauptsatz used a rule of multicut in the case that the right premiss of cut was derived by contraction. Cut elimination is here proved without multicut, by transforming suitably the derivation of the premiss of the contraction.