Towards a Ryll‐Nardzewski‐type theorem for weakly oligomorphic structures

A structure is called weakly oligomorphic if its endomorphism monoid has only finitely many invariant relations of every arity. The goal of this paper is to show that the notions of homomorphism‐homogeneity, and weak oligomorphy are not only completely analogous to the classical notions of homogeneity and oligomorphy, but are actually closely related. We first prove a Fraïssé‐type theorem for homomorphism‐homogeneous relational structures. We then show that the countable models of the theories of countable weakly oligomorphic structures are mutually homomorphism‐equivalent (we call first order theories with this property weakly ω‐categorical). Furthermore we show that every weakly oligomorphic homomorphism‐homogeneous structure contains (up to isomorphism) a unique homogeneous, homomorphism‐homogeneous core, to which it is homomorphism‐equivalent. As a consequence we obtain that every countable weakly oligomorphic structure is homomorphism‐equivalent to a finite or ω‐categorical structure. As a corollary we obtain a characterization of positive existential theories of weakly oligomorphic structures as the positive existential parts of ω‐categorical theories.     

Transitivity is neither hereditary nor finitely productive

We construct a transitive space that is the union of two subspaces homeomorphic to the (non-transitive) Kofner plane. Moreover, we show that the product of two transitive spaces need not be transitive. Finally, we observe that results of E.K. van Douwen establish that, under b = c, there exists a locally countable locally compact non-transitive zero-dimensional space. It follows that under b = c neither a locally transitive nor a compact space need be transitive.     

Countable dense homogeneous spaces under Martin’s axiom

We show that Martin’s axiom for countable partial orders implies the existence of a countable dense homogeneous Bernstein subset of the reals. Using Martin’s axiom we derive a characterization of the countable dense homogeneous spaces among the separable metric spaces of cardinality less thanc. Also, we show that Martin’s axiom implies the existence of a subset of the Cantor set which isλ-dense homogeneous for everyλ <c.     

Theories with only a finite number of existentially complete models

We construct, in particular, a countable universal theory with JEP which has exactly 2 non-isomorphic countable existentially complete models, and these two models can be either elementarily equivalent or inequivalent.     

Genericity for Mathias forcing over general Turing ideals

We construct a homogeneous subspace of 2^ω whose complement is dense in 2^ω and rigid. Using the same method, assuming Martin’s Axiom, we also construct a countable dense homogeneous subspace of 2^ω whose complement is dense in 2^ω and rigid.     

Countable infinite existentially closed models of universally axiomatizable theories

In the present article, we obtain a new criterion for amodel of a universally axiomatizable theory to be existentially closed. The notion of a maximal existential type is used in the proof and for investigating properties of countable infinite existentially closed structures. The notions of a prime and a homogeneous model, which are classical for the general model theory, are introduced for such structures. We study universal theories with the joint embedding property admitting a single countable infinite existentially closed model. We also construct, for every natural n, an example of a complete inductive theory with a countable infinite family of countable infinite models such that n of them are existentially closed and exactly two are homogeneous.     

On κ‐hereditary Sets and Consequences of the Axiom of Choice

We will prove that some so‐called union theorems (see [2]) are equivalent in ZF⁰ to statements about the transitive closure of relations. The special case of “bounded” union theorems dealing with κ‐hereditary sets yields equivalents to statements about the transitive closure of κ‐narrow relations. The instance κ = ω₁ (i. e., hereditarily countable sets) yields an equivalent to Howard‐Rubin's Form 172 (the transitive closure Tc(x) of every hereditarily countable set x is countable). In particular, the countable union theorem (Howard‐Rubin's Form 31) and, a fortiori, the axiom of countable choice imply Form 172.     

Super-Connectivity and Hyper-Connectivity of Vertex Transitive Bipartite Graphs

A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex. In this note, we proved that a vertex transitive bipartite graph is not super-connected if and only if it is isomorphic to the lexicographic product of a cycle C_n(n ≥ 6) by a null graph N_m. We also characterized non-hyper-connected vertex transitive bipartite graphs.     

Transitivity degrees of countable groups and acylindrical hyperbolicity

We prove that every countable acylindrically hyperbolic group admits a highly transitive action with finite kernel. This theorem uniformly generalizes many previously known results and allows us to answer a question of Garion and Glassner on the existence of highly transitive faithful actions of mapping class groups. It also implies that in various geometric and algebraic settings, the transitivity degree of an infinite group can only take two values, namely 1 and ∞. Here, by transitivity degree of a group we mean the supremum of transitivity degrees of its faithful permutation representations. Further, for any countable group G admitting a highly transitive faithful action, we prove the following dichotomy: Either G contains a normal subgroup isomorphic to the infinite alternating group or G resembles a free product from the model theoretic point of view. We apply this theorem to obtain new results about universal theory and mixed identities of acylindrically hyperbolic groups. Finally, we discuss some open problems.     

A Real Number Structure that is Effectively Categorical

On countable structures computability is usually introduced via numberings. For uncountable structures whose cardinality does not exceed the cardinality of the continuum the same can be done via representations. Which representations are appropriate for doing real number computations? We show that with respect to computable equivalence there is one and only one equivalence class of representations of the real numbers which make the basic operations and the infinitary normed limit operator computable. This characterizes the real numbers in terms of the theory of effective algebras or computable structures, and is reflected by observations made in real number computer arithmetic. Demanding computability of the normed limit operator turns out to be essential: the basic operations without the normed limit operator can be made computable by more than one class of representations. We also give further evidence for the well-known non-appropriateness of the representation to some base b by proving that strictly less functions are computable with respect to these representations than with respect to a standard representation of the real numbers. Furthermore we consider basic constructions of representations and the countable substructure consisting of the computable elements of a represented, possibly uncountable structure. For countable structures we compare effectivity with respect to a numbering and effectivity with respect to a representation. Special attention is paid to the countable structure of the computable real numbers.     

The classification of homomorphism homogeneous tournaments

The notion of homomorphism homogeneity was introduced by Cameron and Nešetřil as a natural generalization of the classical model-theoretic notion of homogeneity. A relational structure is called homomorphism homogeneous (HH) if every homomorphism between finite substructures extends to an endomorphism. It is called polymorphism homogeneous (PH) if every finite power of the structure is homomorphism homogeneous. Despite the similarity of the definitions, the HH and PH structures lead a life quite separate from the homogeneous structures. While the classification theory of homogeneous structure is dominated by Fraïssé-theory, other methods are needed for classifying HH and PH structures. In this paper we give a complete classification of HH countable tournaments (with loops allowed). We use this result in order to derive a classification of countable PH tournaments. The method of classification is designed to be useful also for other classes of relational structures. Our results extend previous research on the classification of finite HH and PH tournaments by Ilić, Mašulović, Nenadov, and the first author.     

Dimensions, matroids, and dense pairs of first-order structures

A structure M is pregeometric if the algebraic closure is a pregeometry in all structures elementarily equivalent to M. We define a generalisation: structures with an existential matroid. The main examples are superstable groups of Lascar U-rank a power of ω and d-minimal expansion of fields. Ultraproducts of pregeometric structures expanding an integral domain, while not pregeometric in general, do have a unique existential matroid.Generalising previous results by van den Dries, we define dense elementary pairs of structures expanding an integral domain and with an existential matroid, and we show that the corresponding theories have natural completions, whose models also have a unique existential matroid. We also extend the above result to dense tuples of structures.     

Partition properties of the dense local order and a colored version of Milliken’s theorem

We study finite dimensional partition properties of the countable homogeneous dense local order (a directed graph closely related to the order structure of the rationals). Some of our results use ideas borrowed from the partition calculus of the rationals and are obtained thanks to a strengthening of Milliken’s theorem on trees.     

Shadowing with chain transitivity

A transitive dynamical system is either sensitive or has a dense set of equicontinuity points [E. Akin, J. Auslander, K. Berg, When is a transitive map chaotic, in: Convergence in Ergodic Theory and Probability, Walter de Gruyter & Co., 1996, pp. 25-40]. We show that if a chain transitive system has shadowing property then it is either sensitive or all points are equicontinuous.     

Powerful digraphs

We introduce the concept of a powerful digraph and establish that a powerful digraph structure is included into the saturated structure of each nonprincipal powerful type p possessing the global pairwise intersection property and the similarity property for the theories of graph structures of type p and some of its first-order definable restrictions (all powerful types in the available theories with finitely many (> 1) pairwise nonisomorphic countable models have this property). We describe the structures of the transitive closures of the saturated powerful digraphs that occur in the models of theories with nonprincipal powerful 1-types provided that the number of nonprincipal 1-types is finite. We prove that a powerful digraph structure, considered in a model of a simple theory, induces an infinite weight, which implies that the powerful digraphs do not occur in the structures of the available classes of the simple theories (like the supersimple or finitely based theories) that do not contain theories with finitely many (> 1) countable models.     

Three types of inclusions of innately transitive permutation groups into wreath products in product action

A permutation group is innately transitive if it has a transitive minimal normal subgroup, and this subgroup is called a plinth. In this paper we study three special types of inclusions of innately transitive permutation groups in wreath products in product action. This is achieved by studying the natural Cartesian decomposition of the underlying set that corresponds to the product action of the wreath product. Previously we identified six classes of Cartesian decompositions that can be acted upon transitively by an innately transitive group with a non-abelian plinth. The inclusions studied in this paper correspond to three of the six classes. We find that in each case the isomorphism type of the acting group is restricted, and some interesting combinatorial structures are left invariant. We also give a fairly general construction of inclusions for each type.     

On Morse Conjecture for Flows on Closed Surfaces

Let M be a closed orientable surface and let ϕ be a C¹‐flow on M with set of singularities compact countable. In this paper, we prove the Morse conjecture for ϕ: if ϕ is topologically transitive then it is metrically transitive.     

The conjugacy problem for automorphism groups of countable homogeneous structures

We consider the conjugacy problem for the automorphism groups of a number of countable homogeneous structures. In each case we find the precise complexity of the conjugacy relation in the sense of Borel reducibility.     

Pairwise disjoint eight‐shaped curves in hybrid planes

We introduce a suitable notion of eight‐shaped curve in the product S × ? of a Suslin line S for the real line ?, and we prove that if S is dense in itself, then every collection of pairwise disjoint eight‐shaped curves in S × ? is countable. This parallels a folklore result which holds for the real plane. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Constructing continuum many countable, primitive, unbalanced digraphs

We construct continuum many non-isomorphic countable digraphs which are highly arc transitive, have finite out-valency and infinite in-valency, and whose automorphism groups are primitive.