Logic Papers

ALT We prove that KP, with Full Set Induction, is neither solid nor tight. More generally, every consistent theory obtained from KPC by adding a quantifier bounded set of sentences has a model with a parameter-free definable class surjection from its natural numbers onto its universe. Using such enumerations to define generic extensions by relative interpretations, we show that theories with the stable definable ground property are not tight. Ground definability over MOST and continuum coding over ZFCΠ₃ yield applications to weak inductive set theories with large cardinals and forcing axioms. Finally, solidity for quantifier bounded extensions of MOST with Full Set Induction implies a Ground Axiom formulated using a fixed finite level of genericity; under the same solidity hypothesis, the corresponding extension of full ZFC proves the ordinary Ground Axiom.

ALT Let K be a field which is strongly stable, that is, stable and strongly dependent. Then K is finite or algebraically closed. This answers a question of Shelah.

ALT Many explicit constructions in algebra are not first-order definable in classical finitary logic, but are, however, definable in infinitary logic. The aim of this paper is to show how infinitary logic can be used to lift model-theoretic results in arithmetic to a quantifier-sensitive form. We apply this idea to a deep result of Jahnke and Kartas on the model theory of perfectoid fields. Our main result is that a first-order sentence φ holds in the tilt k♭ of a perfectoid field k if and only if a certain sentence φ♮ holds in a non-principal ultrapower of k, where φ♮ does not depend on k and is only slightly more complicated than φ itself. In particular, tilting preserves the Lévy hierarchy in a precise sense. To this end, we prove that the Standard Decomposition of a valued field at a constant t is infinitarily interpretable by formulas of rank at most 1.

ALT Given a collection of mathematical objects and a natural notion of equivalence (such as isomorphism), we want to find a complete classification. This paper presents methods for proving anti-classification results, that is, when a complete classification is not possible using certain classifying invariants. The problem of using real numbers as classifying invariants is well understood. In this case, the obstruction to classifiability is ergodicity. We consider classifiability by higher rank objects, such as countable sets of real numbers, and present a simple ergodicity-like obstruction for classifiability. This method is particularly useful when applied in various models of ZF where even weak fragments of the axiom of choice fail.

ALT A Johnson graph J(n,k) is a graph whose vertices are the k-element subsets of an underlying set of size n where two vertices are adjacent if they intersect in a subset of size k-1. We extend the definition to allow infinite parameters and we study a natural limit theory T_J of Johnson graphs. We show that T_J is complete and we give an axiomatisation of T_J, from which we obtain a complete description of the models of T_J. We use this to show tameness properties of T_J, namely that T_J is ω-stable of Morley rank ω, but not monadically dependent. In particular it follows that the class of all finite Johnson graphs is stable, and therefore dependent but not monadically dependent.

ALT Can random real carry arbitrary information. In terms of (Turing) computability, Kučera and Gács addressed this question in affirmative. i.e., Every real x∈ 2ω is computable from some Martin-Löf random real. This result motivated quantitative versions of coding into random reals. i.e., How many bits of the random oracle are needed to compute the first n bits of x. Barmpalias and Lewis-Pye obtained a coding that uses n+O(log n) many bits. Is it possible for the coding to use n bits exactly? This is equivalent to say, if every real is rK-reducible to a Martin-Löf random real. In this paper, we prove that such a coding does not exist. i.e., There exists some real that is not rK-reducible to any Martin-Löf random real.

ALT Given a real x∈ 2ω, how many reals are there that are simpler (or equally simple) to describe than x. With “simpler to describe" characterized by K-complexity of initial segments (hence we call such y with y≤_K x a solution to x), if x is infinitely often K-trivial (hence i.o. K-trivial), then a simple counting argument shows that the number of solutions to x is countable. If x is non i.o. K-trivial, then must it admit uncountably many solutions? Motivated by this question, we show that: (1) There is a non i.o. K-trivial x such that most of its solution is i.o. K-trivial. i.e., Only countably many solution to x are non i.o. K-trivial. In particular, the cardinality of K-degree of x is countable. (2) There is a minimal pair of K-degree (meaning their common solutions are all K-trivial) so that each of the pair is non i.o. K-trivial, generalizing a result of Csima and Montalbán (where the pair is not required to be non i.o. K-trivial but non K-trivial). (3) There is a non i.o. K-trivial

ALT We give an example of a directed set whose Tukey spectrum is not closed under stationary limits. This is a counterexample to a theorem due to Isbell from the 60's. We isolate a combinatorial principle arising from our example, between stationary reflection and weak compactness.

ALT We show that, in ZF set theory, the existence of "coset correct means" on all groups is equivalent to the Hahn-Banach Theorem, as well as to the existence of invariant means on abelian groups.

ALT We prove Szemerédi-Trotter-type incidence bounds for algebraic relations in any field F admitting a valuation with finite residue field. This includes Fq(t), Fq((t)), and all finitely generated extensions of finite fields. Bays and Martin show that any algebraic Kd,s-free relation E⊆ Fᵏ× Fℓ admits a power-saving in the classical Zarankiewicz bound of Kővári, Sós, and Turán. Answering a question of the authors, we show that this power-saving is uniform in F: There is some ε>0 depending only on d and the complexity of E (and not on F) such that for A⊆ Fᵏ and B⊆ Fℓ, the number of edges |E(A,B)|is at most O(|A|¹⁻ε|B|¹⁻¹⁻ε⁄ᵈ+|A|+|B|). For the case where A is a set of points and B is a set of lines in F² and E is the incidence relation, we prove the explicit bound O(|P|⁸⁄₉|L|⁵⁄₉+|P|+|L|). As the central ingredient of the proof, we introduce the model-theoretic notion of distality relative to a definable set. We begin developing this notion and prove that the theory of algebraically closed va

ALT We study algebras for the BM-, BI-, and BMI-fragments of combinatory logic, where B xyz →w x(yz), M x →w xx and I x →w x. We prove that every finite BM-algebra A contains an element Y satisfying Yx = x(Yx) for all x∈ A. Moreover, a single closed BM-term represents such an element in every finite BM-algebra. On the other hand, we show that there exists an infinite BMI-algebra with no such element. Consequently, the variety of BM-algebras is not generated by finite BM-algebras. We also characterise finite BI-algebras as finite semigroups with two distinguished left units B and I, and finite BMI-algebras as finite idempotent semigroups with three distinguished left units B, M and I.

ALT In this paper, we consider conservation results for iterated βₙ-model reflection principles. Using these principles, we characterize the Π¹ₘ₊₂-, Σ¹ₘ₊₂- and B(Π¹ₘ₊₂)-consequences of Σ¹ₙ₊₁-DC₀ and Σ¹ₙ₊₁-TDC₀ for m ≤ n. Here, B(Π¹ₘ₊₂) denotes the set of Boolean combinations of Π¹ₘ₊₂-formulas, and TDC stands for transfinite DC. We also show that, in each case, the stronger theory has a super-exponential speed-up over the corresponding conservative subtheory.

ALT Universally Baire sets are a standard tool in modern set theory, where they are closely connected with forcing and absoluteness. In this paper we study universal Baireness instead as purely a regularity notion for subsets of Polish spaces. Our aim is not to develop the set-theoretic theory, but to place the notion on a systematic descriptive-set-theoretic footing and to clarify the several nonequivalent definitions that occur in the literature. A subset of a Polish space is called universally Baire if all its continuous preimages possess the property of Baire. However, it is important to specify what the domain of these continuous functions can be. In fact, a plethora of definitions are used by various authors in the literature, the class of possible domains is sometimes the class of Polish spaces, compact metrizable spaces, all topological spaces, compact topological spaces, etc. We clarify this situation by demonstrating that the above four options are pairwise nonequivalent under th

ALT We determine the Borel-reducibility comparison of each pair of mathbfΠ⁰₃ benchmark equivalence relations in Gao's monograph. The additional comparisons we prove are E∞≤_B c₀, E∞≰_Bℓₚ for 2<p<∞, ℓₚ≰_B≡ₘ for 2<p<∞, c₀≰_B≡ₘ, c₀≰_Bℓ∞⁺ and ≡ₘ≰_Bℓ∞⁺. Together with the previous positive direction, these give ℓₚ≤_B≡ₘ if and only if p≤2. These answer several questions in Gao's monograph and Kanovei' monograph. We also prove that unitary equivalence of all bounded linear operators is not Borel reducible to ≡ₘ. This answers a question of Ding and Gao. Equivalently, unitary equivalence of arbitrary representations of F∞ is strictly more complicated than that of arbitrary representations of ℤ. This answers a question of Thomas.

ALT We show that if κ<κ = κ, then there is a κ-strategically closed, κ⁺-c.c. partial order that forces □κ. We discuss consequences for generic large cardinals.

ALT What does a recursive definition mean when the logic is grounded, so a sentence is true only if a terminating process makes it so? Kripke's answer for the special case of truth was the least fixed point. This paper takes that answer as a rule. Reflective Grounded Arithmetic (RGA) already writes any recursive definition as one self-referential term, paradoxes included. Inductive Grounded Arithmetic (IGA) adds the elimination rule for every positive one, so that accessibility, the winning positions of a game, and grounded truth itself each come with their own induction principle. The rule is sound for the omega model and the system is consistent, both machine-checked in Isabelle/HOL. With the rule, IGA proves Goodstein's theorem outright, in a logic without implication at an undecided hypothesis, and the Kirby-Paris hydra game for primitive recursive strategies, both with every step of the arithmetic a grounded derivation. It proves the Cantor normal forms well-founded, from which the we

ALT Let λ be a Magidor cardinal and let α∈[α_M,λ). We show that λ→[λ]ℵ₀⁻ᵇᵈα,<α. We prove the consistency of a similar statement for Jónsson cardinals.

ALT The Medvedev lattice is a tool used to classify the complexity of effective closed sets. In this article, we are interested in the complexity of using this tool. In particular, we study the complexity of deciding whether two effective closed sets have the same degree, when one is fixed and the other is given as input. This problem is naturally Σ⁰₃, and among other results, we show that for all degrees except the maximal one, the problem reaches its maximal complexity. It turns out that the argument is not uniform and depends on the self-similarity of the fixed degree, a notion that we introduce in this article. The complexity of having maximal degree is particularly difficult to establish, but we obtain a lower bound that almost matches the upper bound. We also show that deciding whether an effective closed set has a degree incomparable with a fixed degree d is Π⁰₃-complete whenever 0ₛ <ₛ d <ₛ 1ₛ.

ALT We show that each of the infinitely many extensions of the basic inquisitive logic has the Craig interpolation property, and deduce from this that each of these extensions also has the Beth definability property. These results stand in contrast to existing characterizations of interpolation within lattices of extensions, in which the distribution of logics with interpolation is sparse.

ALT We study the structure of amenable subrelations of treeable measure-class-preserving equivalence relations, applying the Radon–Nikodym topography perspective initiated in our companion paper [TTD25]. For a nowhere smooth amenable subrelation, we show that the ends selected by each class in Adams's end selection theorem are precisely those which are nonvanishing along that class. From this, we derive a number of structure results about nowhere smooth amenable subrelations of treeable equivalence relations. For example, we show that every nowhere smooth amenable subrelation is contained in an essentially unique maximal amenable subrelation. This yields an anti-treeability criterion, which we use to show that every nonamenable locally compact second countable group with noncompact amenable radical is not treeable, and that every nonamenable nonunimodular treeable group has a compact open subgroup.