Mostrando recursos 1 - 20 de 20

  1. Actualism, Serious Actualism, and Quantified Modal Logic

    Hanson, William H.
    This article studies seriously actualistic quantified modal logics. A key component of the language is an abstraction operator by means of which predicates can be created out of complex formulas. This facilitates proof of a uniform substitution theorem: if a sentence is logically true, then any sentence that results from substituting a (perhaps complex) predicate abstract for each occurrence of a simple predicate abstract is also logically true. This solves a problem identified by Kripke early in the modern semantic study of quantified modal logic. A tableau proof system is presented and proved sound and complete with respect to logical...

  2. Ostrowski Numeration Systems, Addition, and Finite Automata

    Hieronymi, Philipp; Terry Jr., Alonza
    We present an elementary three-pass algorithm for computing addition in Ostrowski numeration systems. When $a$ is quadratic, addition in the Ostrowski numeration system based on $a$ is recognizable by a finite automaton. We deduce that a subset of $X\subseteq\mathbb{N}^{n}$ is definable in $(\mathbb{N},+,V_{a})$ , where $V_{a}$ is the function that maps a natural number $x$ to the smallest denominator of a convergent of $a$ that appears in the Ostrowski representation based on $a$ of $x$ with a nonzero coefficient if and only if the set of Ostrowski representations of elements of $X$ is recognizable by a finite automaton. The decidability...

  3. Nonreduction of Relations in the Gromov Space to Polish Actions

    Álvarez López, Jesús A.; Candel, Alberto
    We show that in the Gromov space of isometry classes of pointed proper metric spaces, the equivalence relations defined by existence of coarse quasi-isometries or being at finite Gromov–Hausdorff distance cannot be reduced to the equivalence relation defined by any Polish action.

  4. A Problem in Pythagorean Arithmetic

    Pambuccian, Victor
    Problem 2 at the 56th International Mathematical Olympiad (2015) asks for all triples $(a,b,c)$ of positive integers for which $ab-c$ , $bc-a$ , and $ca-b$ are all powers of $2$ . We show that this problem requires only a primitive form of arithmetic, going back to the Pythagoreans, which is the arithmetic of the even and the odd.

  5. Two More Characterizations of K-Triviality

    Greenberg, Noam; Miller, Joseph S.; Monin, Benoit; Turetsky, Daniel
    We give two new characterizations of $K$ -triviality. We show that if for all $Y$ such that $\Omega$ is $Y$ -random, $\Omega$ is $(Y\oplusA)$ -random, then $A$ is $K$ -trivial. The other direction was proved by Stephan and Yu, giving us the first titular characterization of $K$ -triviality and answering a question of Yu. We also prove that if $A$ is $K$ -trivial, then for all $Y$ such that $\Omega$ is $Y$ -random, $(Y\oplus A)\equiv_{\textup{LR}}Y$ . This answers a question of Merkle and Yu. The other direction is immediate, so we have the second characterization of $K$ -triviality. ¶ The proof...

  6. Blurring: An Approach to Conflation

    Ripley, David
    I consider the phenomenon of conflation—treating distinct things as one—and develop logical tools for modeling it. These tools involve a purely consequence-theoretic treatment, independent of any proof or model theory, as well as a four-valued valuational treatment.

  7. On Superstable Expansions of Free Abelian Groups

    Palacín, Daniel; Sklinos, Rizos
    We prove that $(\mathbb{Z},+,0)$ has no proper superstable expansions of finite Lascar rank. Nevertheless, this structure equipped with a predicate defining powers of a given natural number is superstable of Lascar rank $\omega$ . Additionally, our methods yield other superstable expansions such as $(\mathbb{Z},+,0)$ equipped with the set of factorial elements.

  8. The Complexity of Primes in Computable Unique Factorization Domains

    Dzhafarov, Damir D.; Mileti, Joseph R.
    In many simple integral domains, such as $\mathbb{Z}$ or $\mathbb{Z}[i]$ , there is a straightforward procedure to determine if an element is prime by simply reducing to a direct check of finitely many potential divisors. Despite the fact that such a naive approach does not immediately translate to integral domains like $\mathbb{Z}[x]$ or the ring of integers in an algebraic number field, there still exist computational procedures that work to determine the prime elements in these cases. In contrast, we will show how to computably extend $\mathbb{Z}$ in such a way that we can control the ordinary integer primes in...

  9. Errata

  10. Invariance and Definability, with and without Equality

    Bonnay, Denis; Engström, Fredrik
    The dual character of invariance under transformations and definability by some operations has been used in classical works by, for example, Galois and Klein. Following Tarski, philosophers of logic have claimed that logical notions themselves could be characterized in terms of invariance. In this article, we generalize a correspondence due to Krasner between invariance under groups of permutations and definability in $\mathscr{L}_{\infty\infty}$ so as to cover the cases (quantifiers, logics without equality) that are of interest in the logicality debates, getting McGee’s theorem about quantifiers invariant under all permutations and definability in pure $\mathscr{L}_{\infty\infty}$ as a particular case. We also...

  11. On the Jumps of the Degrees Below a Recursively Enumerable Degree

    Belanger, David R.; Shore, Richard A.
    We consider the set of jumps below a Turing degree, given by $\mathsf{JB}(\mathbf{a})=\{\mathbf{x}':\mathbf{x}\leq\mathbf{a}\}$ , with a focus on the problem: Which recursively enumerable (r.e.) degrees $\mathbf{a}$ are uniquely determined by $\mathsf{JB}(\mathbf{a})$ ? Initially, this is motivated as a strategy to solve the rigidity problem for the partial order $\mathcal{R}$ of r.e. degrees. Namely, we show that if every high ${}_{2}$ r.e. degree $\mathbf{a}$ is determined by $\mathsf{JB}(\mathbf{a})$ , then $\mathcal{R}$ cannot have a nontrivial automorphism. We then defeat the strategy—at least in the form presented—by constructing pairs $\mathbf{a}_{0}$ , $\mathbf{a}_{1}$ of distinct r.e. degrees such that $\mathsf{JB}(\mathbf{a}_{0})=\mathsf{JB}(\mathbf{a}_{1})$ within any possible...

  12. Negation-Free and Contradiction-Free Proof of the Steiner–Lehmus Theorem

    Pambuccian, Victor
    By rephrasing quantifier-free axioms as rules of derivation in sequent calculus, we show that the generalized Steiner–Lehmus theorem admits a direct proof in classical logic. This provides a partial answer to a question raised by Sylvester in 1852. We also present some comments on possible intuitionistic approaches.

  13. Cardinality and Acceptable Abstraction

    Cook, Roy T.; Linnebo, Øystein
    It is widely thought that the acceptability of an abstraction principle is a feature of the cardinalities at which it is satisfiable. This view is called into question by a recent observation by Richard Heck. We show that a fix proposed by Heck fails but we analyze the interesting idea on which it is based, namely that an acceptable abstraction has to “generate” the objects that it requires. We also correct and complete the classification of proposed criteria for acceptable abstraction.

  14. Classifications of Computable Structures

    Lange, Karen; Miller, Russell; Steiner, Rebecca M.
    Let $\mathcal{K}$ be a family of structures, closed under isomorphism, in a fixed computable language. We consider effective lists of structures from $\mathcal{K}$ such that every structure in $\mathcal{K}$ is isomorphic to exactly one structure on the list. Such a list is called a computable classification of $\mathcal{K}$ , up to isomorphism. Using the technique of Friedberg enumeration, we show that there is a computable classification of the family of computable algebraic fields and that with a $\mathbf{0'}$ -oracle, we can obtain similar classifications of the families of computable equivalence structures and of computable finite-branching trees. However, there is no...

  15. The Logical Strength of Compositional Principles

    Heck Jr., Richard G.
    This paper investigates a set of issues connected with the so-called conservativeness argument against deflationism. Although I do not defend that argument, I think the discussion of it has raised some interesting questions about whether what I call “compositional principles,” such as “a conjunction is true iff its conjuncts are true,” have substantial content or are in some sense logically trivial. The paper presents a series of results that purport to show that the compositional principles for a first-order language, taken together, have substantial logical strength, amounting to a kind of abstract consistency statement.

  16. Ekman’s Paradox

    Schroeder-Heister, Peter; Tranchini, Luca
    Prawitz observed that Russell’s paradox in naive set theory yields a derivation of absurdity whose reduction sequence loops. Building on this observation, and based on numerous examples, Tennant claimed that this looping feature, or more generally, the fact that derivations of absurdity do not normalize, is characteristic of the paradoxes. Striking results by Ekman show that looping reduction sequences are already obtained in minimal propositional logic, when certain reduction steps, which are prima facie plausible, are considered in addition to the standard ones. This shows that the notion of reduction is in need of clarification. Referring to the notion of...

  17. Forking and Dividing in Henson Graphs

    Conant, Gabriel
    For $n\geq3$ , define $T_{n}$ to be the theory of the generic $K_{n}$ -free graph, where $K_{n}$ is the complete graph on $n$ vertices. We prove a graph-theoretic characterization of dividing in $T_{n}$ and use it to show that forking and dividing are the same for complete types. We then give an example of a forking and nondividing formula. Altogether, $T_{n}$ provides a counterexample to a question of Chernikov and Kaplan.

  18. Grades of Discrimination: Indiscernibility, Symmetry, and Relativity

    Button, Tim
    There are several relations which may fall short of genuine identity, but which behave like identity in important respects. Such grades of discrimination have recently been the subject of much philosophical and technical discussion. This paper aims to complete their technical investigation. Grades of indiscernibility are defined in terms of satisfaction of certain first-order formulas. Grades of symmetry are defined in terms of symmetries on a structure. Both of these families of grades of discrimination have been studied in some detail. However, this paper also introduces grades of relativity, defined in terms of relativeness correspondences. This paper explores the relationships...

  19. New Degree Spectra of Abelian Groups

    Melnikov, Alexander G.
    We show that for every computable ordinal of the form $\beta=\delta+2n+1\gt 1$ , where $\delta$ is zero or a limit ordinal and $n\in\omega$ , there exists a torsion-free abelian group having an $X$ -computable copy if and only if $X$ is nonlow $_{\beta}$ .

  20. Prospects for a Naive Theory of Classes

    Field, Hartry; Lederman, Harvey; Øgaard, Tore Fjetland
    The naive theory of properties states that for every condition there is a property instantiated by exactly the things which satisfy that condition. The naive theory of properties is inconsistent in classical logic, but there are many ways to obtain consistent naive theories of properties in nonclassical logics. The naive theory of classes adds to the naive theory of properties an extensionality rule or axiom, which states roughly that if two classes have exactly the same members, they are identical. In this paper we examine the prospects for obtaining a satisfactory naive theory of classes. We start from a result...

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.