In this chapter we show that properties expressible in many logics are almost surely true or almost surely false; that is, either they hold for almost all structures, or they fail for almost all structures. This phenomenon is known as the zero-one law. We prove it for FO, fixed point logics, and L∞ω ω. We shall also see that the “almost everywhere” behavior of logics is drastically different from their “everywhere” behavior. For example, while satisfiability in the finite is undecidable, it is decidable if a sentence is true in almost all finite models.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
- Zero-One Laws
Prof. Leonid Libkin
- Springer Berlin Heidelberg
ec4u, Neuer Inhalt/© ITandMEDIA