Search

In the context of a weak formal theory called Basic Intuitionistic Mathematics BIM\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\textsf{BIM}$$\end{document}, we study Brouwer’s Fan Theorem and a strong negation of the Fan Theorem, Kleene’s Alternative (to the Fan Theorem). We prove that the Fan Theorem is equivalent to contrapositions of a number of intuitionistically accepted axioms of countable choice and that Kleene’s Alternative is equivalent to strong negations of these statements. We discuss finite and infinite games and introduce a constructively useful notion of determinacy. We prove that the Fan Theorem is equivalent to the Intuitionistic Determinacy Theorem. This theorem says that every subset of Cantor space 2ω\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$2^\omega $$\end{document} is, in our constructively meaningful sense, determinate. Kleene’s Alternative is equivalent to a strong negation of a special case of this theorem. We also consider a uniform intermediate value theorem and a compactness theorem for classical propositional logic. The Fan Theorem is equivalent to each of these theorems and Kleene’s Alternative is equivalent to strong negations of them. We end with a note on ‘stronger’ Fan Theorems. The paper is a sequel to Veldman (Arch Math Logic 53:621–693, 2014). [ABSTRACT FROM AUTHOR]

The paper is a contribution to intuitionistic reverse mathematics. We introduce a formal system called Basic Intuitionistic Mathematics BIM, and then search for statements that are, over BIM, equivalent to Brouwer's Fan Theorem or to its positive denial, Kleene's Alternative to the Fan Theorem. The Fan Theorem is true under the intended intuitionistic interpretation and Kleene's Alternative is true in the model of BIM consisting of the Turing-computable functions. The task of finding equivalents of Kleene's Alternative is, intuitionistically, a nontrivial extension of the task of finding equivalents of the Fan Theorem, although there is a certain symmetry in the arguments that we shall try to make transparent. We introduce closed-and-separable subsets of Baire space $${\mathcal{N}}$$ and of the set $${\mathcal{R}}$$ of the real numbers. Such sets may be compact and also positively noncompact. The Fan Theorem is the statement that Cantor space $${\mathcal{C}}$$ , or, equivalently, the unit interval [0, 1], is compact and Kleene's Alternative is the statement that $${\mathcal{C}}$$ , or, equivalently, [0, 1], is positively noncompact. The class of the compact closed-and-separable sets and also the class of the closed-and-separable sets that are positively noncompact are characterized in many different ways and a host of equivalents of both the Fan Theorem and Kleene's Alternative is found. [ABSTRACT FROM AUTHOR]

In intuitionistic analysis, a subset of a Polish space like R or N is called positively Borel if and only if it is an open subset of the space or a closed subset of the space or the result of forming either the countable union or the countable intersection of an infinite sequence of (earlier constructed) positively Borel subsets of the space. The operation of taking the complement is absent from this inductive definition, and, in fact, the complement of a positively Borel set is not always positively Borel itself (see Veldman, 2008a). The main result of Veldman (2008a) is that, assuming Brouwer's Continuity Principle and an Axiom of Countable Choice, one may prove that the hierarchy formed by the positively Borel sets is genuinely growing: every level of the hierarchy contains sets that do not occur at any lower level. The purpose of the present paper is a different one: we want to explore the truly remarkable fine structure of the hierarchy. Brouwer's Continuity Principle again is our main tool. A second axiom proposed by Brouwer, his Thesis on Bars is also used, but only incidentally. [ABSTRACT FROM AUTHOR]

Abstract: The author proved in his Ph.D. Thesis [W. Veldman, Investigations in intuitionistic hierarchy theory, Ph.D. Thesis, Katholieke Universiteit Nijmegen, 1981] that, in intuitionistic analysis, the positively Borel subsets of Baire space form a genuinely growing hierarchy: every level of the hierarchy contains sets that do not occur at any lower level. It follows from this result that there are natural examples of analytic and also of co-analytic sets that are not positively Borel. It turns out, however, that, in intuitionistic analysis, one may give surprisingly different and, in some sense, much more simple examples of analytic and co-analytic sets that fail to be positively Borel. In the paper, two such examples are given. In proving them correct, one obtains new proofs of the Borel Hierarchy Theorem. Brouwer’s Continuity Principle plays a crucial role in arguments. [Copyright &y& Elsevier]

Discusses the proofs given for Kruskal's theorem on embeddability. Computational formulas for embedding; Information on induction principles associated with embedding; Overview of the finite sequence theorem.