Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Limit laws and automorphism groups of random nonrigid structures
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Algebra and Geometry. (logic)
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Algebra and Geometry.
2015 (English)In: Journal of Logic and Analysis, ISSN 1759-9008, E-ISSN 1759-9008, Vol. 7, no 2, 1-53 p., 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.

Place, publisher, year, edition, pages
2015. Vol. 7, no 2, 1-53 p., 1
Keyword [en]
finite model theory, limit law, zero-one law, random structure, automorphism group
National Category
Algebra and Logic
Research subject
Mathematical Logic
Identifiers
URN: urn:nbn:se:uu:diva-248078DOI: 10.4115/jla.2015.7.2ISI: 000359802400001OAI: oai:DiVA.org:uu-248078DiVA: diva2:798508
Available from: 2015-03-26 Created: 2015-03-26 Last updated: 2017-12-04Bibliographically approved
In thesis
1.
The record could not be found. The reason may be that the record is no longer available or you may have typed in a wrong id in the address field.

Open Access in DiVA

fulltext(548 kB)57 downloads
File information
File name FULLTEXT01.pdfFile size 548 kBChecksum SHA-512
2cc0906c0e5db5d108ee086f41303f77784eff14047ceda006da6037f85ff82f49fe379b81021c4d1707035cb51726d2e4ad7b4dec16c3dad211e94463e4f8b2
Type fulltextMimetype application/pdf

Other links

Publisher's full texthttp://www.logicandanalysis.org/index.php/jla/article/view/213/103

Search in DiVA

By author/editor
Ahlman, OveKoponen, Vera
By organisation
Algebra and Geometry
In the same journal
Journal of Logic and Analysis
Algebra and Logic

Search outside of DiVA

GoogleGoogle Scholar
Total: 57 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 790 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf