Mostrando recursos 1 - 20 de 2.509

  1. Bimodal Logics with a “Weakly Connected” Component without the Finite Model Property

    Kurucz, Agi
    There are two known general results on the finite model property (fmp) of commutators $[L_{0},L_{1}]$ (bimodal logics with commuting and confluent modalities). If $L$ is finitely axiomatizable by modal formulas having universal Horn first-order correspondents, then both $[L,\mathbf{K}]$ and $[L,\mathbf{S5}]$ are determined by classes of frames that admit filtration, and so they have the fmp. On the negative side, if both $L_{0}$ and $L_{1}$ are determined by transitive frames and have frames of arbitrarily large depth, then $[L_{0},L_{1}]$ does not have the fmp. In this paper we show that commutators with a “weakly connected” component often lack the fmp. Our...

  2. On Polynomial-Time Relation Reducibility

    Gao, Su; Ziegler, Caleb
    We study the notion of polynomial-time relation reducibility among computable equivalence relations. We identify some benchmark equivalence relations and show that the reducibility hierarchy has a rich structure. Specifically, we embed the partial order of all polynomial-time computable sets into the polynomial-time relation reducibility hierarchy between two benchmark equivalence relations $\mathsf{E}_{\lambda}$ and $\mathsf{id}$ . In addition, we consider equivalence relations with finitely many nontrivial equivalence classes and those whose equivalence classes are all finite.

  3. Infinite Computations with Random Oracles

    Carl, Merlin; Schlicht, Philipp
    We consider the following problem for various infinite-time machines. If a real is computable relative to a large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeager Borel set, is it already computable? We show that the answer is independent of $\mathrm{ZFC}$ for ordinal Turing machines with and without ordinal parameters and give a positive answer for most other machines. For instance, we consider infinite-time Turing machines, unresetting and resetting infinite-time register machines, and $\alpha$ -Turing machines for countable admissible ordinals $\alpha$ .

  4. Why Intuitionistic Relevant Logic Cannot Be a Core Logic

    Vidal-Rosset, Joseph
    At the end of the 1980s, Tennant invented a logical system that he called “intuitionistic relevant logic” ( $\mathbf{IR}$ , for short). Now he calls this same system “Core logic.” In Section 1, by reference to the rules of natural deduction for $\mathbf{IR}$ , I explain why $\mathbf{IR}$ is a relevant logic in a subtle way. Sections 2, 3, and 4 give three reasons to assert that $\mathbf{IR}$ cannot be a core logic.

  5. Dunn–Priest Quotients of Many-Valued Structures

    Ferguson, Thomas Macaulay
    J. Michael Dunn’s Theorem in 3-Valued Model Theory and Graham Priest’s Collapsing Lemma provide the means of constructing first-order, three-valued structures from classical models while preserving some control over the theories of the ensuing models. The present article introduces a general construction that we call a Dunn–Priest quotient, providing a more general means of constructing models for arbitrary many-valued, first-order logical systems from models of any second system. This technique not only counts Dunn’s and Priest’s techniques as special cases, but also provides a generalized Collapsing Lemma for Priest’s more recent plurivalent semantics in general. We examine when and how...

  6. Normal Numbers and Limit Computable Cantor Series

    Beros, Achilles; Beros, Konstantinos
    Given any oracle, $A$ , we construct a basic sequence $Q$ , computable in the jump of $A$ , such that no $A$ -computable real is $Q$ -distribution-normal. A corollary to this is that there is a $\Delta^{0}_{n+1}$ basic sequence with respect to which no $\Delta^{0}_{n}$ real is distribution-normal. As a special case, there is a limit computable sequence relative to which no computable real is distribution-normal.

  7. Infinitesimal Comparisons: Homomorphisms between Giordano’s Ring and the Hyperreal Field

    Reeder, Patrick
    The primary purpose of this paper is to analyze the relationship between the familiar non-Archimedean field of hyperreals from Abraham Robinson’s nonstandard analysis and Paolo Giordano’s ring extension of the real numbers containing nilpotents. There is an interesting nontrivial homomorphism from the limited hyperreals into the Giordano ring, whereas the only nontrivial homomorphism from the Giordano ring to the hyperreals is the standard part function, namely, the function that maps a value to its real part. We interpret this asymmetry to mean that the nilpotent infinitesimal values of Giordano’s ring are “smaller” than the hyperreal infinitesimals. By viewing things from...

  8. Concrete Fibrations

    Pagnan, Ruggero
    As far as we know, no notion of concrete fibration is available. We provide one such notion in adherence to the foundational attitude that characterizes the adoption of the fibrational perspective in approaching fundamental subjects in category theory and discuss it in connection with the notion of concrete category and the notions of locally small and small fibrations. We also discuss the appropriateness of our notion of concrete fibration for fibrations of small maps, which is relevant to algebraic set theory.

  9. Universal Structures

    Shelah, Saharon
    We deal with the existence of universal members in a given cardinality for several classes. First, we deal with classes of abelian groups, specifically with the existence of universal members in cardinalities which are strong limit singular of countable cofinality or $\lambda=\lambda^{\aleph_{0}}$ . We use versions of being reduced—replacing $\mathbb{Q}$ by a subring (defined by a sequence $\bar{t}$ )—and get quite accurate results for the existence of universals in a cardinal, for embeddings and for pure embeddings. Second, we deal with (variants of) the oak property (from a work of Džamonja and the author), a property of complete first-order theories...

  10. Erratum

  11. Editorial Notice

  12. Computing the Number of Types of Infinite Length

    Boney, Will
    We show that the number of types of sequences of tuples of a fixed length can be calculated from the number of $1$ -types and the length of the sequences. Specifically, if $\kappa \leq \lambda$ , then ¶ \[\sup_{\Vert M\Vert =\lambda}\vert S^{\kappa}(M)\vert =(\sup_{\Vert M\Vert =\lambda}\vert S^{1}(M)\vert )^{\kappa}.\] We show that this holds for any abstract elementary class with $\lambda$ -amalgamation. No such calculation is possible for nonalgebraic types. However, we introduce a subclass of nonalgebraic types for which the same upper bound holds.

  13. Indiscernible Extraction and Morley Sequences

    Vasey, Sebastien
    We present a new proof of the existence of Morley sequences in simple theories. We avoid using the Erdős–Rado theorem and instead use only Ramsey’s theorem and compactness. The proof shows that the basic theory of forking in simple theories can be developed using only principles from “ordinary mathematics,” answering a question of Grossberg, Iovino, and Lessmann, as well as a question of Baldwin.

  14. Ramsey Algebras and Formal Orderly Terms

    Teh, Wen Chean
    Hindman’s theorem says that every finite coloring of the natural numbers has a monochromatic set of finite sums. A Ramsey algebra is a structure that satisfies an analogue of Hindman’s theorem. In this paper, we present the basic notions of Ramsey algebras by using terminology from mathematical logic. We also present some results regarding classification of Ramsey algebras.

  15. Inferentialism and Quantification

    Griffiths, Owen
    Logical inferentialists contend that the meanings of the logical constants are given by their inference rules. Not just any rules are acceptable, however: inferentialists should demand that inference rules must reflect reasoning in natural language. By this standard, I argue, the inferentialist treatment of quantification fails. In particular, the inference rules for the universal quantifier contain free variables, which find no answer in natural language. I consider the most plausible natural language correlate to free variables—the use of variables in the language of informal mathematics—and argue that it lends inferentialism no support.

  16. Strange Structures from Computable Model Theory

    Becker, Howard
    Let $L$ be a countable language, let ${\mathcal{I}}$ be an isomorphism-type of countable $L$ -structures, and let $a\in2^{\omega}$ . We say that ${\mathcal{I}}$ is $a$ -strange if it contains a computable-from- $a$ structure and its Scott rank is exactly $\omega_{1}^{a}$ . For all $a$ , $a$ -strange structures exist. Theorem (AD): If $\mathcal{C}$ is a collection of $\aleph_{1}$ isomorphism-types of countable structures, then for a Turing cone of $a$ ’s, no member of $\mathcal{C}$ is $a$ -strange.

  17. Canjar Filters

    Guzmán, Osvaldo; Hrušák, Michael; Martínez-Celis, Arturo
    If $\mathcal{F}$ is a filter on $\omega$ , we say that $\mathcal{F}$ is Canjar if the corresponding Mathias forcing does not add a dominating real. We prove that any Borel Canjar filter is $F_{\sigma}$ , solving a problem of Hrušák and Minami. We give several examples of Canjar and non-Canjar filters; in particular, we construct a $\mathsf{MAD}$ family such that the corresponding Mathias forcing adds a dominating real. This answers a question of Brendle. Then we prove that in all the “classical” models of $\mathsf{ZFC}$ there are $\mathsf{MAD}$ families whose Mathias forcing does not add a dominating real. We also...

  18. Models as Universes

    Halimi, Brice
    Kreisel’s set-theoretic problem is the problem as to whether any logical consequence of ZFC is ensured to be true. Kreisel and Boolos both proposed an answer, taking truth to mean truth in the background set-theoretic universe. This article advocates another answer, which lies at the level of models of set theory, so that truth remains the usual semantic notion. The article is divided into three parts. It first analyzes Kreisel’s set-theoretic problem and proposes one way in which any model of set theory can be compared to a background universe and shown to contain internal models. It then defines logical...

  19. Locally Finite Reducts of Heyting Algebras and Canonical Formulas

    Bezhanishvili, Guram; Bezhanishvili, Nick
    The variety of Heyting algebras has two well-behaved locally finite reducts, the variety of bounded distributive lattices and the variety of implicative semilattices. The variety of bounded distributive lattices is generated by the $\to$ -free reducts of Heyting algebras, while the variety of implicative semilattices is generated by the $\vee$ -free reducts. Each of these reducts gives rise to canonical formulas that generalize Jankov formulas and provide an axiomatization of all superintuitionistic logics (si-logics for short). ¶ The $\vee$ -free reducts of Heyting algebras give rise to the $(\wedge,\to)$ -canonical formulas that we studied in an earlier work. Here we introduce the...

  20. Disarming a Paradox of Validity

    Field, Hartry
    Any theory of truth must find a way around Curry’s paradox, and there are well-known ways to do so. This paper concerns an apparently analogous paradox, about validity rather than truth, which JC Beall and Julien Murzi (“Two flavors of Curry’s paradox”) call the v-Curry. They argue that there are reasons to want a common solution to it and the standard Curry paradox, and that this rules out the solutions to the latter offered by most “naive truth theorists.” To this end they recommend a radical solution to both paradoxes, involving a substructural logic, in particular, one without structural contraction. ¶ In...

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.