10
$\begingroup$

$\DeclareMathOperator\Th{Th}$The random poset is the Fraisse limit of the class of finite posets, just like the random graph is the Fraisse limit of the class of finite graphs? That is, the random poset is the unique (upto isomorphism) countable poset $P$ such that every finite poset embeds into $P$ and every order isomorphism between finite subsets of $P$ extends to an order automorphism of $P$.

Now it has been proven that $\Th(P)$ is countably categorical, with $P$ being its unique model upto isomorphism. But my question is, do we know exactly what $\Th(P)$ is, or at least the complexity of the axioms of $\Th(P)$? I’m hoping for a result similar to the $\Pi^0_2$ axiomatization of the theory of the random graph.

$\endgroup$
6
  • $\begingroup$ Is there a random ring too? (Fraisse limit of finite rigs; should be okay as push-outs of finite rings are finite; if so, does it have a concreteish description?) $\endgroup$ Commented Mar 30, 2021 at 6:23
  • 5
    $\begingroup$ @TomaszKania As far as I can see, the class of finite rigs does not have a Fraïssé limit, as it lacks the joint embedding property (you can’t embed two rigs of different characteristics in a single rig). $\endgroup$ Commented Mar 30, 2021 at 7:11
  • $\begingroup$ What do you mean when you say the random graph has a $\Pi^0_2$ axiomatization? Are you talking about the quantifier complexity of the sentences themselves or the computational complexity of the set of axioms? $\endgroup$ Commented Mar 30, 2021 at 8:07
  • $\begingroup$ @JamesHanson I’m talking about the quantifier complexity of the sentences belonging to a certain set of sentences (called E_i,j by Wikipedia), a set which implies the theory of the random graph. $\endgroup$ Commented Mar 30, 2021 at 8:09
  • 2
    $\begingroup$ The form of the axioms of the random graph is not $\Pi^0_2$, but $\forall_2$. The notation $\Pi^0_2$ means universal quantifiers followed by existential quantifiers followed by a formula using bounded quantifiers, allowing second-order parameters. This only makes sense in the language of arithmetic. The language of random graphs includes neither bounded quantifiers nor set parameters. $\endgroup$ Commented Mar 30, 2021 at 8:21

1 Answer 1

10
$\begingroup$

It is confusing to call this the “random poset”, as it is very different from what is usually called random posets in the literature (in accordance with random graphs): e.g., random posets have height 3 with high probability. Unambiguous descriptions of this structure found in the literature are the countable universal homogeneous poset, the countable generic poset, or the countable existentially closed poset. (I will use the latter, as the axiomatization below rather directly corresponds to existential closedness.)

There is a perfectly general description. If $T$ is any universal theory in a finite relational language with the amalgamation property (and the joint embedding property, which however follows from AP in this case as long as you allow the empty structure), the Fraïssé limit of finite models of $T$ exists, and it is the unique countable existentially closed model of $T$. Its theory $T^*$ is $\omega$-categorical, and it is the theory of existentially closed models of $T$.

$T^*$ can be explicitly axiomatized by $T$ + all axioms of the form $$\forall\vec x\:(\mathrm{Diag}_A(\vec x)\to\exists z\:\mathrm{Diag}_B(\vec x,z)),$$ where $A\models T$ is finite (possibly empty), $\mathrm{Diag}_A$ denotes (the conjunction of) the diagram of $A$, and $B\models T$ is an extension of $A$ of size $|A|+1$.

[Proof sketch: on the one hand, the Fraïssé limit satisfies the given axioms; this amounts to the defining property that any embedding of $A$ into the structure extends to an embedding of $B$. On the other hand, a straightforward zig-zag argument shows that the theory with the given axioms is $\omega$-categorical. Thus, it is the complete theory of the Fraïssé limit.]

This is essentially a special case of the (possibly infinitary) axiomatization of existentially closed models of a given $\forall_2$ theory in terms of resultants; see §8.5 in Hodges, Model theory, CUP, 1993.

In the case of $T$ being the theory of posets, the axiomatization of $T^*$ above simplifies to:

  • The axioms of partial order.

  • The axioms $$\begin{multline} \forall x_1,\dots,x_n,y_1,\dots,y_m,u_1,\dots,u_p\:\Bigl[\bigwedge_{i,j}(x_i<y_j)\land\bigwedge_{i,k}(u_k\nleq x_i)\land\bigwedge_{j,k}(y_j\nleq u_k) \\\to\exists z\:\Bigl(\bigwedge_i(x_i<z)\land\bigwedge_j(z<y_j)\land\bigwedge_k(u_k\nleq z\land z\nleq u_k)\Bigr)\Bigr]\end{multline}$$ for all $n,m,p\in\omega$. That is, if $X,Y,U$ are finite sets such that $X<Y$ and no element of $U$ is below any element of $X$ or above any element of $Y$, then there exists $z$ such that $X<z<Y$ and $z$ is incomparable with all elements of $U$. Note that $n$, $m$, or $p$ may be $0$, thus the axioms ensure that the poset is upwards and downwards directed, but it has no minimal or maximal element.

This axiomatization is mentioned e.g. in Cameron & Lockett, Posets, homomorphisms and homogeneity, Discrete Mathematics 310 (2010), 604–613.

$\endgroup$
11
  • 3
    $\begingroup$ It is generated by a random process: sciencedirect.com/science/article/pii/S0097316503000049 $\endgroup$ Commented Mar 30, 2021 at 7:46
  • 4
    $\begingroup$ I see, I was not aware of this paper. Nevertheless, it is quite confusing to call this the random poset, as it is very different from what are usually know as random posets in the combinatorics literature. $\endgroup$ Commented Mar 30, 2021 at 7:50
  • 3
    $\begingroup$ Actually for the terminology one could imagine "Fraïssé random poset" or "Fraïssé poset". (For graphs, it's widely known, among other names, as "random graph", while plenty of other unrelated "random graphs" are being considered.) $\endgroup$
    – YCor
    Commented Mar 30, 2021 at 8:05
  • 5
    $\begingroup$ @YCor They are not unrelated. The point is that for the random graph, the most obvious probabilistic interpretations do coincide with the theory of the Fraïssé limit (the Fraïssé limit itself can be generated with probability 1 by taking the countable graph where each edge is included independently with probability $1/2$, and its first-order theory equals the theory of all sentences that holds with asymptotic probability $1$ in uniformly chosen (labelled or unlabelled) finite graphs). These connections break down in the case of posets. $\endgroup$ Commented Mar 30, 2021 at 8:15
  • 3
    $\begingroup$ @EmilJeřábek Yeah, model theorists sometimes use "random x" for "fraisse limit of the class of finite x's". I think it's better to say "generic x". $\endgroup$ Commented Mar 30, 2021 at 16:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .