Decidability of definability
From MaRDI portal
Abstract: For a fixed countably infinite structure Gamma with finite relational signature au, we study the following computational problem: input are quantifier-free au-formulas phi_0,phi_1,...,phi_n that define relations R_0,R_1,...,R_n over Gamma. The question is whether the relation R_0 is primitive positive definable from R_1,...,R_n, i.e., definable by a first-order formula that uses only relation symbols for R_1,..., R_n, equality, conjunctions, and existential quantification (disjunction, negation, and universal quantification are forbidden). We show decidability of this problem for all structures Gamma that have a first-order definition in an ordered homogeneous structure Delta with a finite relational signature whose age is a Ramsey class and determined by finitely many forbidden substructures. Examples of structures Gamma with this property are the order of the rationals, the random graph, the homogeneous universal poset, the random tournament, all homogeneous universal C-relations, and many more. We also obtain decidability of the problem when we replace primitive positive definability by existential positive, or existential definability. Our proof makes use of universal algebraic and model theoretic concepts, Ramsey theory, and a recent characterization of Ramsey classes in topological dynamics.
Recommendations
Cited in
(59)- Infinitely many reducts of homogeneous structures
- The wonderland of reflections
- Constants and finite unary relations in qualitative constraint reasoning
- Deciding open definability via subisomorphisms
- Decidability in elementary analysis. I
- Generating primitive positive clones
- Permutation groups with small orbit growth
- Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)
- Deciding quantifier-free definability in finite algebraic structures
- Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
- Fixed points in compactifications and combinatorial counterparts
- Decidability of general extensional mereology
- Gowers' Ramsey theorem with multiple operations and dynamics of the homeomorphism group of the Lelek fan
- Ramsey properties of products and pullbacks of categories and the Grothendieck construction
- Topological dynamics of kaleidoscopic groups
- Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
- The 42 reducts of the random ordered graph
- Reducts of Ramsey structures
- When Is Reachability Intrinsically Decidable?
- scientific article; zbMATH DE number 4085609 (Why is no real title available?)
- scientific article; zbMATH DE number 1302671 (Why is no real title available?)
- \(2^{\aleph_{0}}\) pairwise nonisomorphic maximal-closed subgroups of \(\mathrm{Sym}(\mathbb N)\) via the classification of the reducts of the Henson digraphs
- Reducts of the random partial order
- A dichotomy for first-order reducts of unary structures
- The language of stratified sets is confluent and strongly normalising
- Universal minimal flows of generalized Ważewski dendrites
- scientific article; zbMATH DE number 2151710 (Why is no real title available?)
- scientific article; zbMATH DE number 777294 (Why is no real title available?)
- Decidability in Intuitionistic Type Theory is Functionally Decidable
- Permutations on the random permutation
- Ticket Entailment is decidable
- Permutation groups containing infinite symplectic linear groups and reducts of linear spaces over the two element field
- Topological dynamics of unordered Ramsey structures
- PROJECTIVE CLONE HOMOMORPHISMS
- CORES OVER RAMSEY STRUCTURES
- A dichotomy theorem for the inverse satisfiability problem
- Canonical functions: a proof via topological dynamics
- Constraint satisfaction problems for reducts of homogeneous graphs
- Reducts of the Henson graphs with a constant
- Definability by turing machines
- Decidability and definability with circumscription
- Primitive positive formulas preventing a finite basis of quasi-equations
- The lattice of definability: origins, recent developments, and further directions
- Decidable and Undecidable Problems for First-Order Definability and Modal Definability
- A logic-based framework for characterizing nexus of similarity within knowledge bases
- Complexity classification transfer for CSPs via algebraic products
- From Ramsey degrees to Ramsey expansions via weak amalgamation
- Smooth approximations and CSPs over finitely bounded homogeneous structures
- Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
- Promise and infinite-domain constraint satisfaction
- Topological dynamics of Polish group extensions
- An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
- On the expression complexity of equivalence and isomorphism of primitive positive formulas
- Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
- A complexity dichotomy in spatial reasoning via Ramsey theory
- Generalized completion problems with forbidden tournaments
- Smooth approximations and relational width collapses
- Temporal valued constraint satisfaction problems
- Reducts of the generic digraph
This page was built for publication: Decidability of definability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5407040)
