Skip to main content
2 of 7
added 18 characters in body
Emil Jeřábek
  • 47.8k
  • 4
  • 151
  • 209

It is not appropriate to call this the “random poset”, as it is not generated by a random process. E.g., actual random posets have height 3 with high probability, hence they are very different from this.

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$. It 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, $\mathrm{Diag}_A$ denotes (the conjunction of) the diagram of $A$, and $B\models T$ is an extension of $A$ of size $|A|+1$.

In the case of $T$ being the theory of posets, $T^*$ can be axiomatized over $T$ by:

  • The axioms $$\forall x_1,\dots,x_n,y_1,\dots,y_m\:\Bigl(\bigwedge_{i,j}(x_i<y_j)\to\exists z\:\Bigl(\bigwedge_i(x_i<z)\land\bigwedge_j(z<y_j)\Bigr)\Bigr),$$ for all $n,m\in\omega$. That is, if $X$ and $Y$ are finite sets such that $X<Y$, then there is $z$ such that $X<z<Y$. Note that $n$ or $m$ may be $0$, in which case the axioms ensure that the poset is upwards and downwards directed, but it has no minimal or maximal element.

  • The axioms $$\begin{multline}\forall x,y,u_1,\dots,u_n\:\Bigl(x<y\land\bigwedge_i\neg(u_i\le x\lor y\le u_i)\\\to\exists z\:\Bigl(x<z\land z<y\land\bigwedge_i\neg(u_i\le z\lor z\le u_i)\Bigr)\Bigr),\end{multline}$$ for $n\in\omega$, ensuring that for any finite set $U$, any interval $[x,y]$ contains an element $z$ incomparable with all elements of $U$, as long as this is not impossible (i.e., some $u\in U$ is below $x$ or above $y$).

Emil Jeřábek
  • 47.8k
  • 4
  • 151
  • 209