Lune

LICS2021Top-tier venue

On the logical structure of choice and bar induction principles

Nuria Brede, Hugo Herbelin

Abstract

We develop an approach to choice principles and their contrapositive bar-induction principles as extensionality schemes connecting an "intensional" or "effective" view of respectively ill- and well-foundedness properties to an "extensional" or "ideal" view of these properties. After classifying and analysing the relations between different intensional definitions of ill-foundedness and well-foundedness, we introduce, for a domain A, a codomain B and a "filter" T on finite approximations of functions from A to B, a generalised form GDCABT of the axiom of dependent choice and dually a generalised bar induction principle GBIABT such that:GDCABTintuitionistically captures the strength of·the general axiom of choice expressed as ∀a∃bR(a,b) ⇒ ∃α∀aR(a,α(a))) when T is a filter that derives point-wise from a relation R on A × B without introducing further constraints,·the Boolean Prime Filter Theorem / Ultrafilter Theorem if B is the two-element set (for a constructive definition of prime filter),·the axiom of dependent choice if A = ,·Weak Knig's Lemma if A = and B = (up to weak classical reasoning).GBIABTintuitionistically captures the strength ofGödel's completeness theorem in the form validity implies provability for entailment relations if B = (for a constructive definition of validity),·bar induction if A = ,·the Weak Fan Theorem if A = and B = .Contrastingly, even though GDCABT and GBIABTsmoothly capture several variants of choice and bar induction, some instances are inconsistent, e.g. when A is B is .

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

2 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Oracles Just for Fan: A Robust Computational Interpretation of the Fan Theorem cites The Blurred Drinker Paradox: Constructive Reverse Mathematics of the Downward Löwenheim-Skolem Theorem
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. The Blurred Drinker Paradox: Constructive Reverse Mathematics of the Downward Löwenheim-Skolem TheoremDominik Kirst, Haoyi ZengLICS 2025 · 3 citations
  2. Oracles Just for Fan: A Robust Computational Interpretation of the Fan TheoremTitouan Leclercq, Étienne MiqueyLICS 2026

Related papers

  1. From Co-Coverages to Radicals in Complete LatticesDaniel Misselbeck-WesselLICS 2026 · 2 citations
  2. On the computational content of Zorn's lemmaThomas PowellLICS 2020 · 3 citations
  3. Separating Markov's PrinciplesLiron Cohen, Yannick Forster, Dominik Kirst, Bruno da Rocha Paiva et al.LICS 2024 · 2 citations
  4. A direct computational interpretation of second-order arithmetic via update recursionValentin BlotLICS 2022 · 2 citations
  5. The Algebra of Iterative ConstructionsKevin Batz, Benjamin Lucien Kaminski, Lucas Kehrer, Gerwin Klein et al.LICS 2026
Dusk over the sea between two cliffs drawn in fine vertical lines