11 found
Order:
  1.  3
    Uniform Density in Lindenbaum Algebras.V. Yu Shavrukov & Albert Visser - 2014 - Notre Dame Journal of Formal Logic 55 (4):569-582.
    In this paper we prove that the preordering $\lesssim $ of provable implication over any recursively enumerable theory $T$ containing a modicum of arithmetic is uniformly dense. This means that we can find a recursive extensional density function $F$ for $\lesssim $. A recursive function $F$ is a density function if it computes, for $A$ and $B$ with $A\lnsim B$, an element $C$ such that $A\lnsim C\lnsim B$. The function is extensional if it preserves $T$-provable equivalence. Secondly, we prove a (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  2. Undecidability in Diagonalizable Algebras.V. Yu Shavrukov - 1997 - Journal of Symbolic Logic 62 (1):79-116.
    If a formal theory T is able to reason about its own syntax, then the diagonalizable algebra of T is defined as its Lindenbaum sentence algebra endowed with a unary operator □ which sends a sentence φ to the sentence □φ asserting the provability of φ in T. We prove that the first order theories of diagonalizable algebras of a wide class of theories are undecidable and establish some related results.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  3.  6
    A Smart Child of Peano's.V. Yu Shavrukov - 1994 - Notre Dame Journal of Formal Logic 35 (2):161-185.
  4.  25
    The∀∃ Theory of Peano Σ1 Sentences.Per Lindström & V. Yu Shavrukov - 2008 - Journal of Mathematical Logic 8 (2):251-280.
    We present a decision procedure for the ∀∃ theory of the lattice of Σ1 sentences of Peano Arithmetic.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  5.  26
    The ∀∃ Theory of Peano Σ1 Sentences.Per Lindström & V. Yu Shavrukov - 2008 - Journal of Mathematical Logic 8 (2):251-280.
    We present a decision procedure for the ∀∃ theory of the lattice of Σ1 sentences of Peano Arithmetic.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  6.  29
    Effectively Inseparable Boolean Algebras in Lattices of Sentences.V. Yu Shavrukov - 2010 - Archive for Mathematical Logic 49 (1):69-89.
    We show the non-arithmeticity of 1st order theories of lattices of Σ n sentences modulo provable equivalence in a formal theory, of diagonalizable algebras of a wider class of arithmetic theories than has been previously known, and of the lattice of degrees of interpretability over PA. The first two results are applications of Nies’ theorem on the non-arithmeticity of the 1st order theory of the lattice of r.e. ideals on any effectively dense r.e. Boolean algebra. The theorem on degrees of (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  7.  14
    A Note on the Diagonalizable Algebras of PA and ZF.V. Yu Shavrukov - 1993 - Annals of Pure and Applied Logic 61 (1-2):161-173.
    We prove that the diagonalizable algebras of PA and ZF are not isomorphic.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  8.  54
    Isomorphisms of Diagonalizable Algebras.V. Yu Shavrukov - 1997 - Theoria 63 (3):210-221.
  9.  13
    Duality, Non-Standard Elements, and Dynamic Properties of R.E. Sets.V. Yu Shavrukov - 2016 - Annals of Pure and Applied Logic 167 (10):939-981.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  10.  20
    The Lindenbaum Fixed Point Algebra is Undecidable.V. Yu Shavrukov - 1991 - Studia Logica 50 (1):143-147.
    We prove that the first order theory of the fixed point algebra corresponding to an r.e. consistent theory containing arithmetic is hereditarily undecidable.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  11.  4
    Corrigendum: The ∀∃ Theory of Peano Σ1 Sentences.V. Yu Shavrukov - 2017 - Journal of Mathematical Logic 17 (1):1792001.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark