This paper presents a recent formalization of a Henkin-style completeness proof for the propositional modal logic S5 using the Lean theorem prover. The proof formalized is close to that of Hughes and Cresswell, but the system, based on a different choice of axioms, is better described as a Mendelson system augmented with axiom schemes for K, T, S4, and B, and the necessitation rule as a rule of inference. The language has the false and implication as the (...) only primitive logical connectives and necessity as the only primitive modal operator. The full source code is available online and has been typechecked with Lean 3.4.2. (shrink)

A simple Henkin-style completeness proof for Gödel 3-valued propositional logic G3 is provided. The idea is to endow G3 with an under-determined semantics of the type defined by Dunn. The key concept in u-semantics is that of “under-determined interpretation”. It is shown that consistent prime theories built upon G3 can be understood as u-interpretations. In order to prove this fact we follow Brady by defining G3 as an extension of Anderson and Belnap’s positive fragment of First Degree (...) Entailment Logic. (shrink)

This paper presents a formalization of the classical proof of completeness in Henkin-style developed by Troelstra and van Dalen for intuitionistic logic with respect to Kripke models. The completeness proof incorporates their insights in a fresh and elegant manner that is better suited for mechanization. We discuss details of our implementation in the Lean theorem prover with emphasis on the prime extension lemma and construction of the canonical model. Our implementation is restricted to a system of (...) intuitionistic propositional logic with implication, conjunction, disjunction, and falsity given in terms of a Hilbert-style axiomatization. As far as we know, our implementation is the first verified Henkin-style proof of completeness for intuitionistic logic following Troelstra and van Dalen's method in the literature. (shrink)

§1. Introduction. This paper deals with aspects of my doctoral dissertation which contributed to the early development of model theory. What was of use to later workers was less the results of my thesis, than the method by which I proved the completeness of first-order logic—a result established by Kurt Gödel in his doctoral thesis 18 years before.The ideas that fed my discovery of this proof were mostly those I found in the teachings and writings of Alonzo Church. This (...) may seem curious, as his work in logic, and his teaching, gave great emphasis to the constructive character of mathematical logic, while the model theory to which I contributed is filled with theorems about very large classes of mathematical structures, whose proofs often by-pass constructive methods.Another curious thing about my discovery of a new proof of Gödel's completeness theorem, is that it arrived in the midst of my efforts to prove an entirely different result. Such “accidental” discoveries arise in many parts of scientific work. Perhaps there are regularities in the conditions under which such “accidents” occur which would interest some historians, so I shall try to describe in some detail the accident which befell me.A mathematical discovery is an idea, or a complex of ideas, which have been found and set forth under certain circumstances. The process of discovery consists in selecting certain input ideas and somehow combining and transforming them to produce the new output ideas. The process that produces a particular discovery may thus be represented by a diagram such as one sees in many parts of science; a “black box” with lines coming in from the left to represent the input ideas, and lines going out to the right representing the output. To describe that discovery one must explain what occurs inside the box, i.e., how the outputs were obtained from the inputs. (shrink)

Hebrew and Arabic in Asymmetric Contact in Israel Israeli Hebrew and Palestinian Arabic 1 have existed side by side for well over a century in extremely close contact, accompanied by social and ideological tension, often conflict, between two communities: PA speakers, who turned from a majority to a minority following the establishment of the State of Israel in 1948, and IH speakers, the contemporary majority, representing the dominant culture. The Hebrew-speaking Jewish group is heterogeneous in terms of lands of origin (...) and includes a large community of Judeo-Arabic speakers. In this paper I discuss the ‘when,’ ‘where,’ how,' and especially ‘why’ of mutual borrowing2 between Hebrew and Arabic in Israel since the 1880s.I stress that the contact is asymmetric. The majority of Hebrew speakers today do not speak Arabic. They do, however, have access to borrowed lexicon in the domain of slang and vernacular speech that both enriches these registers and provides the speakers with a feeling of being ‘indigenous’ and ‘belonging’ to the social and cultural milieu of the larger environment. In contrast, most young adult PA-speakers are bilingual. For this minority, borrowing fulfills fundamental sociolinguistic and pragmatic needs. IH lexical items have permeated all areas of professional, educational, administrative, and social activities in everyday life discourse in all styles and registers of the spoken language and, to a lesser extent, written language. They fill lexical gaps and lacunae representing modern and western concepts that did not exist in PA. They also symbolize modernism, education, and social mobility. In other words, borrowing serves as a means of ‘stepping in’ for the Jewish majority and conversely as a means for ‘stepping out and up’ for the Arab minority. (shrink)

About a month after his 83rd birthday Raphael Robinson was almost wholly incapacitated by a massive stroke, and 8 weeks later, on January 27, 1995, he died of ensuing complications. Mathematics was his life. He was always working on problems—those brought to him in journals or by colleagues, and others that he invented. Just three days before his death he received word that a paper of his, originating in a published problem, was accepted for publication. His 64 publications spanned a (...) full 6 decades, and included significant papers on number theory, combinatorics, complex analysis, and geometry, in addition to logic and set theory.Robinson was born on November 2, 1911, in National City, California. He came to Berkeley to study mathematics, obtaining an A.B. in 1932, an M.A. in 1933, and his Ph.D. in December, 1934. His dissertation was in complex analysis. He took 12 graduate courses in a variety of fields, but not one was close to logic or set theory—which was later the setting of about a quarter of his publications.After completing his studies Robinson served as Instructor for two years at Brown University, then returned for good to Berkeley in 1937, reaching the rank of full Professor in 1949. He taught a great variety of courses and was known as an excellent teacher, but was most interested in problemsolving and research and in 1972, at age 61, he elected early retirement, at considerable financial sacrifice, in order to concentrate on these pursuits. (shrink)

We show that basic hybridization makes it possible to give straightforward Henkin-style completeness proofs even when the modal logic being hybridized is higher-order. The key ideas are to add nominals as expressions of type t, and to extend to arbitrary types the way we interpret \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$@_i$\end{document} in propositional and first-order hybrid logic. This means: interpret \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$@_i\alpha _a$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} (...) \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\alpha _a$\end{document} is an expression of any type \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$a$\end{document}, as an expression of type \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$a$\end{document} that rigidly returns the value that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\alpha_a$\end{document} receives at the i-world. The axiomatization and completeness proofs are generalizations of those found in propositional and first-order hybrid logic, and we automatically obtain a wide range of completeness results for stronger logics and languages. Our approach is deliberately low-tech. We don’t, for example, make use of Montague’s intensional type s, or Fitting-style intensional models; we build, as simply as we can, hybrid logicover Henkin’s logic. (shrink)

We show that basic hybridization (adding nominals and @ operators) makes it possible to give straightforward Henkin-style completeness proofs even when the modal logic being hybridized is higher-order. The key ideas are to add nominals as expressions of type t, and to extend to arbitrary types the way we interpret $@_i$ in propositional and first-order hybrid logic. This means: interpret $@_i\alpha _a$ , where $\alpha _a$ is an expression of any type $a$ , as an expression of (...) type $a$ that rigidly returns the value that $\alpha_a$ receives at the i-world. The axiomatization and completeness proofs are generalizations of those found in propositional and first-order hybrid logic, and (as is usual inhybrid logic) we automatically obtain a wide range of completeness results for stronger logics and languages. Our approach is deliberately low-tech. We don’t, for example, make use of Montague’s intensional type s, or Fitting-style intensional models; we build, as simply as we can, hybrid logicover Henkin’s logic. (shrink)

A general result is proved about the existence of maximally consistent theories satisfying prescribed closure conditions. The principle is then used to give streamlined proofs of completeness and omitting-types theorems, in which inductive Henkin-style constructions are replaced by a demonstration that a certain theory respects a certain class of inference rules.

We propose a new approach to positive modal logics, hereby called anodic modal logics. Our treatment is completely positive since the language has neither negation nor any falsum or minimal particle. The elimination of the minimal particle of the language requires introducing the new concept of factual sets and factual deductions which permit us to talk about deductions in the actual world. We start from a positive fragment of the standard system K, denoted by K⊃, ∧, ◊, which is a (...) bimodal system with □ and ◊ as primitive. This system is then extended to a class of fragments of the Lemmon and Scott systems (cf. (Lemmon et al., 1977)), denoted by K⊃, ∧, ◊ + Gk;l;m;n + Gm;n;k;l. It is shown that such classes of systems are characterized with respect to the usual Kripke-style semantics. The proof is by way of a Henkin-style construction, with “possible worlds” being taken to be prime theories as introduced in the modal context by J. M. Dunn in (Dunn, 1995). We also obtain a surprising limiting result showing that the incompleteness phenomenon in modal logic is independent of negation. (shrink)

The semantics of e-models for tense logics with binary operators for `until' and `since' (US-logics) was introduced by Bellissima and Bucalo in 1995. In this paper we show the adequacy of these semantics by proving a general Henkin-style completeness theorem. Moreover, we show that for these semantics there holds a Stone-like duality theorem with the algebraic structures that naturally arise from US-logics.

Mitchell, J.C. and E. Moggi, Kripke-style models for typed lambda calculus, Annals of Pure and Applied Logic 51 99–124. The semantics of typed lambda calculus is usually described using Henkin models, consisting of functions over some collection of sets, or concrete cartesian closed categories, which are essentially equivalent. We describe a more general class of Kripke-style models. In categorical terms, our Kripke lambda models are cartesian closed subcategories of the presheaves over a poset. To those familiar with (...) Kripke models of modal or intuitionistic logics, Kripke lambda models are likely to seem adequately ‘semantic’. However, when viewed as cartesian closed categories, they do not have the property variously referred to as concreteness, well- pointedness or having enough points. While the traditional lambda calculus proof system is not complete for Henkin models that may have empty types, we prove strong completeness for Kripke models. In fact, every set of equations that is closed under implication is the theory of a single Kripke model. We also develop some properties of logical relations over Kripke structures, showing that every theory is the theory of a model determined by a Kripke equivalence relation over a Henkin model. We discuss cartesian closed categories but present the main definitions and results without the use of category theory. (shrink)

An algebraic setting for the validity of Pavelka style completeness for some natural expansions of Łukasiewicz logic by new connectives and rational constants is given. This algebraic approach is based on the fact that the standard MV-algebra on the real segment [0, 1] is an injective MV-algebra. In particular the logics associated with MV-algebras with product and with divisible MV-algebras are considered.

Graham Priest takes the relation of identity to be non-transitive. In this paper, we are going to discuss several consequences of identity as a non-transitive relation. We will consider the Henkin-style completeness proof for classical first-order logic with a non-transitive “identity” predicate, Leibniz-identity in Priest’s second-order minimal logic of paradox, and the question whether or not identity of individuals should be defined as Leibniz-identity.

John Corcoran’s natural deduction system for Aristotle’s syllogistic is reconsidered.Though Corcoran is no doubt right in interpreting Aristotle as viewing syllogisms as arguments and in rejecting Lukasiewicz’s treatment in terms of conditional sentences, it is argued that Corcoran is wrong in thinking that the only alternative is to construe Barbara and Celarent as deduction rules in a natural deduction system.An alternative is presented that is technically more elegant and equally compatible with the texts.The abstract role assigned by tradition and Lukasiewicz (...) to Barbara and Celarent is retained.The two ‘ perfect syllogisms’ serve as ‘basic elements’ in the construction of an inductively defined set of valid syllogisms.The proposal departs from Lukasiewicz, and follows Corcoran, however, in construing the construction as one in natural deduction.The result is a sequent system with fewer rules and in which Barbara and Celarent serve as basic deductions.To compare the theory to Corcoran’s, his original is reformulated in current terms and generalized.It is shown to be equivalent to the proposed sequent system, and several variations are discussed.For all systems mentioned, a method of Henkin‐style completeness proofs is given that is more direct and intuitive than Corcoran’s original. (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)

Proofs and countermodels are the two sides of completeness proofs, but, in general, failure to find one does not automatically give the other. The limitation is encountered also for decidable non-classical logics in traditional completeness proofs based on Henkin’s method of maximal consistent sets of formulas. A method is presented that makes it possible to establish completeness in a direct way: For any given sequent either a proof in the given logical system or a countermodel in (...) the corresponding frame class is found. The method is a synthesis of a generation of calculi with internalized relational semantics, a Tait–Schütte–Takeuti style completeness proof, and procedures to finitize the countermodel construction. Finitizations for intuitionistic propositional logic are obtained through the search for a minimal derivation, through pruning of infinite branches in search trees by means of a suitable syntactic counterpart of semantic filtration, or through a proof-theoretic embedding into an appropriate provability logic. A number of examples illustrates the method, its subtleties, challenges, and present scope. (shrink)

The paper addresses Leon Hen.kin's proposition as a " lighthouse", which can elucidate a vast territory of knowledge uniformly: logic, set theory, information theory, and quantum mechanics: Two strategies to infinity are equally relevant for it is as universal and t hus complete as open and thus incomplete. Henkin's, Godel's, Robert Jeroslow's, and Hartley Rogers' proposition are reformulated so that both completeness and incompleteness to be unified and thus reduced as a joint property of infinity and of all (...) infinite sets. However, only Henkin's proposition equivalent to an internal position to infinity is consistent . This can be retraced back to set theory and its axioms, where that of choice is a key. Quantum mechanics is forced to introduce infinity implicitly by Hilbert space, on which is founded its formalism. One can demonstrate that some essential properties of quantum information, entanglement, and quantum computer originate directly from infinity once it is involved in quantum mechanics. Thus, these phenomena can be elucidated as both complete and incomplete, after which choice is the border between them. A special kind of invariance to the axiom of choice shared by quantum mechanics is discussed to be involved that border between the completeness and incompleteness of infinity in a consistent way. The so-called paradox of Albert Einstein, Boris Podolsky, and Nathan Rosen is interpreted entirely in the same terms only of set theory. Quantum computer can demonstrate especially clearly the privilege of the internal position, or " observer'' , or "user" to infinity implied by Henkin's proposition as the only consistent ones as to infinity. An essential area of contemporary knowledge may be synthesized from a single viewpoint. (shrink)

This paper focuses on the evolution of the notion of completeness in contemporary logic. We discuss the differences between the notions of completeness of a theory, the completeness of a calculus, and the completeness of a logic in the light of Gödel's and Tarski's crucial contributions.We place special emphasis on understanding the differences in how these concepts were used then and now, as well as on the role they play in logic. Nevertheless, we can still observe (...) a certain ambiguity in the use of the close notions of completeness of a calculus and completeness of a logic. We analyze the state of the art under which Gödel's proof of completeness was developed, particularly when dealing with the decision problem for first-order logic. We believe that Gödel had to face the following dilemma: either semantics is decidable, in which case the completeness of the logic is trivial or, completeness is a critical property but in this case it cannot be obtained as a corollary of a previous decidability result. As far as first-order logic is concerned, our thesis is that the contemporary understanding of completeness of a calculus was born as a generalization of the concept of completeness of a theory. The last part of this study is devoted to Henkin's work concerning the generalization of his completeness proof to any logic from his initial work in type theory. (shrink)

The semantical structures called T×W frames were introduced in (Thomason, 1984) for the Ockhamist temporal-modal language, ℒO, which consists of the usual propositional language augmented with the Priorean operators P and F and with a possibility operator ⋄. However, these structures are also suitable for interpreting an extended language, ℒSO, containing a further possibility operator ⋄s which expresses synchronism among possibly incompatible histories and which can thus be thought of as a cross-history ‘simultaneity’ operator. In the present paper we provide (...) an infinite set of axioms in ℒSO, which is shown to be strongly complete forT ×W-validity. Von Kutschera (1997) contains a finite axiomatization of T×W-validity which however makes use of the Gabbay Irreflexivity Rule (Gabbay, 1981). In order to avoid using this rule, the proof presented here develops a new technique to deal with reflexive maximal consistent sets in Henkin-style constructions. (shrink)

In this paper we present a solution of the axiomatization problem for the Fmla-Fmla versions of the Pietz and Rivieccio exactly true logic and the non-falsity logic dual to it. To prove the completeness of the corresponding binary consequence systems we introduce a specific proof-theoretic formalism, which allows us to deal simultaneously with two consequence relations within one logical system. These relations are hierarchically organized, so that one of them is treated as the basic for the resulting logic, and (...) the other is introduced as an extension of this basic relation. The proposed bi-consequences systems allow for a standard Henkin-style canonical model used in the completeness proof. The deductive equivalence of these bi-consequence systems to the corresponding binary consequence systems is proved. We also outline a family of the bi-consequence systems generated on the basis of the first-degree entailment logic up to the classic consequence. (shrink)

In this paper we present a solution of the axiomatization problem for the Fmla-Fmla versions of the Pietz and Rivieccio exactly true logic and the non-falsity logic dual to it. To prove the completeness of the corresponding binary consequence systems we introduce a specific proof-theoretic formalism, which allows us to deal simultaneously with two consequence relations within one logical system. These relations are hierarchically organized, so that one of them is treated as the basic for the resulting logic, and (...) the other is introduced as an extension of this basic relation. The proposed bi-consequences systems allow for a standard Henkin-style canonical model used in the completeness proof. The deductive equivalence of these bi-consequence systems to the corresponding binary consequence systems is proved. We also outline a family of the bi-consequence systems generated on the basis of the first-degree entailment logic up to the classic consequence. (shrink)

The semantical structures called T x W frames were introduced in (Thomason, 1984) for the Ockhamist temporal-modal language, $[Unrepresented Character]_{o}$ , which consists of the usual propositional language augmented with the Priorean operators P and F and with a possibility operator ◇. However, these structures are also suitable for interpreting an extended language, $[Unrepresented Character]_{so}$ , containing a further possibility operator $\lozenge^{s}$ which expresses synchronism among possibly incompatible histories and which can thus be thought of as a cross-history 'simultaneity' operator. (...) In the present paper we provide an infinite set of axioms in $[Unrepresented Character]_{so}$ , which is shown to be strongly complete for T x W-validity. Von Kutschera (1997) contains a finite axiomatization of T x W-validity which however makes use of the Gabbay Irreflexivity Rule (Gabbay, 1981). In order to avoid using this rule, the proof presented here develops a new technique to deal with reflexive maximal consistent sets in Henkin-style constructions. (shrink)

Simple type theory is a higher-order predicate logic for reasoning about truth values, individuals, and simply typed total functions. We present in this paper a version of simple type theory, called PF*, in which functions may be partial and types may have subtypes. We define both a Henkin-style general models semantics and an axiomatic system for PF*, and we prove that the axiomatic system is complete with respect to the general models semantics. We also define a notion of (...) an interpretation of one PF* theory in another. PF* is intended as a foundation for mechanized mathematics. It is the basis for the logic of, an Interactive Mathematical Proof System developed at The MITRE Corporation. (shrink)

One of the logic defined by Richard Epstein in a context of an analysis of subject matter relationship is Symmetric Relatedness Logic S. In the monograph [2] we can find some open problems concerning relatedness logic, a Post-style completeness theorem for logic S is one of them. Our paper introduces a solution of this metalogical issue.

Simple type theory is a higher-order predicate logic for reasoning about truth values, individuals, and simply typed total functions. We present in this paper a version of simple type theory, called PF*, in which functions may be partial and types may have subtypes. We define both a Henkin-style general models semantics and an axiomatic system for PF*, and we prove that the axiomatic system is complete with respect to the general models semantics. We also define a notion of (...) an interpretation of one PF* theory in another. PF* is intended as a foundation for mechanized mathematics. It is the basis for the logic of , an Interactive Mathematical Proof System developed at The MITRE Corporation. (shrink)

American-plan semantics with 4 values 1, 0, { {1, 0}} {{}}, interpretable as True, False, Both and Neither, are furnished for a range of logics, including relevant affixing systems. The evaluation rules for extensional connectives take a classical form: in particular, those for negation assume the form 1 (A, a) iff 0 (A, a) and 0 (A, a) iff 1 (A, a), so eliminating the star function *, on which much criticism of relevant logic semantics has focussed. The cost of (...) these classical features is a further relation (or operation), required in evaluating falsity assignments of implication formulae.Two styles of 4 valued relational semantics are developed; firstly a semantics using notions of double truth and double validity for basic relevant systemB and some extensions of it; and secondly, since the first semantics makes heavy weather of validating negation principles such as Contraposition, a reduced semantics using more complex implicational rules for relevant systemC and various of its extensions. To deal satisfactorily with elite systemsR,E andT, however, further complication is inevitable; and a relation of mateship (suggested by the Australian plan) is introduced to permit cross-over from 1 to 0 values and vice versa. (shrink)