On finite rigid structures

DOI10.2307/2275675MaRDI QIDQ4894726zbMATH OpenOpenAlexFDO

Authors S. Shelah, Yuri Gurevich

Publication date 21 April 1997

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9411236

zbMATH Keywords

finite structuresinfinitary logicfixed-point logicrigid structures

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Models with special properties (saturated, rigid, etc.) (03C50) Other infinitary logic (03C75)

Abstract: The main result of this paper is a probabilistic construction of finite rigid structures. It yields a finitely axiomatizable class of finite rigid structures where no L^omega_{infty, omega} formula with counting quantifiers defines a linear order.

Recommendations

• How to define a linear order on finite models
• scientific article; zbMATH DE number 1361526
• Refuting Ehrenfeucht conjecture on rigid models
• Normalizable linear orders and generic computations in finite models

Cited in

(20)

• Recursive definitions and fixed-points
• scientific article; zbMATH DE number 3843254 (Why is no real title available?)
• Implicit definability and infinitary logic in finite model theory (extended abstract)
• On the descriptive complexity of temporal constraint satisfaction problems
• Is polynomial time choiceless?
• Canonization for two variables and puzzles on the square
• scientific article; zbMATH DE number 1556960 (Why is no real title available?)
• Rank logic is dead, long live rank logic!
• scientific article; zbMATH DE number 1000315 (Why is no real title available?)
• On the target pebbling conjecture
• On the Descriptive Complexity of Linear Algebra
• Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm
• \(\mathrm{SO}^F\): a semantic restriction over second-order logic and its polynomial-time hierarchy
• Finite-Variable Logics Do Not Have Weak Beth Definability Property
• The Structure of Rigid Frames of Depth 3 Only
• How to define a linear order on finite models
• Recursive definitions and fixed-points on well-founded structures
• Benchmark Graphs for Practical Graph Isomorphism
• Constructing hard examples for graph isomorphism
• Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas

This page was built for publication: On finite rigid structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4894726)