In this paper we give a proof of the II12-completeness of the set of countable better quasi orderings . This result was conjectured by Clote in [2] and proved by the author in his Ph.d. thesis [6] . Here we prove it using Simpson's definition of better quasi ordering and as little bqo theory as possible.

A grafted frame is a new kind of frame which combines a modal frame and some relevance frames. A grafted model consists of a grafted frame and a truth-value assignment. In this paper, the grafted frame and the grafted model are constructed and used to show the completeness of S1. The implications of S1-completeness are discussed. A grafted frame does not combine two kinds of frames simply by putting relations defined in the components together. That is, the resulting grafted frame (...) is not in the form of $\langle W, R, R'\rangle$ , or more generally, in the form of $\langle W, R, R', R'',...\rangle$ , which consists of a non-empty set with several relations defined on it. Rather, it resembles the construction of fibering proposed by D. M. Gabbay and M. Finger (see [4] and [3]). On a grafted frame, some modal worlds, which belong to the initial modal frame, are attached by some relevance frames. However, these two semantics have important differences. Consider the combined semantics involving semantics of relevance logic and modal logic. A fibred model and a grafted model proposed in this paper differ in the following respects. First, a fibred model is constructed from a class of modal models and a class of relevance models. A grafted model consists of a grafted frame and a truth-value assignment, where the grafted frame is constructed from a modal frame and some relevance frames, and the assignment is a union of a modal truth-value assignment V M and some relevance truth-value assignments V R . V M (V R ) defined in this paper is not the same as the assignment contained in a modal (relevance) model. Second, in a fibred model each relevance world is associated (or fibred) with a modal model and each modal world with a relevance model. To be the grafted frame on which a grafted model is based, it is enough to have some modal worlds attached by some relevance frames. Moreover, no relevance world is associated with a modal frame in the grafted frame. Third, fibred models are intended to provide an appropriate semantics to combined logics. Grafted frames and grafted models are inspired to characterize S1, which, containing only one modality □, is not a combined logic. It is shown in this paper that S1 is sort of a meta-logic of the intersection of S0.4 and F, where S0.4, a new system proposed in this paper, is in turn a meta-logic of the relevance logic. (shrink)

Several proof-theoretic notions of validity have been proposed in the literature, for which completeness of intuitionistic logic has been conjectured. We define validity for intuitionistic propositional logic in a way which is common to many of these notions, emphasizing that an appropriate notion of validity must be closed under substitution. In this definition we consider atomic systems whose rules are not only production rules, but may include rules that allow one to discharge assumptions. Our central result shows that Harrop’s rule (...) is valid under substitution, which refutes the completeness conjecture for intuitionistic logic. (shrink)

Any explanation of one fact in terms of another will appeal to some sort of connection between the two. In a causal explanation, the connection might be a causal mechanism or law. But not all explanations are causal, and neither are all explanatory connections. For example, in explaining the fact that a given barn is red in terms of the fact that it is crimson, we might appeal to a non-causal connection between things’ being crimson and their being red. Many (...) such connections, like this one, are general rather than particular. I call these general non-causal explanatory connections 'laws of metaphysics'. In this paper I argue that some of these laws are to be found in the world at its most fundamental level, forming a bridge between fundamental reality and everything else. It is only by admitting fundamental laws, I suggest, that we can do justice to the explanatory relationship between what is fundamental and what is not. And once these laws are admitted, we are able to provide a nice resolution of the puzzle of why there are any non-fundamental facts in the first place. (shrink)

In the first year of the twentieth century, in Gottingen, Husserl delivered two talks dealing with a problem that proved central in his philosophical development, that of imaginary elements in mathematics. In order to solve this problem Husserl introduced a logical notion, called “definiteness”, and variants of it, that are somehow related, he claimed, to Hilbert’s notions of completeness. Many different interpretations of what precisely Husserl meant by this notion, and its relations with Hilbert’s ones, have been proposed, but no (...) consensus has been reached. In this paper I approach this question afresh and thoroughly, taking into consideration not only the relevant texts and context, as others have also done before, but, more importantly, Husserl’s philosophy, his intuition-based epistemology in particular. Based on a system of clearly defined concepts that I here present, I reinforce an interpretation—definiteness as a form of syntactic completeness—that has, I believe, some advantages vis-à-vis alternative interpretations. It is in conformity with the available texts; it makes clear that Husserl’s notion of definiteness is indeed close to Hilbert’s notions of completeness; it solves the important problem of imaginaries for which it was created; and last, but not least, it fits naturally into Husserl’s system of concepts and ideas. (shrink)

-/- Continuous first-order logic has found interest among model theorists who wish to extend the classical analysis of “algebraic” structures (such as fields, group, and graphs) to various natural classes of complete metric structures (such as probability algebras, Hilbert spaces, and Banach spaces). With research in continuous first-order logic preoccupied with studying the model theory of this framework, we find a natural question calls for attention. Is there an interesting set of axioms yielding a completeness result? -/- The primary purpose (...) of this article is to show that a certain, interesting set of axioms does indeed yield a completeness result for continuous first-order logic. In particular, we show that in continuous first-order logic a set of formulae is (completely) satisfiable if (and only if) it is consistent. From this result it follows that continuous first-order logic also satisfies an approximated form of strong completeness, whereby Σ⊧φ (if and) only if Σ⊢φ ∸2−n for all n < ω. This approximated form of strong completeness asserts that if Σ⊧φ, then proofs from Σ, being finite, can provide arbitrarily better approximations of the truth of φ. -/- Additionally, we consider a different kind of question traditionally arising in model theory—that of decidability. When is the set of all consequences of a theory (in a countable, recursive language) recursive? Say that a complete theory T is decidable if for every sentence φ, the value φ T is a recursive real, and moreover, uniformly computable from φ. If T is incomplete, we say it is decidable if for every sentence φ the real number φ T o is uniformly recursive from φ, where φ T o is the maximal value of φ consistent with T. As in classical first-order logic, it follows from the completeness theorem of continuous first-order logic that if a complete theory admits a recursive (or even recursively enumerable) axiomatization then it is decidable. (shrink)

The paper studies the containment companion of a logic \. This consists of the consequence relation \ which satisfies all the inferences of \, where the variables of the conclusion are contained into those of the set of premises, in case this is not inconsistent. In accordance with the work started in [10], we show that a different generalization of the Płonka sum construction, adapted from algebras to logical matrices, allows to provide a matrix-based semantics for containment logics. In particular, (...) we provide an appropriate completeness theorem for a wide family of containment logics, and we show how to produce a complete Hilbert style axiomatization. (shrink)

When is an artwork complete? Most hold that the correct answer to this question is psychological in nature. A work is said to be complete just in case the artist regards it as complete or is appropriately disposed to act as if he or she did. Even though this view seems strongly supported by metaphysical, epistemological, and normative considerations, this article argues that such psychologism about completeness is mistaken, fundamentally, because it cannot make sense of the artist's own perspective on (...) his or her work. For the artist, the question is not about his or her own psychology, but about the character of the work and the context in which he or she works. A nonpsychological account of completeness, on which completeness is a question of whether the work satisfies the conditions implicit in the artist's plan, avoids this problem and is equally or better able to explain the metaphysical, epistemic, and normative phenomena which appeared to support psychologism. (shrink)

The paper discusses Husserl’s notion of definiteness as presented in his Göttingen Mathematical Society Double Lecture of 1901 as a defense of two, in many cases incompatible, ideals, namely full characterizability of the domain, i.e., categoricity, and its syntactic completeness. These two ideals are manifest already in Husserl’s discussion of pure logic in the Prolegomena: The full characterizability is related to Husserl’s attempt to capture the interconnection of things, whereas syntactic completeness relates to the interconnection of truths. In the Prolegomena (...) Husserl argues that an ideally complete theory gives an independent norm for objectivity for logic and experiential sciences, hence the notion is central to his argument against psychologism. In the Double Lecture the former is captured by non-extendibility, that is, categoricity of the domain, from which, so Husserl assumes, syntactic completeness is thought to follow. In the so-called ‘mathematical manifolds’ the expressions of the theory are equations that are reducible to equations between elements of the theory. With such an equational reduction structure individual elements of the domain are given criteria of identity and hence they are fully determined. (shrink)

In this paper, we present several extensions of epistemic logic with update operators modelling public information change. Next to the well-known public announcement operators, we also study public substitution operators. We prove many of the results regarding expressivity and completeness using so-called reduction axioms. We develop a general method for using reduction axioms and apply it to the logics at hand.

English translation by Kneller and Losonsky of Klaus Reich, Die Vollständigkeit der Kantischen Urteilstafel -/- "This classic of Kant scholarship, whose first edition appeared in 1932, deals with one of the most controversial and difficult topics in the Critique of Pure Reason: Kant's table of judgments and their connection to the table of categories. Kant's attempt to derive the latter from the former is called the "Metaphysical Deduction," and it paves the way for the Transcendental Deduction that is universally recognized (...) as the heart of the Critique." "Many commentators have passed over the Metaphysical Deduction in silence, as if embarrassed by Kant's fatuity, and his critics are almost unanimous in finding its premise ungrounded, its argument incorrect, and its conclusion false. At the heart of the failure of the Metaphysical Deduction, it is alleged, is Kant's inability to justify the table of the forms of judgment. Critics argue that Kant simply took these forms of judgment from the logic textbooks of his day and doctored them so as to yield the required categories. Such objections were current even in Kant's time; they were repeated by Hegel, and are commonplaces of Kant criticism today." "This book is the fullest and most systematic evaluation ever made of the Metaphysical Deduction. Reich argues that its principal conclusion is correct even though Kant failed to establish it in the Metaphysical Deduction proper, and he defends the conclusion by using Kant material far removed from the text of the Metaphysical Deduction, notes by Kant that only became available in the 1920's and that remain even now untranslated into English. With the publication of this translation for English-speaking Kant scholars, a neglected and impugned part of the Critique of Pure Reason can finally receive the attention it deserves."--BOOK JACKET.Title Summary field provided by Blackwell North America, Inc. All Rights Reserved. (shrink)

T × W logic is a combination of tense and modal logic for worlds or histories with the same time order. It is the basis for logics of causation, agency and conditionals, and therefore an important tool for philosophical logic. Semantically it has been defined, among others, by R. H. Thomason. Using an operator expressing truth in all worlds, first discussed by C. M. Di Maio and A. Zanardo, an axiomatization is given and its completeness proved via D. Gabbay’s irreflexivity (...) lemma. Given this lemma the proof is more or less straight forward. At the end an alternative axiomatization is sketched in which Di Maio’s and Zanardo’s operator is replaced by a version of “actually”. (shrink)

Bi-intuitionistic logic is the union of intuitionistic and dual intuitionistic logic, and was introduced by Rauszer as a Hilbert calculus with algebraic and Kripke semantics. But her subsequent ‘cut-free’ sequent calculus has recently been shown to fail cut-elimination. We present a new cut-free sequent calculus for bi-intuitionistic logic, and prove it sound and complete with respect to its Kripke semantics. Ensuring completeness is complicated by the interaction between intuitionistic implication and dual intuitionistic exclusion, similarly to future and past modalities in (...) tense logic. Our calculus handles this interaction using derivations and refutations as first class citizens. We employ extended sequents which pass information from premises to conclusions using variables instantiated at the leaves of refutations, and rules which compose certain refutations and derivations to form derivations. Automated deduction using terminating backward search is also possible, although this is not our main purpose. (shrink)

Non-trivial calculi of inductive inference are incomplete. This result is demonstrated formally elsewhere. Here the significance and background to the result is described. This note explains what is meant by incompleteness, why it is desirable, if only it could be secured, and it gives some indication of the arguments needed to establish its failure. The discussion will be informal, using illustrative examples rather than general results. Technical details and general proofs are presented in Norton.

T × W logic is a combination of tense and modal logic for worlds or histories with the same time order. It is the basis for logics of causation, agency and conditionals, and therefore an important tool for philosophical logic. Semantically it has been defined, among others, by R. H. Thomason. Using an operator expressing truth in all worlds, first discussed by C. M. Di Maio and A. Zanardo, an axiomatization is given and its completeness proved via D. Gabbay’s irreflexivity (...) lemma. Given this lemma the proof is more or less straight forward. At the end an alternative axiomatization is sketched in which Di Maio’s and Zanardo’s operator is replaced by a version of actually. (shrink)

In this paper we introduce canonical extensions of partially ordered sets and monotone maps and a corresponding discrete duality. We then use these to give a uniform treatment of completeness of relational semantics for various substructural logics with implication as the residual(s) of fusion.

§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)

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.

The success of the AGM paradigmn, Gis remarkable, as even a quick look at the literature it has generated will testify. But it is also remarkable, at least in hindsight, how limited was the original effort. For example, the theory concerns the beliefs of just one agent; all incoming information is accepted; belief change is uniquely determined by the new information; there is no provision for nested beliefs. And perhaps most surprising: there is no analysis of iterated change.

We consider the notion of structural completeness with respect to arbitrary (finitary and/or infinitary) inferential rules. Our main task is to characterize structurally complete intermediate logics. We prove that the structurally complete extension of any pure implicational in termediate logic C can be given as an extension of C with a certain family of schematically denned infinitary rules; the same rules are used for each C. The cardinality of the family is continuum and, in the case of (the pure implicational (...) fragment of) intuitionistic logic, the family cannot be reduced to a countable one. It means that the structurally complete extension of the intuitionistic logic is not countably axiomatizable by schematic rules. (shrink)

This paper presents an abstract study of completeness properties of non-classical logics with respect to matricial semantics. Given a class of reduced matrix models we define three completeness properties of increasing strength and characterize them in several useful ways. Some of these characterizations hold in absolute generality and others are for logics with generalized implication or disjunction connectives, as considered in the previous papers. Finally, we consider completeness with respect to matrices with a linear dense order and characterize it in (...) terms of an extension property and a syntactical metarule. This is the final part of the investigation started and developed in the papers :417–446, 2010; Arch Math Logic 53:353–372, 2016). (shrink)

Peirce’s diagrammatic system of Existential Graphs (EGα)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$EG_{\alpha })$$\end{document} is a logical proof system corresponding to the Propositional Calculus (PL). Most known proofs of soundness and completeness for EGα\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$EG_{\alpha }$$\end{document} depend upon a translation of Peirce’s diagrammatic syntax into that of a suitable Frege-style system. In this paper, drawing upon standard results but using the native diagrammatic notational framework of the graphs, we present (...) a purely syntactic proof of soundness, and hence consistency, for EGα\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$EG_{\alpha }$$\end{document}, along with two separate completeness proofs that are constructive in the sense that we provide an algorithm in each case to construct an EGα\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$EG_{\alpha }$$\end{document} formal proof starting from the empty Sheet of Assertion, given any expression that is in fact a tautology according to the standard semantics of the system. (shrink)

We present an abstract social aggregation theorem. Society, and each individual, has a preorder that may be interpreted as expressing values or beliefs. The preorders are allowed to violate both completeness and continuity, and the population is allowed to be infinite. The preorders are only assumed to be represented by functions with values in partially ordered vector spaces, and whose product has convex range. This includes all preorders that satisfy strong independence. Any Pareto indifferent social preorder is then shown to (...) be represented by a linear transformation of the representations of the individual preorders. Further Pareto conditions on the social preorder correspond to positivity conditions on the transformation. When all the Pareto conditions hold and the population is finite, the social preorder is represented by a sum of individual preorder representations. We provide two applications. The first yields an extremely general version of Harsanyi's social aggregation theorem. The second generalizes a classic result about linear opinion pooling. (shrink)

The standard axiomatization of quantum mechanics (QM) is not fully explicit about the role of the time-parameter. Especially, the time reference within the probability algorithm (the Born Rule, BR) is unclear. From a probability principle P1 and a second principle P2 affording a most natural way to make BR precise, a logical conflict with the standard expression for the completeness of QM can be derived. Rejecting P1 is implausible. Rejecting P2 leads to unphysical results and to a conflict with a (...) generalization of P2, a principle P3. All three principles are shown to be without alternative. It is thus shown that the standard expression of QM completeness must be revised. An absolutely explicit form of the axioms is provided, including a precise form of the projection postulate. An appropriate expression for QM completeness, reflecting the restrictions of the Gleason and Kochen-Specker theorems is proposed. (shrink)

Traditionally, many writers, following Kleene (1952), thought of the Church-Turing thesis as unprovable by its nature but having various strong arguments in its favor, including Turing’s analysis of human computation. More recently, the beauty, power, and obvious fundamental importance of this analysis, what Turing (1936) calls “argument I,” has led some writers to give an almost exclusive emphasis on this argument as the unique justification for the Church-Turing thesis. In this chapter I advocate an alternative justification, essentially presupposed by Turing (...) himself in what he calls “argument II.” The idea is that computation is a special form of mathematical deduction. Assuming the steps of the deduction can be stated in a first order language, the Church-Turing thesis follows as a special case of Gödel’s completeness theorem (first order algorithm theorem). I propose this idea as an alternative foundation for the Church-Turing thesis, both for human and machine computation. Clearly the relevant assumptions are justified for computations presently known. Other issues, such as the significance of Gödel’s 1931 Theorem IX for the Entscheidungsproblem, are discussed along the way. (shrink)

Completeness is an important but misunderstood norm of explanation. It has recently been argued that mechanistic accounts of scientific explanation are committed to the thesis that models are complete only if they describe everything about a mechanism and, as a corollary, that incomplete models are always improved by adding more details. If so, mechanistic accounts are at odds with the obvious and important role of abstraction in scientific modelling. We respond to this characterization of the mechanist’s views about abstraction and (...) articulate norms of completeness for mechanistic explanations that have no such unwanted implications. _1_ Introduction _2_ A Balancing Act: When Do Details Matter? _3_ The Norms of Causal Explanation _4_ The Norms of Constitutive Explanation _5_ Salmon-Completeness _6_ From More Details to More Relevant Details _7_ Non-explanatory Virtues of Abstraction _8_ From Explanatory Models to Explanatory Knowledge _9_ Mechanistic Completeness Reconsidered _10_ Conclusion. (shrink)