bluuebunny/crossref_metadata_2025 huggingface dataset:
A remark on Scott's interpolation theorem for Lω1ω
Authors: Motoháshi Nobuyoshi
Published: May 2006

In [1], H. Africk proved that Scott's interpolation theorem does not hold in the infinitary logic Lω1ω. In this paper we shall show that there is an interpolation theorem in Lω1ω which can be considered as an extension of Scott's interpolation theorem in Lω1ω by using a technique developed in Motohashi [2] and [3]. We use the terminology in [1]. Therefore {Ri; i ∈ J} is the set of predicate symbols in our language. Now let us divide the set of all the free variables into mutually disjoint infinite sets {VI; I ⊆ J}. Suppose that ℱ ⊆ (J). Then a formula in Lω1ω is said to be an ℱ′-formula if it is obtained from atomic formula of the form Ri(X1, …, Xn) for some I ∈ i ∈ I and X1, …, Xn in V1,, by applying ¬ (negation), ∧ (countable conjunction), ∨ (countable disjunction), → (implication), ∀ (universal quantification), and ∃ (existential quantification). Notice that every ℱ-sentence in [1] is an ℱ′. sentence (ℱ′-closed formula) in our sense.

Then we have the following theorem which is an immediate consequence of the interpolation theorem in [2].

Theorem. Let A and ? be sentences. There is an ℱ′-sentence C such that A→C and C→B are provable iff whenever and are ℱ-isomorphic structures and satisfies A, then satisfies B.
Index sets in Ershov's hierarchy
Authors: Grassin Jacques
Published: May 2006

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).
Lω1ω is enough: a reduction theorem for some infinitary languages
Authors: Reyes Gonzalo E.
Published: May 2006

In this paper we deal with infinitary languages which allow arbitrary infinite disjunctions and conjunctions, but finite strings of quantifiers only. Furthermore, we shall assume that the primitive predicate symbols are finitary. (Cf. [K] and §2 for further information and unexplained notations.)

Our main result shows that every “reasonable” language of this type is, in a certain sense, reducible to one of the same type which allows countable disjunctions and conjunctions only. More precisely if we let θ be the first measurable cardinal and μ ≤ θ, we have the following result partially announced in [R1]:

Theorem. Every theory in a Lμω language is equivalent to some theory in a Lω1ω language in the sense that atomic formulas of one language can be mapped into formulas of the other in such a way that, for every set, these maps establish a bijective correspondence between their models having that set as a universe.

The paper is divided into three sections. In the first, we derive the main result from a theorem of Sikorski on ω-homomorphisms of μ-complete boolean algebras. In the second, we give a refined version of Sikorski's theorem from which cardinality bounds can be given for the Lω1ω theories obtained by our reduction. In the last, we use a Skolem ultrapower construction to give examples for which these bounds are actually attained. As a corollary, we obtain the converse of our main result.
Post completeness in modal logic
Authors: Segerberg Krister
Published: May 2006

Let ⊥, →, and □ be primitive, and let us have a countable supply of propositional letters. By a (modal) logic we understand a proper subset of the set of all formulas containing every tautology and being closed under modus ponens and substitution. A logic is regular if it contains every instance of □A ∧ □B ↔ □(A ∧ B) and is closed under the rule

A regular logic is normal if it contains □⊤. The smallest regular logic we denote by C (the same as Lemmon's C2), the smallest normal one by K. If L and L' are logics and L ⊆ L′, then L is a sublogic of L', and L' is an extension of L; properly so if L ≠ L'. A logic is quasi-regular (respectively, quasi-normal) if it is an extension of C (respectively, K).

A logic is Post complete if it has no proper extension. The Post number, denoted by p(L), is the number of Post complete extensions of L. Thanks to Lindenbaum, we know that

There is an obvious upper bound, too:

Furthermore,

.
A new proof of a theorem of Shelah
Authors: Rosenthal John W.
Published: May 2006

In [10, §0, E), 5)] Shelah states using the proofs of 7.9 and 6.9 in [9] it is possible to prove that if a countable first-order theory T is ℵ0-stable (totally transcendental) and not ℵ1-categorical, then it has at least ∣1 + α∣ models of power ℵα.

In this note we will give a new proof of this theorem using the work of Baldwin and Lachlan [1]. Our original proof used the generalized continuum hypothesis (GCH). We are indebted to G. E. Sacks for suggesting that the notions of ℵ0-stability and ℵ1-categoricity are absolute, and that consequently our use of GCH was eliminable [8]. Routine results from model theory may be found, e.g. in [2].

Proof (with GCH). In the proof of Theorem 3 of [1] Baldwin and Lachlin show of power ℵα such that there is a countable definable subset in . Let B0 be such a subset. Say . We will give by transfinite induction an elementary chain of models of T of power ℵα such that B[i1 … in] has power ℵβ and such that every infinite definable subset of has power ≥ℵβ. This clearly suffices.
Systems of notations and the ramified analytical hierarchy
Authors: Lukas Joan D. , Putnam Hilary
Published: May 2006

The purpose of this paper is to show that arithmetically minimal systems of notations can be constructed which provide notations for all ramified analytical ordinals (all the ordinals in the minimum β-model for analysis). This is a much larger section of the second number class than the Church-Kleene constructive ordinals (although still only an initial segment of the ordinals). Arithmetic minimality means that if H is an “H-set” associated with an ordinal α in our system and H′ is an H-set associated with the same ordinal α in an arbitrary system of notations S, then H is arithmetical in H′. Thus the arithmetical degrees associated with ordinals in our system are as low as possible.

In order to clarify the structure of degrees of unsolvability and, more generally, to gain a deeper insight into the power set of the integers, coarser but neater classifications than the structure of Turing degrees have been sought. Several hierarchies of sets of integers have been studied, each of which organizes a certain class of sets (or their degrees of unsolvability) into a well-ordering of levels with increasing complexity of nonrecursiveness appearing at each new level. The best known of these hierarchies is the Kleene hierarchy of arithmetical sets.
Analytic inductive definitions
Authors: Cenzer Douglas
Published: May 2006

An operator Γ mapping P(ω) to itself is inductive if Γ(A) ⊇ A for all A. For such an inductive operator Γ we define {Γα: α ∈ ORD} by letting Γ = ⌀, Γα + 1 = Γ(Γα) for all α, and Γβ = ⋃{Γα: α < β} for limit ordinals β. The closure ordinal ∣Γ∣ of Γ is the least ordinal α such that Γα+1 = Γα and the closure is Γ∣Γ∣.

Let be a class of operators over the natural numbers. The closure ordinal ∣∣ of is the supremum of {∣Γ∣: Γ is an inductive operator and }. The closure algebra generated by is {A ⊆ ω: A is 1-1 reducible to for some inductive operator }. The inductive algebra generated by is {Γα: Γ is an inductive operator in and α < ∣Γ∣}.

For A ∈ P(ω), is the supremum of the ordinals of well-orderings recursive in A. For , let be the supremum of . For example, it is well known that ω() = ω(∆10 = ω1, ω(Π11) = ω1 and ω(Δn1) = δn1 for n > 1 (the latter by definition).
Infinitary formulas preserved under unions of models
Authors: Nebres Bienvenido F.
Published: May 2006

So-called “preservation theorems” relate the (possible) syntactic form of the axioms of a theory to certain closure conditions on its class of models. Such results are well known for the first-order predicate calculus, Lω, ω, and there are various expositions; e.g., Keisler [14], [15]. For the language , the first results were the theorems of Lopez-Escobar on sentences preserved under homomorphic images and of Malitz on formulas preserved under substructures. More recently, Feferman added a result on formulas preserved under (or persistent for) ∈-extensions. Some of these theorems will be considered in subsequent sections. A more thorough treatment may be found in Makkai [17]. The main new preservation result obtained here characterizes the sentences preserved under ω-unions. This notion and the statement of the theorem will be explained shortly.

It is a familiar experience in mathematical research that concepts which are equivalent in a special case diverge in general. In the case at hand, one must expect to consider different possible statements for , which generalize a known result for Lω, ω. Moreover, diverse proofs may yield the same result in the special case, not all of which can be extended to the general case. Again, since the compactness theorem fails for , one cannot expect to extend the arguments from Lω, ω which use this in an essential way.
Almost strongly minimal theories. I
Authors: Baldwin John T.
Published: May 2006

In [1] the notions of strongly minimal formula and algebraic closure were applied to the study of ℵ1-categorical theories. In this paper we study a particularly simple class of ℵ1-categorical theories. We characterize this class in terms of the analysis of the Stone space of models of T given by Morley [3].

We assume familiarity with [1] and [3], but for convenience we list the principal results and definitions from those papers which are used here. Our notation is the same as in [1] with the following exceptions.

We deal with a countable first order language L. We may extend the language L in several ways. If is an L-structure, there is a natural extension of L obtained by adjoining to L a constant a for each (the universe of ). For each sentence A(a1, …, an) ∈ L(A) we say satisfies A(a1, …, an) and write if in Shoenfield's notation If is an L-structure and X is a subset of , then L(X) is the language obtained by adjoining to L a name x for each is the natural expansion of to an L(X)-structure. A structure is an inessential expansion [4, p. 141] of an L-structure if for some .
Omitting quantifier-free types in generic structures
Authors: Macintyre Angus
Published: May 2006

The central result of this paper was proved in order to settle a problem arising from B. H. Neumann's paper [10].

In [10] Neumann proved that if a finitely generated group H is recursively absolutely presentable then H is embeddable in all nontrivial algebraically-closed groups. Harry Simmons [14] clarified this by showing that a finitely generated group H is recursively absolutely presentable if and only if H can be recursively presented with solvable word-problem. Therefore, if a finitely generated group H can be recursively presented with solvable word-problem then H is embeddable in all nontrivial algebraically-closed groups.

The problem arises of characterizing those finitely generated groups which are embeddable in all nontrivial algebraically-closed groups. In this paper we prove, by a forcing argument, that if a finitely generated group H is embeddable in all non-trivial algebraically-closed groups then H can be recursively presented with solvable word-problem. Thus Neumann's result is sharp.

Our results are obtained by the method of forcing in model-theory, as developed in [1], [12]. Our method of proof has nothing to do with group-theory. We prove general results, Theorems 1 and 2 below, about constructing generic structures without certain isomorphism-types of finitely generated substructures. The formulation of these results requires the notion of Turing degree. As an application of the central result we prove Theorem 3 which gives information about the number of countable K-generic structures.

We gratefully acknowledge many helpful conversations with Harry Simmons.
Reduction of tense logic to modal logic. I
Authors: Thomason S. K.
Published: May 2006

It will be shown that propositional tense logic (with the Kripke relational semantics) may be regarded as a fragment of propositional modal logic (again with the Kripke semantics). This paper deals only with model theory. The interpretation of formal systems of tense logic as formal systems of modal logic will be discussed in [6].

The languages M and T, of modal and tense logic respectively, each have a countable infinity of propositional variables and the Boolean connectives; in addition, M has the unary operator ⋄ and T has the unary operators F and P. A structure is a pair <W, ≺<, where W is a nonempty set and ≺ is a binary relation on W. An assignment V assigns to each propositional variable p a subset V(p) of W. Then V(α)£ W is defined for all formulas α of M or T by induction:

We say that α is valid in , or , ⊨ α, if ⊩ (α) = W for every assignment V for . If Γ is a set of formulas of M [T] and α is a formula of M [T], then α is a logical consequence of Γ, or Γ ⊩ α,if α is valid in every model of Γ i.e., in every structure in which all γ ∈ Γ are valid.
A minimal degree not realizing least possible jump
Authors: Sasso Leonard P.
Published: May 2006

The least possible jump for a degree of unsolvability a is its join a ∪ 0′ with 0′. Friedberg [1] showed that each degree b ≥ 0′ is the jump of a degree a realizing least possible jump (i.e., satisfying the equation a′ = a ∪ 0′). Sacks (cf. Stillwell [8]) showed that most (in the sense of Lebesgue measure) degrees realize least possible jump. Nevertheless, degrees not realizing least possible jump are easily found (e.g., any degree b ≥ 0′) even among the degrees <0′ (cf. Shoenfield [5]) and the recursively enumerable (r.e.) degrees (cf. Sacks [3]).

A degree is called minimal if it is minimal in the natural partial ordering of degrees excluding least element 0. The existence of minimal degrees <0” was first shown by Spector [7]; Sacks [3] succeeded in replacing 0” by 0′ using a priority argument. Yates [9] asked whether all minimal degrees <0′ realize least possible jump after showing that some do by exhibiting minimal degrees below each r.e. degree. Cooper [2] subsequently showed that each degree b > 0′ is the jump of a minimal degree which, as corollary to his method of proof, realizes least possible jump. We show with the aid of a simple combinatorial device applied to a minimal degree construction in the manner of Spector [7] that not all minimal degrees realize least possible jump. We have observed in conjunction with S. B. Cooper and R. Epstein that the new combinatorial device may also be applied to minimal degree constructions in the manner of Sacks [3], Shoenfield [6] or [4] in order to construct minimal degrees <0′ not realizing least possible jump. This answers Yates' question in the negative. Yates [10], however, has been able to draw this as an immediate corollary of the weaker result by carrying out the proof in his new system of prioric games.
The consistency of a system of combinatory restricted generality
Authors: Curry Haskell B.
Published: May 2006

The system , proposed without a claim as to its consistency in [CLg, §15C], has turned out to entail a consequence which is extremely suspicious. For from the axiom ⊦LH it follows that

holds for arbitrary X; hence for X ≡ YH, where Y is a fixed-point combinator, we have

Whether or not this leads to an actual contradiction it would be interesting to know; but, no matter whether it does or not, (2) seems highly counterintuitive.

The aim of this note is to point out that a related system, here called , is demonstrably consistent and sufficient for all practical purposes served by , and at the same time to correct an error in [CLg, §15D2], which was discovered too late to be corrected on the proofs. This is formed from by dropping H from the list of θ's, and hence deleting ⊦LH and (1). The new system does not allow inferential rules to be converted into formulas with the same ease as does ; but if one is content with stating the results as rules, is adequate for all the main results deduced for in [CLg, §15C–D].
On the elementary equivalence of automorphism groups of Boolean algebras; downward Skolem Löwenheim theorems and compactness of related quantifiers
Authors: Rubin Matatyahu , Shelah Saharon
Published: May 2006

Theorem 1. (◊ℵ1,) If B is an infinite Boolean algebra (BA), then there is B1, such that ∣ Aut (B1) ≤∣B1∣ = ℵ1 and 〈B1, Aut (B1)〉 ≡ 〈B, Aut(B)〉.

Theorem 2. (◊ℵ1) There is a countably compact logic stronger than first-order logic even on finite models.

This partially answers a question of H. Friedman. These theorems appear in §§1 and 2.

Theorem 3. (a) (◊ℵ1) If B is an atomic ℵ-saturated infinite BA, Ψ Є Lω1ω and 〈B, Aut (B)〉 ⊨Ψ then there is B1, Such that ∣Aut(B1)∣ ≤ ∣B1∣ =ℵ1, and 〈B1, Aut(B1)〉⊨Ψ. In particular if B is 1-homogeneous so is B1. (b) (a) holds for B = P(ω) even if we assume only CH.
Theories with exactly three countable models and theories with algebraic prime models
Authors: Pillay Anand
Published: May 2006

We prove first that if T is a countable complete theory with n(T), the number of countable models of T, equal to three, then T is similar to the Ehrenfeucht example of such a theory. Woodrow [4] showed that if T is in the same language as the Ehrenfeucht example, T has elimination of quantifiers, and n(T) = 3 then T is very much like this example. All known examples of theories T with n(T) finite and greater than one are based on the Ehrenfeucht example. We feel that such theories are a pathological case. Our second theorem strengthens the main result of [2]. The theorem in the present paper says that if T is a countable theory which has a model in which all the elements of some infinite definable set are algebraic of uniformly bounded degree, then n(T) ≥ 4. It is known [3] that if n(T) > 1, then n(T) > 3, so our result is the first nontrivial step towards proving that n(T) ≥ ℵ0. We would also like, of course, to prove the result without the uniform bound on the finite degrees of the elements in the subset.

Theorem 2.1 is included in the author's Ph. D. thesis, as is a weaker version of Theorem 3.7. Thanks are due to Harry Simmons for his suggestions concerning the presentation of the material, and to Wilfrid Hodges for his advice while I was a Ph. D. student.
The upper semilattice of degrees ≤ 0′ is complemented
Authors: Posner David B.
Published: May 2006

Let denote the set of degrees ≤ 0′. A degree a ≤ 0′ is said to be complemented in if there exists a degree b ≤ 0′ such that b ∪ a = 0′ and b ∩ a = 0. R.W. Robinson (cf. [11]) showed that every degree a ≤ 0′ satisfying a″ = 0″ is complemented in and the author [8] showed that every degree a ≤ 0′ satisfying a′ = 0″ is complemented in . Also, in [2], R. L. Epstein showed that every r.e. degree is complemented in . In this paper we will show that in fact every degree ≤ 0′ is complemented in . We will further show that the same is true in the upper semilattice of degrees ≤ c, where c is any complete degree. This is in contrast to the situation in the upper semilattice of r.e. degrees in which, as Lachlan [6] has shown, no degree other than 0 and 0′ is complemented.
Upper bounds on locally countable admissible initial segments of a Turing degree hierarchy
Authors: Hodes Harold T.
Published: May 2006

Where AR is the set of arithmetic Turing degrees, 0(ω) is the least member of {a(2) ∣ a is an upper bound on AR}. This situation is quite different if we examine HYP, the set of hyperarithmetic degrees. We shall prove (Corollary 1) that there is an a, an upper bound on HYP, whose hyperjump is the degree of Kleene's . This paper generalizes this example, using an iteration of the jump operation into the transfinite which is based on results of Jensen and is detailed in [3] and [4]. In § 1 we review the basic definitions from [3] which are needed to state the general results.
Modal semantics without possible worlds
Authors: Kearns John T.
Published: May 2006

In this paper I will develop a semantic account for modal logic by considering only the values of sentences (and formulas). This account makes no use of possible worlds. To develop such an account, we must recognize four values. These are obtained by subdividing (plain) truth into necessary truth (T) and contingent truth (t); and by subdividing falsity into contingent falsity (f) and necessary falsity (impossibility: F). The semantic account results from reflecting on these concepts and on the meanings of the logical operators.

To begin with, we shall consider the propositional language L0. The language L0 has (1) infinitely many atomic sentences, (2) the two truth-functional connectives ∼, ∨, and the modal operator □. (Square brackets are used for punctuation.) The other logical expressions are defined as follows:

D1 [A & B] = (def)∼[∼A ∨ ∼ B],

D2 [A ⊃ B] = (def)[∼A ∨ B],

D3 ◊ A =(def)∼□∼A.

I shall use matrices to give partial characterizations of the significance of logical expressions in L0. For negation, this matrix is wholly adequate:

Upon reflection, it should be clear that this matrix is the obviously correct matrix for negation.
On generic extensions without the axiom of choice
Authors: Monro G. P.
Published: May 2006

Let ZF denote Zermelo-Fraenkel set theory (without the axiom of choice), and let M be a countable transitive model of ZF. The method of forcing extends M to another model M[G] of ZF (a “generic extension”). If the axiom of choice holds in M it also holds in M[G], that is, the axiom of choice is preserved by generic extensions. We show that this is not true for many weak forms of the axiom of choice, and we derive an application to Boolean toposes.
Countable models of nonmultidimensional ℵ0-stable theories
Authors: Bouscaren Elisabeth , Lascar Daniel
Published: May 2006

In this paper T will always be a countable ℵ0-stable theory, and in this introduction a model of T will mean a countable model.

One of the main notions we introduce is that of almost homogeneous model: we say that a model M of T is almost homogeneous if for all ā and finite sequences of elements in M, if the strong type of ā is the same as the strong type of (i.e. for all equivalence relations E, definable over the empty set and with a finite number of equivalence classes, ā and are in the same equivalence class), then there is an automorphism of M taking ā to . Although this is a weaker notion than homogeneity, these models have strong properties, and it can be seen easily that the Scott formula of any almost homogeneous model is in L1. In fact, Pillay [Pi.] has shown that almost homogeneous models are characterized by the set of types they realize.

The motivation of this research is to distinguish two classes of ℵ0-Stable theories:

(1) theories such that all models are almost homogeneous;

(2) theories with 2ℵ0 nonalmost homogeneous models.

The example of theories with Skolem functions [L. 1] (almost homogeneous is then equivalent to homogeneous) seems to indicate a link between these properties and the notion of multidimensionality, and that nonmultidimensional theories are in the first case.
Model theory of strictly upper triangular matrix rings
Authors: Wheeler William H.
Published: May 2006

Two questions on rings of strictly upper triangular matrices arising from B. Rose's work [5] are answered in this paper. An n × n matrix (αi, j) is strictly upper triangular if αi, j = 0 whenever i ≥ j. The ring of strictly upper triangular n × n matrices with entries from a field F will be denoted by Sn(F). Throughout this paper n will be an integer greater than 2. B. Rose [5] has shown that the complete theory of Sn(F) for an algebraically closed field F is ℵ1categorical. The first main result of this paper is that the rings Sn(F) and Sn(K) for fields F and K are isomorphic or elementarily equivalent if and only if F and K are isomorphic or elementarily equivalent, respectively (Corollary 1.6 and Theorem 2.2). This result shortens the proof of B. Rose's categoricity theorem [5, Theorem 7] by avoiding the co-stability considerations; furthermore, this result yields a proof of the converse of this categoricity theorem. The second main result is that the theory of rings of strictly upper triangular n × n matrices over algebraically closed fields is the model-completion of the theory of rings of strictly upper triangular n × n matrices over arbitrary fields (Theorem 2.5). This answers affirmatively the two conjectures at the end of [5].
Definability of r. e. sets in a class of recursion theoretic structures
Authors: Byerly Robert E.
Published: May 2006

It is known [4, Theorem 11-X(b)] that there is only one acceptable universal function up to recursive isomorphism. It follows from this that sets definable in terms of a universal function alone are specified uniquely up to recursive isomorphism. (An example is the set K, which consists of all n such that {n}(n) is defined, where λn, m{n}(m) is an acceptable universal function.) Many of the interesting sets constructed and studied by recursion theorists, however, have definitions which involve additional notions, such as a specific enumeration of the graph of a universal function. In particular, many of these definitions make use of the interplay between the purely number-theoretic properties of indices of partial recursive functions and their purely recursion-theoretic properties.

This paper concerns r.e. sets that can be defined using only a universal function and some purely number-theoretic concepts. In particular, we would like to know when certain recursion-theoretic properties of r.e. sets definable in this way are independent of the particular choice of universal function (equivalently, independent of the particular way in which godel numbers are identified with natural numbers).

We will first develop a suitable model-theoretic framework for discussing this question. This will enable us to classify the formulas defining r.e. sets by their logical complexity. (We use the number of alternations of quantifiers in the prenex form of a formula as a measure of logical complexity.) We will then be able to examine the question at each level.

This work is an approach to the question of when the recursion-theoretic properties of an r.e. set are independent of the particular parameters used in its construction. As such, it does not apply directly to the construction techniques most commonly used at this time for defining particular r.e. sets, e.g., the priority method. A more direct attack on this question for these techniques is represented by such works as [3] and [5]. However, the present work should be of independent interest to the logician interested in recursion theory.
Notions of weak genericity
Authors: Kurtz Stuart A.
Published: May 2006

This paper deals with forcing in arithmetic (as first introduced by Feferman [2]) and its connections with recursive function theory. We define for each n ≥ 1 the class of weakly n-generic sets. We prove that these classes merge with the classes of n-generic sets to form the hierarchy suggested by the terminology. Our notation is the same as that of Jockusch [5].
On the strength of the Sikorski extension theorem for Boolean algebras
Authors: Bell J.L.
Published: May 2006

The Sikorski Extension Theorem [6] states that, for any Boolean algebra A and any complete Boolean algebra B, any homomorphism of a subalgebra of A into B can be extended to the whole of A. That is,

Inj: Any complete Boolean algebra is injective (in the category of Boolean algebras).

The proof of Inj uses the axiom of choice (AC); thus the implication AC → Inj can be proved in Zermelo-Fraenkel set theory (ZF). On the other hand, the Boolean prime ideal theorem

BPI: Every Boolean algebra contains a prime ideal (or, equivalently, an ultrafilter)

may be equivalently stated as:

The two element Boolean algebra 2 is injective,

and so the implication Inj → BPI can be proved in ZF.

In [3], Luxemburg surmises that this last implication cannot be reversed in ZF. It is the main purpose of this paper to show that this surmise is correct. We shall do this by showing that Inj implies that BPI holds in every Boolean extension of the universe of sets, and then invoking a recent result of Monro [5] to the effect that BPI does not yield this conclusion.
Global inductive definability
Authors: Barwise Jon , Moschovakis Yiannis N.
Published: May 2006

We show that several theorems on ordinal bounds in different parts of logic are simple consequences of a basic result in the theory of global inductive definitions.
A characterization of 2-square Ultrafilters
Authors: Rosen Ned I.
Published: May 2006

The class of 2-square ultrafilters on ω equals the union, for n ≥ 1, of the classes of strictly n Ramsey ultrafilters on ω.
Probabilities over rich languages, testing and randomness
Authors: Gaifman Haim , Snir Marc
Published: May 2006

The basic concept underlying probability theory and statistics is a function assigning numerical values (probabilities) to events. An “event” in this context is any conceivable state of affairs including the so-called “empty event”—an a priori impossible state. Informally, events are described in everyday language (e.g. “by playing this strategy I shall win $1000 before going broke”). But in the current mathematical framework (first proposed by Kolmogoroff [Ko 1]) they are identified with subsets of some all-inclusive set Q. The family of all events constitutes a field, or σ-field, and the logical connectives ‘and’, ‘or’ and ‘not’ are translated into the set-theoretical operations of intersection, union and complementation. The points of Q can be regarded as possible worlds and an event as the set of all worlds in which it takes place. The concept of a field of sets is wide enough to accommodate all cases and to allow for a general abstract foundation of the theory. On the other hand it does not reflect distinctions that arise out of the linguistic structure which goes into the description of our events. Since events are always described in some language they can be indentified with the sentences that describe them and the probability function can be regarded as an assignment of values to sentences. The extensive accumulated knowledge concerning formal languages makes such a project feasible. The study of probability functions defined over the sentences of a rich enough formal language yields interesting insights in more than one direction.

Our present approach is not an alternative to the accepted Kolmogoroff axiomatics. In fact, given some formal language L, we can consider a rich enough set, say Q, of models for L (called also in this work “worlds”) and we can associate with every sentence the set of all worlds in Q in which the sentence is true. Thus our probabilities can be considered also as measures over some field of sets. But the introduction of the language adds mathematical structure and makes for distinctions expressing basic intuitions that cannot be otherwise expressed. As an example we mention here the concept of a random sequence or, more generally, a random world, or a world which is typical to a certain probability distribution.
On a condition for Cohen extensions which preserve precipitous ideals
Authors: Kakuda Yuzuru
Published: May 2006

T. Jech and K. Prikry introduced the concept of precipitous ideals as a counterpart of measurable cardinals for small cardinals (Jech and Prikry [1]). To get a precipitous ideal on ℵ1( W. Mitchell used the Cohen extension by the standard Levy collapse that makes κ = ℵ1, where κ is a measurable cardinal in the ground model (Jech, Magidor, Mitchell and Prikry [2]). His proof essentially used the fact that , where is the notion of forcing of Levy collapse and j is the elementary embedding obtained by a normal ultrafilter on κ.

On the other hand, we know that has the κ-chain condition. In this paper, we show that the κ-chain condition for notions of forcing plays an essential role for preserving normal precipitous ideals. Namely,

Theorem 1. Let κ be a regular uncountable cardinal and I a normal ideal on κ. Let be a notion of forcing with the κ-chain condition. Then, I is precipitous iff ⊩“the ideal on κ generated by I is precipitous”.

As an application of Theorem 1, we have the following theorem.

Theorem 2. Let κ be a regular uncountable cardinal, and Γ be a κ-saturated normal ideal on κ. Then, {a < κ; the ideal of thin sets on a is precipitous} has either Γ-measure one or Γ-measure zero, and the ideal of thin sets on κ is precipitous iff {α< κ; the ideal of thin sets on α is precipitous) has Γ-measure one.
Some model theory of modules. II. on stability and categoricity of flat modules
Authors: Rothmaler Philipp
Published: May 2006

This is the second part of a study on model theory of modules begun in [RO]. Throughout, I refer to that paper as “Part I”. I observed there a coincidence between some algebraic and logical points of view in the theory of modules, which led to a convenient representation of p.p. definable sets in flat modules (§1); it becomes especially nice in the case of regular rings (cf. Remark 7 in Part I). Using this in the present paper I obtain a simplified criterion for total transcendence and superstability in the case of flat modules. This enables me to give, besides partial results for arbitrary flat modules (§2), a complete description of the stability classes for modules over regular rings (§3). Particularly, it turns out that a totally transcendental module over a regular ring can be regarded as a module over a semisimple ring (cf. Remark 10 in Part I). This is the crucial observation for the examination of categoricity here: By Morley's theorem, a countable ℵ1-categorical theory is totally transcendental. Consequently, an ℵ1-categorical module over a countable regular ring can be regarded as a module over a semisimple ring. That is why I separately treat categoricity of modules over semisimple rings (§4), even without any assumption on the power of the ring. As a consequence I obtain a complete description of ℵ1-categorical modules over countable regular rings (§5). In the investigation presented here the main tool is the technique of idempotents avoiding the commutativity assumption made in the corresponding results of Garavaglia [GA 1, pp. 86–88], who used maximal ideals for that purpose. At the end of the present paper I show how to derive these latter results in our context.

On the way I simplify the known criterion for elementary equivalence for modules over regular rings (§3), which simplifies again in case of semisimple rings (§4). Such a criterion is needed in order to construct Vaughtian pairs (in the categoricity consideration) and it turns out to be useful also for another purpose treated in the third part of this series of papers.
Canonical modal logics and ultrafilter extensions
Authors: van Benthem J. F. A. K.
Published: May 2006

In this paper thecanonicalmodal logics, a kind of complete modal logics introduced in K. Fine [4] and R. I. Goldblatt [5], will be characterized semantically using the concept of anultrafilter extension, an operation on frames inspired by the algebraic theory of modal logic. Theorem 8 of R. I. Goldblatt and S. K. Thomason [6] characterizing the modally definable Σ⊿-elementary classes of frames will follow as a corollary. A second corollary is Theorem 2 of [4] which states that any complete modal logic defining a Σ⊿-elementary class of frames is canonical.

The main tool in obtaining these results is the duality between modal algebras and general frames developed in R. I. Goldblatt [5]. The relevant notions and results from this theory will be stated in §2. The concept of a canonical modal logic is introduced and motivated in §3, which also contains the above-mentioned theorems. In §4, a kind of appendix to the preceding discussion, preservation of first-order sentences under ultrafilter extensions (and some other relevant operations on frames) is discussed.

The modal language to be considered here has an infinite supply of proposition letters (p, q, r, …), a propositional constant ⊥ (the so-calledfalsum, standing for a fixed contradiction), the usual Boolean operators ¬ (not), ∨ (or), ∨ (and), → (if … then …), and ↔ (if and only if)—with ¬ and ∨ regarded as primitives—and the two unary modal operators ◇ (possibly) and □ (necessarily)— ◇ being regarded as primitive. Modal formulas will be denoted by lower case Greek letters, sets of formulas by Greek capitals.
On uniqueness of prime models
Authors: Shelah Saharon
Published: May 2006

We prove there are theories (stable or countable) for which over every A there is a prime model but it is not necessarily unique. We also give a simplified proof of the uniqueness theorem for countable stable theories.
Théories instables
Authors: Poizat Bruno
Published: May 2006

L'absence ou la présence de la propriété d'indépendance, introduite par Shelah, est sans aucun doute une mesure significative de la complexité, du point de vue de la théorie des modèles, d'une théorie instable. Il importe donc de distinguer les théories qui ont cette propriété de celles qui ne l'ont pas; le critère de Keisler [1] et de Shelah [5], qui consiste à compter le nombre de types qu'on peut obtenir sur un ensemble de paramètres de cardinal λ, n'emporte la décision que si l'on nie assez brutalement l'hypothèse du continu généralisée. Je propose ici de compter, étant donnée une partie X, de cardinal λ, d'un espace de types Si(M), quel peut être le cardinal de l'adhérence de X; ce point de vue équivaut au précédent si la théorie T est stable (voir la remarque après le Théorème 7); et si T n'a pas la propriété d'indépendance ce cardinal est au plus 2λ, tandis que si T a la propriété d'indépendance il peut atteindre 22λ (Théorème 7). Cela donne, indépendamment d'hypothèses de théorie des ensembles, une mesure quantitative de la plus grande complexité des espaces de types s'il y a propriété d'indépendance; et sous la forme du Théorème 8, cela devient un test très maniable dans les situations concrètes, car l'expérience m'a prouvé que les cohéritiers d'un type sont toujours faciles à déterminer.

Dans une première section, je considère un type complet p au dessus d'un modèle M d'une théorie complète T, et parmi les fils de p sur une extension élémentaire de M j'en distingue certains que j'appelle fils spéciaux de p: cette notion est naturelle et utile pour la suite, car le critère que j'ai décrit revient à prouver l'abondance de certains fils spéciaux d'un même type; on notera au passage le Théorème 3.

Le théorème de caractérisation de la propriété d'indépendance est prouvé dans une deuxième section, grâce à un résultat de combinatoire (Théorème 6); j'y montre aussi, à titre d'illustration, qu'un ordre total n'a jamais la propriété d'indépendance.
The generalised RK-order, orthogonality and regular types for modules
Authors: Prest Mike
Published: May 2006

I characterise various model-theoretic properties of types, in complete theories of modules, in terms of the algebraic structure of pure-injective modules. More specifically, I consider the generalised RK-order, and the relation of domination between types, orthogonality of types, and regular types. It will be seen that, essentially, it is the stationary types over pure-injective models which bear the algebraic structural information.

For background in the model theory of modules, see [4], [5], [13], [17], [19], and for the model-theoretic background [10], [11], [12], [18]. More specific references will be given in the text. I summarise some principal definitions and results below. First, though, let me describe the main results.

Throughout this paper, R will be a ring with 1; the language will be that for (right R-) modules. All types will be complete types in a complete theory, T, of R-modules. The notation is reserved for an extremely saturated model of T, inside which all “small” situations may be found. Thus, sets of parameters are just subsets of , and all models will be elementary substructures of . A positive primitive, or pp, formula is one which is equivalent to a formula of the form

with the rij ∈ R.

Suppose that p and q are 1-types over a pure-injective model M.
The degree of the set of sentences of predicate provability logic that are true under every interpretation
Authors: Boolos George , McGee Vann
Published: May 2006

The formalism of P(redicate) P(rovability) L(ogic) is the result of adjoining the unary operator □ to first-order logic without identity, constants, or function symbols. The term “provability” indicates that □ is to be “read” as “it is provable in P(eano) A(rithmetic) that…” and that the formulae of predicate provability logic are to be interpreted via formulae of PA as follows.

Pr(x), alias Bew(x), is the standard provability predicate of PA. For any formula F of PA, Pr[F] is the formula of PA that expresses the PA-provability of F “of” the values of the variables free in F, i.e., it is the formula of PA with the same free variables as F that expresses the PA-provability of the result of substituting for each variable free in F the numeral for the value of that variable. For the details of the construction of Pr[F], the reader may consult [B2, p. 42]. If F is a sentence of PA, then Pr[F] = Pr(‘F’), the sentence that expresses the PA-provability of F.

Let υ1, υ2,… be an enumeration of the variables of PA. An interpretation * of a formula ϕ of PPL is a function which assigns to each predicate symbol P of ϕ a formula P* of the language of arithmetic whose free variables are the first n variables of PA, where n is the degree of P.
Alfred Tarski and undecidable theories
Authors: McNulty George F.
Published: May 2006

Alfred Tarski identified decidability within various logical formalisms as one of the principal themes for investigation in mathematical logic. This is evident already in the focus of the seminar he organized in Warsaw in 1926. Over the ensuing fifty-five years, Tarski put forth a steady stream of theorems concerning decidability, many with far-reaching consequences. Just as the work of the 1926 seminar reflected Tarski's profound early interest in decidability, so does his last work, A formalization of set theory without variables, a monograph written in collaboration with S. Givant [8−m]. An account of the Warsaw seminar can be found in Vaught [1986].

Tarski's work on decidability falls into four broad areas: elementary theories which are decidable, elementary theories which are undecidable, the undecidability of theories of various restricted kinds, and what might be called decision problems of the second degree. An account of Tarski's work with decidable elementary theories can be found in Doner and van den Dries [1987] and in Monk [1986] (for Boolean algebras). Vaught [1986] discusses Tarski's contributions to the method of quantifier elimination. Our principal concern here is Tarski's work in the remaining three areas.

We will say that a set of elementary sentences is a theory provided it is closed with respect to logical consequence and we will say that a theory is decidable or undecidable depending on whether it is a recursive or nonrecursive set. The notion of a theory may be restricted in a number of interesting ways. For example, an equational theory is just the set of all universal sentences, belonging to some elementary theory, whose quantifier-free parts are equations between terms.
The ordered field of real numbers and logics with Malitz quantifiers
Authors: Rapp Andreas
Published: May 2006

Let ℜ = (R, + R,…) be the ordered field of real numbers. It will be shown that the -theory of ℜ is decidable, where denotes the Malitz quantifier of order n in the ℵ1-interpretation.
Functors and ordinal notations. II: A functorial construction of the Bachmann hierarchy
Authors: Girard Jean-Yves , Vauzeilles Jacqueline
Published: May 2006

This paper is the sequel of “a functorial construction of the Veblen hierarchy” [GV]: it was announced in it.

We define the notion of garden (Definition I.1.6), that is a functorial version of a Bachmann collection: in a garden Jy, at each ordinal x ≤ y, of cofinality Ω, is associated an Ω-flower (Definition I.1.1); we define also the notion of a function compatible with a garden (Definition I.3.3). We construct a hierarchy of functors from Ω to Ω (for each x ≤ y and x ∈ Jy) and for each function (f ∈ I(x, y) compatible with Jy a natural transformation T(f) from to ; we show that, if the garden is Gε Ω + 1 (Definition I.2.1), then, for each ordinal x ≤ εΩ + 1, the hierarchy of functions coincides exactly with the usual hierarchy ψx constructed using the usual Bachmann collection of height εΩ + 1, and founded on composition (that is, ψx + 1 = ψx ˚ ψ1; then, (0) is the usual Howard ordinal. We show also, that for eac x ≤ y, φx is an Ω-flower, and so we can use this hierarchy of functors for ordinal notations: see Chapter II of -logic [G].

The construction made in this article corresponds, essentially, to Chapter V of -logic [G]: the exact connections between these two works will be the matter of a subsequent article.
The model theory of finitely generated finite-by-abelian groups
Authors: Oger Francis
Published: May 2006

In [O1], we gave algebraic characterizations of elementary equivalence for finitely generated finite-by-abelian groups, i.e. finitely generated FC-groups. We also provided several examples of finitely generated finite-by-abelian groups which are elementarily equivalent without being isomorphic.

In this paper, we shall use our previous results to describe precisely the models of the theories of finitely generated finite-by-abelian groups and the elementary embeddings between these models.
Finite level Borel games and a problem concerning the jump hierarchy
Authors: Hodes Harold T.
Published: May 2006

The jump hierarchy of Turing degrees assigns to each ξ < (ℵ1)L the degree 0(ξ); we presuppose familiarity with its definition and with the basic terminology of [5]. Let λ be a limit ordinal, λ < (ℵ1)L. The central result of [5] concerns the relation between 0(λ) and exact pairs on Iλ = {0(ξ) ∣ ξ < λ}. In [6] this question is raised: Where a is an upper bound on Iλ, how far apart are a and 0(λ)? It is there shown that if λ is locally countable and admissible, they may be very far apart: 0(λ) = the least member of {a(Ind(λ))∣, a is an upper bound on Iλ}; this is rather pathological, for Ind(λ) may be larger than λ. If λ is locally countable but neither admissible nor a limit of admissibles, we are essentially in the case of λ < ; by results of Sacks [12] and Enderton and Putnam [2], 0(λ) = the least member of {a(2) ∣ a is an upper bound on Iλ}. If λ is not locally countable, Ind(λ) is neither admissible nor a limit of admissibles, so we are again in a case like that of λ < . But what if λ is locally countable and nonadmissible, but is a limit of admissibles? For the rest of this paper let λ be such an ordinal. The central result of this paper answers this question for some such λ.