First-order definability on finite structures
type: Item
instance of: scholarly article
title: First-order definability on finite structures
zbMATH Open document ID: 0688.03018
DOI: 10.1016/0168-0072(89)90036-5
author: Miklós Ajtai
published in: Annals of Pure and Applied Logic
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03C40
Mathematics Subject Classification ID: 03C13
zbMATH DE Number: 4127181
zbMATH Keywords: existential hierarchy
zbMATH Keywords: connectedness
zbMATH Keywords: undefinability
zbMATH Keywords: graph-theoretic property
zbMATH Keywords: finite structures
reviewed by: Daniele Mundici
MaRDI profile type: Publication
full work available at URL: 0168-0072(89)90036-5
OpenAlex ID: W2054510469
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: A spectrum hierarchy
description: scientific article; zbMATH DE number 4127181