| Ups and Downs of First Order Sentences on Random Graphs (2007) | |||||||||||||||
Abstract | |||||||||||||||
| hierarchy Shelah and Spencer [1] proved that the zero-one law holds for the rst order sentences on random graphs G(n; n) whenever is a xed positive irrational. This raises the question what zero-one valued functions on the positive irrationals arise as the limit probability of a rst order sentence on these graphs. Here we prove two necessary conditions on these functions, a number-theoretic and a complexity condition. We hope to prove in a subsequent paper that these conditions together with two simpler and previously proved conditions are also sucient and thus they constitute a characterization. | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||