Random graphs in the monadic theory of order |
| |
| Authors: | Shmuel Lifsches Saharon Shelah |
| |
| Institution: | (1) Institute of Mathematics, The Hebrew University, Jerusalem, Israel , IL |
| |
| 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).
Received: 18 July 1996 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
