Classical provability of uniform versions and intuitionistic provability

Along the line of Hirst‐Mummert 9 and Dorais 4 , we analyze the relationship between the classical provability of uniform versions Uni(S) of Π₂‐statements S with respect to higher order reverse mathematics and the intuitionistic provability of S. Our main theorem states that (in particular) for every Π₂‐statement S of some syntactical form, if its uniform version derives the uniform variant of over a classical system of arithmetic in all finite types with weak extensionality, then S is not provable in strong semi‐intuitionistic systems including bar induction in all finite types but also nonconstructive principles such as K?nig's lemma and uniform weak K?nig's lemma . Our result is applicable to many mathematical principles whose sequential versions imply .     

A note on a forcing related to the S‐space problem in the extension with a coherent Suslin tree

One of the main problems about is that whether a coherent Suslin tree forces that there are no S‐spaces under . We analyze a forcing notion related to this problem, and show that under , S forces that every topology on ω₁ generated by a basis in the ground model is not an S‐topology. This supplements the previous work due to Stevo Todor?evi? [25].     

Totally non‐immune sets

Let be a countable first‐order language and be an ‐structure. “Definable set” means a subset of M which is ‐definable in with parameters. A set is said to be immune if it is infinite and does not contain any infinite definable subset. X is said to be partially immune if for some definable A, is immune. X is said to be totally non‐immune if for every definable A, and are not immune. Clearly every definable set is totally non‐immune. Here we ask whether the converse is true and prove that it is false for every countable structure whose class of definable sets satisfies a mild condition. We investigate further the possibility of an alternative construction of totally non‐immune non‐definable sets with the help of a subclass of immune sets, the class of cohesive sets, as well as with the help of a generalization of definable sets, the semi‐definable ones (the latter being naturally defined in models of arithmetic). Finally connections are found between totally non‐immune sets and generic classes in nonstandard models of arithmetic.     

Peano Corto and Peano Basso: A Study of Local Induction in the Context of Weak Theories

In this paper we study local induction w.r.t. Σ₁‐formulas over the weak arithmetic . The local induction scheme, which was introduced in 7 , says roughly this: for any virtual class that is progressive, i.e., is closed under zero and successor, and for any non‐empty virtual class that is definable by a Σ₁‐formula without parameters, the intersection of and is non‐empty. In other words, we have, for all Σ₁‐sentences S, that S implies , whenever is progressive. Since, in the weak context, we have (at least) two definitions of Σ₁, we obtain two minimal theories of local induction w.r.t. Σ₁‐formulas, which we call Peano Corto and Peano Basso. In the paper we give careful definitions of Peano Corto and Peano Basso. We establish their naturalness both by giving a model theoretic characterization and by providing an equivalent formulation in terms of a sentential reflection scheme. The theories Peano Corto and Peano Basso occupy a salient place among the sequential theories on the boundary between weak and strong theories. They bring together a powerful collection of principles that is locally interpretable in . Moreover, they have an important role as examples of various phenomena in the metamathematics of arithmetical (and, more generally, sequential) theories. We illustrate this by studying their behavior w.r.t. interpretability, model interpretability and local interpretability. In many ways the theories are more like Peano arithmetic or Zermelo Fraenkel set theory, than like finitely axiomatized theories as Elementary Arithmetic, and . On the one hand, Peano Corto and Peano Basso are very weak: they are locally cut‐interpretable in . On the other hand, they behave as if they were strong: they are not contained in any consistent finitely axiomatized arithmetical theory, however strong. Moreover, they extend , the theory of parameter‐free Π₁‐induction.     

Three‐space type Hahn‐Banach properties

In set theory without the axiom of choice , three‐space type results for the Hahn‐Banach property are provided. We deduce that for every Hausdorff compact scattered space K , the Banach space C(K ) of real continuous functions on K satisfies the (multiple) continuous Hahn‐Banach property in . We also prove in Rudin's theorem: “Radon measures on Hausdorff compact scattered spaces are discrete”.     

Cluster expansion and the boxdot conjecture

The boxdot conjecture asserts that every normal modal logic that faithfully interprets  by the well‐known boxdot translation is in fact included in . We confirm that the conjecture is true. More generally, we present a simple semantic condition on modal logics L₀ which ensures that the largest logic where L₀ embeds faithfully by the boxdot translation is L₀ itself. In particular, this natural generalization of the boxdot conjecture holds for , , and in place of .     

Hyperhypersimple sets and Q1‐reducibility

We prove that the c.e. Q₁‐degrees are not dense, and there exists a c.e. Q₁‐degree with no minimal c.e. predecessors. It is proved that if M₁ and M₂ are maximal sets such that then or . We also show that there exist infinite collections of Q₁‐degrees and such that the following hold: (i) for every , , , and , (ii) each consists entirely of maximal sets; and (iii) each consists entirely of non‐maximal hyperhypersimple sets.     

A Hanf number for saturation and omission: the superstable case

Suppose is a triple of two theories in vocabularies with cardinality λ, and a τ₁‐type p over the empty set that is consistent with T₁. We consider the Hanf number for the property “there is a model M₁ of T₁ which omits p, but is saturated”. In [2], we showed that this Hanf number is essentially equal to the Löwenheim number of second order logic. In this paper, we show that if T is superstable, then the Hanf number is less than .     

Clubs on quasi measurable cardinals

We construct a model satisfying “κ is quasi measurable”. Here, we call κ quasi measurable if there is an ℵ₁‐saturated κ‐additive ideal on κ. We also show that, in this model, forcing with adds one but not κ Cohen reals. We introduce a weak club principle and use it to show that, consistently, for some ℵ₁‐saturated κ‐additive ideal on κ, forcing with adds one but not κ random reals.     

Generic trivializations of geometric theories

We study the theory of the structure induced by parameter free formulas on a “dense” algebraically independent subset of a model of a geometric theory T. We show that while being a trivial geometric theory, inherits most of the model theoretic complexity of T related to stability, simplicity, rosiness, the NIP and the NTP₂. In particular, we show that T is strongly minimal, supersimple of SU‐rank 1, has the NIP or the NTP₂ exactly when has these properties. We show that if T is superrosy of thorn rank 1, then so is , and that the converse holds if T satisfies acl = dcl.     

Models of : when two elements are necessarily order automorphic

We are interested in the question of how much the order of a non‐standard model of can determine the model. In particular, for a model M, we want to characterize the complete types of non‐standard elements such that the linear orders and are necessarily isomorphic. It is proved that this set includes the complete types such that if the pair realizes it (in M) then there is an element c such that for all standard n, , , , and . We prove that this is optimal, because if holds, then there is M of cardinality ?₁ for which we get equality. We also deal with how much the order in a model of may determine the addition.     

The Structure of an SL2‐module of finite Morley rank

We consider a universe of finite Morley rank and the following definable objects: a field , a non‐trivial action of a group on a connected abelian group V , and a torus T of G such that . We prove that every T‐minimal subgroup of V has Morley rank . Moreover V is a direct sum of ‐minimal subgroups of the form , where W is T‐minimal and ζ is an element of G of order 4 inverting T .     

Uniqueness of limit models in classes with amalgamation

We prove the following main theorem: Let be an abstract elementary class satisfying the joint embedding and the amalgamation properties with no maximal models of cardinality μ. Let μ be a cardinal above the the Löwenheim‐Skolem number of the class. If is μ‐Galois‐stable, has no μ‐Vaughtian Pairs, does not have long splitting chains, and satisfies locality of splitting, then any two ‐limits over M, for , are isomorphic over M.     

Upward Morley's theorem downward

By a celebrated theorem of Morley, a theory T is ?₁‐categorical if and only if it is κ‐categorical for all uncountable κ. In this paper we are taking the first steps towards extending Morley's categoricity theorem “to the finite”. In more detail, we are presenting conditions, implying that certain finite subsets of certain ?₁‐categorical T have at most one n‐element model for each natural number (counting up to isomorphism, of course).     

Embedding classical in minimal implicational logic

Consider the problem which set V of propositional variables suffices for whenever , where , and ?_c and ?_i denote derivability in classical and intuitionistic implicational logic, respectively. We give a direct proof that stability for the final propositional variable of the (implicational) formula A is sufficient; as a corollary one obtains Glivenko's theorem. Conversely, using Glivenko's theorem one can give an alternative proof of our result. As an alternative to stability we then consider the Peirce formula . It is an easy consequence of the result above that adding a single instance of the Peirce formula suffices to move from classical to intuitionistic derivability. Finally we consider the question whether one could do the same for minimal logic. Given a classical derivation of a propositional formula not involving ⊥, which instances of the Peirce formula suffice as additional premises to ensure derivability in minimal logic? We define a set of such Peirce formulas, and show that in general an unbounded number of them is necessary.     

On the universality of the nonstationary ideal

Burke proved that the generalized nonstationary ideal, denoted by NS, is universal in the following sense: every normal ideal, and every tower of normal ideals of inaccessible height, is a canonical Rudin‐Keisler projection of the restriction of NS to some stationary set. We investigate how far Burke's theorem can be pushed, by analyzing the universality properties of NS with respect to the wider class of ‐systems of filters introduced by Audrito and Steila. First we answer a question of Audrito and Steila, by proving that ‐systems of filters do not capture all kinds of set‐generic embeddings. We provide a characterization of supercompactness in terms of short extenders and canonical projections of NS, without any reference to the strength of the extenders; as a corollary, NS can consistently fail to canonically project to arbitrarily strong short extenders. We prove that ω‐cofinal towers of normal ultrafilters, e.g., the kind used to characterize I2 and I3 embeddings, are well‐founded if and only if they are canonical projections of NS. Finally, we provide a characterization of “ is Jónsson” in terms of canonical projections of NS.     

Asymptotic density and the Ershov hierarchy

We classify the asymptotic densities of the sets according to their level in the Ershov hierarchy. In particular, it is shown that for , a real is the density of an n‐c.e. set if and only if it is a difference of left‐ reals. Further, we show that the densities of the ω‐c.e. sets coincide with the densities of the sets, and there are ω‐c.e. sets whose density is not the density of an n‐c.e. set for any .     

Characterization of ‐like and c0‐like equivalence relations

In this paper, notions of ‐like and c₀‐like equivalence relations are introduced. We characterize the positions of ‐like and c₀‐like equivalence relations in the Borel reducibility hierarchy by comparing them with equivalence relations and .     

A note on the independence of premiss rule

In this note, we prove that certain theories of (many‐sorted) intuitionistic predicate logic are closed under the independence of premiss rule (IPR). As corollaries, we show that and extended by some non‐classical axioms and non‐constructive axioms are closed under IPR.     

Separating principles below

In this paper, we study the Ramsey‐type weak K?nig's Lemma, written , using a technique introduced by Lerman, Solomon, and the second author. This technique uses iterated forcing to construct an ω‐model satisfying one principle T₁ but not another T₂. The technique often allows one to translate a “one step” construction (building an instance of T₂ along with a collection of solutions to each computable instance of T₁) into an ω‐model separation (building a computable instance of T₂ together with a Turing ideal where T₁ holds but this instance has no solution). We illustrate this translation by separating from (reproving a result of Ambos‐Spies, Kjos‐Hanssen, Lempp, and Slaman), and then apply this technique to separate from (which has been shown separately by Bienvenu, Patey, and Shafer).