One of this author's favorite theorems has long been the Zero-One law discovered independently by Glebskii et al. [12] and Ron Fagin [10]. Let A be any first-order property of graphs and let µn(A) be the proportion of labelled graphs on n vertices for which A holds. Then

This result has inspired much work by logicians, generally in the direction of showing (1) for some powerful languages. Thus it is known [5] that (1) holds when A is a sentence in fixed point logic and it is known [13] that (1) does not always hold when A is a sentence in second-order monadic logic. Here, however, we explore recent work in a totally different direction. Let G(n, p) denote the random graph on n vertices with edge probability p. (In §2 we define the random structures we will deal with.) A property A is an event in the probability space and Pr[G(n, p) ╞ A] is well defined. When p = 1/2, each labelled graph on n vertices has equal weight so that (1) may be rewritten

Fagin's proof actually gives that (2) holds for any constant 0 < p < 1.

We develop a Sylow theory for stable groups satisfying certain additional conditions (2- finiteness, solvability or smallness) and show that their maximal p-subgroups are locally finite and conjugate. Furthermore, we generalize a theorem of Baer-Suzuki on subgroups generated by a conjugacy class of p-elements.

Illative combinatory logic consists of the theory of combinators or lambda calculus extended by extra constants (and corresponding axioms and rules) intended to capture inference. The paper considers systems of illative combinatory logic that are sound for first-order propositional and predicate calculus. The interpretation from ordinary logic into the illative systems can be done in two ways: following the propositions-as-types paradigm, in which derivations become combinators or, in a more direct way, in which derivations are not translated. Both translations are closely related in a canonical way. The two direct translations turn out to be complete. The paper fulfills the program of Church [1932], [1933] and Curry [1930] to base logic on a consistent system of λ-terms or combinators. Hitherto this program had failed because systems of ICL were either too weak (to provide a sound interpretation) or too strong (sometimes even inconsistent).

Let E be a equivalence relation for which there does not exist a perfect set of inequivalent reals. If 0* exists or if V is a forcing extension of L, then there is a good well-ordering of the equivalence classes.

In this note, we consider Keisler's stability theory and prove that every measure over a small submodel has a locally pure extension.

Does V = L? Is the Axiom of Constructibility true? Most people with an opinion would answer no. But on what grounds? Despite the near unanimity with which V = L is declared false, the literature reveals no clear consensus on what counts as evidence against the hypothesis and no detailed analysis of why the facts of the sort cited constitute evidence one way or another. Unable to produce a well-developed argument one way or the other, some observers despair, retreating to unattractive fall-back positions, e.g., that the decision on whether or not V = L is a matter of personal aesthetics. I would prefer to avoid such conclusions, if possible. If we are to believe that L is not V, as so many would urge, then there ought to be good reasons for this belief, reasons that can be stated clearly and subjected to rational evaluation. Though no complete argument has been presented, the literature does contain a number of varied argument fragments, and it is worth asking whether some of these might be developed into a persuasive case.

One particularly simple approach would be to note that the existence of a measurable cardinal (MC) implies that V ≠ L,1 and to argue that there is a measurable cardinal. The drawback to this approach is that its implying V ≠ L cannot then be counted as evidence in favor of MC, as it often is. Indeed, there seems to have been considerable sentiment against V = L even before the proof of its negation from MC,2 and this sentiment must either be accounted for as reasonable or explained away as an aberration of some kind.

A minimal formula is a formula which is minimal in provable formulas with respect to the substitution relation. This paper shows the following: (1) A β-normal proof of a minimal formula of depth 2 is unique in NJ. (2) There exists a minimal formula of depth 3 whose βη-normal proof is not unique in NJ. (3) There exists a minimal formula of depth 3 whose βη-normal proof is not unique in NK.

We conclude the discussion of additivity, Baire number, uniformity, and covering for measure and category by constructing the remaining 5 models. Thus we complete the analysis of Cichoń's diagram.

By ℬ2 we denote the σ-ideal of all subsets A of the Cantor set {0, 1}ω such that for every infinite subset T of ω the restriction A∣{0, 1}T is a proper subset of {0, 1}T. In this paper we investigate set theoretical properties of this and similar ideals.

It is proved that—consistently — there can be no ccc closed P-sets in the remainder space ω*.

The interest in fragments of predicate logics is motivated by the well-known fact that full classical predicate calculus is undecidable (cf. Church [1936]). So it is desirable to find decidable fragments which are in some sense “maximal”, i.e., which become undecidable if they are “slightly” extended. Or, alternatively, we can look for “minimal” undecidable fragments and try to identify the vague boundary between decidability and undecidability. A great deal of work in this area concerning mainly classical logic has been done since the thirties. We will not give a complete review of decidability and undecidability results in classical logic, referring the reader to existing monographs (cf. Suranyi [1959], Lewis [1979], and Dreben, Goldfarb [1979]). A short summary can also be found in the well-known book Church [1956]. Let us recall only several facts. Herein we will consider only logics without functional symbols, constants, and equality.

(C1) The fragment of the classical logic with only monadic predicate letters is decidable (cf. Behmann [1922]).

(C2) The fragment of the classical logic with a single binary predicate letter is undecidable. (This is a consequence of Gödel [1933].)

(C3) The fragment of the classical logic with a single individual variable is decidable; in fact it is equivalent to Lewis S5 (cf. Wajsberg [1933]).

(C4) The fragment of the classical logic with two individual variables is decidable (Segerberg [1973] contains a proof using modal logic; Scott [1962] and Mortimer [1975] give traditional proofs.)

(C5) The fragment of the classical logic with three individual variables and binary predicate letters is undecidable (cf. Surańyi [1943]). In fact this paper considers formulas of the following type

φ,ψ being quantifier-free and the set of binary predicate letters which can appear in φ or ψ being fixed and finite.

The problem of coding relations by means of a single binary relation is well known in the mathematical literature. It was considered in interpretation theory, and also in connection with investigations of decidability of elementary theories. Using various constructions (see, e.g., [2,6], proofs of Theorem 11 in [7] and Theorem 16.51 in [3]), for any model for a countable language, one can construct a model for ℒp (a language with a single binary relation symbol ) in which is interpretable. Each of the mentioned constructions has the same weak point: the universe of is different than the universe of . In [4] we have shown that, in the infinite case, one can eliminate this defect, i.e., for any infinite , we have constructed a model , having the same universe as , in which is elementarily definable. In all constructions mentioned above, it appears that formulas, which define in ( in ), are very complicated. In the present paper, another construction of a model for ℒp is given.

Let ω be the set of natural numbers, let be the lattice of recursively enumerable subsets of ω, and let A be the lattice of subsets of ω which are recursively enumerable in A. If U, V ⊆ ω, put U =* V if the symmetric difference of U and V is finite.

A natural and interesting question is then to discover what the relation is between the Turing degree of A and the isomorphism class of A. The first result of this form was by Lachlan, who proved [6] that there is a set A ⊆ ω such that A ≇ . He did this by finding a set A ⊆ ω and a set C ϵ A such that the structure ({W ϵ A∣W ⊇ C},∪,∩)/=* is a Boolean algebra and is not isomorphic to the structure ({W ϵ ∣W ⊇ D},∪,∩)/=* for any D ϵ . There is a nonrecursive ordinal which is recursive in the set A which he constructs, so his set A is not (see, for example, Shoenfield [11] for a definition of what it means for a set A ⊆ ω to be ). Feiner then improved this result substantially by proving [1] that for any B ⊆ ω, B′ ≇ B, where B′ is the Turing jump of B. To do this, he showed that for each X ⊆= ω there is a Boolean algebra which is but not and then applied a theorem of Lachlan [6] (definitions of and Boolean algebras will be given in §2). Feiner's result is of particular interest for the case B = ⊘, for it shows that the set A of Lachlan can actually be chosen to be arithmetical (in fact, ⊘′), answering a question that Lachlan posed in his paper. Little else has been known.

The study of filters on Pκλ started by Jech [5] as a natural generalization of that of filters on an uncountable regular cardinal κ. Several notions including weak normality have been generalized. However, there are two versions proposed as weak normality for filters on Pκλ. One is due to Abe [1] as a straightforward generalization of weak normality for filters on κ due to Kanamori [6] and the other is due to Mignone [8]. While Mignone's version is weaker than normality, Kanamori-Abe's version is not in general. In fact, Abe [2] has proved, generalizing Kanamori [6], that a filter is weakly normal in the sense of Abe iff it is weakly normal in the sense of Mignone and there exists no disjoint family of cfλ-many positive sets. Therefore Kanamori-Abe's version is essentially a large cardinal property and Mignone's version seems to be the most natural formulation of “weak” normality.

In this paper, we study weak normality in the sense of Mignone. In [8], Mignone studies weak normality of canonically defined filters. We complement his chart and try to find the weakly normal closures of these filters (i.e., the minimal weakly normal filters extending them). Therefore our result is a natural refinement of Carr [4].

It is now well known that combinatorics on Pκλ is not a naive generalization of that on κ. For example, Menas [7] showed that stationarity on Pκλ can be characterized by 2-dimensional regressive functions, but not by 1-dimensional ones when λ is strictly larger than κ. We show in terms of weak normality that combinatorics on Pκλ vary drastically with respect to cfλ.

In a series of papers culminating in [9], M. Talagrand, the second author, and others investigated at length the properties and structure of pointwise compact sets of measurable functions. A number of problems, interesting in themselves and important for the theory of Pettis integration, were solved subject to various special axioms. It was left unclear just how far the special axioms were necessary. In particular, several results depended on the fact that it is consistent to suppose that every countable relatively pointwise compact set of Lebesgue measurable functions is ‘stable’ in Talagrand's sense, the point being that stable sets are known to have a variety of properties not shared by all pointwise compact sets. In the present paper we present a model of set theory in which there is a countable relatively pointwise compact set of Lebesgue measurable functions which is not stable and discuss the significance of this model in relation to the original questions. A feature of our model which may be of independent interest is the following: in it, there is a closed negligible set Q ⊆ [0, 1]2 such that whenever D ⊆ [0,1] has outer measure 1, then

has inner measure 1 (see 2G below).

We embark immediately on the central ideas of this paper, setting out a construction of a partially ordered set which forces a fairly technical proposition in measure theory (IS below); the relevance of this proposition to pointwise compact sets will be discussed in §2.

In recent work, Cooper [3, 1990] has extended results of Jockusch and Shore [6, 1984] to show that the Turing jump is definable in the structure given by the Turing degrees and the ordering of Turing reducibility. In his definition of x′ from x, Cooper identifies an order-theoretic property shared by all of the degrees that are recursively enumerable in x and above x. He then shows that x′ is the least upper bound of all the degrees with this property. Thus, the jump of x is identified by comparing the recursively enumerable degrees with other degrees which are not recursively enumerable. Of course, once the jump operator is known to be definable, the relation of jump equivalence x′ = y′ is also known to be a definable relation on x and y. If we consider how much of the global theory of the Turing degrees is sufficient for Cooper's methods, it is immediately clear that his methods can be implemented to show that the jump operator and its weakening to the relation of jump equivalence are definable in any ideal closed under the Turing jump. However, his methods do not localize to , the degrees, or to the recursively enumerable degrees.

This paper fits, as do Shore and Slaman [16, 1990] and [17, to appear], within the general project to develop an understanding of the relationship between the local degree-theoretic properties of a recursively enumerable set A and its jump class. For an analysis of the possibility of defining jump equivalence in , consult Shore [15, to appear] who shows that the relation x(3) = y(3) is definable. In this paper, we will restrict our attention to definitions expressed completely in ℛ (Note: All sets and degrees discussed for the remainder of this paper will be recursively enumerable.) Ultimately, one would like to find some degree-theoretic properties definable in terms of the ordering of Turing reducibility and quantifiers over the recursively enumerable degrees that would define the relation of jump equivalence or define one or more of the jump classes Hn = {w∣ wn = 0n+1} or Ln = {w ∣ wn = 0n}. Such a result could very likely then be used as a springboard to other general definability results for the recursively enumerable degrees. It would be especially interesting to know whether every recursively enumerable degree is definable and whether every arithmetical degree-invariant property of the recursively enumerable sets is definable in .

We give an example of a countable theory T such that for every cardinal λ ≥ ℵ2 there is a fully indiscernible set A of power λ such that the principal types are dense over A, yet there is no atomic model of T over A. In particular, T(A) is a theory of size λ where the principal types are dense, yet T(A) has no atomic model.

We study the strength (over bounded induction) of axioms expressing particular cases of the Chinese Remainder Theorem with respect to the axiom ∀x, y∃z (z = xy).

We will consider some partition properties of the following type: given a function F: ωω →2, is there a sequence H0, H1, … of subsets of ω such that F is constant on ΠiεωHi? The answer is obviously positive if we allow all the Hi's to have exactly one element, but the problem is nontrivial if we require the Hi's to have at least two elements. The axiom of choice contradicts the statement “for all F: ωω→ 2 there is a sequence H0, H1, H2,… of subsets of ω such that {i|(Hi) ≥ 2} is infinite and F is constant on ΠHi”, but the infinite exponent partition relation ω(ω)ω implies it; so, this statement is relatively consistent with an inaccessible cardinal. (See [1] where these partition properties were considered.)

We will also consider partitions into any finite number of pieces, and we will prove some facts about partitions into ω-many pieces.

Given a partition F: ωω → k, we say that H0, H1…, a sequence of subsets of ω, is homogeneous for F if F is constant on ΠHi. We say the sequence H0, H1,… is nonoverlapping if, for all i ∈ ω, ∪Hi > ∩Hi+1.

The sequence 〈Hi: i ∈ ω〉 is of type 〈α0, α1,…〉 if, for every i ∈ ω, ∣Hi∣ = αi.

We will adopt the usual notation for polarized partition relations due to Erdös, Hajnal, and Rado.

means that for every partition F: κ1 × κ2 × … × κn→δ there is a sequence H0, H1,…, Hn such that Hi ⊂ κi and ∣Hi∣ = αi for every i, 1 ≤ i ≤ n, and F is constant on H1 × H2 × … × Hn.

Models of normal open induction (NOI) are those discretely ordered rings, integrally closed in their fraction field whose nonnegative part satisfy Peano's induction axioms for open formulas in the language of ordered semirings.

Here we study the problem of representability of an element a of a model M of NOI (in some extension of M) by a quadratic form of the type X2 + b Y2 where b is a nonzero integer. Using either a trigonometric or a hyperbolic parametrization we prove that except in some trivial cases, M[x, y] with x2 + by2 = a can be embedded in a model of NOI.

We also study quadratic extensions of a model M of NOI; we first prove some properties of the ring of Gaussian integers of M. Then we study the group of solutions of a Pell equation in NOI; we construct a model in which the quotient group by the squares has size continuum.