Skip to main content
archive Search
Submit Donate Log in

Press Enter to search · Advanced search

Logic

  • New submissions
  • Cross-lists
  • Replacements

See recent articles

Showing new listings for Monday, 16 November 2026

Total of 17 entries
Showing up to 2000 entries per page: fewer | more | all

New submissions (showing 6 of 6 entries)

[1] arXiv:2611.17475 [pdf, html, other]
Title: Forcing global $Π^2_n$ uniformization with or without projective determinacy
Stefan Hoffelner
Subjects: Logic (math.LO)

We construct a set-forcing extension of $L$ which has the same reals as $L$ and satisfies the $\Pi^2_n$-uniformization property for every $n\geq1$. Assuming $\omega$ Woodin cardinals and a measurable cardinal above them, we also obtain a forcing extension of $L(\mathbb R)^{M_\omega}$ which has the same reals and satisfies projective determinacy together with the $\Pi^2_n$-uniformization property for every $n\geq1$.

[2] arXiv:2611.17643 [pdf, html, other]
Title: A large ultrafilter number at $\aleph_ω$
Fanxin Wu
Subjects: Logic (math.LO)

Gitik constructed a model where $\aleph_\omega$ is strong limit, $2^{\aleph_\omega}=\aleph_{\omega+2}$ and every strongly uniform ultrafilter on $\aleph_\omega$ has character $\aleph_{\omega+2}$. We show that in fact every uniform ultrafilter on $\aleph_\omega$ has character $\aleph_{\omega+2}$ in that model.

[3] arXiv:2611.17884 [pdf, html, other]
Title: HOL in HOL: mechanized soundness, completeness and consistency, with and without infinity
Christoph Benzmüller (Otto-Friedrich-Universität Bamberg and Freie Universität Berlin), Daniel Kirchner (Otto-Friedrich-Universität Bamberg)
Comments: 23 pages, 1 figure. Formal proof artifacts: Archive of Formal Proofs entries HOL_in_HOL_Deep and HOL_in_HOL_Deep_Infinity_ZFC (Isabelle2026). Submitted
Subjects: Logic (math.LO); Logic in Computer Science (cs.LO)

What can a logic certify about a copy of itself? For Church's simple theory of types, formalized as a deep embedding in Isabelle/HOL with Henkin semantics and a natural-deduction calculus, the answer has two tiers. On the first tier, plain Isabelle/HOL certifies the logic without an axiom of infinity, by a standard model with one individual. On the second tier, the logic with a Dedekind-style axiom of infinity is certified only in Isabelle/HOL extended by a large enough set-theoretic universe. Both tiers appear in Harrison's self-verification of HOL Light. What the present formalization adds is Henkin completeness, and with it a semantics that matches the calculus exactly, compactness and model existence on the first tier, and the boundary between the tiers. Comparing two ways of adding infinity to the object logic shows where the boundary lies. One is an infinite domain of individuals, expressed by the first-order sentences "there are at least $n$ individuals", each of which has a finite model; the other is the Dedekind axiom, a single sentence with no finite model, and there the first tier ends. In the calculus the axiom is strictly stronger than the sentences together: it derives each of them, but they do not derive it. The witness is a countable Henkin model in which every sentence holds and the axiom fails, because its function domain is too sparse for an injective, non-surjective self-map. On the second tier, the universe serves one purpose only: to prove the Dedekind axiom consistent. Everything that follows, completeness and even the countable Henkin model of the axiom, is obtained in plain Isabelle/HOL. The universe axiom is Harrison-style, realized in Paulson's ZFC_in_HOL with the domain of every type in $V_{\omega+\omega}$; with it, full classical higher-order logic with infinity and relational choice is consistent relative to set theory.

[4] arXiv:2611.18011 [pdf, html, other]
Title: Higher derived limits, Kurepa families and Chang's Conjecture
Dianthe Basak, Matteo Casarosa, Chris Lambie-Hanson, Pedro Marun, Boban Velickovic, Alessandro Vignati
Comments: 37 pages
Subjects: Logic (math.LO)

We investigate the interplay between homological algebra and combinatorial set theory, specifically focusing on the (non)vanishing of higher derived limits of certain inverse systems of abelian groups, denoted $\mathbf C_{[\kappa]^\lambda}$, indexed by the ordered sets $([\kappa]^{\lambda},\subseteq)$, where $\lambda < \kappa$ are infinite cardinals.
Our first main result is a general structural theorem which provides a generalisation of Goblot's theorem to the setting of locally small directed sets. We then present the first systematic study of generalised cofinal Kurepa families. We establish their existence in the constructible universe $L$ and under specific cardinal arithmetic hypotheses. Then, we apply our structural result to show that $\mathrm{lim}^{n+2} \mathbf{C}_{[\kappa]^{\aleph_n}} = 0$ in environments where the appropriate cofinal Kurepa families exist.
In contrast, we explore conditions that force these derived limits to be nonzero. In particular, we prove that certain instances of Chang's conjecture (CC), together with the existence of suitable $\diamondsuit$ sequences, imply that $\mathrm{lim}^{n+2} \mathbf{C}_{[\kappa]^{\aleph_n}} \neq 0$ for appropriate values of $\kappa$. Adapting forcing techniques from Eskew and Hayut, we construct models of these instances of CC together with the required $\diamondsuit$ sequences, establishing the consistency, for each $n \in \mathbb{N}$, of $\mathrm{lim}^{n+2} \mathbf{C}_{[\aleph_{\omega_n}]^{\aleph_n}} \neq 0$.

[5] arXiv:2611.18300 [pdf, html, other]
Title: Arithmetical and set-theoretic semantics of the logic of problems and propositions
Anastasia Onoprienko, Nikolay Vereshchagin
Subjects: Logic (math.LO)

Kolmogorov interpreted intuitionistic logic as a calculus of problems and later remarked that a complete treatment should deal with problems and propositions together. Melikhov's logic HC is such a joint two-sorted system: it combines classical propositions with intuitionistic problems by means of two modalities, the problem !A (``find a proof of the proposition A'') and the proposition phi (``the problem phi has a solution''). We give the language of HC a formal semantics in which the modalities are read literally: solutions of !A are proofs of A in a fixed formal theory, ?phi states that phi has a solution, and the connectives on problems are interpreted as in Kleene realizability. Three variants are studied: the arithmetical semantics I (provability in PA), its external version E (truth in the standard model), and the set-theoretic semantics B over ZF, where problem variables are ``black boxes'' and a quantifier Pi over them is available. Validity is defined as the existence of a computable uniform solution. We determine which schemes are valid, build calculi HCI, HCE, HCB sound with respect to the three semantics, and derive Lob's scheme from the fixed-point lemma inside the common core of our calculi and HC. The propositional fragments of HCI and HCE are exactly the provability logics GL and GLS; the positive modality-free fragment of valid problems is intuitionistic logic, while the full modality-free fragment lies strictly above it (Rose's formula is valid, Scott's principle is not). We compare the calculi with HC, which turns out to be incompatible with fixed points, prove independence results and list open questions.

[6] arXiv:2611.18383 [pdf, html, other]
Title: Self-Interpretations and Kraj\'ı{č}ek-Theories
Albert Visser
Subjects: Logic (math.LO)

We study self-interpretations of theories and their connection to Kraj\'ıček-theories. Our two main results are the following. Firstly, if the self-interpretations of a theory form a group in the category ${\sf INT}_3$ of theories and interpretations, then the theory is a Kraj\'ıček-theory. Secondly, a sequential theory is a Kraj\'ıček-theory iff all its self-interpretations are initial. Here initiality of the interpretation $K$ means roughly that its internal interpretations of the weak theory ${\sf S}^1_2$ are initial in all interpretations of ${\sf S}^1_2$.

Cross submissions (showing 4 of 4 entries)

[7] arXiv:2611.17446 (cross-list from math.OA) [pdf, html, other]
Title: Effectively nuclear C*-algebras
Christopher J. Eagle, Isaac Goldbring, Timothy H. McNicholl, Russell Miller
Comments: 30 pages. Comments welcome!
Subjects: Operator Algebras (math.OA); Logic (math.LO)

We study the computable content of nuclearity for $C^*$-algebras. We show that nuclearity effectivizes automatically: a presentation of a $C^*$-algebra is effectively nuclear, in the sense that the completely positive approximations witnessing nuclearity can be computed uniformly from the data they approximate, if and only if it is a computable presentation of a nuclear $C^*$-algebra, and likewise for the effectivization of the Choi--Effros form of nuclearity. The main tool is an effective version of the Arveson extension theorem: we prove that the $n$-th matrix numerical range of a tuple from a computable presentation is computably compact, uniformly in all of its data, and deduce an algorithm which converts an approximately attainable tuple of matrices into a computable unital completely positive map attaining it. A byproduct is that the computable states of any computable presentation of a unital $C^*$-algebra are weak$^*$-dense in its state space.
We also prove that the Cuntz algebras $\mathcal{O}_n$ are computably categorical and obtain an effective form of Kirchberg--Phillips absorption. By contrast with the conditions above, we do not know whether every computable presentation of a nuclear $C^*$-algebra admits a computable embedding into $\mathcal{O}_2$ with a computable conditional expectation; we answer this affirmatively for commutative $C^*$-algebras, for AF algebras, and, by a dynamical argument using invariant states, for the group $C^*$-algebras of a class of amenable groups including all finitely presented residually finite ones. Finally, we show that the set of indices of computable presentations of nuclear $C^*$-algebras is $\Pi^0_2$, and that the corresponding set for c.e. presentations is $\Pi^0_2$-hard; the latter rests on a result of independent interest, namely that amenability of computable groups is $\Pi^0_2$-complete within the class of computable groups.

[8] arXiv:2611.17546 (cross-list from math.RA) [pdf, html, other]
Title: Weak Generators in Stable Module Categories
Christian Lomp
Comments: comments are welcome
Subjects: Rings and Algebras (math.RA); Logic (math.LO)

The aim of this note is to show that the existence of weak generators in the stable module category of a ring, or equivalently, of $p$-indigent modules in the terminology of Holston et al., depends on the underlying model of set theory.

[9] arXiv:2611.18328 (cross-list from math.OA) [pdf, html, other]
Title: Matrix ultraproducts have trivial fundamental group
Hiroshi Ando, Isaac Goldbring
Comments: 43 pages; first draft; comments welcome!
Subjects: Operator Algebras (math.OA); Logic (math.LO); Representation Theory (math.RT)

We prove that every tracial ultraproduct $\prod_{\mathcal{U}} M_n(\mathbb{C})$ of matrix algebras has trivial fundamental group. In particular, this establishes that there are uncountably many nonisomorphic matrix ultraproducts, answering a question of Sorin Popa. We actually prove the stronger result that every matrix ultraproduct has trivial first-order fundamental group and thus our techniques are model-theoretic in nature.

[10] arXiv:2611.18541 (cross-list from math.RA) [pdf, html, other]
Title: No free lattice contains an infinite ascending chain of copies of FL(3)
William DeMeo, Ralph Freese
Comments: 59 pages, 13 figures; the main theorem is checked in Agda; the formal development is available at this https URL
Subjects: Rings and Algebras (math.RA); Logic in Computer Science (cs.LO); Group Theory (math.GR); Logic (math.LO)

No free lattice contains an infinite strictly ascending chain of sublattices isomorphic to FL(3), the free lattice on three generators; this answers a question that R. A. Dean asked and the second author's 1997 notes on the problem left open. Every such chain would yield, inside FL(3), a coherent chain of proper self-embeddings $\Theta_0, \Theta_1, \Theta_2, \dots$ with $\Theta_k \circ \Theta_j = \Theta_j$ for $j < k$, so that each later embedding fixes the image of each earlier one pointwise. Every proper self-embedding of FL(3) whose fixed sublattice contains a free generating triple fixes one of the three generators, say $z$, because a power of it or of its dual lies above the identity, and a self-embedding that moves every generator and lies above the identity fixes at most eleven elements. Up to duality, a proper self-embedding fixing the image of such a $\Theta_1$ pointwise fixes only elements above $z \wedge (x \vee y)$, where no free generating triple containing $z$ can lie. We also verify the one-step example of the 1997 notes, prove that no step toward such a chain is self-similar, and show that the configuration the argument rules out at length three does occur at length two.
Without freeness the answer reverses: FL(3) contains an infinite strictly ascending chain of 3-generated sublattices, so the lattice analogue of Takahasi's chain condition for free groups fails. The theorem itself is checked by the Agda proof assistant under its safe flags, for free lattices over generators with decidable equality, and its formal proof uses no classical principle: finite searches and an induction on a finite set replace the infinite pigeonhole principle by which a chain yields a coherent chain.

Replacement submissions (showing 7 of 7 entries)

[11] arXiv:2611.05656 (replaced) [pdf, html, other]
Title: Every obstruction to noncontextual hidden variables is finite: well-founded refutations in infinitary real-valued logic
Olivia Aubone, José Iovino
Subjects: Logic (math.LO)

We study the obstructions to noncontextual hidden variables when quantum probability is described in full, by the complete lattice of closed subspaces of a separable infinite-dimensional Hilbert space together with its countably additive measures. We give such a description in infinitary real-valued logic, the infinitary extension of Keisler's model theory of general structures; the countable suprema and infima of this logic express the completeness of the lattice and the countable additivity of the measures. The standard models of our axioms represent exactly the density-operator measures of Gleason's theorem. The axioms are closed conditions, non-strict inequalities between the values of sentences and rational numbers. The expressive power afforded by infinitary sentences comes at the price of compactness. The hypothesis that at each hidden state every event receives the value 0 or 1, whatever the context of measurement, contradicts the axioms, yet it is consistent with every finite subset of them. The obstructions nevertheless remain finite. We prove that in this logic a countable set of closed conditions is inconsistent if and only if a well-founded tree whose branches end in finite contradictions refutes it; for the hypothesis above, every such tree has an infinitely branching node. The finiteness theorem is therefore maximal: a hidden-variable hypothesis expressed by countably many closed conditions is inconsistent with the axioms, and thus an obstruction, exactly when such a tree refutes the hypothesis together with the axioms. The same language defines, uniformly across standard models, exactly the $\sigma$-projective sets of probabilities, and all these results are proved in ZFC.

[12] arXiv:2611.15620 (replaced) [pdf, html, other]
Title: Splitting Number at Singular Cardinals
Andrés F. Uribe-Zapata
Comments: 23 pages, 1 table. Minor typo corrections
Subjects: Logic (math.LO)

We study the splitting number at singular cardinals with emphasis on what we call the reduction to the cofinality problem: whether $\mathfrak{s}_{\kappa} = \mathfrak{s}_{\mathrm{cf}(\kappa)}$ holds for a singular cardinal $\kappa$. Our main tool is the transfinite logarithm function $\mathrm{log}_{2}(\mu) := \min \{ \lambda \in \mathrm{card} \colon \mu \leq 2^{\lambda} \}$ defined for every infinite cardinal $\mu$. We prove that the reduction holds, and in fact $\mathfrak{s}_{\kappa} = \mathrm{log}_{2}(\mathrm{cf}(\kappa))$, whenever $\mathrm{cf}(\kappa)$ is uncountable and not weakly compact. When $\mathrm{cf}(\kappa) = \aleph_{0}$, we show that $\mathfrak{s}_{\kappa} = \mathfrak{s}$ provided that $\mathfrak{s} \leq \log_{2}(\kappa)$, while the failure of the reduction is consistent with $\mathrm{ZFC}$. When $\mathrm{cf}(\kappa)$ is weakly compact, we use a model constructed by Ben-Neria and Gitik to prove that, under suitable large cardinals hypothesis, $\mathfrak{s}_{\kappa} < \mathfrak{s}_{\mathrm{cf}(\kappa)}$ is consistent. Furthermore, we show that the consistency strength of $\mathrm{ZFC} \, +$"$\exists \kappa \in \mathrm{card} [\mathrm{cf}(\kappa) > \aleph_{0} \wedge \mathfrak{s}_{\kappa} < \mathfrak{s}_{\mathrm{cf}(\kappa)}]$'' is at least that of the negation of the singular cardinal hypothesis. Finally, we study the cofinality of $\mathfrak{s}_{\kappa}$, extending several results about the cofinality of $\mathfrak{s}$ to the uncountable setting. In particular, we show in $\mathrm{ZFC}$ that there are regular cardinals $\kappa$ such that $\mathfrak{s}_{\kappa}$ is singular, partially answering an open question posed by Fischer and Soukup.

[13] arXiv:2601.21843 (replaced) [pdf, html, other]
Title: The Leibniz adjunction in homotopy type theory, with an application to simplicial type theory
Tom de Jong, Nicolai Kraus, Axel Ljungström
Comments: v4: Corrected links to Agda HTML. To appear at CSL 2027
Subjects: Category Theory (math.CT); Logic in Computer Science (cs.LO); Logic (math.LO)

Simplicial type theory extends homotopy type theory and equips types with a notion of directed morphisms. A Segal type is defined to be a type in which these directed morphisms can be composed. We show that all higher coherences can be stated and derived if simplicial type theory is taken to be homotopy type theory with a postulated interval type. In technical terms, this means that if a type has unique fillers for $(2,1)$-horns, it has unique fillers for all inner $(n,k)$-horns. This generalizes a result of Riehl and Shulman for the case $n = 3, k \in \{1, 2\}$. Our main technical tool is the Leibniz adjunction: the pushout-product is left adjoint to the pullback-hom in the wild category of types. While this adjunction is well known for ordinary categories, it is much more involved for higher categories, and the fact that it can be proved for the wild category of types (a higher category without stated higher coherences) is non-trivial. We make profitable use of the equivalence between the wild category of maps and that of families. We have formalized the results in Cubical Agda.

[14] arXiv:2605.13348 (replaced) [pdf, html, other]
Title: Adequate Losses via Quantitative Linear Logic
Matteo Capucci, Robert Atkey, Charles Grellois, Ekaterina Komendantskaya, Matthew Daggitt
Comments: Numerous tweaks and small corrections. To appear at POPL 2027
Subjects: Logic in Computer Science (cs.LO); Logic (math.LO)

As neural components are increasingly embedded in existing symbolic software -- including safety-critical systems -- the question arises of how to specify and enforce the safety of the newly introduced neural parts. Unlike traditional logical specifications, these must be amenable not only to the standard Boolean interpretation, but also to training and optimisation. The latter calls for a quantitative interpretation of the logical syntax, subject to further requirements such as smoothness and differentiability. Moreover, the qualitative and quantitative sides of the logic must share a unifying proof-theoretic and categorical semantics. Finally, the new logic should link cleanly to the substructural and program logics that underpin the verification of existing symbolic programs. In this paper, we present a logic that ticks all of these boxes. We introduce a family of calculi, $p$QLL, indexed by a hardness degree $p$, prove a cut-elimination theorem for them, and establish completeness with respect to enriched residuated `soft' lattices. At $p = \infty$, $p$QLL reduces to multiplicative additive linear logic (MALL), and provability in $p$QLL converges to provability in MALL as $p \to \infty$. We express optimisation objectives in the syntax of this logic and prove the quantitative adequacy of neuro-symbolic loss functions -- a result that has eluded the neuro-symbolic machine learning community for nearly a decade.

[15] arXiv:2610.16473 (replaced) [pdf, other]
Title: Some complete $ω$-powers of a one-counter language in the difference hierarchy
Jacques Duparc (UNIL), Olivier Finkel (IMJ-PRG (UMR\_7586)), Dominique Lecomte (IMJ-PRG (UMR\_7586))
Subjects: Logic in Computer Science (cs.LO); Computation and Language (cs.CL); Formal Languages and Automata Theory (cs.FL); Computer Science and Game Theory (cs.GT); General Topology (math.GN); Logic (math.LO)

Fix a finite alphabet $\Sigma$ having at least two letters, and natural numbers $n,k\geq 1$. We denote by $D_n(\mathbf{\Pi}^0_k)$ the class of differences of $n$ subsets of the Cantor space $\Sigma^\omega$ in $\mathbf{\Pi}^0_k$, and by $D^-_n(\mathbf{\Pi}^0_k)$ the class of complements of sets in $D_n(\mathbf{\Pi}^0_k)$. We prove, for any natural numbers $n,k\geq 1$, the existence of a finite alphabet $\Sigma$ having at least two letters and a finitary language $U_{n,k}$ over $\Sigma$ accepted by a one-counter automaton such that the $\omega$-power $$U_{n,k}^\infty:=\{ w_0w_1\cdots\in\Sigma^\omega\mid\forall i\in\omega ~~w_i\in U_{n,k}\}$$ is $D_{2n-1}(\mathbf{\Pi}^0_k)$-complete. We also prove a conditional result for the dual classes $D^-_{2n}(\mathbf{\Pi}^0_k)$: under the assumption that there exists a finitary language $V_{n,3}$ accepted by a one-counter automaton, such that its $\omega$-power $V_{n,3}^\infty$ is $D^-_{2n}(\mathbf{\Pi}^0_3)$-complete, there would also exist, for any integer $k > 3$, a finitary language $V_{n,k}$ accepted by a one-counter automaton, such that its $\omega$-power $V_{n,k}^\infty$ is $D^-_{2n}(\mathbf{\Pi}^0_k)$-complete. Finally we add another conditionnal result about Wadge degrees of rational $\mathbf{\Delta}^0_2$ omega powers, which completes the recent results of [FGL26].

[16] arXiv:2610.29771 (replaced) [pdf, html, other]
Title: Logics vs doctrines, a mirror symmetry
Ivan Di Liberti, Umberto Tarantino, Lingyuan Ye
Comments: Corrected minor mistakes and introduced the notion of tightness in Section 5
Subjects: Category Theory (math.CT); Logic in Computer Science (cs.LO); Logic (math.LO)

We study the relationship between doctrines, encoding 2-categories of theories in predicate logic, and fragments of geometric logic, defined through Kan injectivity in the 2-category of topoi. After a brief historical account of the notion of doctrine, we propose our working definition. Our main result then establishes a Galois connection between doctrines and subgeometric logics. This connection suggests a mirror symmetry between the world of doctrines and the world of logics, in which constructions and results on either side admit counterparts on the other. We develop this symmetry through constructions of syntactic categories and classifying topoi in both settings, recovering the familiar examples from categorical logic. We prove paired Diaconescu-type theorems and give symmetric descriptions of the two closure operators induced by the Galois connection. Finally, we characterise when passing from a doctrine to its closure induces a reflection between the corresponding 2-categories of algebras, and we relate this reflection to conceptual completeness.

[17] arXiv:2611.14605 (replaced) [pdf, html, other]
Title: $\mathbb Z$ is diophantine over $\mathbb Q$ with 26 unknowns
Zhi-Wei Sun
Comments: 39 pages. Reduce 28 variables to 26 variables, and add Theorem 1.2
Subjects: Number Theory (math.NT); Logic (math.LO)

Recently, OpenAI proved that Hilbert's Tenth Problem over the field $\mathbb Q$ of rational numbers has a negative solution. Motivated by this work, G. Conant et al. showed that $\mathbb Z$ is diophantine over $\mathbb Q$, i.e., there is an integer-coefficient polynomial $F(x,y_1,\ldots,y_n)$ such that for any $x\in\mathbb Q$ we have $$ x\in\mathbb Z\quad\iff \exists\,y_1,\ldots,y_{n}\in\mathbb Q\ [F(x,y_1,\ldots,y_{n})=0].$$ They constructed such a polynomial $F$ with $°F=4$ and $n=221$.In this paper, we prove the existence of such a polynomial $F$ with $n=26$. We also show that $16$ existential unknowns suffice under the $abc$-conjecture.

Total of 17 entries
Showing up to 2000 entries per page: fewer | more | all
We gratefully acknowledge support from our major funders, member institutions, , and all contributors.
About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab)