Hereditary Zero-One Laws for Graphs

by Doron and Shelah. [DoSh:953]
Fields Logic and Computation: Essays dedicated to Yuri Gurevich on Occasion his 70th Birthday, 2010
We consider the random graph M^n_{bar {p}} on the set [n], were the probability of {x,y} being an edge is p_{|x-y|}, and bar {p}=(p_1,p_2,p_3,...) is a series of probabilitie. We consider the set of all bar {q} derived from bar {p} by inserting 0 probabilities to bar {p}, or alternatively by decreasing some of the p_i . We say that bar {p} hereditarily satisfies the 0-1 law if the 0-1 law (for first order logic) holds in M^n_{bar {q}} for any bar {q} derived from bar {p} in the relevant way described above. We give a necessary and sufficient condition on bar {p} for it to hereditarily satisfy the 0-1 law.

Back to the list of publications