Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Limit Laws, Homogenizable Structures and Their Connections
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Matematiska institutionen.ORCID-id: 0000-0002-4477-4476
2018 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)Alternativ tittel
Gränsvärdeslagar, Homogeniserbara Strukturer och Deras Samband (svensk)
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.

sted, utgiver, år, opplag, sider
Uppsala: Department of Mathematics, 2018. , s. 43
Serie
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 104
Emneord [en]
Model theory, random structure, finite model theory, simple theory, homogeneous structure, countably categorical, 0-1 law
HSV kategori
Forskningsprogram
Matematisk logik; Matematik
Identifikatorer
URN: urn:nbn:se:uu:diva-330142ISBN: 978-91-506-2672-8 (tryckt)OAI: oai:DiVA.org:uu-330142DiVA, id: diva2:1160702
Disputas
2018-02-16, Polhemssalen, Ångströmlaboratoriet, Lägerhyddsvägen 1, Uppsala, 13:15 (engelsk)
Opponent
Veileder
Tilgjengelig fra: 2018-01-17 Laget: 2017-11-28 Sist oppdatert: 2018-02-09
Delarbeid
1. Simple structures axiomatized by almost sure theories
Åpne denne publikasjonen i ny fane eller vindu >>Simple structures axiomatized by almost sure theories
2016 (engelsk)Inngår i: Annals of Pure and Applied Logic, ISSN 0168-0072, E-ISSN 1873-2461, Vol. 167, nr 5, s. 435-456Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

In this article we give a classification of the binary, simple, ω-categorical structures with SU-rank 1 and trivial algebraic closure. This is done both by showing that they satisfy certain extension properties, but also by noting that they may be approximated by the almost sure theory of some sets of finite structures equipped with a probability measure. This study give results about general almost sure theories, but also considers certain attributes which, if they are almost surely true, generate almost sure theories with very specific properties such as ω-stability or strong minimality.

Emneord
Random structure, Almost sure theory, Pregeometry, Supersimple, Countably categorical
HSV kategori
Forskningsprogram
Matematik
Identifikatorer
urn:nbn:se:uu:diva-276995 (URN)10.1016/j.apal.2016.02.001 (DOI)000372680500001 ()
Tilgjengelig fra: 2016-03-01 Laget: 2016-02-17 Sist oppdatert: 2017-11-30bibliografisk kontrollert
2. On sets with rank one in simple homogeneous structures
Åpne denne publikasjonen i ny fane eller vindu >>On sets with rank one in simple homogeneous structures
2015 (engelsk)Inngår i: Fundamenta Mathematicae, ISSN 0016-2736, E-ISSN 1730-6329, Vol. 228, s. 223-250Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

We study definable sets D of SU-rank 1 in Meq, where M is a countable homogeneous and simple structure in a language with finite relational vocabulary. Each such D can be seen as a 'canonically embedded structure', which inherits all relations on D which are definable in Meq, and has no other definable relations. Our results imply that if no relation symbol of the language of M has arity higher than 2, then there is a close relationship between triviality of dependence and D being a reduct of a binary random structure. Somewhat more precisely: (a) if for every n≥2, every n-type p(x1,...,xn) which is realized in D is determined by its sub-2-types q(xi,xj)⊆p, then the algebraic closure restricted to D is trivial; (b) if M has trivial dependence, then D is a reduct of a binary random structure.

Emneord
model theory, homogeneous structure, simple theory, pregeometry, rank, reduct, random structure
HSV kategori
Forskningsprogram
Matematik
Identifikatorer
urn:nbn:se:uu:diva-243006 (URN)10.4064/fm228-3-2 (DOI)000352858400002 ()
Tilgjengelig fra: 2015-02-03 Laget: 2015-02-03 Sist oppdatert: 2017-12-05bibliografisk kontrollert
3. Random l-colourable structures with a pregeometry
Åpne denne publikasjonen i ny fane eller vindu >>Random l-colourable structures with a pregeometry
2017 (engelsk)Inngår i: Mathematical logic quarterly, ISSN 0942-5616, E-ISSN 1521-3870, Vol. 63, nr 1-2, s. 32-58Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

We study finite -colourable structures with an underlying pregeometry. The probability measure that is usedcorresponds to a process of generating such structures by which colours are first randomly assigned to all1-dimensional subspaces and then relationships are assigned in such a way that the colouring conditions aresatisfied but apart from this in a random way. We can then ask what the probability is that the resulting structure,where we now forget the specific colouring of the generating process, has a given property. With this measurewe get the following results: (1) A zero-one law. (2) The set of sentences with asymptotic probability 1 has anexplicit axiomatisation which is presented. (3) There is a formula ξ (x, y) (not directly speaking about colours)such that, with asymptotic probability 1, the relation “there is an -colouring which assigns the same colourto x and y” is defined by ξ (x, y). (4) With asymptotic probability 1, an -colourable structure has a unique-colouring (up to permutation of the colours).

sted, utgiver, år, opplag, sider
Wiley-VCH Verlagsgesellschaft, 2017
HSV kategori
Forskningsprogram
Matematisk logik
Identifikatorer
urn:nbn:se:uu:diva-321515 (URN)10.1002/malq.201500006 (DOI)000400361900003 ()
Tilgjengelig fra: 2017-05-06 Laget: 2017-05-06 Sist oppdatert: 2017-11-28bibliografisk kontrollert
4. Limit laws and automorphism groups of random nonrigid structures
Åpne denne publikasjonen i ny fane eller vindu >>Limit laws and automorphism groups of random nonrigid structures
2015 (engelsk)Inngår i: Journal of Logic and Analysis, ISSN 1759-9008, E-ISSN 1759-9008, Vol. 7, nr 2, s. 1-53, artikkel-id 1Artikkel i tidsskrift (Fagfellevurdert) 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.

Emneord
finite model theory, limit law, zero-one law, random structure, automorphism group
HSV kategori
Forskningsprogram
Matematisk logik
Identifikatorer
urn:nbn:se:uu:diva-248078 (URN)10.4115/jla.2015.7.2 (DOI)000359802400001 ()
Tilgjengelig fra: 2015-03-26 Laget: 2015-03-26 Sist oppdatert: 2017-12-04bibliografisk kontrollert
5. Homogenizable structures and model completeness
Åpne denne publikasjonen i ny fane eller vindu >>Homogenizable structures and model completeness
2016 (engelsk)Inngår i: Archive for mathematical logic, ISSN 0933-5846, E-ISSN 1432-0665, Vol. 55, nr 7-8, s. 977-995Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

A homogenizable structure M is a structure where we may add a finite amount of new relational symbols to represent some 0-definable relations in order to make the structure homogeneous. In this article we will divide the homogenizable structures into different classes which categorize many known examples and show what makes each class important. We will show that model completeness is vital for the relation between a structure and the amalgamation bases of its age and give a necessary and sufficient condition for an countably categorical model-complete structure to be homogenizable.

Emneord
Homogenizable, Model-complete, Amalgamation class, Quantifier-elimination
HSV kategori
Forskningsprogram
Matematik
Identifikatorer
urn:nbn:se:uu:diva-303714 (URN)10.1007/s00153-016-0507-6 (DOI)000385155700010 ()
Tilgjengelig fra: 2016-09-22 Laget: 2016-09-22 Sist oppdatert: 2017-11-28bibliografisk kontrollert
6. >k-homogeneous infinite graphs
Åpne denne publikasjonen i ny fane eller vindu >>>k-homogeneous infinite graphs
2018 (engelsk)Inngår i: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 128, s. 160-174Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

In this article we give an explicit classification for the countably infinite graphs G which are, for some k, ≥k-homogeneous. It turns out that a ≥k  -homogeneous graph M is non-homogeneous if and only if it is either not 1-homogeneous or not 2-homogeneous, both cases which may be classified using ramsey theory.

Emneord
>k-homomogeneous, countably infinite graph
HSV kategori
Forskningsprogram
Matematisk logik
Identifikatorer
urn:nbn:se:uu:diva-329362 (URN)10.1016/j.jctb.2017.08.007 (DOI)000417771100009 ()
Tilgjengelig fra: 2017-09-26 Laget: 2017-09-26 Sist oppdatert: 2018-04-05bibliografisk kontrollert

Open Access i DiVA

fulltext(414 kB)124 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 414 kBChecksum SHA-512
ad5e0bd6aa4ed09a1855774e642d62e448bd50b56d9e122ac7c95bd8f2f7fede874cb753fab6501ef8d23a2e70566050b53b1e1f4b3598f375e37ab7d29d8e27
Type fulltextMimetype application/pdf
errata(20 kB)6 nedlastinger
Filinformasjon
Fil ERRATA01.pdfFilstørrelse 20 kBChecksum SHA-512
c7bbc171a7ae81943542c0999b20bed00a73d0be87dd0da1bd7da116d08e80f734f5756767d9678c6915a259e90f3abc14623c3db775935109f8bd1bbdbf1a49
Type errataMimetype application/pdf

Søk i DiVA

Av forfatter/redaktør
Ahlman, Ove
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 124 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

isbn
urn-nbn

Altmetric

isbn
urn-nbn
Totalt: 811 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf