First-order definability on finite structures (Q1263576)

From MaRDI portal
Revision as of 11:54, 20 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
First-order definability on finite structures
scientific article

    Statements

    First-order definability on finite structures (English)
    0 references
    0 references
    1989
    0 references
    The author proves an undefinability result for a simple graph-theoretic property. He then shows that existential first-order formulas have a nontrivial hierarchy on finite structures.
    0 references
    0 references
    existential hierarchy
    0 references
    connectedness
    0 references
    undefinability
    0 references
    graph-theoretic property
    0 references
    finite structures
    0 references
    0 references