We give alternative characterizations of exact, extendible and projective formulas in intuitionistic propositional calculus IPC in terms of n-universal models. From these characterizations we derive a new syntactic description of all extendible formulas of IPC in two variables. For the formulas in two variables we also give an alternative proof of Ghilardi’s theorem that every extendible formula is projective.

We give alternative characterizations of exact, extendible and projective formulas in intuitionistic propositional calculus IPC in terms of n -universal models. From these characterizations we derive a new syntactic description of all extendible formulas of IPC in two variables. For the formulas in two variables we also give an alternative proof of Ghilardi’s theorem that every extendible formula is projective.

In 1995 Visser, van Benthem, de Jongh, and Renardel de Lavalette introduced NNIL-formulas, showing that these are exactly the formulas preserved under taking submodels of Kripke models. In this article we show that NNIL-formulas are up to frame equivalence the formulas preserved under taking subframes of frames, that NNIL-formulas are subframe formulas, and that subframe logics can be axiomatized by NNIL-formulas. We also define a new syntactic class of ONNILLI-formulas. We show that (...) these are the formulas preserved in monotonic images of frames and that ONNILLI-formulas are stable formulas as introduced by Bezhanishvili and Bezhanishvili in 2013. Thus, ONNILLI is a syntactically defined set of formulas axiomatizing all stable logics. This resolves a problem left open in 2013. (shrink)

Here, we provide a detailed description of the mutual relation of formulas with finite propositional variables p1, …, pm in modal logic S4. Our description contains more information on S4 than those given in Shehtman (1978) and Moss (2007); however, Shehtman (1978) also treated Grzegorczyk logic and Moss (2007) treated many other normal modal logics. Specifically, we construct normal forms, which behave like the principal conjunctive normal forms in the classical propositional logic. The results include finite and effective methods (...) to find a normal form equivalent to a given formula A by clarifying the behavior of connectives and giving a finite method to list all exact models. (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)

Akama et al. [1] introduced a hierarchical classification of first-order formulas for a hierarchical prenex normal form theorem in semi-classical arithmetic. In this paper, we give a justification for the hierarchical classification in a general context of first-order theories. To this end, we first formalize the standard transformation procedure for prenex normalization. Then we show that the classes $$\textrm{E}_k$$ and $$\textrm{U}_k$$ introduced in [1] are exactly the classes induced by $$\Sigma _k$$ and $$\Pi _k$$ respectively via the transformation procedure (...) in any first-order theory. (shrink)

In [60] N. Belnap presented an 8-element matrix for the relevant logic R with the following property: if in an implication A → B the formulas A and B do not have a common variable then there exists a valuation v such that v(A → B) does not belong to the set of designated elements of this matrix. A 6-element matrix of this kind can be found in: R. Routley, R.K. Meyer, V. Plumwood and R.T. Brady [82]. Below we (...) prove that the logics generated by these two matrices are the only maximal extensions of the relevant logic R which have the relevance property: if A → B is provable in such a logic then A and B have a common propositional variable. (shrink)

Normal forms for wide classes of closed IL formulas were given in Čačić and Vuković. Here we quantify asymptotically, in exact numbers, how wide those classes are. As a consequence, we show that the “majority” of closed IL formulas have GL-equivalents, and by that, they have the same normal forms as GL formulas. Our approach is entirely syntactical, except for applying the results of Čačić and Vuković. As a byproduct we devise a convenient way of computing (...) asymptotic behaviors of somewhat general classes of formulas given by their grammar rules. Its applications do not require any knowledge of the recurrence relations, generating functions, or the asymptotic enumeration methods, as all these are incorporated into two fundamental parameters. (shrink)

We show that the variety of Heyting algebras has finitary unification type. We also show that the subvariety obtained by adding it De Morgan law is the biggest variety of Heyting algebras having unitary unification type. Proofs make essential use of suitable characterizations (both from the semantic and the syntactic side) of finitely presented projective algebras.

In this work we propose the partial Wiener index as one possible measure of branching in phylogenetic evolutionary trees. We establish the connection between the generalized Robinson–Foulds (RF) metric for measuring the similarity of phylogenetic trees and partial Wiener indices by expressing the number of conflicting pairs of edges in the generalized RF metric in terms of partial Wiener indices. To do so we compute the minimum and maximum value of the partial Wiener index WT,r,n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} (...) \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$W\left(T,r, n\right)$$\end{document}, where T\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T$$\end{document} is a binary rooted tree with root r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r$$\end{document} and n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document} leaves. Moreover, under the Yule probabilistic model, we show how to compute the expected value of WT,r,n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$W\left(T,r, n\right)$$\end{document}. As a direct consequence, we give exact formulas for the upper bound and the expected number of conflicting pairs. By doing so we provide a better theoretical understanding of the computational complexity of the generalized RF metric. (shrink)

We focus on the dichotomous choice model, which goes back as far as Condorcet (1785; Essai sur l'application de l'analyse a la probabilité des décisions rendues a la pluralité des voix, Paris). A group of experts is required to select one of two alternatives, of which exactly one is regarded as correct. The alternatives may be related to a wide variety of areas. A decision rule translates the individual opinions of the members into a group decision. A decision rule is (...) optimal if it maximizes the probability of the group to make a correct choice. In this paper we assume the correctness probabilities of the experts to be independent random variables, selected from some given distribution. Moreover, the ranking of the members in the team is (at least partly) known. Thus, one can follow rules based on this ranking. The polar different rules are the expert and the majority rules. The probabilities of the two polar rules being optimal were compared in a series of papers. The main purpose of this paper is to outline the results, providing exact formulas or estimates for these probabilities. We consider a variety of distributions and show that for all of these distributions the asymptotic behaviour of the probabilities of the two polar rules follows the same patterns. (shrink)

I develop a notion of nonlinear stochastic integrals for hyperfinite Lévy processes and use it to find exact formulas for expressions which are intuitively of the form $\sum_{s=0}^t\phi(\omega,dl_{s},s)$ and $\prod_{s=0}^t\psi(\omega,dl_{s},s)$ , where l is a Lévy process. These formulas are then applied to geometric Lévy processes, infinitesimal transformations of hyperfinite Lévy processes, and to minimal martingale measures. Some of the central concepts and results are closely related to those found in S. Cohen’s work on stochastic calculus for (...) processes with jumps on manifolds, and the paper may be regarded as a reworking of his ideas in a different setting and with totally different techniques. (shrink)

A well-known open problem in epistemic logic is to give a syntactic characterization of the successful formulas. Semantically, a formula is successful if and only if for any pointed model where it is true, it remains true after deleting all points where the formula was false. The classic example of a formula that is not successful in this sense is the “Moore sentence” p ∧ ¬BOXp, read as “p is true but you do not know p.” Not only is (...) the Moore sentence unsuccessful, it is self-refuting, for it never remains true as described. We show that in logics of knowledge and belief for a single agent (extended by S5), Moorean phenomena are the source of all self-refutation; moreover, in logics for an introspective agent (extending KD45), Moorean phenomena are the source of all unsuccessfulness as well. This is a distinctive feature of such logics, for with a non-introspective agent or multiple agents, non-Moorean unsuccessful formulas appear. We also consider how successful and self-refuting formulas relate to the Cartesian and learnable formulas, which have been discussed in connection with Fitch’s “paradox of knowability.” We show that the Cartesian formulas are exactly the formulas that are not eventually self-refuting and that not all learnable formulas are successful. In an appendix, we give syntactic characterizations of the successful and the self-refuting formulas. (shrink)

ABSTRACT The Gödel–Dummett logic and Łukasiewicz one are two main many-valued logics used by the fuzzy logic community. Our goal is a quantitative comparison of these two. In this paper, we will mostly consider the 3-valued Gödel–Dummett logic as well as the 3-valued Łukasiewicz one. We shall concentrate on their implicational-negation fragments which are limited to formulas formed with a fixed finite number of variables. First, we investigate the proportion of the number of true formulas of a certain (...) length n to the number of all formulas of such length built with exactly one variable. Then, we investigate such proportion for satisfiable formulas. Second, we generalise our investigation on formulas written with $ k\ge 1 $ k ≥ 1 variables. The primary goal of the paper is the research on the asymptotic behaviour of these fractions when the length n tends to infinity. If such limits exists, they are real numbers between 0 and 1, which are called the density of truth or the density of SAT. To compare the density of truth and the density of satisfiable formulas for both fragments of 3-valued Gödel–Dummett's and Łukasiewicz's logics we use the powerful theory of analytic combinatorics. This paper is a natural continuation of the previous brief conference note by Kostrzycka and Zaionc (2020) as well as enriched with some previous results from Kostrzycka and Zaionc (2003). In the conference note we computed analytically the density of truth and the density of SAT (with a determined precision) for 3-valued Łukasiewicz's logic restricted to a language with only one variable. In Kostrzycka and Zaionc (2003) we computed the same values for exactly the same fragment of the 3-valued Gödel–Dummett logic. This paper answers the more general questions of the existence of density of truth and density of SAT for both many-valued logics with an arbitrary finite number of variables. Therefore this paper gives an an interesting picture of two main families of finite-valued fuzzy logics problems treated quantitatively. This picture is taken from the perspective of classical logic. It shows that unexpectedly there is quantitatively a little distance between these two approaches. (shrink)

In mathematical practice certain formulas φ are believed to essentially decide all other natural properties of the object x. The purpose of this paper is to exactly quantify such a belief for four formulas φ, namely “x is a Ramsey ultrafilter”, “x is a free Souslin tree”, “x is an extendible strong Lusin set” and “x is a good diamond sequence”.

Predicate modal formulas with non-modalized quantifiers (call them Q-formulas) are considered as schemata of arithmetical formulas, where is interpreted as the provability predicate of some fixed correct extension T of arithmetic. A method of constructing 1) non-provable in T and 2) false arithmetical examples for Q-formulas by Kripke-like countermodels of certain type is given. Assuming the means of T to be strong enough to solve the (undecidable) problem of derivability in QGL, the Q-fragment of the predicate (...) version of the logic GL, we prove the recursive enumerability of the sets of Q-formulas all arithmetical examples of which are: 1) T-provable, 2) true. In. particular, the first one is shown to be exactly QGL and the second one to be exactly the Q-fragment of the predicate version of Solovay's logic S. (shrink)

We present an axiomatization for Basic Propositional Calculus BPC and give a completeness theorem for the class of transitive Kripke structures. We present several refinements, including a completeness theorem for irreflexive trees. The class of intermediate logics includes two maximal nodes, one being Classical Propositional Calculus CPC, the other being E1, a theory axiomatized by T → ⊥. The intersection CPC ∩ E1 is axiomatizable by the Principle of the Excluded Middle A V ∨ ⌝A. If B is a formula (...) such that → B is not derivable, then the lattice of formulas built from one propositional variable p using only the binary connectives, is isomorphically preserved if B is substituted for p. A formula → B is derivable exactly when B is provably equivalent to a formula of the form → A) →. (shrink)

In theTractatus, Wittgenstein advocates two major notational innovations in logic. First, identity is to be expressed by identity of the sign only, not by a sign for identity. Secondly, only one logical operator, called “N” by Wittgenstein, should be employed in the construction of compound formulas. We show that, despite claims to the contrary in the literature, both of these proposals can be realized, severally and jointly, in expressively complete systems of first-order logic. Building on early work of Hintikka’s, (...) we identify three ways in which the first notational convention can be implemented, show that two of these are compatible with the text of theTractatus, and argue on systematic and historical grounds, adducing posthumous work of Ramsey’s, for one of these as Wittgenstein’s envisaged method. With respect to the second Tractarian proposal, we discuss how Wittgenstein distinguished between general and non-general propositions and argue that, claims to the contrary notwithstanding, an expressively adequate N-operator notation is implicit in theTractatuswhen taken in its intellectual environment. We finally introduce a variety of sound and complete tableau calculi for first-order logics formulated in a Wittgensteinian notation. The first of these is based on the contemporary notion of logical truth as truth in all structures. The others take into account the Tractarian notion of logical truth as truth in all structures over one fixed universe of objects. Here the appropriate tableau rules depend on whether this universe is infinite or finite in size, and in the latter case on its exact finite cardinality.As it is obviously easy to express how propositions can be constructed by means of this operation and how propositions are not to be constructed by means of it, this must be capable of exact expression.5.503. (shrink)

In this paper, I will describe a technique for generating a novel kind of semantics for a logic, and explore some of its consequences. It would be natural to call the semantics produced by the technique in question ‘many-valued'; but that name is, of course, already taken. I call them, instead, ‘plurivalent'. In standard logical semantics, formulas take exactly one of a bunch of semantic values. I call such semantics ‘univalent'. In a plurivalent semantics, by contrast, formulas may (...) take one or more such values. The construction I shall describe can be applied to any univalent semantics to produce a corresponding plurivalent one. In the paper I will be concerned with the application of the technique to propositional many-valued logics. Sometimes going plurivalent does not change the consequence relation; sometimes it does. I investigate the possibilities in detail with respect to small family of many-valued logics. (shrink)

Although we believe the results reported below to have direct philosophical import, we shall for the most part confine our remarks to the realm of mathematics. The reader is referred to [4] for a philosophically oriented discussion, comprehensible to mathematicians, of tense logic.The “minimal” tense logicT0is the system having connectives ∼, →,F(“at some future time”), andP(“at some past time”); the following axioms:(whereGandHabbreviate ∼F∼ and ∼P∼ respectively); and the following rules:(8) fromαandα → β, inferβ,(9) fromα, infer any substitution instance ofα,(10) fromα, (...) inferGα,(11) fromα, inferHα.A tense logic is a systemTwhose language is that ofT0and whose axioms and rules include (1)–(11). The axioms and rules ofTother than (1)–(11) are calledproperaxioms and rules.We shall investigate three systems of semantics for tense logics, i.e. three notions ofstructureand three relations ⊧ which stand between structures and formulas. One reads⊧αas “αis valid in.” A structureis amodelof a tense logicTif every formula provable inTis valid in. A semantics isadequateforTif the set of models ofTin the semantics is characteristic forT, i.e. if wheneverT ∀ αthen there is a modelofTin the semantics such that∀ α. Two structuresand, possibly from different semantics, are calledequivalent(∼) if exactly the same formulas are valid inas in. (shrink)

In this paper, I will describe a technique for generating a novel kind of semantics for a logic, and explore some of its consequences. It would be natural to call the semantics produced by the technique in question ‘many-valued'; but that name is, of course, already taken. I call them, instead, ‘plurivalent'. In standard logical semantics, formulas take exactly one of a bunch of semantic values. I call such semantics ‘univalent'. In a plurivalent semantics, by contrast, formulas may (...) take one or more such values. The construction I shall describe can be applied to any univalent semantics to produce a corresponding plurivalent one. In the paper I will be concerned with the application of the technique to propositional many-valued logics. Sometimes going plurivalent does not change the consequence relation; sometimes it does. I investigate the possibilities in detail with respect to small family of many-valued logics. (shrink)

Free logics is a family of first-order logics which came about as a result of examining the existence assumptions of classical logic. What those assumptions are varies, but the central ones are that the domain of interpretation is not empty, every name denotes exactly one object in the domain and the quantifiers have existential import. Free logics usually reject the claim that names need to denote in, and of the systems considered in this paper, the positive free logic concedes that (...) some atomic formulas containing non-denoting names are true, while negative free logic rejects even the latter claim. Inclusive logics, which reject, are likewise considered. These logics have complex and varied axiomatizations and semantics, and the goal of this paper is to present an orderly examination of the various systems and their mutual relations. This is done by first offering a formalization, using sequent calculi which possess all the desired structural properties of a good proof system, including admissibility of contraction and cut, while streamlining free logics in a way no other approach has. We then present a simple and unified system of abstract semantics, which allows for a straightforward demonstration of the meta-theoretical properties, and offers insights into the relationship between different logics. The final part of this paper is dedicated to extending the system with modalities by using a labeled sequent calculus, and here we are again able to map out the different approaches and their mutual relations using the same framework. (shrink)

A complementary system for a given logic is a proof system whose theorems are exactly the formulas that are not valid according to the logic in question. This article is a contribution to the complementary proof theory of classical propositional logic. In particular, we present a complementary proof-net system, $$\textsf{CPN}$$ CPN, that is sound and complete with respect to the set of all classically invalid (one-side) sequents. We also show that cut elimination in $$\textsf{CPN}$$ CPN enjoys strong normalization along (...) with strong confluence (and, hence, uniqueness of normal forms). (shrink)

There is a long-standing debate whether propositions, sentences, statements or utterances provide an answer to the question of what objects logical formulas stand for. Based on the traditional understanding of logic as a science of valid arguments, this question is firstly framed more exactly, making explicit that it calls not only for identifying some class of objects, but also for explaining their relationship to ordinary language utterances. It is then argued that there are strong arguments against the proposals commonly (...) put forward in the debate. The core of the problem is that an informative account of the objects formulas stand for presupposes a theory of formalization; that is, a theory that explains what formulas may adequately substitute for an inference in proofs of validity. Although such theories are still subject to research, some consequences can be drawn from an analysis of the reasons why the common accounts featuring sentences, propositions or utterances fail. Theories of formalization cannot refer to utterances qua expressions of propositions; instead they may refer to sentences and rely on additional information about linguistic structure and pragmatic context. (shrink)

Fine (J Philos Log 43:549–577, 2014) developed a truthmaker semantics for intuitionistic logic, which is also called exact semantics, since it is based on a relation of exact verification between states and formulas. A natural question arises as to what are the limits of Fine’s approach and whether an exact semantics of similar kind can be constructed for other important non-classical logics. In our paper, we will generalize Fine’s approach and develop an exact semantics for (...) some substructural logics. In particular, we will provide a truthmaker semantics for the Non-associative Lambek calculus and some of its extensions. This generalization will reveal some interesting connections between Fine’s recent work on truthmaker semantics and his early work on relevant logic. (shrink)

The bounded proper forcing axiom BPFA is the statement that for any family of ℵ 1 many maximal antichains of a proper forcing notion, each of size ℵ 1 , there is a directed set meeting all these antichains. A regular cardinal κ is called Σ 1 -reflecting, if for any regular cardinal χ, for all formulas $\varphi, "H(\chi) \models`\varphi'"$ implies " $\exists\delta . We investigate several algebraic consequences of BPFA, and we show that the consistency strength of the (...) bounded proper forcing axiom is exactly the existence of a Σ 1 -reflecting cardinal (which is less than the existence of a Mahlo cardinal). We also show that the question of the existence of isomorphisms between two structures can be reduced to the question of rigidity of a structure. (shrink)

The logical calculus for SAT are not valid for MaxSAT and MinSAT because they preserve satisfiability but not the number of unsatisfied clauses. To overcome this drawback, a MaxSAT resolution rule preserving the number of unsatisfied clauses was defined in the literature. This rule is complete for MaxSAT when it is applied following a certain strategy. In this paper we first prove that the MaxSAT resolution rule also provides a complete calculus for MinSAT if it is applied following the strategy (...) proposed here. We then describe an exact variable elimination algorithm for MinSAT based on that rule. Finally, we show how the results for Boolean MinSAT can be extended to solve the MinSAT problem of the multiple-valued clausal forms known as signed conjunctive normal form formulas. (shrink)

Classical propositional logic can be characterized, indirectly, by means of a complementary formal system whose theorems are exactly those formulas that are not classical tautologies, i.e., contradictions and truth-functional contingencies. Since a formula is contingent if and only if its negation is also contingent, the system in question is paraconsistent. Hence classical propositional logic itself admits of a paraconsistent characterization, albeit “in the negative”. More generally, any decidable logic with a syntactically incomplete proof theory allows for a paraconsistent characterization (...) of its set of theorems. This, we note, has important bearing on the very nature of paraconsistency as standardly characterized. (shrink)

This article begins by exploring a lost topic in the philosophy of science:the properties of the relations evidence confirming h confirmsh'' and, more generally, evidence confirming each ofh1, h2, ..., hm confirms at least one of h1, h2,ldots;, hn''.The Bayesian understanding of confirmation as positive evidential relevanceis employed throughout. The resulting formal system is, to say the least, oddlybehaved. Some aspects of this odd behaviour the system has in common withsome of the non-classical logics developed in the twentieth century. Oneaspect (...) – its ``parasitism'''' on classical logic – it does not, and it is this featurethat makes the system an interesting focus for discussion of questions in thephilosophy of logic. We gain some purchase on an answer to a recently prominentquestion, namely, what is a logical system? More exactly, we ask whether satisfaction of formal constraints is sufficient for a relation to be considered a (logical) consequence relation. The question whether confirmation transfer yields a logical system is answered in the negative, despite confirmation transfer having the standard properties of a consequence relation, on the grounds that validity of sequents in the system is not determined by the meanings of the connectives that occur in formulas. Developing the system in a different direction, we find it bears on the project of ``proof-theoretic semantics'''': conferring meaning on connectives by means of introduction (and possibly elimination) rules is not an autonomous activity, rather it presupposes a prior, non-formal,notion of consequence. Some historical ramifications are alsoaddressed briefly. (shrink)

Bi-intuitionistic logic is the result of adding the dual of intuitionistic implication to intuitionistic logic. In this note, we characterize the expressive power of this logic by showing that the first order formulas equivalent to translations of bi-intuitionistic propositional formulas are exactly those preserved under bi-intuitionistic directed bisimulations. The proof technique is originally due to Lindstrom and, in contrast to the most common proofs of this kind of result, it does not use the machinery of neither saturated models (...) nor elementary chains. (shrink)

For “natural enough” systems of ordinal notation we show that α times iterated local reflection schema over a sufficiently strong arithmetic T proves the same Π 1 0 -sentences as ω α times iterated consistency. A corollary is that the two hierarchies catch up modulo relative interpretability exactly at ε-numbers. We also derive the following more general “mixed” formulas estimating the consistency strength of iterated local reflection: for all ordinals α ⩾ 1 and all β, β ≡ Π 1 (...) 0 T ω α · , α ≡ Π 1 0 T β + ω α . Here T α stands for α times iterated local reflection over T , T β stands for β times iterated consistency, and ≡ Π 1 0 denotes mutual Π 1 0 -conservativity. In an appendix to this paper we develop our notion of “natural enough” system of ordinal notation and show that such systems do exist for every recursive ordinal. (shrink)

The systems T N and T M show that necessity can be consistently construed as a predicate of syntactical objects, if the expressive/deductive power of the system is deliberately engineered to reflect the power of the original object language operator. The system T N relies on salient limitations on the expressive power of the language L N through the construction of a quotational hierarchy, while the system T Mrelies on limiting the scope of the modal axioms schemas to the sublanguage (...) L infM +, which corresponds exactly with the restrictive hierarchy of L N. The fact that L infM + is identical to the image of the metalinguistic mapping C + from the normal operator system into L M reveals that iterated operator modality is implicitly hierarchical, and that inconsistency is produced by applying the principles of the modal logic to formulas which have no natural analogues in the operator development. Thus the contradiction discovered by Montague can be diagnosed as the result of instantiating the axiom schemas with modally ungrounded formulas, and thereby adding radically new modal axioms to the predicate system.The predicate treatment of necessity differs significantly from that of the operator in that the cumulative models for the predicate system are strictly first-order. Possible worlds are not used as model-theoretic primitives, but rather alternate models are appealed to in order to specify the extension of N, which is semantically construed as a first-order predicate. In this manner, the intensional aspects of modality are built into the mode of specifying the particular set of objects which the denotation function assigns to N, rather than in the specification of the basic truth conditions for modal formulas. Intensional phenomena are thereby localised to the special requirements for determining the extension of a particular predicate, and this does not constitute a structural modification of the first-order models, but rather limits the relevant class of models to those which possess an appropriate denotation function. (shrink)

By Solovay’s celebrated completeness result [31] on formal provability we know that the provability logic ${\textbf {GL}}$ describes exactly all provable structural properties for any sound and strong enough arithmetical theory with a decidable axiomatisation. Japaridze generalised this result in [22] by considering a polymodal version ${\mathsf {GLP}}$ of ${\textbf {GL}}$ with modalities $[n]$ for each natural number n referring to ever increasing notions of provability. Modern treatments of ${\mathsf {GLP}}$ tend to interpret the $[n]$ provability notion as “provable in (...) a base theory T together with all true $\Pi ^0_n$ formulas as oracles.” In this paper we generalise this interpretation into the transfinite. In order to do so, a main difficulty to overcome is to generalise the syntactical characterisations of the oracle formulas of complexity $\Pi ^0_n$ to the hyper-arithmetical hierarchy. The paper exploits the fact that provability is $\Sigma ^0_1$ complete and that similar results hold for stronger provability notions. As such, the oracle sentences to define provability at level $\alpha $ will recursively be taken to be consistency statements at lower levels: provability through provability whence the name of the paper. The paper proves soundness and completeness for the proposed interpretation for a wide class of theories, namely for any theory that can formalise the recursion described above and that has some further very natural properties. Some remarks are provided on how the recursion can be formalised into second order arithmetic and on lowering the proof-theoretical strength of these systems of second order arithmetic. (shrink)

Dzhaparidze, G., A generalized notion of weak interpretability and the corresponding modal logic, Annals of Pure and Applied Logic 61 113-160. A tree Tr of theories T1,...,Tn is called tolerant, if there are consistent extensions T+1,...,T+n of T1,...,Tn, where each T+i interprets its successors in the tree Tr. We consider a propositional language with the following modal formation rule: if Tr is a tree of formulas, then Tr is a formula, and axiomatically define in this language the decidable logics (...) TLR and TLRω. It is proved that TLR yields exactly the schemata of PA-provable sentences, if Tr is understood as “Tr is tolerant”. In fact, TLR axiomatizes a considerable fragment of provability logic with quantifiers over ∑1-sentences, and many relations that have been studied in the literature can be expressed in terms of tolerance. We introduce and study two more relations between theories: cointerpretability and cotolerance which are, in a sense, dual to interpretability and tolerance. Cointerpretability is a characterization of ∑1-conservativity for essentially reflexive theories in terms of translations. (shrink)

THE methodological principle known as Ockham’s Razor is usually formulated as “Entia non sunt multiplicanda praeter necessarium”. However, it is well known that neither this formulation of the principle nor the idea behind it come originally from William of Ockham. This particular formula is due to Leibniz, though Ockham’s works contain equivalent formulas: “Pluralitas non est ponenda sine necessitate”; “Si duae res sufficiunt ad eius veritatem, superfluum est ponere aliam rem”; “Frustra fit per plura, quod potest fieri per pauciora”. (...) But Duns Scotus had also used the same principle before Ockham and he refers it directly to Aristotle. If the Razor belongs to anyone then, it belongs to Aristotle, and the study of its exact meaning and value must begin with Aristotle’s views about it. It is interesting to note, in this respect, that the principle was recognized as Aristotle’s at least until the time of Galileo. Thus in his Dialogue concerning the Two chief World Systems Galileo supports his theory that “diurnal motion belongs to the earth alone rather than to the rest of the universe excepting the earth” by referring to “a very true maxim of Aristotle’s which teaches that ‘frustra fit per plura quod potest fieri per pauciora’.”. (shrink)

The guarded fragment (GF) was introduced by Andréka, van Benthem and Németi as a fragment of first order logic which combines a great expressive power with nice, modal behavior. It consists of relational first order formulas whose quantifiers are relativized by atoms in a certain way. Slightly generalizing the admissible relativizations yields the packed fragment (PF). In this paper we investigate interpolation and definability in these fragments. We first show that the interpolation property of first order logic fails in (...) restriction to GF and PF. However, each of these fragments turns out to have an alternative interpolation property that closely resembles the interpolation property usually studied in modal logic. These results are strong enough to entail the Beth definability property for GF and PF. Even better, every guarded or packed finite variable fragment has the Beth property. For interpolation, we characterize exactly which finite variable fragments of GF and PF enjoy this property. (shrink)

A quasi-canonical Gentzen-type system is a Gentzen-type system in which each logical rule introduces either a formula of the form , or of the form , and all the active formulas of its premises belong to the set . In this paper we investigate quasi-canonical systems in which exactly one of the two classical rules for negation is included, turning the induced logic into either a paraconsistent logic or a paracomplete logic, but not both. We provide a constructive coherence (...) criterion for such systems, and show that a quasi-canonical system of the type we investigate is coherent iff it is strongly paraconsistent or strongly paracomplete (in a sense defined in the paper), iff it has a trivalent, non-deterministic semantics of a special type (also defined in the paper) for which it is sound and complete. Finally, we determine when a system of this sort admits cut-elimination, and provide a simple procedure for transforming one which does not into one which does. (shrink)

We characterize the proof-theoretic strength of systems of explicit mathematics with a general principle asserting the existence of least fixed points for monotone inductive definitions, in terms of certain systems of analysis and set theory. In the case of analysis, these are systems which contain the Σ12-axiom of choice and Π12-comprehension for formulas without set parameters. In the case of set theory, these are systems containing the Kripke-Platek axioms for a recursively inaccessible universe together with the existence of a (...) stable ordinal. In all cases, the exact strength depends on what forms of induction are admitted in the respective systems. (shrink)

The main purpose of this paper is to present a formal systemPin which we enjoy a smooth-running technique and which countenances a universe of classes which is symmetrical as between large and small. More exactly,Pis a system which differs from the inconsistent system of [1] only in the introduction of a rather natural new restrictive condition on the defining formulas of the elements. It will be proved that if the weaker system of [2] is consistent, thenPis also consistent.After the (...) discovery of paradoxes, it may be recalled, Russell and Zermelo in the same year proposed two different ways of safeguarding logic against contradictions. Since then various simplifications and refinements of these systems have been made. However, in the resulting systems of Zermelo set theory, generation of classes still tends to be laborious and uncertain; and in the systems of Russell's theory of types, complications in the matter of reduplication of classes and meaningfulness of formulas remain. In [2], Quine introduced a system which seems to be free from all these complications. But later it was found out that in it there appears to be an unavoidable difficulty connected with mathematical induction. Indeed, we encounter the curious situation that although we can prove in it the existence of a class V of all classes, and we can also prove particular existence theorems for each of infinitely many classes, nobody has so far contrived to prove in it that V is an infinite class or that there exists an infinite class at all. (shrink)

A class of Kripke models is modally definable if there is a set of modal formulas such that the class consists exactly of models on which every formula from that set is globally true. In this paper, a class is also considered definable if there is a set of formulas such that it consists exactly of models in which every formula from that set is satisfiable. The notion of modal definability is then generalized by combining these two. For (...) thus obtained types of modal definability on the level of Kripke models, we give characterization theorems in the usual form, in terms of algebraic closure conditions. As some consequences of these, various preservation results are presented. Also, some characterizations are strengthened by replacing closure under ultraproducts with closure under ultrapowers. (shrink)

A canonical Gentzen-type system is a system in which every rule has the subformula property, it introduces exactly one occurrence of a connective, and it imposes no restrictions on the contexts of its applications. A larger class of Gentzen-type systems which is also extensively in use is that of quasi-canonical systems. In such systems a special role is given to a unary connective \ of the language. Accordingly, each application of a logical rule in such systems introduces either a formula (...) of the form \\), or of the form \\), and all the active formulas of its premises belong to the set \. In this paper we investigate the whole class of quasi-canonical systems. We provide a constructive coherence criterion for such systems, and show that a quasi-canonical system is coherent iff it is analytic iff it has a characteristic non-deterministic matrix which is based on some subset of the set of the four truth-values which are used in the famous Dunn–Belnap four-valued matrix for information processing. In addition, we determine when a quasi-canonical system admits cut-elimination. (shrink)

THE methodological principle known as Ockham’s Razor is usually formulated as “Entia non sunt multiplicanda praeter necessarium”. However, it is well known that neither this formulation of the principle nor the idea behind it come originally from William of Ockham. This particular formula is due to Leibniz, though Ockham’s works contain equivalent formulas: “Pluralitas non est ponenda sine necessitate”; “Si duae res sufficiunt ad eius veritatem, superfluum est ponere aliam rem”; “Frustra fit per plura, quod potest fieri per pauciora”. (...) But Duns Scotus had also used the same principle before Ockham and he refers it directly to Aristotle. If the Razor belongs to anyone then, it belongs to Aristotle, and the study of its exact meaning and value must begin with Aristotle’s views about it. It is interesting to note, in this respect, that the principle was recognized as Aristotle’s at least until the time of Galileo. Thus in his Dialogue concerning the Two chief World Systems Galileo supports his theory that “diurnal motion belongs to the earth alone rather than to the rest of the universe excepting the earth” by referring to “a very true maxim of Aristotle’s which teaches that ‘frustra fit per plura quod potest fieri per pauciora’.”. (shrink)

The projective plane of Baldwin 695) is model complete in a language with additional constant symbols. The infinite rank bicolored field of Poizat 1339) is not model complete. The finite rank bicolored fields of Baldwin and Holland 371; Notre Dame J. Formal Logic , to appear) are model complete. More generally, the finite rank expansions of a strongly minimal set obtained by adding a ‘random’ unary predicate are almost strongly minimal and model complete provided the strongly minimal set is ‘well-behaved’ (...) and admits ‘exactly rank k formulas’. The last notion is a geometric condition on strongly minimal sets formalized in this paper. (shrink)

The traditional Dung networks depict arguments as atomic and study the relationships of attack between them. This can be generalised in two ways. One is to consider various forms of attack, support, feedback, etc. Another is to add content to nodes and put there not just atomic arguments but more structure, e.g. proofs in some logic or simply just formulas from a richer language. This paper offers to use temporal and modal language formulas to represent arguments in the (...) nodes of a network. The suitable semantics for such networks is Kripke semantics. We also introduce a new key concept of usability of an argument. This is the beginning of a continuing research for adding contents to the nodes of an argumentation network. This research will allow us to address notions like ?what does it exactly mean for a node to attack another? or ?what does it mean for a network to be consistent? or ?can we give proper proof rules to manipulate networks?, and more. (shrink)

An important component in the interventionist account of causal explanation is an interpretation of counterfactual conditionals as statements about consequences of hypothetical interventions. The interpretation receives a formal treatment in the framework of functional causal models. In Judea Pearl’s influential formulation, functional causal models are assumed to satisfy a “unique-solution” property; this class of Pearlian causal models includes the ones called recursive. Joseph Halpern showed that every recursive causal model is Lewisian, in the sense that from the causal model one (...) can construct a possible worlds model in David Lewis’s well-known semantics that satisfies the exact same formulas in a certain language. Moreover, he demonstrated that some Pearlian (non-recursive) models are not Lewisian in this sense. This raises the question regarding the exact contour of Lewisian causal models. In this paper, we provide a characterization of the class of Lewisian causal models and a complete axiomatization with respect to this class. Our results have philosophically interesting consequences, two of which are especially worth noting. First, the class of Stalnakerian causal models, a subclass of Lewisian causal models, is precisely the class of Pearlian models that do not contain any cycle of counterfactual dependence (in a sense of counterfactual dependence akin to Lewis’s famous relation between distinct events). Second, a more natural class of causal models is actually a superclass of Lewisian causal models, the logic of which respects only weak centering rather than centering. (shrink)

For the given logical calculus we investigate the proportion of the number of true formulas of a certain length n to the number of all formulas of such length. We are especially interested in asymptotic behavior of this fraction when n tends to infinity. If the limit exists it is represented by a real number between 0 and 1 which we may call the density of truth for the investigated logic. In this paper we apply this approach to (...) the intuitionistic logic of one variable with implication and negation. The result is obtained by reducing the problem to the same one of Dummett's intermediate linear logic of one variable (see [2]). Actually, this paper shows the exact density of intuitionistic logic and demonstrates that it covers a substantial part (more than 93%) of classical prepositional calculus. Despite using strictly mathematical means to solve all discussed problems, this paper in fact, may have a philosophical impact on understanding how much the phenomenon of truth is sporadic or frequent in random mathematics sentences. (shrink)

The guarded fragment (GF) was introduced by Andréka, van Benthem and Németi as a fragment of first order logic which combines a great expressive power with nice, modal behavior. It consists of relational first order formulas whose quantifiers are relativized by atoms in a certain way. Slightly generalizing the admissible relativizations yields the packed fragment (PF). In this paper we investigate interpolation and definability in these fragments. We first show that the interpolation property of first order logic fails in (...) restriction to GF and PF. However, each of these fragments turns out to have an alternative interpolation property that closely resembles the interpolation property usually studied in modal logic. These results are strong enough to entail the Beth definability property for GF and PF. Even better, every guarded or packed finite variable fragment has the Beth property. For interpolation, we characterize exactly which finite variable fragments of GF and PF enjoy this property. (shrink)

Analytical philosophy of the last one hundred years has been heavily influenced by a doctrine to the effect that one can arrive at a correct ontology by paying attention to certain superficial (syntactic) features of first-order predicate logic as conceived by Frege and Russell. More specifically, it is a doctrine to the effect that the key to the ontological structure of reality is captured syntactically in the ‘Fa’ (or, in more sophisticated versions, in the ‘Rab’) of first-order logic, where ‘F’ (...) stands for what is general in reality and ‘a’ for what is individual. Hence “f(a)ntology”. Because predicate logic has exactly two syntactically different kinds of referring expressions—‘F’, ‘G’, ‘R’, etc., and ‘a’, ‘b’, ‘c’, etc.—so reality must consist of exactly two correspondingly different kinds of entity: the general (properties, concepts) and the particular (things, objects), the relation between these two kinds of entity being revealed in the predicate-argument structure of atomic formulas in first-order logic. (shrink)

We study the theory of the structure induced by parameter free formulas on a “dense” algebraically independent subset of a model of a geometric theory T. We show that while being a trivial geometric theory, inherits most of the model theoretic complexity of T related to stability, simplicity, rosiness, the NIP and the NTP2. In particular, we show that T is strongly minimal, supersimple of SU‐rank 1, has the NIP or the NTP2 exactly when has these properties. We show (...) that if T is superrosy of thorn rank 1, then so is, and that the converse holds if T satisfies acl = dcl. (shrink)

Given the frequency of human error, it seems rational to believe that some of our own rational beliefs are false. This is the axiom of epistemic modesty. Unfortunately, using standard propositional quantification, and the usual relational semantics, this axiom is semantically inconsistent with a common logic for rational belief, namely KD45. Here we explore two alternative semantics for KD45 and the axiom of epistemic modesty. The first uses the usual relational semantics and bisimulation quantifiers. The second uses a topological semantics (...) and standard propositional quantification. We show the two different semantics validate many of the same formulas, though we do not know whether they validate exactly the same formulas. Along the way we address various philosophical concerns. (shrink)