bluuebunny/crossref_metadata_2025_split huggingface dataset:
On Σ1 well-orderings of the universe
Authors: Harrington Leo , Jech Thomas 
Published: May 2006

The constructible universe L of Gödel [2] has a natural well-ordering <L given by the order of construction; a closer look reveals that this well-ordering is definable by a Σ1 formula. Cohen's method of forcing provides several examples of models of ZF + V ≠ L which have a definable well-ordering but none is definable by a relatively simple formula.Recently, Mansfield [7] has shown that if a set of reals (or hereditarily countable sets) has a Σ1, well-ordering then each of its elements is constructible. A question has thus arisen whether one can find a model of ZF + V ≠ L that has a Σ1 well-ordering of the universe. We answer this question in the affirmative.The main result of this paper isTheorem. There is a model of ZF + V ≠ L which has a Σ1 well-ordering.The model is a generic extension of L by adjoining a branch through a Suslin tree with certain properties. The branch is a nonconstructible subset of ℵ1. Note that by Mansfield's theorem, the model must not have nonconstructible subsets of ω.Our results can be generalized in several directions. We note that in particular, we can get a model with a Σ1 well-ordering that is not L[X] for any set X. As one might expect from a joint paper by a recursion theorist and a set theorist, the proof consists of a construction and a computation.
The ⊰-order on submodels
Authors: Marcus Leo 
Published: May 2006

The relation M1 ⊰ M2, where M1 and M2 are elementary submodels of a given model M, defines a partial ordering ⊰(M). A natural question is: What are the general properties of this ordering and what special properties can it have for given M? Here we give an example of a prime model M for which ⊰(M) is a dense linear order, in particular ⊰(M) is isomorphic to the natural order of (− ∞, ∞], the reals with a last element (Theorem 1). In fact, this is the only way for ⊰(M) to be a linear order when M is prime (Theorem 3).We then remark that if N is a model of an ℵ0-categorical theory then ⊰(N) cannot be a linear order, but we give an example where ⊰(N) is a dense partial order, N a model of an ℵ0-categorical theory.Independently, and about the same time, Benda [1] found nonprime models M where ⊰(M) is isomorphic to any one of a large class of orders, including (− ∞, ∞]. His methods are very similar to ours.Notation. We assume the reader is familar with Vaught [2] where he will find the definitions and standard results pertaining to prime models, homogeneous models, and ℵ0-categorical theories.
Existentially closed structures
Authors: Simmons H. 
Published: May 2006

One of the major problems of model theory is the spectrum problem, i.e. the development of structure theorems for the spectrum of models of a given theory. I hope that this paper will make a (small) contribution to the solution of this problem.Broadly speaking, in this paper we take a fixed (but arbitrary) theory T and consider a particular class ℰ of models of T. The structures in ℰ (which are known as existentially closed structures) are connected with the model complete extensions of T. These structures have already appeared several times in the literature.In §1 we survey the notation and terminology that we use, as well as the well known facts that we require. We also consider several concepts which are not new here but which may not be well known.In §2 we define, and give the basic results concerning existentially closed structures. For most theories, T, the class ℰ is not elementary and hence is not directly amenable to a model theoretic study. Because of this we consider a smaller class of structures—the uniformly existentially closed structures. These are discussed in §3.In §4 we look at model complete theories via existentially closed structures. This section is essentially a refinement of parts of [6].In §5 we look at model companions of theories via existentially closed structures.Finally, in §6 we make some remarks on the relevance of existentially closed structures to the spectrum problem.
Limitations on the Fraenkel-Mostowski method of independence proofs
Authors: Howard Paul E. 
Published: May 2006

AbstractThe Fraenkel-Mostowski method has been widely used to prove independence results among weak versions of the axiom of choice. In this paper it is shown that certain statements cannot be proved by this method. More specifically it is shown that in all Fraenkel-Mostowski models the following hold:1. The axiom of choice for sets of finite sets implies the axiom of choice for sets of well-orderable sets.2. The Boolean prime ideal theorem implies a weakened form of Sikorski's theorem.
The word problem for division rings
Authors: Macintyre Angus 
Published: May 2006

In this paper we prove that the word problem for division rings is recursively unsolvable. Our proof relies on the corresponding result for groups [7], [28], and makes essential use of P. M. Cohn's recent work [11], [13], [15], [16] on division rings.The word problem for groups is usually formulated in terms of group presentations or finitely presented groups, as in [7], [24], [28], [30]. An equivalent formulation, in terms of the universal Horn sentences of group theory, is mentioned in [32]. This formulation makes sense for arbitrary first-order theories, and it is with respect to this formulation that we show that the word problem for division rings has degree 0′.
Iterated reflection principles and the ω-rule
Authors: Schmerl Ulf R. 
Published: May 2006

The ω-rule,with the meaning “if the formula A(n) is provable for all n, then the formula ∀xA(x) is provable”, has a certain formal similarity with a uniform reflection principle saying “if A(n) is provable for all n, then ∀xA(x) is true”. There are indeed some hints in the literature that uniform reflection has sometimes been understood as a “formalized ω-rule” (cf. for example S. Feferman [1], G. Kreisel [3], G. H. Müller [7]). This similarity has even another aspect: replacing the induction rule or scheme in Peano arithmetic PA by the ω-rule leads to a complete and sound system PA∞, where each true arithmetical statement is provable. In [2] Feferman showed that an equivalent system can be obtained by erecting on PA a transfinite progression of formal systems PAα based on iterations of the uniform reflection principle according to the following scheme:Then T = (∪dЄ, PAd, being Kleene's system of ordinal notations, is equivalent to PA∞. Of course, T cannot be an axiomatizable theory.
On computational complexity in weakly admissible structures
Authors: Stoltenberg-Hansen Viggo 
Published: May 2006

The theory of abstract computational complexity in ordinary recursion theory (ORT) was initiated by Rabin [7] and Blum [1]. Jacobs [5] generalized the notions to recursion theory on an admissible ordinal α(α-recursion theory) and proved in this setting certain main theorems such as Blum's Theorem and the Compression Theorem.In ORT the notions of “finite” and “bounded” coincide. Thus when lifting a theorem from ORT to α-recursion theory, “finite” may be translated to either “bounded below α” or to the stronger and more natural “α-finite”. Jacobs conjectured that “bounded below α” was the best possible in the theorems mentioned above. In this paper we shall prove that the stronger version of these theorems are, in fact, true. Furthermore our constructions are uniform for all admissible α.Rather than restricting ourselves to α-recursion theory we shall consider transitive rudimentarily closed structures M = 〈M, ∈, R〉 which admit what we call an acceptable prewellordering. The special case M = 〈Lα, ∈〉 and M = 〈Sβ, ∈〉 where α is admissible and β a limit ordinal constitute, respectively, α-recursion theory and β-recursion theory (see Friedman [4]).
Changing cofinalities and infinite exponents
Authors: Apter Arthur W. 
Published: May 2006

Ever since Cohen invented forcing in 1963, people have studied the properties that cardinals can have in generic extensions of the ground model. A very early result of Lévy shows that if κ is a regular cardinal and λ > κ is strongly inaccessible, then there is a notion of forcing which collapses every cardinal strictly between κ and λ yet preserves every other cardinal. This, of course, answers one question of the genre “What properties can a cardinal have in a generic extension?”Another question of the same genre that can be asked is the following: Is it possible to have a generic extension of the ground model in which all cardinals are preserved and yet the cofinalities of some cardinals are different? This question was first answered in the affirmative by Prikry, who proved the following theorem.Theorem 1.1 (Prikry [5]). Assume that V ⊨ “ZFC + κ is measurable”. Then there is a notion of forcing, P, such that for G V-generic over P:(1) V and V[G] have the same cardinals.(2) V and V[G] have the same bounded subsets of κ.(3) V[G], i.e, V[G] ⊨ “κ is Rowbottom”.(4) V[G] ⊨ “cof(κ) = ω”.Prikry's result naturally raises the following question: Is it possible to get a generic extension in which cardinals are preserved and yet the cofinalities of certain cardinals are different from the ground model's but are uncountable? This question was first answered in the affirmative by Magidor, who proved the following theorem.
Maximality in effective topology
Authors: Kalantari Iraj , Leggett Anne 
Published: May 2006

In this paper we continue the study of the structure of the lattice of recursively enumerable (r.e.) open subsets of a topological space. Work in this approach to effective topology began in Kalantari and Retzlaff [5] and continued in Kalantari [2], Kalantari and Leggett [3] and Kalantari and Remmel [4]. Studies in effectiveness of results in structures other than integers began with the work of Specker [17] and Lacombe [8] on effective analysis.The renewed activity in the study of the effective content of mathematical structures owes much to Nerode's program and Metakides' and Nerode's [11], [12] work on vector spaces and fields. These studies have been extended by Kalantari, Remmel, Retzlaff, Shore and Smith. Similar studies on the effective content of other mathematical structures have been conducted. These include work on topological vector spaces, boolean algebras, linear orderings etc.Kalantari and Retzlaff [5] began a study of effective topological spaces by considering a topological space with a countable basis ⊿ for the topology. The space X is to be fully effective; that is, the basis elements are coded into ω and the operations of intersection of basis elements and the relation of inclusion among them are both computable. An r.e. open subset of X is then represented as the union of basic open sets whose codes lie in an r.e. subset of ω.
Decomposition of totally transcendental modules
Authors: Garavaglia Steven 
Published: May 2006

The main theorem of this paper states that if R is a ring and is a totally transcendental R-module, then has a unique decomposition as a direct sum of indecomposable R-modules. Natural examples of totally transcendental modules are injective modules over noetherian rings, artinian modules over commutative rings, projective modules over left-perfect, right-coherent rings, and arbitrary modules over Σ – α-gens rings. Therefore, our decomposition theorem yields as special cases the purely algebraic unique decomposition theorems for these four classes of modules due to Matlis; Warfield; Mueller, Eklof, and Sabbagh; and Shelah and Fisher. These results and a number of other corollaries about totally transcendental modules are covered in §1. In §2, I show how the results of § 1 can be used to give an improvement of Baur's classification of ω-categorical modules over countable rings. In §3, the decomposition theorem is used to study modules with quantifier elimination over noetherian rings.The goals of this section are to prove the decomposition theorem and to derive some of its immediate corollaries. I will begin with some notational conventions. R will denote a ring with an identity element. LR is the language of left R-modules described in [4, p. 251] and TR is the theory of left R-modules. “R-module” will mean “unital left R-module”. A formula will mean an LR-formula.
Ultrafilters on spaces of partitions
Authors: Henle James M. , Zwicker William S. 
Published: May 2006

Qκλ. Pκλ the space of all < κ-sized subsets of λ, has provided numerous opportunities for the gainful employment of set theorists in recent years, thanks to its combinatorial richness and to its relationships with various large cardinals. In the spirit of Pκλ we offer the following definition:For κ ≤ λ both cardinals, Qκλ is the set of all partitions of λ into < κ-many pieces (an element of q ∈ Qκλ is called a piece of q). EquivalentlyAn element of Pκλ may be viewed as an injection from a < κ-sized set into λ, with some information thrown away. An element of Qκλ is a surjection from λ onto a < κ-sized set, with analogous loss of information.For p, q ∈ Qκλ, we say p ≤ q iff q is a refinement of p (every piece of q is contained in a piece of p).
Decidability and ℵ0-categoricity of theories of partially ordered sets
Authors: Schmerl James H. 
Published: May 2006

AbstractThis paper is primarily concerned with ℵ0-categoricity of theories of partially ordered sets. It contains some general conjectures, a collection of known results and some new theorems on ℵ0-categoricity. Among the latter are the following.Corollary 3.3. For every countable ℵ0-categoricalthere is a linear order of A such that (, <) is ℵ0-categorical.Corollary 6.7. Every ℵ0-categorical theory of a partially ordered set of finite width has a decidable theory.Theorem 7.7. Every ℵ0-categorical theory of reticles has a decidable theory.There is a section dealing just with decidability of partially ordered sets, the main result of this section beingTheorem 8.2. If (P, <) is a finite partially ordered set and KP is the class of partially ordered sets which do not embed (P, <), then Th(KP) is decidable iff KP contains only reticles.
A selection theorem
Authors: Kirousis Lefteris Miltiades 
Published: May 2006

In [1978] Harrington and MacQueen proved that if B is an (A, E)-semirecursive subset of A, such that the functions in BA can be coded as elements of A in an (A, E)-recursive way, then ENV(A, E) is closed under the existential quantifier ∃T ∈ B.Later Moschovakis showed that if ENV(Vκ, ∈, E) is closed under the quantifier ∃t ∈ λ, where λ is the p-cofinality of κ, thenthe p-cofinality of κ is the least ordinal λ for which there exists a (κ, <, E)-recursive partial function ƒ into κ, such that ƒ∣λ is total from λ onto an unbounded subset of κ.In this paper we prove that for any infinite ordinal κ if p-card(κ) = κ, then ENV(κ, <, E) is closed under ∃t ∈ μ, for μ < p-cf(κ); p-cf(κ) is the “boldface” analog of p-cf((κ) and p-card(κ) is defined similarly.From this follows that for any infinite ordinal κ the following two statements are equivalent.(i) ENV(κ, <, E) is closed under bounded existential quantification.(ii) ENV(κ, <, E) = ENV(κ, <, E#) or p-cf(κ) = κ.We also show that we cannot omit any of the hypotheses in the above theorem.We follow mainly the notation of Kechris and Moschovakis [1977].
A second paper “On the interpolation theorem for the logic of constant domains”
Authors: López-Escobar E.G.K. 
Published: May 2006

It was brought to our attention by M. Fitting that Beth's semantic tableau system using the intuitionistic propositional rules and the classical quantifier rules produces a correct but incomplete axiomatization of the logic CD of constant domains. The formulawhere T is a truth constant, being an instance of a formula which is valid in all Kripke models with constant domains but which is not provable without cut.From the Fitting formula one can immediately obtain that the sequentalthough provable in the system GD outlined in [3], does not have a cut-free proof (in the system GD).If the only problem with GD were the sequent S0, then we could extend GD to the system GD+ by adding the following (correct) rule:Since the new rule still satisfies the subformula property a cut elimination theorem for GD+ would be a step in the right direction for a syntactical proof for the interpolation theorem for the logic of constant domains (cf. Gabbay [2]; see also §4). Unfortunately, one can show that the sequentwhere P is a propositional parameter (or formula without x free) has a derivation in GD+, but does not have a cut-free derivation (in GD+). Of course, we could extend GD+ to GD++ by adding the following correct (and with the subformula property) rule:But then we can find a sequent S2 which, although provable with cut in GD++, does not have a cut-free derivation in GD++.
Sets constructed from sequences of measures: Revisited
Authors: Mitchell William J. 
Published: May 2006

Let U and U′ be measures on a cardinal κ: that is, normal κ-complete ultrafilters on κ. The partial ordering ⊲ was defined in [M74]: we say U ⊲ U′ if U ∈ Vκ/U′. A model L(ℱ) was constructed in which this ordering was a well ordering, and it was shown that under proper assumptions the length of this well ordering could be any ordinal up to κ++L(ℱ). In this paper we will revisit this material and show that the coherence required in the construction of ℱ can be greatly weakened. This change simplifies some proofs, weakens the assumption needed for the results stated above (Theorem 1, below), and proves one new result (Theorem 5, below) which is suggestive although its significance is not clear.We have tried to make this paper self-contained and to that end have repeated some material from [M74]. We begin with some definitions before stating Theorem 1.The ordering ⊲ is well founded. This may be seen by assuming that it is not and letting κ be least such that ⊲ is not well founded on measures on κ. If U is a measure on κ with an infinite descending chain below it, then the measures on κ in VκU are still not well founded by ⊲, contradicting the fact that iU(κ) is the least cardinal in Vκ/U such that ⊲ is not well founded. Since ⊲ is well founded, we can define O(U) to be the rank of U in the partial ordering ⊲ of measures on κ, and O(κ) to be the rank of this partial ordering.
Examples in the theory of existential completeness
Authors: Hirschfeld Joram 
Published: May 2006

Since A. Robinson introduced the classes of existentially complete and generic models, conditions which were interesting for elementary classes were considered for these classes. In [6] H. Simmons showed that with the natural definitions there are prime and saturated existentially complete models and these are very similar to their elementary counterparts which were introduced by Vaught [2, 2.3]. As Example 6 will show, there is a limit to the similarity—there are theories which have exactly two existentially complete models.In [6] H. Simmons considers the following list of properties, shows that each property implies the next one and asks whether any of them implies the previous one:1.1. T is ℵ0-categorical.1.2. T has an ℵ0-categorical model companion.1.3. ∣E∣ = 1.1.4. ∣E∣ < .1.5. T has a countable ∃-saturated model.1.6. T has a ∃-prime model.1.7. Each universal formula is implied by a ∃-atomic existential formula.[The reader is referred to [1], [3], [4] and [6] for the definitions and background.We only mention that T is always a countable theory. All the models under discussion are countable. Thus E is the class of countable existentially complete models and F and G, respectively, are the classes of countable finite and infinite generic models. For every class C,∣C∣ is the number of (countable) models in C.]
On the compactness of ℵ1 and ℵ2
Authors: di Prisco C. A. , Henle J. 
Published: May 2006

In recent years, the Axiom of Determinateness (AD) has yielded numerous results concerning the size and properties of the first ω-many uncountable cardinals. Briefly, these results began with Solovay's discovery that ℵ1 and ℵ2 are measurable [8], [3], continued with theorems of Solovay, Martin, and Kunen concerning infinite-exponent partition relations [6], [3], Martin's proof that ℵn has confinality ℵ2 for 1 < n < ω, and very recently, Kleinberg's proof that the ℵn are Jonsson cardinals [4].This paper was inspired by a very recent result of Martin from AD that ℵ1 is ℵ2-super compact. It was known for some time that AD implies ℵ1 is α-strongly compact for all ℵ < θ (where θ is the least cardinal onto which 2ω cannot be mapped, quite a large cardinal under AD), and that ADR implies that ℵ1, is α-super compact for all α < θ. A key open question had been whether or not ℵ1 is super compact under AD alone.This paper comments on the method of Martin in several different ways. In §2, we will prove that ℵ1 is ℵ2-super compact, and then generalize the method to show that ℵ2 is ℵ3-strongly compact. In addition, we will demonstrate a limitation in the method by showing that the possible measures obtained on are not normal, and that the method cannot be extended to show that ℵ2 is ℵ4-strongly compact.
The stability function of a theory
Authors: Keisler H. Jerome 
Published: May 2006

AbstractLet T be a complete theory with infinite models in a countable language. The stability function gT(κ) is defined as the supremum of the number of types over models of T of power κ. It is proved that there are only six possible stability functions, namely κ, κ + 2ω, κω, ded κ, (ded κ)ω, 2κ.
The nonconstructive content of sentences of arithmetic
Authors: Goodman Nicolas D. 
Published: May 2006

This note is concerned with the old topic, initiated by Kleene, of the connections between recursive function theory and provability in intuitionistic arithmetic. More specifically, we are interested in the relationship between the hierarchy of degrees of unsolvability and the interdeducibility of cases of excluded middle. The work described below was motivated by a counterexample, to be given presently, which shows that that relationship is more complicated than one might suppose.Let HA be first-order intuitionistic arithmetic. Let the symbol ⊢ mean derivability in HA. For each natural number n, let n¯ be the corresponding numeral. Let Ω be the standard model of arithmetic. Say that a sentence ϕ is true iff Ω⊨ ϕ. Now suppose ϕ(x) and Ψ(x) are formulas with only the variable x free. SupposeThen it is natural to conjecture that {n∣Ω⊨Ψ(n¯)} is recursive in {n∣Ω⊨ϕ(n¯)}.However, this conjecture is false. Consider the formula is a formalization of Kleene's T-predicate.
Some useful preservation theorems
Authors: Compton Kevin J. 
Published: May 2006

The study of preservation theorems for first order logic was the focus of much research by model theorists in the 1960's. These theorems, which came to form the foundation for classical model theory, characterize first order sentences and theories that are preserved under operations such as the taking of unions or submodels (see Chang and Keisler [5] for a discussion of preservation theorems for first order logic). In current model theoretic research, logics richer than first order logic and applications of logic to other parts of mathematics have assumed the central position. In the former area, preservation theorems are not so important; in the latter, especially in applications to algebra, many of the techniques developed for proving these theorems have been useful.In this paper I prove several preservation theorems for first order logic which I discovered while investigating the asymptotic growth of classes of finite combinatorial structures. The significance of these theorems lies in their applications to problems in finite combinatorics. Since the applications require combinatorial and analytical techniques that are not pertinent to logical questions discussed here, I shall present them in another paper [7].