Random graphs in the monadic theory of order (Q1306794): Difference between revisions

In an earlier paper [``Peano arithmetic may not be interpretable in the monadic theory of linear orders'', J. Symb. Log. 62, No. 3, 848-872 (1997; Zbl 0888.03033)] the authors proved that it is consistent with ZFC that Peano Arithmetic is not interpretable in the monadic theory of linear orderings. In this paper a similar result is established for the (simpler) first order theory of random graphs. For \(1<K\leq\omega\), an undirected graph \(\mathcal G=(G,R)\) is \(K\)-random if any two pairwise disjoint subsets of \(G\) of cardinality \(<K\) are separated by some element of \(G\). \(\text{RG}_K\) is the first order theory of \(K\)-random graphs. The authors prove that there is a forcing notion \(P\) such that in \(V^P\) the theory \(\text{RG}_\omega\) is not interpretable in the monadic theory of order. This non-interpretability is provable in ZFC if it restricted to the monadic theory of short chains, i.e., the monadic theory of the real line.