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

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

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

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

2^\kappa $2^\kappa$

\kappa $\kappa$

\kappa $\kappa$

\mathsf {Exp}(X)$\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$\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$\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)$\mathcal {K}(X)$ be the set of compact subsets of X ordered by inclusion. A map \phi :\mathcal {K}(X) \to \mathcal {K}(Y)$\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))$(X,\mathcal {K}(X)) \ge _T (Y,\mathcal {K}(Y))$, and write (X,\mathcal {K}(X)) =_T (Y,\mathcal {K}(Y))$(X,\mathcal {K}(X)) =_T (Y,\mathcal {K}(Y))$ if (X,\mathcal {K}(X)) \ge _T (Y,\mathcal {K}(Y))$(X,\mathcal {K}(X)) \ge _T (Y,\mathcal {K}(Y))$ and vice versa.

We investigate the initial structure of pairs (X,\mathcal {K}(X))$(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 $\sigma$-pseudocompact or for some separable metrizable M, we have \mathcal {K}(M) \ge _T (G,\mathcal {K}(G))$\mathcal {K}(M) \ge _T (G,\mathcal {K}(G))$.

For any n<\omega $n<\omega$ we construct an infinite (n+1)$(n+1)$-generated Heyting algebra whose n-generated subalgebras are of cardinality \leq m_n$\leq m_n$ for some positive integer m_n$m_n$. From this we conclude that for every n<\omega $n<\omega$ there exists a variety of Heyting algebras which contains an infinite (n+1)$(n+1)$-generated algebra, but which contains only finite n-generated algebras. For the case n=2$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$\Delta _0$-formula \varphi (x)$\varphi (x)$; the parameter is the size of \varphi $\varphi$. This parameterization focusses attention on instances where n is large compared to the size of \varphi $\varphi$. We show unconditionally that this problem does not belong to the parameterized analogue of \mathsf {AC}^0$\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$I\Delta _0$ proves the MRDP theorem in a certain weak sense.

Let K denote prefix-free Kolmogorov complexity, and let K^A$K^A$ denote it relative to an oracle A. We show that for any n, K^{\emptyset ^{(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$\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]$[0,1]$ is again normal iff X is countably metacompact. In a recent paper, Leiderman and Szeptycki studied \Delta $\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$L$ over the first uncountable cardinal for which the corresponding space X_{ L}$X_{ L}$ is not a \Delta $\Delta$-space, and asked whether there is a ZFC example of a ladder system L$L$ over some cardinal \kappa $\kappa$ for which X_{ L}$X_{ L}$ is not countably metacompact, in particular, not a \Delta $\Delta$-space. We prove that an affirmative answer holds for the cardinal \kappa =\operatorname {\mathrm {cf}}(\beth _{\omega +1})$\kappa =\operatorname {\mathrm {cf}}(\beth _{\omega +1})$. Assuming \beth _\omega =\aleph _\omega $\beth _\omega =\aleph _\omega$, we get an example at a much lower cardinal, namely \kappa =2^{2^{2^{\aleph _0}}}$\kappa =2^{2^{2^{\aleph _0}}}$, and our ladder system L is moreover \omega $\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 $\omega$-categorical counterexamples. These happen to be various \omega $\omega$-categorical Hrushovski constructions. Using a probabilistic independence theorem from Jahel and Tsankov, we show how simple \omega $\omega$-categorical structures where a formula forks over \emptyset $\emptyset$ if and only if it is universally measure zero must satisfy a stronger version of the independence theorem.

The axiom of dependent choice (\mathsf {DC}$\mathsf {DC}$) and the axiom of countable choice ({\mathsf {AC}}_\omega ${\mathsf {AC}}_\omega$) are two weak forms of the axiom of choice that can be stated for a specific set: \mathsf {DC} ( X )$\mathsf {DC} ( X )$ asserts that any total binary relation on X has an infinite chain, while {\mathsf {AC}}_\omega ( X )${\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 $\mathsf {DC} \Rightarrow {\mathsf {AC}}_\omega$. We study for which sets and under which hypotheses \mathsf {DC} ( X ) \Rightarrow {\mathsf {AC}}_\omega ( X )$\mathsf {DC} ( X ) \Rightarrow {\mathsf {AC}}_\omega ( X )$, and then we show it is consistent with \mathsf {ZF}$\mathsf {ZF}$ that there is a set A \subseteq \mathbb {R}$A \subseteq \mathbb {R}$ for which \mathsf {DC} ( A )$\mathsf {DC} ( A )$ holds, but {\mathsf {AC}}_\omega ( A )${\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}$\lambda <2^{\aleph _0}$. Let {\mathbf {K}}${\mathbf {K}}$ be an abstract elementary class with \lambda \geq {\operatorname {LS}}({\mathbf {K}})$\lambda \geq {\operatorname {LS}}({\mathbf {K}})$. Assume {\mathbf {K}}${\mathbf {K}}$ has amalgamation in \lambda $\lambda$, no maximal model in \lambda $\lambda$, and is stable in \lambda $\lambda$. If {\mathbf {K}}${\mathbf {K}}$ is (<\lambda ^+, \lambda )$(<\lambda ^+, \lambda )$-local, then {\mathbf {K}}${\mathbf {K}}$ has a model of cardinality \lambda ^{++}$\lambda ^{++}$.

The set theoretic assumption that \lambda <2^{\aleph _0}$\lambda <2^{\aleph _0}$ and model theoretic assumption of stability in \lambda $\lambda$ can be weakened to the model theoretic assumptions that |{\mathbf {S}}^{na}(M)|< 2^{\aleph _0}$|{\mathbf {S}}^{na}(M)|< 2^{\aleph _0}$ for every M \in {\mathbf {K}}_\lambda $M \in {\mathbf {K}}_\lambda$ and stability for \lambda $\lambda$-algebraic types in \lambda $\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$\mathbb {Q}_p$, then G^0 = G^{00}$G^0 = G^{00}$. As an application, definably amenable groups over \mathbb {Q}_p$\mathbb {Q}_p$ are open subgroups of algebraic groups, up to finite factors. We also prove that G^0 = G^{00}$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}$NTP_{2}$, strongness, NSOP_{1}$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}$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)_{-}$\operatorname {\mathrm {bdn}}(\text {"}x=x\text {"})=(\aleph _0)_{-}$.

In this paper we consider the classes of all continuous \mathcal {L}$\mathcal {L}$-(pre-)structures for a continuous first-order signature \mathcal {L}$\mathcal {L}$. We characterize the moduli of continuity for which the classes of finite, countable, or all continuous \mathcal {L}$\mathcal {L}$-(pre-)structures have the amalgamation property. We also characterize when Urysohn continuous \mathcal {L}$\mathcal {L}$-(pre)-structures exist, establish that certain classes of finite continuous \mathcal {L}$\mathcal {L}$-structures are countable Fraïssé classes, prove the coherent EPPA for these classes of finite continuous \mathcal {L}$\mathcal {L}$-structures, and show that actions by automorphisms on finite \mathcal {L}$\mathcal {L}$-structures also form a Fraïssé class. As consequences, we have that the automorphism group of the Urysohn continuous \mathcal {L}$\mathcal {L}$-structure is a universal Polish group and that Hall’s universal locally finite group is contained in the automorphism group of the Urysohn continuous \mathcal {L}$\mathcal {L}$-structure as a dense subgroup.

In the study of the arithmetic degrees the \omega \text {-REA}$\omega \text {-REA}$ sets play a role analogous to the role the r.e. degrees play in the study of the Turing degrees. However, much less is known about the arithmetic degrees and the role of the \omega \text {-REA}$\omega \text {-REA}$ sets in that structure than about the Turing degrees. Indeed, even basic questions such as the existence of an \omega \text {-REA}$\omega \text {-REA}$ set of minimal arithmetic degree are open. This paper makes progress on this question by demonstrating that some promising approaches inspired by the analogy with the r.e. sets fail to show that no \omega \text {-REA}$\omega \text {-REA}$ set is arithmetically minimal. Finally, it constructs a \prod ^0_{2}$\prod ^0_{2}$ singleton of minimal arithmetic degree. Not only is this a result of considerable interest in its own right, constructions of \prod ^0_{2}$\prod ^0_{2}$ singletons often pave the way for constructions of \omega \text {-REA}$\omega \text {-REA}$ sets with similar properties. Along the way, a number of interesting results relating arithmetic reducibility and rates of growth are established.

A partition is finitary if all its members are finite. For a set A, \mathscr {B}(A)$\mathscr {B}(A)$ denotes the set of all finitary partitions of A. It is shown consistent with \mathsf {ZF}$\mathsf {ZF}$ (without the axiom of choice) that there exist an infinite set A and a surjection from A onto \mathscr {B}(A)$\mathscr {B}(A)$. On the other hand, we prove in \mathsf {ZF}$\mathsf {ZF}$ some theorems concerning \mathscr {B}(A)$\mathscr {B}(A)$ for infinite sets A, among which are the following:

1. (1) If there is a finitary partition of A without singleton blocks, then there are no surjections from A onto \mathscr {B}(A)$\mathscr {B}(A)$ and no finite-to-one functions from \mathscr {B}(A)$\mathscr {B}(A)$ to A.

2. (2) For all n\in \omega $n\in \omega$, |A^n|<|\mathscr {B}(A)|$|A^n|<|\mathscr {B}(A)|$.

3. (3) |\mathscr {B}(A)|\neq |\mathrm {seq}(A)|$|\mathscr {B}(A)|\neq |\mathrm {seq}(A)|$, where \mathrm {seq}(A)$\mathrm {seq}(A)$ is the set of all finite sequences of elements of A.

Let \Omega $\Omega$ be a complex lattice which does not have complex multiplication and \wp =\wp _\Omega $\wp =\wp _\Omega$ the Weierstrass \wp $\wp$-function associated with it. Let D\subseteq \mathbb {C}$D\subseteq \mathbb {C}$ be a disc and I\subseteq \mathbb {R}$I\subseteq \mathbb {R}$ be a bounded closed interval such that I\cap \Omega =\varnothing $I\cap \Omega =\varnothing$. Let f:D\rightarrow \mathbb {C}$f:D\rightarrow \mathbb {C}$ be a function definable in (\overline {\mathbb {R}},\wp |_I)$(\overline {\mathbb {R}},\wp |_I)$. We show that if f is holomorphic on D then f is definable in \overline {\mathbb {R}}$\overline {\mathbb {R}}$. The proof of this result is an adaptation of the proof of Bianconi for the \mathbb {R}_{\exp }$\mathbb {R}_{\exp }$ case. We also give a characterization of lattices with complex multiplication in terms of definability and a nondefinability result for the modular j-function using similar methods.

Consider a variant of the usual story about the iterative conception of sets. As usual, at every stage, you find all the (bland) sets of objects which you found earlier. But you also find the result of tapping any earlier-found object with any magic wand (from a given stock of magic wands).

By varying the number and behaviour of the wands, we can flesh out this idea in many different ways. This paper's main Theorem is that any loosely constructive way of fleshing out this idea is synonymous with a ZF-like theory.

This Theorem has rich applications; it realizes John Conway's (1976) Mathematicians' Liberation Movement; and it connects with a lovely idea due to Alonzo Church (1974).

We study a version of the Craig interpolation theorem formulated in the framework of the theory of institutions. This formulation proved crucial in the development of a number of key results concerning foundations of software specification and formal development. We investigate preservation of interpolation properties under institution extensions by new models and sentences. We point out that some interpolation properties remain stable under such extensions, even if quite arbitrary new models and sentences are permitted. We give complete characterisations of such situations for institution extensions by new models, by new sentences, as well as by new models and sentences, respectively.