# Foundational and Mathematical Uses of Higher Types

### Abstract

In this paper we develop mathematically strong systems of analysis inhigher types which, nevertheless, are proof-theoretically weak, i.e. conservative

over elementary resp. primitive recursive arithmetic. These systems

are based on non-collapsing hierarchies (Phi_n-WKL+, Psi_n-WKL+) of principles

which generalize (and for n = 0 coincide with) the so-called `weak' K¨onig's

lemma WKL (which has been studied extensively in the context of second order

arithmetic) to logically more complex tree predicates. Whereas the second

order context used in the program of reverse mathematics requires an encoding

of higher analytical concepts like continuous functions F : X -> Y between

Polish spaces X, Y , the more flexible language of our systems allows to treat

such objects directly. This is of relevance as the encoding of F used in reverse

mathematics tacitly yields a constructively enriched notion of continuous functions

which e.g. for F : N^N -> N can be seen (in our higher order context) to be equivalent

to the existence of a continuous modulus of pointwise continuity.

For the direct representation of F the existence of such a modulus is

independent even of full arithmetic in all finite types E-PA^omega plus quantifier-free

choice, as we show using a priority construction due to L. Harrington.

The usual WKL-based proofs of properties of F given in reverse mathematics

make use of the enrichment provided by codes of F, and WKL does not seem

to be sufficient to obtain similar results for the direct representation of F in

our setting. However, it turns out that Psi_1-WKL+ is sufficient.

Our conservation results for (Phi_n-WKL+, Psi_n-WKL+) are proved via a new

elimination result for a strong non-standard principle of uniform Sigma^0_1-

boundedness

which we introduced in 1996 and which implies the WKL-extensions studied

in this paper.

Published

1999-12-01

How to Cite

*BRICS Report Series*,

*6*(31). https://doi.org/10.7146/brics.v6i31.20100

Section

Articles

Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.