A Fraïssé theory for partial orders of a fixed finite dimension
Iian B. Smythe, Mithuna Threz, Max Wiebe · 2024
Read A Fraïssé theory for partial orders of a fixed finite dimension by Iian B. Smythe, Mithuna Threz, Max Wiebe (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-18704.txt.
Introduction
Iian Smythe, Mithuna Threz, and Max Wiebe built a Fraïssé theory for partial orders of fixed finite dimension in two thousand twenty-four. A partial order has a dimension given by how many total orders combine to make it. Fraïssé theory builds a single large limit structure from a well-behaved class of finite ones.
For each dimension of two or more, they show the expanded class of finite orders is a Fraïssé class and name its limit. They give a finite set of axioms that pins the limit down among countable structures. The finite substructures have the Ramsey property, which by a known correspondence makes the limit's symmetry group extremely amenable. Similar results hold for rational grids.
Catalog record
| CREATOR | Iian B. Smythe, Mithuna Threz, Max Wiebe |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-18704
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Fraïssé theory for partial orders of a fixed finite dimension Thanks: This research was conducted as part of two undergraduate summer research projects under the supervision of the first author and supported by his NSERC Discovery Grant (RGPIN-2023-03343). The second author was also supported by two Undergraduate Summer Research Awards – International from the University of Winnipeg. The authors gratefully acknowledge these organizations and their support for undergraduate research. Iian B. Smythe, Mithuna Threz, Max Wiebe Abstract . For each n ≥ 2 n\geq 2 , we show that the class of all finite n n -dimensional partial orders, when expanded with n n linear orders which realize the partial order, forms a Fraïssé class and identify its Fraïssé limit ( D n , < , < 1 , … , < n ) (D_{n},<,<_{1},\ldots,<_{n}) . We give a finite axiomatization of this limit which specifies it uniquely up to isomorphism among countable structures, show that its class of finite substructures satisfies the Ramsey property, and conclude, by the Kechris–Pestov–Todorčević correspondence, that the automorphism group of the limit is extremely amenable. We then identify the universal minimal flow of the automorphism group of the reduct ( D n , < ) (D_{n},<) . Similar results are established for the n n -dimensional rational grid ( ℚ n , < ) (\mathbb{Q}^{n},<) and its expansion by the coordinate orders. 2020 Mathematics Subject Classification 06A07, 03C15, 05D10, 37B05 Introduction In his 1895 Beiträge [ 6 ] , Cantor proved that the set \mathbb{Q} of rational numbers, with its usual ordering, is the unique countable dense linear order without endpoints, up to isomorphism. The most well-known proof of this fact (e.g., in [ 13 ] ) is by a ‘‘back-and-forth’’ argument: 1 1 1 While the “back-and-forth” argument is often credited to Cantor, his original proof uses only the “forth” direction; see [ 25 ] for the history of this proof. Given a countable dense linear order without endpoints (L,<) , we enumerate both L and \mathbb{Q} , and construct an isomorphism from (L,<) to (\mathbb{Q},<) by building an increasing chain of isomorphisms between finite substructures. To extend the domain of our isomorphism to the next enumerated point of L , we find a corresponding point in \mathbb{Q} (going “forth”), and to extend the range to the next enumerated point of \mathbb{Q} , we find a corresponding point in L (going “back”). Density and the lack of endpoints ensure that these extensions are always possible. Fraïssé [ 8 ] gave a new interpretation of Cantor’s result by showing that (\mathbb{Q},<) can be viewed as the “limit” of its class of finite substructures, namely the finite linear orderings. More generally, Fraïssé showed that whenever a class of finite structures satisfies certain properties, all of its members embed into a unique countable ultrahomogeneous structure, up to isomorphism, now called its Fraïssé limit . This line of research connects to topological dynamics via the study of automorphism groups of countable structures. The most remarkable such connection, established by Kechris, Pestov, and Todorčević in [ 14 ] , says that a certain strong fixed-point property, extreme amenability , of the automorphism group of a Fraïssé limit of a class of finite structures endowed with a linear ordering, is equivalent to a finite combinatorial Ramsey property for that class. For example, the classical form of Ramsey’s Theorem [ 26 ] can be viewed as saying that the Ramsey property holds for the class of finite linear orders and thus, via this correspondence, the automorphism group of (\mathbb{Q},<) is extremely amenable, a result original proved by Pestov [ 24 ] . In cases where the underlying class of finite structures does not have the Ramsey property, but can be expanded to one which does, techniques from [ 14 ] can be used to identify the largest irreducible action, or universal minimal flow , of the automorphism group of its Fraïssé limit. The goal of the present article is to establish generalizations of the above results to partial orders of an arbitrary fixed finite dimension. The notion of dimension for a partial order (P,<) was defined by Dushnik and Miller in [ 7 ] to be the minimum number of linear orders on P whose intersection is < . The prototypical examples of n -dimensional partial orders are n -fold direct products of linear orders. Consequently, every countable n -dimensional partial order embeds into the rational grid (\mathbb{Q}^{n},<) . We will focus particular attention on certain topologically dense subsets D_{n} of \mathbb{Q}^{n} , isolated by Manaster and Remmel in [ 17 ] . The prima facie difficulty in attempting to develop a Fraïssé theory for n -dimensional partial orders is that, when n\geq 2 , they do not form a Fraïssé class (Proposition 2.3 ), nor are the natural “limit” objects (\mathbb{Q}^{n},<) or (D_{n},<) ultrahomogeneous (Proposition 2.4 ). The solution, as we will see, is to expand these structures by the n linear orders (or “realizers”) in the case of D_{n} , or n weak linear orders (or “weak realizers”) in the case of \mathbb{Q}^{n} , which intersect to give the underlying partial order. This article is arranged as follows: We begin by reviewing partial orders and dimension in Section 1 , and then Fraïssé theory in Section 2 . We show, in Section 3 , that the class of finite n -dimensional partial orders with realizers is a Fraïssé class with Fraïssé limit (D_{n},<,<_{1},\ldots,<_{n}) , where <_{1},\ldots,<_{n} are the n coordinate orderings inherited from \mathbb{Q}^{n} (Theorem 3.2 ). In Section 4 , we give a finite axiomatization of the first-order theory of this Fraïssé limit which specifies it uniquely up to isomorphism among countable structures (Theorem 4.5 ). In Section 5 , we show, as a consequence of the Product Ramsey Theorem of Graham, Rothschild, and Spencer [ 9 ] , that the class of finite n -dimensional partial orders with realizers satisfies the Ramsey property (Theorem 5.3 ) and conclude that the automorphism group of (D_{n},<,<_{1}\ldots,<_{n}) is extremely amenable (Corollary 5.6 ). In Section 6 , we identify the universal minimal flow of the automorphism group of (D_{n},<) as its natural action on the (finite) set of realizers for the underlying partial order (Theorem 6.7 ). Finally, in Section 7 , we carry out a similar analysis for (\mathbb{Q}^{n},\leq) and its expansion by the (weak) coordinate orders \leq_{1},\ldots,\leq_{n} . Before proceeding further, we note that some of our results, namely the fact that the finite n -dimensional partial orders with realizers form a Fraïssé class and have the Ramsey property, are equivalent to results first proved by Bodirsky [ 4 ] and Sokić [ 29 ] , a fact of which we only became aware after establishing them on our own. However, in neither [ 4 ] nor [ 29 ] is the Fraïssé limit of this class explicitly described, and our proof of the Ramsey property appears to be both simpler and more direct. Our other results, in particular those concerning universal minimal flows, are, to the best our knowledge, completely new. 1. Partial orders and dimension By a partial order we will mean both an irreflexive and transitive relation < on a set P ,