Open this publication in new window or tab >>2015 (English)In: Journal of Logic and Analysis, E-ISSN 1759-9008, Vol. 7, no 2, p. 1-53, article id 1Article in journal (Refereed) Published
Abstract [en]
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.
Keywords
finite model theory, limit law, zero-one law, random structure, automorphism group
National Category
Algebra and Logic
Research subject
Mathematical Logic
Identifiers
urn:nbn:se:uu:diva-248078 (URN)10.4115/jla.2015.7.2 (DOI)000359802400001 ()
2015-03-262015-03-262023-10-02Bibliographically approved