Wikipedia informs me that the probability that a given structure (G-subN) with Domain {1,...,n} models S where 'S' is a first order sentence converges to either 0 or 1 as n->inf.

enter image description here

I have two questions regarding this result.

First, am I to understand the 'Domain' in this context to be the Domain of Discourse which is stipulated by G-subN, and is given by the non-empty set {1,...,n}?

Second, what does it mean for n->inf in this context?

  • 1
    G is indexed by n, so I think G_1 has domain {1}, but G_2 has domain {1, 2}, ... and that should help understand n -> inf. The G_i have progressively larger and larger domains.
    – Frank
    Mar 8 at 4:07
  • 1
    Predicates in the sentence can be interpreted as relations on the domain G_n={1,...,n} in many different ways, but for each n there are finitely many such interpretations up to isomorphism. Pr[G_n ⊨ S] is the fraction of those under which the sentence turns out to be true. Taking larger and larger domains you get a sequence of such fractions labeled by n. The 0-1 law states that this sequence converges to 0 or 1.
    – Conifold
    Mar 8 at 4:17
  • It is reminiscent of a kind of completeness result, but it would be good to tighten the presentation with more precise definitions.
    – Frank
    Mar 8 at 4:29
  • I applaud the effort and the results. It's long overdue, a particular deceased person (requiescat in pace) notwithstanding. Mar 8 at 4:57


You must log in to answer this question.

Browse other questions tagged .