bluuebunny/crossref_metadata_2025 huggingface dataset:
Uncountable models and infinitary elementary extensions
Authors: Gregory John
Published: May 2006

Let A be a countable admissible set (as defined in [1], [3]). The language LA consists of all infinitary finite-quantifier formulas (identified with sets, as in [1]) that are elements of A. Notationally, LA = A ∩ Lω1ω. Then LA is a countable subset of Lω1ω, the language of all infinitary finite-quantifier formulas with all conjunctions countable. The set is the set of Lω1ω sentences defined in 2.2 below. The following theorem characterizes those A-Σ1 sets Φ of LA sentences that have uncountable models.

Main Theorem (3.1.). If Φ is an A-Σ1set of LA sentences, then the following are equivalent:

(a) Φ has an uncountable model,

(b) Φ has a model with a proper LA-elementary extension,

(c) for every , ⋀Φ → C is not valid.

This theorem was announced in [2] and is proved in §§3, 4, 5. Makkai's earlier [4, Theorem 1] implies that, if Φ determines countable structure up to Lω1ω-elementary equivalence, then (a) is equivalent to (c′) for all , ⋀Φ → C is not valid.

The requirement in 3.1 that Φ is A-Σ1 is essential when the set ω of all natural numbers is an element of A. For by the example of [2], then there is a set Φ LA sentences such that (b) holds and (a) fails; it is easier to show that, if ω ϵ A, there is a set Φ of LA sentences such that (c) holds and (b) fails.
A topological analog to the Rice-Shapiro index theorem
Authors: Hay Louise , Miller Douglas
Published: May 2006

Ever since Craig-Beth and Addison-Kleene proved their versions of the Lusin-Suslin theorem, work in model theory and recursion theory has demonstrated the value of classical descriptive set theory as a source of ideas and inspirations. During the sixties in particular, J.W. Addison refined the technique of “conjecture by analogy” and used it to generate a substantial number of results in both model theory and recursion theory (see, e.g., Addison [1], [2], [3]).

During the past 15 years, techniques and results from recursion theory and model theory have played an important role in the development of descriptive set theory. (Moschovakis's book [6] is an excellent reference, particularly for the use of recursion-theoretic tools.) The use of “conjecture by analogy” as a means of transferring ideas from model theory and recursion theory to descriptive set theory has developed more slowly. Some notable recent examples of this phenomenon are in Vaught [9], where some results in invariant descriptive set theory reflecting and extending model-theoretic results are obtained and others are left as conjectures (including a version of the well-known conjecture on the number of countable models) and in Hrbacek and Simpson [4], where a notion analogous to that of Turing reducibility is used to study Borel isomorphism types. Moschovakis [6] describes in detail an effective descriptive set theory based in large part on classical recursion theory.
Analytic sets having incomparable kleene degrees
Authors: Weitkamp Galen
Published: May 2006

One concern of descriptive set theory is the classification of definable sets of reals. Taken loosely ‘definable’ can mean anything from projective to formally describable in the language of Zermelo-Fraenkel set theory (ZF). Recursiveness, in the case of Kleene recursion, can be a particularly informative notion of definability. Sets of integers, for example, are categorized by their positions in the upper semilattice of Turing degrees, and the algorithms for computing their characteristic functions may be taken as their defining presentations. In turn it is interesting to position the common fauna of descriptive set theory in the upper semilattice of Kleene degrees. In so doing not only do we gain a perspective on the complexity of those sets common to the study of descriptive set theory but also a refinement of the theory of analytic sets of reals. The primary concern of this paper is to calculate the relative complexity of several notable coanalytic sets of reals and display (under suitable set theoretic hypothesis) several natural solutions to Post's problem for Kleene recursion.

For sets of reals A and B one says A is Kleene recursive in B (written A ≤KB) iff there is a real y so that the characteristic function XA of A is recursive (in the sense of Kleene [1959]) in y, XB and the existential integer quantifier ∃; i.e. there is an integer e so that XA(x) ≃ {e}(x, y, XB, ≃). Intuitively, membership of a real x ϵ ωω in A can be decided from an oracle for x, y and B using a computing machine with a countably infinite memory and an ability to search and manipulate that memory in finite time. A set is Kleene semirecursive in B if it is the domain of an integer valued partial function recursive in y, XB and ≃ for some real y.
A combinatorial property of the homomorphism relation between countable order types
Authors: Landraitis Charles
Published: May 2006

The relation ≪ (is a homomorphic image of) between (linear) order types has properties similar to those of the better known relation ≤ (is embeddable in). For example, the order type η of the rationals not only embeds every countable order type but also maps homomorphically onto . If is scattered, then can be embedded in (ω* + ω)α for some α < ω1. In that case, is also a homomorphic image of (ω* + ω)α [Lan 2]. If is uncountable, then for some uncountable ordinal α, α ≪, α* ≪, or η ≪. Proofs of these facts are much the same for ≤ and ≪.

The main theorem of [Lav 1] implies that the embedding relation better-quasiorders the set of countable order types. Our main theorem (§3) states the analogous result for the homomorphism relation. As a consequence, if 0, 1, … is an infinite sequence of countable order types, then there are i, j, i < j, such that i, is a homomorphic image of j. We observed in [Lan 1] that if this is true, then for each countable order type there is a sentence of Lω1ω such that if is a countable order type, then satisfies if and only if is a homomorphic image of . In fact, the motivation for the work leading to this paper came from this observation.

On the negative side, it is pointed out (§3) that our theorem cannot be extended as far as that of [Lav 1].
Index sets and degrees of unsolvability
Authors: Stob Michael
Published: May 2006

The characterization of classes of r.e. sets by their index sets has proved valuable in producing new results about the r.e. sets and degrees. The classic example is Yates' proof [5, Theorem 7] of Sacks' density theorem for r.e. degrees using his classification of {e: We ≤TD) as Σ3(D) whenever D is r.e. Theorem 1 of this paper is a refinement of this index set theorem of Yates which has already proved to have interesting consequences about the r.e. degrees. This theorem was originally announced by Kallibekov [1, Theorem 1]. Kallibekov there proposed a new and ingenious method for doing priority arguments which has also since been used by Kinber [2]. Unfortunately his proof to this particular theorem contains an error. We have a totally different proof using standard techniques which is of independent interest.

The proof to Theorem 1 is an infinite injury priority argument. In §1 therefore we give a short summary of the infinite injury priority method. We draw heavily on the exposition of Soare [4] where a complete description of the method is given along with many examples. In §2 we prove the main theorem and also give what we think are the most interesting corollaries to this theorem announced by Kallibekov. In §3 we prove a theorem about Σ3 sets of indices of r.e. sets. This theorem is a strengthening of a theorem of Kinber [2, Theorem 1] which was proved using a modification of Kallibekov's technique. As application, we use our theorem to show that an r.e. set A has supersets of every r.e. degree iff A is not simple.
Equivalence between semantics for intuitionism. I
Authors: López-Escobar E. G. K.
Published: May 2006

It is probably because intuitionism is founded on the concept of (abstract) proof that it has been possible to develop various kinds of models. The following is but a partial list: Gabbay [5], Beth [2], Kripke [8], Kleene [7], Läuchli [9], McKinsey and Tarski [10], Rasiowa and Sikorski [14], Scott [15], de Swart [16], and Veldman [17].

The original purpose for having the models appears to have been for obtaining independence or consistency results for certain formalizations of intuitionism [see Beth [2], Prawitz [13]]; of course, if the models could be also justified as being plausible interpretations of intuitionistic thinking, so much the better. In fact, having some kind of plausible interpretation makes it much easier to work with the models. Occasionally the models were used to suggest possible extensions of the formal systems; for example, the Kripke models with constant domains have motivated interest in the formal logic CD which extends the Intuitionistic Predicate Calculus (IPC) by having the axiom schema
Ordinal analysis of simple cases of bar recursion
Authors: Howard W. A.
Published: May 2006

The purpose of the following is to give an ordinal analysis of bar recursion of type 0 for the cases in which the bar recursion operator has type level 3 or 4. We show that the associated ordinals are the ε0th epsilon number and the first ε0-critical number, respectively. Also we analyze a restricted bar recursion operator of level 3 which provides the Gödel functional interpretation of an intuitionistic form of König's lemma. The ordinal in this case is ε0.

Let + BR0 be Gödel's theory of primitive recursive functional of finite type extended by functors Φ for bar recursion of type zero. To make bar recursion resemble transfinite recursion more closely, and thereby facilitate the ordinal analysis, we extend + BR0 to a system of terms . By Theorem 1.1a term of + BR0 which is computable by the rules of is already computable by the rules of + BR0, so it is sufficient to give an ordinal analysis of the terms of .

A term H of is said to be semi-closed if its free variables have level not exceeding 1. If, in addition, H has level not exceeding 2, then an ordinal measure for H is given by a length for one of its computation trees. We call this a computation size for H. Let F(X) be a term whose free variables have level not exceeding 2, and suppose the variable X of type 2 is the only free variable of level 2.
The κ-closed unbounded filter and supercpmpact cardinals
Authors: Spector Mitchell
Published: May 2006

The consistency of the Axiom of Determinateness (AD) poses a somewhat problematic question for set theorists. On the one hand, many mathematicians have studied AD, and none has yet derived a contradiction. Moreover, the consequences of AD which have been proven form an extensive and beautiful theory. (See [5] and [6], for example.) On the other hand, many extremely weird propositions follow from AD; these results indicate that AD is not an axiom which we can justify as intuitively true, a priori or by reason of its consequences, and we thus cannot add it to our set theory (as an accepted axiom, evidently true in the cumulative hierarchy of sets). Moreover, these results place doubt on the very consistency of AD. The failure of set theorists to show AD inconsistent over as short a time period as fifteen years can only be regarded as inconclusive, although encouraging, evidence.

On the contrary, there is a great deal of rather convincing evidence that the existence of various large cardinals is not only consistent but actually true in the universe of all sets. Thus it becomes of interest to see which consequences of AD can be proven consistent relative to the consistency of ZFC + the existence of some large cardinal. Earlier theorems with this motivation are those of Bull and Kleinberg [2] and Spector ([14]; see also [12], [13]).
Modest theory of short chains. II
Authors: Gurevich Yuri , Shelah Saharon
Published: May 2006

We analyse here the monadic theory of the rational order, the monadic theory of the real line with quantification over “small” subsets and models of these theories. We prove that the results are in some sense the best possible.
A generalized model companion for a theory of partially ordered fields
Authors: Stegbauer Werner
Published: May 2006

The notion of a model companion for a first-order theory T was introduced and discussed in [1] and [2] as a generalization of the concept of a model completion of a theory. Both concepts reflect, on a general model theoretic level, properties of the theory of algebraically closed fields. The literature provides many examples of first-order theories with and without model companions—see [3] for a survey of these results. In this paper, we give a further generalization of the notion of a model companion.

Roughly speaking, we allow instead of embeddings more general classes of maps (e.g. homomorphisms) and we allow any set of formulas which is preserved by these maps instead of existential formulas. This plan is worked out in detail in [5], where we discuss also several examples. One of these examples is given in this paper.

In order to clarify the model theoretic background, we now introduce the relevant concepts and theorems from [5].
Martin's axiom in the model theory of LA
Authors: Stark W. Richard
Published: May 2006

Working in ZFC + Martin's Axiom we develop a generalization of the Barwise Compactness Theorem which holds in languages of cardinality less than . Next, using this compactness theorem, an omitting types theorem for fewer than types is proved. Finally, in ZFC, we prove that this compactness result implies Martin's Axiom (the Equivalence Theorem). Our compactness theorem applies to a new class of theories—ccΣ-theories—which generalize the countable Σ-theories of Barwise's theorem. The Omitting Types Theorem and the Equivalence Theorem serve as examples illustrating the use of ccΣ-theories.

Assume = (A, ε) or = (A, ε R1,…,Rm) where is admissible. L() is the first-order language with constants for elements of A and relation symbols for relations in . LA is A ⋂ L∞ω where the L of L∞ω is any language in A. A theory T in LA is consistent if there is no derivation in A of a contradiction from T. is LA with new constants ca for each a and A. The basic terms of consist of the constants of and the terms f(ca1,…,cam) built directly from constants using functions f of . The symbol t is used for basic terms. A theory T in LA is Σ if it is defined by a formula of L(). The formula φ⌝ is a logical equivalent of ¬φ defined by: (1) φ⌝ = ¬φ if φ is atomic; (2) (¬φ)⌝ = φ (3) (⋁φ∈Φ φ)⌝ = ⋀φ∈Φ φ⌝; (4) (⋀φ∈Φ φ) ⋁φ∈Φ φ⌝; (5) (∃χφ(x))⌝ ∀χφ⌝(x); ∀χφ(x))⌝ = ∃χφ⌝(x).
Splitting theorems for speed-up related to order of enumeration
Authors: Dawes A. M.
Published: May 2006

It is known from work of P. Young that there are recursively enumerable sets which have optimal orders for enumeration, and also that there are sets which fail to have such orders in a strong sense. It is shown that both these properties are widespread in the class of recursively enumerable sets. In fact, any infinite recursively enumerable set can be split into two sets each of which has the property under consideration. A corollary to this result is that there are recursive sets with no optimal order of enumeration.
Supercompact cardinals and trees of normal ultrafilters
Authors: Barbanel Julius B.
Published: May 2006

Supercompact cardinals are usually defined in terms of the existence of certain normal ultrafilters. It is well known that there is a natural partial ordering on the collection of all normal ultrafilters associated with a super-compact cardinal, that of normal ultrafilter restriction. Using this notion, we define a tree structure T on the collection of normal ultrafilters associated with a fixed supercompact cardinal. Many results already appearing in the literature can be conveniently phrased in terms of structural properties of T (see, e.g. [4] or [6]). In this paper, we establish additional structural facts concerning T.

In §1 we standardize our notation and review some of the basic facts and methods that will be used throughout. §2 begins with a presentation of an important technique, due to Solovay, which will be an important tool for us. Also in §2, we begin a detailed study of the structure of T in terms of branching and the existence of many successors to branches at limit levels. §3 contains results proving the existence of many nodes of T which do not have successors above certain levels of T. This complements work of Magidor [6] who established the existence of many nodes which have successors at all higher levels of T.
On the number of countable homogeneous models
Authors: Lo Libo
Published: May 2006

The number of homogeneous models has been studied in [1] and other papers. But the number of countable homogeneous models of a countable theory T is not determined when dropping the GCH. Morley in [2] proves that if a countable theory T has more than ℵ1 nonisomorphic countable models, then it has such models. He conjectures that if a countable theory T has more than ℵ0 nonisomorphic countable models, then it has such models. In this paper we show that if a countable theory T has more than ℵ0 nonisomorphic countable homogeneous models, then it has such models.

We adopt the conventions in [1]–[3]. Throughout the paper T is a theory and the language of T is denoted by L which is countable.

Lemma 1. If a theory T has more than ℵ0types, then T hasnonisomorphic countable homogeneous models.

Proof. Suppose that T has more than ℵ0 types. From [2, Corollary 2.4] T has types. Let σ be a Ttype with n variables, and T′ = T ⋃ {σ(c1, …, cn)}, where c1, …, cn are new constants. T′ is consistent and has a countable model (, a1, …, an). From [3, Theorem 3.2.8] the reduced model has a countable homogeneous elementary extension . σ is realized in . This shows that every type σ is realized in at least one countable homogeneous model of T. But each countable model can realize at most ℵ0 types. Hence T has at least countable homogeneous models. On the other hand, a countable theory can have at most nonisomorphic countable models. Hence the number of nonisomorphic countable homogeneous models of T is .

In the following, we shall use the languages Lα (α = 0, 1, 2) defined in [2]. We give a brief description of them. For a countable theory T, let K be the class of all models of T. L = L0 is countable.
Games played on Boolean algebras
Authors: Foreman Matthew
Published: May 2006

In this paper we consider the special case of the Banach-Mazur game played on a topological space when the space also has an underlying Boolean Algebra structure. This case was first studied by Jech [2]. The version of the Banach-Mazur game we will play is the following game played on the Boolean algebra:

Players I and II alternate moves playing a descending sequence of elements of a Boolean algebra ℬ.

Player II wins the game iff Πi∈ωbi ≠ 0. Jech first considered these games and showed:

Theorem (Jech [2]). ℬ is (ω1, ∞)-distributive iff player I does not have a winning strategy in the game played on ℬ.

If ℬ has a dense ω-closed subset then it is easy to see that player II has a winning strategy in this game. This paper establishes a partial converse to this, namely it gives cardinality conditions on ℬ under which II having a winning strategy implies ω-closure.

In the course of proving the converse, we consider games of length > ω and generalize Jech's theorem to these games. Finally we present an example due to C. Gray that stands in counterpoint to the theorems in this paper.

In this section we give a few basis definitions and explain our notation. These definitions are all standard.
Forcing and reductibilities. II. Forcing in fragments of analysis
Authors: Odifreddi Piergiorgio
Published: May 2006

In Forcing and reducibilities, I [20] we reviewed various forcing techniques in the context of arithmetic. This second part deals with the same topics in the context of analysis. The numbering of sections is the continuation of the numbering of the first part. For the reader's convenience, we collect in an independent bibliography the papers which are referred to in this part.
Classifications of generalized index sets of open classes
Authors: Johnson Nancy
Published: May 2006

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.
Number of countable models
Authors: Pillay Anand
Published: May 2006

We prove that a countable complete theory whose prime model has an infinite definable subset, all of whose elements are named, has at least four countable models up to isomorphism. The motivation for this is the conjecture that a countable theory with a minimal model has infinitely many countable models. In this connection we first prove that a minimal prime model A has an expansion by a finite number of constants A′ such that the set of algebraic elements of A′ contains an infinite definable subset.

We note that our main conjecture strengthens the Baldwin–Lachlan theorem. We also note that due to Vaught's result that a countable theory cannot have exactly two countable models, the weakest possible nontrivial result for a non-ℵ0-categorical theory is that it has at least four countable models.

§1. Notation and preliminaries. Our notation follows Chang and Keisler [1], except that we denote models by A, B, etc. We use the same symbol to refer to the universe of a model. Models we refer to are always in a countable language. For T a countable complete theory we let n(T) be the number of countable models of T up to isomorphism. ∃n means ‘there are exactly n’.
Paires de structures stables
Authors: Poizat Bruno
Published: May 2006

Le paradigme de théorie stable est la théorie T d'un corps algébriquement clos; une autre théorie stable T′ est celle de la structure formée d'un corps algébriquement clos, avec en outre un symbole relationnel unaire interprétant un de ses sous-corps propres algébriquement clos. C'est à l'éclaircissement des rapports de T et de T′ qu'est consacré cet article.

J'y considère une théorie complète T stable, et les structures formées d'un modèle N de T, avec en outre un symbole relationnel unaire (x) interprétant une restriction élémentaire M de N; j'appelle ces structures paires de modèles de T.

Et je dis que la paire (N, M) est belle si d'une part M est ∣T∣+-saturé, et d'autre part pour tout n-uplet ā d'éléments de N, tout type, au sens de T, sur M ⋃ {α} est réalisé dans N.

Le premier résultat (Théorème 4) est que deux belles paires sont élémentairement équivalentes. Plus précisément, si (N1, M1) et (N2, M2) sont deux belles paires, et si ā est dans la première, b¯ dans la seconde, le fait que le type de ā sur M1 et celui de b¯ sur M2 soient équivalents dans l'ordre fondamental au sens de T suffit (et est bien sûr nécessaire) pour que ā at b¯ aient même type (sur ⊘) au sens de la théorie T′ des belles paires.
Universal diophantine equation
Authors: Jones James P.
Published: May 2006

In 1961 Martin Davis, Hilary Putnam and Julia Robinson [2] proved that every recursively enumerable set W is exponential diophantine, i.e. can be represented in the form

Here P is a polynomial with integer coefficients and the variables range over positive integers.

In 1970 Ju. V. Matijasevič used this result to establish the unsolvability of Hilbert's tenth problem. Matijasevič proved [11] that the exponential relation y = 2x is diophantine This together with [2] implies that every recursively enumerable set is diophantine, i.e. every r.e. set Wcan be represented in the form

From this it follows that there does not exist an algorithm to decide solvability of diophantine equations. The nonexistence of such an algorithm follows immediately from the existence of r.e. nonrecursive sets.

Now it is well known that the recursively enumerable sets W1, W2, W3, … can be enumerated in such a way that the binary relation x ∈ Wv is also recursively enumerable. Thus Matijasevič's theorem implies the existence of a diophantine equation U such that for all x and v,
Saturated models of Peano arithmetic
Authors: Pabion J. F.
Published: May 2006

We study reducts of Peano arithmetic for which conditions of saturation imply the corresponding conditions for the whole model. It is shown that very weak reducts (like pure order) have such a property for κ-saturation in every κ ≥ ω1. In contrast, other reducts do the job for ω and not for κ > ω1. This solves negatively a conjecture of Chang.
Implicational complexity in intuitionistic arithmetic
Authors: Leivant Daniel
Published: May 2006

In classical arithmetic a natural measure for the complexity of relations is provided by the number of quantifier alternations in an equivalent prenex normal form. However, the proof of the Prenex Normal Form Theorem uses the following intuitionistically invalid rules for permuting quantifiers with propositional constants.

Each one of these schemas, when added to Intuitionistic (Heyting's) Arithmetic IA, generates full Classical (Peano's) Arithmetic. Schema (3) is of little interest here, since one can obtain a formula intuitionistically equivalent to A ∨ ∀xBx, which is prenex if A and B are:

For the two conjuncts on the r.h.s. (1) may be successively applied, since y = 0 is decidable.

We shall readily verify that there is no way of similarly going around (1) or (2). This fact calls for counting implication (though not conjunction or disjunction) in measuring in IA the complexity of arithmetic relations. The natural implicational measure for our purpose is the depth of negative nestings of implication, defined as follows. I(F): = 0 if F is atomic; I(F ∧ G) = I(F ∨ G): = max[I(F), I(G)]; I(∀xF) = I(∃xF): = I(F); I(F → G):= max[I(F) + 1, I(G)].
Vaught's theorem recursively revisited
Authors: Millar Terrence
Published: May 2006

In this paper we investigate the relationship between the number of countable and decidable models of a complete theory. The number of decidable models will be determined in two ways, in §1 with respect to abstract isomorphism type, and in §2 with respect to recursive isomorphism type.

Definition 1. A complete theory is (α, β) if the number of countable models of T, up to abstract isomorphism, is β, and similarly the number of decidable models of T is α.

Definition 2. A model is ω-decidable if ∣∣= ω and for an effective listing {θn∣n < ω} of all sentences in the language of Th() augmented by new constant symbols i*, i < ω, {n ∣〈, i〉i<ω ⊨ θn} is recursive, where i interprets i* (in these terms, is decidable if is abstractly isomorphic to an ω-decidable model).

Definition 3. A complete theory is (α, β)r if it is (γ, β) for some γ and it has exactly αω-decidable models up to recursive isomorphism.

Specifically we will show in §1 that there is a (2, ω) theory, and in §2 that although there is a (2, 2ω) theory, there is no (2, β)r theory for any β, β < 2ω.
Forcing and reducibilities. III. Forcing in fragments of set theory
Authors: Odifreddi Piergiorgio
Published: May 2006

We conclude here the treatment of forcing in recursion theory begun in Part I and continued in Part II of [31]. The numbering of sections is the continuation of the numbering of the first two parts. The bibliography is independent.

In Part I our language was a first-order language: the only set we considered was the (set constant for the) generic set. In Part II a second-order language was introduced, and we had to interpret the second-order variables in some way. What we did was to consider the ramified analytic hierarchy, defined by induction as:

A0 = {X ⊆ ω: X is arithmetic},

Aα+1 = {X ⊆ ω: X is definable (in 2nd order arithmetic) over Aα},

Aλ = ⋃α<λAα (λ limit),

RA = ⋃αAα.

We then used (a relativized version of) the fact that (Kleene [27]). The definition of RA is obviously modeled on the definition of the constructible hierarchy introduced by Gödel [14]. For this we no longer work in a language for second-order arithmetic, but in a language for (first-order) set theory with membership as the only nonlogical relation:

L0 = ⊘,

Lα+1 = {X: X is (first-order) definable over Lα},

Lλ = ⋃α<λLα (λ limit),

L = ⋃αLα.
Degrees of types and independent sequences
Authors: Knight Julia F.
Published: May 2006

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.
A boundedness theorem in ID1(W)
Authors: Jäger Gerhard
Published: May 2006

In this paper we prove a boundedness theorem in the theory ID1(W). This answers a question asked by Feferman, for example in [3]. The background is the following.

Let A[X, x] be an X-positive formula arithmetic in X. The theory ID1(PA) is an extension of Peano arithmetic PA by the following axioms:

for arbitrary formulas F; PA is a constant for the least fixed point of A[X, x]. Set-theoretically, PA can be defined by recursion on the ordinals as follows:

where is the first nonrecursive ordinal.

Now let a ≺ b be the arithmetic relation which expresses that the recursive tree coded by a is a proper subtree of the tree coded by b, and define

The least fixed point of Tree[X, x] is the set PTree of all well-founded recursive trees. We write W or Wα for PTree or , respectively. Since W is complete we have for all α < . If we define for each element a ∈ W its inductive norm ∣a∣ by ∣a∣≔ min{ξ: a ∈ Wξ}, then we have = {∣a∣: a ∈ W} and the elements of W can be used as codes for the ordinals less than .

Assume that B[X, x] is an X-positive formula arithmetic in X with the only free variables X and x, and assume that QB is a relation that satisfies

If we define

then we obviously have PB = IB.
The weak □* is really weaker than the full □
Authors: Ben-David Shai , Magidor Menachem
Published: May 2006

We show that relative to the consistency of a supercompact cardinal does not imply . The model-theoretic transfer property ⟨ℵ1, ℵ0⟩ → ⟨ℵω + 1, ℵω⟩ does not imply , and it is consistent to have an ultrafilter on ℵω + 1 which is λ-indecomposible for all ω < λ < ℵω.
A guide to “Coding the universe” by Beller, Jensen, Welch
Authors: Friedman Sy D.
Published: May 2006

In the wake of Silver's breakthrough on the Singular Cardinals Problem (Silver [74]) followed one of the landmark results in set theory, Jensen's Covering Lemma (Devlin-Jensen [74]): If 0# does not exist then for every uncountable x ⊆ ORD there exists a constructible Y ⊇ X, card(Y) = card(X). Thus it is fair to say that in the absence of large cardinals, V is “close to L”.

It is natural to ask, as did Solovay, if we can fairly interpret the phrase “close to L” to mean “generic over L”. For example, if V = L[a], a ⊆ ω and if 0# does not exist then is V-generic over L for some partial ordering ∈ L? Notice that an affirmative answer implies that in the absence of 0#, no real can “code” a proper class of information.

Jensen's Coding Theorem provides a negative answer to Solovay's question, in a striking way: Any class can be “coded” by a real without introducing 0#. More precisely, if A ⊆ ORD then there is a forcing definable over 〈L[A], A〉 such that ⊩ V = L[a], a ⊆ ω, A is definable from a. Moreover if 0# ∉ L[A] then ⊩ 0# does not exist. Now as any M ⊨ ZFC can be generically extended to a model of the form L[A] (without introducing 0#) we obtain: For any 〈M, A〉 ⊨ ZFC (that is, M ⊨ ZFC and M obeys Replacement for formulas mentioning A as a predicate) there is an 〈M, A〉-definable forcing such that ⊩ V = L[a], a ⊆ ω, 〈M, A〉 is definable from a. Moreover if 0# ∉ M then ⊩ 0# does not exist.
Taking out LK parts from a proof in Peano arithmetic
Authors: Yukami Tsuyoshi
Published: May 2006

Let PA be Peano arithmetic with function symbols′, + and ·. The length of a proof P, denoted by lh(P), is the maximum length of threads of P (for the term ‘thread’, see [T, p. 14]). For a formula A and a natural number m, PA ⊢mA denotes the fact that there is a proof in PA of A whose length is less than or equal to m. PA ⊢ A denotes the fact that there is a proof in PA of A.

G. Kreisel conjectured that the following proposition holds.

“Let m be a natural number and A(a) be a formula. If for each natural number n, then PA ⊢ ∀xA(x)”.

Let PA1 be the corresponding system with + and · replaced by ternary predicates and axioms saying that these predicates represent functions. Parikh [P] proved the following proposition which is obtained from Kreisel's conjecture by replacing PA by PA1.

Proposition. Let A(a) be a formula in PA1and m be a natural number. Assume thatfor each natural number n. Then PA1 ⊢ ∀xA(x).

The reason why Parikh's method succeeds is the fact that the only function symbol ′ in PA1 is unary. So his method fails for PA.

To solve this conjecture for PA, we must make syntactical investigation into proofs in PA of formulas of the form A() with length ≤ m. Even if lengths of proofs are less than or equal to m, depths of occurrences of bound variables in induction axiom schemata or equality axiom schemata in proofs are not always bounded.
Commutative regular rings and Boolean-valued fields
Authors: Smith Kay
Published: May 2006

In this paper we present an equivalence between the category of commutative regular rings and the category of Boolean-valued fields, i.e., Boolean-valued sets for which the field axioms are true. The author used this equivalence in [12] to develop a Galois theory for commutative regular rings. Here we apply the equivalence to give an alternative construction of an algebraic closure for any commutative regular ring (the original proof is due to Carson [2]).

Boolean-valued sets were developed in 1965 by Scott and Solovay [10] to simplify independence proofs in set theory. They later were applied by Takeuti [13] to obtain results on Hilbert and Banach spaces. Ellentuck [3] and Weispfenning [14] considered Boolean-valued rings which consisted of rings and associated Boolean-valued relations. (Lemma 4.2 shows that their equality relation is the same as the one used in this paper.) To the author's knowledge, the present work is the first to employ the Boolean-valued sets of Scott and Solovay to obtain results in algebra.

The idea that commutative regular rings can be studied by examining the properties of related fields is not new. For several years algebraists and logicians have investigated commutative regular rings by representing a commutative regular ring as a subdirect product of fields or as the ring of global sections of a sheaf of fields over a Boolean space (see, for example, [9] and [8]). These representations depend, as does the work presented here, on the fact that the set of central idempotents of any ring with identity forms a Boolean algebra. The advantage of the Boolean-valued set approach is that the axioms of classical logic and set theory are true in the Boolean universe. Therefore, if the axioms for a field are true for a Boolean-valued set, then other properties of the set can be deduced immediately from field theory.
Monotone reducibility and the family of infinite sets
Authors: Cenzer Douglas
Published: May 2006

Let A and B be subsets of the space 2N of sets of natural numbers. A is said to be Wadge reducible to B if there is a continuous map Φ from 2N into 2N such that A = Φ−1 (B); A is said to be monotone reducible to B if in addition the map Φ is monotone, that is, a ⊂ b implies Φ(a) ⊂ Φ(b). The set A is said to be monotone if a ∈ A and a ⊂ b imply b ∈ A. For monotone sets, it is shown that, as for Wadge reducibility, sets low in the arithmetical hierarchy are nicely ordered. The sets are all reducible to the ( but not ) sets, which are in turn all reducible to the strictly sets, which are all in turn reducible to the strictly sets. In addition, the nontrivial sets all have the same degree for n ≤ 2. For Wadge reducibility, these results extend throughout the Borel hierarchy. In contrast, we give two natural strictly monotone sets which have different monotone degrees. We show that every monotone set is actually positive. We also consider reducibility for subsets of the space of compact subsets of 2N. This leads to the result that the finitely iterated Cantor-Bendixson derivative Dn is a Borel map of class exactly 2n, which answers a question of Kuratowski.
C.c.c. forcing without combinatorics
Authors: Mekler Alan H.
Published: May 2006

c.c.c. posets are characterised in terms of -generic conditions. This characterisation can be applied to get simple proofs of many facts about c.c.c. forcing including Con(MA + ┐CH).
A note on some intermediate propositional calculi
Authors: Boričić Branislav R.
Published: May 2006

This note is written in reply to López-Escobar's paper [L-E] where a “sequence” of intermediate propositional systems NLCn (n ≥ 1) and corresponding implicative propositional systems NLICn (n ≥ 1) is given. We will show that the “sequence” NLCn contains three different systems only. These are the classical propositional calculus NLC1, Dummett's system NLC2 and the system NLC3. Accordingly (see [C], [Hs2], [Hs3], [B 1], [B2], [Hs4], [L-E]), the problem posed in the paper [L-E] can be formulated as follows: is NLC3a conservative extension of NLIC3? Having in mind investigations of intermediate propositional calculi that give more general results of this type (see V. I. Homič [H1], [H2], C. G. McKay [Mc], T. Hosoi [Hs 1]), in this note, using a result of Homič (Theorem 2, [H1]), we will give a positive solution to this problem.

NLICnand NLCn. If X and Y are propositional logical systems, by X ⊆ Y we mean that the set of all provable formulas of X is included in that of Y. And X = Y means that X ⊆ Y and Y ⊆ X. A(P1/B1, …, Pn/Bn) is the formula (or the sequent) obtained from the formula (or the sequent) A by substituting simultaneously B1, …, Bn for the distinct propositional variables P1, …, Pn in A.

Let Cn(n ≥ 1) be the string of the following sequents:

Having in mind that the calculi of sequents can be understood as meta-calculi for the deducibility relation in the corresponding systems of natural deduction (see [P]), the systems of natural deductions NLCn and NLICn (n ≥ 1), introduced in [L-E], can be identified with the calculi of sequents obtained by adding the sequents Cn as axioms to a sequential formulation of the Heyting propositional calculus and to a system of positive implication, respectively (see [C], [Ch], [K], [P]).
Orthomodularity is not elementary
Authors: Goldblatt Robert
Published: May 2006

In this note it is shown that the property of orthomodularity of the lattice of orthoclosed subspaces of a pre-Hilbert space is not determined by any first-order properties of the relation ⊥ of orthogonality between vectors in . Implications for the study of quantum logic are discussed at the end of the paper.

The key to this result is the following:

Ifis a separable Hilbert space, andis an infinite-dimensional pre-Hilbert subspace of, then (, ⊥) and (, ⊥) are elementarily equivalent in the first-order languageL2of a single binary relation.

Choosing to be a pre-Hilbert space whose lattice of orthoclosed subspaces is not orthomodular, we obtain our desired conclusion. In this regard we may note the demonstration by Amemiya and Araki [1] that orthomodularity of the lattice of orthoclosed subspaces is necessary and sufficient for a pre-Hilbert space to be metrically complete, and hence be a Hilbert space. Metric completeness being a notoriously nonelementary property, our result is only to be expected (note also the parallel with the elementary L2-equivalence of the natural order (Q, <) of the rationals and its metric completion to the reals (R, <)).

To derive (1), something stronger is proved, viz. that (, ⊥) is an elementary substructure of (, ⊥).
Global quantification in Zermelo-Fraenkel set theory
Authors: Mayberry John
Published: May 2006

My aim here is to investigate the role of global quantifiers—quantifiers ranging over the entire universe of sets—in the formalization of Zermelo-Fraenkel set theory. The use of such quantifiers in the formulas substituted into axiom schemata introduces, at least prima facie, a strong element of impredicativity into the thapry. The axiom schema of replacement provides an example of this. For each instance of that schema enlarges the very domain over which its own global quantifiers vary. The fundamental question at issue is this: How does the employment of these global quantifiers, and the choice of logical principles governing their use, affect the strengths of the axiom schemata in which they occur?

I shall attack this question by comparing three quite different formalizations of the intuitive principles which constitute the Zermelo-Fraenkel system. The first of these, local Zermelo-Fraenkel set theory (LZF), is formalized without using global quantifiers. The second, global Zermelo-Fraenkel set theory (GZF), is the extension of the local theory obtained by introducing global quantifiers subject to intuitionistic logical laws, and taking the axiom schema of strong collection (Schema XII, §2) as an additional assumption of the theory. The third system is the conventional formalization of Zermelo-Fraenkel as a classical, first order theory. The local theory, LZF, is already very strong, indeed strong enough to formalize any naturally occurring mathematical argument. I have argued (in [3]) that it is the natural formalization of naive set theory. My intention, therefore, is to use it as a standard against which to measure the strength of each of the other two systems.
On the ultrafilters and ultrapowers of strong partition cardinals
Authors: Henle J.M. , Kleinberg E.M. , Watro R.J.
Published: May 2006

A strong partition cardinal is an uncountable well-ordered cardinal κ such that every partition of [κ]κ (the size κ subsets of κ) into less than κ many pieces has a homogeneous set of size κ. The existence of such cardinals is inconsistent with the axiom of choice, and our work concerning them is carried out in ZF set theory with just dependent choice (DC). The consistency of strong partition cardinals with this weaker theory remains an open question. The axiom of determinacy (AD) implies that a large number of cardinals including ℵ1 have the strong partition property. The hypothesis that AD holds in the inner model of constructible sets built over the real numbers as urelements has important consequences for descriptive set theory, and results concerning strong partition cardinals are often applied in this context. Kechris [4] and Kechris et al. [5] contain further information concerning the relationship between AD and strong partition cardinals.

We assume familiarity with the basic results on strong partition cardinals as developed in Kleinberg [6], [7], [8] and Henle [2]. Recall that a strong partition cardinal κ is measurable; in fact every stationary subset of κ is measure one under some normal measure on κ. If μ is a countably additive ultrafilter extending the closed unbounded filter on κ, then the length of the ultrapower [κ]κ under the less than almost everywhere μ ordering is again a measurable cardinal. In §1 below we establish a polarized partition property on these measurable cardinals.
On Cantor-Bendixson spectra containing (1,1). II
Authors: Marcja Annalisa , Toffalori Carlo
Published: May 2006

Let T be a (countable, complete, quantifier eliminable) ω-stable theory; an analysis of T, and consequently a classification of ω-stable theories, can be done by looking at the Boolean algebras B(M) of definable subsets of its countable models M (as usual, we often confuse a definable subset of M with the class of formulas defining it). If M ⊨ T, ∣M∣ = ℵ0, then, for every LM-formula ϕ(v) and for every ordinal α, we define a relation

(CB = Cantor-Bendixson, of course) by induction on α:

CB-rank ϕ(v) ≥ 0 if ϕ(M) ≠ ∅

CB-rank ϕ(v) ≥ λ for λ a limit ordinal, if CB-rank ϕ(v) ≥ for all v < λ;

CB-rank ϕ(v)≥ α + 1 if, for all n ∈ ω,

(*) there are LM-formulas ϕ0(v), …, ϕn − 1(v) such that

It is well known that the ω-stability of T implies that, for every consistent LM-formula ϕ(v), there is exactly one ordinal α < ω1 such that CB-rank ϕ(v) ≥ α and CB-rank ϕ(v)≱α + 1. Therefore we define:

CB-rank ϕ(v) = α

CB-degree ϕ(v) = d if d is the maximal n ∈ ω satisfying (*); and

CB-type ϕ(v) = (α, d).
On Scott and Karp trees of uncountable models
Authors: Hyttinen Tapani , Väänänen Jouko
Published: May 2006

Let and be two countable relational models of the same first order language. If the models are nonisomorphic, there is a unique countable ordinal α with the property that

i.e. and are L∞ω-equivalent up to quantifier-rank α but not up to α + 1. In this paper we consider models and of cardinality ω1 and construct trees which have a similar relation to and as a above. For this purpose we introduce a new ordering T ≪ T′ of trees, which may have some independent interest of its own. It turns out that the above ordinal α has two qualities which coincide in countable models but will differ in uncountable models. Respectively, two kinds of trees emerge from α. We call them Scott trees and Karp trees, respectively. The definition and existence of these trees is based on an examination of the Ehrenfeucht game of length ω1 between and . We construct two models of power ω1 with mutually noncomparable Scott trees.