uu.seUppsala universitets publikationer
Ändra sökning
Länk till posten
Permanent länk

Direktlänk
BETA
Alternativa namn
Publikationer (10 of 26) Visa alla publikationer
Koponen, V. (2019). Supersimple omega-categorical theories and pregeometries. Annals of Pure and Applied Logic, 170(12), Article ID 102718.
Öppna denna publikation i ny flik eller fönster >>Supersimple omega-categorical theories and pregeometries
2019 (Engelska)Ingår i: Annals of Pure and Applied Logic, ISSN 0168-0072, E-ISSN 1873-2461, Vol. 170, nr 12, artikel-id 102718Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We prove that if T is an omega-categorical supersimple theory with nontrivial dependence (given by forking), then there is a nontrivial regular 1-type over a finite set of reals which is realized by real elements; hence forking induces a nontrivial pregeometry on the solution set of this type and the pregeometry is definable (using only finitely many parameters). The assumption about omega-categoricity is necessary. This result is used to prove the following: If V is a finite relational vocabulary with maximal arity 3 and T is a supersimple V-theory with elimination of quantifiers, then T has trivial dependence and finite SU-rank. This immediately gives the following strengthening of [18, Theorem 4.1]: if M is a ternary simple homogeneous structure with only finitely many constraints, then Th(M) has trivial dependence and finite SU-rank. (C) 2019 Published by Elsevier B.V.

Ort, förlag, år, upplaga, sidor
Elsevier, 2019
Nyckelord
Model theory, Simple theory, Pregeometry, Omega-categorical theory, Elimination of quantifiers, Homogeneous structure
Nationell ämneskategori
Algebra och logik
Identifikatorer
urn:nbn:se:uu:diva-399083 (URN)10.1016/j.apal.2019.102718 (DOI)000491614200004 ()
Tillgänglig från: 2019-12-16 Skapad: 2019-12-16 Senast uppdaterad: 2019-12-16Bibliografiskt granskad
Koponen, V. (2018). Binary simple homogeneous structures. Annals of Pure and Applied Logic, 169(12), 1335-1368
Öppna denna publikation i ny flik eller fönster >>Binary simple homogeneous structures
2018 (Engelska)Ingår i: Annals of Pure and Applied Logic, ISSN 0168-0072, E-ISSN 1873-2461, Vol. 169, nr 12, s. 1335-1368Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We describe all binary simple homogeneous structures M in terms of ∅-definable equivalence relations on M, which “coordinatize” M and control dividing, and extension properties that respect these equivalence relations.

Nyckelord
model theory, homogeneous structure, simple theory, stability theory, classification theory
Nationell ämneskategori
Algebra och logik
Forskningsämne
Matematisk logik
Identifikatorer
urn:nbn:se:uu:diva-364743 (URN)10.1016/j.apal.2018.08.006 (DOI)000448496300007 ()
Tillgänglig från: 2018-11-01 Skapad: 2018-11-01 Senast uppdaterad: 2019-06-27Bibliografiskt granskad
Koponen, V. (2018). On Constraints And Dividing In Ternary Homogeneous Structures. Journal of Symbolic Logic (JSL), 83(4), 1691-1721
Öppna denna publikation i ny flik eller fönster >>On Constraints And Dividing In Ternary Homogeneous Structures
2018 (Engelska)Ingår i: Journal of Symbolic Logic (JSL), ISSN 0022-4812, E-ISSN 1943-5886, Vol. 83, nr 4, s. 1691-1721Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Let M be ternary, homogeneous and simple. We prove that if M is finitely constrained, then it is supersimple with finite SU-rank and dependence is k-trivial for some k < omega and for finite sets of real elements. Now suppose that, in addition, M is supersimple with SU-rank 1. If M is finitely constrained then algebraic closure in M is trivial. We also find connections between the nature of the constraints of M, the nature of the amalgamations allowed by the age of M, and the nature of definable equivalence relations. A key method of proof is to "extract" constraints (of M) from instances of dividing and from definable equivalence relations. Finally, we give new examples, including an uncountable family, of ternary homogeneous supersimple structures of SU-rank 1.

Nyckelord
model theory, homogeneous structure, simple theory, constraint, dividing, amalgamation
Nationell ämneskategori
Algebra och logik
Identifikatorer
urn:nbn:se:uu:diva-373241 (URN)10.1017/jsl.2018.61 (DOI)000454236900023 ()
Tillgänglig från: 2019-01-14 Skapad: 2019-01-14 Senast uppdaterad: 2019-01-14Bibliografiskt granskad
Koponen, V. (2017). Binary primitive homogeneous simple structures. Journal of Symbolic Logic (JSL), 82(1), 183-207
Öppna denna publikation i ny flik eller fönster >>Binary primitive homogeneous simple structures
2017 (Engelska)Ingår i: Journal of Symbolic Logic (JSL), ISSN 0022-4812, E-ISSN 1943-5886, Vol. 82, nr 1, s. 183-207Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Suppose that M is countable, binary, primitive, homogeneous, and simple. We prove that the SU-rank of the complete theory of M is 1 and hence 1-based. It follows that M is a random structure. The conclusion that M is a random structure does not hold if the binarity condition is removed, as witnessed by the generic tetrahedron-free 3-hypergraph. However, to show that the generic tetrahedron-free 3-hypergraph is 1-based requires some work (it is known that it has the other properties) since this notion is defined in terms of imaginary elements. This is partly why we also characterize equivalence relations which are definable without parameters in the context of omega-categorical structures with degenerate algebraic closure. Another reason is that such characterizations may be useful in future research about simple (nonbinary) homogeneous structures.

Nyckelord
model theory, homogeneous structure, simple theory, random structure
Nationell ämneskategori
Algebra och logik
Forskningsämne
Matematisk logik
Identifikatorer
urn:nbn:se:uu:diva-320741 (URN)10.1017/jsl.2016.51 (DOI)000397110700011 ()
Tillgänglig från: 2017-04-24 Skapad: 2017-04-24 Senast uppdaterad: 2017-04-26Bibliografiskt granskad
Koponen, V. (2017). Homogeneous 1-based structures and interpretability in random structures. Mathematical logic quarterly, 63(1-2), 6-18
Öppna denna publikation i ny flik eller fönster >>Homogeneous 1-based structures and interpretability in random structures
2017 (Engelska)Ingår i: Mathematical logic quarterly, ISSN 0942-5616, E-ISSN 1521-3870, Vol. 63, nr 1-2, s. 6-18Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Let V be a finite relational vocabulary in which no symbol has arity greater than 2. Let math formula be countable V-structure which is homogeneous, simple and 1-based. The first main result says that if math formula is, in addition, primitive, then it is strongly interpretable in a random structure. The second main result, which generalizes the first, implies (without the assumption on primitivity) that if math formula is “coordinatized” by a set with SU-rank 1 and there is no definable (without parameters) nontrivial equivalence relation on M with only finite classes, then math formula is strongly interpretable in a random structure.

Ort, förlag, år, upplaga, sidor
Wiley-VCH Verlagsgesellschaft, 2017
Nyckelord
model theory, homogeneous structure, simple theory, random structure
Nationell ämneskategori
Algebra och logik
Forskningsämne
Matematisk logik
Identifikatorer
urn:nbn:se:uu:diva-322293 (URN)10.1002/malq.201400096 (DOI)000400361900001 ()
Tillgänglig från: 2017-05-18 Skapad: 2017-05-18 Senast uppdaterad: 2017-06-26Bibliografiskt granskad
Ahlman, O. & Koponen, V. (2017). Random l-colourable structures with a pregeometry. Mathematical logic quarterly, 63(1-2), 32-58
Öppna denna publikation i ny flik eller fönster >>Random l-colourable structures with a pregeometry
2017 (Engelska)Ingår i: Mathematical logic quarterly, ISSN 0942-5616, E-ISSN 1521-3870, Vol. 63, nr 1-2, s. 32-58Artikel i tidskrift (Refereegranskat) 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).

Ort, förlag, år, upplaga, sidor
Wiley-VCH Verlagsgesellschaft, 2017
Nationell ämneskategori
Algebra och logik
Forskningsämne
Matematisk logik
Identifikatorer
urn:nbn:se:uu:diva-321515 (URN)10.1002/malq.201500006 (DOI)000400361900003 ()
Tillgänglig från: 2017-05-06 Skapad: 2017-05-06 Senast uppdaterad: 2017-11-28Bibliografiskt granskad
Koponen, V. (2016). Binary simple homogeneous structures are supersimple with finite rank. Proceedings of the American Mathematical Society, 144(4), 1745-1759
Öppna denna publikation i ny flik eller fönster >>Binary simple homogeneous structures are supersimple with finite rank
2016 (Engelska)Ingår i: Proceedings of the American Mathematical Society, ISSN 0002-9939, E-ISSN 1088-6826, Vol. 144, nr 4, s. 1745-1759Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Suppose that M is an infinite structure with finite relational vocabulary such that every relation symbol has arity at most 2. If M is simple and homogeneous, then its complete theory is supersimple with finite SU-rank which cannot exceed the number of complete 2-types over the empty set.

Nyckelord
Model theory; homogeneous structure; simple theory; stable theory; rank
Nationell ämneskategori
Algebra och logik
Forskningsämne
Matematisk logik
Identifikatorer
urn:nbn:se:uu:diva-275007 (URN)10.1090/proc/12828 (DOI)000369298400034 ()
Tillgänglig från: 2016-01-27 Skapad: 2016-01-27 Senast uppdaterad: 2017-11-30Bibliografiskt granskad
Ahlman, O. & Koponen, V. (2015). Limit laws and automorphism groups of random nonrigid structures. Journal of Logic and Analysis, 7(2), 1-53, Article ID 1.
Öppna denna publikation i ny flik eller fönster >>Limit laws and automorphism groups of random nonrigid structures
2015 (Engelska)Ingår i: Journal of Logic and Analysis, ISSN 1759-9008, 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 ()
Tillgänglig från: 2015-03-26 Skapad: 2015-03-26 Senast uppdaterad: 2017-12-04Bibliografiskt granskad
Koponen, V. & Hyttinen, T. (2015). On compactness of logics that can express properties of symmetry or connectivity. Studia Logica: An International Journal for Symbolic Logic, 103(1), 1-20
Öppna denna publikation i ny flik eller fönster >>On compactness of logics that can express properties of symmetry or connectivity
2015 (Engelska)Ingår i: Studia Logica: An International Journal for Symbolic Logic, ISSN 0039-3215, E-ISSN 1572-8730, Vol. 103, nr 1, s. 1-20Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

A condition, in two variants, is given such that if a property P satisfies this condition, then every logic which is at least as strong as first-order logic and can express P fails to have the compactness property. The result is used to prove that for a number of natural properties P speaking about automorphism groups or connectivity, every logic which is at least as strong as first-order logic and can express P fails to have the compactness property. The basic idea underlying the results and examples presented here is that it is possible to construct a countable first-order theory T such that every model of T has a very rich automorphism group, but every finite subset T' of T has a model which is rigid.

Ort, förlag, år, upplaga, sidor
Springer, 2015
Nyckelord
Abstract logic, Model theoretic logic, Compactness, Completeness, Automorphism, Connectivity, Random graph theory
Nationell ämneskategori
Algebra och logik
Forskningsämne
Matematisk logik
Identifikatorer
urn:nbn:se:uu:diva-244545 (URN)10.1007/s11225-013-9522-3 (DOI)000349360100001 ()
Tillgänglig från: 2015-02-17 Skapad: 2015-02-17 Senast uppdaterad: 2017-12-04Bibliografiskt granskad
Ahlman, O. & Koponen, V. (2015). On sets with rank one in simple homogeneous structures. Fundamenta Mathematicae, 228, 223-250
Öppna denna publikation i ny flik eller fönster >>On sets with rank one in simple homogeneous structures
2015 (Engelska)Ingår i: Fundamenta Mathematicae, ISSN 0016-2736, E-ISSN 1730-6329, Vol. 228, s. 223-250Artikel i tidskrift (Refereegranskat) 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.

Nyckelord
model theory, homogeneous structure, simple theory, pregeometry, rank, reduct, random structure
Nationell ämneskategori
Algebra och logik
Forskningsämne
Matematik
Identifikatorer
urn:nbn:se:uu:diva-243006 (URN)10.4064/fm228-3-2 (DOI)000352858400002 ()
Tillgänglig från: 2015-02-03 Skapad: 2015-02-03 Senast uppdaterad: 2017-12-05Bibliografiskt granskad
Organisationer
Identifikatorer
ORCID-id: ORCID iD iconorcid.org/0000-0002-9838-3403

Sök vidare i DiVA

Visa alla publikationer