The standard omniscience principles are interpreted in a systematic waywithin the context of binary trees. With this dictionary at hand we revisit the weakKönig lemma (WKL) and Brouwer's fan theorem (FAN). We first study how one canarrive from FAN at WKL, and then give a direct decomposition, without coding, ofWKL into the lesser limited principle of omniscience and an instance of the principleof dependent choices. As a complement we provide, among other equivalents of thestandard omniscience principles, a uniform method to formulate most of them.
The weak König lemma, Brouwer's fan theorem, de Morgan's law, and dependent choice
Schuster, Peter Michael
2012-01-01
Abstract
The standard omniscience principles are interpreted in a systematic waywithin the context of binary trees. With this dictionary at hand we revisit the weakKönig lemma (WKL) and Brouwer's fan theorem (FAN). We first study how one canarrive from FAN at WKL, and then give a direct decomposition, without coding, ofWKL into the lesser limited principle of omniscience and an instance of the principleof dependent choices. As a complement we provide, among other equivalents of thestandard omniscience principles, a uniform method to formulate most of them.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
