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)

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.

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)

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)

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)

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)

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.

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.

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)

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.

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)

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.

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)

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.

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.

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

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)

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.

D2.1 (PL models and assignments) i. A PL model is a pair M = 〈DM, ·M〉 such that (a) DM is a non-empty set, and (b) ·M maps each A ∈ Con to AM ∈ DM, and each B ∈ Prdn to BM  (DM)n. ii. GM = {g| g: Var  DM} is the set of M-assignments. For any g ∈ GM, u ∈ Var, d ∈ DM, g[u/d] := (g\{u, g(u)})  {u, d} is the u-to-d alternative to (...) g. (shrink)

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.

Providing more human-like concept learning in machines has always been one of the most significant goals of machine learning paradigms and of human-machine interaction techniques. This article attempts to provide a logical specification of conceptual mappings from humans’ minds into machines’ knowledge bases. We will focus on the representation of the mappings (transformations) relying on First-Order Predicate Logic. Additionally, the structure of concepts in the common ground between humans and machines will be analysed. It seems quite necessary to (...) pay attention to the philosophy of constructivism and constructivist models of knowing. This research constructs a conceptual ground for expressing and analysing concepts in the common ground between humanistic and informatics sciences and in the context of human-machine interplays. (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)

Noun phrases with overt determiners, such as <i>some apples</i> or <i>a quantity of milk</i>, differ from bare noun phrases like <i>apples</i> or <i>milk</i> in their contribution to aspectual composition. While this has been attributed to syntactic or algebraic properties of these noun phrases, such accounts have explanatory shortcomings. We suggest instead that the relevant property that distinguishes between the two classes of noun phrases derives from two modes of existential quantification, one of which holds the values of a variable fixed (...) throughout a quantificational context while the other allows them to vary. Inspired by Dynamic Plural Logic and Dependence Logic, we propose Plural Predicate Logic as an extension of Predicate Logic to formalize this difference. We suggest that temporal <i>for</i>-adverbials are sensitive to aspect because of the way they manipulate quantificational contexts, and that analogous manipulations occur with spatial <i>for</i>-adverbials, habituals, and the quantifier <i>all</i>. (shrink)

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)

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)

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)

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.

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)

What precisely are fragments of classical first-order logic showing “modal” behaviour? Perhaps the most influential answer is that of Gabbay 1981, which identifies them with so-called “finite-variable fragments”, using only some fixed finite number of variables (free or bound). This view-point has been endorsed by many authors (cf. van Benthem 1991). We will investigate these fragments, and find that, illuminating and interesting though they are, they lack the required nice behaviour in our sense. (Several new negative results support this (...) claim.) As a counterproposal, then, we define a large fragment of predicate logic characterized by its use of only bounded quantification. This so-called guarded fragment enjoys the above nice properties, including decidability, through an effectively bounded finite model property. (These are new results, obtained by generalizing notions and techniques from modal logic.) Moreover, its own internal finite variable hierarchy turns out to work well. Finally, we shall make another move. The above analogy works both ways. Modal operators are like quantifiers, but quantifiers are also like modal operators. This observation inspires a generalized semantics for first-order predicate logic with accessibility constraints on available assignments (cf. N´emeti 1986, 1992) which moves the earlier quantifier restrictions into the semantics. This provides a fresh look at the landscape of possible predicate logics, including candidates sharing various desirable features with basic modal logic – in particular, its decidability. (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)

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)

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

We prove that an intermediate predicate logic characterized by a class of finite partially ordered sets is recursively axiomatizable iff it is "finite", i.e., iff it is characterized by a single finite partially ordered set. Therefore, the predicate logic LFin of the class of all predicate Kripke frames with finitely many possible worlds is not recursively axiomatizable.