In [5], Metakides and Nerode introduced the study of recursively enumerable (r.e.) substructures of a recursively presented structure. The main line of study presented in [5] is to examine the effective content of certain algebraic structures. In [6], Metakides and Nerode studied the lattice of r.e. subspaces of a recursively presented vector space. This lattice was later studied by Kalantari, Remmel, Retzlaff and Shore. Similar studies have been done by Metakides and Nerode [7] for algebraically closed fields, by Remmel [10] for Boolean algebras and by Metakides and Remmel [8] and [9] for orderings. Kalantari and Retzlaff [4] introduced and studied the lattice of r.e. subsets of a recursively presented topological space. Kalantari and Retzlaff considered X, a topological space with ⊿, a countable basis. This basis is coded into integers and with the help of this coding, r.e. subsets of ω give rise to r.e. subsets of X. The notion of “recursiveness” of a topological space is the natural next step which gives rise to the question of what should be the “degree” of an r.e. open subset of X? It turns out that any r.e. open set partitions ⊿; into four sets whose Turing degrees become central in answering the question raised above.

In this paper we show that the degrees of the elements of the partition of ⊿ imposed by an r.e. open set can be “controlled independently” in a sense to be made precise in the body of the paper. In [4], Kalantari and Retzlaff showed that given A any r.e. set and any r.e. open subset of X, there exists an r.e. open set ℋ which is a subset of and is dense in (in a topological sense) and in which A is coded. This shows that modulo a nowhere dense set, an r.e. open set can become as complicated as desired. After giving the general technical and notational machinery in §1, and giving the particulars of our needs in §2, in §3 we prove that the set ℋ described above could be made to be precisely of degree of A. We then go on and establish various results (both existential and universal) on the mentioned partitioning of ⊿. One of the surprising results is that there are r.e. open sets such that every element of partitioning of ⊿ is of a different degree. Since the exact wording of the results uses the technical definitions of these partitioning elements, we do not summarize the results here and ask the reader to examine §3 after browsing through §§1 and 2.

Cet article ne contient rien de révolutionnaire, et son auteur a conscience du risque qu'il court de le voir dépassé, lors de sa parution, par des travaux plus profonds. Il a pensé qu'il n'était pas inutile de publier, faute de mieux, les résultats simples auxquels il est parvenu (le lecteur lui saura gré de ce caractère reposant), en espérant qu'il passeront à la postérité sous forme d'exercices dans les manuels futurs où les petits enfants apprendront la théorie des modèles.

Il s'agit de groupes stables; on sait depuis longtemps que la stabilité de la théorie d'un groupe impose des “conditions de chaîne” sur ses sous-groupes définissables : l'exploitation de ce phénomène, de nature bien algébrique, qui est brièvement exposé dans la première section de cet article, a fait le bonheur d'une génération de théoriciens des modèles. Un autre phénomène, plus subtil, semble ne pas avoir épuisé sa substance : c'est celui, dont l'apparition remonte aux travaux de B. Zilber, qui est décrit dans [7] sous le nom de “types de strate maximum”, et dans [2] sous le nom de “large sets”; la deuxième section lui est consacrée: elle a été écrite dans le désir de montrer l'équivalence de ces deux approches, et aussi par repentir de n'avoir pas suffisament éclairé ses motivations dans [7]. Ce souci d'unification a eu une influence, que j'espère salutaire, sur le vocabulaire: je parle ici de “types génériques” et d'“ensembles (ou de formules) génériques”. Ces termes, ainsi que celui de “composante connexe”, sont empruntés au langage de la géométrie: un groupe algébrique, étant définissable dans la théorie d'un corps algébriquement clos, est stable, et ses “types génériques” sont les “points génériques” des géomètres.

We review some known results about the Ramsey property for partitions of reals, and we present a certain two-person game such that if either player has a winning strategy then a homogeneous set for the partition can be constructed, and conversely. This gives alternative proofs of some of the known results. We then discuss possible uses of the game in obtaining effective versions of Ramsey's theorem and prove a theorem along these lines.

There are several ways for a formula to be “the contrary” of a thesis. When there is a negation we could call a formula an “antithesis” if it is the negation of a thesis—or its negation is a thesis—both properties being equivalent when the negation is classical.

When there is no negation or when the connective called “negation” is very different from classical negation, we are forced to look for a different notion.

Whence:

Definition 1. In a propositional calculus, a substitution antithesis—or, for short, an s-antithesis—is a formula no instance of which is a thesis.

There is another kindred notion, but only for calculi for which a deducibility has been defined:

Definition 2. A deduction antithesis—for short, a d-antithesis—is a formula from which every formula is deducible.

Both notions have been used in the study of the deducibility of certain systems (see below, §4).

In the classical propositional calculus, the s-antitheses are simply the formulas which are negations of theses (and whose negations are theses).

In S5 and in all the weaker modal propositional calculi, there are s-antitheses which are not negations of theses (and whose negations are not theses); typical examples are ¬(Mp ⊃ Lp) and ¬(p ⊃ Lp) where p is a propositional variable, and ⊃, ¬, M and L are respectively material implication, negation, possibility and necessity (see [8]).

It is well known that many statements provable from combinatorial principles true in the constructible universe L can also be shown to be consistent with ZFC by forcing. Recent work by Shelah and Stanley [4] and the author [5] has clarified the relationship between the axiom of constructibility and forcing by providing Martin's Axiom-type forcing axioms equivalent to ◊ and the existence of morasses. In this paper we continue this line of research by providing a forcing axiom equivalent to □κ. The forcing axiom generalizes easily to inaccessible, non-Mahlo cardinals, and provides the motivation for a corresponding generalization of □κ.

In order to state our forcing axiom, we will need to define a strategic closure condition for partial orders. Suppose P = 〈P, ≤〉 is a partial order. For each ordinal α we will consider a game played by two players, Good and Bad. The players choose, in order, the terms in a descending sequence of conditions 〈pβ∣β < α〉 Good chooses all terms pβ for limit β, and Bad chooses all the others. Bad wins if for some limit β<α, Good is unable to move at stage β because 〈pγ∣γ < β〉 has no lower bound. Otherwise, Good wins. Of course, we will be rooting for Good.

In [6], Nadel showed that if is a recursively saturated model of Pr = Th(ω, +) of power at most ℵ1, then there is a model such that ≡ ∞ω and can be expanded to a recursively saturated model of P. For a fixed completion T of P, can be chosen to have a recursively saturated expansion to a model of T just in case is recursive in T-saturated. (“Recursive in T-saturation” is defined just like recursive saturation except that the sets of formulas considered are those that are recursive in T.)

Nadel also showed in [6] that for a fixed completion T of P, a countable nonstandard model of Pr can be expanded to a model of T (not necessarily recursively saturated) iff satisfies a condition called “exp(T)-saturation.” This condition is stronger than recursive saturation but weaker than recursive in T-saturation. Nadel left open the problem of characterizing the models of Pr of power ℵ1 such that for some , ≣ ∞ω and can be expanded to a model of T. The present paper gives such a characterization. The condition on is that it is recursively saturated, and for each n ∈ ω, the set Tn of Πn-sentences of T is recursive in some type realized in .

This result can be interpreted in various ways, just as the results from [6] were interpreted in various ways in [4]. Friedman [2] introduced the notion of a “standard system.”

We say that a set A of reals is recursive in a real y together with a set B of reals if one can imagine a computing machine with an ability to perform a countably infinite sequence of program steps in finite time and with oracles for B and y so that decides membership in A for any real x input to by way of an oracle for x. We write A ≤ yB. A precise definition of this notion of recursion was first considered in Kleene [9]. In the notation of that paper, A ≤yB if there is an integer e so that χA(x) = {e}(x y, χB, 2E). Here χA is the characteristic function of A. Thus Kleene would say that A is recursive in (y, B, 2E), where 2E is the existential integer quantifier.

Gandy [5] observes that the halting problem for infinitary machines such as , as in the case of Turing machines, gives rise to a jump operator for higher type recursion. Thus given a set B of reals, the superjump B′ of B is defined to be the set of all triples 〈e, x, y〉 such that the eth machine with oracles for y and B eventually halts when given input x. A set A is said to be semirecursive in y together with B if for some integer e, A is the cross section {x: 〈e, x, y 〉 ∈ B′}. In Kleene [9] it is demonstrated that a set A is semirecursive in y alone if and only if it is

In this paper we continue the study of the structure of the lattice of recursively enumerable (r.e.) open subsets of a topological space. Work in this approach to effective topology began in Kalantari and Retzlaff [5] and continued in Kalantari [2], Kalantari and Leggett [3] and Kalantari and Remmel [4]. Studies in effectiveness of results in structures other than integers began with the work of Specker [17] and Lacombe [8] on effective analysis.

The renewed activity in the study of the effective content of mathematical structures owes much to Nerode's program and Metakides' and Nerode's [11], [12] work on vector spaces and fields. These studies have been extended by Kalantari, Remmel, Retzlaff, Shore and Smith. Similar studies on the effective content of other mathematical structures have been conducted. These include work on topological vector spaces, boolean algebras, linear orderings etc.

Kalantari and Retzlaff [5] began a study of effective topological spaces by considering a topological space with a countable basis ⊿ for the topology. The space X is to be fully effective; that is, the basis elements are coded into ω and the operations of intersection of basis elements and the relation of inclusion among them are both computable. An r.e. open subset of X is then represented as the union of basic open sets whose codes lie in an r.e. subset of ω.

In recent years higher recursion theory has experienced a deep interaction with other areas of logic, particularly set theory (fine structure, forcing, and combinatorics) and infinitary model theory. In this paper we wish to illustrate this interaction by surveying the progress that has been made in two areas: the global theory of the κ-degrees and the study of closure ordinals.

This paper looks at linear orders in the following way. A preordering is given, which is linear and recursively enumerable. By performing the natural identification, one obtains a linear order for which equality is not necessarily recursive. A format similar to Metakides and Nerode's [3] is used to study these linear orders. In effective studies of linear orders thus far, the law of antisymmetry (x ≦ y ∧ y ≦ x ⇒ y) has been assumed, so that if the order relation x ≦ y is r.e. then x < y is also r.e. Here the assumption is dropped, so that x < y may not be r.e. and the equality relation may not be recursive; the possibility that equality is not recursive leads to new twists which sometimes lead to negative results.

Reported here are some interesting preliminary results with simple proofs, which are obtained if one looks at these objects with a view to doing recursion theory in the style of Metakides and Nerode. (This style, set in [3], is seen in many subsequent papers by Metakides and Nerode, Kalantari, Remmel, Retzlaff, Shore, and others, e.g. [1], [4], [6], [7], [8], [11]. In a sequel, further investigations will be reported which look at r.e. presented linear orders in this fashion and in the context of Rosenstein's comprehensive work [10].

Obviously, only countable linear orders are under consideration here. For recursion-theoretic notation and terminology see Rogers [9].

Let be a well-founded model of ZFC whose class of ordinals has uncountable cofinality, such that has a Σn end extension for each n ∈ ω. It is shown in Theorem 1.1 that there is such a model which has no elementary end extension. In the process some interesting facts about topless end extensions (those with no least new ordinal) are uncovered, for example Theorem 2.1: If is a well-founded model of ZFC, such that has uncountable cofinality and has a topless Σ3 end extension, then has a topless elementary end extension and also a well-founded elementary end extension, and contains ordinals which are (in ) highly hyperinaccessible. In §3 related results are proved for κ-like models (κ any regular cardinal) which need not be well founded. As an application a soft proof is given of a theorem of Schmerl on the model-theoretic relation κ → λ. (The author has been informed that Silver had earlier, independently, found a similar unpublished proof of that theorem.) Also, a simpler proof is given of (a generalization of) a characterization by Keisler and Silver of the class of well-founded models which have a Σn end extension for each n ∈ ω. The case κ = ω1 is investigated more deeply in §4, where the problem solved by Theorem 1.1 is considered for non-well-founded models. In Theorems 4.1 and 4.4, ω1-like models of ZFC are constructed which have a Σn end extension for all n ∈ ω but have no elementary end extension. ω1-like models of ZFC which have no Σ3 end extension are produced in Theorem 4.2. The proof uses a notion of satisfaction class, which is also applied in the proof of Theorem 4.6: No model of ZFC has a definable end extension which satisfies ZFC. Finally, Theorem 5.1 generalizes results of Keisler and Morley, and Hutchinson, by asserting that every model of ZFC of countable cofinality has a topless elementary end extension. This contrasts with the rest of the paper, which shows that for well-founded models of uncountable cofinality and for κ-like models with κ regular, topless end extensions are much rarer than blunt end extensions.

The modern problem of infinity was first raised by Aristotle who held (at least on the popular interpretation) that infinite sets exist potentially (i.e. one more number can always be counted, one more division can always be made in a line segment) but not actually (i.e. the numbers or divisions cannot all exist at one time). In fact, Aristotle not only held that completed infinities never actually exist, but also that they are impossible, that is, that the assumption that they do exist leads to contradictions. To see this, consider Aristotle's view that mathematical entities depend for their existence on the existence of primary substance in which they inhere, coupled with his view that there can be no infinite body. From these it follows that if there were actual completed infinities, infinite bodies would both exist and not exist. The details here are not so important as the idea that if a completed infinite is assumed to exist a contradiction follows.

This negative attitude towards completed infinities flourished for centuries. By the mid-1500's, the German mathematician Stifel (who apparently also invented Pascal's triangle) was moved to condemn irrational numbers simply by their association with the completed infinite:

About a hundred years later, Galileo further discredited the completed infinite by pointing out that line segments of different lengths can be brought into one-to-one correspondence by projection, as can the natural numbers and the perfect squares by assigning each number to its square.

We discuss the problem of finding forcing posets which introduce closed unbounded subsets to a given stationary set.

We show that all QE rings of prime power characteristic are constructed in a straightforward way out of three components: a filtered Boolean power of a finite field, a nilpotent Jacobson radical, and the ring Zp. or the Witt ring W2(F4) (which is the characteristic four analogue of the Galois field with four elements).

The notations and the definitions used here are identical to those in [B.L.]. We also assume that the reader is familiar with the properties of the Rudin-Keisler order on types [L.].

Let T denote an ℵ0-stable countable theory. The main result in [B.L.] is: All countable models of T are almost homogeneous if and only if T satisfies

(*) For all models M of T and all ā ∈ M, if p ∈ S1(ā) is strongly regular multidimensional, then Dim(p; M) ≥ ℵ0.

In this paper we investigate the case of a theory T which does not satisfy condition (*) and, under certain additional assumptions, we construct nonisomorphic and non-almost-homogeneous countable models. The same type of construction has been used before to show that if T is multidimensional, then for all α ≥ 1, T has at least nonisomorphic models of cardinality ℵα [La.], [Sh.]. As a corollary of our main theorem (Theorem 6) and of the previous result in [B.L.], we prove Vaught's Conjecture (and, in fact, Martin's Strong Conjecture) for theories T with αT finite.

Although we are here interested in countable models, we can also note that our construction proves that theories satisfying the assumptions in Theorem 6 have at least nonisomorphic models of cardinality ℵα.

The theories considered here are countable and complete, and the types are all complete too. Let T be an L-theory. A sequence σ = (σn(ν))n∈ω of L-formulas is said to be independent (with respect to T) if for each α ∈ 2<ω, the sentence

is in T. As an example, let T = Th(Z, +), and let σ be the sequence of formulas saying (in the language of groups) ν is divisible by the nth prime, for n ∈ ω.

A theory T has an independent sequence of formulas just in case it has types. If T has one independent sequence σ, then it has other independent sequences of arbitrarily high degree. (These can be obtained by taking conjunctions of the formulas from σ. If T has an independent sequence that is recursive, or one that is recursive in some type, then T will have types of arbitrarily high degree. (This follows from the fact that the independent sequence can be used to encode any set in a type.)

Nadel and the author had wondered whether a theory with types must have an independent sequence of formulas that is recursive in one of the types. The main result of the present paper is an example of a recursive theory for which this is not the case.

Compactness of supervaluational semantics has long been an open problem. Recently, Peter Woodruff [2] showed that the full quantificational language is not compact. In the present note, I will show that the quantifier-free fragment of the language is compact. Since this result can be easily extended to the monadic quantificational language, and since Woodruff's result only requires the presence of one binary predicate, the two results combined give a complete solution of the problem.

My language L contains infinitely many individual constants, infinitely many n-ary predicates (for every n > 0), the usual connectives, the symbols E! and =, and parentheses. (Atomic) sentences are defined as usual, and Ab/a is the result of uniformly substituting b for a in the sentence A.

An interpretation of L is an ordered pair I = 〈D, φ〉, where D is a set (possibly empty) and φ is a unary function, total from the set of n-ary predicates into the power set of Dn, and partial from the set of constants into D.

A classical valuation for an interpretation I = 〈D, φ〉 is a total unary function V from the set of sentences into {T, F} such that

(a) if φ is defined for all of a1, …, am, then V(Pa1 … an) = T iff 〈φ(a1), …, φ(an)〉 ∈ φ(P);

(b) if φ(a) and φ(b) are both defined, then V(a = b) = T iff φ(a) = φ(b;

(c) if exactly one of φ(a) and φ(b) is defined, then V(a = b) = F;

(d) V(a = a) = T;

(e) if V(a = b) = T and A is atomic, then V(A) = V(Ab/a);

(f)V(E!a) = T iff φ(a) is defined;

(g) V(~ A) = T iff V(A) = F, and similarly for the other connectives.

A model M (of a countable first order language) is said to be finitely generated if it is prime over a finite set, namely if there is a finite tuple ā in M such that (M, ā) is a prime model of its own theory. Similarly, if A ⊂ M, then M is said to be finitely generated overA if there is finite ā in M such that M is prime over A ⋃ ā. (Note that if Th(M) has Skolem functions, then M being prime over A is equivalent to M being generated by A in the usual sense, that is, M is the closure of A under functions of the language.) We show here that if N is ā model of an ω-stable theory, M ≺ N, M is finitely generated, and N is finitely generated over M, then N is finitely generated. A corollary is that any countable model of an ω-stable theory is the union of an elementary chain of finitely generated models. Note again that all this is trivial if the theory has Skolem functions.

The result here strengthens the results in [3], where we show the same thing but assuming in addition that the theory is either nonmultidimensional or with finite αT. However the proof in [3] for the case αT finite actually shows the following which does not assume ω-stability): Let A be atomic over a finite set, tp(ā / A) have finite Cantor-Bendixson rank, and B be atomic over A ⋃ ā. Then B is atomic over a finite set.

We shall prove the following theorem: If κ is an infinite cardinal and Γ: P(κ) → cf κ a partition of the power-set of κ then we can find a homogeneous ⊿-system of size κ such that the kernel of the ⊿-system is in the same partition class as all the members of the ⊿-system.

ℵ2. One of the first examples of the forcing method is cardinal collapsing (A. Levy, see [5]), for example, collapsing ℵ2 to ℵ1: the poset P is the collection of all countable functions from a countable ordinal into ℵ2. As is well known, in VP, , and because P is closed under union of countable chains, remains a cardinal and, in fact, no new countable sets are added. But to prove that remains a cardinal we need to conclude ∣P∣ ≤ ℵ2 and hence ℵ3 is not collapsed. If it has been observed that is actually collapsed in VP. Hence the following theorem, which makes no assumptions on the continuum, is relevant.

1. Theorem. There is a poset R such that in VR ℵ2 becomes of cardinality ℵ1, but ℵ1 and the cardinals above ℵ2 are not collapsed.