Recursively Enumerable Equivalence Relations Modulo Finite Differences

We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first-order definable in Eq*. Building on this we define a copy of the structure of recursively enumerable many-one degrees in Eq*, thereby showing that Th(Eq*) has the same computational complexity as the true first-order arithmetic. Mathematics Subject Classification: 03D25, 03D15, 03D35.     

Distributivity and stationary reflections

In this paper, we present some relations between generalized distributivity of quotient algebras and Mahlo operations, and show that the distributivity implies some variants of stationary relections.

     

Local sentences and Mahlo cardinals

Local sentences were introduced by Ressayre in [6] who proved certain remarkable stretching theorems establishing the equivalence between the existence of finite models for these sentences and the existence of some infinite well ordered models. Two of these stretching theorems were only proved under certain large cardinal axioms but the question of their exact (consistency) strength was left open in [4]. Here we solve this problem, using a combinatorial result of J. H. Schmerl [7]. In fact, we show that the stretching principles are equivalent to the existence of n ‐Mahlo cardinals for appropriate integers n. This is done by proving first that for every integer n, there is a local sentence φ_n having well ordered models of order type τ, for every infinite ordinal τ > ω which is not an n ‐Mahlo cardinal. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Indestructibility and stationary reflection

If κ < λ are such that κ is a strong cardinal whose strongness is indestructible under κ ‐strategically closed forcing and λ is weakly compact, then we show that A = {δ < κ | δ is a non‐weakly compact Mahlo cardinal which reflects stationary sets} must be unbounded in κ. This phenomenon, however, need not occur in a universe with relatively few large cardinals. In particular, we show how to construct a model where no cardinal is supercompact up to a Mahlo cardinal in which the least supercompact cardinal κ is also the least strongly compact cardinal, κ 's strongness is indestructible under κ ‐strategically closed forcing, κ 's supercompactness is indestructible under κ ‐directed closed forcing not adding any new subsets of κ, and δ is Mahlo and reflects stationary sets iff δ is weakly compact. In this model, no strong cardinal δ < κ is indestructible under δ ‐strategically closed forcing. It therefore follows that it is relatively consistent for the least strong cardinal κ whose strongness is indestructible under κ ‐strategically closed forcing to be the same as the least supercompact cardinal, which also has its supercompactness indestructible under κ ‐directed closed forcing not adding any new subsets of κ (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Definability in the enumeration degrees

We prove that every countable relation on the enumeration degrees, , is uniformly definable from parameters in . Consequently, the first order theory of is recursively isomorphic to the second order theory of arithmetic. By an effective version of coding lemma, we show that the first order theory of the enumeration degrees of the sets is not decidable. Received: August 1, 1994     

Ordinal diagrams for recursively Mahlo universes

In this paper we introduce a recursive notation system of ordinals. An element of the notation system is called an ordinal diagram following G. Takeuti [25]. The system is designed for proof theoretic study of theories of recursively Mahlo universes. We show that for each in KPM proves that the initial segment of determined by is a well ordering. Proof theoretic study for such theories will be reported in [9]. Received: 13 January, 1998     

Elementary inductive dichotomy: Separation of open and clopen determinacies with infinite alternatives

We introduce a new axiom called inductive dichotomy, a weak variant of the axiom of inductive definition, and analyze the relationships with other variants of inductive definition and with related axioms, in the general second order framework, including second order arithmetic, second order set theory and higher order arithmetic. By applying these results to the investigations on the determinacy axioms, we show the following. (i) Clopen determinacy is consistency-wise strictly weaker than open determinacy in these frameworks, except second order arithmetic; this is an enhancement of Schweber–Hachtman separation of open and clopen determinacy into the consistency-wise separation. (ii) Hausdorff–Kuratowski hierarchy of differences of opens is faithfully reflected by the hierarchy of consistency strengths of corresponding parameter-free determinacies in the aforementioned frameworks; this result is valid also in second order arithmetic only except clopen determinacy.     

A Galois correspondence for countable short recursively saturated models of PA

In this paper we investigate the properties of automorphism groups of countable short recursively saturated models of arithmetic. In particular, we show that Kaye's Theorem concerning the closed normal subgroups of automorphism groups of countable recursively saturated models of arithmetic applies to automorphism groups of countable short recursively saturated models as well. That is, the closed normal subgroups of the automorphism group of a countable short recursively saturated model of PA are exactly the stabilizers of the invariant cuts of the model which are closed under exponentiation. This Galois correspondence is used to show that there are countable short recursively saturated models of arithmetic whose automorphism groups are not isomorphic as topological groups. Moreover, we show that the automorphism groups of countable short arithmetically saturated models of PA are not topologically isomorphic to the automorphism groups of countable short recursively saturated models of PA which are not short arithmetically saturated (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Selective ultrafilters and

Mathias (Happy families, Ann. Math. Logic. 12 (1977), 59-111) proved that, assuming the existence of a Mahlo cardinal, it is consistent that CH holds and every set of reals in is -Ramsey with respect to every selective ultrafilter . In this paper, we show that the large cardinal assumption cannot be weakened.

     

Proper forcing extensions and Solovay models

We study the preservation of the property of being a Solovay model under proper projective forcing extensions. We show that every strongly-proper forcing notion preserves this property. This yields that the consistency strength of the absoluteness of under strongly-proper forcing notions is that of the existence of an inaccessible cardinal. Further, the absoluteness of under projective strongly-proper forcing notions is consistent relative to the existence of a -Mahlo cardinal. We also show that the consistency strength of the absoluteness of under forcing extensions with -linked forcing notions is exactly that of the existence of a Mahlo cardinal, in contrast with the general ccc case, which requires a weakly-compact cardinal.Research partially supported by the research projects BFM2002-03236 of the Spanish Ministry of Science and Technology, and 2002SGR 00126 of the Generalitat de Catalunya. The second author was also partially supported by the research project GE01/HUM10, Grupos de excelencia, Principado de Asturias.Mathematics Subject Classification (2000): 03E15, 03E35     

The basis decision problem in λ-calculus

We show that the problem of deciding if a finite set of closed terms in normal form is a basis is recursively unsolvable. The restricted problem concerning one element sets is still recursively unsolvable. MSC: 03B40, 03D35.     

Cupping the Recursively Enumerable Degrees by D.R.E. Degrees

We prove that there are two incomplete d.r.e. degrees (the Turingdegrees of differences of two recursively enumerable sets) suchthat every non-zero recursively enumerable degree cups at leastone of them to 0', the greatest recursively enumerable (Turing)degree. 1991 Mathematics Subject Classification: primary 03D25,03D30; secondary 03D35.     

Remarks on Levy's reflection axiom

Adding higher types to set theory differs from adding inaccessible cardinals, in that higher type arguments apply to all sets rather than just ordinary ones. Levy's reflection axiom is justified, by considering the principle that we can pretend that the universe is a set, together with methods of Gaifman [8]. We reprove some results of Gaifman, and some facts about Levy's reflection axiom, including the fact that adding higher types yields no new theorems about sets. Some remarks on standard models are made. An obvious strengthening of Levy's axiom to higher types is considered, which implies the existence of indescribable cardinals. Other remarks about larger cardinals are made; some questions of Gloede [9] are settled. Finally we argue that the evidence for V = L is strong, and that CH is certainly true. MSC: 03E30, 03E55.     

The metamathematics of scattered linear orderings

Pursuing the proof-theoretic program of Friedman and Simpson, we begin the study of the metamathematics of countable linear orderings by proving two main results. Over the weak base system consisting of arithmetic comprehension, II ₁ ¹ -CA₀ is equivalent to Hausdorff's theorem concerning the canonical decomposition of countable linear orderings into a sum over a dense or singleton set of scattered linear orderings. Over the same base system, ATR₀ is equivalent to a version of the Continuum Hypothesis for linear orderings, which states that every countable linear ordering either has countably many or continuum many Dedekind cuts.Research partially supported by NSF grant # DCR-8606165. AMS Subject Classification 03F35, 03F15, 03D55     

Effective Nonrecursiveness

Productive sets are sets which are “effectively non recursively enumerable”. In the same spirit, we introduce a notion of “effectively nonrecursive sets” and prove an effective version of Post's theorem. We also show that a set is recursively enumerable and effectively nonrecursive in our sense if and only if it is effectively nonrecursive in the sense of Odifreddi [1].     

Strong Minimal Covers for Recursively Enumerable Degrees

We prove that there exists a nonzero recursively enumerable Turing degree possessing a strong minimal cover. Mathematics Subject Classification: 03D30.     

Bounding the consistency strength of a five element linear basis

In [13] it was demonstrated that the Proper Forcing Axiom implies that there is a five element basis for the class of uncountable linear orders. The assumptions needed in the proof have consistency strength of at least infinitely many Woodin cardinals. In this paper we reduce the upper bound on the consistency strength of such a basis to something less than a Mahlo cardinal, a hypothesis which can hold in the constructible universe L. A crucial notion in the proof is the saturation of an Aronszajn tree, a statement which may be of broader interest. We show that if all Aronszajn trees are saturated and PFA(ω ₁) holds, then there is a five element basis for the uncountable linear orders. We show that PFA(ω ₂) implies that all Aronszajn trees are saturated and that it is consistent to have PFA(ω ₁) plus every Aronszajn tree is saturated relative to the consistency of a reflecting Mahlo cardinal. Finally we show that a hypothesis weaker than the existence of a Mahlo cardinal is sufficient to force the existence of a five element basis for the uncountable linear orders. The first author acknowledges a fellowship granted by the French ministry of research. The research of the second author was partially supported by the Centre de Rercerca Matemàtica of the Universitat Autònoma de Barcelona, and by NSF Grant DMS-0401603. The second author would also like to thank the third and fourth authors for bringing him to Boise and Paris respectively for further discussions. The third author was supported by NSF grants DMS-0401893 and DMS-0200671. The second and fourth authors would like to thank CIRM in Luminy for hosting them during a petit group de travaille, and to thank the others participants, Ralf Schindler and Ernest Schimmerling, for discussions on this topic.     

A construction of interpolating wavelets on invariant sets

We introduce the concept of a refinable set relative to a family of contractive mappings on a metric space, and demonstrate how such sets are useful to recursively construct interpolants which have a multiscale structure. The notion of a refinable set parallels that of a refinable function, which is the basis of wavelet construction. The interpolation points we recursively generate from a refinable set by a set-theoretic multiresolution are analogous to multiresolution for functions used in wavelet construction. We then use this recursive structure for the points to construct multiscale interpolants. Several concrete examples of refinable sets which can be used for generating interpolatory wavelets are included.

     

Dynamic ordinal analysis

 Dynamic ordinal analysis is ordinal analysis for weak arithmetics like fragments of bounded arithmetic. In this paper we will define dynamic ordinals – they will be sets of number theoretic functions measuring the amount of sΠ ^b ₁(X) order induction available in a theory. We will compare order induction to successor induction over weak theories. We will compute dynamic ordinals of the bounded arithmetic theories sΣ ^b _n (X)−L ^m IND for m=n and m=n+1, n≥0. Different dynamic ordinals lead to separation. In this way we will obtain several separation results between these relativized theories. We will generalize our results to further languages extending the language of bounded arithmetic. Received: 27 April 2001 / Published online: 19 December 2002 The results for sΣ ^b _n (X)−L ^m IND are part of the authors dissertation [3]; the results for sΣ ^b _m (X)−L ^m+1 IND base on results of ARAI [1]. Mathematics Subject Classification (2000): Primary 03F30; Secondary 03F05, 03F50 Key words or phrases: Dynamic ordinal – Bounded arithmetic – Proof-theoretic ordinal – Order induction – Semi-formal system – Cut-elimination     

The strong soundness theorem for real closed fields and Hilbert’s Nullstellensatz in second order arithmetic

By RCA₀, we denote a subsystem of second order arithmetic based on ⁰₁ comprehension and ⁰₁ induction. We show within this system that the real number system R satisfies all the theorems (possibly with non-standard length) of the theory of real closed fields under an appropriate truth definition. This enables us to develop linear algebra and polynomial ring theory over real and complex numbers, so that we particularly obtain Hilberts Nullstellensatz in RCA₀.Mathematics Subject Classification (2000): Primary 03F35; Secondary 03B30, 12D10