Inspired by Adler’s idea on VC minimal theories [1], we introduce VC-minimal complexity. We show that for any $N\in \mathbb {N}^{>0}$, there is $k_N>0$ such that for any finite bipartite graph $(X,Y;E)$ with VC-minimal complexity $< N$, there exist $X'\subseteq X$, $Y'\subseteq Y$ with $|X'|\geq k_N |X|$, $|Y'|\geq k_N |Y|$ such that $X'\times Y' \subseteq E$ or $X'\times Y'\cap E=\emptyset $.

Let ${\mathbb K}$ be an algebraically bounded structure, and let T be its theory. If T is model complete, then the theory of ${\mathbb K}$ endowed with a derivation, denoted by $T^{\delta }$, has a model completion. Additionally, we prove that if the theory T is stable/NIP then the model completion of $T^{\delta }$ is also stable/NIP. Similar results hold for the theory with several derivations, either commuting or non-commuting.

In the first part of this paper, we consider several natural axioms in urelement set theory, including the Collection Principle, the Reflection Principle, the Dependent Choice scheme and its generalizations, as well as other axioms specifically concerning urelements. We prove that these axioms form a hierarchy over $\text {ZFCU}_{\text {R}}$ (ZFC with urelements formulated with Replacement) in terms of direct implication. The second part of the paper studies forcing over countable transitive models of $\text {ZFU}_{\text {R}}$. We propose a new definition of ${\mathbb P}$-names to address an issue with the existing approach. We then prove the fundamental theorem of forcing with urelements regarding axiom preservation. Moreover, we show that forcing can destroy and recover certain axioms within the previously established hierarchy. Finally, we demonstrate how ground model definability may fail when the ground model contains a proper class of urelements.

We characterize Borel line graphs in terms of 10 forbidden induced subgraphs, namely the nine finite graphs from the classical result of Beineke together with a 10th infinite graph associated with the equivalence relation $\mathbb {E}_0$ on the Cantor space. As a corollary, we prove a partial converse to the Feldman–Moore theorem, which allows us to characterize all locally countable Borel line graphs in terms of their Borel chromatic numbers.

We generalize Hrushovski’s group configuration theorem to the case where the type of the configuration is generically stable, without assuming tameness of the ambient theory. The properties of generically stable types, which we recall in the second section, enable us to adapt the proof known in the stable context.

All spaces are assumed to be Tychonoff. Given a realcompact space X, we denote by $\mathsf {Exp}(X)$ the smallest infinite cardinal $\kappa $ such that X is homeomorphic to a closed subspace of $\mathbb {R}^\kappa $. Our main result shows that, given a cardinal $\kappa $, the following conditions are equivalent:

• • There exists a countable crowded space X such that $\mathsf {Exp}(X)=\kappa $.

• • $\mathfrak {p}\leq \kappa \leq \mathfrak {c}$.

$\mathfrak {d}\leq \kappa \leq \mathfrak {c}$

$2^\kappa $

$\kappa $

$\kappa $

$\mathsf {Exp}(X)$

It is shown that every model of NF admits a permutation model containing an internal automorphism.

We show that there exists a recursive coloring function c such that any $\Pi ^0_3$ set is not a solution to c for Hindman’s theorem. We also show that there exists a recursive coloring function c such that any $\Delta ^0_3$ set is not a solution to c for Hindman’s theorem restricted to sums of at most three numbers.

For a space X let $\mathcal {K}(X)$ be the set of compact subsets of X ordered by inclusion. A map $\phi :\mathcal {K}(X) \to \mathcal {K}(Y)$ is a relative Tukey quotient if it carries compact covers to compact covers. When there is such a Tukey quotient write $(X,\mathcal {K}(X)) \ge _T (Y,\mathcal {K}(Y))$, and write $(X,\mathcal {K}(X)) =_T (Y,\mathcal {K}(Y))$ if $(X,\mathcal {K}(X)) \ge _T (Y,\mathcal {K}(Y))$ and vice versa.

We investigate the initial structure of pairs $(X,\mathcal {K}(X))$ under the relative Tukey order, focussing on the case of separable metrizable spaces. Connections are made to Menger spaces.

Applications are given demonstrating the diversity of free topological groups, and related free objects, over separable metrizable spaces. It is shown a topological group G has the countable chain condition if it is either $\sigma $-pseudocompact or for some separable metrizable M, we have $\mathcal {K}(M) \ge _T (G,\mathcal {K}(G))$.

For any $n<\omega $ we construct an infinite $(n+1)$-generated Heyting algebra whose n-generated subalgebras are of cardinality $\leq m_n$ for some positive integer $m_n$. From this we conclude that for every $n<\omega $ there exists a variety of Heyting algebras which contains an infinite $(n+1)$-generated algebra, but which contains only finite n-generated algebras. For the case $n=2$ this provides a negative answer to a question posed by G. Bezhanishvili and R. Grigolia in [4].

We study the parameterized complexity of the problem to decide whether a given natural number n satisfies a given $\Delta _0$-formula $\varphi (x)$; the parameter is the size of $\varphi $. This parameterization focusses attention on instances where n is large compared to the size of $\varphi $. We show unconditionally that this problem does not belong to the parameterized analogue of $\mathsf {AC}^0$. From this we derive that certain natural upper bounds on the complexity of our parameterized problem imply certain separations of classical complexity classes. This connection is obtained via an analysis of a parameterized halting problem. Some of these upper bounds follow assuming that $I\Delta _0$ proves the MRDP theorem in a certain weak sense.

We give explicit formulas witnessing IP, IP$_{\!n}$, or TP2 in fields with Artin–Schreier extensions. We use them to control p-extensions of mixed characteristic henselian valued fields, allowing us most notably to generalize to the NIP$_{\!n}$ context one way of Anscombe–Jahnke’s classification of NIP henselian valued fields. As a corollary, we obtain that NIP$_{\!n}$ henselian valued fields with NIP residue field are NIP. We also discuss tameness results for NTP2 henselian valued fields.

Let K denote prefix-free Kolmogorov complexity, and let $K^A$ denote it relative to an oracle A. We show that for any n, $K^{\emptyset ^{(n)}}$ is definable purely in terms of the unrelativized notion K. It was already known that 2-randomness is definable in terms of K (and plain complexity C) as those reals which infinitely often have maximal complexity. We can use our characterization to show that n-randomness is definable purely in terms of K. To do this we extend a certain “limsup” formula from the literature, and apply Symmetry of Information. This extension entails a novel use of semilow sets, and a more precise analysis of the complexity of $\Delta _2^0$ sets of minimal descriptions.

The property of countable metacompactness of a topological space gets its importance from Dowker’s 1951 theorem that the product of a normal space X with the unit interval $[0,1]$ is again normal iff X is countably metacompact. In a recent paper, Leiderman and Szeptycki studied $\Delta $-spaces, which is a superclass of the class of countably metacompact spaces. They proved that a single Cohen real introduces a ladder system $ L$ over the first uncountable cardinal for which the corresponding space $X_{ L}$ is not a $\Delta $-space, and asked whether there is a ZFC example of a ladder system $ L$ over some cardinal $\kappa $ for which $X_{ L}$ is not countably metacompact, in particular, not a $\Delta $-space. We prove that an affirmative answer holds for the cardinal $\kappa =\operatorname {\mathrm {cf}}(\beth _{\omega +1})$. Assuming $\beth _\omega =\aleph _\omega $, we get an example at a much lower cardinal, namely $\kappa =2^{2^{2^{\aleph _0}}}$, and our ladder system L is moreover $\omega $-bounded.

A recent article of Chernikov, Hrushovski, Kruckman, Krupinski, Moconja, Pillay, and Ramsey finds the first examples of simple structures with formulas which do not fork over the empty set but are universally measure zero. In this article we give the first known simple $\omega $-categorical counterexamples. These happen to be various $\omega $-categorical Hrushovski constructions. Using a probabilistic independence theorem from Jahel and Tsankov, we show how simple $\omega $-categorical structures where a formula forks over $\emptyset $ if and only if it is universally measure zero must satisfy a stronger version of the independence theorem.

We investigate the statement “all automorphisms of ${\mathcal {P}}(\lambda )/[\lambda ]^{<\lambda }$ are trivial.” We show that MA implies the statement for regular uncountable $\lambda <2^{\aleph _0}$, that the statement is false for measurable $\lambda $ if $2^\lambda =\lambda ^+$, and that for “densely trivial” it can be forced (together with $2^\lambda =\lambda ^{++}$) for inaccessible $\lambda $.

The axiom of dependent choice ($\mathsf {DC}$) and the axiom of countable choice (${\mathsf {AC}}_\omega $) are two weak forms of the axiom of choice that can be stated for a specific set: $\mathsf {DC} ( X )$ asserts that any total binary relation on X has an infinite chain, while ${\mathsf {AC}}_\omega ( X )$ asserts that any countable collection of nonempty subsets of X has a choice function. It is well-known that $\mathsf {DC} \Rightarrow {\mathsf {AC}}_\omega $. We study for which sets and under which hypotheses $\mathsf {DC} ( X ) \Rightarrow {\mathsf {AC}}_\omega ( X )$, and then we show it is consistent with $\mathsf {ZF}$ that there is a set $A \subseteq \mathbb {R}$ for which $\mathsf {DC} ( A )$ holds, but ${\mathsf {AC}}_\omega ( A )$ fails.

There are many results in the literature where superstablity-like independence notions, without any categoricity assumptions, have been used to show the existence of larger models. In this paper we show that stability is enough to construct larger models for small cardinals assuming a mild locality condition for Galois types.Theorem 0.1.

Suppose $\lambda <2^{\aleph _0}$. Let ${\mathbf {K}}$ be an abstract elementary class with $\lambda \geq {\operatorname {LS}}({\mathbf {K}})$. Assume ${\mathbf {K}}$ has amalgamation in $\lambda $, no maximal model in $\lambda $, and is stable in $\lambda $. If ${\mathbf {K}}$ is $(<\lambda ^+, \lambda )$-local, then ${\mathbf {K}}$ has a model of cardinality $\lambda ^{++}$.

The set theoretic assumption that $\lambda <2^{\aleph _0}$ and model theoretic assumption of stability in $\lambda $ can be weakened to the model theoretic assumptions that $|{\mathbf {S}}^{na}(M)|< 2^{\aleph _0}$ for every $M \in {\mathbf {K}}_\lambda $ and stability for $\lambda $-algebraic types in $\lambda $. This is a significant improvement of Theorem 0.1, as the result holds on some unstable abstract elementary classes.

We generalize two of our previous results on abelian definable groups in p-adically closed fields [12, 13] to the non-abelian case. First, we show that if G is a definable group that is not definably compact, then G has a one-dimensional definable subgroup which is not definably compact. This is a p-adic analogue of the Peterzil–Steinhorn theorem for o-minimal theories [16]. Second, we show that if G is a group definable over the standard model $\mathbb {Q}_p$, then $G^0 = G^{00}$. As an application, definably amenable groups over $\mathbb {Q}_p$ are open subgroups of algebraic groups, up to finite factors. We also prove that $G^0 = G^{00}$ when G is a definable subgroup of a linear algebraic group, over any model.

As a continuation of ideas initiated in [19], we study bi-colored (generic) expansions of geometric theories in the style of the Fraïssé–Hrushovski construction method. Here we examine that the properties $NTP_{2}$, strongness, $NSOP_{1}$, and simplicity can be transferred to the expansions. As a consequence, while the corresponding bi-colored expansion of a red non-principal ultraproduct of p-adic fields is $NTP_{2}$, the expansion of algebraically closed fields with generic automorphism is a simple theory. Furthermore, these theories are strong with $\operatorname {\mathrm {bdn}}(\text {"}x=x\text {"})=(\aleph _0)_{-}$.