The strength of Martin-Löf type theory with a superuniverse. Part II

Universes of types were introduced into constructive type theory by Martin-L?f [3]. The idea of forming universes in type theory is to introduce a universe as a set closed under a certain specified ensemble of set constructors, say ?. The universe then “reflects”?. This is the second part of a paper which addresses the exact logical strength of a particular such universe construction, the so-called superuniverse due to Palmgren (cf.[4–6]). It is proved that Martin-L?f type theory with a superuniverse, termed MLS, is a system whose proof-theoretic ordinal resides strictly above the Feferman-Schütte ordinal Γ₀ but well below the Bachmann-Howard ordinal. Not many theories of strength between Γ₀ and the Bachmann-Howard ordinal have arisen. MLS provides a natural example for such a theory. In this second part of the paper the concern is with the with upper bounds. Received: 8 December 1998 / Published online: 21 March 2001     

The strength of Martin-Löf type theory with a superuniverse. Part I

Universes of types were introduced into constructive type theory by Martin-L?f [12]. The idea of forming universes in type theory is to introduce a universe as a set closed under a certain specified ensemble of set constructors, say . The universe then “reflects”. This is the first part of a paper which addresses the exact logical strength of a particular such universe construction, the so-called superuniverse due to Palmgren (cf. [16, 18, 19]). It is proved that Martin-L?f type theory with a superuniverse, termed MLS, is a system whose proof-theoretic ordinal resides strictly above the Feferman-Schütte ordinal but well below the Bachmann-Howard ordinal. Not many theories of strength between and the Bachmann-Howard ordinal have arisen. MLS provides a natural example for such a theory. Received: 14 October 1997     

Polynomial-time Martin-Löf type theory

Summary Fragments of extensional Martin-Löf type theory without universes,ML ₀, are introduced that conservatively extend S.A. Cook and A. Urquhart'sIPV . A model for these restricted theories is obtained by interpretation in Feferman's theory APP of operators, a natural model of which is the class of partial recursive functions. In conclusion, some examples in group theory are considered.     

Definability of finite sum types in Martin-Löf's type theories

In this note we show that in the extensional versions of Martin-Löf's type theories the type-forming operation + (disjoint union of two types; finite sum-type) is actually explicitly definable from other basic types and type-forming operations.     

Extending Martin-Löf Type Theory by one Mahlo-universe

We define a type theory MLM, which has proof theoretical strength slightly greater then Rathjen's theory KPM. This is achieved by replacing the universe in Martin-L?f's Type Theory by a new universe V having the property that for every function f, mapping families of sets in V to families of sets in V, there exists a universe inside V closed under f. We show that the proof theoretical strength of MLM is . This is slightly greater than , and shows that V can be considered to be a Mahlo-universe. Together with [Se96a] it follows . Received: 8 February 1996     

Upper Limitation of Kolmogorov Complexity and Universal P. Martin-Löf Tests

In this paper we study the Kolmogorov complexity of initial strings in infinite sequences (being inspired by [9]), and we relate it with the theory of P. Martin-Lof random sequences. Working with partial recursive functions instead of recursive functions we can localize on an apriori given recursive set the points where the complexity is small. The relation between Kolmogorov's complexity and P. Martin-Lof's universal tests enables us to show that the randomness theories for finite strings and infinite sequences are not compatible (e.g.because no universal test is sequential).We lay stress upon the fact that we work within the general framework of a non-necessarily binary alphabet.     

The Hölder exponent of some Fourier series

In this paper we study the local regularity of fractional integrals of Fourier series using several definitions of the Hölder exponent. We especially consider series coming from fractional integrals of modular forms. Our results show that in general, cusp forms give rise to pure fractals (as opposed to multifractals). We include explicit examples and computer plots.     

The polynomial sub-Riemannian differentiability of some Hölder mappings of Carnot groups

The polynomial sub-Riemannian differentiability is established for the large classes of Hölder mappings in the sub-Riemannian sense, namely, the classes of smooth mappings, their graphs, and the graphs of Lipschitz mappings in the sub-Riemannian sense defined on nilpotent graded groups. We also describe some special bases that carry the sub-Riemannian structure of the preimage to the image.     

The Schröder-Bernstein property for weakly minimal theories

For a countable, weakly minimal theory T, we show that the Schröder-Bernstein property (any two elementarily bi-embeddable models are isomorphic) is equivalent to each of the following:

1. 1.
   For any U-rank-1 type q ∈ S(acl ^eq (?)) and any automorphism f of the monster model C, there is some n < ω such that f ⁿ (q) is not almost orthogonal to q ? f(q) ? … ? f ^n?1(q)
    
2. 2.
   T has no infinite collection of models which are pairwise elementarily bi-embeddable but pairwise nonisomorphic.
    

We conclude that for countable, weakly minimal theories, the Schröder-Bernstein property is absolute between transitve models of ZFC.     

On an inequality of Levinson of the Phragmèn-Lindelöf type

In this paper a new proof, based on Džrbašjan's characterization of H^p-spaces in a half-plane, of an integral inequality of Levinson of the Phragmèn-Lindelöf type is presented.     

The Lindelöf Number of Functional Spaces on Monolithic Compacta

Let X be a compactum, τ be an infinite cardinal, and t(X) ≤ τ. In this case, l(C_p(X)) ≤ 2^τ. If X is τ-monolitliic, then l(C_p(X)) ≤ τ⁺. In addition, if X is zero-dimensional and there are no τ⁺-Aronszajn trees, then l(C_p(X)) ≤ τ.     

The one-point Lindelöfication of an uncountable discrete space can be surlindelöf

We prove that the one-point Lindelöfication of a discrete space of cardinality ω ₁ is homeomorphic to a subspace of C _p (X) for some hereditarily Lindelöf space X if the axiom holds.     

Resolvability of Lindelöf spaces

We prove the ω-resolvability of hereditarily finally compact spaces and the resolvability of Lindelöf spaces whose dispersion character is uncountable.     

The Lindelöf principle in ℂ n

Let D be a bounded domain in ? ⁿ . A holomorphic function f: D → ? is called normal function if f satisfies a Lipschitz condition with respect to the Kobayashi metric on D and the spherical metric on the Riemann sphere ??. We formulate and prove a few Lindelöf principles in the function theory of several complex variables.     

Hölder estimates for the\bar \partial - equation in some domains of finite typein some domains of finite type

We obtain Hölder estimates for the $\bar \partial - equation$ on some domains of finite type in ?ⁿ using proper mapping techniques. The domains considered are domains of finite type in the sense of D’Angelo and are defined by local coordinate expressions satisfying certain algebraic geometric conditions which prevent the existence of complex analytic varieties in the boundary of the domain. Using a proper mapping which is given by the finite type condition and which carries all the information about the intrinsic geometry of the boundary, we transform the finite type points into strongly pseudoconvex ones. At these strongly pseudoconvex points we compute an explicit solution using the Henkin integral formula and we obtain estimates that we are able to pull back to the original domain. We achieve this by exploiting the branching behavior of the proper mapping. We also construct some biholomorphic numerical invariants associated with some of the domains under consideration.     

The error norm of Gauss-Kronrod quadrature formulae for weight functions of Bernstein-Szegö type

We consider the Gauss-Kronrod quadrature formulae for the Bernstein-Szegö weight functions consisting of any one of the four Chebyshev weights divided by the polynomial On certain spaces of analytic functions, the error term of these formulae is a continuous linear functional. We compute explicitly the norm of the error functional.