Blurred Drinker Paradoxes and Blurred Choice Axioms: Constructive Reverse Mathematics of the Downward Löwenheim-Skolem Theorem

Dominik Kirst ORCID:0000-0003-4126-6975, Haoyi Zeng ORCID:0009-0007-2506-3787 · 2026

Read Blurred Drinker Paradoxes and Blurred Choice Axioms: Constructive Reverse Mathematics of the Downward Löwenheim-Skolem Theorem by Dominik Kirst ORCID:0000-0003-4126-6975, Haoyi Zeng ORCID:0009-0007-2506-3787 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-12592.txt.

Introduction

Dominik Kirst and Haoyi Zeng work in constructive reverse mathematics on a classic theorem of logic. The downward Lowenheim Skolem theorem says every infinite model has a countable elementary submodel. Over classical base theories, it is known to match the axiom of dependent choice. Constructive logic, which demands explicit constructions, allows a finer split of such claims.

The pair refine that known equivalence with care. Assuming only countable choice, they split the theorem into finer parts. One part is dependent choice, and another is a new fragment of the excluded middle. Their title names playful tools in the proof: blurred drinker paradoxes and blurred choice axioms. The work shows how constructive analysis can dissect a theorem brick by brick.

Catalog record

CREATORDominik Kirst ORCID:0000-0003-4126-6975, Haoyi Zeng ORCID:0009-0007-2506-3787
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-12592

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Blurred Drinker Paradoxes and Blurred Choice Axioms: Constructive Reverse Mathematics of the Downward Löwenheim-Skolem Theorem Thanks: The first author received funding from the European Union’s Horizon research and innovation programme under the Marie Skłodowska-Curie grant agreement No.101152583 and a Minerva Fellowship of the Minerva Stiftung Gesellschaft für die Forschung mbH Dominik Kirst ORCID:0000-0003-4126-6975, Haoyi Zeng ORCID:0009-0007-2506-3787 Abstract . In the setting of constructive reverse mathematics, we analyse the downward Löwenheim-Skolem (DLS) theorem of first-order logic, stating that every infinite model has a countable elementary submodel. Refining the well-known equivalence of the DLS theorem to the axiom of dependent choice (DC) over classical base theories, our constructive approach allows for several finer logical decompositions: Just assuming countable choice (CC), the DLS theorem is equivalent to the conjunction of DC with a newly identified fragment of the excluded middle (LEM) that we call the blurred drinker paradox (BDP). Further without CC, the DLS theorem is equivalent to the conjunction of BDP with similarly blurred weakenings of DC and CC. Independently of their connection with the DLS theorem, we also study BDP and the blurred choice axioms on their own, for instance by showing that BDP is LEM without a contribution of Markov’s principle and that blurred DC is DC without a contribution of CC. The paper is hyperlinked with an accompanying Coq development. [a,b] [c] 1. Introduction The Löwenheim-Skolem theorem 1 1 1 Usually attributed to Löwenheim [ lowenheim1915moglichkeiten ] and Skolem [ Skolem1920-SKOLUB ] by name, but credit is also due to Maltsev [ Mal36 ] who in turn credits Tarski. is a central result about first-order logic, entailing that the formalism is incapable of distinguishing different infinite cardinalities. In particular the theorem’s so-called downward part, stating that every infinite model (over a countable signature) can be turned into a countably infinite model with otherwise the exact same behaviour, can be considered surprising or even paradoxical: 2 2 2 Discovered and discussed by Skolem [ skolem1922einige ] . See also the discussion by McCarty and Tennant [ mccarty1987skolem ] for a constructivist perspective. even axiom systems like ZF set theory, concerned with uncountably large sets like the reals or their iterated power sets, admit countable interpretations. This seeming contradiction in particular and its metamathematical relevance in general led to an investigation of the exact logical assumptions under which the downward Löwenheim-Skolem (DLS) theorem applies. From the perspective of (classical) reverse mathematics [ friedman1976systems , simpson2009subsystems ] , there is a definite answer: the DLS theorem is equivalent to the dependent choice axiom (DC), a weak form of the axiom of choice, stating that there is a path through every total relation [ boolos2002computability , espindolalowenheim , karagila2014downward ] . To argue the first direction, one can organise the usually iterative construction of the countable submodel such that a single application of DC yields the desired result. For the converse direction, one uses the DLS theorem to turn a given total relation R into a countable sub-relation R^{\prime} , applies a (classically available) instance of the axiom of countable choice (CC) to obtain a path f^{\prime} through R^{\prime} , which is then reflected back as a path f through R . In total, that is: \mathsf{DLS}~\leftrightarrow~\mathsf{DC} However, the classical answer is insufficient if one investigates the computational content of the DLS theorem, i.e. the question how effective the transformation of a model into a countable submodel really is. A more adequate answer can be obtained by switching to the perspective of constructive reverse mathematics [ ishihara_reverse_2006 , diener2018constructive ] , which is concerned with the analysis of logical strength over a constructive meta-theory, i.e. in particular without the law of excluded middle (LEM), stating that p\lor\neg p for all propositions p , and ideally also without CC [ richman2001constructive ] . In that setting, finer logical distinctions become visible and one can analyse the computational content of the DLS theorem by investigating two questions: (1) Does the DLS theorem still follow from DC alone, without any contribution of LEM? (2) Does the DLS theorem still imply all of DC, without any contribution of CC? \mathsf{DLS}\,(+\,\mathsf{CC})~\overset{?}{\leftrightarrow}~\mathsf{DC}\,(+\,\mathsf{LEM}) In this paper, after giving a fully constructive proof of a weak form of the DLS theorem sharing the same computational content as constructivised model existence theorems [ herbelin2024analysis , forster2020completeness ] , we observe that neither 1) nor 2) is the case. Instead, we clarify which exact fragment of LEM is needed on top of DC to prove the DLS theorem and, conversely, which exact fragment of DC it implies. Regarding (1), note that the DLS theorem requires LEM in the form of the drinker paradox: 3 3 3 Polularised as a logic puzzle by Smullyan [ smullyan1990name ] and studied in relation to other principles of constructive mathematics by Escardó and Oliva [ escardo2010searchable ] . in every (non-empty) bar there is a particular person, such that if this person drinks, then everybody in the bar drinks. The classical explanation for that phenomenon is simple, either everyone drinks anyway, in which case we can choose just an arbitrary person, or there is someone not drinking, in which case we choose that person and obtain a contradiction to the assumption they would drink. The role of the drinker paradox in the proof of the DLS theorem now is to ensure that the constructed model correctly interprets universal quantification: 4 4 4 Incidentally, a similar requirement is needed in Henkin-style completeness proofs [ henkin_completeness_1949 ] , connecting to our favoured strategy to establish the DLS theorem. given a formula \forall x.\,\varphi(x) one can find a special domain element a such that \varphi(a) implies \forall x.\,\varphi(x) , thereby reducing a test over the whole domain to a test of a single point and easing the correctness proof. However, we observe that one actually does not need to know a concretely but only that it is contained somewhere in the countable model we construct, more formally, that there is a countable subset A such that \forall a\in A.\,\varphi(a) implies \forall x.\,\varphi(x) . Seen computationally, this means that we reduce testing over the whole domain to testing only a countable part of it. On a more abstract level, this observation corresponds to a constructively weaker form of the drinker paradox: in every bar, there is a countable group, such that if everyone in this group drinks, then everybody in the bar drinks. We call this principle the blurred drinker paradox as it continues the bar situation at a later point when everyone’s vision got blurred and clear identifications of persons become impossible. That it corresponds to the DLS theorem is suggestive since both statements in a sense collapse arbitrary to countable cardinality and indeed we can show that, with CC still assumed in the background, the DLS theorem is equivalent to the conjunction of DC with the blurred drinker paradox. On top of this equivalence, we study the principle (and its dual needed for existential quantification) in a more general setting with arbitrary blurring cardinalities and in relation to other non-constructive principles, unveiling a hierarchy of classically invisible logical structure. Turning to question (2), we observe that DC becomes underivable from the DLS theorem if we further give up on

Read the complete text