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.
2012
omniscience principles, binary trees, König's Lemma, Fan Theorem, dependent choice
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/927916
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact