Nonconvergence in the theory of random orders (Q1177706): Difference between revisions

Let \(P_ k\) be the random poset of dimension \(k\) on \(n\) elements obtained by intersecting \(k\) randomly and independently chosen linear orders; for \(k=2\) this amounts to selecting a randon non-identity permutation in \(S_ n\), the symmetric group. Let \(P_ 2(n)=\hbox{Ran}(n)\). If \(A\) is a property of posets, one might consider expressions \(\lim_{n\to \infty}\hbox{Pr}[\hbox{Ran}(n)\vdash A]\), where the value 1 denotes almost always (aa) and the value 0 denotes almost never (an). Winkler and Brightwell have shown that such limits may take values other than 0 and 1 if the property \(A\) can be written as a first- order sentence and in this paper the author constructs a suitably clever complicated first-order sentence such that \(\lim_{n\to \infty}\text{Pr}[\hbox{Ran}(n)\vdash A]\) does not exist. The method employed has as intermediate product an important non-separability result based on a special universal representation lemma developed in the paper as well as the Trakhtenbrot-Vaught Theorem, viz., there is no separation procedure on first-order sentences \(A\) that returns `yes' when \(A\) holds aa and `no' when A holds an. The technique used involves the sentence \(A\), built up out of various component parts designed to fail in some critical way along with estimates of various functions \(\varphi (n)\) of \(n\) with the property that \(\lim_{n\to \infty}\varphi(n)=0\) and Pr\([\hbox{something troublesome happens}]\leq \varphi(n)\), permitting the avoiding of unwanted complications in the long run.