Search

We discuss the celebrated Blok-Esakia theorem on the isomorphism between the lattices of extensions of intuitionistic propositional logic and the Grzegorczyk modal system. In particular, we present the original algebraic proof of this theorem found by Blok, and give a brief survey of generalisations of the Blok-Esakia theorem to extensions of intuitionistic logic with modal operators and coimplication.

Now we can relate the semantical systems of sections 9.1, 9.2 and 9.3 to the syntactical systems of chapter 10 by means of soundness and completeness theorems. We are going to present three kinds of such theorems: (“strong”) soundness and completeness concerning derivability on the syntactical side and entailment on the semantical side, (“weak”) soundness and completeness concerning provability on the syntactical side and validity on the semantical side, and (“strong”) soundness and completeness concerning conditional theories on the syntactical side and conditional theories that are associated with models on the semantical side. The completeness parts of the theorems of the latter kind correspond to the type of completeness theorem by which a consistent classical theory is shown to have a non-empty set of classical models; in the case of probability semantics, such a kind of theorem is of course only available if the probability semantics considered includes the notion of a model.

In contrast to the prevailing tradition in epistemology, the focus in this book is on low-level inferences, i.e., those inferences that we are usually not consciously aware of and that we share with the cat nearby which infers that the bird which she sees picking grains from the dirt, is able to fly. Presumably, such inferences are not generated by explicit logical reasoning, but logical methods can be used to describe and analyze such inferences. Part 1 gives a purely system-theoretic explication of belief and inference. Part 2 adds a reliabilist theory of justification for inference, with a qualitative notion of reliability being employed. Part 3 recalls and extends various systems of deductive and nonmonotonic logic and thereby explains the semantics of absolute and high reliability. In Part 4 it is proven that qualitative neural networks are able to draw justified deductive and nonmonotonic inferences on the basis of distributed representations. This is derived from a soundness/completeness theorem with regard to cognitive semantics of nonmonotonic reasoning. The appendix extends the theory both logically and ontologically, and relates it to A. Goldman's reliability account of justified belief.

The last Chapter ended with an informal presentation of Godel’s argument. This one is devoted to a formalized version. I’ll also consider some objections and modifications. There are two kinds of objections. One amounts to saying that Godel committed the same fallacy Descartes did: assuming something equivalent to God’s existence. Nonetheless, again as in the Descartes case, much of the argument is of interest even if it falls short of establishing the desired conclusion. The second kind of objection is that Godel’s axioms are too strong, and lead to a collapse of the modal system involved. Various extensions and modifications of Godel’s axioms have been proposed, to avoid this modal collapse. I’ll discuss these, and propose a modification of my own. Now down to details, with the proof of God’s possible existence coming first. I will not try to match the numbering of the informal axioms in the last chapter, but I will refer to them when appropriate.

Most of the investigations contained in this essay were made for a course in logic, which I gave during the spring term of 1955 at the University of Stockholm. My intention at that time was to present a technique of logical proof that would be easier to master than those usually encountered in textbooks on logic. Thus, the essay may be regarded as having a kind of pedagogical aim. It is hoped that this aim is not overshadowed by the technical character of my exposition.

This chapter is intended as an introduction to the Deduction Theorem and to applications of this theorem in metalogic.

The term Proof Theory shows a certain ambiguity. In the fifties when Stig Kanger carried out his logical work it stood for a cluster of topics pertaining to the syntactic turnstile ⊢, that is, the syntactic counterpart to the semantical notion of (logical) consequence ⊨. On the other hand, and more narrowly, it also stood for investigations of the properties of the syntactic turnstile by means of systematic transformations of derivation trees. Stig Kanger was a proof theorist only in the former sense. For him, model-theoretic semantics, couched in a rich set-theoretic framework, held pride of place, and in this he was very close to the then main European school of logic, namely the Munster School, under the leadership of Heinrich Scholz. There are indeed many questions to be asked with respect to the mere 26 (!!) non-modal pages of Provability in Logic. 1 Not the least of these is the question: where did Stig Kanger find his semantics? He admired Alfred Tarski above all other logicians. By the side of Finnegan’s Wake, Tarski-Mostowski-Robinson, Undecidable Theories,2 and, of course, Der Wahrheitsbegriff in den formalisierten Sprachen,3 would have been with him on the Desert Island. The rare off-print copy of the German (1935) version of Tarski’s masterpiece from 1933, formerly in Stockholms Hogskolas Humanistiska Bibliotek, now in the University library at Stockholm, bears the mark of careful study, but it does contain the model-theoretic semantics in question only derivatively at pp. 361–62: Tarski’s official definition of truth in §3, for the general calculus of classes, is not relativized to a domain of individuals, but quantifies over a universe of everything.

Stig Kanger — born of Swedish parents in China in 1924 — was professor of Theoretical Philosophy at Uppsala University from 1968 until his death in 1988. He received his Ph. D. from Stockholm University in 1957 under the supervision of Anders Wedberg. Kanger’s dissertation, Provability in Logic, was remarkably short, only 47 pages, but also very rich in new ideas and results. By combining Gentzen-style techniques with a model theory a la Tarski, Kanger obtained new and simplified proofs of central metalogical results of classical predicate logic: Godel’s completeness theorem, Lowenheim-Skolem’s theorem and Gentzen’s Hauptsatz. The part that had the greatest impact, however, was the 15 pages devoted to modal logic. There Kanger developed a new semantic interpretation for quantified modal logic which had a close family resemblance to semantic theories that were developed around the same time by Jaakko Hintikka, Richard Montague and Saul Kripke (independently of each other and independently of Kanger).

A Henkin-style completeness proof (of a formal system of non-modal logic) consists of two steps. First, one has to prove that every consistent set is embeddable into a maximal consistent set of sentences. Secondly, one has to show that every maximal consistent set determines (in a natural way) an interpretation satisfying it. There are known adaptations of this method to modal logic. (See, e.g., [4], [5], Chapters IX and X, and [14], §4.) Here the first step is modified as follows. One has to prove that if α is a consistent set of sentences, then there exists a structure 〈W, R, Φ〉 satisfying the following conditions: (i) W is a nonempty set, R ⊆ W 2, Φ is a function defined on W, and the values of Φ are maximal consistent sets of sentences. (ii) For some w 0 ∈ W, α ⫅ Φ(w 0). (iii) For all w#x2208; W, if M f∈ Φ(w), then there is a υ∈ W such that 〈w, υ〉∈ R, and f∈ Φ(υ) hold. (iv) For all w, υ∈ W, if N f∈ Φ(w), and 〈w, υ〉∈ R, then f∈ Φ(υ). (v) R satisfies certain conditions (e.g., R is reflexive).—In the second step, one proves that the structure 〈W, R, Φ〉 determines a modal interpretation 〈W, R, U, ϱ〉 such that for all w∈ W, f∈ Φ(w) iff ϱ(f) w = 1.

If 〈Σ, Φ〉 is a complete μ-tree structure, and II is the set of all parameters occurring in the values of Φ, then there is a μ-interpretation I= 〈W, R, U, ϱ〉 of II with W= Σ such that for all w∈ W, and for all f∈ Co(Φ(w)), ϱ(f)w=1 holds.

In this chapter we shall prove Chang’s completeness theorem stating that if an equation holds in the unit real interval [0,1], then the equation holds in every MV-algebra. Thus, intuitively, the two element structure {0,1} stands to boolean algebras as the interval [0,1] stands to MV-algebras. Our proof is elementary, and makes use of tools (such as “good sequences”) that shall also find applications in a subsequent chapter to show the equivalence between MV-algebras and lattice-ordered abelian groups with strong unit.

Free algebras are universal objects: every n-generated MV-algebra A is a homomorphic image of the free MV-algebra Free n over n generators; if an equation is satisfied by Free n then the equation is automatically satisfied by all MV-algebras. As a consequence of the completeness theorem, Free n is easily described as an MV-algebra of piecewise linear continuous [0,1]-valued functions defined over the cube [0, 1] n . Known as McNaughton functions, they stand to MV-algebras as {0,1}-valued functions stand to boolean algebras. Many interesting classes of MV-algebras can be described as algebras of [0, l]-valued continuous functions over some compact Hausdorff space. The various representation theorems presented in this chapter all depend on our concrete representation of free MV-algebras.

Herbrand’s theorem is a central fact about classical logic [9, 10]. It provides a constructive method for associating, with each first-order formula X, a sequence of formulas X 1, X 2, X 3,..., so that X has a first-order proof if and only if some X i is a tautology. Herbrand’s theorem serves as a constructive alternative to Godel’s completeness theorem. It provides the theoretical basis for automated theorem proving, reducing a first-order problem to a search through an infinite sequence of propositional problems [12]. It provides machinery for theoretical investigations [2]. But it does not travel well. Unlike Gentzen’s cut elimination theorem, or Godel’s completeness theorem, analogs of Herbrand’s result essentially do not exist for nonclassical logics.

The first system of axioms for the arithmetic of natural numbers was proposed in 1889 by the Italian mathematician Giuseppe Peano. Later it has been modified and improved. Its today’s form is called Peano arithmetic. A main difference between Peano arithmetic and the original system of Peano is the fact that in the former no set-theoretical notions appear (such as the notion of a set and the predicate ∈ of being an element of a set).

A full-circle theorem 1 for a given logical system ℒ says that certain proof systems S 1, ..., S 4 for ℒ of the four most important types of inference systems (Hilbert-style, natural deduction, tableaux, sequent calculi) are all equivalent in the following sense (cf. Figure 1): Every proof of a wff A from wffs A 1,..., A k in S 1 can be transformed into a proof of A from A 1,..., A k in S 2; every proof of A from A 1,..., A n in S 4 can be transformed into a proof of A from A 1,..., A k in S 1.

This paper has two parts. In the first part (Chapters 1–4) a general method of constructing axiomatizable approximations for logics with additional quantifiers is given. The completeness theorem relative to a proper weak semantics for these approximations is proved.

In the literature one can find three quite different proofs of the completeness of the infinite-valued sentential calculus of Lukasiewicz [8]: (i). the syntactical proof of Rose and Rosser [7], using McNaughton’s theorem, (ii). the algebraic proof of Chang [1, 2], using quantifier elimination in the first-order theory of divisible totally ordered abelian groups, and (iii). the recent proof of Cignoli [3], using the representation of free latticeordered abelian groups.

Attempts to establish, a priori, the nature and structure of the mind go back to the very origins of philosophy, and have continued apace ever since. The things on the basis of which, people have tried to establish this are many and varied: the phenomenology of consciousness, the nature of action, end even the nature of the state (to take but a few examples). Logic, as traditionally (though incorrectly) conceived, is precisely a compendium of the laws of thought. Hence it is unsurprising that some philosophers have tried to use logic as a basis in the inquiry. The high point of this enterprise was undoubtedly Kant and his successors. Kant thought that the structure of the mind could be read off from the categories of logic – which was, for him, the somewhat bowdlerised form of Aristotelian Logic of his day; and under Hegel, not only the number of categories blossomed, but so did the nature of the mind in question; until it came to encompass everything – literally.

In their paper [29], Rose and Rosser gave a proof of the completeness of the infinite-valued sentential calculus of Lukasiewicz. Their proof is syntactic in nature. In two subsequent papers [7], [8], Chang introduced MV algebras (many-valued algebras), and gave an algebraic proof of the completeness theorem using these structures. Thus, MV algebras were originally introduced as algebraic counterparts of many-valued logic, just as Boolean algebras are the algebraic counterpart of classical, two-valued, logic. Recently, however, MV algebras have found novel and surprising applications, and today they are studied per se. As proved in [19], MV algebras are categorically equivalent to abelian lattice-groups with strong unit. They are also equivalent to bounded commutative BCK algebras [20], and to several other mathematical structures. Composition with the Grothendieck functor K O yields a one-one correspondence between countable MV algebras and approximately finite-dimensional (AF) C*-algebras whose Murray von Neumann ordering of projections is a lattice order. This correspondence has many applications [10], [19], [21], [22], [23]. AF C*-algebras are the mathematical counterpart of quantum spin systems.

It is proposed that a more convenient formalization of predicate calculus is as a free Boolean algebra with extrema for the subsets of variable renaming, these extrema functioning as the quantifiers. In support of this proposal, an ab initio development of the calculus is sketched, a comparison with the standard treatment (which in effect construes the quantifiers as certain closure operators) is made and a proof of the Godel completeness theorem based on this formalization is presented.

The birth of the concept of an algorithm and development of the theory was stimulated not only by practical needs of solving mass problems but also by speculative attempts to comprehend the meaning of the combination of quantifiers ∀x∃y. Both tasks are closely related: on the one hand, if a mass problem is solvable then (∀ individual problem)(∃ solution), on the other hand, to prove a statement that begins with ∀x∃y means to find for any x the corresponding y, i.e. to solve a certain mass problem.

The SAK system is the expert system shell for building diagnostic applications. For knowledge representation in the SAK system, contextually conditioned if-then rules with uncertainty are used. Logical Inlerence Mechanism (LIM) of the system is based on an application of the completeness theorem for Lukasiewicz many-valued logic. As a case study, an expert system for evaluating the inftuence of traffic on the environment in a residential area is presented.

During 1962–63, as a senior at Yale University, I had the good fortune to work as Nuel Belnap’s research assistant. I was helping Nuel (at least he let me feel I was helping) investigate a certain fragment of the logic E of Entailment. Of those days I now recall mainly the excitement of collaboration, on which I have been hooked ever since, and the discovery of what it is like to do research. While I thoroughly enjoyed the experience, it was many years before I completely realized how important working with Nuel had been for me.

The central task of this chapter is to show the Soundness and Completeness of our axiomatizations of the various tense logic systems. This amounts to showing that a statement A is provable (in a given system) from a set S of statements if and only if S entails A (in that system). The upshot of this result is the exact correspondence of the syntactical-deductive and the semantic accounts given for the system.

There are various results due to Godel which are commonly collectively called ‘Godel’s theorem’; of these, we list the most important

Ever since Epimenides made his startling confession, philosophers and mathematicians have been fascinated by self-reference. Of course, mathematicians are not free to admit this.

By set-theoretical model theory I mean the kind of model theory for finitary first order predicate calculus L ω,ω exemplified by the book by Chang and Keisler [C, K]. As we know, parts of this (such as the completeness theorem) can be carried out in a completely elementary framework. The distinctively set-theoretical parts of [C, K] use the theory of transfinite ordinals and cardinals, the axiom of choice and, on occasion, the continuum hypothesis and its generalizations.

The Priorean research program has blossomed into a whole logical discipline; its slightly shaky motivation notwithstanding.1 The enterprise is described in various textbooks already; whence a new introduction is not intended here. This chapter will rather contain a presentation stressing the general lay-out and spirit of the subject, providing a perspective upon contemporary technical research. As these considerations are not restricted to this special field, here is a sketch of the underlying view of logic in general.

In 1931 in the journal Monatshefte fur Mathematik und Physik a short paper (a bit more than 20 pages) of an Austrian mathematician and logician Kurt Godel was published — paper which has turned out to be one of the greatest and most important papers in mathematical logic and foundations of mathematics. Its title was “Uber formal unentscheidbare Satze der ‘Principia Mathematica’ und verwandter Systeme. I”. In it Godel proved that arithmetic of natural numbers and all systems containing it are essentially incomplete provided they are consistent. It means that there are sentences which are undecidable in them, i.e. sentences φ such that neither φ, nor ¬φ are theorems. What’s more, we know which sentence of the pair φ, ¬φ is true in the basic model of the theory, i.e. in the model to the description of which the theory was formulated. This incompleteness is essential, i.e. it cannot be removed by adding the undecidable sentences as a new axioms because new undecidable sentences will appear (undecidable in the new, richer theory). This theorem (so called 1st Godel theorem) indicates the cognitive limitations of the deductive method.

One of the main goals of research in the foundations of mathematics in the 1920’s was to find a consistency proof for number theory. Not that the consistency of number theory was considered to be very dubious, but the consistency of set theory was considered a partially open question and finding a convincing consistency proof for number theory seemed a natural first step in that direction. The possibility of such a proof does not seem too unlikely since we can formalize the statement of consistency in a rather simple form: (x) — Bew(x, ‘0 = 1’). It is true that one would have to use some number theoretic principles or their equivalents to prove a statement of this form, but there was reason to hope that the proof could be carried out in a relatively ‘small’ subsystem, for example, using induction only for quantifier free formulas. Godel showed, however, in 1931 that no such proof was possible.

Until now we did not introduce a formal language when discussing some properties of the relational systems under consideration. For the following we want to use several facts from model theory — a rapidly developing area of formal logic which investigates the connection between formal languages and their interpretations. In order to do so we have to introduce a formal language. This makes our investigation more precise. For our purpose it will be sufficient to consider only a quite simple formal language, namely the first-order logic with identity.

We will begin by proving a fundamental result which will be used repeatedly in the proofs of our major theorems. We will prove it for the full language of quantification theory even though some of our systems will have a restricted vocabulary. No change in the proof is required for the restricted vocabularies.

Modern computers do not only perform much faster tasks which are already feasible for older calculating machines, but are also fit for more refined, more complicated and more differentiated operations. In particular operations such as self-correction and self-programming make one think almost irresistably of ‘intelligent’ and ‘human’ behavior. For that reason it is no wonder that one has begun to speak of ‘thinking machines’. There is no longer a large step needed to arrive at the notion of a ‘thought machine’, even if that is something completely different.

The title of this talk raises the problem, whether it is possible to argue for or against norms. But this is only a problem, if “possible” stands for something like “reasonably possible”. We are asking whether “reasonable argumentation” about norms is possible. This in turn means that we are looking for norms of such argumentations, that we are looking for “meta-norms”, if you like.

My purpose in this paper is to formulate a general completeness problem for statistical theories, and to show that the quantum theory is complete. It follows as a corollary to the completeness theorem for quantum mechanics that a phase space reconstruction of the quantum statistics is excluded, i.e., there are no ‘hidden variables’ underlying the quantum statistics.