uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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, 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.

Place, publisher, year, edition, pages
2015. Vol. 7, no 2, p. 1-53, article id 1
Keywords [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, id: diva2:798508
Available from: 2015-03-26 Created: 2015-03-26 Last updated: 2017-12-04Bibliographically approved
In thesis
1. Limit Laws, Homogenizable Structures and Their Connections
Open this publication in new window or tab >>Limit Laws, Homogenizable Structures and Their Connections
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Alternative title[sv]
Gränsvärdeslagar, Homogeniserbara Strukturer och Deras Samband
Abstract [en]

This thesis is in the field of mathematical logic and especially model theory. The thesis contain six papers where the common theme is the Rado graph R. Some of the interesting abstract properties of R are that it is simple, homogeneous (and thus countably categorical), has SU-rank 1 and trivial dependence. The Rado graph is possible to generate in a probabilistic way. If we let K be the set of all finite graphs then we obtain R as the structure which satisfy all properties which hold with assymptotic probability 1 in K. On the other hand, since the Rado graph is homogeneous, it is also possible to generate it as a Fraïssé-limit of its age.

Paper I studies the binary structures which are simple, countably categorical, with SU-rank 1 and trivial algebraic closure. The main theorem shows that these structures are all possible to generate using a similar probabilistic method which is used to generate the Rado graph. Paper II looks at the simple homogeneous structures in general and give certain technical results on the subsets of SU-rank 1.

Paper III considers the set K consisting of all colourable structures with a definable pregeometry and shows that there is a 0-1 law and almost surely a unique definable colouring. When generating the Rado graph we almost surely have only rigid structures in K. Paper IV studies what happens if the structures in K are only the non-rigid finite structures. We deduce that the limit structures essentially try to stay as rigid as possible, given the restriction, and that we in general get a limit law but not a 0-1 law.

Paper V looks at the Rado graph's close cousin the random t-partite graph and notices that this structure is not homogeneous but almost homogeneous. Rather we may just add a definable binary predicate, which hold for any two elemenets which are in the same part, in order to make it homogeneous. This property is called being homogenizable and in Paper V we do a general study of homogenizable structures. Paper VI conducts a special case study of the homogenizable graphs which are the closest to being homogeneous, providing an explicit classification of these graphs.

Place, publisher, year, edition, pages
Uppsala: Department of Mathematics, 2018. p. 43
Series
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 104
Keywords
Model theory, random structure, finite model theory, simple theory, homogeneous structure, countably categorical, 0-1 law
National Category
Algebra and Logic
Research subject
Mathematical Logic; Mathematics
Identifiers
urn:nbn:se:uu:diva-330142 (URN)978-91-506-2672-8 (ISBN)
Public defence
2018-02-16, Polhemssalen, Ångströmlaboratoriet, Lägerhyddsvägen 1, Uppsala, 13:15 (English)
Opponent
Supervisors
Available from: 2018-01-17 Created: 2017-11-28 Last updated: 2018-02-09

Open Access in DiVA

fulltext(548 kB)65 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

Authority records BETA

Ahlman, OveKoponen, Vera

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: 65 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: 846 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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