𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Some conservation results on weak König's lemma

✍ Scribed by Stephen G. Simpson; Kazuyuki Tanaka; Takeshi Yamazaki

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
274 KB
Volume
118
Category
Article
ISSN
0168-0072

No coin nor oath required. For personal study only.

✦ Synopsis

By RCA0, we denote the system of second-order arithmetic based on recursive comprehension axioms and 0 1 induction. WKL0 is deÿned to be RCA0 plus weak K onig's lemma: every inÿnite tree of sequences of 0's and 1's has an inÿnite path. In this paper, we ÿrst show that for any countable model M of RCA0, there exists a countable model M of WKL0 whose ÿrst-order part is the same as that of M , and whose second-order part consists of the M -recursive sets and sets not in the second-order part of M . By combining this fact with a certain forcing argument over universal trees, we obtain the following result (which has been called Tanaka's conjecture): if WKL0 proves ∀X ∃!Y'(X; Y ) with ' arithmetical, so does RCA0. We also discuss several improvements of this results.

📜 SIMILAR VOLUMES

On uniform weak König's lemma
On uniform weak König's lemma
✍ Ulrich Kohlenbach 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 121 KB

The so-called weak K onig's lemma WKL asserts the existence of an inÿnite path b in any inÿnite binary tree (given by a representing function f). Based on this principle one can formulate subsystems of higher-order arithmetic which allow to carry out very substantial parts of classical mathematics b

Remarks on the cofinality of a partially
Remarks on the cofinality of a partially ordered set, and a generalization of König's lemma
✍ E.C. Milner; N. Sauer 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 694 KB

A problem concerning the cardinality of the cofinal subsets of a partially ordered set is reduced to an open problem irr graph tteory. Let A be an in&it: wdinal, V = Ui,, Vi, I Uiii VJC IVJ (i CA). J\_et G be a graph on V with the proper?y that whenever i <A, x=u ie,cA Vi and IXICIVil, then there is