Switch to: References

Add citations

You must login to add citations.
  1. Arithmetical definability over finite structures.Troy Lee - 2003 - Mathematical Logic Quarterly 49 (4):385.
    Arithmetical definability has been extensively studied over the natural numbers. In this paper, we take up the study of arithmetical definability over finite structures, motivated by the correspondence between uniform AC0 and FO. We prove finite analogs of three classic results in arithmetical definability, namely that < and TIMES can first-order define PLUS, that < and DIVIDES can first-order define TIMES, and that < and COPRIME can first-order define TIMES. The first result sharpens the equivalence FO =FO to FO = (...)
    Direct download (2 more)  
     
    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 (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Theories of generalized Pascal triangles.Ivan Korec - 1997 - Annals of Pure and Applied Logic 89 (1):45-52.
  • Friedman, Sy D. and VeliCkovit, B., Al-Definability.I. Hodkinson, R. Kaye, I. Korec, F. Maurin, H. Mildenberger & F. O. Wagner - 1997 - Annals of Pure and Applied Logic 89 (1):277.