math.LO

Motivated by the "composition theorems" of Chernikov-Hempel and Abd Aldaim-Conant-Terry we introduce $k$-trace definability between first order theories. Any theory which is $k$-trace definable in a NIP theory is $k$-NIP and any theory which is $2$-trace definable in a stable theory is $2$-NFOP. All known examples of $k$-NIP theories are $k$-trace definable in NIP theories. We show that for several of the main examples of $k$-NIP theories $T$ there is a NIP theory $T^*$ such that $T$ is the (unique up to a certain notion of equivalence) universal theory which is $k$-trace definable in $T^*$. For example the theory of Hilbert space is the universal theory which is $2$-trace definable in RCF, the theory of the generic class $k$ nilpotent Lie algebra over $\mathbb{F}_p$ is the universal theory which is $k$-trace definable in the theory of infinite $\mathbb{F}_p$-vector spaces, the theory of the generic $k$-hypergraph is the universal theory which is $k$-trace definable in the theory of a set with two elements, and the theory of Uryshon space is the universal theory which is $2$-trace definable in the theory of $(\mathbb{R}; +, <)$. We construct the universal theory $D_k(T)$ which is $k$-trace definable in an arbitrary theory $T$.

I investigate modal group theory for arbitrary homomorphisms. Possibility is interpreted by the existence of a group homomorphism out of the given group, so the semantics is governed by the possibility of collapse: elements may be identified, parameters may be killed, and new relations may hold in the target. I show that the modal language nevertheless expresses cyclic subgroup membership, subgroup generation by a fixed finite tuple, cyclicity, finite generation by a fixed number of elements, and torsion. I use these definability results to interpret arithmetic, and prove that, as sets of Goedel numbers, the homomorphic modal theory of finitely presented groups is computably isomorphic to true arithmetic. I also analyze propositional modal validities: sentential validities are exactly S5, the trivial group has exact parameter-validities S5, and uniformly prime-indivisible groups have exact parameter-validities S4.2.

I introduce modal group theory, in which we study the category of all groups, considering embeddability as providing a notion of modal possibility. Using HNN extensions and Britton's lemma, I demonstrate that the modal language of groups is more expressive than the first-order language of groups. I interpret the theory of true arithmetic in modal group theory, and show that, as sets of Goedel numbers, it is computably isomorphic to the modal theory of finitely presented groups. I answer an open question of Berger, Block, and Loewe by showing that the formulaic propositional modal validities of groups under embeddings are precisely S4.2. I also analyze sentential validities and worlds validating S5.

We view ultrametric spaces as two-sorted structures consisting of a set of points and of a linearly ordered set of distances. We call the appropriate notion of embeddings distance-carrying (dc for short). Those are obtained by combining isometries and linear order embeddings. We show that the class of all finite two-sorted ultrametric spaces with dc-embeddings is Fra\"iss\'e, and that the limit is the countable rational Urysohn ultrametric space $\mathbb{U}$. The space $\mathbb{U}$ is dc-universal for all countable ultrametric spaces, and its Cauchy completion $\overline{\mathbb{U}}$ is dc-universal for all separable ultrametric spaces, which is in contrast with the situation of classical ultrametric spaces and isometric embeddings, where no such universal space can exist. We study further properties of $\mathbb{U}$, of its variants, and of its automorphism group, which is richer than its group of isometries. In particular, we provide two types of tree representations of the two-sorted ultrametric spaces, discuss connections to valued fields, and characterize the automorphism group of $\mathbb{U}$ as the semidirect product of a group of order preserving bijections and a group of isometries. Furthermore, we show universality of $\operatorname{Aut}(\mathbb{U})$ and identify its universal minimal flow.