Undecidability and intuitionistic incompleteness

Let S be a deductive system such that S-derivability (s) is arithmetic and sound with respect to structures of class K. From simple conditions on K and s, it follows constructively that the K-completeness of s implies MP(S), a form of Markov's Principle. If s is undecidable then MP(S) is independent of first-order Heyting arithmetic. Also, if s is undecidable and the S proof relation is decidable, then MP(S) is independent of second-order Heyting arithmetic, HAS. Lastly, when s is many-one complete, MP(S) implies the usual Markov's Principle MP.An immediate corollary is that the Tarski, Beth and Kripke weak completeness theorems for the negative fragment of intuitionistic predicate logic are unobtainable in HAS. Second, each of these: weak completeness for classical predicate logic, weak completeness for the negative fragment of intuitionistic predicate logic and strong completeness for sentential logic implics MP. Beth and Kripke completeness for intuitionistic predicate or sentential logic also entail MP.These results give extensions of the theorem of Gödel and Kreisel (in [4]) that completeness for pure intuitionistic predicate logic requires MP. The assumptions of Gödel and Kreisel's original proof included the Axiom of Dependent Choice and Herbrand's Theorem, no use of which is explicit in the present article.     

Intuitionistic Propositional Logic without 'Contraction' but with 'Reductio'

Routley-Meyer type relational complete semantics are constructed for intuitionistic contractionless logic with reductio. Different negation completions of positive intuitionistic logic without contraction are treated in a systematical, unified and semantically complete setting.     

The "Natural" and the "Formal"

The paper presents an argument against a metaphysical conception of logic according to which logic spells out a specific kind of mathematical structure that is somehow inherently related to our factual reasoning. In contrast, it is argued that it is always an empirical question as to whether a given mathematical structure really does captures a principle of reasoning. (More generally, it is argued that it is not meaningful to replace an empirical investigation of a thing by an investigation of its a priori analyzable structure without paying due attention to the question of whether it really is the structure of the thing in question.) It is proposed to elucidate the situation by distinguishing two essentially different realms with which our reason must deal: the realm of the natural, constituted by the things of our empirical world, and the realm of the formal, constituted by the structures that we use as prisms to view, to make sense of, and to reconstruct the world. It is suggested that this vantage point may throw light on many foundational problems of logic.     

Partiality and Its Dual

This paper explores allowing truth value assignments to be undetermined or "partial" (no truth values) and overdetermined or "inconsistent" (both truth values), thus returning to an investigation of the four-valued semantics that I initiated in the sixties. I examine some natural consequence relations and show how they are related to existing logics, including ukasiewicz's three-valued logic, Kleene's three-valued logic, Anderson and Belnap's (first-degree) relevant entailments, Priest's "Logic of Paradox", and the first-degree fragment of the Dunn-McCall system "R-mingle". None of these systems have nested implications, and I investigate twelve natural extensions containing nested implications, all of which can be viewed as coming from natural variations on Kripke's semantics for intuitionistic logic. Many of these logics exist antecedently in the literature, in particular Nelson's "constructible falsity".     

Skepticism and Epistemic Logic

This essay attempts to implement epistemic logic through a non-classical inference relation. Given that relation, an account of '(the individual) a knows that A' is constructed as an unfamiliar non-normal modal logic. One advantage to this approach is a new analysis of the skeptical argument.     

Absolute Probability Functions for Intuitionistic Propositional Logic

Provided here is a characterisation of absolute probability functions for intuitionistic (propositional) logic L, i.e. a set of constraints on the unary functions P from the statements of L to the reals, which insures that (i) if a statement A of L is provable in L, then P(A) = 1 for every P, L's axiomatisation being thus sound in the probabilistic sense, and (ii) if P(A) = 1 for every P, then A is provable in L, L's axiomatisation being thus complete in the probabilistic sense. As there are theorems of classical (propositional) logic that are not intuitionistic ones, there are unary probability functions for intuitionistic logic that are not classical ones. Provided here because of this is a means of singling out the classical probability functions from among the intuitionistic ones.     

An Operational Logic of Proofs with Positive and Negative Information

The logic of proofs was introduced by Artemov in order to analize the formalization of the concept of proof rather than the concept of provability. In this context, some operations on proofs play a very important role. In this paper, we investigate some very natural operations, paying attention not only to positive information, but also to negative information (i.e. information saying that something cannot be a proof). We give a formalization for a fragment of such a logic of proofs, and we prove that our fragment is complete and decidable.     

Every Finitely Reducible Logic has the Finite Model Property with Respect to the Class of ♦-Formulae

In this paper a unified framework for dealing with a broad family of propositional multimodal logics is developed. The key tools for presentation of the logics are the notions of closure relation operation and monotonous relation operation. The two classes of logics: FiRe-logics (finitely reducible logics) and LaFiRe-logics (FiRe-logics with local agreement of accessibility relations) are introduced within the proposed framework. Further classes of logics can be handled indirectly by means of suitable translations. It is shown that the logics from these classes have the finite model property with respect to the class of -formulae, i.e. each -formula has a -model iff it has a finite -model. Roughly speaking, a -formula is logically equivalent to a formula in negative normal form without occurrences of modal operators with necessity force. In the proof we introduce a substantial modification of Claudio Cerrato's filtration technique that has been originally designed for graded modal logics. The main core of the proof consists in building adequate restrictions of models while preserving the semantics of the operators used to build terms indexing the modal operators.     

Predicate Logics on Display

The paper provides a uniform Gentzen-style proof-theoretic framework for various subsystems of classical predicate logic. In particular, predicate logics obtained by adopting van Behthem's modal perspective on first-order logic are considered. The Gentzen systems for these logics augment Belnap's display logic by introduction rules for the existential and the universal quantifier. These rules for x and x are analogous to the display introduction rules for the modal operators and and do not themselves allow the Barcan formula or its converse to be derived. En route from the minimal modal predicate logic to full first-order logic, axiomatic extensions are captured by purely structural sequent rules.