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