Ever since Cohen invented forcing in 1963, people have studied the properties that cardinals can have in generic extensions of the ground model. A very early result of Lévy shows that if κ is a regular cardinal and λ > κ is strongly inaccessible, then there is a notion of forcing which collapses every cardinal strictly between κ and λ yet preserves every other cardinal. This, of course, answers one question of the genre “What properties can a cardinal have in a generic extension?”

Another question of the same genre that can be asked is the following: Is it possible to have a generic extension of the ground model in which all cardinals are preserved and yet the cofinalities of some cardinals are different? This question was first answered in the affirmative by Prikry, who proved the following theorem.

Theorem 1.1 (Prikry [5]). Assume that V ⊨ “ZFC + κ is measurable”. Then there is a notion of forcing, P, such that for G V-generic over P:

(1) V and V[G] have the same cardinals.

(2) V and V[G] have the same bounded subsets of κ.

(3) V[G], i.e, V[G] ⊨ “κ is Rowbottom”.

(4) V[G] ⊨ “cof(κ) = ω”.

Prikry's result naturally raises the following question: Is it possible to get a generic extension in which cardinals are preserved and yet the cofinalities of certain cardinals are different from the ground model's but are uncountable? This question was first answered in the affirmative by Magidor, who proved the following theorem.

We present Woodin's proof that if there exists a measurable Woodin cardinal δ then there is a forcing extension satisfying all sentences ϕ such that CH + ϕ holds in a forcing extension of V by a partial order in Vδ. We also use some of the techniques from this proof to show that if there exists a stationary limit of stationary limits of Woodin cardinals, then in a homogeneous forcing extension there is an elementary embedding j: V → M with critical point such that M is countably closed in the forcing extension.

We introduce the notion of skinniness for subsets of and its variants, namely skinnier and skinniest. We show that under some cardinal arithmetical assumptions, precipitousness or 2λ-saturation of NSκλ ∣ X, where NSκλ denotes the non-stationary ideal over , implies the existence of a skinny stationary subset of X. We also show that if λ is a singular cardinal, then there is no skinnier stationary subset of . Furthermore, if λ is a strong limit singular cardinal, there is no skinny stationary subset of . Combining these results, we show that if λ is a strong limit singular cardinal, then NSκλ ∣ X can satisfy neither precipitousness nor 2λ-saturation for every stationary X ⊆ . We also indicate that , where , is equivalent to the existence of a skinnier (or skinniest) stationary subset of under some cardinal arithmetical hypotheses.

In this paper we prove:

Theorem 1. Any finite model of the axiom of power-set also satisfies the axioms of extensionality, sum-set and choice.

Clearly, it will follow from (2) below that in a finite model the axiom of power-set is satisfied if and only if every set is a power-set. Thus, Theorem 1 follows immediately from Theorem 2 below, where by a theory of sets we mean a first-order theory without identity and with only one binary predicate symbol ∈.

Theorem 2. If in a theory of sets every set is a power-set and if the axiom of power-set is valid, then the axioms of extensionality, sum-set and choice are valid.

The proof of Theorem 2 will follow from the lemmas which we establish below.

We mean by x = y that x and y have the same elements. We denote a power-set of x by P(x) when it exists; similarly, we denote a sum-set of x by Ux.

Clearly, in every theory of sets we have:

(1) (x ⊂ y) ↔ (P(x) ⊂ P(y)),

(2) (x = y) ↔ (P(x) = P(y)),

(3) (x = y) → ((x ∈ P(z)) → (y ∈ P(z))),

(4) ⋃P(x) = x.

In view of (2), (3) and the definition of equality, we have:

Lemma 1. If in a theory of sets every set is a power-set, then equal sets are elements of the same sets.

We have also, in view of (4):

Lemma 2. If in a theory of sets every set is a power-set, then every set has a sum-set.

Professor R. L. Goodstein's neat proposal for formalising and proving the Policeman — the logical truth mentioned in my paper — illustrates the main thesis of that paper, viz., that in formalising the logic of indirect discourse one needs to avoid assigning what was said, and the report that it was said, to different levels of a semantical hierarchy. But there are two main difficulties in his proposal:

1. It is not quite clear whether the axioms and rules of Prof. Goodstein's system are to be such that substitutivity of the biconditional is maintained for all wff. If so, the system takes no account of the referentially opaque quality of indirect discourse. For example, the analogue for “If Sir Walter Scott always says the same as the author of Waverley, then George III says that anything Sir Walter Scott says is true if and only if George III says that anything the author of Waverley says is true” would be provable, though this statement is not logically true. If “A(x){Bx→x)” is well-formed (as it must be for Professor Goodstein's proof), the corresponding theorem is

2. In interpreting the letters “A”, “B”, etc. as operators, so that sentences are the substitution-instances both for variables like “x” and for schematic functions of those variables like “Ax”, Professor Goodstein's system does not provide for formalising logical truths in which ordinary predication also plays a part: e.g., “If the policeman says that all women are dangerous drivers and anything the policeman says is true, then no non-dangerous drivers are women”.

To each computable enumerable (c.e.) set A with a particular enumeration {As}s∈ω there is associated a settling function mA(x), where mA(x) is the last stage when a number less than or equal to x was enumerated into A. One c.e. set A is settling time dominated by another set B (B >stA) if for every computable function f, for all but finitely many x, mB(x) > f(mA(x)). This settling-time ordering, which is a natural extension to an ordering of the idea of domination, was first introduced by Nabutovsky and Weinberger in [3] and Soare [6]. They desired a sequence of sets descending in this relationship to give results in differential geometry. In this paper we examine properties of the <st ordering. We show that it is not invariant under computable isomorphism, that any countable partial ordering embeds into it. that there are maximal and minimal sets, and that two c.e. sets need not have an inf or sup in the ordering. We also examine a related ordering, the strong settling-time ordering where we require for all computable f and g, for almost all x, mB(x) > f(mA(g(x))).

With reservations, one can think of abstract algebra as the study of what consequences can be drawn from the axioms associated with certain concrete algebraic structures. Two important examples of such concrete algebraic structures are the integers and the rational numbers. The integers and the rational numbers have two properties which are not in general mirrored in the abstract axiom systems associated with them. That is, the integers and the rational numbers both have effectively computable metrics and their algebraic operations are effectively computable. The study of abstract algebraic systems which possess effectively computable algebraic operations has produced many interesting results. One can think of a computable algebraic structure as one whose elements have been labeled by the set of positive integers and whose operations are effectively computable. The formal definition of computable local integral domain will be given in §3. Some specific computable structures which have been studied are the integers, the rational numbers, and the rational numbers with p-adic valuation. Computable structures were studied in general by Rabin [12]. This paper concerns computable local integral domains as exemplified by the local integral domain Zp. Zp is the localization of the integers with respect to the maximal prime ideal generated by the positive prime p. We should note that the concept of local integral domain is not first order.

Let the ordered pair (Q, M) stand for a local ring, where Q is the local ring and M is the unique maximal prime ideal of Q. Since most of my results are proving the existence of certain effective procedures, the assumption that Q has a principal maximal ideal M (rather than M has n generators) greatly simplifies many of the proofs.

The Rice-Shapiro Theorem [4] says that the index set of a class of recursively enumerable (r.e.) sets is r.e. if and only if consists of all sets which extend an element of a canonically enumerable sequence of finite sets. If an index of a difference of r.e. (d.r.e.) sets is defined to be the pair of indices of the r.e. sets of which it is the difference, then the following generalization due to Hay [3] is obtained: The index set of a class of d.r.e. sets is d.r.e. if and only if is empty or consists of all sets which extend a single fixed finite set. In that paper Hay also classifies index sets of classes consisting of d.r.e. sets which extend one of a finite collection of finite sets. These sets turn out to be finite Boolean combinations of r.e. sets. The question then arises “What about the classification of the index set of a class consisting of d.r.e. sets which extend an element of a canonically enumerable sequence of finite sets?” The results in this paper come from an attempt to answer this question.

Since classes of sets which are Boolean combinations of r.e. sets form a hierarchy (the finite Ershov hierarchy, see Ershov [1]) with the r.e. and d.r.e. sets respectively levels 1 and 2 of this hierarchy, we may define index sets of classes of level n sets. If is a class of level n sets which extend some element of a canonically enumerable sequence of finite sets and if we let co-, then we extend the original classification question to the classification of the index sets of the classes and co-.

Now if the sequence of finite sets enumerates only finitely many sets or if only finitely many of the finite sets are minimal under inclusion, then it is a routine computation to verify that the index sets of and co- are in the finite Ershov hierarchy. Thus we are interested in the case in which infinitely many of the sequence of finite sets are minimal under inclusion. However if the infinite sequence is fairly simple, for instance{0}, {1}, {2}, … then the r.e. index set of co- is Σ20-complete as well as the index sets of and co- for all levels n > 2. Since the finite Ershov hierarchy does not exhaust ⊿20 there is a lot of “room” between these two extreme cases.

It is known that the usual definition of a dense series without extreme elements is complete with respect to first-order functions, in the sense that any first-order function on the base of a set of postulates defining such a series either is implied by the postulates or is inconsistent with them. It is here understood, in accordance with the usual convention, that when we speak of a function on the base , the function shall be such as to place restrictions only upon elements belonging to the class determined by f; or, more exactly, every variable with a universal prefix shall occur under the hypothesis that its values satisfy f, while every variable with an existential prefix shall have this condition categorically imposed upon it.

Consider a set of postulates defining a dense series without extreme elements, and add to this set the condition of Dedekind section, to be formulated as follows. Let the conjunction of the three functions,

be written H(ϕ), where the free variables f and g, being parameters throughout, are suppressed. This is the hypothesis of Dedekind's condition, and the conclusion is

which may be written C(ϕ).

We give three counterexamples to the folklore claim that in an arbitrary theory, if a complete type p over a set B does not divide over $C\subseteq B$, then no extension of p to a complete type over $\operatorname {acl}(B)$ divides over C. Two of our examples are also the first known theories where all sets are extension bases for nonforking, but forking and dividing differ for complete types (answering a question of Adler). One example is an $\mathrm {NSOP}_1$ theory with a complete type that forks, but does not divide, over a model (answering a question of d’Elbée). Moreover, dividing independence fails to imply M-independence in this example (which refutes another folklore claim). In addition to these counterexamples, we summarize various related properties of dividing that are still true. We also address consequences for previous literature, including an earlier unpublished result about forking and dividing in free amalgamation theories, and some claims about dividing in the theory of generic $K_{m,n}$-free incidence structures.

We construct a non-discrete Polish group none of whose non-discrete subgroups admits a complete left-invariant metric.

Say that an incomplete d.r.e. degree has almost universal cupping property, if it cups all the r.e. degrees not below it to 0′. In this paper, we construct such a degree d, with all the r.e. degrees not cupping d to 0′ bounded by some r.e. degree strictly below d. The construction itself is an interesting 0″′ argument and this new structural property can be used to study final segments of various degree structures in the Ershov hierarchy.