Papers

This paper proves that every nonrecursive many-one degree contains either exactly one or infinitely many finite-one degrees. This gives a negative answer to Open Question 2 of Richter, Stephan, and Zhang~\cite[p.~17]{RSZ}. Earlier work established that, for almost every $A\subseteq\N$ with respect to the standard product measure on $2^\N$, the degree $[A]_{\m}$ contains an infinite antichain of finite-one degrees~\cite{Cintioli}. Thus the question had already received an almost-sure negative answer; the present theorem settles it for every nonrecursive many-one degree.

We investigate decidability of properties in the lattice $\mathop{\mathsf{NExt}} \mathsf{Grz}_t$ of extensions of the Grzegorczyk tense logic $\mathsf{Grz}_t$ and the lattice $\mathop{\mathsf{NExt}} \mathsf{S4}_t$ of reflexive and transitive tense logics, with applications to the lattice $\mathop{\mathsf{Ext}} \mathsf{biIPC}$ of bi-superintuitionistic logics. We prove that a broad class of properties is undecidable in $\mathop{\mathsf{NExt}} \mathsf{Grz}_t$, including tabularity, Kripke completeness, the finite model property, and decidability, which also yields their undecidability in $\mathop{\mathsf{NExt}} \mathsf{S4}_t$. We also construct infinitely many tabular extensions of $\mathsf{Grz}_t$ (and thus of $\mathsf{S4}_t$) whose coincidence problems are undecidable, while presenting one tabular extension of $\mathsf{Grz}_t$ and infinitely many ones of $\mathsf{S4}_t$ with a decidable coincidence problem. As a consequence, we obtain that the finite model property and tabularity are undecidable in $\mathop{\mathsf{Ext}} \mathsf{biIPC}$, and that there are infinitely many tabular extensions of $\mathsf{biIPC}$ whose coincidence problems are undecidable. These results clarify some similarities and differences between $\mathop{\mathsf{NExt}} \mathsf{Grz}_t$ and $\mathop{\mathsf{NExt}} \mathsf{Grz}$, $\mathop{\mathsf{NExt}} \mathsf{S4}_t$ and $\mathop{\mathsf{NExt}} \mathsf{S4}$, as well as $\mathop{\mathsf{Ext}} \mathsf{biIPC}$ and $\mathop{\mathsf{Ext}} \mathsf{IPC}$. The proofs adapt Chagrov's method of reducing from an undecidable problem for Minsky machines. We isolate and explicitly formulate the method of good valuations, a recurring technique underlying several proofs in the literature that use large frames, making it available for further applications.

The main aim of this note is to provide a characterisation of coextensive morphisms in the category of bounded hoops. This characterisation is then used to show that several categories of bounded hoops are coextensive as categories. Among these are the variety of bounded Wajsberg hoops, or more generally the variety of bounded $\vee$-hoops. Our characterisation also yields the coextensivity of the category $\mathbf{Heyt}$ of Heyting algebras and recovers the known coextensivity of the category $\mathbf{MV}$ of MV-algebras.

We investigate the iterative conception of set in its most general form, allowing urelements without assuming that they form a set. We formulate this conception in two ways, as stage theory and as level theory, and develop a general theory of levels with urelements. Unlike their pure-set counterparts, the resulting stage and level theories are not set-theoretically equivalent; moreover, second-order level theory with urelements is not weakly quasi-categorical. We then consider further principles governing stages and levels, motivated by directedness, unboundedness, and reflection. Some of these principles restore set-theoretic equivalence between the corresponding theories, while their level-theoretic versions yield forms of quasi-categoricity. These principles form strict implication hierarchies, thereby revealing distinct stronger conceptions of set beyond the basic iterative conception.

For every quadratic number field $K$, we prove a uniform $3$-unknown Diophantine definition of integer tuples in $\mathcal{O}_K$, allowing finitely many polynomial nonvanishing conditions. This yields an effective $+3$ transfer principle and a $13$-unknown representation of every recursively enumerable integer relation. Consequently, there exists an absolute degree bound $D_0\geq1$ such that for every quadratic number field $K$, there is no algorithm that, given \[ P(Y_1,\ldots,Y_{13})\in\mathbb{Z}[Y_1,\ldots,Y_{13}],\quad \mathrm{deg}\ P\leq D_0, \] decides whether $P=0$ has a solution in $\mathcal{O}_K^{13}$. The arithmetic input is a fourth-order Pell–Lucas congruence. It is a specialization of the norm-one Lucas multiplication formula, which yields exact valuations for the deviation of a Lucas quotient from its linear term, together with deviation criteria for Lucas–Wieferich and Wall–Sun–Sun primes. We also establish local surjectivity and $\ell$-adic density for second-order correction terms for norm-one Lucas sequences.

In this paper, we study how the classification complexity of natural orbit equivalence relations changes when the full homeomorphism group of a compact metrizable space is replaced by a dense non-closed subgroup. For a compact space $X$ and a subgroup $G \leq \mathcal{H}(X)$, we consider three canonical actions: the left shift action on $\mathcal{H}(X)$, the induced hyperspace action on $\mathcal{F}(X)$, and the conjugation action on $G$ We first analyze subgroups of the group $\mathcal{H}^+([0,1])$ of increasing interval homeomorphisms, focusing on bi-Lipschitz homeomorphisms, diffeomorphisms, and bi-absolutely continuous homeomorphisms. We show that, in contrast to the behavior of closed subgroups, passing to these subgroups strictly increases the complexities of the associated classification problems or makes them incomparable with the corresponding full-group relations. In the second part, we investigate hyperspace actions of bi-absolutely continuous homeomorphisms on the Cantor space and the Hilbert cube with respect to some Borel probability measure and show that a similar behavior occurs on these spaces as well.

The fundamental theorem of statistical learning states that, under suitable measurability assumptions, finite Vapnik–Chervonenkis (VC) dimension guarantees that every proper consistent learning rule is probably approximately correct (PAC). Blumer, Ehrenfeucht, Haussler, and Warmuth showed, assuming the Continuum Hypothesis, that the "well-behavedness" condition of the concept class cannot be omitted: they constructed a concept class of Borel sets of VC dimension one admitting a consistent learning rule that is not PAC. We show that the Continuum Hypothesis is unnecessary. Working in Zermelo–Fraenkel set theory with the Axiom of Choice (ZFC) alone, we construct a concept class of Borel sets on $[0,1]$ of VC dimension one and a proper consistent learning rule that is not PAC. More precisely, for a suitable Borel probability measure and target concept, the rule has true risk one at every sample size on a set of samples of outer probability one. Consequently, finite VC dimension and Borel measurability of the individual concepts do not suffice to guarantee that every proper consistent learning rule is PAC. The result shows, with no need of extra set-theoretical assumptions, that the additional regularity assumption in the fundamental theorem cannot in general be omitted.

We study fixed points in abstract provability structures (APSs), which were introduced by Beklemishev and Shamkanov as an order-theoretic framework for studying Gödel's second incompleteness theorem (G2). For one-variable APS terms built from the provability and refutability operations $\Box$ and $\boxtimes$, we investigate the existence and uniqueness of fixed points in terms of their degree. The degree of a term is the number of occurrences of $\boxtimes$. We prove that every term of degree two has a fixed point and establish a strict hierarchy among the fixed-point properties of the terms $\boxtimes\Box^k v$. We further show that suitable levels of this hierarchy guarantee the existence and uniqueness of fixed points for arbitrary one-variable APS terms of positive degree. We also obtain several G2-like non-refutability results, some of which depend only on whether the degree is even or odd. Finally, we consider APSs based on meet-semilattices. Under an additional condition, we obtain stronger fixed-point results and show that a parametrized fixed-point property implies an abstract form of Löb's theorem.

This paper gives a survey of propositional modal logic in an intuitionistic setting. Mainly intended for readers already familiar with classical modal logic, we discuss why there are two prominent families of such logics, intuitionistic modal logics (IMLs) and constructive modal logics (CMLs), what motivates their study, and how they compare with each other. We then take a look at the logics lying between the CML and IML traditions, and survey various extensions and $\Diamond$/$\Box$-free fragments. We further record several observations which seem to be implicit or absent in the literature; we point out a small defect in the original semantics for $\textbf{CK}$ and prove Lyndon interpolation theorems for $\textbf{CK}$ and $\textbf{WK}$.

We prove a purely classical, coding-theoretic characterization of Hausdorff and packing dimensions in \(\mathbb R^n\). A ball code assigns names to closed balls of \(\mathbb R^n\): it is a partial map from a prefix-free set of finite binary strings to balls. For every nonempty \(E\subseteq\mathbb R^n\), the Hausdorff dimension of \(E\) is the minimum, over all ball codes, of the supremum over \(x\in E\) of the lower asymptotic rate at which \(x\) can be described by names of balls containing it; the packing dimension is obtained in the same way from the upper rates. The Hausdorff characterization is a Euclidean counterpart of Ryabko's coding theorem for combinatorial sources. We obtain the packing characterization from the standard characterization of packing dimension by upper modified box-counting dimension, without encoding \(\mathbb R^n\) into a sequence space. We then derive the point-to-set principle of J.~Lutz and N.~Lutz by replacing a minimizing ball code with a rational one and storing the resulting countable codebook in an oracle.

We answer Problems 8.1 and 8.3 from \cite{Tianyuan2026}. We first note that the condition attributed there to ordinary Prikry forcing is not correct as written: the appropriate formulation uses finite symmetric difference of the ranges of the generic sequences, rather than eventual equality at the same coordinates. We record answers to the two problems for both formulations. A length-$\omega$ Magidor forcing gives a genuinely Prikry-type example satisfying both conditions. Rigid real-adding forcing gives a broad source of further examples, and a forcing of Jech and Shelah shows that the condition does not carry any large cardinal strength. An $E_0$-invariant Jensen-type forcing of Kanovei and Lyubetsky gives a stronger nontrivial example in which the generic reals in a fixed extension form exactly one full $E_0$-class. Finally, a simple recoding turns the real-forcing previous examples into answers for the version of the problems with corrected condition.

Proof theorists developed various frameworks to analyze impredicative systems like $\Pi^1_1\text{-}\mathsf{CA}_0$ or $\mathsf{KP}$; One is an operator-controlled derivation system, and the other is Girard's dilator-based $\beta$-logic. In this paper, we provide a functorial formulation of operator-controlled analysis of $\mathsf{KP}$, thereby unifying the two approaches into a single framework. As an application, a new proof of Girard's boundedness theorem is also provided, which states that every $\Sigma_1$-over-$L_{\omega_1^{\mathsf{CK}}}$-definable function $\omega_1^\mathsf{CK}\to \omega_1^\mathsf{CK}$ is bounded by a recursive dilator.

We study the dependence of the transfinite Schreier hierarchy on the choice of fundamental sequences for the countable limit ordinals. With each Schreier family we associate an interval endpoint function. We prove that the bounding number is equal to $\omega_1$ exactly when the fundamental sequences may be chosen so that these endpoint functions form an unbounded family in the eventual domination order. Equivalently, the hierarchy then satisfies the tail-covering property isolated by Shiliaev, or every infinite compact interval family has infinite intersection with some member of the hierarchy. We also prove that the dominating number is equal to $\omega_1$ exactly when the fundamental sequences may be chosen so that every compact family of finite subsets of $\{2,3,\ldots\}$ is contained in one Schreier family. The latter equivalence combines Fremlin's cofinality theorem for compact subsets of the rationals with an absorption construction for compact families.

Hechler forcing changes the ordinal theory.

We show that a certified formalization of the hitting-set-existence axiom of Atserias and Tzameret, instantiated on the parity-based Nisan-Wigderson compression class of Khaniki, is independent of the two-sorted theory $V^0_1$ of $\mathrm{AC}^0$-reasoning, unconditionally: $V^0_1$ proves neither it nor its negation. The same holds for the corresponding certified dual weak pigeonhole principle, whose refutation is witnessed by a single seed that certified-computes every string of the model simultaneously. The mechanism is a bounded-arithmetic transfer of Atserias-Tzameret's reduction from hitting sets to the dual weak pigeonhole principle: the amplification half of that reduction, the sole source of its NP-oracle, is unnecessary at the native stretch of the Nisan-Wigderson map, and the compression half becomes a $V^0_1$-provable implication once circuit evaluation is replaced by its certified $\Sigma^B_0$ unfolding. This is, to our knowledge, the first independence result for a derandomization-flavoured existence principle at the $\mathrm{AC}^0$-reasoning level, and it makes explicit the bridge between the Khaniki Nisan-Wigderson line and the Atserias-Tzameret reverse mathematics of hitting sets.

In 1972, Jech asked whether there exists a Suslin $(\omega_1, \omega_2)$-forest in the constructible universe. As reported by Jech, Laver gave a positive answer, but his proof was never published and appears no longer to be available. In 2015, Eskew introduced the combinatorial principle $W^*_\kappa(\lambda)$, a strengthening of Silver's principle, and used it to construct a coherent Suslin $(\kappa, \lambda)$-forest. He then asked whether the principle $W^*_{\kappa^+}(\kappa^{++})$ holds in $\mathsf{L}$ for every regular cardinal $\kappa$. We give an affirmative answer to Eskew's question, thereby also settling Jech's question.

Evidential argumentation extends Dung's abstract argumentation by requiring arguments and interactions to be backed by chains of evidence rooted in prima-facie elements. However, existing formalisms lack a unified treatment of evidential support, higher-order relations (attacks and supports targeting arbitrary elements), and collective interactions (sources as sets). In this paper, we introduce the Evidential-Based Higher-Order Set Argumentation Framework (EHSAF), which conservatively generalises several existing frameworks within a single expressive setting. We develop two complete semantics for EHSAFs: an adjacent complete labelling semantics that admits multiple truth values (true, false, undecided) for arguments in support cycles, reflecting an open epistemic attitude toward future evidence; and an extension-based complete semantics that follows a strict evidentialist stance, accepting only arguments with well-founded support chains. We show that these two semantics diverge in the presence of support cycles, and prove their equivalence under support-acyclicity. To enable computational reasoning, we provide a normal propositional encoding of EHSAFs and prove that, in three-valued Łukasiewicz logic, its models correspond precisely to the adjacent complete labellings. We further extend this encoding to continuous fuzzy logics (Gödel, Product, and Łukasiewicz), defining a continuous fuzzy normal encoded semantics. We establish that this fuzzy semantics satisfies key properties—continuity, monotonicity, boundary conditions, and solution existence—and that its ternarisation recovers the adjacent complete labellings under natural t-norm conditions. Our framework thus unifies expressive argumentation with principled three-valued and fuzzy semantics, bridging the gap between qualitative and quantitative reasoning about evidence.

We describe a (combinatorial, monoidal, Cat-enriched) Quillen model structure on the category of Cartmell's generalized algebraic theories (gats); its homotopy bicategory consists essentially of Taylor's rooted display map categories. This allows us to compare two kinds of morphisms of gats: one where sort dependency and substitution are preserved strictly, thus directly matching the syntax, and one where the given structure is preserved up to isomorphism. We prove a strictification result for morphisms out of cofibrant theories, which are the retracts of theories without sort equality axioms. Along the way, we give a structural characterization of when a contextual category can be presented without sort equality axioms. Our results also imply that when restricted to cofibrant objects, the tensor product of gats has the expected semantic behaviour, namely, it corresponds to the tensor product of locally finitely presentable categories equipped with a cofibrantly generated weak factorization system. Strict and weak morphisms specialize, respectively, to two familiar concepts of model of a gat A: ones valued in iterated families of sets, with substitution interpreted as reindexing, and set-valued models of the contextual category C(A) viewed as a finite-limit sketch. We characterize strictifiability of a model of the latter kind via a loop freeness condition on a certain map of functors out of the category of context projections of A.

The usual settings for discussing the notion of stochasticity are very different from Kolmogorov's original setting as recorded by Shen in November 1981. This paper simplifies Kolmogorov's setting and shows that the universal machine generates nonstochastic objects with surprisingly high probability.

We show that there is a $\Pi^0_2$ subset $B$ of the Euclidean plane, of Hausdorff dimension 1, such that for every line $\ell$ through the origin with hyperarithmetic direction, the projection of $B$ onto $\ell$ has Hausdorff dimension 0, thus is exceptional for Marstrand's projection theorem. It follows that for any computable ordinal $\alpha$, being $\alpha$-random does not guarantee the “almost-all” statement of the projection theorem.

We answer the question whether all Heyting algebras can appear as the lattice of subterminal objects of an elementary topos in the negative. Concretely, we show that the free Heyting algebra on two generators, hence also on N generators for every N greater than 2, cannot be such a Heyting algebra. The mathematical results in this document were obtained with the help of ChatGPT 5.6 Sol, although the document itself was written entirely by us, and we take full responsibility for its contents.

These open problems were presented in the Problem Sessions held during the Tianyuan Workshop on Definability and Computation, June 22-26, 2026. The problems are organized into sections named after their contributors, in the order of their presentations during the workshop. Notes were taken and compiled by Wei Dai, Xiangxi Hu, Yingying Jiang, Ruiwen Li, Tianhao Wang, Xu Wang, and Jie Zou.

We provide an easy proof that there are no P-points in the models obtained by adding many Silver reals with countable support to a model of CH.

In [10] it was suggested that the countable chain condition should be defined in the absence of choice as "every predense set contains a countable predense subset". During his tutorial at the "120 Years of Choice" conference in 2024, Philipp Schlicht remarked that this definition does not have an iteration theorem in $\mathsf{ZF}$. We provide a proof of this claim. Specifically, we show that if every finite support iteration of ccc forcings is again ccc, then the Axiom of Choice for countable families of countable sets must hold. However, we prove that under the assumption of the Principle of Dependent Choice, the finite support iteration of ccc forcings is again ccc. This requires correcting some issues with the definition of properness (and therefore Mekler's definition of ccc) from [1]. We then study Knaster principles and their relations to this version of ccc.

Esakia duality is the dual equivalence between Heyting algebras and Esakia spaces. However, the traditional proof uses the Prime Ideal Theorem to recover the algebra from its spectrum, a choice principle that is not constructively valid. We build on Townsend's localic Priestley duality to describe a fully constructive, localic Esakia duality. On the algebraic side, we use the recently introduced Heyting frames as the point-free version of Heyting algebras. On the spatial side, Esakia spaces are modeled by two point-free alternatives. First, Esakia locales are defined as a subclass of the ordered Stone locales introduced by Townsend, and it is shown directly that Townsend's equivalence restricts to a duality between Heyting frames and Esakia locales. Second, using the theory of conic frames, in which join-preserving closure operators on frames model localic preorders, we introduce Esakia frames as a frame-theoretic analogue of Esakia spaces. It is shown that Esakia frames are equivalent to Heyting frames and dually equivalent to Esakia locales, and that this factorises the restriction of Townsend's equivalence. This yields a fully constructive, localic Esakia duality.

The Turing jump has no fixed point on the Turing degrees: $\mathbf a <_T \mathbf a'$ for every degree $\mathbf a$. After passing to the ideal completion, however, a natural fixed-point phenomenon appears. We study the Scott-continuous lifting $\Gamma:\operatorname{Idl}(\mathbf D_T)\to\operatorname{Idl}(\mathbf D_T)$, given by $\Gamma(I)=\downarrow\{\mathbf a':\mathbf a\in I\}$. Starting from the computable degree, Kleene iteration reaches its first fixed point at stage $\omega$, namely the Turing ideal of arithmetical degrees; more generally, above $\mathbf a$ the least fixed point is the ideal of degrees arithmetical in $\mathbf a$. To pass beyond this fixed point, we introduce a limit-uniformization operator. Although the ideal of finite jumps contains every $\mathbf 0^{(n)}$, it does not contain the uniform limit oracle $\mathbf 0^{(\omega)}=\deg_T\!\left(\bigoplus_{n < \omega}0^{(n)}\right)$. The uniformization operator adjoins this oracle only when all finite jump degrees are present. It is monotone but not Scott-continuous. Composing jump closure with one such gate yields closure ordinal $\omega\cdot 2$; gates at $\omega,2\omega,3\omega,\ldots$ yield closure ordinal $\omega^2$. Thus non-uniform closure under relativized halting problems is Scott-continuous and reaches fixed ideals, while uniform coding of an entire prior hierarchy is infinitary, discontinuous, and reopens diagonalization. This gives a domain-theoretic semantics for the successor/limit distinction in transfinite Turing-jump hierarchies and links failures of Scott continuity with closure ordinals.

We give an example of a coherent theory, a topological space, and a continuous assignment of the (model-theoretic) types of the theory to the points of the space, such that there is no sheaf model of the theory over the space with the property that the fibre over a point, as a set-based model, realises the corresponding type; thus, we answer in the negative a problem posed by Kristóf Kanalas.

We study multipartite hypergraphs definable in $1$-semi-equational theories and prove almost-linear Zarankiewicz bounds in every fixed arity $r\geq2$. If $T$ is a $1$-semi-equational theory, then, for every formula $\varphi$ and fixed $t,r\geq2$, there is a constant $c$ such that each $K_{t,\ldots,t}$-free $r$-partite hypergraph defined by $\varphi$ on $n$ vertices has $O_{T,\varphi,t,r}\!\left( n^{r-1}(1+\log(1+n))^c \right) $ edges. Put $\alpha_k=\min\{k-1,2\}$. In the bipartite case, a Boolean combination of $m$ $(k,1)$-semi-equations has $ O_{k,t,m}\!\left( n(1+\log(1+n))^{(m-1)\alpha_k} \right) $ edges whenever it is $K_{t,t}$-free. In particular, a relation defined by one $(k,1)$-semi-equation or its negation has a linear bound. The proofs combine incidence estimates for indexed set systems with low-crossing orderings of finite $k$-wise laminar families. Consequently, no $1$-semi-equational theory locally trace-defines an infinite domain.

The thin set theorem $\mathsf{RT}_{<\infty,\ell}^{n}$ asserts that for every natural number $k$, each coloring $c\colon[\mathbb{N}]^n \to \{0,1,\dots,k-1\}$ admits an infinite set $H$ such that $|c([H]^n)| \le \ell$. Within the framework of the reverse mathematics of second-order arithmetic, $\mathsf{RT}_{<\infty,\ell}^{n}$ implies the $\Sigma_{n+1}^{0}$-bounding principle ($\mathsf{B}\Sigma_{n+1}^{0}$) over $\mathsf{RCA}_0$ for all natural numbers $n, \ell \ge 1$.

We prove that for any countable ring $R$ (not necessarily commutative), if the associated left $R$-module ${}_R R$ has a strictly descending sequence of pp-definable subgroups, then the theory $Th(R^{(\omega)})$ of the infinite dimensional direct sum is Borel complete. From this, we conclude that if $R$ is countable and not left perfect, then the theory of $R$-modules is Borel complete, and we give a full characterization of which countable simple rings have Borel complete theories. One special case is that the complete theory $Th({\mathbb Z}^{(\omega)})$ is Borel complete, which strengthens the existing proofs of the Borel completeness of TFAB, the theory of torsion free abelian groups. The proof also introduces, relative to the chosen pp-chain, a proper two-sided ideal $L^R$, and a notion of f.g. hulls which, for countable rings and countable parameter sets in theories satisfying $T=T^{\aleph_0}$ exist and are unique up to isomorphism. These constructions may be of independent interest in the model theory of modules.