On finite rigid structures

DOI10.2307/2275675zbMATH Open0860.03029arXivmath/9411236OpenAlexW2164809404MaRDI QIDQ4894726FDOQ4894726

Authors: S. Shelah, Yuri Gurevich 

Publication date: 21 April 1997

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

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.

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

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

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)

Cited In (20)

• Recursive definitions and fixed-points
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Rank logic is dead, long live rank logic!
• Title not available (Why is that?)
• 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
• Benchmark Graphs for Practical Graph Isomorphism
• Recursive definitions and fixed-points on well-founded structures
• 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)