Recently, several authors have explored the connections between NP-complete problems for finite objects and the complexity of their analogs for infinite objects. In this paper, we will categorize infinite versions of several problems arising from finite complexity theory in terms of their recursion theoretic complexity and proof theoretic strength. These infinite analogs can behave in a variety of unexpected ways.

We prove that the statement “there is aksuch that for everyfthere is ak-bounded diagonally nonrecursive function relative tof” does not imply weak König’s lemma over${\rm{RC}}{{\rm{A}}_0} + {\rm{B\Sigma }}_2^0$. This answers a question posed by Simpson. A recursion-theoretic consequence is that the classic fact that everyk-bounded diagonally nonrecursive function computes a 2-bounded diagonally nonrecursive function may fail in the absence of${\rm{I\Sigma }}_2^0$.

We show that a version of Ramsey’s theorem for trees for arbitrary exponents is equivalent to the subsystem ${{\sf ACA}^\prime_{0}}$ of reverse mathematics.

Two countable well orderings are weakly comparable if there is an order preserving injection of one into the other. We say the well orderings are strongly comparable if the injection is an isomorphism between one ordering and an initial segment of the other. In [5], Friedman announced that the statement “any two countable well orderings are strongly comparable” is equivalent to ATR 0 . Simpson provides a detailed proof of this result in Chapter 5 of [13]. More recently, Friedman has (...) proved that the statement “any two countable well orderings are weakly comparable” is equivalent to ATR 0 . The main goal of this paper is to give a detailed exposition of this result. (shrink)

We examine the reverse mathematics and computability theory of a form of Ramsey's theorem in which the linear n-tuples of a binary tree are colored.

This book covers a wide variety of topics in combinatorics and graph theory.

Simpson has claimed that “ATR0 is the weakest set of axioms which permits the development of a decent theory of countable ordinals” [8]. This paper provides empirical support for Simpson's claim. In particular, Cantor's Normal Form Theorem and Sherman's Inequality for countable well-orderings are both equivalent to ATR0. The proofs of these results require a substantial development of ordinal exponentiation and a strengthening of the comparability result in [3].

We show that when certain statements are provable in subsystems of constructive analysis using intuitionistic predicate calculus, related sequential statements are provable in weak classical subsystems. In particular, if a $\Pi^1_2$ sentence of a certain form is provable using E-HA ${}^\omega$ along with the axiom of choice and an independence of premise principle, the sequential form of the statement is provable in the classical system RCA. We obtain this and similar results using applications of modified realizability and the Dialectica interpretation. (...) These results allow us to use techniques of classical reverse mathematics to demonstrate the unprovability of several mathematical principles in subsystems of constructive analysis. (shrink)

We show that \\) cannot be proved with one typical application of \\) in an intuitionistic extension of \ to higher types, but that this does not remain true when the law of the excluded middle is added. The argument uses Kohlenbach’s axiomatization of higher order reverse mathematics, results related to modified reducibility, and a formalization of Weihrauch reducibility.

We show that a statement HIL, which is motivated by a lemma of Hilbert and close in formulation to Hindman’s theorem, is actually much weaker than Hindman’s theorem. In particular, HIL is finitistically reducible in the sense of Hilbert’s program, while Hindman’s theorem is not.

We examine a number of results of infinite combinatorics using the techniques of reverse mathematics. Our results are inspired by similar results in recursive combinatorics. Theorems included concern colorings of graphs and bounded graphs, Euler paths, and Hamilton paths.

Working in subsystems of second order arithmetic, we formulate several representations for hypergraphs. We then prove the equivalence of various vertex coloring theorems to \, \, and \.

We study the effective and proof-theoretic content of the polarized Ramsey’s theorem, a variant of Ramsey’s theorem obtained by relaxing the definition of homogeneous set. Our investigation yields a new characterization of Ramsey’s theorem in all exponents, and produces several combinatorial principles which, modulo bounding for ${\Sigma^0_2}$ formulas, lie (possibly not strictly) between Ramsey’s theorem for pairs and the stable Ramsey’s theorem for pairs.

We analyze the logical strength of theorems on marriage problems with unique solutions using the techniques of reverse mathematics, restricting our attention to problems in which each boy knows only finitely many girls. In general, these marriage theorems assert that if a marriage problem has a unique solution then there is a way to enumerate the boys so that for every m, the first m boys know exactly m girls. The strength of each theorem depends on whether the underlying marriage (...) problem is finite, infinite, or bounded. (shrink)

If α and β are ordinals, α ≤ β, and $\beta \nleq \alpha$ , then α + 1 ≤ β. The first result of this paper shows that the restriction of this statement to countable well orderings is provably equivalent to ACA 0 , a subsystem of second order arithmetic introduced by Friedman. The proof of the equivalence is reminiscent of Dekker's construction of a hypersimple set. An application of the theorem yields the equivalence of the set comprehension scheme ACA (...) 0 and an arithmetical transfinite induction scheme. (shrink)

Extrapolating from the work of Mahlo , one can prove that given any pair of countable closed totally bounded subsets of complete separable metric spaces, one subset can be homeomorphically embedded in the other. This sort of topological comparability is reminiscent of the statements concerning comparability of well orderings which Friedman has shown to be equivalent to ATR0 over the weak base system RCA0. The main result of this paper states that topological comparability is also equivalent to ATR0. In Section (...) 1, the pertinent subsystems of second-order arithmetic and results on well orderings are reviewed. Sections 2 and 3 overview the encoding of metric spaces and homeomorphisms in second-order arithmetic. Section 4 contains a proof of the topological comparability result in ATR0. Section 5 contains the reversal, a derivation of ATR0 from the topological comparability result. In Section 6, additional information about the structure of the embeddings is obtained, culminating in an application to closed subsets of the real numbers. (shrink)

If there is a homeomorphic embedding of one set into another, the sets are said to be topologically comparable. Friedman and Hirst have shown that the topological comparability of countable closed subsets of the reals is equivalent to the subsystem of second order arithmetic denoted byATR 0. Here, this result is extended to countable closed locally compact subsets of arbitrary complete separable metric spaces. The extension uses an analogue of the one point compactification of ℝ.

One of the earliest applications of transfinite numbers is in the construction of derived sequences by Cantor [2]. In [6], the existence of derived sequences for countable closed sets is proved in ATR0. This existence theorem is an intermediate step in a proof that a statement concerning topological comparability is equivalent to ATR0. In actuality, the full strength of ATR0 is used in proving the existence theorem. To show this, we will derive a statement known to be equivalent to ATR0, (...) using only RCA0 and the assertion that every countable closed set has a derived sequence. We will use three of the subsystems of second order arithmetic defined by H. Friedman , which can be roughly characterized by the strength of their set comprehension axioms. RCA0 includes comprehension for Δmath image definable sets, ACA0 includes comprehension for arithmetical sets, and ATR0 appends to ACA0 a comprehension scheme for sets defined by transfinite recursion on arithmetical formulas. MSC: 03F35, 54B99. (shrink)

Suppose that 〈xk〉k∈ℕ is a countable sequence of real numbers. Working in the usual subsystems for reverse mathematics, RCA0 suffices to prove the existence of a sequence of reals 〈uk〉k∈ℕ such that for each k, uk is the minimum of {x0, x1, …, xk}. However, if we wish to prove the existence of a sequence of integer indices of minima of initial segments of 〈xk〉k∈ℕ, the stronger subsystem WKL0 is required. Following the presentation of these reverse mathematics results, we will (...) derive computability theoretic corollaries and use them to illustrate a distinction between computable analysis and constructive analysis. (shrink)

A rank function for a directed graph G assigns elements of a well ordering to the vertices of G in a fashion that preserves the order induced by the edges. While topological sortings require a one-to-one matching of vertices and elements of the ordering, rank functions frequently must assign several vertices the same value. Theorems stating basic properties of rank functions vary significantly in logical strength. Using the techniques of reverse mathematics, we present results that require the subsystems ${\ensuremath{\vec{RCA}_0}}$ , (...) ${{\vec{ACA}_0}}$ , ${{\vec{ATR}_0}}$ , and ${{\vec{\Pi^1_1 - CA}_0}}$. (shrink)

This paper uses the framework of reverse mathematics to analyze the proof theoretic content of several statements concerning multiplication of countable well-orderings. In particular, a division algorithm for ordinal arithmetic is shown to be equivalent to the subsystem ATR0.

One of the earliest applications of Cantor's Normal Form Theorem is Jacobstahl's proof of the existence of prime factorizations of ordinals. Applying the techniques of reverse mathematics, we show that the full strength of the Normal Form Theorem is used in this proof.

This paper contains a corrected proof that the statement “every non-empty closed subset of a compact complete separable metric space is separably closed” implies the arithmetical comprehension axiom of reverse mathematics.

We show that a version of Ramsey’s theorem for trees for arbitrary exponents is equivalent to the subsystem \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\sf ACA}^\prime_{0}}$$\end{document} of reverse mathematics.

We formulate a polarized version of Ramsey’s theorem for trees. For those exponents greater than 2, both the reverse mathematics and the computability theory associated with this theorem parallel that of its linear analog. For pairs, the situation is more complex. In particular, there are many reasonable notions of stability in the tree setting, complicating the analysis of the related results.

For over forty years, Leland Ryken has championed and modeled a Christian liberal arts education. His scholarship and commitment to integrating faith with learning in the classroom have influenced thousands of students who have sat under his winsome teaching. Published in honor of Professor Ryken and presented on the occasion of his retirement from Wheaton College, this compilation carries on his legacy of applying a Christian liberal arts education to all areas of life. Five sections explore the background of a (...) Christian liberal arts education, its theological basis, habits and virtues, differing approaches, and ultimate aims. Contributors including Philip Ryken, Jeffry Davis, Duane Litfin, John Walford, Alan Jacobs, and Jim Wilhoit analyze liberal arts as they relate to the disciplines, the Christian faith, and the world. Also included are a transcript of a well-known 1984 chapel talk delivered by Leland Ryken on the student's calling and practical chapters on how to read, write, and speak well. Comprehensive in scope, this substantial volume will be a helpful guide to anyone involved in higher education, as well as to students, pastors, and leaders looking for resources on the importance of faith in learning. - Publisher. (shrink)

In an interesting experimental study, Bonini et al. (1999) present partial support for truth-gap theories of vagueness. We say this despite their claim to find theoretical and empirical reasons to dismiss gap theories and despite the fact that they favor an alternative, epistemic account, which they call ‘vagueness as ignorance’. We present yet more experimental evidence that supports gap theories, and argue for a semantic/pragmatic alternative that unifies the gappy supervaluationary approach together with its glutty relative, the subvaluationary approach.

In the case of an actual proper name such as ‘Aristotle’ opinions as to the Sinn may differ. It might, for instance, be taken to be the following: the pupil of Plato and teacher of Alexander the Great. Anybody who does this will attach another Sinn to the sentence ‘Aristotle was born in Stagira’ than will a man who takes as the Sinn of the name: the teacher of Alexander the Great who was born in Stagira. So long as the (...) Bedeutung remains the same, such variations of Sinn may be tolerated, although they are to be avoided.. (shrink)

Samkara (c. 700 CE), the great Indian Advaitin thinker, was a commentator on sacred text and an Advaitin teacher. This book provides an introduction to the thought of Samkara, who is the most well-known and most perhaps the most authoritative Hindu thinker of all time. The author develops an innovative approach using Samkara's method of interpreting sacred texts and creatively examines the profound interrelationship between sacred text, content and method in Samkara's thought. In particular Samkara's teaching method is the main (...) focus of this book; it is a method that is based on Upanisadic truth and expects teachers to skillfully draw pupils towards it. This book will be of interest to students and scholars of Indian philosophy. (shrink)

Introduction. Murder, some may suggest, is to be defined as the intentional and uncoerced killing of the innocent; and it is true by definition that murder is wrong. Yet wars, particularly modern wars, seem to require the killing of the innocent, e.g. through anti-morale terror bombing. Therefore war must be wrong.