A fragment with the same provably recursive functions as n iterated inductive definitions is obtained by restricting second order arithmetic in the following way. The underlying language allows only up to n + 1 nested second order quantifications and those are in such a way. that no second order variable occurs free in the scope of another second order quantifier. The amount of induction on arithmetical formulae only affects the arithmetical consequences of these theories, whereas adding induction for arbitrary formulae increases the strength by one inductive definition.

A 2-affable ultrafilter has only finitely many predecessors in the Rudin-Keisler ordering of isomorphism classes of ultrafilters over the natural numbers. If the continuum hypothesis is true, then there is an ℵ1-sequence of ultrafilters Dα such that the strict Rudin-Keisler predecessors of Dα are precisely the isomorphs of the Dβ's for β < α.

Given I, a reasonable countable set of Turing degrees, can we find some sort of canonical strict upper bound on I? If I = {a ∣ a ≤ b}, the upper bound on I which springs to mind is b′. But what if I is closed under jump? This question arises naturally out of the question which motivates a large part of hierarchy theory: Is there a canonical increasing function from a countable ordinal, preferably a large one, into D, the set of Turing degrees? If d is to be such a function, it is natural to require that d(α + 1) = d(α)′; but how should d(λ) depend on d ↾ λ, where λ is a limit ordinal?

For any I ⊆ D, let MI, = ⋃I. Towards making the above questions precise, we introduce ideals of Turing degrees.

Definition 1. I ⊆ D is an ideal iff I is closed under jump and join, and I is downward-closed, i.e., if a ≤ b & b ϵ I then a ϵ I.

The following definition reflects the hierarchy-theoretic motivation for this paper.

Definition 2. For I ⊆ D and A ⊆ ω, I is an A-hierarchy ideal iff for some countable ordinal α, MI = Lα[A]∩ ωω.

All hierarchy ideals are ideals, but not conversely.

Early in the game Spector knocked out the best sort of canonicity for upper bounds on ideals, proving that no set of degrees closed under jump has a least upper bound.

We prove a variation of Easton’s lemma for strongly proper forcings, and use it to prove that, unlike the stronger principle IGMP, GMP together with 2ω ≤ ω2 is consistent with the existence of an ω1-distributive nowhere c.c.c. forcing poset of size ω1. We introduce the idea of a weakly guessing model, and prove that many of the strong consequences of the principle GMP follow from the existence of stationarily many weakly guessing models. Using Namba forcing, we construct a model in which there are stationarily many indestructibly weakly guessing models which have a bounded countable subset not covered by any countable set in the model.

Let Γ be a collection of relations on the reals and let M be a set of reals. We call M a perfect set basis for Γ if every set in Γ with parameters from M which is not totally included in M contains a perfect subset with code in M. A simple elementary proof is given of the following result (assuming mild regularity conditions on Γ and M): If M is a perfect set basis for Γ, the field of every wellordering in Γ is contained in M. An immediate corollary is Mansfield's Theorem that the existence of a Σ21 wellordering of the reals implies that every real is constructible. Other applications and extensions of the main result are also given.

We answer a question of Blass, Di Nasso, and Forti [2, 7] by proving, assuming Continuum Hypothesis or Martin’s Axiom, that (1) there exists a P-point which is not interval-to-one and (2) there exists an interval-to-one P-point which is neither quasi-selective nor weakly Ramsey.

Let T be an uncountable, superstable theory. In this paper we prove

Theorem A. If T has finite rank, then I(|T|, T) ≥ ℵ0.

Theorem B. If T is trivial, then I(|T|, T) ≥ ℵ0.

We shall describe Boolean extensions of models of set theory with the axiom of choice in which cardinals are collapsed by mappings definable from parameters in the ground model. In particular, starting from the constructible universe, we get Boolean extensions in which constructible cardinals are collapsed by ordinal definable sets.

Let be a transitive model of set theory with the axiom of choice. Definability of sets in the generic extensions of is closely related to the automorphisms of the corresponding Boolean algebra. In particular, if G is an -generic ultrafilter on a rigid complete Boolean algebra C, then every set in [G] is definable from parameters in . Hence if B is a complete Boolean algebra containing a set of forcing conditions to collapse some cardinals in , it suffices to construct a rigid complete Boolean algebra C, in which B is completely embedded. If G is as above, then [G] satisfies “every set is -definable” and the inner model [G ∩ B] contains the collapsing mapping determined by B. To complete the result, it is necessary to give some conditions under which every cardinal from [G ∩ B] remains a cardinal in [G].

The absolutness is granted for every cardinal at least as large as the saturation of C. To keep the upper cardinals absolute, it often suffices to construct C with the same saturation as B. It was shown in [6] that this is always possible, namely, that every Boolean algebra can be completely embedded in a rigid complete Boolean algebra with the same saturation.

We prove that each ω-categorical, generically stable group is solvable-by-finite.

Every definably complete expansion of an ordered field satisfies an analogue of the Baire Category Theorem.

We prove optimal lower bounds on the computation time for several well-known test problems on a quite realistic computational model: the random access machine. These lower bound arguments may be of special interest for logicians because they rely on finitary analogues of two important concepts from mathematical logic: inaccessible numbers and order indiscernibles.

We show that if κ is an inaccessible cardinal then P κλ splits into λ<κ many disjoint stationary subsets. We also show that if P κλ carries a strongly saturated ideal then the nonstationary ideal cannot be λ+-saturated.

We investigate the uniform computational content of the open and clopen Ramsey theorems in the Weihrauch lattice. While they are known to be equivalent to $\mathrm {ATR_0}$ from the point of view of reverse mathematics, there is not a canonical way to phrase them as multivalued functions. We identify eight different multivalued functions (five corresponding to the open Ramsey theorem and three corresponding to the clopen Ramsey theorem) and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility. In particular one of our functions turns out to be strictly stronger than any previously studied multivalued functions arising from statements around $\mathrm {ATR}_0$ .

L'analyse de la démonstration par contradiction de Frécon 2018 qui est faite dans Poizat 2018 met en évidence la structure symétrique des groupes de rang de Morley fini sans involutions; en effet, cette démonstration consiste en la construction d'un espace symétrique de dimension deux (“un plan”), puis à montrer que ce plan ne peut exister.

Aux sous-espaces symétriques définissables de ces groupes sont associées des symétries et des transvexions, qu'on entreprend d'étudier ici dans l'abstrait, sans référence à un groupe qui les enveloppe; cela nous mène à considérer des structures introduites axiomatiquement que nous appelons symétrons (plutôt qu'ensembles symétriques diadiques, comme les ont nommées Lawson & Lim 2004).

Le $Z^*$ -Theorem de Glauberman permet d'élucider complètement la structure des symétrons finis: chacun est isomorphe à l'ensemble des symétries associées à un sous-espace symétrique d'un groupe fini sans involutions, qui est loin d'être uniquement déterminé: de fait, il existe des groupes finis non isomorphes qui ont les mêmes symétries, et aussi des symétrons finis qui ne sont pas isomorphes aux symétries d'un groupe,

La situation est plus incertaine dans le cas des symétrons de rang de Morley fini, ou même algébriques, qui sont l'objet d'étude principal de cet article. Mais bien qu'un symétron soit une structure nettement plus faible qu'un groupe, nous pouvons étendre aux symétrons des résultats bien connus à propos des groupes de rang de Morley fini: condition de chaîne, décomposition en composantes connexes, caractérisation des parties définissables génériques, génération elliptique, etc. Ces propriétés sont nouvelles même dans le cas des sous-espaces symétriques d’un groupe, et permettent de court-circuiter les calculs de Frécon dans la construction de son plan paradoxal.

En outre, sous l'hypothèse de la Conjecture d'Algébricité, nous généralisons le Théorème de Glauberman au contexte de rang de Morley fini.

Lewis has made an attempt to construct a logistic system containing an implication-relation ⊰ in such a way that p⊰q shall have the meaning: q is deducible from p. Lewis and Langford admit that “the one serious doubt which can arise concerning the equivalence of p⊰q to the relation of deducibility … arises from the fact that strict implication has its corresponding paradoxes:

19.74˜⋄ p ⊰ · p ⊰ q,

‘If p is impossible, then p strictly implies any proposition q’; and

19.75 ˜⋄˜p ⊰ · q ⊰ p,

‘If p is necessary, then any proposition q strictly implies p.’”

Indeed, it is not obvious that 19.74 and 19.75 should hold. It is true that in many cases 19.75 (as well as 19.74) is valid; for in the system of Lewis and Langford

p · ˜p · ⊰ q

is provable, and the conformity of this law with real deduction is shown by them. In all cases in which a proposition of the form p·∼p can be derived from an impossible proposition, 19.75 holds. But it is not obvious that there are no other kinds of impossible propositions.

Fortunately it is easy to see what is the origin of the paradoxes. They are introduced into the system by the definition

11.02 p ⊰ q · = ˜ ⋄(p · ˜q).

Assume this definition. Then if q is necessary, p·∼q is impossible, and so, in accordance with 11.02, p⊰q is valid.

In this note we define a class of properties for which the following holds: If we can prove in NF that the property holds for the universe V, then we can prove in NF that it holds for every set equipollent to its power set.

Definition. For any stratified formula A and any variable υ which does not occur in A, let Aυ be the formula obtained by replacing in A each quantifier (Qx) by the bounded quantifier (Qx ∈ SCi(υ)), where i is the type of x in A. We will say that a property P(υ) is typed when there is a stratified sentence S such that P(υ) ↔ Sυ holds in NF.

Examples of typed properties are: “υ is Dedekind-infinite”, “υ is not well-orderable”. Specker [3] proved that these typed properties hold for the universe V, and C. Ward Henson [1] extended this result to any set equipollent to its power set. We will show that such an extension holds for any typed property.

Theorem. For any typed property P(υ):

Proof. Fix a bijective map h: υ → SC(υ) and define for i = 0, 1, 2, …, n, … a bijective map hi: υ → SCi(υ) as follows:

For every formula A, let A(h) be obtained by replacing in A each atomic part (x ∈ y) by (x ∈ h(y)) and each quantifier (Qx) by (Qx ∈ υ).

A first-order theory is equational if every definable set is a Boolean combination of instances of equations, that is, of formulae such that the family of finite intersections of instances has the descending chain condition. Equationality is a strengthening of stability. We show the equationality of the theory of proper extensions of algebraically closed fields and of the theory of separably closed fields of arbitrary imperfection degree.