Kripke completeness of some infinitary predicate modal logics is presented. More precisely, we prove that if a normal modal logic above is -persistent and universal, the infinitary and predicate extension of with BF and BF is Kripke complete, where BF and BF denote the formulas pi pi and x x, respectively. The results include the completeness of extensions of standard modal logics such as , and its extensions by the schemata T, B, 4, 5, D, and their combinations. (...) The proof is obtained by extending the correspondence between the representation of modal algebras and the completeness of propositional modal logic to infinite. (shrink)

An interpolation Theorem is proved for first order logic with infinitary predicates. Our proof is algebraic via cylindric algebras.1.

If the language is extended by new individual variables, in classical first order logic, then the deduction system obtained is a conservative extension of the original one. This fails to be true for the logics with infinitary predicates. But it is shown that restricting the commutativity of quantifiers and the equality axioms in the extended system and supposing the merry-go-round property in the original system, the foregoing extension is already conservative. It is shown that these restrictions are crucial (...) for an extension to be conservative. The origin of the results is algebraic logic. (shrink)

How robust is a contraction-free approach to the semantic paradoxes? This paper aims to show some limitations with the approach based on multiplicative rules by presenting and discussing the significance of a revenge paradox using a predicate representing an alethic modality defined with infinitary rules.

We prove a completeness theorem for Kmath image, the infinitary extension of the graded version K0 of the minimal normal logic K, allowing conjunctions and disjunctions of countable sets of formulas. This goal is achieved using both the usual tools of the normal logics with graded modalities and the machinery of the predicate infinitary logics in a version adapted to modal logic.

In recent years much effort has gone into the study of languages which strengthen the classical first-order predicate calculus in various ways. This effort has been motivated by the desire to find a language which is(I) strong enough to express interesting properties not expressible by the classical language, but(II) still simple enough to yield interesting general results. Languages investigated include second-order logic, weak second-order logic, ω-logic, languages with generalized quantifiers, and infinitary logic.

In this paper we apply proof theoretic methods used for classical systems in order to obtain upper bounds for systems in partial logic. We focus on a truth predicate interpreted in a Kripke style way via strong Kleene; whereas the aim is to connect harmoniously the partial version of Kripke–Feferman with its intended semantics. The method we apply is based on infinitary proof systems containing an ω-rule.

Inspired by Pohlers' local predicativity approach to Pure Proof Theory and Howard's ordinal analysis of bar recursion of type zero we present a short, technically smooth and constructive strong normalization proof for Gödel's system T of primitive recursive functionals of finite types by constructing an ε 0 -recursive function [] 0 : T → ω so that a reduces to b implies [a] $_0 > [b]_0$ . The construction of [] 0 is based on a careful analysis of the Howard-Schütte (...) treatment of Gödel's T and utilizes the collapsing function ψ: ε 0 → ω which has been developed by the author for a local predicativity style proof-theoretic analysis of PA. The construction of [] 0 is also crucially based on ideas developed in the 1995 paper "A proof of strongly uniform termination for Gödel's T by the method of local predicativity" by the author. The results on complexity bounds for the fragments of T which are obtained in this paper strengthen considerably the results of the 1995 paper. Indeed, for given n let T n be the subsystem of T in which the recursors have type level less than or equal to n+2. (By definition, case distinction functionals for every type are also contained in T n .) As a corollary of the main theorem of this paper we obtain (reobtain?) optimal bounds for the T n -derivation lengths in terms of ω n+2 -descent recursive functions. The derivation lengths of type one functionals from T n (hence also their computational complexities) are classified optimally in terms of $ -descent recursive functions. In particular we obtain (reobtain?) that the derivation lengths function of a type one functional a ∈ T 0 is primitive recursive, thus any type one functional a in T 0 defines a primitive recursive function. Similarly we also obtain (reobtain?) a full classification of T 1 in terms of multiple recursion. As proof-theoretic corollaries we reobtain the classification of the IΣ n+1 -provably recursive functions. Taking advantage from our finitistic and constructive treatment of the terms of Gödel's T we reobtain additionally (without employing continuous cut elimination techniques) that PRA + PRWO ( $\varepsilon_0) \vdash \Pi^0_2$ - Refl(PA) and PRA + PRWO ( $\omega_{n+2}) \vdash \Pi^0_2$ - Refl(I Σ n+1 ), hence PRA + PRWO( $\epsilon_0) \vdash$ Con(PA) and PRA + PRWO( $\omega_{n+2}) \vdash$ Con(IΣ n+1 ). For programmatic reasons we outline in the introduction a vision of how to apply a certain type of infinitary methods to questions of finitary mathematics and recursion theory. We also indicate some connections between ordinals, term rewriting, recursion theory and computational complexity. (shrink)

The infinitary function of the truth predicate consists in its ability to express infinite conjunctions and disjunctions. A transparency principle for truth states the equivalence between a sentence and its truth predication; it requires an introduction principle—which allows the inference from “snow is white” to “the sentence ‘snow is white’ is true”—and an elimination principle—which allows the inference from “the sentence ‘snow is white’ is true” to “snow is white”. It is commonly assumed that a theory of truth needs (...) to satisfy a transparency principle to fulfil the infinitary function. Picollo and Schindler (Erkenntnis 83:899–928, 2017) argue against this idea. They prove that, given certain assumptions, an elimination principle is sufficient for the purpose. Then, they pose a challenge: to show why we should incorporate introduction principles to our theory of truth. In this essay I take on the challenge. I show that, given the authors’ assumptions, an introduction principle is also sufficient to perform the infinitary function. (shrink)

Inspired by Pohlers' local predicativity approach to Pure Proof Theory and Howard's ordinal analysis of bar recursion of type zero we present a short, technically smooth and constructive strong normalization proof for Godel's system T of primitive recursive functionals of finite types by constructing an $\varepsilon_0$-recursive function [ ]$_0$: T $\rightarrow \omega$ so that a reduces to b implies [a]$_0 > [b]_0$. The construction of [ ]$_0$ is based on a careful analysis of the Howard-Schutte treatment of Godel's T and (...) utilizes the collapsing function $\psi: \varepsilon_0 \rightarrow \omega$ which has been developed by the author for a local predicativity style proof-theoretic analysis of PA. The construction of []$_0$ is also crucially based on ideas developed in the 1995 paper "A proof of strongly uniform termination for Godel's T by the method of local predicativity" by the author. The results on complexity bounds for the fragments of T which are obtained in this paper strengthen considerably the results of the 1995 paper. Indeed, for given n let T$_n$ be the subsystem of T in which the recursors have type level less than or equal to n+2. As a corollary of the main theorem of this paper we obtain optimal bounds for the T$_n$-derivation lengths in terms of $\omega_{n+2}$-descent recursive functions. The derivation lengths of type one functionals from T$_n$ are classified optimally in terms of $< \omega_{n+2}$-descent recursive functions. In particular we obtain that the derivation lengths function of a type one functional a $\in T_0$ is primitive recursive, thus any type one functional a in T$_0$ defines a primitive recursive function. Similarly we also obtain a full classification of T$_1$ in terms of multiple recursion. As proof-theoretic corollaries we reobtain the classification of the I$\Sigma_{n+1}$-provably recursive functions. Taking advantage from our finitistic and constructive treatment of the terms of Godel's T we reobtain additionally that PRA + PRWO \vdash \Pi^0_2$ - Refl and PRA + PRWO \vdash \Pi^0_2$ - Refl, hence PRA + PRWO \vdash$ Con and PRA + PRWO \vdash$ Con$. For programmatic reasons we outline in the introduction a vision of how to apply a certain type of infinitary methods to questions of finitary mathematics and recursion theory. We also indicate some connections between ordinals, term rewriting, recursion theory and computational complexity. (shrink)

In “Properties and the Interpretation of Second-Order Logic” Bob Hale develops and defends a deflationary conception of properties where a property with particular satisfaction conditions actually exists if and only if it is possible that a predicate with those same satisfaction conditions exists. He argues further that, since our languages are finitary, there are at most countably infinitely many properties and, as a result, the account fails to underwrite the standard semantics for second-order logic. Here a more lenient version of (...) the view is explored, which allows for the possibility of countably infinite predicates understood as the product of linguistic supertasks. This enriched deflationist account of properties—the Infinitary Deflationary Conception of Existence—supports the standard semantics for models with countable first-order domains, and allows one to prove the categoricity of the second-order Peano axioms. (shrink)

In this paper we apply proof theoretic methods used for classical systems in order to obtain upper bounds for systems in partial logic. We focus on a truth predicate interpreted in a Kripke style way via strong Kleene; whereas the aim is to connect harmoniously the partial version of Kripke–Feferman with its intended semantics. The method we apply is based on infinitary proof systems containing an ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\omega $$\end{document}-rule.

Aim of this work is to investigate from a proof-theoretic viewpoint a propositional and a predicate sequent calculus with an ω–type schema of inference that naturally interpret the propositional and the predicate until–free fragments of Linear Time Logic LTL respectively. The two calculi are based on a natural extension of ordinary sequents and of standard modal rules. We examine the pure propositional case (no extralogical axioms), the propositional and the first order predicate cases (both with a possibly infinite set of (...) extralogical axioms). For each system we provide a syntactic proof of cut elimination and a proof of completeness. (shrink)

We shall prove that if a model of cardinality κ can be expanded to a model of a sentence ψ of Lλ+,ω by adding a suitable predicate in more than κ ways, then, it has a submodel of power μ which can be expanded to a model of ψ in $> \mu$ ways provided that λ,κ,μ satisfy suitable conditions.

We give an extension of the Jónsson‐Tarski representation theorem for both normal and non‐normal modal algebras so that it preserves countably many infinite meets and joins. In order to extend the Jónsson‐Tarski representation to non‐normal modal algebras we consider neighborhood frames instead of Kripke frames just as Došen's duality theorem for modal algebras, and to deal with infinite meets and joins, we make use of Q‐filters, which were introduced by Rasiowa and Sikorski, instead of prime filters. By means of the (...) extended representation theorem, we show that every predicate modal logic, whether it is normal or non‐normal, has a model defined on a neighborhood frame with constant domains, and we give a completeness theorem for some predicate modal logics with respect to classes of neighborhood frames with constant domains. Similarly, we show a model existence theorem and a completeness theorem for infinitary modal logics which allow conjunctions of countably many formulas. (shrink)

This paper provides a logic framework for investigations of game theoretical problems. We adopt an infinitary extension of classical predicate logic as the base logic of the framework. The reason for an infinitary extension is to express the common knowledge concept explicitly. Depending upon the choice of axioms on the knowledge operators, there is a hierarchy of logics. The limit case is an infinitary predicate extension of modal propositional logic KD4, and is of special interest in applications. (...) In Part I, we develop the basic framework, and show some applications: an epistemic axiomatization of Nash equilibrium and formal undecidability on the playability of a game. To show the formal undecidability, we use a term existence theorem, which will be proved in Part II. (shrink)

The infinitary languages studied in this book are those in which quantification of infinitely many variables simultaneously, and conjunctions or alternations of infinitely many are permitted. Infinitary concatenation and infinitary propositional logics are first discussed, and a completeness theorem is proved about the latter. The later chapters deal with infinitary predicate languages and Scott's proof of incompleteness is introduced. Throughout the discussion, unsolved problems are mentioned and areas undergoing current development are emphasized. A short bibliography lists (...) most recent articles on this new branch of logic.—P. J. M. (shrink)

We introduce a framework for a graph-theoretic analysis of the semantic paradoxes. Similar frameworks have been recently developed for infinitary propositional languages by Cook and Rabern, Rabern, and Macauley. Our focus, however, will be on the language of first-order arithmetic augmented with a primitive truth predicate. Using Leitgeb’s notion of semantic dependence, we assign reference graphs (rfgs) to the sentences of this language and define a notion of paradoxicality in terms of acceptable decorations of rfgs with truth values. It (...) is shown that this notion of paradoxicality coincides with that of Kripke. In order to track down the structural components of an rfg that are responsible for paradoxicality, we show that any decoration can be obtained in a three-stage process: first, the rfg is unfolded into a tree, second, the tree is decorated with truth values (yielding a dependence tree in the sense of Yablo), and third, the decorated tree is re-collapsed onto the rfg. We show that paradoxicality enters the picture only at stage three. Due to this we can isolate two basic patterns necessary for paradoxicality. Moreover, we conjecture a solution to the characterization problem for dangerous rfgs that amounts to the claim that basically the Liar- and the Yablo graph are the only paradoxical rfgs. Furthermore, we develop signed rfgs that allow us to distinguish between ‘positive’ and ‘negative’ reference and obtain more fine-grained versions of our results for unsigned rfgs. (shrink)

The class forcing theorem, which asserts that every class forcing notion ${\mathbb {P}}$ admits a forcing relation $\Vdash _{\mathbb {P}}$, that is, a relation satisfying the forcing relation recursion—it follows that statements true in the corresponding forcing extensions are forced and forced statements are true—is equivalent over Gödel–Bernays set theory $\text {GBC}$ to the principle of elementary transfinite recursion $\text {ETR}_{\text {Ord}}$ for class recursions of length $\text {Ord}$. It is also equivalent to the existence of truth predicates for (...) the infinitary languages $\mathcal {L}_{\text {Ord},\omega }$, allowing any class parameter A; to the existence of truth predicates for the language $\mathcal {L}_{\text {Ord},\text {Ord}}$ ; to the existence of $\text {Ord}$ -iterated truth predicates for first-order set theory $\mathcal {L}_{\omega,\omega }$ ; to the assertion that every separative class partial order ${\mathbb {P}}$ has a set-complete class Boolean completion; to a class-join separation principle; and to the principle of determinacy for clopen class games of rank at most $\text {Ord}+1$. Unlike set forcing, if every class forcing notion ${\mathbb {P}}$ has a forcing relation merely for atomic formulas, then every such ${\mathbb {P}}$ has a uniform forcing relation applicable simultaneously to all formulas. Our results situate the class forcing theorem in the rich hierarchy of theories between $\text {GBC}$ and Kelley–Morse set theory $\text {KM}$. (shrink)

In this paper, we give a constructive nonstandard model of intuitionistic arithmetic (Heyting arithmetic). We present two axiomatisations of the model: one finitary and one infinitary variant. Using the model these axiomatisations are proven to be conservative over ordinary intuitionistic arithmetic. The definition of the model along with the proofs of its properties may be carried out within a constructive and predicative metatheory (such as Martin-Löf's type theory). This paper gives an illustration of the use of sheaf semantics to (...) obtain effective proof-theoretic results.The axiomatisations of nonstandard intuitionistic arithmetic (to be calledHAIandHAIωrespectively) as well as their model are based on the construction in [5] of a sheaf model for arithmetic using a site of filters. In this paper we present a “minimal” version of this model, built instead on a suitable site of provable filter bases. The construction of this site can be viewed as an extension of the well-known construction of the classifying topos for a geometric theory which uses “syntactic sites”. (Such sites can in fact be used to prove semantical completeness of first order logic in a strictly constructive framework, see [6].)We should mention that for classical nonstandard arithmetics there are several nonconstructive methods of proving conservativity over arithmetic, e.g. the compactness theorem, Mac Dowell–Specker's theorem [3]. (shrink)

In this paper, we give a constructive nonstandard model of intuitionistic arithmetic (Heyting arithmetic). We present two axiomatisations of the model: one finitary and one infinitary variant. Using the model these axiomatisations are proven to be conservative over ordinary intuitionistic arithmetic. The definition of the model along with the proofs of its properties may be carried out within a constructive and predicative metatheory (such as Martin-Löf's type theory). This paper gives an illustration of the use of sheaf semantics to (...) obtain effective proof-theoretic results.The axiomatisations of nonstandard intuitionistic arithmetic (to be calledHAIandHAIωrespectively) as well as their model are based on the construction in [5] of a sheaf model for arithmetic using a site of filters. In this paper we present a “minimal” version of this model, built instead on a suitable site of provable filter bases. The construction of this site can be viewed as an extension of the well-known construction of the classifying topos for a geometric theory which uses “syntactic sites”. (Such sites can in fact be used to prove semantical completeness of first order logic in a strictly constructive framework, see [6].)We should mention that for classical nonstandard arithmetics there are several nonconstructive methods of proving conservativity over arithmetic, e.g. the compactness theorem, Mac Dowell–Specker's theorem [3]. (shrink)

In 1969, De Jongh proved the “maximality” of a fragment of intuitionistic predicate calculus forHA. Leivant strengthened the theorem in 1975, using proof-theoretical tools (normalisation of infinitary sequent calculi). By a refinement of De Jongh's original method (using Beth models instead of Kripke models and sheafs of partial combinatory algebras), a semantical proof is given of a result that is almost as good as Leivant's. Furthermore, it is shown thatHA can be extended to Higher Order Heyting Arithmetic+all trueΠ 2 (...) 0 -sentences + transfinite induction over primitive recursive well-orderings. As a corollary of the proof, maximality of intuitionistic predicate calculus is established wrt. an abstract realisability notion defined over a suitable expansion ofHA. (shrink)

We prove an institutional version of A. Robinson ’s Consistency Theorem. This result is then appliedto the institution of many-sorted first-order predicate logic and to two of its variations, infinitary and partial, obtaining very general syntactic criteria sufficient for a signature square in order to satisfy the Robinson consistency and Craig interpolation properties.

We present an alternative solution to the problem of inductive generation of covers in formal topology by using a restricted form of type universes. These universes are at the same time constructive analogues of regular cardinals and sets of infinitary formulae. The technique of regular universes is also used to construct canonical positivity predicates for inductively generated covers.

We introduce the notion of infinitary preorder and use it to obtain a predicative presentation of sup-lattices by generators and relations. The method is uniform in that it extends in a modular way to obtain a presentation of quantales, as “sup-lattices on monoids”, by using the notion of pretopology.Our presentation is then applied to frames, the link with Johnstone’s presentation of frames is spelled out, and his theorem on freely generated frames becomes a special case of our results on (...) quantales.The main motivation of this paper is to contribute to the development of formal topology. That is why all our definitions and proofs can be expressed within an intuitionistic and predicative foundation, like constructive type theory. (shrink)

We generalize ordinary register machines on natural numbers to machines whose registers contain arbitrary ordinals. Ordinal register machines are able to compute a recursive bounded truth predicate on the ordinals. The class of sets of ordinals which can be read off the truth predicate satisfies a natural theory SO. SO is the theory of the sets of ordinals in a model of the Zermelo-Fraenkel axioms ZFC. This allows the following characterization of computable sets: a set of ordinals is ordinal register (...) computable if and only if it is an element of Gödel’s constructible universe L. (shrink)

We describe a short model-theoretic proof of an extended normal form theorem for derivations in predicate logic which implies in PRA a normal form theorem for the arithmetic derivations . Consider the Gentzen-type formulation of predicate logic with invertible rules. A derivation with proper variables is one where a variable b can occur in the premiss of an inference L but not below this premiss only in the case when L is () or () and b is its eigenvariable. Free (...) variables of such derivation are eigenvariables and free variables of its last sequent. Then any sequent derivable in predicate logic has a cut-free derivation with proper variables where the main formula of any antecedent rule is underivable. The proof is by a simple modification of the construction of a countermodel of the formula from the open branch of its canonical proof-search tree. It extends to intuitionistic and higher order systems. The proof of the corresponding normalization theorem outlined in [8] uses the passage to the infinitary derivations enriched by finitary derivations. The normal form after a modification to make it decidable can be considered as a realization of Gentzen's idea stated at the end of [2], that his notion of reduction for arithmetic can be extended to other fields of mathematics. (shrink)

We study the expressive power in the finite of the logic Fixed-Point+Counting, the extension of first-order logic which is obtained through adding both the fixed-point constructor and the ability to count. To this end an isomorphism preserving (`generic') model of computation is introduced whose PTime restriction exactly corresponds to this level of expressive power, while its PSpace restriction corresponds to While+Counting. From this model we obtain a normal form which shows a rather clear separation of the relational vs. the arithmetical (...) side of the algorithms involved. In parallel, we study the relations of Fixed-Point+Counting with the infinitary logics L r ∞ω (∃ ≥ m ) m∈ω and the corresponding pebble games. The main result, however, involves the concept of an arithmetical invariant. By this we mean a functor taking every finite relational structure to an expansion of (an initial segment of) the standard arithmetical structure. In particular its values are linearly ordered structures. We establish the existence of a family of arithmetical invariants (J r ) r≥ 1 with the following properties: $\bullet$ The invariants themselves can be evaluated in polynomial time. $\bullet$ A class of finite relational structures is definable in Fixed-Point+Counting if and only if membership can be decided in polynomial time on the basis of the values of one of the invariants. $\bullet$ The invariant J r classifies all finite relational structures exactly up to equivalence with respect to the logic L r ∞ω (∃ ≥ m ) m∈ω . We also give a characterization of Fixed-Point+Counting in terms of sequences of formulae in the L r ωω (∃ ≥ m ) m∈ω : It corresponds exactly to the polynomial time computable families (φ n ) n∈ω in these logics. Towards a positive assessment of the expressive power of Fixed-Point+Counting, it is shown that the natural extension of fixed-point logic by Lindström quantifiers, which capture all the PTime computable properties of cardinalities of definable predicates, is strictly weaker than what we get here. This implies in particular that every extension of fixed-point logic by means of monadic Lindstrom quantifiers, which stays within PTime, must be strictly contained in Fixed-Point+Counting. (shrink)

If one regards an ordinal number as a generalization of a counting number, then it is natural to begin thinking in terms of computations on sets of ordinal numbers. This is precisely what Takeuti [22] had in mind when he initiated the study of recursive functions on ordinals. Kreisel and Sacks [9] too developed an ordinal recursion theory, called metarecursion theory, which specialized to the initial segment of the ordinals bounded by.The notion of admissibility was introduced by Kripke [11] and (...) Platek [14] and served to generalize metarecursion theory. Kripke called ordinal α admissible if it satisfied certain closure properties of infinitary computations. It was shown that admissibility could be equivalently formulated in terms of the replacement schema of ZF set theory and that α =is an admissible ordinal. The study of a recursion theory on an initial segment of the ordinals bounded by some arbitrary admissible α became known as α-recursion theory.Kripke [10] employed a Gödel numbering scheme to perform an arithmetiza-tion of α -recursion theory and created an analogue to Kleene'sT-predicate of ordinary recursion theory. TheT-predicate then served as the basis for showing that analogues of the major results of unrelativized o.r.t. held in α-recursion theory; namely, the α-Enumeration Theorem,T Theorem, α-Recursion Theorem, and α-Universal Function Theorem. (shrink)

A game for testing the equivalence of Kripke models with respect to finitary and infinitary intuitionistic predicate logic is introduced and applied to discuss a concept of categoricity for intuitionistic theories.

In order to capture the concept of common knowledge, various extensions of multi-modal epistemic logics, such as fixed-point ones and infinitary ones, have been proposed. Although we have now a good list of such proposed extensions, the relationships among them are still unclear. The purpose of this paper is to draw a map showing the relationships among them. In the propositional case, these extensions turn out to be all Kripke complete and can be comparable in a meaningful manner. F. (...) Wolter showed that the predicate extension of the Halpern-Moses fixed-point type common knowledge logic is Kripke incomplete. However, if we go further to an infinitary extension, Kripke completeness would be recovered. Thus there is some gap in the predicate case. In drawing the map, we focus on what is happening around the gap in the predicate case. The map enables us to better understand the common knowledge logics as a whole. (shrink)