Papers

We continue the study of the Menger and Rothberger games on lattices carried out in "Pointless proofs of the Menger and Rothberger games" (Topology Appl. 300 (2021), 107774). This time, we extend the earlier results by dropping some hypotheses that turned out to be unnecessary, and use Stone duality to recover known game characterizations for dense open families. We also give a formulation of $\mathsf U_{\mathrm{fin}}$ for partially ordered sets and prove its game characterization without any lattice assumption. Finally, almost disjoint families give complete distributive lattices on which the selection principles and the corresponding games differ. Dias's results give the lower bounds $\operatorname{cov}(\mathcal M)$ and $\mathfrak d$ for the least sizes of such counterexamples.

We discuss in detail Neutral Measures, which are measures which believably generate any real in Cantor space. We intuitively build up the classical notions of randomness, and show that neutral measures do exist, using the language of continuous semimeasures. Finally, we construct some specific randomness tests which allow us to enforce de- sirable properties on neutral measures. As an application, we show the existence of Gibbs measures for a large class of finite range Hamilto- nians on lattice models, and establish their relationship with neutral measures.

We study combinatorial properties of translations of meager and closed sets of measure zero. We discuss constellations of Borel conjectures for related classes of small sets and show that there are no uncountable null-additive sets in the Miller model. We also study cardinal invariants of those classes. In particular, we investigate the cardinal invariants of $\sigma$-ideals $\mathcal{H}_{F}$ related to meager-additive sets. We obtain a new characterization of additivity of meager ideal and answer some questions of Cardona. We also show that $\mathrm{non}(\mathcal{E}^{*})$, that is equal to the translation version of the covering number of the ideal $\mathcal{E}$, is close to the cardinal invariant related to the Laver property. This strengthens a result of Bartoszyński and Judah and a result of Elekes and Steprāns. Finally, we show that every $\mathcal{E}$-Luzin set is in $\mathcal{E}^{*}$.

We confirm Vaught's conjecture for each partial order ${\mathbb X}=\sum _{{\mathbb I}}\prod _{j<m_i}{\mathbb X}_{i,j}$ from the closure $\langle \langle {\mathcal C}^{\rm rt}\rangle _\Pi\rangle _\Sigma$ of the class ${\mathcal C}^{\rm rt}$ of rooted trees under finite direct products and lexicographic sums. In addition, (a) ${\mathcal T}:=\mathop{\rm Th}\nolimits ({\mathbb X})$ is $\omega $-categorical iff all the theories ${\mathcal T}_{i,j}:=\mathop{\rm Th}\nolimits ({\mathbb X}_{i,j})$ are $\omega $-categorical; (b) ${\mathcal T}$ satisfies VC$^\sharp$ (that is, $I({\mathcal T})\in \{1,{\mathfrak{c}}\}$), if VC$^\sharp$ holds for all ${\mathcal T}_{i,j}$. If ${\mathbb X}\in \langle \langle {\mathcal C}^{\rm rt}_{\rm fa}\rangle _\Pi\rangle _\Sigma$, where ${\mathcal C}^{\rm rt}_{\rm fa}$ is the class of finitely axiomatizable rooted trees, then (c) ${\mathcal T}$ is finitely axiomatizable and (d) ${\mathbb Y}\in \mathop{\rm Mod}\nolimits ({\mathcal T})$ iff ${\mathbb Y} \cong \sum _{{\mathbb I}}\prod _{j<m_i}{\mathbb Y}_{i,j}$, where ${\mathbb Y}_{i,j}\in \mathop{\rm Mod}\nolimits ({\mathcal T}_{i,j})$, for all indices. As a by-product we prove that (e) For each $n$ the class ${\mathcal C} _n$ of partial orders isomorphic to a direct product of $n$ rooted trees of size $>1$ is first-order definable; (f) Each $\omega $-categorical partial order from the class $\langle \langle {\mathcal C}^{\rm rt}_{\rm fb}\rangle _\Pi\rangle _\Sigma$, where ${\mathcal C}^{\rm rt}_{\rm fb}$ is the class of finite-branching rooted trees, is finitely axiomatizable. Statement (f) is related to the results of Rosenstein (for the class of linear orders) and Schmerl (for the class of partial orders of finite width).

A class of models which does not require additional operators on the language of classical sentential calculi to capture some notion of necessity, possibility, and impossibility is introduced and investigated.

A connected skew brace of finite Morley rank is left nilpotent (resp. weakly soluble) whenever the additive and multiplicative groups are nilpotent (resp. are soluble and the left chief length is at most 3).

In this paper, we prove that $\mathbb{Z}$ is first-order definable in the ring of integers $\mathbb{Z}^{\text{ab}}$ of the maximal abelian extension $\mathbb{Q}^{\text{ab}}$ of $\mathbb{Q}$, which implies that the first-order theory of $\mathbb{Z}^{\text{ab}}$ is undecidable. More generally, writing $i = \sqrt{-1}$ and $\mathbb{Q}^{\text{tr}}$ for the field of all totally real numbers, we prove new definability and undecidability results for rings of integers of subfields of $\mathbb{Q}^{\text{tr}}(i)$, focusing especially on fields which contain infinitely many roots of unity. The key ingredient for these results is that there is a parameter-free positive-existential formula which defines the roots of unity $\mu(\mathcal{O}_L)$ inside $\mathcal{O}_L$ for every field $L\subseteq \mathbb{Q}^{\text{tr}}(i)$.

We extend Fine's selection method to the setting of intuitionistic modal logic and use it to provide a model-theoretic proof that Fischer Servi-style intuitionistic $\sf K4$ has the finite model property.

We prove that every bounded-to-one action of a finitely generated commutative monoid has asymptotic dimension at most the torsion-free rank of its group completion, with control uniform for a fixed monoid, generating set, and generator fiber bound. The estimate is sharp. Together with the equality of classical and Borel asymptotic dimensions for these actions, it gives the sharp Borel rank bound and recovers hyperfiniteness for bounded-to-one Borel actions of countable commutative monoids.

We will use consistency properties to characterize strongly compact cardinals, first showing an adequate Model Existence Theorem for larger fragments.

Inductive definitions are an important form of knowledge in mathematics and computer science. Two common techniques to prove theorems about inductive definitions are the principle of mathematical induction and the principle of infinite descent. To formalize these principles, Brotherston and Simpson introduced the sequent calculus proof systems LKID, for mathematical induction, and LKID{\omega} and CLKID{\omega} , for infinite descent. LKID{\omega} is an infinitary system, in which proofs are infinite trees, and CLKID{\omega} a cyclic system, in which proofs are finite graphs. However, these calculi restrict to monotone definitions, while inductive definitions are generally non-monotone. The logic FO(ID) extends classical first-order logic with non-monotone inductive definitions. In earlier work, we provided a formalization of the principle of mathematical induction for non-monotone definitions by extending LKID to a sequent calculus SCFO(ID) for FO(ID). In this paper, we provide a formalization of the principle of infinite descent for non-monotone definitions by extending LKID{\omega} and CLKID{\omega} to sequent calculi SCFO(ID)-inf resp. SCFO(ID)-cyc for FO(ID). Furthermore, we extend several proof-theoretic results for LKID{\omega} and CLKID{\omega} to SCFO(ID)-inf and SCFO(ID)-cyc regarding soundness, completeness, cut-elimination and the relation with SCFO(ID).

Dixmier asked in 1967 whether the spectra of simple separable non-type-I $C^*$-algebras all have the same Borel structure. We solve the formulation using ordinary isomorphisms of quotient Borel $\sigma$-algebras by proving that its universal assertion is independent of ZFC, relative to the consistency of ZFC. Under the continuum hypothesis, all separable non-type-I spectra are measurably isomorphic, without simplicity or unitality assumptions. In the model obtained by iterating Sacks forcing for $\omega_2$ stages with countable supports over a GCH ground model, a fixed simple unital universal spectrum is not measurably isomorphic to the CAR spectrum. Neither consistency direction requires a large cardinal. The Borel-definable formulation, which requires isomorphisms to admit Borel lifts between irreducible representations, has a negative answer in ZFC. For the CAR algebra $A$ and a simple separable exact crossed product $B$ associated to $\mathrm{SL}_3(\mathbb{Z})$, there is no Borel-definable injection $\widehat B\to\widehat A$. Nevertheless, all separable nuclear non-type-I spectra are Borel-definably isomorphic. We also determine the answer under several choiceless hypotheses. The axiom of determinacy together with dependent choice gives a stronger negative conclusion: the spectrum of $B$ does not even inject as a set into the spectrum of $A$. The symmetric Solovay model gives the same conclusion. Over ZF, a wellordering of the reals of order type $\omega_1$ suffices for a positive answer. The finite-permutation Feferman–Levy model gives another positive answer for the full sigma-generated Borel structures. These comparisons concern the quotient structures themselves, without measure completion.

In their studies of pathologies in recursion categories, Montagna (1989) and Di Paola–Montagna (1991) introduce the algebraic systems $S'$ and $S'_T$, respectively, and claim that they are categories. We show that the proposed composition is not independent of the choice of representatives. For every consistent recursively enumerable extension $T$ of Peano arithmetic ($\mathrm{PA}$), we exhibit two unary programs whose partial functions are provably equal in $T$, separately at each standard input. Composing each after a program that searches for a $T$-proof of contradiction and returns its code yields programs that are not equivalent in this sense. An alternative proof uses the productivity of the complement of the diagonal halting set. Montagna's $S'$ is the case $T=\mathrm{PA}$. More generally, for consistent $T\supseteq\mathrm{PA}$, pointwise provable equality is a composition congruence exactly when $T$ proves every true $\Pi^0_1$ sentence, in which case it is extensional equality. This completeness condition fails for every consistent recursively enumerable $T\supseteq\mathrm{PA}$ by Gödel's second incompleteness theorem. For every extension $T\supseteq\mathrm{PA}$, the least composition congruence containing pointwise provable equality is extensional equality if $T$ is $\Sigma^0_1$-sound and the universal relation otherwise.

Assuming the nonexistence of uncountable measurable cardinals, we construct an $\mathbb F_2$-algebra and a covering class of right modules which is not closed under colimits of countable chains. This gives a counterexample to Enochs' conjecture under $V=L$.

We study the (Haar) measure of verbal sets in profinite groups, and especially in free profinite groups. Relating the measure of a verbal set with the width of the corresponding word, we find verbal sets of positive measure different from one. We prove a sufficient condition for the measure of a verbal set to be zero in a free profinite group of finite rank, from which we deduce that certain existentially definable sets in free profinite groups of finite rank can only have measure zero or one. Finally, we compute the measure of definable sets in torsion-free finitely generated abelian groups.

We characterise exacting, rank-Berkeley, Berkeley, and club Berkeley cardinals by compactness properties of logics and, equivalently, by compactness properties of certain topological spaces. This raises the strength known to be obtainable by statements about compactness into the realm of choiceless large cardinal axioms, the strongest known statements in terms of consistency strength. Moreover, it shows that compactness assumptions can directly violate the axiom of choice and the axiom $V=\text{HOD}$.

Reverse mathematics is a branch of mathematical logic dedicated to determining the minimal set existence principles necessary and sufficient to derive ordinary mathematical theorems about concrete structures like the real line. Since the mid-1970s, reverse mathematics has developed a systematic classification of the strength of theorems in areas of mathematics ranging from real and complex analysis to infinitary combinatorics. This essay will place reverse mathematics in its historical and philosophical context, and reveal its relevance to central issues in the philosophy of mathematics, from the foundational programmes of Hilbert and Brouwer to contemporary debates about realism, determinacy, and applicability of mathematics. In doing so, it will discuss the role of computability theory in measuring the strength of set existence principles, as well as related questions about idealisation when these principles are applied in the physical sciences and in philosophy.

We study the finite spectra of the syllogistic logic with cardinality comparisons $S^\dagger(card)$. Since the language does not contain conjunction at the sentence level, we consider the spectrum of a theory $\Gamma$, namely the set of positive integers $n$ for which $\Gamma$ is satisfiable in an $n$-element model. We give a complete classification of these spectra: besides the empty set, every $S^\dagger(card)$-spectrum is either an eventual tail of the positive integers or an eventual tail of the positive even integers. We then consider the extension of $S^\dagger(card)$ by Boolean connectives at the sentence level and show that the collection of its spectra forms the topology generated by the spectra of the original language.

Gödel-Löb provability logic $\GL$ is a propositional modal system that on one hand enjoys completeness with respect to conversely well-founded Kripke frames and on the other hand captures all modal principles about $\PA$-provability that are provable in $\PA$ itself. In the present paper we carry out an initial investigation into the question of what the infinitary counterpart of $\GL$ is. We develop a non-well-founded deep inference proof system $\dgla$ for the modal language with at most countably infinite conjunctions and disjunctions. We show that the calculus is sound and complete for well-founded transitive Kripke frames. Using Kripke-Platek set theory we develop an interpretation of the infinitary modal language in terms of infinitary provability over admissible sets. Then we show that a natural Hilber-style variant of infinitary $\GL$ is sound for this interpretation. We leave open, however, the question if $\dgla$ proves any additional theorems in comparison with the Hilbert-style calculus. Nevertheless, under certain conditions we do show that the infinitary provability logic arising from certain admissible sets lies between the set of theorems of the Hilbert-style calculus and the non-well-founded deep inference system.

A key motivation for Heyting's intuitionistic logic was to gain a formal notion of Brouwer's idea of mathematics as a "construction of the mind". One might thus argue that Heyting's Calculus should also correspond to a notion of provability. Inspired by this idea, Gödel formalised this connection via an embedding into a modal calculus, which is now known as the modal logic S4. While in his original publication, he only proved soundness for the embedding from intuitionistic propositional logic into S4, the converse was proved fifteen years later by McKinsey and Tarski. Although, it was later discovered that Gödel also had obtained a proof of the faithfulness of his embedding in unpublished notes in 1941. Rasioa and Sikorski later extended Gödel's embedding to first-order intuitionistic logic. In 1954, Maehara independently obtained the same results using proof-theoretic methods, even extending the embedding to one from intuitionistic first-order logic into intuitionistic first-order modal logic. This document presents a faithful English translation of Maehara's 1954 paper.

We prove that the first-order theory of nonabelian free groups does not admit a model companion.

We uniformly generalize Goodstein's theorem (Goodstein 1944) and Cichon's independence proof (Cichon 1983) via the concept of maximality quotients.

We establish the full version of a conjecture of Guth and Zahl, giving a lower bound for the volume of a semialgebraic set that has a large intersection with a collection of $\delta$-separated $\delta$-tubes. Our proof uses o-minimal methods to simplify the proof of Katz and Rogers, who proved the conjecture up to a small factor. We also establish that the constants depend polynomially on the complexity of the semialgebraic set, and more generally in the #o-minimal setting.

In dynamic epistemic logic, the four notions of success, self-refutation, true lies, and impossible lies have been discussed in the context of public announcements. In this paper, we introduce eventual and strong eventual versions of these notions, as well as their transfinite versions, which allow transfinite iteration of announcements. We also introduce the notions of always informativeness when true or false. For example, a formula is eventually self-refuting if, whenever initially true, it eventually becomes false at some finite stage under iterated announcements, and strong eventual self-refutation further requires the formula to remain false at all sufficiently late stages. There are two main results. The first result gives the relationship among strong eventual notions, eventual notions, and several other conditions including conditions on the limit of the truth values of the announced formula, the uniform bound condition, and the fixed-point views of the Moore sentence and the self-fulfilling sentence. The second result gives the relationship among finite and transfinite versions of the eventual and strong eventual notions and the fixed-point views.

We introduce several Ramsey-theoretic properties of 0-dimensional ambits and obtain their dynamical characterizations. In consequence, we obtain Ramsey-theoretic criteria for triviality and for profiniteness of some important invariants (in particular, of the Ellis groups) of the ambits in question. This yields a criterion for the structural property that each distal minimal factor of the given ambit is a profinite flow. Another result is a criterion for metrizability of the minimal left ideals in the Ellis semigroup. Then we study three specializations of the above abstract context: to first order theories, to definable groups, and to the classical Kechris-Pestov-Todorčević theory, recovering known and obtaining new results in each of these contexts.

We obtain a strong decomposition theorem for invariant global types in a monadically NIP theory. From this, we prove that if an $n$-type $tp(\bar{a}/MC)$ does not fork over $M$ then $\bar{a}=(\bar{f},\bar{d})$ where $tp(\bar{d}/MC)$ is $M$-definable and $tp(\bar{f}/MC\bar{d})$ is finitely satisfied in $M$. Over arbitrary base sets $B$, we prove that an $n$-type $tp(\bar{a}/BC)$ does not fork over $B$ if and only if $tp(a_i/BC)$ does not fork over $B$ for each singleton $a_i\in\bar{a}$. We show that monadically NIP theories satisfy density of definable types among non-forking extensions.

In this paper, we determine the precise asymptotics of the number of parts of stable regularity equipartitions in terms of the Littlestone dimension: every graph $G$ of Littlestone dimension $\operatorname{Lit}(G)\leq\ell$ has a regular equipartition into excellent sets with $(1 + o_{\epsilon\to 0,\ell}(1))\cdot\epsilon^{-\ell-1}$ parts and in the other direction, for every $\ell\in\mathbb{N}_+$, there is an infinite family of graphs, all of Littlestone dimension $\ell$, whose equipartitions into good sets must have size at least $(1 + o_{\epsilon\to 0,\ell}(1))\cdot\epsilon^{-\ell-1}$. Dropping the equitability condition, we determine the asymptotics of non-equitable partitions up to a multiplicative $\log(1/\epsilon)$: every graph $G$ with $\operatorname{Lit}(G)\leq\ell$ has a regular partition into excellent sets with $(1 + o_{\epsilon\to 0,\ell}(1))\cdot\epsilon^{-\ell}\cdot\ln(1/\epsilon)$ parts and in the other direction, for every $\ell\in\mathbb{N}_+$, there is an infinite family of graphs, all of Littlestone dimension $\ell$, whose partitions into good sets must have size at least $(1 + o_{\epsilon\to 0,\ell}(1))\cdot\epsilon^{-\ell}$. We also show that such partition can be obtained algorithmically efficiently in an approximation scheme fashion: replacing the $o_{\epsilon\to 0,\ell}(1)$ term above by a constant $c > 0$, we obtain randomized $O_{c,\epsilon,\ell}(n\cdot\log(n))$-time algorithms for partitions/equipartitions into good sets, a deterministic $O_{c,\epsilon,\ell}(n^2)$-time algorithm for partitions into good sets, a deterministic $O_{c,\epsilon,\ell}(n^6)$-time algorithm for equipartitions into good sets, a deterministic $O_{c,\ell,\epsilon}(1)\cdot n^{O(\ell\cdot 2^{2\cdot\ell+4})}$-time algorithm for partitions/equipartitions into excellent sets, and $O_{c,\epsilon,\ell}(\log(n+1))$-space algorithms for partitions/equipartitions into good/excellent sets.

We reconsider the theory of probabilistic formal languages generated by n-gram models and by probabilistic context-free grammars (PCFGs). The expected hierarchy of probabilistic grammars is established by proving that every probabilistic language generated by an n-gram model is also generated by some PCFG, while some probabilistic languages generated by PCFGs cannot be generated by any $n$-gram model. We introduce the notion of fully connected PCFGs, namely PCFGs in Chomsky normal form where every production rule only involving non-terminals has non-zero probability. Our main result shows that any probabilistic language generated by an $n$-gram model differs from any probabilistic language generated by a fully connected PCFG. Therefore, the class of probabilistic languages generated by $n$-gram models is not a subset of the class generated by fully connected PCFGs.

We study Borel-Tukey morphisms between almost-homogeneity relations. For finite $r,s\ge1$ and $m,n\ge2$, we give the complete one-stage classification: $\mathbf{Hom}^r_m\to_{\mathrm{BT}}\mathbf{Hom}^s_n$ holds exactly when $r>s$, or when $r=s$ and $m\ge n$. Our main result is that binary triple homogeneity requires exactly three sequential binary pair stages: $\mathbf{Hom}^2_2;\mathbf{Hom}^2_2;\mathbf{Hom}^2_2\longrightarrow_{\mathrm{BT}}\mathbf{Hom}^3_2$ and $\mathbf{Hom}^2_2;\mathbf{Hom}^2_2\not\longrightarrow_{\mathrm{BT}}\mathbf{Hom}^3_2$. We also construct Borel morphisms $\mathbf{Hom}^2_2;\mathbf{Hom}^2_3\longrightarrow_{\mathrm{BT}}\mathbf{Hom}^3_2$ and $\mathbf{Hom}^2_2;\mathbf{Hom}^2_2\longrightarrow_{\mathrm{BT}}\mathbf{Hom}^2_k$ for every finite positive $k$.

We use stationary common-neighborhood properties to study highly connected Ramsey relations and partition hypotheses. For weakly compact $\kappa$, $\operatorname{Coll}(\omega_1,{<}\kappa)$ forces $\omega_2\to_{\mathrm{hc},<5}(\omega_2)^2_\omega$ and $\operatorname{PH}_1(\omega_2)$. If $\kappa$ is $T^{\kappa^+}_{\omega_1}$-Ramsey, the same collapse forces that every countable coloring of $[\omega_2]^2$ has a stationary set $X\subseteq\omega_2$ and a color $i$ such that every finite subset of $X$ has stationarily many color-$i$ common neighbors in $X$. From one weakly compact cardinal, we obtain a model of the ${<}5$-edge relation at $\omega_3$ and $\operatorname{PH}_1(\omega_3)$, in which $\check H^2(\omega_3,A_d)\ne0$ for every nontrivial abelian group $A$. This separates $\operatorname{PH}_1(\omega_3)$ from $\operatorname{PH}_2(\omega_3)$, with the exact consistency strength of one weakly compact cardinal. We also show that $\operatorname{PH}_1(\omega_2\times\omega_5)$ is equiconsistent with two weakly compact cardinals.