In this note we study generic existence of maximal almost disjoint (MAD) families. Among other results we prove that Cohen-indestructible families exist generically if and only if b = c. We obtain analogous results for other combinatorial properties of MAD families, including Sacks-indestructibility and being +-Ramsey.

Given a supercompact cardinal κ and a regular cardinal λ < κ, we describe a type of forcing such that in the generic extension the cofinality of κ is λ, there is a very good scale at κ, a bad scale at κ, and SCH at κ fails. When creating our model we have great freedom in assigning the value of 2κ, and so we can make SCH hold or fail arbitrarily badly.

We characterize the expressive power of extensions of Dependence Logic and Independence Logic by monotone generalized quantifiers in terms of quantifier extensions of existential second-order logic.

If a and b are degrees of unsolvability, a is called (as in [1]) a minimal cover of b if b < a and no degree c satisfies b < c < a. A degree a is called a minimal cover if it is a minimal cover of some degree b. We show in ZF set theory that there is a degree d such that every degree a ≥ d is a minimal cover. In [1] it was remarked that this result follows via a lemma of D. A. Martin [4] from the determinacy of a certain Σ50 Gale-Stewart game (which in turn follows [5] from the existence of a measurable cardinal). The argument here is parallel to that of [1], but the essential new ingredient is the result of Paris [6] that Σ50 determinacy can be proved in ZF. Also it is necessary to replace the Σ50 game of [1] by a related Σ40 game and to use the method, rather than just the statement, of Martin's lemma.

Theorem. There is a degreedsuch that every degreea ≥ dis a minimal cover.

Proof. In a (Gale–Stewart) game on 2ω, players I and II construct a set of integers A as follows: At the nth stage, player I determines whether n ϵ A if n is even and player II if n is odd. Thus player I controls A0 and player II controls A1 where Ai = {n: 2n + i ϵ A}. Let Aij denote (Ai)j and let M (A, B) mean that the degree of A is a minimal cover of that of B. Consider now the particular game in which player I wins iff M(A, A00) holds.

A number of specific cardinal numbers have been defined in terms of /fin or ωω. Some have been generalized to higher cardinals, and some even to arbitrary Boolean algebras. Here we study eight of these cardinals, defining their generalizations to higher cardinals, and then defining them for Boolean algebras. We then attempt to completely describe their relationships within each of several important classes of Boolean algebras.

The generalizations to higher cardinals might involve several cardinals instead of just one as in the case of ω, For example, the number a associated with maximal almost disjoint families of infinite sets of integers can be generalized to talk about maximal subsets of [κ]μ subject to the pairwise intersections having size less than ν. (For this multiple generalization of . see Monk [2001].) For brevity we do not consider such generalizations, restricting ourselves to just one cardinal. The set-theoretic generalizations then associate with each infinite cardinal κ some other cardinal λ, defined as the minimum of cardinals with a certain property.

The generalizations to Boolean algebras assign to each Boolean algebra some cardinal λ, also defined as the minimum of cardinals with a certain property.

For the theory of the original “continuum” cardinal numbers, see Douwen [1984]. Balcar and Simon [1989]. and Vaughan [1990].

I am grateful to Mati Rubin for some conversations concerning these functions for superatomic algebras, and to Bohuslav Balcar for information concerning the function h.

The notation for set theory is standard. For Boolean algebras we follow Koppelberg [1989], but recall at the appropriate place any somewhat unusual notation.

This work is an attempt to characterize the index sets of classes of recursively enumerable sets which are expressible in terms of open sets in the Baire topology on the power set of the set N of natural numbers, usual in recursion theory. Let be a class of subsets of N and be the set of indices of recursively enumerable sets Wх belonging to .

A well-known theorem of Rice and Myhill (cf. [5, p. 324, Rice-Shapiro Theorem]) states that is recursively enumerable if and only ifis a r.e. open set. In this case, note that if is not empty and does not contain all recursively enumerable sets, is a complete set. This theorem will be partially extended to classes which are boolean combinations of open sets by the following:

(i) There is a canonical boolean combination which represents, namely the shortest among boolean combinations which represent.

(ii) The recursive isomorphism type of depends on the length n of this canonical boolean combination (and trivial properties of ); for instance, is recursively isomorphic (in the particular case where is a boolean combination of recursive open sets) to an elementary set combination Yn or Un, constructed from {х ∣ х Wх) and depending on the length n. We can say also that is a complete set in the sense of Ershov's hierarchy [1] (in this particular case).

We prove new upper bound theorems on the consistency strengths of SPFA(θ), SPFA(θ-linked) and SPFA(θ+ -cc). Our results are in terms of (θ, Γ)-subcompactness, which is a new large cardinal notion that combines the ideas behind subcompactness and Γ-indescribability. Our upper bound for SPFA(ϲ-linked) has a corresponding lower bound, which is due to Neeman and appears in his follow-up to this paper. As a corollary, SPFA(ϲ-linked) and PFA(ϲ-linked) are each equiconsistent with the existence of a -indescribable cardinal. Our upper bound for SPFA(ϲ-c.c) is a -indescribable cardinal, which is consistent with V = L. Our upper bound for SPFA(ϲ+-linked) is a cardinals κ that is (κ+,)-subcompact, which is strictly weaker than κ+-supercompact. The axiom MM(ϲ) is a consequence of SPFA(ϲ+-linked) by a slight refinement of a theorem of Shelah. Our upper bound for SPFA(ϲ++-c.c.) is a cardinal κ that is (κ+, )-subcompact, which is also strictly weaker than κ+-supercompact.

We show that for any real number, the class of real numbers less random than it, in the sense of rK-reducibility, forms a countable real closed subfield of the real ordered field. This generalizes the well-known fact that the computable reals form a real closed field.

With the same technique we show that the class of differences of computably enumerable reals (d.c.e. reals) and the class of computably approximable reals (c.a. reals) form real closed fields. The d.c.e. result was also proved nearly simultaneously and independently by Ng (Keng Meng Ng, Master's Thesis, National University of Singapore, in preparation).

Lastly, we show that the class of d.c.e. reals is properly contained in the class or reals less random than Ω (the halting probability), which in turn is properly contained in the class of c.a. reals, and that neither the first nor last class is a randomness class (as captured by rK-reducibility).

We give model theoretic criteria for the existence of ∃∀ and ∀∃- formulas in the ring language to define uniformly the valuation rings ${\cal O}$ of models $\left( {K,\,{\cal O}} \right)$ of an elementary theory Σ of henselian valued fields. As one of the applications we obtain the existence of an ∃∀-formula defining uniformly the valuation rings ${\cal O}$ of valued henselian fields $\left( {K,\,{\cal O}} \right)$ whose residue class field k is finite, pseudofinite, or hilbertian. We also obtain ∀∃-formulas φ2 and φ4 such that φ2 defines uniformly k[[t]] in k(t) whenever k is finite or the function field of a real or complex curve, and φ4 replaces φ2 if k is any number field.

A cylindric algebra atom structure is said to be strongly representable if all atomic cylindric algebras with that atom structure are representable. This is equivalent to saying that the full complex algebra of the atom structure is a representable cylindric algebra. We show that for any finite n ≥ 3, the class of all strongly representable n-dimensional cylindric algebra atom structures is not closed under ultraproducts and is therefore not elementary.

Our proof is based on the following construction. From an arbitrary undirected, loop-free graph Γ, we construct an n-dimensional atom structure , and prove, for infinite Γ, that is a strongly representable cylindric algebra atom structure if and only if the chromatic number of Γ is infinite. A construction of Erdős shows that there are graphs Γk(k < ω) with infinite chromatic number, but having a non-principal ultraproduct ΠDΓk whose chromatic number is just two. It follows that is strongly representable (each k < ω) but is not.

The history of the Gentzenization of relevant logics goes back to Kripke [17], who in 1959 Gentzenized R→ and went on to prove its decidability. Formulae were separated by commas on the left side of the turnstile, the commas just representing nested implications. Kripke employed just a singleton formula to the right of the turnstile. He also considered adding negation, as well as other connectives, but it was not until 1961 that Belnap and Wallace, in [5], Gentzenized and proved its decidability, though their Gentzenization employed commas on both sides of the turnstile. Subsequently, in 1966, the logic R without distribution, now called LR (for lattice R), was Gentzenized in a similar style by Meyer in [20]. He also went on to show decidability for LR by extending Kripke's argument. Later, in 1969, Dunn Gentzenized R+ (published in [1], pp. 381–391) using two structural connectives (commas and semicolons) to the left of the turnstile, and with a single formula to the right. Here, the commas represent conjunction and the semicolons represent an intensional conjunction, called “fusion”. This is all nicely set out in McRobbie [19], where he also introduces left-handed Gentzenizations and analytic tableaux for a number of fragments of relevant logics. In 1979, further work on distributionless logic was done by Grishin, in a series of papers, including [16], in which he produced a Gentzenization of quantified RW without distribution (which we will call LRWQ), and used it to prove the decidability of this quantified logic.

Conjecture (1) of [Ma83] is confirmed here by the following result: if 3 ≤ α < ω, then there is a finite relation algebra of dimension α, which is not a relation algebra of dimension α + 1. A logical consequence of this theorem is that for every finite α ≥ 3 there is a formula of the form S ⊆ T (asserting that one binary relation is included in another), which is provable with α + 1 variables, but not provable with only α variables (using a special sequent calculus designed for deducing properties of binary relations).

It is consistent that there is a set mapping from the four-tuples of ωn into the finite subsets with no free subsets of size tn for some natural number tn. For any n < ω it is consistent that there is a set mapping from the pairs of ωn into the finite subsets with no infinite free sets. For any n < ω it is consistent that there is a set mapping from the pairs of ωn into ωn with no uncountable free sets.

Let A2 be the axiomatic system of second order arithmetic as described in [2]. One of the models of A2 is the “principal model” Mpr consisting of all integers and all sets of integers. Obviously there exist many denumerable ω-models elementarily equivalent to Mpr and we shall deal in this paper with some questions pertaining to this family which we denote by .

In §1 we define a rather natural relation ε between two denumerable families of sets of integers. From the upward Skolem-Löwenheim theorem it follows easily that there exists a family ordered by ε in the type ω1, but it is not immediately obvious whether there exist a subfamily of not well-ordered by ε. In the present paper we construct such a family of type η. ω1 where η is the order type of rationals and indicate some applications to hyperdegrees.

We adopt the terminology and notation of [2], with the only change that we adjoin to the language of A2 the constants ν0, ν1, … for the consecutive numerals 0, 1, 2, … and axioms which characterise them:

Also we modify the axioms of A2 given in [2] by prefixing them by general quantifiers bounded either to S or to N.

It is proved that the following conditions are equivalent:

(a) there exists a complete, atomless, σ–centered Boolean algebra, which does not contain any regular, atomless, countable subalgebra.

(b) there exists a nowhere dense ultrafilter on ω.

Therefore, the existence of such algebras is undecidable in ZFC. In “forcing language” condition (a) says that there exists a non–trivial σ–centered forcing not adding Cohen reals.

The starting point of this article is an old question asked by Feferman in his paper on Hancock's conjecture [6] about the strength of . This theory is obtained from the well-known theory ID1 by restricting fixed point induction to formulas that contain fixed point constants only positively. The techniques used to perform the proof-theoretic analysis of also permit to analyze its transfinitely iterated variants . Thus, we eventually know that

We apply Hrushovski-Fraïsseé's amalgamation procedure to obtain a theory of fields of prime characteristic of Morley rank 2 equipped with a definable additive subgroup of rank 1.

Recursion theory has been dominated by one example. The notion of a dominical category was introduced (see [2] and [3]) at least in part in the hope of subverting this dominance. The structures of number theory, freed from this original context, led to much of modern algebra with a consequent enrichment of number theory itself: it seemed not unreasonable to attempt to contribute, however modestly, to a similar development of recursion theory. Thus (in the loosest sort of analogy) recursion categories are intended to stand in relation to the class of partial recursive functions as rings do to the rational integers.

But if such a generalization is to serve its intended purpose, it ought to allow examples substantially different in spirit from the prototype. Recursion categories are, of course, the proper generalization of classical recursion theory. As a novice in this formidable field I am incapable of encompassing its full extent and must rely on the advice of others (I thank in particular R. DiPaola) in concluding that most of these earlier generalizations are not of this character. Indeed, the examples of recursion categories so far adduced (cf., in addition to the references above, [1] and [4]) are themselves closely tied to the classical one.

We attempt here to open the door to radically disparate examples by proving an existence theorem allowing the construction of recursion categories in a wide, and so far unexplored, variety of contexts very distant from that of the natural or ordinal numbers and their subsets, the locus of the traditional theory.

In order to do this, it has been necessary to introduce a number of unfamiliar notions—unfamiliar, that is, even in the context of the earlier discussion of dominical categories. This novelty is perhaps mitigated by the fact that, however unfamiliar, they cannot be said to be unusual, as the discussion later will show. We mention in particular those of a “formally free semigroup”, which retains the indexation function of a free semigroup, while giving up the characteristic universal property and that of “uniform generation”, which generalizes finite generation in the fashion assorted to our argument.