pith. sign in

arxiv: 1907.02769 · v1 · pith:XRZDCPKKnew · submitted 2019-07-05 · 🧮 math.LO · cs.LO

A comparison of various analytic choice principles

Paul-Elliot Angl\`es d'Auriac , Takayuki Kihara This is my paper

Pith reviewed 2026-05-25 01:58 UTC · model grok-4.3

classification 🧮 math.LO cs.LO
keywords analytic choice principlesWeihrauch degreesMedvedev latticeΣ¹₁ setsdescriptive set theorycomputability theoryparallelizationchoice on integers
0
0 comments X

The pith

The parallelization of the Σ¹₁-choice principle on the integers receives a definite Weihrauch degree via analysis of the Medvedev lattice of Σ¹₁-closed sets.

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

The paper compares analytic choice principles by examining their contents inside the Medvedev lattice of Σ¹₁-closed sets. This lattice encodes how computably hard each principle is when viewed as a multi-valued function on reals. The central result determines the Weihrauch degree of the parallelized version of Σ¹₁-choice on the integers, settling an open question. The argument relies on Harrington's result about jump hierarchies along pseudo-well-orderings to separate degrees in the lattice. Knowing this degree lets one locate the principle relative to other analytic choice principles in the Weihrauch ordering.

Core claim

By carrying out a detailed analysis inside the Medvedev lattice of Σ¹₁-closed sets, the authors establish the Weihrauch degree of the parallelization of the Σ¹₁-choice principle on the integers and thereby solve the open problem; Harrington's unpublished result on a jump hierarchy along a pseudo-well-ordering supplies the key separation.

What carries the argument

The Medvedev lattice of Σ¹₁-closed sets, which organizes the computability contents of analytic choice principles so that Weihrauch degrees become comparable.

If this is right

  • The relative Weihrauch strengths of several analytic choice principles become comparable once the parallelized Σ¹₁-choice degree is fixed.
  • The same lattice analysis yields positions for non-parallelized versions and for choice on other spaces.
  • The result extends the known diagram of degrees for Σ¹₁ principles by one new node.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar lattice techniques might classify parallelizations of choice principles at higher levels such as Π¹₁ or Σ¹₂.
  • The dependence on an unpublished hierarchy result suggests that effective descriptive set theory could benefit from publishing or reproving that hierarchy in greater detail.
  • If the lattice separations hold, one obtains new examples of Weihrauch degrees that are not realized by any continuous functional on Polish spaces.

Load-bearing premise

Harrington's unpublished result on a jump hierarchy along a pseudo-well-ordering is available and applies correctly to the Medvedev-degree analysis of the parallelized Σ¹₁-choice principle.

What would settle it

An explicit Weihrauch reduction showing that the parallelized Σ¹₁-choice principle on the integers is equivalent to a degree other than the one obtained from the lattice analysis would falsify the claimed degree.

read the original abstract

We investigate computability theoretic and descriptive set theoretic contents of various kinds of analytic choice principles by performing detailed analysis of the Medvedev lattice of $\Sigma^1_1$-closed sets. Among others, we solve an open problem on the Weihrauch degree of the parallelization of the $\Sigma^1_1$-choice principle on the integers. Harrington's unpublished result on a jump hierarchy along a pseudo-well-ordering plays a key role in solving the problem.

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

1 major / 0 minor

Summary. The paper analyzes the computability-theoretic and descriptive set-theoretic content of analytic choice principles through a detailed study of the Medvedev lattice of Σ¹₁-closed sets. It claims to solve an open problem by determining the Weihrauch degree of the parallelization of the Σ¹₁-choice principle on the integers, with Harrington's unpublished result on jump hierarchies along pseudo-well-orderings serving as the key tool for the Medvedev-degree analysis.

Significance. If the central claim holds, the resolution of an open Weihrauch-degree question for a parallelized analytic choice principle would be a notable contribution to the study of choice principles in computable analysis and descriptive set theory. The manuscript's strength lies in its systematic comparison of various analytic choice principles via the Medvedev lattice, but the dependence on an external unpublished result limits the immediate verifiability and self-contained impact of the main theorem.

major comments (1)
  1. [Abstract and the section presenting the solution to the open problem on the Weihrauch degree] The central claim (resolution of the Weihrauch degree of the parallelization of Σ¹₁-choice on ℤ) rests on the applicability of Harrington's unpublished result on a jump hierarchy along a pseudo-well-ordering to the Medvedev-degree analysis of the parallelized principle. This result is invoked as the key tool but is neither derived nor referenced to a published source, so the precise manner of its application cannot be verified from the manuscript text alone.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for highlighting the issue of verifiability in our main result. We address the single major comment below.

read point-by-point responses

  1. Referee: [Abstract and the section presenting the solution to the open problem on the Weihrauch degree] The central claim (resolution of the Weihrauch degree of the parallelization of Σ¹₁-choice on ℤ) rests on the applicability of Harrington's unpublished result on a jump hierarchy along a pseudo-well-ordering to the Medvedev-degree analysis of the parallelized principle. This result is invoked as the key tool but is neither derived nor referenced to a published source, so the precise manner of its application cannot be verified from the manuscript text alone.

    Authors: We agree that the manuscript would be strengthened by a clearer exposition of how Harrington's result is applied. In the revised version we will expand the relevant section with an additional subsection that (i) recalls the precise statement of the jump-hierarchy result used, (ii) specifies the pseudo-well-ordering constructed for the parallelized Σ¹₁-choice instance, and (iii) walks through the Medvedev-reduction steps that rely on the hierarchy. This will make the logical connection explicit without deriving the unpublished theorem itself. revision: partial

Circularity Check

0 steps flagged

No circularity; derivation relies on external unpublished result rather than self-referential reduction

full rationale

The paper's central claim solves an open Weihrauch-degree problem by applying Harrington's unpublished jump-hierarchy result to the Medvedev-degree analysis of parallelized Σ¹₁-choice. This is an external input, not a self-citation chain, fitted parameter renamed as prediction, or any of the enumerated circular patterns. No equations or definitions in the provided text reduce the solved degree to the paper's own constructions by construction. The result is therefore not circular, though it is not self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Abstract supplies insufficient detail to enumerate concrete free parameters or invented entities; the work rests on standard background from descriptive set theory and computability plus one unpublished result.

axioms (2)
  • standard math Standard facts about the Medvedev lattice of Σ¹₁-closed sets and Weihrauch reducibility hold.
    Invoked throughout the comparison of choice principles.
  • domain assumption Harrington's result on jump hierarchies along pseudo-well-orderings is correct and applicable.
    Cited as the key tool for solving the open problem.

pith-pipeline@v0.9.0 · 5600 in / 1294 out tokens · 23224 ms · 2026-05-25T01:58:01.646246+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    Con tinuous higher randomness

    Laurent Bienvenu, Noam Greenberg, and Benoit Monin. Con tinuous higher randomness. J. Math. Log., 17(1):1750004, 53, 2017

    work page 2017

  2. [2]

    Borel choice

    Vasco Brattka, Guido Gherardi, Rupert H¨ olzl, Hugo Nobr ega, and Arno Pauly. Borel choice. in preparation

    work page

  3. [3]

    W eihrauc h complexity in computable anal- ysis

    Vasco Brattka, Guido Gherardi, and Arno Pauly. W eihrauc h complexity in computable anal- ysis. arXiv 1707.03202, 2017

    work page arXiv 2017

  4. [4]

    On the algebraic structure of Weihrauch degrees

    Vasco Brattka and Arno Pauly. On the algebraic structure of Weihrauch degrees. arXiv 1604.08348, 2016

    work page arXiv 2016

  5. [5]

    Douglas Cenzer and Peter G. Hinman. Density of the Medved ev lattice of Π 0 1 classes. Arch. Math. Logic, 42(6):583–600, 2003

    work page 2003

  6. [6]

    Subsystems of analysis

    Harvey Friedman. Subsystems of analysis . PhD thesis, Massachusetts Institute of Technology, ProQuest LLC, Ann Arbor, MI, 1968

    work page 1968

  7. [7]

    Uniformly defined descending sequence s of degrees

    Harvey Friedman. Uniformly defined descending sequence s of degrees. J. Symbolic Logic , 41(2):363–367, 1976

    work page 1976

  8. [8]

    On Harrington’s unpublished result, 2018

    Jun Le Goh. On Harrington’s unpublished result, 2018. in preparation

    work page 2018

  9. [9]

    Some computability-theoretic reductions be tween principles around ATR0, 2018

    Jun Le Goh. Some computability-theoretic reductions be tween principles around ATR0, 2018. in preparation

    work page 2018

  10. [10]

    Classes of Polish spaces under effective Borel isomorphism

    Vassilios Gregoriades. Classes of Polish spaces under effective Borel isomorphism. Mem. Amer. Math. Soc. , 240(1135):vii+87, 2016

    work page 2016

  11. [11]

    A. Kechris. Classical Descriptive Set Theory . Springer-Verlag, 1995

    work page 1995

  12. [12]

    Searc hing for an analogue of ATR 0 in the Weihrauch lattice, 2018

    Takayuki Kihara, Albert Marcone, and Arno Pauly. Searc hing for an analogue of ATR 0 in the Weihrauch lattice, 2018. in preparation

    work page 2018

  13. [13]

    Dividing by Zero – How Ba d Is It, Really? In Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier, editors , 41st Int

    Takayuki Kihara and Arno Pauly. Dividing by Zero – How Ba d Is It, Really? In Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier, editors , 41st Int. Sym. on Mathemat- ical Foundations of Computer Science (MFCS 2016) , volume 58 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 58:1–58:14. Schloss Dagstuhl, 2016

    work page 2016

  14. [14]

    Yu. T. Medvedev. Degrees of difficulty of the mass problem . Dokl. Akad. Nauk SSSR (N.S.) , 104:501–504, 1955

    work page 1955

  15. [15]

    Moschovakis

    Yiannis N. Moschovakis. Descriptive set theory , volume 155 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, second ed ition, 2009

    work page 2009

  16. [16]

    S. Simpson. Subsystems of Second Order Arithmetic . Perspectives in Logic. Cambridge Uni- versity Press, 2009

    work page 2009

  17. [17]

    Descending sequences of degrees

    John Steel. Descending sequences of degrees. J. Symbolic Logic , 40(1):59–61, 1975

    work page 1975

  18. [18]

    John R. Steel. A note on analytic sets. Proc. Amer. Math. Soc. , 80(4):655–657, 1980

    work page 1980

  19. [19]

    The hyperarithmetical axiom of choic e HAC and its companions

    Kazuyuki Tanaka. The hyperarithmetical axiom of choic e HAC and its companions. S¯ urikaisekikenky¯ usho K¯ oky¯ uroku, (1301):79–83, 2003. Sequent calculi and proof theory (Japanese) (Kyoto, 2002). A COMPARISON OF V ARIOUS ANALYTIC CHOICE PRINCIPLES 27 LACL, D ´epartement d’Informatique, F acult´e des Sciences et Technologie, 61 avenue du G ´en´eral de G...

    work page 2003