Various natural deduction formulations of classical, minimal, intuitionist, and intermediate propositional and first-order logics are presented and investigated with respect to satisfaction of the separation and subformula properties. The technique employed is, for the most part, semantic, based on general versions of the Lindenbaum and Lindenbaum–Henkin constructions. Careful attention is paid to which properties of theories result in the presence of which rules of inference, and to restrictions on the sets of formulas to which the rules may be employed, restrictions (...) determined by the formulas occurring as premises and conclusion of the invalid inference for which a counterexample is to be constructed. We obtain an elegant formulation of classical propositional logic with the subformula property and a singularly inelegant formulation of classical first-order logic with the subformula property, the latter, unfortunately, not a product of the strategy otherwise used throughout the article. Along the way, we arrive at an optimal strengthening of the subformula results for classical first-order logic obtained as consequences of normalization theorems by Dag Prawitz and Gunnar Stålmarck. (shrink)

Intervals in boolean algebras enter into the study of conditional assertions (or events) in two ways: directly, either from intuitive arguments or from Goodman, Nguyen and Walker's representation theorem, as suitable mathematical entities to bear conditional probabilities, or indirectly, via a representation theorem for the family of algebras associated with de Finetti's three-valued logic of conditional assertions/events. Further representation theorems forge a connection with rough sets. The representation theorems and an equivalent of the boolean prime ideal theorem yield an algebraic (...) completeness theorem for the three-valued logic. This in turn leads to a Henkin-style completeness theorem. Adequacy with respect to a family of Kripke models for de Finetti's logic, Łukasiewicz's three-valued logic and Priest's Logic of Paradox is demonstrated. The extension to first-order yields a short proof of adequacy for Körner's logic of inexact predicates. (shrink)

Questions concerning the proof-theoretic strength of classical versus nonclassical theories of truth have received some attention recently. A particularly convenient case study concerns classical and nonclassical axiomatizations of fixed-point semantics. It is known that nonclassical axiomatizations in four- or three-valued logics are substantially weaker than their classical counterparts. In this paper we consider the addition of a suitable conditional to First-Degree Entailment—a logic recently studied by Hannes Leitgeb under the label HYPE. We show in particular that, by formulating the theory (...) PKF over HYPE, one obtains a theory that is sound with respect to fixed-point models, while being proof-theoretically on a par with its classical counterpart KF. Moreover, we establish that also its schematic extension—in the sense of Feferman—is as strong as the schematic extension of KF, thus matching the strength of predicative analysis. (shrink)

Certain extensions of Nelson's constructive logic N with strong negation have recently become important in arti.cial intelligence and nonmonotonic reasoning, since they yield a logical foundation for answer set programming (ASP). In this paper we look at some extensions of Nelson's .rst-order logic as a basis for de.ning nonmonotonic inference relations that underlie the answer set programming semantics. The extensions we consider are those based on 2-element, here-and-there Kripke frames. In particular, we prove completeness for .rst-order here-and-there logics, and their (...) minimal strong negation extensions, for both constant and varying domains. We choose the constant domain version, which we denote by QNc5, as a basis for de.ning a .rst-order nonmonotonic extension called equilibrium logic. We establish several metatheoretic properties of QNc5, including Skolem forms and Herbrand theorems and Interpolation, and show that the .rst-oder version of equilibrium logic can be used as a foundation for answer set inference. (shrink)

Versions and extensions of intuitionistic and modal logic involving biHeyting and bimodal operators, the axiom of constant domains and Barcan's formula, are formulated as structured categories. Representation theorems for the resulting concepts are proved. Essentially stronger versions, requiring new methods of proof, of known completeness theorems are consequences. A new type of completeness result, with a topos theoretic character, is given for theories satisfying a condition considered by Lawvere . The completeness theorems are used to conclude results asserting that certain (...) logics are conservatively interpretable in others. (shrink)

We give topological proofs of Görnemann’s adaptation to Heyting algebras of the Rasiowa-Sikorski Lemma for Boolean algebras; and of the Rauszer-Sabalski generalisation of it to distributive lattices. The arguments use the Priestley topology on the set of prime filters, and the Baire category theorem. This is preceded by a discussion of criteria for compactness of various spaces of subsets of a lattice, including spaces of filters, prime filters etc.

We give completeness results — with respect to Kripke's semantic — for the negation-free intermediate predicate calculi.

It is known that for any subdirectly irreducible finite Heyting algebra A and any Heyting algebra, B, A is embeddable into a quotient algebra of B, if and only if Jankov's formula ${\rm{\chi A}}$ A for A is refuted in B. In this paper, we present an infinitary extension of the above theorem given by Jankov. More precisely, for any cardinal number ${\rm{\kappa }}$, we present Jankov's theorem for homomorphisms preserving infinite meets and joins, a class of subdirectly irreducible complete (...) ${\rm{\kappa }}$ - Heyting algebras and ${\rm{\kappa }}$ - infinitary logic, where a ${\rm{\kappa }}$ -Heyting algebra is a Heyting algebra A with ${\rm{\# A}} \le {\rm{\kappa }}$ and ${\rm{\kappa }}$ - infinitary logic is the infinitary logic such that for any set ${\rm{\Theta }}$ of formulas with ${\rm{\# \Theta }} \le {\rm{\kappa }}$ ⌈ Θ and ‷ Θ are well defined formulas. (shrink)

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)

We prove some preservation theorems concerning inductive and model-complete theories in the framework of semi-classical logic introduced in [1].

We extend to the predicate frame a previous characterization of the maximal intermediate propositional constructive logics. This provides a technique to get maximal intermediate predicate constructive logics starting from suitable sets of classically valid predicate formulae we call maximal nonstandard predicate constructive logics. As an example of this technique, we exhibit two maximal intermediate predicate constructive logics, yet leaving open the problem of stating whether the two logics are distinct. Further properties of these logics will be also investigated.

The intersection of a linearly ordered set of total subrelations of a total relation with range 2 need not be total, constructively.

In the 80's Pierangelo Miglioli, starting from motivations in the framework of Abstract Data Types and Program Synthesis, introduced semiconstructive theories, a family of large subsystems of classical theories that guarantee the computability of functions and predicates represented by suitable formulas. In general, the above computability results are guaranteed by algorithms based on a recursive enumeration of the theorems of the whole system. In this paper we present a family of semiconstructive systems, we call uniformly semiconstructive, that provide computational procedures (...) only involving formulas with bounded complexity. We present several examples of uniformly semiconstructive systems containing Harrop theories, induction principles and some well-known predicate intermediate principles. Among these, we give an account of semiconstructive and uniformly semiconstructive systems which lie between Intuitionistic and Classical Arithmetic and we discuss their constructive incompatibility. (shrink)

Wajsberg and Jankov provided us with methods of constructing a continuum of logics. However, their methods are not suitable for super-intuitionistic and modal predicate logics. The aim of this paper is to present simple ways of modification of their methods appropriate for such logics. We give some concrete applications as generic examples. Among others, we show that there is a continuum of logics (1) between the intuitionistic predicate logic and the logic of constant domains, (2) between a predicate extension ofS4 (...) andS4 with the Barcan formula. Furthermore, we prove that (3) there is a continuum of predicate logics with equality whose equality-free fragment is just the intuitionistic predicate logic. (shrink)

Let denote a first‐order logic in a language that contains infinitely many constant symbols and also containing intuitionistic logic. By, we mean the associated logic axiomatized by the double negation of the universal closure of the axioms of plus. We shall show that if is strongly complete for a class of Kripke models, then is strongly complete for the class of Kripke models that are ultimately in.

Predicate modal logics based on Kwith non-compact extra axioms are discussed and a sufficient condition for the model existence theorem is presented. We deal with various axioms in a general way by an algebraic method, instead of discussing concrete non-compact axioms one by one.

We combine a variety of constructive methods (including forcing, realizability, asymmetric interpretation), to obtain consistency results concerning combinatory logic with extensionality and (forms of) the axiom of choice.

In this paper we study the elementary amalgamation property and the joint embedding property for intermediate logics. We point out the class of Kripke structures with elementary embedding can be viewed within abstract elementary class framework. Following this approach, both elementary AP and JEP can be considered quite naturally for intermediate logics. The main method for our investigations is the extension of Morleyization method from classical model theory to Kripke model theory. The almost-classical logic and almost-classical models have been defined. (...) After verifying that the class of almost-classical models forms an abstract elementary class, we, furthermore, prove that the almost-classical logic neither has the elementary AP nor JEP property. We finally give an example of a non-classical intermediate logic which extends the almost-classical logic and has both elementary AP and JEP. (shrink)

We present axiom systems, and provide soundness and strong completeness theorems, for classes of Kripke models with restricted extension rules among the node structures of the model. As examples we present an axiom system for the class of cofinal extension Kripke models, and an axiom system for the class of end-extension Kripke models. We also show that Heyting arithmetic is strongly complete for its class of end-extension models. Cofinal extension models of HA are models of Peano arithmetic.