Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T05:25:12.614Z Has data issue: false hasContentIssue false

A geometric zero-one law

Published online by Cambridge University Press:  12 March 2014

Robert H. Gilman
Affiliation:
Department of Mathematical Sciences, Stevens Institute of Technology, Hoboken, Nj 07030, USA, E-mail: rgilman@stevens.edu
Yuri Gurevich
Affiliation:
Microsoft Research, One Microsoft Way, Redmond, Wa 98052, USA E-mail: gurevich@microsoft.com
Alexei Miasnikov
Affiliation:
Department of Mathematics and Statistics, Mcgill University, Montreal, Quebec H3A 2K6, Canada, E-mail: alexeim@math.mcgill.ca

Abstract

Each relational structure X has an associated Gaifman graph, which endows X with the properties of a graph. If x is an element of X, let Bn(x) be the ball of radius n around x. Suppose that X is infinite, connected and of bounded degree. A first-order sentence ϕ in the language of X is almost surely true (resp. a.s. false) for finite substructures of X if for every x ∈ X, the fraction of substructures of Bn(x) satisfying ϕ approaches 1 (resp. 0) as n approaches infinity. Suppose further that, for every finite substructure, X has a disjoint isomorphic substructure. Then every ϕ is a.s. true or a.s. false for finite substructures of X. This is one form of the geometric zero-one law. We formulate it also in a form that does not mention the ambient infinite structure. In addition, we investigate various questions related to the geometric zero-one law.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable