pith. sign in

arxiv: 2411.07792 · v2 · submitted 2024-11-12 · 🧮 math.LO

Chains and antichains in the Weihrauch lattice

Steffen Lempp , Alberto Marcone , Manlio Valenti This is my paper

Pith reviewed 2026-05-23 17:51 UTC · model grok-4.3

classification 🧮 math.LO
keywords Weihrauch degreeschainsantichainscofinalitycoinitial sequencescontinuum hypothesisreducibilitylattice
0
0 comments X

The pith

There are no cofinal chains of any order type in the Weihrauch degrees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper maps the order structure of the Weihrauch degrees by examining long chains and antichains. It establishes that every chain is bounded above by some degree. It further shows that a descending sequence of nonzero degrees that is coinitial exists exactly when the continuum hypothesis holds. The results also give necessary conditions for an antichain to be maximal under extension.

Core claim

No chain of Weihrauch degrees, of any order type, is cofinal in the lattice. The existence of coinitial sequences of nonzero degrees is equivalent to the continuum hypothesis. Necessary conditions are supplied for the extendibility of antichains to maximal ones.

What carries the argument

The Weihrauch lattice ordered by reducibility, which classifies problems by whether one can be solved using a computable functional applied to an oracle for the other.

Load-bearing premise

The results depend on the standard definition of Weihrauch reducibility being studied inside ZFC set theory.

What would settle it

Constructing an explicit cofinal chain of Weihrauch degrees, or exhibiting a model of ZFC plus the negation of CH that still contains a coinitial sequence of nonzero degrees, would refute the central claims.

read the original abstract

We study the existence and the distribution of "long" chains in the Weihrauch degrees, mostly focusing on chains with uncountable cofinality. We characterize when such chains have an upper bound and prove that there are no cofinal chains (of any order type) in the Weihrauch degrees. Furthermore, we show that the existence of coinitial sequences of non-zero degrees is equivalent to $\mathrm{CH}$. Finally, we explore the extendibility of antichains, providing some necessary conditions for maximality.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper studies the existence and distribution of long chains (especially those with uncountable cofinality) in the Weihrauch degrees. It characterizes when such chains possess upper bounds, proves that no cofinal chains of any order type exist in the Weihrauch degrees, establishes that the existence of coinitial sequences of non-zero degrees is equivalent to CH, and provides necessary conditions for the extendibility and maximality of antichains.

Significance. If the central claims hold, the results supply key structural facts about the Weihrauch lattice: the absence of cofinal chains limits possible embeddings and order-theoretic constructions, while the CH-equivalence for coinitial sequences demonstrates explicit set-theoretic sensitivity. The antichain results add to the lattice's combinatorial description. The work rests on the standard definition of Weihrauch reducibility inside ZFC and supplies falsifiable, axiom-sensitive statements.

minor comments (3)
  1. §1: the phrase 'long chains' is used informally before the formal definition of cofinality; a brief parenthetical gloss would improve readability for readers outside the immediate subfield.
  2. The statement of the CH-equivalence (abstract and §4) would benefit from an explicit citation to the precise formulation of Weihrauch reducibility employed, even though it is standard.
  3. Notation for the Weihrauch degrees (e.g., the symbol for the lattice order) is introduced without a dedicated 'Notation' paragraph; collecting the main symbols in one place would aid cross-reference.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report and recommendation to accept the manuscript. The summary accurately captures the main results on chains and antichains in the Weihrauch degrees.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained in ZFC

full rationale

The paper presents standard mathematical proofs about Weihrauch reducibility inside ZFC, characterizing chains and antichains with explicit axiom-sensitivity only for the CH equivalence. No self-definitional reductions, fitted parameters renamed as predictions, load-bearing self-citations, or ansatzes smuggled via prior work appear. All claims rest on the external, independently defined notion of Weihrauch reducibility and set-theoretic reasoning that does not reduce to the paper's own inputs by construction. This is the expected outcome for a pure logic paper with no data-fitting or definitional circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on ZFC set theory and the established definition of the Weihrauch lattice; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math ZFC set theory
    Standard foundation used for all set-theoretic arguments about order types and cardinalities.
  • domain assumption Definition of Weihrauch reducibility and the induced lattice
    The lattice structure and its basic properties are taken from prior literature on Weihrauch degrees.

pith-pipeline@v0.9.0 · 5608 in / 1274 out tokens · 39554 ms · 2026-05-23T17:51:33.486351+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [1]

    Andrews, Uri, Lempp, Steffen, Marcone, Alberto, Miller, Joseph S., and Valenti, Manlio, A jump operator on the Weihrauch degrees , Submitted, 2024

    work page 2024

  2. [2]

    Brattka, Vasco, Gherardi, Guido, and Pauly, Arno, Weihrauch Complexity in Computable Anal- ysis, Handbook of Computability and Complexity in Analysis (Brattka, Vas co and Hertling, Peter, eds.), Springer International Publishing, Jul 2021, doi:10.1 007/978-3-030-59234-9 11, pp. 367–417. MR 4300761

    work page 2021

  3. [3]

    4, 1–36, doi:10.23638/LMCS-14(4:4)2018

    Brattka, Vasco and Pauly, Arno, On the algebraic structure of Weihrauch degrees , Logical Methods in Computer Science 14 (2018), no. 4, 1–36, doi:10.23638/LMCS-14(4:4)2018. MR 3868998

    work page doi:10.23638/lmcs-14(4:4)2018 2018

  4. [4]

    3, 321–340, doi:10.1070/SM1976v030n03ABEH00227 7

    Dyment, Elena Z., On Some Properties of the Medvedev Lattice , Mathematics of the USSR- Sbornik 30 (1976), no. 3, 321–340, doi:10.1070/SM1976v030n03ABEH00227 7. MR 0432433

    work page doi:10.1070/sm1976v030n03abeh00227 1976

  5. [5]

    Dzhafarov, Damir D., Some questions and observations about the structure of the W eihrauch degrees, New directions in computability theory, Luminy, France, 2022

    work page 2022

  6. [6]

    2:02, 1–17, doi:10.2168/LMCS-9(2:02)2013

    Higuchi, Kojiro and Pauly, Arno, The degree structure of Weihrauch reducibility , Logical Meth- ods in Computer Science 9 (2013), no. 2:02, 1–17, doi:10.2168/LMCS-9(2:02)2013. MR 30456 29

    work page doi:10.2168/lmcs-9(2:02)2013 2013

  7. [7]

    2, 161–229

    Hinman, Peter G., A survey of Muˇ cnik and Medvedev degrees, The Bulletin of Symbolic Logic 18 (2012), no. 2, 161–229. MR 2931672

    work page 2012

  8. [8]

    11, 4893–4901

    Lempp, Steffen, Miller, Joseph S., Pauly, Arno, Soskova, Mariya I ., and Valenti, Manlio, Min- imal covers in the Weihrauch degrees , Proceedings of the American Mathematical Society 152 (2024), no. 11, 4893–4901

    work page 2024

  9. [9]

    125 , Elsevier,

    Odifreddi, Piergiorgio, Classical Recursion Theory - The Theory of Functions and Set s of Nat- ural Numbers, 1 ed., Studies in Logic and the Foundations of Mathematics, vol. 125 , Elsevier,

    work page

  10. [10]

    MR 262080 15

    Platek, Richard A., A note on the cardinality of the Medvedev lattice , Proceedings of the Amer- ican Mathematical Society 25 (1970), 917, doi:10.2307/2036781. MR 262080 15

    work page doi:10.2307/2036781 1970

  11. [11]

    thesis, Cornell University, 2011, p

    Shafer, Paul, On the complexity of mathematical problems: Medvedev degre es and reverse math- ematics, Ph.D. thesis, Cornell University, 2011, p. 195. MR 2982190

    work page 2011

  12. [12]

    B., Slaman, T

    Sorbi, Andrea, The Medvedev Lattice of Degrees of Difficulty , Computability, Enumerability, Unsolvability (Cooper, S. B., Slaman, T. A., and Wainer, S. S., eds.), Lo ndon Math. Soc. Lecture Note Ser., vol. 224, Cambridge University Press, Cambridg e, New York, NY, USA, 1996, doi:10.1017/CBO9780511629167.015, pp. 289–312. MR 1395 886

    work page doi:10.1017/cbo9780511629167.015 1996

  13. [13]

    2, 543–558, doi:10.2178/jsl/1208359059

    Terwijn, Sebastiaan A., On the Structure of the Medvedev Lattice , The Journal of Symbolic Logic 73 (2008), no. 2, 543–558, doi:10.2178/jsl/1208359059. MR 241446 4 Steffen Lempp Department of Mathematics, University of Wisconsin - Madis on, Madison, Wisconsin 53706, USA Email address : lempp@math.wisc.edu Alberto Marcone Dipartimento di Scienze Matematiche...

    work page doi:10.2178/jsl/1208359059 2008