Switch to: Citations

Add references

You must login to add references.
  1. Undecidable Extensions of Skolem Arithmetic.Alexis Bes & Denis Richard - 1998 - Journal of Symbolic Logic 63 (2):379-401.
    Let $<_{P_2}$ be the restriction of usual order relation to integers which are primes or squares of primes, and let $\bot$ denote the coprimeness predicate. The elementary theory of $\langle\mathbb{N};\bot,<_{P_2}\rangle$, is undecidable. Now denote by $<_\Pi$ the restriction of order to primary numbers. All arithmetical relations restricted to primary numbers are definable in the structure $\langle\mathbb{N};\bot,<_\Pi\rangle$. Furthermore, the structures $\langle\mathbb{N};\mid,<_\Pi\rangle, \langle\mathbb{N};=,x,<_\Pi\rangle$ and $\langle\mathbb{N};=,+,x\rangle$ are interdefinable.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Undecidable extensions of Skolem arithmetic.Alexis Bès & Denis Richard - 1998 - Journal of Symbolic Logic 63 (2):379-401.
    Let $ be the restriction of usual order relation to integers which are primes or squares of primes, and let ⊥ denote the coprimeness predicate. The elementary theory of $\langle\mathbb{N};\bot, , is undecidable. Now denote by $ the restriction of order to primary numbers. All arithmetical relations restricted to primary numbers are definable in the structure $\langle\mathbb{N};\bot, . Furthermore, the structures $\langle\mathbb{N};\mid, and $\langle\mathbb{N};=,+,x\rangle$ are interdefinable.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Theory of recursive functions and effective computability.Hartley Rogers - 1987 - Cambridge: MIT Press.
    Download  
     
    Export citation  
     
    Bookmark   482 citations  
  • Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
    Download  
     
    Export citation  
     
    Bookmark   594 citations  
  • Definability and decision problems in arithmetic.Julia Robinson - 1949 - Journal of Symbolic Logic 14 (2):98-114.
    In this paper, we are concerned with the arithmetical definability of certain notions of integers and rationals in terms of other notions. The results derived will be applied to obtain a negative solution of corresponding decision problems.In Section 1, we show that addition of positive integers can be defined arithmetically in terms of multiplication and the unary operation of successorS(whereSa=a+ 1). Also, it is shown that both addition and multiplication can be defined arithmetically in terms of successor and the relation (...)
    Download  
     
    Export citation  
     
    Bookmark   43 citations  
  • Decidability and essential undecidability.Hilary Putnam - 1957 - Journal of Symbolic Logic 22 (1):39-54.
    Download  
     
    Export citation  
     
    Bookmark   10 citations  
  • Presburger arithmetic with unary predicates is Π11 complete.Joseph Y. Halpern - 1991 - Journal of Symbolic Logic 56 (2):637 - 642.
    We give a simple proof characterizing the complexity of Presburger arithmetic augmented with additional predicates. We show that Presburger arithmetic with additional predicates is Π 1 1 complete. Adding one unary predicate is enough to get Π 1 1 hardness, while adding more predicates (of any arity) does not make the complexity any worse.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Subsystems of Second Order Arithmetic.Stephen George Simpson - 1999 - Springer Verlag.
    Stephen George Simpson. with definition 1.2.3 and the discussion following it. For example, taking 90(n) to be the formula n §E Y, we have an instance of comprehension, VYEIXVn(n€X<—>n¢Y), asserting that for any given set Y there exists a ...
    Download  
     
    Export citation  
     
    Bookmark   131 citations  
  • Subsystems of Second Order Arithmetic.Stephen G. Simpson - 1999 - Studia Logica 77 (1):129-129.
    Download  
     
    Export citation  
     
    Bookmark   234 citations