A Geometric Zero-One Law
| dc.creator | Gilman, Robert H. | |
| dc.creator | Gurevich, Yuri | |
| dc.creator | Miasnikov, Alexei | |
| dc.date | 2007-06-02 | |
| dc.date.accessioned | 2026-07-07T08:03:56Z | |
| dc.date.available | 2026-07-07T08:03:56Z | |
| dc.description | Each relational structure X has an associated Gaifman graph, which endows X with the properties of a graph. 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 element x in X, the fraction of substructures of the ball of radius n around x which satisfy the sentence approaches 1 (resp. 0) as n approaches infinity. Suppose further that, for every finite substructure, X has a disjoint isomorphic substructure. Then every sentence 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. | |
| dc.description | 13 pages | |
| dc.identifier | https://arxiv.org/abs/0706.0271 | |
| dc.identifier | http://arxiv.org/abs/0706.0271 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/129768 | |
| dc.subject | Logic | |
| dc.subject | 03C13 | |
| dc.title | A Geometric Zero-One Law | |
| dc.type | text |