Definability in substructure orderings. I: Finite semilattices
Let \(K\) be a fixed class of structures of some given finite signature. Consider the collection \(L\) of all subclasses of \(K\) that are axiomatizable by a selected type \(T\) of axioms. This collection is usually a complete lattice with respect to inclusion. Let us say that \(L\) has \textit{positive definability} if one can prove the following statements: (1) the collection of all finitely \(T\)-axiomatizable subclasses of \(K\) is a definable subset of \(L\) and every element of that collection is definable in \(L\) up to the automorphisms of \(L\); (2) the collection of all finitely generated \(T\)-subclasses of \(K\) is a definable subset of \(L\) and every element of that collection is definable in \(L\) up to the automorphisms of \(L\); (3) the collection of the subclasses of \(K\) that are axiomatizable by a single \(T\)-axiom is a definable subset of \(L\); (4) \(L\) has no other automorphisms than the obvious, syntactically defined ones. In this paper, the authors investigate definability in the set of isomorphism types of finite semilattices ordered by embeddability; they prove, among other things, that every finite semilattice is a definable element in this ordered set. Then they apply these results to investigate definability in the closely related lattice of universal classes of semilattices; also, they prove that the lattice has no non-identical automorphisms, the set of finitely generated universal classes and also the set of finitely axiomatizable universal classes are definable subsets and each element of the two subsets is a definable element in the lattice.
- Avoidable structures. I: Finite ordered sets, semilattices and lattices
- Definability in substructure orderings. IV: Finite lattices
- Definability in substructure orderings. III: Finite distributive lattices
- Axiomatizing the subsumption and subword preorders on finite and infinite partial words
- Identical inclusions of semilattices
- Lattice of definability in the order of rational numbers
- Definability in the embeddability ordering of finite directed graphs
- Definability in the embeddability ordering of finite directed graphs. II
- Definability in the substructure ordering of simple graphs
- Definability in the substructure ordering of finite directed graphs
- Complexity in Young's lattice
- Alternating complexity of counting first-order logic for the subword order
- Well-Quasi Orders and Hierarchy Theory
- Semilattices of Definable Subalgebras
- Rogers Semilattices of Finite Partially Ordered Sets
- Definability in the Subword Order
- Definable Sets in Ordered Structures. II
- Defining recursive predicates in graph orders
- The lattice of definability. Origins, recent developments, and further directions
- The subtrace order and counting first-order logic
- Complexity of counting first-order logic for the subword order
- scientific article; zbMATH DE number 4195916 (Why is no real title available?)
- Definability of recursive predicates in the induced subgraph order
- Definability in first order theories of graph orderings
- scientific article; zbMATH DE number 7056230 (Why is no real title available?)
- Definability in the Homomorphic Quasiorder of Finite Labeled Forests
- On the automorphism group of the substructure ordering of finite directed graphs
- Semilattices of definable subalgebras. II
- Definability in substructure orderings. II: Finite ordered sets
This page was built for publication: Definability in substructure orderings. I: Finite semilattices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1040653)
