Home  Online Resources  Table of Contents

Journal of Logic and Computation, Volume 10, Issue 2, pp. 209-212: Abstract.

Stability, the finite cover property and 0-1 laws

JT Baldwin

Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, Chicago, IL, USA, E-mail: jbaldwin@math.uic.edu

We combine some tools from stability theory and finite model theory to prove the following results. Theorem. Let T[infin] be the almost sure theory for a class K and probability P satisfying the first order 0-1 law. Suppose for some [kgr], there are infinitely many distinct L[kgr]-types consistent with T[infin]. If LFP logic and first order-logic are almost everywhere equivalent with respect to P and T[infin] is unstable. Theorem. For appropriate functions f determining the interpretation of the Ramsey quantifier the logic L[ohgr],[ohgr](Qram,f) is almost everywhere equivalent to first-order logic on graphs with respect to edge probability n-[agr] for irrational [agr].

Keywords: finite model theory, stability theory.

  Full-Text PDF  (174 KB)


[ Oxford University Press]   [ Oxford Journals]   [ Comments & Feedback]   Copyright© Oxford University Press, 2000.