Switch to: References

Add citations

You must login to add citations.
  1. Arithmetic of divisibility in finite models.A. E. Wasilewska & M. Mostowski - 2004 - Mathematical Logic Quarterly 50 (2):169.
    We prove that the finite-model version of arithmetic with the divisibility relation is undecidable . Additionally we prove FM-representability theorem for this class of finite models. This means that a relation R on natural numbers can be described correctly on each input on almost all finite divisibility models if and only if R is of degree ≤0′. We obtain these results by interpreting addition and multiplication on initial segments of finite models with divisibility only.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Theories of arithmetics in finite models.Michał Krynicki & Konrad Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.
    We investigate theories of initial segments of the standard models for arithmetics. It is easy to see that if the ordering relation is definable in the standard model then the decidability results can be transferred from the infinite model into the finite models. On the contrary we show that the Σ₂—theory of multiplication is undecidable in finite models. We show that this result is optimal by proving that the Σ₁—theory of multiplication and order is decidable in finite models as well (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations