Abstract We explore the interplay between $\omega $ -categoricity and pseudofiniteness for groups, and we conjecture that $\omega $ -categorical pseudofinite groups are finite-by-abelian-by-finite. We show that the conjecture reduces …
Abstract We explore the interplay between $\omega $ -categoricity and pseudofiniteness for groups, and we conjecture that $\omega $ -categorical pseudofinite groups are finite-by-abelian-by-finite. We show that the conjecture reduces to nilpotent p -groups of class 2, and give a proof that several of the known examples of $\omega $ -categorical p -groups satisfy the conjecture. In particular, we show by a direct counting argument that for any odd prime p the ( $\omega $ -categorical) model companion of the theory of nilpotent class 2 exponent p groups, constructed by Saracino and Wood, is not pseudofinite, and that an $\omega $ -categorical group constructed by Baudisch with supersimple rank 1 theory is not pseudofinite. We also survey some scattered literature on $\omega $ -categorical groups over 50 years.
We explore two constructions of oligomorphic Jordan permutation groups preserving a `limit of betweenness relations' and a `limit of $D$-relations', from \cite{bhattmacph2006jordan} and \cite{almazaydeh2021jordan} respectively. Several issues left open in …
We explore two constructions of oligomorphic Jordan permutation groups preserving a `limit of betweenness relations' and a `limit of $D$-relations', from \cite{bhattmacph2006jordan} and \cite{almazaydeh2021jordan} respectively. Several issues left open in \cite{almazaydeh2021jordan} are resolved. In particular it is shown that the `limit of $D$-relations' is not homogeneous in the given language, but is `homogenizable', that is, there is a homogeneous structure over a finite relational language with the same universe and the same automorphism group. The structure is NIP, but not monadically NIP, its age is not well-quasi-ordered under embeddability, and the growth rate of the sequence enumerating orbits on $k$-sets grows faster than exponentially. The automorphism group is maximal-closed in the symmetric group. Similar results are shown for the construction in \cite{bhattmacph2006jordan}.
We develop a general framework (multidimensional asymptotic classes, or m.a.c.s) for handling classes of finite first order structures with a strong uniformity condition on cardinalities of definable sets: The condition …
We develop a general framework (multidimensional asymptotic classes, or m.a.c.s) for handling classes of finite first order structures with a strong uniformity condition on cardinalities of definable sets: The condition asserts that definable families given by a formula \phi(x,y) should take on a fixed number n_\phi of approximate sizes in any M in the class, with those sizes varying with M. The prototype is the class of all finite fields, where the uniformity is given by a theorem of Chatzidakis, van den Dries and Macintyre. It inspired the development of asymptotic classes of finite structures, which this new framework extends. The underlying theory of m.a.c.s is developed, including preservation under bi-interpretability, and a proof that for the m.a.c. condition to hold it suffices to consider formulas \phi(x,y) with x a single variable. Many examples of m.a.c.s are given, including 2-sorted structures (F,V) where V is a vector space over a finite field F possibly equipped with a bilinear form, and an example arising from representations of quivers of finite representation type. We also give examples and structural results for multidimensional exact classes (m.e.c.s), where the definable sets take a fixed number of precisely specified cardinalities, which again vary with M. We also develop a notion of infinite generalised measurable structure, whereby definable sets are assigned values in an ordered semiring. We show that any infinite ultraproduct of a m.a.c. is generalised measurable, that values can be taken in an ordered ring if the m.a.c. is a m.e.c., and explore model-theoretic consequences of generalised measurability. Such a structure cannot have the strict order property, and stability-theoretic properties can be read off from the measures in the semiring.
We explore the interplay between omega-categoricity and pseudofiniteness for groups, conjecturing that omega-categorical pseudofinite groups are finite-by-abelian-by-finite. We show that the conjecture reduces to nilpotent p-groups of class 2, and …
We explore the interplay between omega-categoricity and pseudofiniteness for groups, conjecturing that omega-categorical pseudofinite groups are finite-by-abelian-by-finite. We show that the conjecture reduces to nilpotent p-groups of class 2, and give a proof that several of the known examples of omega-categorical p-groups satisfy the conjecture. In particular, we show by a direct counting argument that for any odd prime p the (omega-categorical) model companion of the theory of nilpotent class 2 exponent p groups, constructed by Saracino and Wood, is not pseudofinite, and that an omega-categorical group constructed by Baudisch with supersimple rank 1 theory is not pseudofinite. We also survey some scattered literature on omega-categorical groups over 50 years.
Abstract A ‐uniform hypergraph is set‐homogeneous if it is countable (possibly finite) and whenever two finite induced subhypergraphs are isomorphic there is with ; the hypergraph is said to be …
Abstract A ‐uniform hypergraph is set‐homogeneous if it is countable (possibly finite) and whenever two finite induced subhypergraphs are isomorphic there is with ; the hypergraph is said to be homogeneous if in addition every isomorphism between finite induced subhypergraphs extends to an automorphism. We give four examples of countably infinite set‐homogeneous ‐uniform hypergraphs that are not homogeneous (two with , one with and one with ). Evidence is also given that these may be the only ones, up to complementation. For example, for there is just one countably infinite ‐uniform hypergraph whose automorphism group is not 2‐transitive, and there is none for . We also give an example of a finite set‐homogeneous 3‐uniform hypergraph that is not homogeneous.
A $k$-uniform hypergraph $M$ is set-homogeneous if it is countable (possibly finite) and whenever two finite induced subhypergraphs $U,V$ are isomorphic there is $g\in Aut(M)$ with $U^g=V$; the hypergraph $M$ …
A $k$-uniform hypergraph $M$ is set-homogeneous if it is countable (possibly finite) and whenever two finite induced subhypergraphs $U,V$ are isomorphic there is $g\in Aut(M)$ with $U^g=V$; the hypergraph $M$ is said to be homogeneous if in addition every isomorphism between finite induced subhypergraphs extends to an automorphism. We give four examples of countably infinite set-homogeneous $k$-uniform hypergraphs which are not homogeneous (two with $k=3$, one with $k=4$, and one with $k=6$). Evidence is also given that these may be the only ones, up to complementation. For example, for $k=3$ there is just one countably infinite $k$-uniform hypergraph whose automorphism group is not 2-transitive, and there is none for $k=4$. We also give an example of a finite set-homogeneous 3-uniform hypergraph which is not homogeneous.
Abstract We construct via Fraïssé amalgamation an 𝜔-categorical structure whose automorphism group is an infinite oligomorphic Jordan primitive permutation group preserving a “limit of 𝐷-relations”. The construction is based on …
Abstract We construct via Fraïssé amalgamation an 𝜔-categorical structure whose automorphism group is an infinite oligomorphic Jordan primitive permutation group preserving a “limit of 𝐷-relations”. The construction is based on a semilinear order whose elements are labelled by sets carrying a 𝐷-relation, with strong coherence conditions governing how these 𝐷-sets are inter-related.
We construct via Fraïssé amalgamation an $ω$-categorical structure whose automorphism group is an infinite oligomorphic Jordan primitive permutation group preserving a `limit of $D$-relations'. The construction is based on a …
We construct via Fraïssé amalgamation an $ω$-categorical structure whose automorphism group is an infinite oligomorphic Jordan primitive permutation group preserving a `limit of $D$-relations'. The construction is based on a semilinear order whose elements are labelled by sets carrying a $D$-relation, with strong coherence conditions governing how these $D$-sets are inter-related.
VC-dimension and VC-density are measures of combinatorial complexity of set systems. VC-dimension was first introduced in the context of statistical learning theory, and is tightly related to the sample complexity …
VC-dimension and VC-density are measures of combinatorial complexity of set systems. VC-dimension was first introduced in the context of statistical learning theory, and is tightly related to the sample complexity in PAC learning. VC-density is a refinement of VC-dimension. Both notions are also studied in model theory, in the context of \emph{dependent} theories. A set system that is definable by a formula of first-order logic with parameters has finite VC-dimension if and only if the formula is a dependent formula. In this paper we study the VC-dimension and the VC-density of the edge relation $Exy$ on Johnson graphs and on Hamming graphs. On a graph $G$, the set system defined by the formula $Exy$ is the vertex set of $G$ along with the collection of all \emph{open neighbourhoods} of $G$. We show that the edge relation has VC-dimension at most $4$ on Johnson graphs and at most $3$ on Hamming graphs and these bounds are optimal. We furthermore show that the VC-density of the edge relation on the class of all Johnson graphs is $2$, and on the class of all Hamming graphs the VC-density is $2$ as well. Moreover, we show that our bounds on the VC-dimension carry over to the class of all induced subgraphs of Johnson graphs, and to the class of all induced subgraphs of Hamming graphs, respectively. It also follows that the VC-dimension of the set systems of \emph{closed neighbourhoods} in Johnson graphs and Hamming graphs is bounded. Johnson graphs and Hamming graphs are well known examples of distance transitive graphs. Neither of these graph classes is nowhere dense nor is there a bound on their (local) clique-width. Our results contrast this by giving evidence of structural tameness of the graph classes.
This is a survey, intended both for group theorists and model theorists, concerning the structure of pseudofinite groups, that is, infinite models of the first-order theory of finite groups. The …
This is a survey, intended both for group theorists and model theorists, concerning the structure of pseudofinite groups, that is, infinite models of the first-order theory of finite groups. The focus is on concepts from stability theory and generalisations in the context of pseudofinite groups, and on the information this might provide for finite group theory.
We consider profinite groups as 2-sorted first order structures, with a group sort, and a second sort which acts as an index set for a uniformly definable basis of neighbourhoods …
We consider profinite groups as 2-sorted first order structures, with a group sort, and a second sort which acts as an index set for a uniformly definable basis of neighbourhoods of the identity. It is shown that if the basis consists of {\em all} open subgroups, then the first order theory of such a structure is NIP (that is, does not have the independence property) precisely if the group has a normal subgroup of finite index which is a direct product of finitely many compact $p$-adic analytic groups, for distinct primes $p$. In fact, the condition NIP can here be weakened to NTP${}_2$. We also show that any NIP profinite group, presented as a 2-sorted structure, has an open prosoluble normal subgroup.
Abstract Answering a question of Junker and Ziegler, we construct a countable first order structure which is not ω -categorical, but does not have any proper nontrivial reducts, in either …
Abstract Answering a question of Junker and Ziegler, we construct a countable first order structure which is not ω -categorical, but does not have any proper nontrivial reducts, in either of two senses (model-theoretic, and group-theoretic). We also construct a strongly minimal set which is not ω -categorical but has no proper nontrivial reducts in the model-theoretic sense.
This is a survey, intended both for group theorists and model theorists, concerning the structure of pseudofinite groups, that is, infinite models of the first order theory of finite groups. …
This is a survey, intended both for group theorists and model theorists, concerning the structure of pseudofinite groups, that is, infinite models of the first order theory of finite groups. The focus is on concepts from stability theory and generalisations in the context of pseudofinite groups, and on the information this might provide for finite group theory.
This is a survey, intended both for group theorists and model theorists, concerning the structure of pseudofinite groups, that is, infinite models of the first order theory of finite groups. …
This is a survey, intended both for group theorists and model theorists, concerning the structure of pseudofinite groups, that is, infinite models of the first order theory of finite groups. The focus is on concepts from stability theory and generalisations in the context of pseudofinite groups, and on the information this might provide for finite group theory.
We recast the problem of calculating Vapnik-Chervonenkis (VC) density into one of counting types, and thereby calculate bounds (often optimal) on the VC density for some weakly o-minimal, weakly quasi-o-minimal, …
We recast the problem of calculating Vapnik-Chervonenkis (VC) density into one of counting types, and thereby calculate bounds (often optimal) on the VC density for some weakly o-minimal, weakly quasi-o-minimal, and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P"> <mml:semantics> <mml:mi>P</mml:mi> <mml:annotation encoding="application/x-tex">P</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-minimal theories.
We explore a notion of pseudofinite dimension, introduced by Hrushovski and Wagner, on an infinite ultraproduct of finite structures. Certain conditions on pseudofinite dimension are identified that guarantee simplicity or …
We explore a notion of pseudofinite dimension, introduced by Hrushovski and Wagner, on an infinite ultraproduct of finite structures. Certain conditions on pseudofinite dimension are identified that guarantee simplicity or supersimplicity of the underlying theory, and that a drop in pseudofinite dimension is equivalent to forking. Under a suitable assumption, a measure-theoretic condition is shown to be equivalent to local stability. Many examples are explored, including vector spaces over finite fields viewed as 2-sorted finite structures, and homocyclic groups. Connections are made to products of sets in finite groups, in particular to word maps, and a generalization of Tao's Algebraic Regularity Lemma is noted.
We explore a notion of pseudofinite dimension, introduced by Hrushovski and Wagner, on an infinite ultraproduct of finite structures. Certain conditions on pseudofinite dimension are identified that guarantee simplicity or …
We explore a notion of pseudofinite dimension, introduced by Hrushovski and Wagner, on an infinite ultraproduct of finite structures. Certain conditions on pseudofinite dimension are identified that guarantee simplicity or supersimplicity of the underlying theory, and that a drop in pseudofinite dimension is equivalent to forking. Under a suitable assumption, a measure-theoretic condition is shown to be equivalent to local stability. Many examples are explored, including vector spaces over finite fields viewed as 2-sorted finite structures, and homocyclic groups. Connections are made to products of sets in finite groups, in particular to word maps, and a generalization of Tao's algebraic regularity lemma is noted.
We explore a notion of pseudofinite dimension, introduced by Hrushovski and Wagner, on an infinite ultraproduct of finite structures. Certain conditions on pseudofinite dimension are identified that guarantee simplicity or …
We explore a notion of pseudofinite dimension, introduced by Hrushovski and Wagner, on an infinite ultraproduct of finite structures. Certain conditions on pseudofinite dimension are identified that guarantee simplicity or supersimplicity of the underlying theory, and that a drop in pseudofinite dimension is equivalent to forking. Under a suitable assumption, a measure-theoretic condition is shown to be equivalent to local stability. Many examples are explored, including vector spaces over finite fields viewed as 2-sorted finite structures, and homocyclic groups. Connections are made to products of sets in finite groups, in particular to word maps, and a generalization of Tao's algebraic regularity lemma is noted.
A famous result by Jeavons, Cohen, and Gyssens shows that every Constraint Satisfaction Problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. …
A famous result by Jeavons, Cohen, and Gyssens shows that every Constraint Satisfaction Problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. This is one of the basic facts for the so-called universal algebraic approach to a systematic theory of tractability and hardness in finite domain constraint satisfaction. Not surprisingly, the theorem of Jeavons et al. fails for arbitrary infinite domain CSPs. Many CSPs of practical interest, though, and in particular those CSPs that are motivated by qualitative reasoning calculi from artificial intelligence, can be formulated with constraint languages that are rather well-behaved from a model-theoretic point of view. In particular, the automorphism group of these constraint languages tends to be large in the sense that the number of orbits of n -subsets of the automorphism group is bounded by some function in n . In this article we present a generalization of the theorem by Jeavons et al. to infinite domain CSPs where the number of orbits of n -subsets grows subexponentially in n , and prove that preservation under a semi-lattice operation for such CSPs implies polynomial-time tractability. Unlike the result of Jeavons et al., this includes CSPs that cannot be solved by Datalog.
Answering a question of Junker and Ziegler, we construct a countable first order structure which is not omega-categorical, but does not have any proper non-trivial reducts, in either of two …
Answering a question of Junker and Ziegler, we construct a countable first order structure which is not omega-categorical, but does not have any proper non-trivial reducts, in either of two senses (model-theoretic, and group-theoretic). We also construct a strongly minimal set which is not omega-categorical but has no proper non-trivial reducts in the model-theoretic sense.
Abstract We give an example of an imaginary defined in certain valued fields with analytic structure which cannot be coded in the ‘geometric’ sorts which suffice to code all imaginaries …
Abstract We give an example of an imaginary defined in certain valued fields with analytic structure which cannot be coded in the ‘geometric’ sorts which suffice to code all imaginaries in the corresponding algebraic setting.
We study the Vapnik–Chervonenkis (VC) density of definable families in certain stable first-order theories. In particular, we obtain uniform bounds on the VC density of definable families in finite U-rank …
We study the Vapnik–Chervonenkis (VC) density of definable families in certain stable first-order theories. In particular, we obtain uniform bounds on the VC density of definable families in finite U-rank theories without the finite cover property, and we characterize those abelian groups for which there exist uniform bounds on the VC density of definable families.
Answering a question of Junker and Ziegler, we construct a countable first order structure which is not omega-categorical, but does not have any proper non-trivial reducts, in either of two …
Answering a question of Junker and Ziegler, we construct a countable first order structure which is not omega-categorical, but does not have any proper non-trivial reducts, in either of two senses (model-theoretic, and group-theoretic). We also construct a strongly minimal set which is not omega-categorical but has no proper non-trivial reducts in the model-theoretic sense.
Let G,H be closed permutation groups on an infinite set X, with H a subgroup of G. It is shown that if G and H are orbit-equivalent, that is, have …
Let G,H be closed permutation groups on an infinite set X, with H a subgroup of G. It is shown that if G and H are orbit-equivalent, that is, have the same orbits on the collection of finite subsets of X, and G is primitive but not 2-transitive, then G=H.
We show that any pseudofinite group with NIP theory and with a finite upper bound on the length of chains of centralisers is soluble-by-finite. In particular, any NIP rosy pseudofinite …
We show that any pseudofinite group with NIP theory and with a finite upper bound on the length of chains of centralisers is soluble-by-finite. In particular, any NIP rosy pseudofinite group is soluble-by-finite. This gener- alises, and shortens the proof of, an earlier result for stable pseudofinite groups. An example is given of an NIP pseudofinite group which is not soluble-by-finite. However, if C is a class of finite groups such that all infinite ultraproducts of members of C have NIP theory, then there is a bound on the index of the soluble radical of any member of C. We also survey some ways in which model theory gives information on families of finite simple groups, particularly concerning products of images of word maps.
Let G,H be closed permutation groups on an infinite set X, with H a subgroup of G. It is shown that if G and H are orbit-equivalent, that is, have …
Let G,H be closed permutation groups on an infinite set X, with H a subgroup of G. It is shown that if G and H are orbit-equivalent, that is, have the same orbits on the collection of finite subsets of X, and G is primitive but not 2-transitive, then G=H.
We show that any pseudofinite group with NIP theory and with a finite upper bound on the length of chains of centralisers is soluble-by-finite. In particular, any NIP rosy pseudofinite …
We show that any pseudofinite group with NIP theory and with a finite upper bound on the length of chains of centralisers is soluble-by-finite. In particular, any NIP rosy pseudofinite group is soluble-by-finite. This generalises, and shortens the proof of, an earlier result for stable pseudofinite groups. An example is given of an NIP pseudofinite group which is not soluble-by-finite. However, if C is a class of finite groups such that all infinite ultraproducts of members of C have NIP theory, then there is a bound on the index of the soluble radical of any member of C. We also survey some ways in which model theory gives information on families of finite simple groups, particularly concerning products of images of word maps.
We give an example of an imaginary defined in certain valued fields with analytic structure which cannot be coded in the `geometric' sorts which suffice to code all imaginaries in …
We give an example of an imaginary defined in certain valued fields with analytic structure which cannot be coded in the `geometric' sorts which suffice to code all imaginaries in the corresponding algebraic setting.
A famous result by Jeavons, Cohen, and Gyssens shows that every constraint satisfaction problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. …
A famous result by Jeavons, Cohen, and Gyssens shows that every constraint satisfaction problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. This is one of the basic facts for the so-called universal-algebraic approach to a systematic theory of tractability and hardness in finite domain constraint satisfaction.
Not surprisingly, the theorem of Jeavons et al. fails for arbitrary infinite domain CSPs. Many CSPs of practical interest, though, and in particular those CSPs that are motivated by qualitative reasoning calculi from Artificial Intelligence, can be formulated with constraint languages that are rather well-behaved from a model-theoretic point of view. In particular, the automorphism group of these constraint languages tends to be large in the sense that the number of orbits of n-subsets of the automorphism group is bounded by some function in n.
In this paper we present a generalization of the theorem by Jeavons et al. to infinite domain CSPs where the number of orbits of n-subsets grows sub-exponentially in n, and prove that preservation under a semi-lattice operation for such CSPs implies polynomial-time tractability. Unlike the result of Jeavons et al., this includes many CSPs that cannot be solved by Datalog.
We consider groups G interpretable in a supersimple finite rank theory T such that Teq eliminates ∃∞. It is shown that G has a definable soluble radical. If G has …
We consider groups G interpretable in a supersimple finite rank theory T such that Teq eliminates ∃∞. It is shown that G has a definable soluble radical. If G has rank 2, then if G is pseudofinite, it is soluble-by-finite, and partial results are obtained under weaker hypotheses, such as ‘functional unimodularity’ of the theory. A classification is obtained when T is pseudofinite and G has a definable and definably primitive action on a rank 1 set.
This paper provides an overview of recent work by the authors and others on two topics in the model theory of finite structures. The point of view here differs from …
This paper provides an overview of recent work by the authors and others on two topics in the model theory of finite structures. The point of view here differs from that usually associated with the term 'finite model theory', as presented for example in [21] or [46], in which the emphasis and motivation come primarily from computer science. Instead, the inspiration for this work has its origins in contemporary (infinite) model theoretic themes such as dimension, independence, and various measures of the complexity of definable sets. Each of the topics deals with classes of finite structures for first-order logic that are isolated by conditions that are drawn from these model-theoretic considerations. Moreover, in both cases, connections exist to areas in infinite model theory such as stability and simplicity theory, and o-minimality. This survey is intended for both mathematical logicians and computer scientists whose work focuses on logical aspects of the subject.
A famous result by Jeavons, Cohen, and Gyssens shows that every constraint satisfaction problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. …
A famous result by Jeavons, Cohen, and Gyssens shows that every constraint satisfaction problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. This is one of the basic facts for the so-called universal-algebraic approach to a systematic theory of tractability and hardness in finite domain constraint satisfaction. Not surprisingly, the theorem of Jeavons et al. fails for arbitrary infinite domain CSPs. Many CSPs of practical interest, though, and in particular those CSPs that are motivated by qualitative reasoning calculi from Artificial Intelligence, can be formulated with constraint languages that are rather well-behaved from a model-theoretic point of view. In particular, the automorphism group of these constraint languages tends to be large in the sense that the number of orbits of n-subsets of the automorphism group is bounded by some function in n. In this paper we present a generalization of the theorem by Jeavons et al. to infinite domain CSPs where the number of orbits of n-subsets grows sub-exponentially in n, and prove that preservation under a semi-lattice operation for such CSPs implies polynomial-time tractability. Unlike the result of Jeavons et al., this includes many CSPs that cannot be solved by Datalog.
We give an example of an imaginary defined in certain valued fields with analytic structure which cannot be coded in the `geometric' sorts which suffice to code all imaginaries in …
We give an example of an imaginary defined in certain valued fields with analytic structure which cannot be coded in the `geometric' sorts which suffice to code all imaginaries in the corresponding algebraic setting.
A directed graph is set-homogeneous if, whenever U and V are isomorphic finite subdigraphs, there is an automorphism g of the digraph with U^g=V. Here, extending work of Lachlan on …
A directed graph is set-homogeneous if, whenever U and V are isomorphic finite subdigraphs, there is an automorphism g of the digraph with U^g=V. Here, extending work of Lachlan on finite homogeneous digraphs, we classify finite set-homogeneous digraphs, where we allow some pairs of vertices to have arcs in both directions. Under the assumption that such pairs of vertices are not allowed, we obtain initial results on countably infinite set-homogeneous digraphs, classifying those which are not 2-homogeneous.
A directed graph is set-homogeneous if, whenever U and V are isomorphic finite subdigraphs, there is an automorphism g of the digraph with U^g=V. Here, extending work of Lachlan on …
A directed graph is set-homogeneous if, whenever U and V are isomorphic finite subdigraphs, there is an automorphism g of the digraph with U^g=V. Here, extending work of Lachlan on finite homogeneous digraphs, we classify finite set-homogeneous digraphs, where we allow some pairs of vertices to have arcs in both directions. Under the assumption that such pairs of vertices are not allowed, we obtain initial results on countably infinite set-homogeneous digraphs, classifying those which are not 2-homogeneous.
We give a description of infinite families of finite primitive permutation groups for which there is a uniform finite upper bound on the diameter of all orbital graphs. This is …
We give a description of infinite families of finite primitive permutation groups for which there is a uniform finite upper bound on the diameter of all orbital graphs. This is equivalent to describing families of finite permutation groups such that every ultraproduct of the family is primitive. A key result is that, in the almost simple case with socle of fixed Lie rank, apart from very specific cases, there is such a diameter bound. This is proved using recent results on the model theory of pseudofinite fields and difference fields.
The second of a two volume set showcasing current research in model theory and its connections with number theory, algebraic geometry, real analytic geometry and differential algebra. Each volume contains …
The second of a two volume set showcasing current research in model theory and its connections with number theory, algebraic geometry, real analytic geometry and differential algebra. Each volume contains a series of expository essays and research papers around the subject matter of a Newton Institute Semester on Model Theory and Applications to Algebra and Analysis. The articles convey outstanding new research on topics such as model theory and conjectures around Mordell-Lang; arithmetic of differential equations, and Galois theory of difference equations; model theory and complex analytic geometry; o-minimality; model theory and non-commutative geometry; definable groups of finite dimension; Hilbert's tenth problem; and Hrushovski constructions. With contributions from so many leaders in the field, this book will undoubtedly appeal to all mathematicians with an interest in model theory and its applications, from graduate students to senior researchers and from beginners to experts.
A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
The study of permutation groups has always been closely associated with that of highly symmetric structures. The objects considered here are countably infinite, but have only finitely many different substructures …
The study of permutation groups has always been closely associated with that of highly symmetric structures. The objects considered here are countably infinite, but have only finitely many different substructures of any given finite size. They are precisely those structures which are determined by first-order logical axioms together with the assumption of countability. This book concerns such structures, their substructures and their automorphism groups. A wide range of techniques are used: group theory, combinatorics, Baire category and measure among them. The book arose from lectures given at a research symposium and retains their informal style, whilst including as well many recent results from a variety of sources. It concludes with exercises and unsolved research problems.
A tournament <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T"> <mml:semantics> <mml:mi>T</mml:mi> <mml:annotation encoding="application/x-tex">T</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is called homogeneous just in case every isomorphism of subtournaments of smaller cardinality can be …
A tournament <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T"> <mml:semantics> <mml:mi>T</mml:mi> <mml:annotation encoding="application/x-tex">T</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is called homogeneous just in case every isomorphism of subtournaments of smaller cardinality can be lifted to an automorphism of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T"> <mml:semantics> <mml:mi>T</mml:mi> <mml:annotation encoding="application/x-tex">T</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. It is shown that there are precisely three homogeneous tournaments of power <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal alef 0"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi mathvariant="normal">ℵ<!-- ℵ --></mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\aleph _0}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Some analogous results for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2"> <mml:semantics> <mml:mn>2</mml:mn> <mml:annotation encoding="application/x-tex">2</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-tournaments are obtained.
A collection ${\mathcal C}$ of finite $\mathcal {L}$-structures is a 1-dimensional asymptotic class if for every $m \in {\mathbb N}$ and every formula $\varphi (x,\bar {y})$, where $\bar {y}=(y_1,\ldots ,y_m)$: …
A collection ${\mathcal C}$ of finite $\mathcal {L}$-structures is a 1-dimensional asymptotic class if for every $m \in {\mathbb N}$ and every formula $\varphi (x,\bar {y})$, where $\bar {y}=(y_1,\ldots ,y_m)$: [(i)] There is a positive constant $C$ and a finite set $E\subset {\mathbb R}^{>0}$ such that for every $M\in {\mathcal C}$ and $\bar {a}\in M^m$, either $|\varphi (M,\bar {a})|\leq C$, or for some $\mu \in E$, \[ \big ||\varphi (M,\bar {a})|-\mu |M|\big | \leq C|M|^{\frac {1}{2}}.\] [(ii)] For every $\mu \in E$, there is an $\mathcal {L}$-formula $\varphi _{\mu }(\bar {y})$, such that $\varphi _{\mu }(M^m)$ is precisely the set of $\bar {a}\in M^m$ with \[ \big ||\varphi (M,\bar {a})|-\mu |M|\big | \leq C|M|^{\frac {1}{2}}.\] One-dimensional asymptotic classes are introduced and studied here. These classes come equipped with a notion of dimension that is intended to provide for the study of classes of finite structures a concept that is central in the development of model theory for infinite structures. Connections with the model theory of infinite structures are also drawn.
In this paper we formulate a notion similar to o -minimality but appropriate for the p -adics. The paper is in a sense a sequel to [11] and [5]. In …
In this paper we formulate a notion similar to o -minimality but appropriate for the p -adics. The paper is in a sense a sequel to [11] and [5]. In [11] a notion of minimality was formulated, as follows. Suppose that L, L + are first-order languages and + is an L + -structure whose reduct to L is . Then + is said to be -minimal if, for every N + elementarily equivalent to + , every parameterdefinable subset of its domain N + is definable with parameters by a quantifier-free L -formula. Observe that if L has a single binary relation which in is interpreted by a total order on M , then we have just the notion of strong o-minimality , from [13]; and by a theorem from [6], strong o -minimality is equivalent to o -minimality. If L has no relations, functions, or constants (other than equality) then the notion is just strong minimality . In [11], -minimality is investigated for a number of structures . In particular, the C-relation of [1] was considered, in place of the total order in the definition of strong o -minimality. The C -relation is essentially the ternary relation which naturally holds on the maximal chains of a sufficiently nice tree; see [1], [11] or [5] for more detail, and for axioms. Much of the motivation came from the observation that a C -relation on a field F which is preserved by the affine group AGL(1, F ) (consisting of permutations ( a,b ) : x ↦ ax + b , where a ∈ F \ {0} and b ∈ F ) is the same as a non-trivial valuation: to get a C -relation from a valuation ν, put C ( x;y,z ) if and only if ν( y − x ) < ν( y − z ).
Let G be a permutation group on an infinite set X, and for k ∈ N let nk(G), respectively Nk(G), be the numbers of orbits of G on unordered k-sets, …
Let G be a permutation group on an infinite set X, and for k ∈ N let nk(G), respectively Nk(G), be the numbers of orbits of G on unordered k-sets, respectively ordered k-sets, of X. It is shown that if G is primitive but not highly homogeneous, then nk(G) has at least exponential growth rate; also, that if G is primitive but not highly transitive, then Nk(G) grows not much slower than k!. Finally, there is a proof that if G is primitive but not highly transitive, and if X is countable, then G has 2N0 orbits on the power set of X.
By W. Carter Roger: pp. viii, 331. £7.50. John Wiley & Sons, December 1972.)
By W. Carter Roger: pp. viii, 331. £7.50. John Wiley & Sons, December 1972.)
We prove that every infinite primitive Jordan permutation group preserves a structure in one of a finite list of familiar families, or a limit of structures in one of these …
We prove that every infinite primitive Jordan permutation group preserves a structure in one of a finite list of familiar families, or a limit of structures in one of these families. The structures are: semilinear orders (‘trees’) or betweenness relations induced from semilinear orders, chains of semilinear orders, points at infinity of a betweenness relation, linear and circular orders and the corresponding betweenness and separation relations, and Steiner systems. A Jordan group is a permutation group (G, Ω) such that there is a subset Γ ⊆ Ω satisfying various non-triviality assumptions, with G(Ω\Γ) transitive on Γ.
Results are obtained concerning normal subgroups of the automorphism groups of certain infinite trees. These structures are mostly ℵo-categorical, and are trees in a poset-theoretic but not graph-theoretic sense. It …
Results are obtained concerning normal subgroups of the automorphism groups of certain infinite trees. These structures are mostly ℵo-categorical, and are trees in a poset-theoretic but not graph-theoretic sense. It is shown that the automorphism group has a smallest non-trivial normal subgroup, a largest proper normal subgroup, and at least 22ο normal subgroups between these two. We also obtain and use some results on groups of automorphisms of chains.
In this paper we extend two theorems from [2] on p-adic subanalytic sets, where p is a fixed prime number, Qp is the field of p-adic numbers and Zp is …
In this paper we extend two theorems from [2] on p-adic subanalytic sets, where p is a fixed prime number, Qp is the field of p-adic numbers and Zp is the ring of p-adic integers. One of these theorems [2, 3.32] says that each subanalytic subset of Zp is semialgebraic. This is extended here as follows.
In this paper we consider classes of finite structures where we have good control over the sizes of the definable sets. The motivating example is the class of finite fields: …
In this paper we consider classes of finite structures where we have good control over the sizes of the definable sets. The motivating example is the class of finite fields: it was shown in [1] that for any formula in the language of rings, there are finitely many pairs ( d , μ ) ∈ ω × Q >0 so that in any finite field F and for any ā ∈ F m the size | ø ( F n ,ā)| is “approximately” μ | F | d . Essentially this is a generalisation of the classical Lang-Weil estimates from the category of varieties to that of the first-order-definable sets.
A Frobenius difference field is an algebraically closed field of characteristic $p>0$, enriched with a symbol for $x \mapsto x^{p^m}$. We study a sentence or formula in the language of …
A Frobenius difference field is an algebraically closed field of characteristic $p>0$, enriched with a symbol for $x \mapsto x^{p^m}$. We study a sentence or formula in the language of fields with a distinguished automorphism, interpreted in Frobenius difference fields with $p$ or $m$ tending to infinity. In particular, a decision procedure is found to determine when a sentence is true in almost every Frobenius difference field. This generalizes Cebotarev's density theorem and Weil's Riemann hypothesis for curves (both in qualitative versions), but hinges on a result going slightly beyond the latter.
The setting for the proof is the geometry of difference varieties of transformal dimension zero; these generalize algebraic varieties, and are shown to have a rich structure, only partly explicated here.
Some applications are given, in particular to finite simple groups, and to the Jacobi bound for difference equations.
It is proved that any supersimple field has trivial Brauer group, and more generally that any supersimple division ring is commutative. As prerequisites we prove several results about generic types …
It is proved that any supersimple field has trivial Brauer group, and more generally that any supersimple division ring is commutative. As prerequisites we prove several results about generic types in groups and fields whose theory is simple.
Abstract This book is a collection of articles, some introductory, some extended surveys, and some containing previously unpublished research, on a range of topics linking infinite permutation group theory and …
Abstract This book is a collection of articles, some introductory, some extended surveys, and some containing previously unpublished research, on a range of topics linking infinite permutation group theory and model theory. Topics covered include: oligomorphic permutation groups and omega-categorical structures; totally categorical structures and covers; automorphism groups of recursively saturated structures; Jordan groups; Hrushovski's constructions of pseudoplanes; permutation groups of finite Morley rank; applications of permutation group theory to models of set theory without the axiom of choice. There are introductory chapters by the editors on general model theory and permutation theory, recursively saturated structures, and on groups of finite Morley rank. The book is almost self-contained, and should be useful to both a beginning postgraduate student meeting the subject for the first time, and to an active researcher from either of the two main fields looking for an overview of the subject.
A difference field is a field with a distinguished automorphism<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="sigma"><mml:semantics><mml:mi>σ</mml:mi><mml:annotation encoding="application/x-tex">\sigma</mml:annotation></mml:semantics></mml:math></inline-formula>. This paper studies the model theory of existentially closed difference fields. We introduce a dimension theory …
A difference field is a field with a distinguished automorphism<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="sigma"><mml:semantics><mml:mi>σ</mml:mi><mml:annotation encoding="application/x-tex">\sigma</mml:annotation></mml:semantics></mml:math></inline-formula>. This paper studies the model theory of existentially closed difference fields. We introduce a dimension theory on formulas, and in particular on difference equations. We show that an arbitrary formula may be reduced into one-dimensional ones, and analyze the possible internal structures on the one-dimensional formulas when the characteristic is<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="0"><mml:semantics><mml:mn>0</mml:mn><mml:annotation encoding="application/x-tex">0</mml:annotation></mml:semantics></mml:math></inline-formula>.
Abstract We give a self-contained proof of the O'Nan-Scott Theorem for finite primitive permutation groups.
Abstract We give a self-contained proof of the O'Nan-Scott Theorem for finite primitive permutation groups.
We study forking, Lascar strong types, Keisler measures and definable groups, under an assumption of NIP (not the independence property), continuing aspects of the paper [16]. Among key results are …
We study forking, Lascar strong types, Keisler measures and definable groups, under an assumption of NIP (not the independence property), continuing aspects of the paper [16]. Among key results are (i) if p = \mathrm{tp}(b/A) does not fork over A then the Lascar strong type of b over A coincides with the compact strong type of b over A and any global nonforking extension of p is Borel definable over \mathrm{bdd}(A) , (ii) analogous statements for Keisler measures and definable groups, including the fact that G^{000} = G^{00} for G definably amenable, (iii) definitions, characterizations and properties of “generically stable” types and groups, (iv) uniqueness of invariant (under the group action) Keisler measures on groups with finitely satisfiable generics, (v) a proof of the compact domination conjecture for (definably compact) commutative groups in o -minimal expansions of real closed fields.
We give a description of infinite families of finite primitive permutation groups for which there is a uniform finite upper bound on the diameter of all orbital graphs. This is …
We give a description of infinite families of finite primitive permutation groups for which there is a uniform finite upper bound on the diameter of all orbital graphs. This is equivalent to describing families of finite permutation groups such that every ultraproduct of the family is primitive. A key result is that, in the almost simple case with socle of fixed Lie rank, apart from very specific cases, there is such a diameter bound. This is proved using recent results on the model theory of pseudofinite fields and difference fields.
By Gregory Cherlin and Ehud Hrushovski: 193 pp., £35.00/£17.95, isbn 0-691-11331-9/0-691-11332-7(P) (Princeton University Press, 2003).
By Gregory Cherlin and Ehud Hrushovski: 193 pp., £35.00/£17.95, isbn 0-691-11331-9/0-691-11332-7(P) (Princeton University Press, 2003).
Let Γ be the unique (up to isomorphism) countable graph with the following property: (*) Given any two finite disjoint subsets U and V of Γ , there exists a …
Let Γ be the unique (up to isomorphism) countable graph with the following property: (*) Given any two finite disjoint subsets U and V of Γ , there exists a vertex z ∈ Γ joined to every vertex in U and to none in V . Thus Γ is the countable, universal, homogeneous graph; also known as the random graph. In this paper, we shall study the reducts of Γ Here a reduct of Γ is defined to be a permutation group (G, Γ ) such that: (i) Aut( Γ ) ≤ G ; and (ii) G is a closed subgroup of Sym( Γ ). Equivalently, there exists a structure for some language L such that: (iii) has universe Γ; (iv) for each R ∈ L , is definable without parameters in Γ ; and (v) G = Aut( ).