Papers

Descriptive set theorists often refer to elements of the Baire space, $\mathcal{N} = {}^\omega\omega$, as “reals.” In this expository article, we present mathematical justification for this practice and highlight the advantages of working with $\mathcal{N}$ over $\mathbb{R}$ in the context of descriptive set theory.

In this note, we prove a stronger version of the Kővári-Sós-Turán theorem for partition-wise $k$-stable $r$-hypergraphs. More precisely, we show that for every $k,r\in\mathbb{N}_{\geq 2}$ there is $\eta=\eta(r,k)>0$ such that if $H=(V;E)$ is a partition-wise $k$-stable $r$-uniform $K^{(r)}_{t,\ldots,t}$-free hypergraph with $|V|=n$, then $|E| = O_{r,k,t}(n^{r-\eta})$. Crucially, $\eta$ is independent of $t$. The proof follows the pseudofinite regime used by Chernikov and Starchenko to prove an analogous version of Erdős-Hajnal for stable hypergraphs.

We construct a nonmicroscopic $G_\delta$ subset of the real line all of whose compact subsets are microscopic, answering a question of Zindulka and Nowakowski. We first obtain such a set in the standard Cantor space by coding branches of a finitely branching tree together with suitable choices of marked nodes. The coding of the branches ensures that the resulting set is not microscopic, while the marked nodes allow us to construct covers showing that every compact subset is microscopic. The example is then transferred from the Cantor space to the real line by the binary-expansion map.

We study finite Laver algebras, the generalizations of Laver tables on sets of cardinality not of the form $2^n$. We characterize the conditions under which projections and embeddings between Laver algebras exist and show that there are $2^{\aleph_0}$ pairwise non-isomorphic direct limits of finite Laver algebras.

We show that whenever $G$ is a finitely generated group with the rapid decay property (property RD), then the norm on the reduced group C*-algebra $C^*_r(G)$ is computable if (and only if) $G$ has solvable word problem. We also give an example of a finitely presented group $G$ with solvable word problem for which the norm on $C^*_r(G)$ is not computable.

Answering a question of Thomas Sinclair, we show that the standard presentation of the reduced group C*-algebra $C^*_r(G)$ of an infinite hyperbolic group $G$ is computable. The main ingredient in proving this result is showing that the Gromov boundary $\partial G$ of $G$ admits a computably compact metric presentation for which the natural action of $G$ on $\partial G$ is computable.

We generalise the $\sigma$-ideal $\mathcal E$ generated by the closed Lebesgue null subsets of the Cantor space ${}^\omega 2$ to the context of higher Cantor spaces ${}^\kappa 2$ for an uncountable cardinal $\kappa$ satisfying $\kappa=\kappa^{<\kappa}$. We introduce candidates for a higher closed null ideal based on slaloms on partitions of $\kappa$ into sets of size ${<}\kappa$, and study their combinatorial properties. We also give some relations between the cardinal characteristics of the higher closed null ideals and other cardinal characteristics.

We show that for each countable ordinal $\alpha$, there is a $\mathbf{\Delta}^0_\alpha$ operator that, for all $A$ of Scott rank at most $\alpha$, takes copies of $T_A$ to copies of $A$, where $T_A$ is the tree of tuples corresponding to $A$. For finite $\alpha$, we show that this is best possible. The proof that there is a $\mathbf{\Delta}^0_\alpha$ operator uses Harrington's method of workers. The sharpness result, for finite $n$, uses recent work of Harrison-Trainor on “unfriendly jump inversion.”

We show that unlike $\textsf{PFA}$, $\textsf{MA}_{\omega_{1}}$ is consistent with the existence of $2^{\omega_{1}}$-many Countryman lines which pairwise contain no uncountable isomorphic or reverse-isomorphic suborders. This clarifies an issue regarding the claim that $\textsf{MA}_{\omega_{1}}$ implies that there is a finite basis for the Countryman lines. The family of Countryman lines comes from a family of $2^{\omega_{1}}$-many coherent trees which pairwise contain no club-isomorphic subtrees. To prove this, we first construct such a family of trees using $\diamondsuit$, and then we iterate ccc forcings while preserving this property.

We study which structural results about Aronszajn trees require the Proper Forcing Axiom and which require only MA(aleph1). In particular, we show that MA(aleph1) is consistent with the existence of 2^aleph1 pairwise non-club-isomorphic coherent A-trees.

It was recently shown by Paolini and Shelah, with another proof by Laskowski and Ulrich, that torsion-free abelian groups are Borel complete. This means that isomorphism for torsion-free abelian groups is as complicated as possible, so that torsion-free abelian groups do not admit any meaningful complete isomorphism invariants. We give a proof following the ideas of the Paolini-Shelah argument but with several expository advantages. In particular, the combinatorial part of the argument is much simplified. We make use of the ideas of this proof to show that there is a torsion-free abelian group with no computable copy but with a copy computable from every non-computable set. This answers a long-standing question of Downey and Goncharov.

We introduce sub-connectivity logic, denoted by $\textsf{FOscon}$, an extension of first-order logic for graphs with a specified set $Z$ of admissible edges. Its additional atom $\textsf{scon}(x,y;\bar z)$ asserts that $x$ and $y$ are connected by a path using only edges of $Z$ and avoiding the vertices in $\bar z$. Our main structural result states that, for every weakly sparse graph class $\mathscr C$, the class of all expansions of graphs in $\mathscr C$ by rooted spanning forest orders has bounded twin-width if and only if $\mathscr C$ excludes a fixed minor. When $\mathscr C$ excludes a fixed minor, we can also compute an additional linear order that preserves bounded twin-width in polynomial time. We translate $\textsf{FOscon}$ into first-order logic over an expansion by a depth-first spanning forest order of the admissible-edge graph. Combining this translation with our structural result, we obtain a model checking algorithm for $\textsf{FOscon}$ with running time $f(|\phi|,h(G))\cdot |G|^c$, where $f$ is computable, $c$ is an absolute constant, and $h(G)$ is the Hadwiger number of $G$. The translation and model-checking algorithm extend to binary relational structures, with the Hadwiger number measured on the Gaifman graph. For a graph class $\mathscr C$ let $\mathscr C_Z:=\{(G,Z):G\in\mathscr C,\ Z\subseteq E(G)\}$. We show that for every weakly sparse graph class $\mathscr C$, the class $\mathscr C_Z$ is monadically dependent for $\textsf{FOscon}$ if and only if $\mathscr C$ excludes a fixed minor. For monotone classes that admit efficient minor encodings, a corresponding hardness result makes this frontier computationally tight. We give applications to combinatorial reconfiguration and solution discovery problems, and study a guarded extension of $\textsf{FOscon}$ motivated by database queries.

Motivated by the EPPA problem for finite tournaments,we consider various extension properties for partial permutations. We show that for any set $\Pi$ of prime numbers, the $\Pi$-extension property is equivalent to the $\Pi$-LERF. As a consequence of known results, the odd-extension property is then equivalent to the EPPA for finite tournaments. To study the $\Pi$-extension property, we reformate the property using the concepts of EP problems and $\Pi$-solutions. We then show that the existence of a $\Pi$-solution for an EP problem depends entirely on its fundamental group. In particular, when the fundamental group is trivial or cyclic, the EP problem has a $\Pi$-solution for any $\Pi$. These extend some known results of Huang, Pawliuk, Sabok and Wise [HPSW19]. We give examples of EP problems without nilpotent-solutions; they witness that the $p$-extension property and the $p$-LERF fail for any prime $p$. Then we consider a special kind of EP problems whose fundamental groups have two generators. We show that any 1-weakly wandering problem has a $\Pi$-solution for any $\Pi$. For 2-weakly wandering problems, we show that they all have odd-solutions and we completely characterize those without nilpotent-solutions.

We provide a modern overview of several forcing methods in bounded arithmetic and compare them with forcing in set theory. We specifically discuss the countable forcing framework of Atserias and Muller, the restricted ultrapowers of Bydzovsky and Muller, and forcing with random variables developed by Krajicek. We illustrate these forcing arguments by reviewing the Paris–Wilkie forcing and by giving a self-contained construction of the shallow PHP model constructed by Krajicek. We observe that, from a formal point of view, Krajicek's forcing with uncountable structures can be interpreted in the framework of Atserias and Muller after a countable collapse using an LS argument. We further observe that the countable restricted ultrapowers of Bydzovsky and Muller, used to obtain models of the theory $T_{PV}$, can also be interpreted in this framework. This part serves as a primer on modern forcing methods in bounded arithmetic. In the next part, we discuss the analogies and differences between forcing in arithmetic and set theory. We embed Krajicek's Boolean-valued models into generic extensions of models of set theory, observing that the set-theoretic forcing framework can be used to interpret forcing in arithmetics. In our interpretation, set theory offers a convenient method for formalizing forcing arguments with uncountable structures. We end with a question whether analogies with set theory can facilitate the discovery of new uncountable partial orders for arithmetic.

We prove that NIP nilrings of bounded nilexponent are nilpotent. We also deduce that NIP $\omega$-categorical $n$-Engel Lie algebras of characteristic $p>n$ are nilpotent, yielding a case of the Lie algebra analogous of Wilson conjecture for $\omega$-categorical groups.

We show that every definable function in a weakly o-minimal expansion of a field $K$ is generically differentiable, where the derivative takes values in the Cauchy completion of $K$, i.e. it is a definable nonvaluational cut. As a consequence, every definable field is definably isomorphic to either $K$ or its algebraic closure.

We study Scott-product compatibility and sobriety for countable meet-continuous directed-complete partial orders (dcpos). We construct a countable meet-continuous dcpo $\mathcal R$ whose Scott space is well-filtered but not sober, although the Scott topology on every finite power is the product of the factor Scott topologies. The ideals of $\mathcal R$ admit a unique finite-parameter description. We also construct a countable meet-continuous dcpo $\mathbb{H}$ with a greatest element whose Scott space is coherent and well-filtered, but whose Scott square has a topology strictly finer than the ordinary product topology. These constructions answer negatively two questions about countable meet-continuous dcpos. On the positive side, we prove that a meet-continuous $L$-dcpo, meaning a dcpo whose principal ideals are complete lattices, is Scott sober whenever its Scott square carries the ordinary product topology. This answers Jia's core-compactness question affirmatively for $L$-dcpos without any countability assumption. Finally, we characterize well-filteredness of $L$-dcpos by boundedness of closed Rudin sets and formulate related open questions.

We study the universal isotypic block-diagonalization problem in the Type-2 theory of effectivity (TTE). We obtain a uniform computability result for the universal block diagonalizer for commutants of given finite group representations. As an application, when the given representation is orthogonal, we compute ordinary $QR$ factorizations blockwise in the isotypic basis. After transforming back to the original coordinates this yields a factorization $A=QX$, where $Q$ is orthogonal and $X$ is generally not upper triangular. Moreover, given a Wedderburn-adapted orthogonal basis, the transformed-back factors can be computed within the commutant.

We study idealized maximal eventually different families through Van Douwen maximality, productivity, and ultrafilter maximality. We show that Van Douwen $\mathcal{J}$-MED families correspond to $(\mathcal{J}\times\emptyset)$-MAD families, and for coanalytic ideals containing the finite sets they are further reduced to infinite analytic $\mathcal{J}$-MAD families. This yields nonexistence results for analytic Van Douwen families for several standard ideals, together with a characterization of the finite case. We recall the definition of finite productivity and introduce finite-section and $\omega$-centered productivity. Finite-section productivity is equivalent to $\mathcal{U}^*$-maximality for some ultrafilter $\mathcal{U}$ extending $\mathcal{J}^*$, and these notions admit natural Stone-space characterizations. We construct Borel finitely productive families for uniformly weakly Ramsey ideals and Borel $\omega$-centered productive families for uniformly weakly $P^+$ ideals, while no analytic finite-section productive $\mathrm{Fin}$-MED family exists. Finally, for every Ramsey ultrafilter $\mathcal{U}$ and $1\leq\alpha<\omega_1$, there is no analytic $(\mathcal{U}^{\alpha})^*$-MED family, while under $V=L$, there is a $ \boldsymbol{\Sigma}^1_2 $ Ramsey ultrafilter $ \mathcal{U} $ where there is a coanalytic $ \mathcal{U}^* $-MED family.

We give a column-avoidance modification of the no-least-join construction of Downey, Greenberg, Lewis, and Montalbán. We show that if $C$ is computably enumerable, $A,B<_T C$, and $A\not\leq_T B$, then for every noncomputable set $E$ there is a set $X\leq_T C$ such that $B\leq_T A\oplus X$ and $E\not\leq_T X$. Consequently, for the corresponding Turing degrees $a,b,c$, the degrees $x\leq c$ satisfying $b\leq a\vee x$ have no nonzero common lower bound; equivalently, no nonzero Turing cone contains all of them. This gives a negative answer to their Question 1.19.

We study combinatorial Banach spaces, i.e. Banach spaces induced by families of finite sets, of uncountable density. We prove some general theorems, for example we characterize when such spaces contain isomorphic copies of long $c_0$ and long $\ell_1$. We discuss the existence of Banach spaces which are (complementedly) universal in the category of Banach spaces with unconditional basis of fixed cardinality. We present some examples, in particular we show that the Banach spaces generated by Suslin trees do not contain uncountable equilateral sets.

We study the minimal tense logic $K_t$ from an algebraic and proof-theoretic perspective. We introduce the degree-of-truth-preserving logic associated with the class of tense Boolean algebras. We then introduce a sequent calculus for this logic and establish its soundness and completeness with respect to tense Boolean algebras by means of an adaptation of the Lindenbaum–Tarski construction. Consequently, this calculus provides an additional syntactic presentation of the minimal tense logic $K_t$. We also provide a second, purely syntactic proof of completeness. Furthermore, we establish an algebraic soundness and completeness theorem for Kashima's Gentzen-style calculus. To this end, we develop an adaptation of the Lindenbaum–Tarski construction to Kashima's nested sequent framework, which allows us to construct the algebraic semantics directly from the proof-theoretic system. This yields a direct algebraic completeness proof for Kashima's calculus and connects its nested-sequent formulation with the algebraic semantics of tense Boolean algebras.

Weak modal logics can be obtained by restricting the axioms and inference rules governing the modal operator. At the extreme, one may consider the least modal logic, in which no specifically modal axiom or inference rule is imposed. We introduce closure semantics, a new possible-world semantics for such weak modal logics, and establish soundness and strong completeness for a range of systems. We also give truth-preserving translations between closure models and other possible-world semantics, including neighborhood, FMT, and Kripke semantics.

We examine the relationship between trees and narrow systems. In particular, we prove that if a tree of height $\kappa$ admits a narrow subsystem, it must contain a well-pruned subtree of height $\kappa$. We extend these results to two-cardinal trees.

Let \(H(A)\) be the Hattori space associated with \(A\subseteq\mathbb R\), and put \(B=\mathbb R\setminus A\). Kulesza announced at the 2018 Joint Mathematics Meetings that Lindelöfness of \(H(A)^{2n}\) forces Lindelöfness of \(H(A)^{2n+1}\) for every positive integer \(n\). The meeting abstract states this implication without a proof. This paper proves the case \(n=1\) in ZFC. The same one-sided geometry gives a pointwise half-space criterion for affine discreteness and, when \(H(A)^2\) is Lindelöf, a four-coordinate obstruction for uncountable closed discrete monotone traces. Known results on mixed Sorgenfrey–Euclidean products lead to hereditary-Lindelöf criteria for finite powers, a countable-power characterization, and a finite-power Lindelöf reduction. A transfinite construction gives \(A\subseteq\mathbb R\) for which \(H(A)^2\) and \(H(A)^3\) are Lindelöf, whereas \(H(A)^4\) contains a closed discrete affine line of cardinality \(\mathfrak c\).

We prove in ZFC that $\mathfrak d=\omega_1$ implies $\mathfrak a=\omega_1$, settling a question of Roitman from the 1970s. Here $\mathfrak d$ is the least size of a family that eventually dominates every function in $\omega^\omega$, and $\mathfrak a$ is the least size of an infinite maximal almost disjoint (MAD) family of infinite subsets of $\omega$. Consequently, $\mathfrak a\leq\mathfrak d$ whenever the continuum $\mathfrak c=2^{\aleph_0}$ is at most $\omega_2$. This answers negatively Shelah's question whether $\mathfrak d<\mathfrak a$ is consistent with $\mathfrak c=\omega_2$, and shows that his model of $\mathfrak d=\omega_2<\mathfrak a=\mathfrak c=\omega_3$ has the least possible values of $\mathfrak d$, $\mathfrak a$ and $\mathfrak c$ among models of $\mathfrak d<\mathfrak a$. The proof also gives a preservation theorem: from any dominating family of size $\omega_1$, we construct a MAD family of size $\omega_1$ that remains maximal in every outer model in which the given family is still dominating. Thus, under $\mathfrak d=\omega_1$, some MAD family is indestructible by every $\omega^\omega$-bounding forcing; it can moreover be chosen almost strongly separable, hence Cohen-indestructible. These results give negative answers, under $\mathfrak d=\omega_1$, to two questions of Hrušák and to one of Brendle, Guzmán, Hrušák and Raghavan.

We study the existence of model companions after adjoining an automorphism to field theories in two complementary settings. For bounded PAC fields of characteristic zero containing all roots of unity and admitting a cyclic Galois quotient of prime order, a suitable choice of countably many constants gives a model-complete field theory which has no model companion after adding an automorphism fixing the named constants. This applies, in particular, when the absolute Galois group is free profinite or free pro-$p$ of finite positive rank. Secondly, for every completion of $\ACFA$ in every characteristic, adjoining a second commuting automorphism has no model companion. The two explicit obstructions use a common ordered product of inertia automorphisms along an infinite orbit, combined respectively with an equivariant PAC completion and an algebraically closed difference-field embedding.

We consider the 653 equational laws of order up to 4 for an associative binary operation, and all of their conjunctions. We determine that there are only 456 equivalence classes of such conjunctions (associative equational theories), and find all implications between them. The conjunction operation makes this set of theories into a semi-lattice. These results are formalized in Lean. This is a semigroup analogue of the Equational Theories Project, but extended to conjunctions of equations.

For every fixed integer $d\geq2$, we prove that the finite graphs receiving a continuous homomorphism from the standard Schreier graph $F(2^{\mathbb Z^d})$ form a $\Sigma^0_1$-complete set. This extends a theorem of Gao, Jackson, Krohne and Seward when $d=2$. For the positive part of the reduction, we show that if a graph $H$ satisfies a certain property then there is a continuous graph homomorphism from $F(2^{\mathbb Z^d})$ to $H$, in particular, the complete graph $K_4$ satisfies this property. This extends a theorem of Gao and Jackson. We also prove that $\big (\mathcal H_d\big )$ is a strictly decreasing sequence.

We prove that $\mathsf{Cheq}$ is not finitely axiomatizable, resolving a longstanding open problem in intermediate and modal logics. We further prove that the undecidability of Medvedev logic implies the undecidability of $\mathsf{Cheq}$.