In this paper we discuss sequent calculi for the propositional fragment of the logic of HYPE. The logic of HYPE was recently suggested by Leitgeb as a logic for hyperintensional contexts. On the one hand we introduce a simple \-system employing rules of contraposition. On the other hand we present a \-system with an admissible rule of contraposition. Both systems are equivalent as well as sound and complete proof-system of HYPE. In order to provide a cut-elimination procedure, we expand the (...) calculus by connections as introduced in Kashima and Shimura. (shrink)

Ātman (soul) and Nairātmya (no soul) are, for the Brahmanical schools and the Buddhists respectively, equally fundamental tenets which neither side can concede to the other. Among the 16 formulations presented by Uddyotakara, the fifteenth, which is a proof of Ātman and is originally an indirect proof ( avīta/āvīta ), is presented in a prasaṅga -style, and contains double negation ( na nairātmyam ) in the thesis. However, it is perhaps Dharmakīrti who first transformed it into a normal style ( (...) sātmakam ). He is well aware of the law of excluded middle, and insisits that the negation is paryudāsa . On the Nyāya side, Uddyotakara at least seems to be unaware of the law of the logical equivalence of contraposition concerning pervasion ( vyāpti ). After Uddyotakara, however, Vyoman (Vyomaśiva), Bhāsarvajña and Vācaspatimiśra, all seem to be well aware of it. Dharmakīrti, in his conter-argument against the proof of ātman , discusses the negative expressions ‘‘ nairātmya ” and ‘‘ a-nairātmya ” Dharmakīrti here uses two logical arguments skillfully and tactically. As a critic of both the authenticity of the Veda and the existence of ātman , he insists on the theory of dichotomy and the equivalence of anvaya and vyatireka , whereas as an apologist he denies the application of these theories to the relation between the existence of ātman and the concept of nairātmya , because for him as a Buddhist the latter is not a negative but essentially positive state of affairs. (shrink)

We show that in elementary analysis (EL) the contrapositive of countable choice is equivalent to double negation elimination for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma_{2}^{0}}$$\end{document}-formulas. By also proving a recursive adaptation of this equivalence in Heyting arithmetic (HA), we give an instance of the conservativity of EL over HA with respect to recursive functions and predicates. As a complement, we prove in HA enriched with the (extended) Church thesis that every decidable predicate is recursive.

The logic BKc1 is the basic constructive logic for weak consistency in the ternary relational semantics without a set of designated points. In this paper, a number of extensions of B Kc1 defined with a propositional falsity constant are defined. It is also proved that weak consistency is not equivalent to negation-consistency or absolute consistency in any logic included in positive contractionless intermediate logic LC plus the constructive negation of BKc1 and the contraposition axioms.

We study the uniform computational content of different versions of the Baire category theorem in the Weihrauch lattice. The Baire category theorem can be seen as a pigeonhole principle that states that a complete metric space cannot be decomposed into countably many nowhere dense pieces. The Baire category theorem is an illuminating example of a theorem that can be used to demonstrate that one classical theorem can have several different computational interpretations. For one, we distinguish two different logical versions (...) of the theorem, where one can be seen as the contrapositive form of the other one. The first version aims to find an uncovered point in the space, given a sequence of nowhere dense closed sets. The second version aims to find the index of a closed set that is somewhere dense, given a sequence of closed sets that cover the space. Even though the two statements behind these versions are equivalent to each other in classical logic, they are not equivalent in intuitionistic logic, and likewise, they exhibit different computational behavior in the Weihrauch lattice. Besides this logical distinction, we also consider different ways in which the sequence of closed sets is “given.” Essentially, we can distinguish between positive and negative information on closed sets. We discuss all four resulting versions of the Baire category theorem. Somewhat surprisingly, it turns out that the difference in providing the input information can also be expressed with the jump operation. Finally, we also relate the Baire category theorem to notions of genericity and computably comeager sets. (shrink)

We introduce a new framework for classifying logics on finite structures and studying their expressive power. This framework is based on the concept of almost everywhere equivalence of logics, that is to say, two logics having the same expressive power on a class of asymptotic measure 1. More precisely, if L, L ′ are two logics and μ is an asymptotic measure on finite structures, then $\scr{L}\equiv _{\text{a.e.}}\scr{L}^{\prime}(\mu)$ means that there is a class C of finite structures with μ (...) (C)=1 and such that L and L ′ define the same queries on C. We carry out a systematic investigation of $\equiv _{\text{a.e.}}$ with respect to the uniform measure and analyze the $\equiv _{\text{a.e.}}$ -equivalence classes of several logics that have been studied extensively in finite model theory. Moreover, we explore connections with descriptive complexity theory and examine the status of certain classical results of model theory in the context of this new framework. (shrink)

Two logics L1 and L2 are negatively equivalent if for any set of formulas X and any negated formula ¬, ¬ can be deduced from the set of hypotheses X in L1 if and only if it can be done in L2. This article is devoted to the investigation of negative equivalence relation in the class of extensions of minimal logic.

In the context of a weak formal theory called Basic Intuitionistic Mathematics $$\textsf{BIM}$$ BIM, we study Brouwer’s Fan Theorem and a strong negation of the Fan Theorem, Kleene’s Alternative (to the Fan Theorem). We prove that the Fan Theorem is equivalent to contrapositions of a number of intuitionistically accepted axioms of countable choice and that Kleene’s Alternative is equivalent to strong negations of these statements. We discuss finite and infinite games and introduce a constructively useful notion of determinacy. We prove (...) that the Fan Theorem is equivalent to the Intuitionistic Determinacy Theorem. This theorem says that every subset of Cantor space $$2^\omega $$ 2 ω is, in our constructively meaningful sense, determinate. Kleene’s Alternative is equivalent to a strong negation of a special case of this theorem. We also consider a uniform intermediate value theorem and a compactness theorem for classical propositional logic. The Fan Theorem is equivalent to each of these theorems and Kleene’s Alternative is equivalent to strong negations of them. We end with a note on ‘stronger’ Fan Theorems. The paper is a sequel to Veldman (Arch Math Logic 53:621–693, 2014). (shrink)

We study the relationship between least and inflationary fixed-point logic. In 1986, Gurevich and Shelah proved that in the restriction to finite structures, the two logics have the same expressive power. On infinite structures however, the question whether there is a formula in IFP not equivalent to any LFP-formula was left open.In this paper, we answer the question negatively, i.e. we show that the two logics are equally expressive on arbitrary structures. We give a syntactic translation of IFP-formulae to LFP-formulae (...) such that the two formulae are equivalent on all structures.As a consequence of the proof we establish a close correspondence between the LFP-alternation hierarchy and the IFP-nesting depth hierarchy. We also show that the alternation hierarchy for IFP collapses to the first level, i.e. the complement of any inflationary fixed point is itself an inflationary fixed point. (shrink)

Chs. 8 and 9 convert the two basic forms of slingshot argument—one used by Alonzo Church, W. V. Quine, and Donald Davidson, the other by Kurt Gödel—into knock‐down deductive proofs that Donald Davidson's and Richard Rorty's cases against facts and the representation of facts are unfounded, and their slingshot arguments for discrediting the existence of facts unsatisfactory. The proofs are agnostic on key semantic issues; in particular, they assume no particular account of reference and do not even assume that sentences (...) have references. Using this procedure, Ch. 8 shows that cleaned‐up versions of the slingshot arguments used by Davidson, Church, and Quine demonstrate theses weaker than those their authors were seeking—the impossibility of facts and non‐truth‐functional connectives. This is primarily because the arguments depend upon logical equivalences and theories of definite descriptions that must satisfy certain semantic conditions if the aforementioned logical equivalences are to obtain. The four sections of the chapter are: Introductory Remarks; The Quinean Strategy; An Incomplete Connective Proof; and A Complete Connective Proof. (shrink)

In this study, an extended paradefinite logic with classical negation (EPLC), which has the connectives of conflation, paraconsistent negation, classical negation, and classical implication, is introduced as a Gentzen-type sequent calculus. The logic EPLC is regarded as a modification of Arieli, Avron, and Zamansky’s ideal four-valued paradefinite logic (4CC) and as an extension of De and Omori’s extended Belnap–Dunn logic with classical negation (BD+) and Avron’s self-extensional four-valued paradefinite logic (SE4). The completeness, cut-elimination, and decidability theorems for EPLC are proved (...) and EPLC is shown to be embeddable into classical logic. The strong equivalence substitution property and the admissibilities of the rules of negative symmetry, contraposition, and involution are shown for EPLC. Some alternative simple Gentzen-type sequent calculi, which are theorem-equivalent to EPLC, are obtained via these characteristic properties. (shrink)

This mathematics textbook covers the fundamental ideas used in writing proofs. Proof techniques covered include direct proofs, proofs by contrapositive, proofs by contradiction, proofs in set theory, proofs of existentially or universally quantified predicates, proofs by cases, and mathematical induction. Inductive and deductive reasoning are explored. A straightforward approach is taken throughout. Plenty of examples are included and lots of exercises are provided after each brief exposition on the topics at hand. The text begins with a study of symbolic (...) logic, deductive reasoning, and quantifiers. Inductive reasoning and making conjectures are examined next, and once there are some statements to prove, techniques for proving conditional statements, disjunctions, biconditional statements, and quantified predicates are investigated. Terminology and proof techniques in set theory follow with discussions of the pick-a-point method and the algebra of sets. Cartesian products, equivalence relations, orders, and functions are all incorporated. Particular attention is given to injectivity, surjectivity, and cardinality. The text includes an introduction to topology and abstract algebra, with a comparison of topological properties to algebraic properties. This book can be used by itself for an introduction to proofs course or as a supplemental text for students in proof-based mathematics classes. The contents have been rigorously reviewed and tested by instructors and students in classroom settings. (shrink)

In this paper a principle of substitutivity of logical equivalents salve veritate and a version of Leibniz’s law are formulated and each is shown to cause problems when combined with naive truth theories.

The first section of the paper establishes the minimal properties of so-called consequential implication and shows that they are satisfied by at least two different operators of decreasing strength and \). Only the former has been analyzed in recent literature, so the paper focuses essentially on the latter. Both operators may be axiomatized in systems which are shown to be translatable into standard systems of normal modal logic. The central result of the paper is that the minimal consequential system for (...) \, CI\, is definitionally equivalent to the deontic system KD and is intertranslatable with the minimal consequential system for \, CI. The main drawback ot the weaker operator \ is that it lacks unrestricted contraposition, but the final section of the paper argues that \ has some properties which make it a valuable alternative to \, turning out especially plausible as a basis for the definition of operators representing synthetic conditionals. (shrink)

Some of the concerns which motivate attempts to provide a philosophical reduction of nomological necessity are briefly introduced in I. In II, Hempel's treatment of the paradoxes is contrasted with a position which holds that nomological necessity is a pragmatic dimension of laws of nature, and that this pragmatic dimension is of such a type that it prevents laws of nature from contraposing. Such a position is, however, untenable unless (i) the sense of 'pragmatics' at issue is specified, and the (...) possibility of pragmatic differences resulting in differences in confirmation is defended, and (ii) a relevant pragmatic difference between contrapositives is indicated. III attempts to satisfy condition (i) by developing a new sense of pure pragmatics and argues that some remarks by Goodman and Scheffler together with work on the logic of explanation by Dr. Rescher and myself suggest that nomological contrapositives are not pragmatically equivalent (i.e. substitutable salva veritate in the pure pragmatics of an ideal scientific language). If such is the case, condition (ii) is also satisfied. (shrink)

The properties, theoretical magnitudes, and natural kinds which science seeks to characterize, and not the sense or meanings which parts of speech may possess, are the subject of this paper. Many philosophers (e.g., Putnam [1971] and Achinstein [1974]) have agreed that two predicates of different meaning may pick out the same property, but they usually hold that that logically equivalent predicates must pick out the same properties. I propose to deny this thesis. My argument is by way of an example (...) and by appeal to a principle. The principle connects propertyhood with causal efficacy. The example situation I will describe in what follows is intended to show that the property of being a closed straight-sided figure having three sides is not the same property as that of being a closed straight-sided figure having three angles (a triangle). (shrink)

Several investigations in probability theory and the theory of expert systems show that it is important to search for some reasonable generalizations of fuzzy logics (e.g. Łukasiewicz, Gödel or product logic) having a non-associative conjunction. In the present paper, we offer a non-associative fuzzy logic L CBA having as an equivalent algebraic semantics lattices with section antitone involutions satisfying the contraposition law, so-called commutative basic algebras. The class (variety) CBA of commutative basic algebras was intensively studied in several recent papers (...) and includes the class of MV-algebras. We show that the logic L CBA is very close to the Łukasiewicz one, both having the same finite models, and can be understood as its non-associative generalization. (shrink)

In a recent issue of this Bulletin, S. Meskhi cites 7 additional conditions for Heyting algebras with involution and linearly ordered matrix [10, p. 11]. In [2], R. Cignoli indicates 3 additional conditions for P-algebras [5] with normal involution [9]. The equivalence of these conditions is shown.

A category theoretic generalization of the theory of algebraizable deductive systems of Blok and Pigozzi is developed. The theory of institutions of Goguen and Burstall is used to provide the underlying framework which replaces and generalizes the universal algebraic framework based on the notion of a deductive system. The notion of a term -institution is introduced first. Then the notions of quasi-equivalence, strong quasi-equivalence and deductive equivalence are defined for -institutions. Necessary and sufficient conditions are given for (...) the quasi-equivalence and the deductive equivalence of two term -institutions, based on the relationship between their categories of theories. The results carry over without any complications to institutions, via their associated -institutions. The -institution associated with a deductive system and the institution of equational logic are examined in some detail and serve to illustrate the general theory. (shrink)

The equivalence of leaf languages of tree adjoining grammars and monadic linear context-free grammars was shown about a decade ago. This paper presents a proof of the strong equivalence of these grammar formalisms. Non-strict tree adjoining grammars and monadic linear context-free grammars define the same class of tree languages. We also present a logical characterisation of this tree language class showing that a tree language is a member of this class iff it is the two-dimensional yield of (...) an MSO-definable three-dimensional tree language. (shrink)

In this paper I consider whether there is a measure of coherence that could be rightly claimed to generalize the notion of logical equivalence. I show that Fitelson’s (2003) proposal to that effect encounters some serious difficulties. Furthermore, there is reason to believe that no mutual-support measure could ever be suitable for the formalization of coherence as generalized logical equivalence. Instead, it appears that the only plausible candidate for such a measure is one of relative overlap. (...) The measure I propose in this paper is quite similar to Olsson’s (2002) proposal but differs from it by not being susceptible to the type of counterexample that Bovens and Hartmann (2003) have devised against it. (shrink)

This paper corrects a mistake I saw students make but I have yet to see in print. The mistake is thinking that logically equivalent propositions have the same counterexamples—always. Of course, it is often the case that logically equivalent propositions have the same counterexamples: “every number that is prime is odd” has the same counterexamples as “every number that is not odd is not prime”. The set of numbers satisfying “prime but not odd” is the same as the set of (...) numbers satisfying “not odd but not not-prime”. The mistake is thinking that every two logically-equivalent false universal propositions have the same counterexamples. Only false universal propositions have counterexamples. A counterexample for “every two logically-equivalent false universal propositions have the same counterexamples” is two logically-equivalent false universal propositions not having the same counterexamples. The following counterexample arose naturally in my sophomore deductive logic course in a discussion of inner and outer converses. “Every even number precedes every odd number” is counterexemplified only by even numbers, whereas its equivalent “Every odd number is preceded by every even number” is counterexemplified only by odd numbers. Please let me know if you see this mistake in print. Also let me know if you have seen these points discussed before. I learned them in my own course: talk about learning by teaching! (shrink)

Say that a property is topological if and only if it is invariant under homeomorphism. Homeomorphism would be a successful criterion for the equivalence of logical systems only if every logically significant property of every logical system were topological. Alas, homeomorphisms are sometimes insensitive to distinctions that logicians value: properties such as functional completeness are not topological. So logics are not just devices for exploring closure topologies. One still wonders, though, how much of logic is topological. This (...) essay examines some logically significant properties that are topological (or are topological in some important class). In the process, we learn something about the conditions under which the meaning of a connective can be "given by the connective's role in inference.". (shrink)

The aim of this work is to develop a declarative semantics for N-Prolog with negation as failure. N-Prolog is an extension of Prolog proposed by Gabbay and Reyle, which allows for occurrences of nested implications in both goals and clauses. Our starting point is an operational semantics of the language defined by means of top-down derivation trees. Negation as finite failure can be naturally introduced in this context. A goal-G may be inferred from a database if every top-down derivation of (...) G from the database finitely fails, i.e., contains a failure node at finite height.Our purpose is to give a logical interpretation of the underlying operational semantics. In the present work we take into consideration only the basic problems of determining such an interpretation, so that our analysis will concentrate on the propositional case. Nevertheless we give an intuitive account of how to extend our results to a first order language. A full treatment of N-Prolog with quantifiers will be deferred to the second part of this work. (shrink)

Normative systems have been advocated as an effective tool to regulate interaction in multi-agent systems. The use of deontic operators and the ability to represent defeasible information are known to be two fundamental ingredients to represent and reason about normative systems. In this paper, after introducing a framework that combines standard deontic logic and non-monotonic logic programming, deontic logic programs (DLP), we tackle the fundamental problem of equivalence between normative systems using a deontic extension of David Pearce’s Equilibrium Logic (...) and its monotonic basis, the logic of Here-and-There. We also show how deontic logic programs can be used to represent and reason about normative systems, and establish a strong connection with input-output logic. (shrink)

Journal of Mathematical Logic, Ahead of Print. Asperó and Schindler have completely solved the Axiom [math] vs. [math] problem. They have proved that if [math] holds then Axiom [math] holds, with no additional assumptions. The key question now concerns the relationship between [math] and Axiom [math]. This is because the foundational issues raised by the problem of Axiom [math] vs. [math] arguably persist in the problem of Axiom [math] vs. [math]. The first of our two main theorems is that Axiom (...) [math] is equivalent to Axiom [math], and as a corollary we show that Axiom [math] fails in all the known models of [math]. This suggests that [math] actually refutes Axiom [math]. Our second main theorem is that the [math] Conjecture holds assuming [math]. This is the strongest partial result known on this conjecture which is one of the central open problems of [math]-theory and [math]-logic. These results identify a fundamental asymmetry between the Continuum Hypothesis and any axiom which is both [math]-expressible and which implies [math], on the basis of generic absoluteness for the simplest of the nontrivial sentences of Third-Order Number Theory. These are the [math]-sentences with no parameters. Such sentences are those which simply assert the existence of a set [math] for which some property involving only quantification over [math] holds. (shrink)

We define classes Φnof formulae of first-order arithmetic with the following properties:(i) Everyφϵ Φnis classically equivalent to a Πn-formula (n≠ 1, Φ1:= Σ1).(ii)(iii)IΠnandiΦn(i.e., Heyting arithmetic with induction schema restricted to Φn-formulae) prove the same Π2-formulae.We further generalize a result by Visser and Wehmeier. namely that prenex induction within intuitionistic arithmetic is rather weak: After closing Φnboth under existential and universal quantification (we call these classes Θn) the corresponding theoriesiΘnstill prove the same Π2-formulae. In a second part we consideriΔ0plus collection-principles. We (...) show that both the provably recursive functions and the provably total functions ofare polynomially bounded. Furthermore we show that the contrapositive of the collection-schema gives rise to instances of the law of excluded middle and hence. (shrink)

Equivalences and translations between consequence relations abound in logic. The notion of equivalence can be defined syntactically, in terms of translations of formulas, and order-theoretically, in terms of the associated lattices of theories. W. Blok and D. Pigozzi proved in [4] that the two definitions coincide in the case of an algebraizable sentential deductive system. A refined treatment of this equivalence was provided by W. Blok and B. Jónsson in [3]. Other authors have extended this result to the (...) cases of k-deductive systems and of consequence relations on associative, commutative, multiple conclusion sequents. Our main result subsumes all existing results in the literature and reveals their common character. The proofs are of order-theoretic and categorical nature. (shrink)

This article presents a weak system of intuitionistic second-order arithmetic, WKV, a subsystem of the one in S.C. Kleene, R.E. Vesley [The Foundations of Intuitionistic Mathematics: Especially in Relation to Recursive Functions, North-Holland Publishing Company, Amsterdam, 1965]. It is then shown that some statements of real analysis, like a version of the Heine–Borel Theorem, and some statements of logic, e.g. compactness of classical proposition calculus, are equivalent to the Fan Theorem in this system.

We present statements equivalent to some fragments of the principle of non-deterministic inductive definitions (NID) by van den Berg (2013), working in a weak subsystem of constructive set theory CZF. We show that several statements in constructive topology which were initially proved using NID are equivalent to the elementary and finitary NIDs. We also show that the finitary NID is equivalent to its binary fragment and that the elementary NID is equivalent to a variant of NID based on the notion (...) of biclosed subset. Our result suggests that proving these statements in constructive topology requires genuine extensions of CZF with the elementary or finitary NID. (shrink)

On the one hand, Pavel Tichý has shown in his Transparent Intensional Logic (TIL) that the best way of explicating meaning of the expressions of a natural language consists in identification of meanings with abstract procedures. TIL explicates objective abstract procedures as so-called constructions. Constructions that do not contain free variables and are in a well-defined sense ´normalized´ are called concepts in TIL. On the second hand, Kolmogorov in (Mathematische Zeitschrift 35: 58–65, 1932) formulated a theory of problems, using NL (...) expressions. He explicitly avoids presenting a definition of problems. In the present paper an attempt at such a definition (explication)—independent of but in harmony with Medvedev´s explication—is given together with the claim that every concept defines a problem. The paper treats just mathematical concepts, and so mathematical problems, and tries to show that this view makes it possible to take into account some links between conceptual systems and the ways how to replace a noneffective formulation of a problem by an effective one. To show this in concreto a wellknown Kleene’s idea from his (Introduction to metamathematics. D. van Nostrand, New York, 1952) is exemplified and explained in terms of conceptual systems so that a threatening inconsistence is avoided. (shrink)

In La Téntation de Saint Antoine Gustave Flaubert dramatizes a philosophical exchange about the nature of divine providence and the efficacy of petitionary prayer. The Devil and Antony consider the question of whether God can be called upon for relief from suffering. The Saint assumes as popular religion teaches that it is possible to ask for God's help in emergency situations, while the Devil poses a dilemma to challenge Antony's faith. The Devil seeks to expose contradictions in some of the (...) beliefs Antony holds about God's infinite perfection. The Devil's argument purports to prove that God is not a person, and that for this reason God is inaccessible to human interaction. The Devil's dilemma is supposed to be this: If God as an infinitely perfect being created the universe, then divine providence is not needed [does not exist]. If divine providence is needed [exists], then the universe is defective [not the creation of God as an infinitely perfect being].Although these look at first to be the opposite poles of an excluded middle, propositions and are mere contrapositives. Since the Devil's propositions and are logically equivalent, the Devil can only proceed to the conclusion that God does not exist or that divine providence is not needed or does not exist paradoxically by assuming that God exists or that divine providence is needed or exists. Yet if divine providence is needed or exists, then God exists as its divine source. If the Devil is supposed to succeed by logic, his dilemma as Flaubert portrays it is powerless to prove that the only reasonable religious attitude is an impassionate metaphysical acknowledgement of the existence of an impersonal infinitely perfect Substance, which is absolute unchanging unmoveable Being. (shrink)

We characterize elementary equivalences and inclusions between von Neumann regular real closed rings in terms of their boolean algebras of idempotents, and prove that their theories are always decidable. We then show that, under some hypotheses, the map sending an L-structure R to the L-structure of definable functions from R n to R preserves elementary inclusions and equivalences and gives a structure with a decidable theory whenever R is decidable. We briefly consider structures of definable functions satisfying an extra condition (...) such as continuity. (shrink)

A number of theories have been developed to characterize ALogTime (or uniform NC 1, or just NC 1), the class of languages accepted by alternating logtime Turing machines, in the same way that Buss’s theory ${{\bf S}^{1}_{2}}$ characterizes polytime functions. Among these, ALV′ (by Clote) is particularly interesting because it is developed based on Barrington’s theorem that the word problem for the permutation group S 5 is complete for ALogTime. On the other hand, ALV (by Clote), T 0 NC 0 (...) (by Clote and Takeuti) as well as Arai’s theory ${{\bf AID}+\Sigma_0^B{-}{\bf CA}}$ and its two-sorted version VNC 1 (by Cook and Morioka) are based on the circuit characterization of ALogTime. While the last three theories have been known to be equivalent, their relationship to ALV′ has been an open problem. Here we show that ALV′ is indeed equivalent to the other theories. (shrink)

Two first-order logic theories are definitionally equivalent if and only if there is a bijection between their model classes that preserves isomorphisms and ultraproducts (Theorem 2). This is a variant of a prior theorem of van Benthem and Pearce. In Example 2, uncountably many pairs of definitionally inequivalent theories are given such that their model categories are concretely isomorphic via bijections that preserve ultraproducts in the model categories up to isomorphism. Based on these results, we settle several conjectures of Barrett, (...) Glymour and Halvorson. (shrink)

We characterize, in terms of determinacy, the existence of 0 ♯♯ as well as the existence of each of the following: 0 ♯♯♯ , 0 ♯♯♯♯ ,0 ♯♯♯♯♯ , .... For k ∈ ω, we define two classes of sets, (k * Σ 0 1 ) * and (k * Σ 0 1 ) * + , which lie strictly between $\bigcup_{\beta and Δ(ω 2 -Π 1 1 ). We also define 0 1♯ as 0 ♯ and in general, 0 (...) (k + 1)♯ as (0 k♯) ♯ . We then show that the existence of 0 (k + 1)♯ is equivalent to the determinacy of ((k + 1) * Σ 0 1 ) * as well as the determinacy of (k * Σ 0 1 ) * +. (shrink)

For Tarski logics, there are simple criteria that enable one to conclude that two premise sets are equivalent. We shall show that the very same criteria hold for adaptive logics, which is a major advantage in comparison to other approaches to defeasible reasoning forms. A related property of Tarski logics is that the extensions of equivalent premise sets with the same set of formulas are equivalent premise sets. This does not hold for adaptive logics. However a very similar criterion does. (...) We also shall show that every monotonic logic weaker than an adaptive logic is weaker than the lower limit logic of the adaptive logic or identical to it. This highlights the role of the lower limit for settling the adaptive equivalence of extensions of equivalent premise sets. (shrink)

Relevant logic is a proper subset of classical logic. It does not include among its theorems any ofpositive paradox A (B A).

A generalized version of Martin's axiom, called BACH, is shown to be equivalent to one of its combinatorial consequences, a generalization of P(c).

Given a countable transitive model of set theory and a partial order contained in it, there is a natural countable Borel equivalence relation on generic filters over the model; two are equivalent if they yield the same generic extension. We examine the complexity of this equivalence relation for various partial orders, focusing on Cohen and random forcing. We prove, among other results, that the former is an increasing union of countably many hyperfinite Borel equivalence relations, and hence (...) is amenable, while the latter is neither amenable nor treeable. (shrink)

In [2], Bar-Hillel, Gaifman, and Shamir prove that the simple phrase structure grammars dened by Chomsky are equivalent in a cer- tain sense to Bar-Hillel's bidirectional categorial grammars . On the other hand, Cohen [3] proves the equivalence of the latter ones to what he calls free categorial grammars . They are closely related to Lambek's syntactic calculus which is, in turn, based on the idea due to Ajdukiewicz [1]. For some reasons, Cohen's proof seems to be at least (...) in- complete. Here, I give a short outline of the direct proof of the equivalence between SF G's and F CG's. (shrink)

In a modal system of arithmetic, a theory S has the modal disjunction property if whenever $S \vdash \square\varphi \vee \square\psi$ , either $S \vdash \square\varphi$ or $S \vdash \square\psi. S$ has the modal numerical existence property if whenever $S \vdash \exists x\square\varphi(x)$ , there is some natural number n such that $S \vdash \square\varphi(\mathbf{n})$ . Under certain broadly applicable assumptions, these two properties are equivalent.

Several extensions of Gödel's system TT with new forms of recursion have been designed for the purpose of giving a computational interpretation to classical analysis. One can organise many of these extensions into two groups: those based on bar recursion , which include Spector's original bar recursion, modified bar recursion and the more recent products of selections functions, or those based on open recursion which in particular include the symmetric Berardi–Bezem–Coquand functional. We relate these two groups by showing that both (...) open recursion and the BBC functional are primitive recursively equivalent to a variant of modified bar recursion. Our results, in combination with existing research, essentially complete the classification up to primitive recursive equivalence of those extensions of system TT used to give a direct computational interpretation to choice principles. (shrink)