Choice principles characterizing the difference between König’s lemma and weak König’s lemma in constructive reverse mathematics

Article type: Research Article

Authors: Fujiwara, Makoto^{a; *} | Nemoto, Takako^b

Affiliations: [a] Department of Applied Mathematics, Faculty of Science Division I, Tokyo University of Science, 1-3 Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan | [b] Graduate School of Information Sciences, Tohoku University, 6-3-09 Aoba, Aramaki-aza Aoba-ku, Sendai, 980-8579, Japan

Correspondence: [*] Corresponding author. makotofujiwara@rs.tus.ac.jp.

Abstract: In the context of constructive reverse mathematics, we characterize the difference between König’s lemma and weak König’s lemma by a particular fragment of the countable choice principle. Specifically, we show that König’s lemma can be decomposed into weak König’s lemma and the choice principle over a weak intuitionistic two-sorted arithmetic.

Keywords: Constructive reverse mathematics, König’s lemma, weak König’s lemma, uniqueness hypotheses, choice principles

DOI: 10.3233/COM-230478

Journal: Computability, vol. Pre-press, no. Pre-press, pp. 1-8, 2024