In this paper, we show that the predicate logics of consistent extensions of Heyting's Arithmetic plus Church's Thesis with uniqueness condition are complete $\Pi _{2}^{0}$. Similarly, we show that the predicate logic of HA*, i.e. Heyting's Arithmetic plus the Completeness Principle (for HA*) is complete $\Pi _{2}^{0}$. These results extend the known results due to Valery Plisko. To prove the results we adapt Plisko's method to use Tennenbaum's Theorem to prove 'categoricity of interpretations' under certain assumptions.

This paper is devoted to the formulation and investigation of a dynamic semantic interpretation of the language of first-order predicate logic. The resulting system, which will be referred to as ‘dynamic predicate logic’, is intended as a first step towards a compositional, non-representational theory of discourse semantics. In the last decade, various theories of discourse semantics have emerged within the paradigm of model-theoretic semantics. A common feature of these theories is a tendency to do away with (...) the principle of compositionality, a principle which, implicitly or explicitly, has dominated semantics since the days of Frege. Therefore the question naturally arises whether non-compositionality is in any way a necessary feature of discourse semantics. Since we subscribe to the interpretation of compositionality as constituting primarily a methodological principle, we consider this to be a methodological rather than an empirical question. As a consequence, the emphasis in the present paper lies on developing an alternative compositional semantics of discourse, which is empirically equivalent to its non-compositional brethren, but which differs from them in a principled methodological way. Hence, no attempts are made to improve on existing theories empirically. Nevertheless, as we indicate in section 5, the development of a compositional alternative may in the end have empirical consequences, too. First of all, it can be argued that the dynamic view on interpretation developed in this paper suggests natural and relatively easy to formulate extensions which enable one to deal with a wider range of phenomena than can be dealt with in existing theories. Moreover, the various approaches to the model-theoretic semantics of discourse that have been developed during the last decade, have constituted a ‘fresh start’ in the sense that much of what had been accomplished before was ignored, at least for a start. Of course, this is a justified strategy if one feels one is trying to develop a radically different approach to recalcitrant problems. However, there comes a time when such new approaches have to be compared with the older one, and when an assessment of the pros and cons of each has to be made. One of the main problems in semantics today, we feel, is that a semantic theory such as Montague grammar, and an approach like Kamp’s discourse representation theory, are hard to compare, let alone that it is possible to unify their insights and results.. (shrink)

The complexity of any logical modeling reflects both the intrinsic structure of a topic described and the weight of the formal tools. Some of this weight seems inherent in even the most basic logical systems. Notably, standard predicate logic is undecidable. In this paper, we investigate ‘lighter’ versions of this general purpose tool, by modally ‘deconstructing’ the usual semantics, and locating implicit choice points in its set up. The first part sets out the interest of this program and (...) the modal techniques employed, while the second part provides technical elaborations demonstrating its viability. (shrink)

We develop a predicate logical extension of a subintuitionistic propositional logic. Therefore a Hilbert type calculus and a Kripke type model are given. The propositional logic is formulated to axiomatize the idea of strategic weakening of Kripke''s semantic for intuitionistic logic: dropping the semantical condition of heredity or persistence leads to a nonmonotonic model. On the syntactic side this leads to a certain restriction imposed on the deduction theorem. By means of a Henkin argument strong completeness (...) is proved making use of predicate logical principles, which are only classically acceptable. (shrink)

The paper presents predicate logical extensions of some subintuitionistic logics. Subintuitionistic logics result if conditions of the accessibility relation in Kripke models for intuitionistic logic are dropped. The accessibility relation which interprets implication in models for the propositional base subintuitionistic logic considered here is neither persistent on atoms, nor reflexive, nor transitive. Strongly complete predicate logical extensions are modeled with a second accessibility relation, which is a partial order, for the interpretation of the universal quantifier.

A logic-enriched type theory is a type theory extended with a primitive mechanism for forming and proving propositions. We construct two LTTs, named and , which we claim correspond closely to the classical predicative systems of second order arithmetic and . We justify this claim by translating each second order system into the corresponding LTT, and proving that these translations are conservative. This is part of an ongoing research project to investigate how LTTs may be used to formalise different (...) approaches to the foundations of mathematics.The two LTTs we construct are subsystems of the logic-enriched type theory , which is intended to formalise the classical predicative foundation presented by Herman Weyl in his monograph Das Kontinuum. The system has also been claimed to correspond to Weyl’s foundation. By casting and as LTTs, we are able to compare them with . It is a consequence of the work in this paper that is strictly stronger than .The conservativity proof makes use of a novel technique for proving one LTT conservative over another, involving defining an interpretation of the stronger system out of the expressions of the weaker. This technique should be applicable in a wide variety of different cases outside the present work. (shrink)

This clearly written book makes logic interesting and easier to learn without sacrificing content or rigor. It covers symbolization, proofs, counterexamples, and truth trees. These topics are presented in graded steps, beginning with the symbolization of categorical propositions and concluding with the properties of relations. Logic is applied to materials with which readers will be familiar; both examples and exercises are drawn from newspapers, television, and other popular sources. For individuals intrigued by the formal study of logic.

We investigate a rst-order predicate logic based on Wittgenstein's suggestion to express identity of object by identity of sign, and difference of objects by difference of signs. Hintikka has shown that predicate logic can indeed be set up in such a way; we show that it can be done nicely. More specically, we provide a perspicuous cut-free sequent calculus, as well as a Hilbert-type calculus, for Wittgensteinian predicate logic and prove soundness and completeness theorems.

The paper provides a uniform Gentzen-style proof-theoretic framework for various subsystems of classical predicate logic. In particular, predicate logics obtained by adopting van Behthem''s modal perspective on first-order logic are considered. The Gentzen systems for these logics augment Belnap''s display logic by introduction rules for the existential and the universal quantifier. These rules for x and x are analogous to the display introduction rules for the modal operators and and do not themselves allow the Barcan (...) formula or its converse to be derived. En route from the minimal modal predicate logic to full first-order logic, axiomatic extensions are captured by purely structural sequent rules. (shrink)

In our previous paper [5], we have studied Kripke-type semantics for propositional logics without the contraction rule. In this paper, we will extend our argument to predicate logics without the structure rules. Similarly to the propositional case, we can not carry out Henkin's construction in the predicate case. Besides, there exists a difficulty that the rules of inference () and () are not always valid in our semantics. So, we have to introduce a notion of normal models.

A new formalism for predicate logic is introduced, with a non-standard method of binding variables, which allows a compositional formalization of certain anaphoric constructions, including donkey sentences and cross-sentential anaphora. A proof system in natural deduction format is provided, and the formalism is compared with other accounts of this type of anaphora, in particular Dynamic Predicate Logic.

Monoidal t-norm based logic $\mathbf {MTL}$ is the weakest t-norm based residuated fuzzy logic, which is a $[0,1]$ -valued propositional logical system having a t-norm and its residuum as truth function for conjunction and implication. Monadic fuzzy predicate logic $\mathbf {mMTL\forall }$ that consists of the formulas with unary predicates and just one object variable, is the monadic fragment of fuzzy predicate logic $\mathbf {MTL\forall }$, which is indeed the predicate version of monoidal (...) t-norm based logic $\mathbf {MTL}$. The main aim of this paper is to give an algebraic proof of the completeness theorem for monadic fuzzy predicate logic $\mathbf {mMTL\forall }$ and some of its axiomatic extensions. Firstly, we survey the axiomatic system of monadic algebras for t-norm based residuated fuzzy logic and amend some of them, thus showing that the relationships for these monadic algebras completely inherit those for corresponding algebras. Subsequently, using the equivalence between monadic fuzzy predicate logic $\mathbf {mMTL\forall }$ and S5-like fuzzy modal logic $\mathbf {S5(MTL)}$, we prove that the variety of monadic MTL-algebras is actually the equivalent algebraic semantics of the logic $\mathbf {mMTL\forall }$, giving an algebraic proof of the completeness theorem for this logic via functional monadic MTL-algebras. Finally, we further obtain the completeness theorem of some axiomatic extensions for the logic $\mathbf {mMTL\forall }$, and thus give a major application, namely, proving the strong completeness theorem for monadic fuzzy predicate logic based on involutive monoidal t-norm logic $\mathbf {mIMTL\forall }$ via functional representation of finitely subdirectly irreducible monadic IMTL-algebras. (shrink)

Geach's account of the Aristotelian logic of categorical sentences supplemented the views shared by Frege, Russell, Quine and others. I argue that this particular predicate logic approach and Geach's points apply to only one variety of natural language categorical sentences. For example, it takes the universal categorical as a universal conditional “If anything is a man, then it is mortal”. A different natural language form can and should be invoked: “Every man is a mortal.” Employing special restricted (...) quantifiers in a version of predicate logic, we justify a full square of opposition and the rules of quality and quantity that Geach rejected. (shrink)

Predicates are supposed to slice reality neatly in two halves, one for which the predicate holds, the other for which it fails. Yet far from being razors, predicates tend to be dull knives that mangle reality. If reality is a tomato and predicates are knives, then when these knives divide the tomato, plenty of mush remains unaccounted for. Of course some knives are sharper than others, just as some predicates are less vague than others. “x is water” is certainly (...) sharper than “x is beautiful.” But perfect sharpness, perfect boundaries, and perfect separation seem only to obtain in mathematics. The vagueness inherent in many predicates became particularly evident in the twentieth century. Quantum mechanics, the revival of certain ancient paradoxes, and the philosophy of science all contributed to a growing awareness that vagueness was ineliminable from many predicates. Quantum mechanical superposition seems to allow mutually exclusive simultaneous states. In searching for plausible interpretations of quantum mechanics, some researchers attempted to do away with classical bivalent logic. In its place they substituted multivalent quantum logics. Any logic with more than two values forces its predicates to slice reality into more than two parts. Ancient paradoxes involving heaps and baldness also pointed up the 1 Random Predicate Logic 2.. (shrink)

In this paper we introduce a notion of context for Groenendijk & Stokhof's Dynamic Predicate Logic DPL. We use these contexts to give a characterization of the relations on assignments that can be generated by composition from tests and random resettings in the case that we are working over an infinite domain. These relations are precisely the ones expressible in DPL if we allow ourselves arbitrary tests as a starting point. We discuss some possible extensions of DPL and (...) the way these extensions interact with our notion of context. (shrink)

The article deals with the interpretation of propositional attitudes in the framework of modal predicate logic. The first part discusses the classical puzzles arising from the interplay between propositional attitudes, quantifiers and the notion of identity. After comparing different reactions to these puzzles it argues in favor of an analysis in which evaluations of de re attitudes may vary relative to the ways of identifying objects used in the context of use. The second part of the article gives (...) this analysis a precise formalization from a model-and proof-theoretic perspective. (shrink)

For each ordinal $\alpha > 0, L(\alpha)$ is the intermediate predicate logic characterized by the class of all Kripke frames with the poset α and with constant domain. This paper will be devoted to a study of logics of the form L(α). It will be shown that for each uncountable ordinal of the form α + η with a finite or a countable $\eta (> 0)$ , there exists a countable ordinal of the form β + η such (...) that L(α + η) = L(β + η). On the other hand, such a reduction of ordinals to countable ones is impossible for a logic L(α) if α is an uncountable regular ordinal. Moreover, it will be proved that the mapping L is injective if it is restricted to ordinals less than ω ω , i.e. α ≠ β implies L(α) ≠ L(β) for each ordinal $\alpha,\beta. (shrink)

A notion of strictly primitive recursive realizability is introduced by Damnjanovic in 1994. It is a kind of constructive semantics of the arithmetical sentences using primitive recursive functions. It is of interest to study the corresponding predicate logic. It was argued by Park in 2003 that the predicate logic of strictly primitive recursive realizability is not arithmetical. Park’s argument is essentially based on a claim of Damnjanovic that intuitionistic logic is sound with respect to strictly (...) primitive recursive realizability, but that claim was disproved by the author of this article in 2006. The aim of this paper is to present a correct proof of the result of Park. (shrink)

• 1st try: Free variables in PL (Predicate Logic) (1) Jim1 came in. He1 sat down. (antecedent Jim1 … anaphoric he1) |=M, g cm ιx(x = z1  z1 = jim)  sit z1 iff g(z1) ∈ cm & g(z1) = jim & g(z1) ∈ sit.

The epsilon substitution method was proposed by D. Hilbert as a tool for consistency proofs. A version for first order predicate logic had been described and proved to terminate in the monograph “Grundlagen der Mathematik”. As far as the author knows, there have been no attempts to extend this approach to the second order case. We discuss possible directions for and obstacles to such extensions.

Basic Predicate Logic, BQC, is a proper subsystem of Intuitionistic Predicate Logic, IQC. For every formula in the language {, , , , , , }, we associate two sequences of formulas 0,1,... and 0,1,... in the same language. We prove that for every sequent , there are natural numbers m, n, such that IQC , iff BQC n m. Some applications of this translation are mentioned.

This clearly written book makes logic interesting and easier to learn without sacrificing content or rigor. KEY TOPICS: It covers symbolization, proofs, counterexamples, and truth trees. These topics are presented in graded steps, beginning with the symbolization of categorical propositions and concluding with the properties of relations. Logic is applied to materials with which readers will be familiar; both examples and exercises are drawn from newspapers, television, and other popular sources. MARKET: For individuals intrigued by the formal study (...) of logic. (shrink)

In this paper a semantics for dynamic predicate logic is developed that uses sequence valued assignments. This semantics is compared with the usual relational semantics for dynamic predicate logic: it is shown that the most important intuitions of the usual semantics are preserved. Then it is shown that the refined semantics reflects out intuitions about information growth. Some other issues in dynamic semantics are formulated and discussed in terms of the new sequence semantics.

In this paper we study the notion of forcing for Łukasiewicz predicate logic (Ł∀, for short), along the lines of Robinson’s forcing in classical model theory. We deal with both finite and infinite forcing. As regard to the former we prove a Generic Model Theorem for Ł∀, while for the latter, we study the generic and existentially complete standard models of Ł∀.

An intermediate predicate logicS + n (n>0) is introduced and investigated. First, a sequent calculusGS n is introduced, which is shown to be equivalent toS + n and for which the cut elimination theorem holds. In § 2, it will be shown thatS + n is characterized by the class of all linear Kripke frames of the heightn.

In this work we extend results from [4], [3] and [2] about propositional calculi with graded modalities to the predicative level. Our semantic is based on Kripke models with a single domain of interpretation for all the worlds. Therefore the axiomatic system will need a suitable generalization of the Barcan formula. We haven't considered semantics with world-relative domains because they don't present any new difficulties with respect to classical case. Our language will have, as in [1], constant and function symbols, (...) but they will have a rigid interpretation. In this instance the terms will be considered rigid designators, that is, their interpretations will be the same in all possible worlds (cfr. [5]). Nevertheless we will not consider languages with identity: in this way we avoid the problems of identity in modal contexts. On the other hand, we think that in that context would arise essentially the same problems which occur in classical predicative modal logic. Finally we will consider only denumerable languages because the extension to non denumerable ones isn't conceptually problematic. (shrink)

After a summary of earlier work it is shown that elementary or Kalmar arithmetic can be interpreted within the system of Russell's Principia Mathematica with the axiom of infinity but without the axiom of reducibility.

Since Aristotle and the Stoa, there has been a clash, worsened by modern predicate logic, between logically defined operator meanings and natural intuitions. Pragmatics has tried to neutralize the clash by an appeal to the Gricean conversational maxims. The present study argues that the pragmatic attempt has been unsuccessful. The “softness” of the Gricean explanation fails to do justice to the robustness of the intuitions concerned, leaving the relation between the principles evoked and the observed facts opaque. Moreover, (...) there are cases where the Gricean maxims fail to apply. A more adequate solution consists in the devising of a sound natural logic, part of the innate cognitive equipment of mankind. This account has proved successful in conjunction with a postulated cognitive mechanism in virtue of which the universe of discourse is stepwise and recursively restricted, so that the negation selects different complements according to the degree of restrictedness of Un. This mechanism explains not only the discrepancies between natural logical intuitions and known logical systems; it also accounts for certain systematic lexicalization gaps in the languages of the world. Finally, it is shown how stepwise restriction of Un produces the ontogenesis of natural predicate logic, while at the same time resolving the intuitive clashes with established logical systems that the Gricean maxims sought to explain. (shrink)

A partial solution to Ono’s problem P54 is given. Here Ono’s problem P54 is whether Harrop disjunction property is equivalent to disjunction property or not in intermediate predicate logics. As an application of this result it is shown that some intermediate predicate logics satisfy Harrop disjunction property.

We propose a new, rather simple and short proof of Kripke-completeness for the predicate variant of Dummett's logic. Also a family of Kripke-incomplete extensions of this logic that are complete w.r.t. Kripke frames with equality (or equivalently, w.r.t. Kripke sheaves [8]), is described.

Aristotle’s modal syllogistic is his study of patterns of reasoning about necessity and possibility. Many scholars think the modal syllogistic is incoherent, a ‘realm of darkness’. Others think it is coherent, but devise complicated formal modellings to mimic Aristotle’s results. This volume provides a simple interpretation of Aristotle’s modal syllogistic using standard predicate logic. Rini distinguishes between red terms, such as ‘horse’, ‘plant’ or ‘man’, which name things in virtue of features those things must have, and green terms, (...) such as ‘moving’, which name things in virtue of their non-necessary features. By applying this distinction to the Prior Analytics, Rini shows how traditional interpretive puzzles about the modal syllogistic melt away and the simple structure of Aristotle’s own proofs is revealed. The result is an applied logic which provides needed links between Aristotle’s views of science and logical demonstration. The volume is particularly valuable to researchers and students of the history of logic, Aristotle’s theory of modality, and the philosophy of logic in general. (shrink)

An intermediate predicate logic L is called finite iff it is characterized by a finite partially ordered set M, i.e., iff L is the logic of the class of all predicate Kripke frames based on M. In this paper we study axiomatizability of logics of this kind. Namely, we consider logics characterized by finite trees M of a certain type (levelwise uniform trees) and establish the finite axiomatizability criterion for this case.

Abstract.Given a class C of t-norm BL-algebras, one may wonder which is the complexity of the set Taut(C∀) of predicate formulas which are valid in any algebra in C. We first characterize the classes C for which Taut(C∀) is recursively axiomatizable, and we show that this is the case iff C only consists of the Gödel algebra on [0,1]. We then prove that in all cases except from a finite number Taut(C∀) is not even arithmetical. Finally we consider (...) class='Hi'>predicate monadic logics TautM(C∀) of classes C of t-norm BL-algebras, and we prove that (possibly with finitely many exceptions) they are undecidable. (shrink)

The paper proves a predicate version of Solovay's well-known theorem on provability interpretations of modal logic: If a closed modal predicate-logical formula R is not valid in some finite Kripke model, then there exists an arithmetical interpretation f such that $PA \nvdash fR$ . This result implies the arithmetical completeness of arithmetically correct modal predicate logics with the finite model property (including the one-variable fragments of QGL and QS). The proof was obtained by adding "the (...) class='Hi'>predicate part" as a specific addition to the standard Solovay construction. (shrink)

Two variants of monadic fuzzy predicate logic are analyzed and compared with the full fuzzy predicate logic with respect to finite model property (properties) and arithmetical complexity of sets of tautologies, satisfiable formulas and of analogous notion restricted to finite models.

Shehtman and Skvortsov introduced Kripke bundles as semantics of non-classical first-order predicate logics. We show the structural equivalence between Kripke bundles for intermediate predicate lógics and Kripke-type frames for intuitionistic modal propositional logics. This equivalence enables us to develop the semantical study of relations between intermediate predicate logics and intuitionistic modal propositional logics. New examples of modal counterparts of intermediate predicate logics are given.

In §93 of The Principles of Mathematics, Bertrand Russell observes that “the variable is a very complicated logical entity, by no means easy to analyze correctly”. This assessment is borne out by the fact that even now we have no fully satisfactory understanding of the role of variables in a compositional semantics for first-order logic. In standard Tarskian semantics, variables are treated as meaning-bearing entities; moreover, they serve as the basic building blocks of all meanings, which are constructed out (...) of variable assignments. But this has disquieting consequences, including Fine’s antinomy of the variable and an undue dependence of meanings on language. Here I develop an alternative, Fregean version of predicate logic that uses the traditional quantifier–variable apparatus for the expression of generality, possesses a fully compositional, non-representational semantics, and is not subject to the antinomy of the variable. The advantages of Fregean over Tarskian predicate logic are due to the former’s treating variables not as meaningful lexical items, but as mere marks of punctuation, similar to parentheses. I submit that this is indeed how the variables of predicate logic should be construed. (shrink)

We discuss relationships among the existence property, the disjunction property, and their weak variants in the setting of intermediate predicate logics. We deal with the weak and sentential existence properties, and the Z-normality, which is a weak variant of the disjunction property. These weak variants were presented in the author’s previous paper [16]. In the present paper, the Kripke sheaf semantics is used.

This paper establishes model-theoretic properties of \, a variation of monadic first-order logic that features the generalised quantifier \. We will also prove analogous versions of these results in the simpler setting of monadic first-order logic with and without equality and \, respectively). For each logic \ we will show the following. We provide syntactically defined fragments of \ characterising four different semantic properties of \-sentences: being monotone and continuous in a given set of monadic predicates; having (...) truth preserved under taking submodels or being truth invariant under taking quotients. In each case, we produce an effectively defined map that translates an arbitrary sentence \ to a sentence \ belonging to the corresponding syntactic fragment, with the property that \ is equivalent to \ precisely when it has the associated semantic property. As a corollary of our developments, we obtain that the four semantic properties above are decidable for \-sentences. (shrink)

In this paper we study the notion of forcing for Łukasiewicz predicate logic (Ł∀, for short), along the lines of Robinson’s forcing in classical model theory. We deal with both finite and infinite forcing. As regard to the former we prove a Generic Model Theorem for Ł∀, while for the latter, we study the generic and existentially complete standard models of Ł∀.

Coherence with respect to Kelly–Mac Lane graphs is proved for categories that correspond to the multiplicative fragment without constant propositions of classical linear first-order predicate logic without or with mix. To obtain this result, coherence is first established for categories that correspond to the multiplicative conjunction–disjunction fragment with first-order quantifiers of classical linear logic, a fragment lacking negation. These results extend results of [K. Došen, Z. Petrić, Proof-Theoretical Coherence, KCL Publications , London, 2004 ; K. Došen, Z. (...) Petrić, Proof-Net Categories, Polimetrica, Monza, 2007 ], where coherence was established for categories of the corresponding fragments of propositional classical linear logic, which are related to proof nets, and which could be described as star-autonomous categories without unit objects. (shrink)

We show how to interpret intuitionistic propositional logic into a predicative second-order intuitionistic propositional system having only the conditional and the universal second-order quantifier. We comment on this fact. We argue that it supports the legitimacy of using classical logic in a predicative setting, even though the philosophical cast of predicativism is nonrealistic. We also note that the absence of disjunction and existential quantifications allows one to have a process of normalization of proofs that avoids the use of (...) "commuting conversions.". (shrink)