Name
Abstract | ||
|---|---|---|
A systematic study is made, for an arbitrary finite relational language with at least one symbol of arity at least 2, of classes of nonrigid finite structures. The well known results that almost all finite structures are rigid and that the class of finite structures has a zero-one law are, in the present context, the first layer in a hierarchy of classes of finite structures with increasingly more complex automorphism groups. Such a hierarchy can be defined in more than one way. For example, the kth level of the hierarchy can consist of all structures having at least k elements which are moved by some automorphism. Or we can consider, for any finite group G, all finite structures M such that G is a subgroup of the group of automorphisms of M; in this case the "hierarchy" is a partial order. In both cases, as well as variants of them, each "level" satisfies a logical limit law, but not a zero-one law (unless k = 0 or G is trivial). Moreover, the number of (labelled or unlabelled) n-element structures in one place of the hierarchy divided by the number of n-element structures in another place always converges to a rational number or to infinity as n -> infinity. All instances of the respective result are proved by an essentially uniform argument. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.4115/jla.2015.7.2 | JOURNAL OF LOGIC AND ANALYSIS |
Keywords | Field | DocType |
finite model theory, limit law, zero-one law, random structure, automorphism group | Discrete mathematics,Limit of a function,Combinatorics,Rational number,Arity,Division (mathematics),Mathematical analysis,Automorphism,Hierarchy,Finite group,Mathematics,Mathematical logic | Journal |
Volume | Issue | ISSN |
7 | 2 | 1759-9008 |
Citations | PageRank | References |
1 | 0.43 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ove Ahlman | 1 | 3 | 1.57 |
| Vera Koponen | 2 | 2 | 0.80 |