Michael Kremer defines fixed-point logics of truth based on Saul Kripke’s fixed point semantics for languages expressing their own truth concepts. Kremer axiomatizes the strong Kleene fixed-point logic of truth and the weak Kleene fixed-point logic of truth, but leaves the axiomatizability question open for the supervaluation fixed-point logic of truth and its variants. We show that the principal supervaluation fixed point logic of truth, (...) when thought of as consequence relation, is highly complex: it is not even analytic. We also consider variants, engendered by a stronger notion of ‘fixed point’, and by variant supervaluation schemes. A ‘logic’ is often thought of, not as a consequence relation, but as a set of sentences – the sentences true on each interpretation. We axiomatize the supervaluation fixed-point logics so conceived. (shrink)

We consider fixed point logics, i.e., extensions of first order predicate logic with operators defining fixed points. A number of such operators, generalizing inductive definitions, have been studied in the context of finite model theory, including nondeterministic and alternating operators. We review results established in finite model theory, and also consider the expressive power of the resulting logics on infinite structures. In particular, we establish the relationship between inflationary and nondeterministic fixed point logics and (...) second order logic, and we consider questions related to the determinacy of games associated with alternating fixed points. (shrink)

We study the system IFP of intuitionistic fixed point logic, an extension of intuitionistic first-order logic by strictly positive inductive and coinductive definitions. We define a realizability interpretation of IFP and use it to extract computational content from proofs about abstract structures specified by arbitrary classically true disjunction free formulas. The interpretation is shown to be sound with respect to a domain-theoretic denotational semantics and a corresponding lazy operational semantics of a functional language for extracted programs. (...) We also show how extracted programs can be translated into Haskell. As an application we extract a program converting the signed digit representation of real numbers to infinite Gray code from a proof of inclusion of the corresponding coinductive predicates. (shrink)

This is indeed a very nice draft that I have read with great pleasure, and that has helped me to better understand the completeness proof for LCC. Modal fixed point logic allows for an illuminating new version (and a further extension) of that proof. But still. My main comment is that I think the perspective on substitutions in the draft paper is flawed. The general drift of the paper is that relativization, (predicate) substitution and product update are (...) general operations on models, and that it is important to check whether given logical languages are closed under these operations. FO logic is closed under relativization, predicate substitution and product constructions (such as those involved in relative interpretation). The minimal modal logic is closed under relativization, which explains the reduction of epistemic logic (withhout common knowledge) + public announcement to epistemic logic simpliciter (as observed in Van Benthem, [2]). The reduction breaks down as soon as one adds common knowledge. The minimal modal logic is also closed under substitution, which explains the reduction of epistemic logic plus (publicly observable) factual change to epistemic logic simpliciter, via the following reduction axioms (I use !p := φ for the operation of publicly changing the truth value of p to φ): [!p := φ]p ↔ φ [!p := φ]q ↔ q (p and q syntactically different ) [!p := φ]¬ψ ↔ ¬[!p := φ]ψ [!p := φ](ψ1 ∧ ψ2) ↔ [!p := φ]ψ1 ∧ [!p := φ]ψ2 [!p := φ][i]ψ ↔ [i][!p := φ]ψ Unlike the case of relativisation, this can be extended to the case of epistemic logic with common knowledge, by means of: [!p := φ]CGψ ↔ CG[!p := φ]ψ We get the following.. (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)

We develop a variant of Least Fixed Point logic based on First Orderlogic with a relaxed version of guarded quantification. We develop aGame Theoretic Semantics of this logic, and find that under reasonableconditions, guarding quantification does not reduce the expressibilityof Least Fixed Point logic. But we also find that the guarded version ofa least fixed point algorithm may have a greater time complexity thanthe unguarded version, by a linear factor.

This paper considers standard completeness for fixed-pointed involutive micanorm-based logics. For this, we first discuss fixed-pointed involutive micanorm-based logics together with their algebraic semantics. Next, after introducing some examples of fixed-pointed involutive micanorms, we provide standard completeness results for those logics.

The paper presents a survey of author's results on definable fixed points in modal, temporal, and intuitionistic propositional logics. The well-known Fixed Point Theorem considers the modalized case, but here we investigate the positive case. We give a classification of fixed point theorems, describe some classes of models with definable least fixed points of positive operators, special positive operators, and give some examples of undefinable least fixed points. Some other interesting phenomena are discovered (...) – definability by formulas that do not preserve positivity of parameters and definability by finite sets of formulas. We also consider negative operators, graded modalities, construct undefinable inflationary fixed points, and put some problems. (shrink)

We study the relationship between least and inflationary fixed-point logic. In 1986, Gurevich and Shelah proved that in the restriction to finite structures, the two logics have the same expressive power. On infinite structures however, the question whether there is a formula in IFP not equivalent to any LFP-formula was left open.In this paper, we answer the question negatively, i.e. we show that the two logics are equally expressive on arbitrary structures. We give a syntactic translation of (...) IFP-formulae to LFP-formulae such that the two formulae are equivalent on all structures.As a consequence of the proof we establish a close correspondence between the LFP-alternation hierarchy and the IFP-nesting depth hierarchy. We also show that the alternation hierarchy for IFP collapses to the first level, i.e. the complement of any inflationary fixed point is itself an inflationary fixed point. (shrink)

The problem of Uniqueness and Explicit Definability of Fixed Points for Interpretability Logic is considered. It turns out that Uniqueness is an immediate corollary of a theorem of Smoryski.

This paper deals with the modal logics associated with (possibly nonstandard) provability predicates of Peano Arithmetic. One of our goals is to present some modal systems having the fixed point property and not extending the Gödel-Löb system GL. We prove that, for every has the explicit fixed point property. Our main result states that every complete modal logic L having the Craig's interpolation property and such that , where and are suitable modal formulas, has the (...) explicit fixed point property. (shrink)

Buchholz’s Ω μ+1-rules provide a major tool for the proof-theoretic analysis of arithmetical inductive definitions. The aim of this paper is to put this approach into the new context of modal fixed point logic. We introduce a deductive system based on an Ω-rule tailored for modal fixed point logic and develop the basic techniques for establishing soundness and completeness of the corresponding system. In the concluding section we prove a cut elimination and collapsing result (...) similar to that of Buchholz (Iterated inductive definitions and subsystems of analysis: recent proof theoretic studies. Lecture notes in mathematics, vol. 897, pp. 189–233, Springer, Berlin, 1981). (shrink)

The problem of Uniqueness and Explicit Definability of Fixed Points for Interpretability Logic is considered. It turns out that Uniqueness is an immediate corollary of a theorem of Smoryński.

We study a system, μŁΠ, obtained by an expansion of ŁΠ logic with fixed points connectives. The first main result of the paper is that μŁΠ is standard complete, i.e., complete with regard to the unit interval of real numbers endowed with a suitable structure. We also prove that the class of algebras which forms algebraic semantics for this logic is generated, as a variety, by its linearly ordered members and that they are precisely the interval algebras (...) of real closed fields. This correspondence is extended to a categorical equivalence between the whole category of those algebras and another category naturally arising from real closed fields. Finally, we show that this logic enjoys implicative interpolation. (shrink)

Reviewed Works:Dick de Jongh, Franco Montagna, Provable Fixed Points.Dick de Jongh, Franco Montagna, Much Shorter Proofs.Alessandra Carbone, Franco Montagna, Rosser Orderings in Bimodal Logics.Alessandra Carbone, Franco Montagna, Much Shorter Proofs: A Bimodal Investigation.

An algebraic proof is presented for the finite strong standard completeness of the Involutive Uninorm Logic with Fixed Point ($${{\mathbf {IUL}}^{fp}}$$ IUL fp ). It may provide a first step towards settling the standard completeness problem for the Involutive Uninorm Logic ($${\mathbf {IUL}}$$ IUL, posed in G. Metcalfe, F. Montagna. (J Symb Log 72:834–864, 2007)) in an algebraic manner. The result is proved via an embedding theorem which is based on the structural description of the class (...) of odd involutive FL$$_e$$ e -chains which have finitely many positive idempotent elements. (shrink)

Our purpose is to present some connections between modal incompleteness andmodal logics related to the Gödel-Löb logic GL. One of our goals is to prove that for all m, n, k, l ∈ ℕ the logic K + equation image□i □jp ↔ p) → equation image□ip is incomplete and does not have the fixed point property. As a consequence we shall obtain that the Boolos logic KH does not have the fixed point property.

In response to the liar’s paradox, Kripke developed the fixed-point semantics for languages expressing their own truth concepts. Kripke’s work suggests a number of related fixed-point theories of truth for such languages. Gupta and Belnap develop their revision theory of truth in contrast to the fixed-point theories. The current paper considers three natural ways to compare the various resulting theories of truth, and establishes the resulting relationships among these theories. The point is to (...) get a sense of the lay of the land amid a variety of options. Our results will also provide technical fodder for the methodological remarks of the companion paper to this one. (shrink)

In this paper, we study when a set-continuous operator has a fixed-point that is the intersection of a directed family. The framework of our study is the Kelley-Morse theory KMC– and the Gödel-Bernays theory GBC–, both theories including an Axiom of Choice and excluding the Axiom of Foundation. On the one hand, we prove a result concerning monotone operators in KMC– that cannot be proved in GBC–. On the other hand, we study conditions on directed superclasses in GBC– (...) in order that their intersection is a fixed-point of a set-continuous operator. Finally, we illustrate our results with a solution to the liar paradox and a construction of maximal bisimulations. (shrink)

This paper introduces a new kind of fixed-point semantics, filling a gap within approaches to Liar-like paradoxes involving fixed-point models à la Kripke (1975). The four-valued models presented below, (i) unlike the three-valued, consistent fixed-point models defined in Kripke (1975), are able to differentiate between paradoxical and pathological-but-unparadoxical sentences, and (ii) unlike the four-valued, paraconsistent fixed-point models first studied in Visser (1984) and Woodruff (1984), preserve consistency and groundedness of truth.

Within the technical frame supplied by the algebraic variety of diagonalizable algebras, defined by R. Magari in [2], we prove the following: Let T be any first-order theory with a predicate Pr satisfying the canonical derivability conditions, including Löb's property. Then any formula in T built up from the propositional variables $q,p_{1},...,p_{n}$ , using logical connectives and the predicate Pr, has the same "fixed-points" relative to q (that is, formulas $\psi (p_{1},...,p_{n})$ for which for all $p_{1},...,p_{n}\vdash _{T}\phi (\psi (p_{1},...,p_{n}),p_{1},...,p_{n})\leftrightarrow (...) \psi (p_{1},...,p_{n})$ ) of a formula $\phi ^{\ast}$ of the same kind, obtained from φ in an effective way. Moreover, such $\phi ^{\ast}$ is provably equivalent to the formula obtained from φ substituting with $\phi ^{\ast}$ itself all the occurrences of q which are under Pr. In the particular case where q is always under Pr in φ, $\phi ^{\ast}$ is the unique (up to provable equivalence) "fixed-point" of φ. Since this result is proved only assuming Pr to be canonical, it can be deduced that Löb's property is, in a sense, equivalent to Gödel's diagonalization lemma. All the results are proved more generally in the intuitionistic case. (shrink)

The relation between least and diagonal fixed points is a well known and completely studied question for a large class of partially ordered models of the lambda calculus and combinatory logic. Here we consider this question in the context of algebraic recursion theory, whose close connection with combinatory logic recently become apparent. We find a comparatively simple and rather weak general condition which suffices to prove the equality of least fixed points with canonical (corresponding to those (...) produced by the Curry combinator in lambda calculus) diagonal fixed points in a class of partially ordered algebras which covers both combinatory spaces of Skordev and operative spaces of Ivanov. Especially, this yields an essential improvement of the axiomatization of recursion theory via combinatory spaces. (shrink)

We give a characterization of the fixed points and of the lattices of fixed points of fuzzy Galois connections. It is shown that fixed points are naturally interpreted as concepts in the sense of traditional logic.

We present a quite simple proof of the fixed point theorem for GL. We also use this proof to show that Sambin's algorithm yields a fixed point.

In this paper it is shown that the intuitionistic fixed point theory equation image for α times iterated fixed points of strictly positive operator forms is conservative for negative arithmetic and equation image sentences over the theory equation image for α times iterated arithmetic comprehension without set parameters. This generalizes results previously due to Buchholz [5] and Arai [2].

In Aczel [1], the existence of largest fixed points of set continuous operators is proved assuming the schema version of dependent choices in Zermelo-Fraenkel set theory without the axiom of Foundation. In the present paper, we study whether the existence of largest fixed points of set continuous operators is provable without the schema version of dependent choices, using Boffa's weak antifoundation axioms.

In the context of his theory of numberings, Ershov showed that Kleene's recursion theorem holds for any precomplete numbering. We discuss various generalizations of this result. Among other things, we show that Arslanov's completeness criterion also holds for every precomplete numbering, and we discuss the relation with Visser's ADN theorem, as well as the uniformity or nonuniformity of the various fixed point theorems. Finally, we base numberings on partial combinatory algebras and prove a generalization of Ershov's theorem in (...) this context. (shrink)

We present a theory of stratified truth with a μ‐operator, where terms representing fixed points of stratified monotone operations are available. We prove that is relatively intepretable into Quine's (or subsystems thereof). The motivation is to investigate a strong theory of truth, which is consistent by means of stratification, i.e., by adopting an implicit type theoretic discipline, and yet is compatible with self‐reference (to a certain extent). The present version of is an enhancement of the theory presented in [2].

Self-referential sentences have troubled our understanding of language for centuries. The most famous self-referential sentence is probably the Liar, a sentence that says of itself that it is false. The Liar Paradox has encouraged many philosophers to establish theories of truth that manage to give a proper account of the truth predicate in a formal language. Kripke’s Fixed Point Theory from 1975 is one famous example of such a formal theory of truth that aims at giving a plausible (...) notion of truth by allowing truth value gaps. However, not only the concept of truth gives rise to paradoxes. A syntactical treatment of epistemic notions like belief and knowledge leads to contradictions that very much resemble the Liar Paradox. Therefore, it seems to be fruitful to apply the established theories of truth to epistemic concepts. In this paper, I will present one such attempt of solving the epistemic paradoxes: I adapt Kripke’s Fixed Point Theory and interpret truth, knowledge and belief within the framework of a partial logic. Thereby I find not only the fixed point of truth but also the fixed points of knowledge and belief. In this fixed point, the predicates of truth, belief and knowledge find their definite interpretation and the paradoxes are avoided. (shrink)

We prove an analogue of the fixed-point theorem for the case of definably amenable groups.

Taking Löb's Axiom in modal provability logic as a running thread, we discuss some general methods for extending modal frame correspondences, mainly by adding fixed-point operators to modal languages as well as their correspondence languages. Our suggestions are backed up by some new results – while we also refer to relevant work by earlier authors. But our main aim is advertizing the perspective, showing how modal languages with fixed-point operators are a natural medium to work (...) with. (shrink)

Jäger, G., Fixed points in Peano arithmetic with ordinals, Annals of Pure and Applied Logic 60 119-132. This paper deals with some proof-theoretic aspects of fixed point theories over Peano arithmetic with ordinals. It studies three such theories which differ in the principles which are available for induction on the natural numbers and ordinals. The main result states that there is a natural theory in this framework which is a conservative extension of Peano arithmeti.

This article defends the Fixed Point Thesis: that it is always a rational mistake to have false beliefs about the requirements of rationality. The Fixed Point Thesis is inspired by logical omniscience requirements in formal epistemology. It argues to the Fixed Point Thesis from the Akratic Principle: that rationality forbids having an attitude while believing that attitude is rationally forbidden. It then draws out surprising consequences of the Fixed Point Thesis, for instance (...) that certain kinds of a priori justification are indefeasible and that misleading all-things-considered evidence about rational requirements is impossible. Finally, the Fixed Point Thesis is applied to defend the Right Reasons position on peer disagreement, according to which an agent who has drawn the correct conclusion from her evidence should retain belief in that conclusion even in the face of disagreeing peers. (shrink)

There is a vibrant community among philosophical logicians seeking to resolve the paradoxes of classes, properties and truth by way of adopting some non-classical logic in which trivialising paradoxical arguments are not valid. There is also a long tradition in theoretical computer science|going back to Dana Scott's fixed point model construction for the untyped lambda-calculus of models allowing for fixed points. In this paper, I will bring these traditions closer together, to show how these model constructions (...) can shed light on what we could hope for in a non-trivial model of a theory for classes, properties or truth featuring fixed points. (shrink)

By an unfounded chain for a function f:X→X we mean a sequence nω of elements of X s.t. fxn+1=xn for every n. Unfounded chains can be regarded as a generalization of fixed points, but on the other hand are linked with concepts concerning non-well-founded situations, as ungrounded sentences and the hypergame. In this paper, among other things, we prove a lemma in general topology, we exhibit an extensional recursive function from the set of sentences of PA into itself without (...) an unfounded chain, and we prove that every term in a Magari algebra has an unfounded chain. (shrink)

We define infinitary extensions to classical epistemic logic systems, and add also a common belief modality, axiomatized in a finitary, fixed-point manner. In the infinitary K system, common belief turns to be provably equivalent to the conjunction of all the finite levels of mutual belief. In contrast, in the infinitary monotonic system, common belief implies every transfinite level of mutual belief but is never implied by it. We conclude that the fixed-point notion of common belief (...) is more powerful than the iterative notion of common belief. (shrink)