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

interpretabilityforcingconsistent with ZFCmonadic theory of the real linemonadic theory of linear orderstheory of random graphs

Mathematics Subject Classification ID

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

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).

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

(7)

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

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)