Random graph: stronger logic but with the zero one law

by Shelah. [Sh:1077]

We find a logic really stronger than first order for the random graph with edge probability frac 12 but satisfies the 0-1 law. This means that on the one hand it satisfies the 0-1 law, e.g. for the random graph G_{n,1/2} and on the other hand there is a formula phi (x) such that for no first order psi (x) do we have: for every random enough G_{n,1/2} the formulas phi (x), psi (x) equivalent in it.

Back to the list of publications