• DocumentCode
    2893743
  • Title

    Axiomatizable classes of finite models and definability of linear order

  • Author

    Stolboushkin, Alex

  • Author_Institution
    AI Res. Center, Russian Acad. of Sci., Pereslavl-Zalessky, Russia
  • fYear
    1992
  • fDate
    22-25 Jun 1992
  • Firstpage
    64
  • Lastpage
    70
  • Abstract
    It may happen that a first order formula with two free variables over a signature defines a linear order of some finite structure of the signature. Then, naturally, this finite structure is rigid, i.e. admits the single (trivial) automorphism. Also, the class of all the finite structures such that the formula defines a linear order on any of them, is finitely axiomatizable in the class of all finite structures (of the signature). It is shown that the inverse is not true, i.e. that there exists a finitely axiomatizable class of rigid finite structures, such that no first-order formula defines a linear order on all the structures of the class. To illustrate possible applications of the result in finite model theory, it is shown that Y. Gurevich´s (1984) result that E.W. Beth´s (1953) definability theorem fails for finite models is an immediate corollary
  • Keywords
    computational complexity; formal logic; axiomatizable; definability; finite models; first order formula; linear order; Artificial intelligence; Computer science; Database languages; Ear; Electronic mail; Integrated circuit modeling; Logic; Relational databases; Safety;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Logic in Computer Science, 1992. LICS '92., Proceedings of the Seventh Annual IEEE Symposium on
  • Conference_Location
    Santa Cruz, CA
  • Print_ISBN
    0-8186-2735-2
  • Type

    conf

  • DOI
    10.1109/LICS.1992.185520
  • Filename
    185520