Abstract
Let \({{\uppercase {\mathcal{p}}}} \) be the ordered set of isomorphism types of finite ordered sets (posets), where the ordering is by embeddability. We study first-order definability in this ordered set. We prove among other things that for every finite poset P, the set \(\{p,p^{\partial}\}\) is definable, where p and \(p^{\partial}\) are the isomorphism types of P and its dual poset. We prove that the only non-identity automorphism of \({{\uppercase {\mathcal{p}}}}\) is the duality map. Then we apply these results to investigate definability in the closely related lattice of universal classes of posets. We prove that this lattice has only one non-identity automorphism, the duality map; that the set of finitely generated and also the set of finitely axiomatizable universal classes are definable subsets of the lattice; and that for each member K of either of these two definable subsets, \(\{K,K^{\partial}\}\) is a definable subset of the lattice. Next, making fuller use of the techniques developed to establish these results, we go on to show that every isomorphism-invariant relation between finite posets that is definable in a certain strongly enriched second-order language \(\textup{\emph L}_2\) is, after factoring by isomorphism, first-order definable up to duality in the ordered set \({{\uppercase {\mathcal{p}}}}\). The language \(\textup{\emph L}_2\) has different types of quantifiable variables that range, respectively, over finite posets, their elements and order-relation, and over arbitrary subsets of posets, functions between two posets, subsets of products of finitely many posets (heteregenous relations), and can make reference to order relations between elements, the application of a function to an element, and the membership of a tuple of elements in a relation.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Dziobiak, W., Ježek, J., McKenzie, R.: Avoidable structures, I: finite ordered sets, semilattices and lattices. Algebra Univers. 60, 247–258 (2009)
Dziobiak, W., Ježek, J., McKenzie, R.: Avoidable structures, II: finite distributive lattices and nicely-structured ordered sets. Algebra Univers. 60, 259–291 (2009)
Ježek, J., McKenzie, R.: Definability in substructure orderings, I: finite semilattices. Algebra Univers. 61, 59-75 (2009)
Ježzek, J., McKenzie, R.: Definability in substructure orderings, III: finite distributive lattices. Algebra Univers. 61, 283–300 (2009)
Ježzek, J., McKenzie, R.: Definability in substructure orderings, IV: finite lattices. Algebra Univers. 61, 301–312 (2009)
Rampon, J.X.: What is reconstruction for ordered sets. Discrete Math. 291, 191–233 (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
While working on this paper, both authors were supported by US NSF grant DMS-0604065. The first author was also supported by the institutional grant MSM0021620839 financed by MSMT and partially supported by the grant GAČR 201/05/0002.
Rights and permissions
About this article
Cite this article
Ježek, J., McKenzie, R. Definability in Substructure Orderings, II: Finite Ordered Sets. Order 27, 115–145 (2010). https://doi.org/10.1007/s11083-010-9141-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-010-9141-9