Öppna denna publikation i ny flik eller fönster >>2015 (Engelska)Ingår i: Journal of Logic and Analysis, E-ISSN 1759-9008, Vol. 7, nr 2, s. 1-53, artikel-id 1Artikel i tidskrift (Refereegranskat) 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.
Nyckelord
finite model theory, limit law, zero-one law, random structure, automorphism group
Nationell ämneskategori
Algebra och logik
Forskningsämne
Matematisk logik
Identifikatorer
urn:nbn:se:uu:diva-248078 (URN)10.4115/jla.2015.7.2 (DOI)000359802400001 ()
2015-03-262015-03-262023-10-02Bibliografiskt granskad