Random graphs in the monadic theory of order

DOI10.1007/S001530050129MaRDI QIDQ1306794zbMATH OpenOpenAlexFDO

Authors Shmuel Lifsches, S. Shelah

Publication date 2 May 2000

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9701219

zbMATH Keywords

consistent with ZFCforcinginterpretabilitymonadic theory of linear ordersmonadic theory of the real linetheory of random graphs

Mathematics Subject Classification ID

Consistency and independence results (03E35) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We continue the works of Gurevich-Shelah and Lifsches-Shelah by showing that it is consistent with ZFC that the first-order theory of random graphs is not interpretable in the monadic theory of all chains. It is provable from ZFC that the theory of random graphs is not interpretable in the monadic second order theory of short chains (hence, in the monadic theory of the real line).

Review text

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.

Recommendations

• scientific article; zbMATH DE number 426367
• Peano arithmetic may not be interpretable in the monadic theory of linear orders
• Undecidable statements and random graphs
• Monadic structures over an ordered universal random graph and finite automata

Cited in

(8)

• The monoid of the random graph
• Interpretation of graphs in noncommutative theories of Frechet powers
• Lower bounds on coloring numbers from hardness hypotheses in pcf theory
• The full binary tree cannot be interpreted in a chain
• Order with successors is not interprétable in RCF
• Peano arithmetic may not be interpretable in the monadic theory of linear orders
• MONOTONE INDEPENDENCE, COMB GRAPHS AND BOSE–EINSTEIN CONDENSATION
• Random graphs with a random bijection

This page was built for publication: Random graphs in the monadic theory of order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1306794)