bluuebunny/crossref_metadata_2025_split huggingface dataset:
General models and extensionality
Authors: Andrews Peter B. 
Published: May 2006

It is well known that equality is definable in type theory. Thus, in the language of [2], the equality relation between elements of type α is definable as , i.e., xα = yα iff every set which contains xα also contains yα. However, in a nonstandard model of type theory, the sets may be so sparse that the wff above does not denote the true equality relation. We shall use this observation to construct a general model in the sense of [2] in which the Axiom of Extensionality is not valid. Thus Theorem 2 of [2] is technically incorrect. However, it is easy to remedy the situation by slightly modifying the definition of general model.Our construction will show that the Axiom Schema of Extensionality is independent even if one takes as an axiom schema.We shall assume familiarity with, and use the notation of, [2] and §§2–3 of [1].
Metamathematical problems
Authors: Robinson Abraham 
Published: May 2006

When a logician approaches the world of mathematics, he may have in mind one or more of several purposes. He may try to find in mathematics a framework for formalizing commonly accepted laws of thought or perhaps laws of thought that are not commonly accepted. He may want to assist the mathematician by providing him with firm foundations for his theories. But it may also be the case that the logician wishes to use his own characteristic tools—formalized languages, explicit relations between symbols and objects, rigidly expressed and controlled rules of deduction—in order to gain a better understanding of the various and variegated kinds of structures, methods, theories and theorems that are to be found in mathematics. We may then expect him to adopt the attitude of the physicist or psychologist who (whatever his professed philosophy) feels that he deals with phenomena of the external world, whose rules cannot be imposed by him arbitrarily. He, or those that come after him, may indeed use the understanding thus gained in order to modify these phenomena, but as a scientist he would not regard this possibility as his only justification.For many years now, I have concentrated on the third of the lines of approach sketched above, and it seemed natural that I should discuss it again on the present occasion. However, today I do not wish to emphasize past developments but, using some of them as a background, I propose to enumerate a number of open problems. These problems seemed to me of some interest not only for their own sake but also because their solution might well require weapons whose introduction would close definite gaps in our armory.
Constructible lattices of c-degrees
Authors: Farrington C.P. 
Published: May 2006

This paper is devoted to the proof of the following theorem.Theorem. Let M be a countable standard transitive model of ZF + V = L, and let ℒ Є M be a wellfounded lattice in M, with top and bottom. Let ∣ℒ∣M = λ, and suppose κ ≥ λ is a regular cardinal in M. Then there is a generic extension N of M such that(i) N and M have the same cardinals, and κN ⊂ M;(ii) the c-degrees of sets of ordinals of N form a pattern isomorphic to ℒ;(iii) if A ⊂ On and A Є N, there is B Є P(κ+)N such that L(A) = L(B).The proof proceeds by forcing with Souslin trees, and relies heavily on techniques developed by Jech. In [5] he uses these techniques to construct simple Boolean algebras in L, and in [6] he uses them to construct a model of set theory whose c-degrees have orderlype 1 + ω*.The proof also draws on ideas of Adamovicz. In [1]–[3] she obtains consistency results concerning the possible patterns of c-degrees of sets of ordinals using perfect set forcing and symmetric models. These methods have the advantage of yielding real degrees, but involve greater combinatorial complexity, in particular the use of ‘sequential representations’ of lattices.The advantage of the approach using Souslin trees is twofold: first, we can make use of ready-made combinatorial principles which hold in L, and secondly, the notion of genericity over a Souslin tree is particularly simple.
Partial degrees and the density problem
Authors: Cooper S. B. 
Published: May 2006

A notion of relative reducibility for partial functions, which coincides with Turing reducibility on the total functions, was first given by S.C. Kleene in Introduction to metamathematics [4]. Following Myhill [7], this was made more explicit in Hartley Rogers, Jr., Theory of recursive functions and effective computability [8, pp. 146, 279], where some basic properties of the partial degrees or (equivalent, but notationally more convenient) the enumeration degrees, were derived. The question of density of this proper extension of the degrees of unsolvability was left open, although Medvedev's result [6] that there are quasi-minimal partial degrees (that is, nonrecursive partial degrees with no nonrecursive total predecessors) is proved.In 1971, Sasso [9] introduced a finer notion of partial degree, which also contained the Turing degrees as a proper substructure (intuitively, Sasso's notion of reducibility between partial functions differed from Rogers' in that computations terminated when the oracle was asked for an undefined value, whereas a Rogers computation could be thought of as proceeding simultaneously along a number of different branches of a ‘consistent’ computation tree—cf. Sasso [10]). His construction of minimal ‘partial degrees’ [11], while of interest in itself, left open the analogous problem for the more standard partial degree structure.
Jumping through the transfinite: the master code hierarchy of Turing degrees
Authors: Hodes Harold T. 
Published: May 2006

AbstractWhere a is a Turing degree and ξ is an ordinal < (ℵ1)L1, the result of performing ξ jumps on a, a(ξ), is defined set-theoretically, using Jensen's fine-structure results. This operation appears to be the natural extension through (ℵ1)L1 of the ordinary jump operations. We describe this operation in more degree-theoretic terms, examine how much of it could be defined in degree-theoretic terms and compare it to the single jump operation.
On P-points over a measurable cardinal
Authors: Kanamori A. 
Published: May 2006

This paper continues the study of κ-ultrafilters over a measurable cardinal κ, following the sequence of papers Ketonen [2], Kanamori [1] and Menas [4]. Much of the concern will be with p-point κ-ultrafilters, which have become a focus of attention because they epitomize situations of further complexity beyond the better understood cases, normal and product κ-ultrafilters.For any κ-ultrafilter D, let iD: V → MD ≃ Vκ/D be the elementary embedding of the universe into the transitization of the ultrapower by D. Situations of U < RKD will be exhibited when iU(κ) < iD(κ), and when iU(κ) = iD(κ). The main result will then be that if the latter case obtains, then there is an inner model with two measurable cardinals. (As will be pointed out, this formulation is due to Kunen, and improves on an earlier version of the author.) Incidentally, a similar conclusion will also follow from the assertion that there is an ascending Rudin-Keisler chain of κ-ultrafilters of length ω + 1. The interest in these results lies in the derivability of a substantial large cardinal assertion from plausible hypotheses on κ-ultrafilters.
Son of George and V = L
Authors: Fleissner William G. 
Published: May 2006

AbstractThis paper has three parts. In this first part, we formulate and prove from V = L a new combinatorial principle, ⋄++. In the second part, we discuss the topological problem which led to the formulation of ⋄++. Finally, we use ⋄++ to construct a space solving the topological problem.
Omitting types, type spectrums, and decidability
Authors: Millar Terrence 
Published: May 2006

Notations, conventions, and definitions. {μi∣i < ω} will be an effective enumeration of all partial recursive μi{ω → 2. A type of a theory T will be a set of formulas in the language of T, in finitely many free variables, which is consistent with T. A complete type is a maximal type in some fixed number of free variables. A type is recursive if, relative to some effective enumeration of the formulas of the language, the characteristic function for the type is recursive. A set ψ of recursive types has property P if some set of indices of characteristic functions for all the types in ψ has property P. So, for example, we might say that a set of recursive types is . If is an L-structure, then the type spectrum of , denoted ‘TySp()’, is the set of complete types realized in (we will assume that an n-type has formulas with free variables among {x1, …, xn}). A type spectrum for a theory T is a type spectrum of some model of T. ‘TySp0(T)’ will denote the set of principal types of T.We will assume that the reader is familiar with Henkin constructions of models, and of passing from a maximal consistent set of sentences, with “Henkin constants”, to a model. In particular, for a theory T in L we will let {ai∣i < ω} be new distinct constant symbols, and {φi < ω} a list of all sentences in the expanded language. ‘ΔN’ will denote the elementary diagram constructed at stage N, and .
Two-dimensional partial orderings: Recursive model theory
Authors: Manaster Alfred B. , Rosenstein Joseph G. 
Published: May 2006

In this paper and the companion paper [9] we describe a number of contrasts between the theory of linear orderings and the theory of two-dimensional partial orderings.The notion of dimensionality for partial orderings was introduced by Dushnik and Miller [3], who defined a partial ordering 〈A, R〉 to be n-dimensional if there are n linear orderings of A, 〈A, L1〉, 〈A, L2〉 …, 〈A, Ln〉 such that R = L1 ∩ L2 ∩ … ∩ Ln. Thus, for example, if Q is the linear ordering of the rationals, then the (rational) plane Q × Q with the product ordering (〈x1, y1〉 ≤Q×Q 〈x2, y2, if and only if x1 ≤ x2 and y1 ≤ y2) is 2-dimensional, since ≤Q×Q is the intersection of the two lexicographic orderings of Q × Q. In fact, as shown by Dushnik and Miller, a countable partial ordering is n-dimensional if and only if it can be embedded as a subordering of Qn.Two-dimensional partial orderings have attracted the attention of a number of combinatorialists in recent years. A basis result recently obtained, independently, by Kelly [7] and Trotter and Moore [10], describes explicitly a collection of finite partial orderings such that a partial ordering is a 2dpo if and only if it contains no element of as a subordering.
Recursively enumerable complexity sequences and measure independence
Authors: Bennison Victor L. 
Published: May 2006

Though researchers in the field of abstract computational complexity theory have utilized many of the tools of recursive function theory in the development of their field, the early results obtained (e.g., see [8]) seemed to be rather independent of results in recursion theory (at least to the extent that the results were not uniformly interesting to both varieties of theorists). It seems to have been generally accepted, however, that strong parallels of one form or another must exist between the two fields. Indeed, recent results of Blum and Marques [7], Morris [13], Soare [15] and Bennison [1], [3] have revealed a striking correspondence between complexity theoretic properties and recursion theoretic properties. These results are not contrived, but rather link together interesting properties which had arisen naturally and independently in their respective fields. This paper presents the results of research aimed at finding a recursion theoretic characterization for a complexity theoretic property which had arisen from the study of the speed-up phenomenon.In abstract computational complexity theory we are concerned with categorizing computable functions or sets according to their relative difficulty of computation. The phrase “difficult to compute” may take on different meanings depending on which criteria (complexity theoretic properties) we use to define what it means for a function or set to be hard to compute. In the abstract setting, however, such criteria should yield the same classes of functions or sets regardless of the underlying abstract complexity measure (in the sense of Blum [4], e.g., tape, time, etc.). In other words, such criteria should be measure-independent. In this paper we will be considering one way of defining “difficult to compute”. Namely, we shall say that a function or set is difficult to compute if it does not have a recursively enumerable complexity sequence as defined by Meyer and Fischer [12]. For a property to have a recursion theoretic characterization it must be measure-independent, for a recursion theoretic property is, by its very nature, measure-independent. It will not be immediately obvious whether or not the property of having an r.e. complexity sequence is measure-independent. We attack this question by first considering an alternative definition of an r.e. complexity sequence, one which is easily seen to be measure-independent.
Mapping a set of reals onto the reals
Authors: Miller Arnold W. 
Published: May 2006

AbstractIn this paper we show that it is consistent with ZFC that for any set of reals of cardinality the continuum, there is a continuous map from that set onto the closed unit interval. In fact, this holds in the iterated perfect set model. We also show that in this model every set of reals which is always of first category has cardinality less than or equal to ω1.
Additive structure in uncountable models for a fixed completion of P
Authors: Knight Julia F. 
Published: May 2006

In [6], Nadel showed that if is a recursively saturated model of Pr = Th(ω, +) of power at most ℵ1, then there is a model such that ≡ ∞ω and can be expanded to a recursively saturated model of P. For a fixed completion T of P, can be chosen to have a recursively saturated expansion to a model of T just in case is recursive in T-saturated. (“Recursive in T-saturation” is defined just like recursive saturation except that the sets of formulas considered are those that are recursive in T.)Nadel also showed in [6] that for a fixed completion T of P, a countable nonstandard model of Pr can be expanded to a model of T (not necessarily recursively saturated) iff satisfies a condition called “exp(T)-saturation.” This condition is stronger than recursive saturation but weaker than recursive in T-saturation. Nadel left open the problem of characterizing the models of Pr of power ℵ1 such that for some , ≣ ∞ω and can be expanded to a model of T. The present paper gives such a characterization. The condition on is that it is recursively saturated, and for each n ∈ ω, the set Tn of Πn-sentences of T is recursive in some type realized in .This result can be interpreted in various ways, just as the results from [6] were interpreted in various ways in [4]. Friedman [2] introduced the notion of a “standard system.”
Church's thesis without tears
Authors: Richman Fred 
Published: May 2006

The modern theory of computability is based on the works of Church, Markov and Turing who, starting from quite different models of computation, arrived at the same class of computable functions. The purpose of this paper is the show how the main results of the Church-Markov-Turing theory of computable functions may quickly be derived and understood without recourse to the largely irrelevant theories of recursive functions, Markov algorithms, or Turing machines. We do this by ignoring the problem of what constitutes a computable function and concentrating on the central feature of the Church-Markov-Turing theory: that the set of computable partial functions can be effectively enumerated. In this manner we are led directly to the heart of the theory of computability without having to fuss about what a computable function is.The spirit of this approach is similar to that of [RGRS]. A major difference is that we operate in the context of constructive mathematics in the sense of Bishop [BSH1], so all functions are computable by definition, and the phrase “you can find” implies “by a finite calculation.” In particular ifPis some property, then the statement “for eachmthere isnsuch thatP(m, n)” means that we can construct a (computable) functionθsuch thatP(m, θ(m))for allm. Church's thesis has a different flavor in an environment like this where the notion of a computable function is primitive.One point of such a treatment of Church's thesis is to make available to Bishopstyle constructivists the Markovian counterexamples of Russian constructivism and recursive function theory. The lack of serious candidates for computable functions other than recursive functions makes it quite implausible that a Bishopstyle constructivist could refute Church's thesis, or any consequence of Church's thesis. Hence counterexamples such as Specker's bounded increasing sequence of rational numbers that is eventually bounded away from any given real number [SPEC] may be used, as Brouwerian counterexamples are, as evidence of the unprovability of certain assertions.
Cardinal collapsing and ordinal definability
Authors: Štěpánek Petr 
Published: May 2006

We shall describe Boolean extensions of models of set theory with the axiom of choice in which cardinals are collapsed by mappings definable from parameters in the ground model. In particular, starting from the constructible universe, we get Boolean extensions in which constructible cardinals are collapsed by ordinal definable sets.Let be a transitive model of set theory with the axiom of choice. Definability of sets in the generic extensions of is closely related to the automorphisms of the corresponding Boolean algebra. In particular, if G is an -generic ultrafilter on a rigid complete Boolean algebra C, then every set in [G] is definable from parameters in . Hence if B is a complete Boolean algebra containing a set of forcing conditions to collapse some cardinals in , it suffices to construct a rigid complete Boolean algebra C, in which B is completely embedded. If G is as above, then [G] satisfies “every set is -definable” and the inner model [G ∩ B] contains the collapsing mapping determined by B. To complete the result, it is necessary to give some conditions under which every cardinal from [G ∩ B] remains a cardinal in [G].The absolutness is granted for every cardinal at least as large as the saturation of C. To keep the upper cardinals absolute, it often suffices to construct C with the same saturation as B. It was shown in [6] that this is always possible, namely, that every Boolean algebra can be completely embedded in a rigid complete Boolean algebra with the same saturation.
End extensions and numbers of countable models
Authors: Shelah Saharon 
Published: May 2006

AbstractWe prove that every model of T = Th(ω, <,…) (T countable) has an end extension; and that every countable theory with an infinite order and Skolem functions has nonisomorphic countable models; and that if every model of T has an end extension, then every ∣T∣-universal model of T has an end extension definable with parameters.
On the Gödel class with identity
Authors: Goldfarb Warren D. 
Published: May 2006

The Gödel Class is the class of prenex formulas of pure quantification theory whose prefixes have the form ∀y1∀y2∃x1 … ∃xn. The Gödel Class with Identity, or GCI, is the corresponding class of formulas of quantification theory extended by inclusion of the identity-sign “ = ”. Although the Gödel Class has long been kndwn to be solvable, the decision problem for the Gödel Class with Identity is open. In this paper we prove that there is no primitive recursive decision procedure for the GCI, or, indeed, for the subclass of the GCI containing just those formulas with prefixes ∀y1∀y2∃x.Throughout this paper we take quantification theory to include, aside from logical signs, infinitely many k-place predicate letters for each k > 0, but no function signs or constants. Moreover, by “prenex formula” we include only those without free variables. A decision procedure for a class of formulas is a recursive function that carries a formula in the class to 0 if the formula is satisfiable and to 1 if not. A class is solvable iff there exists a decision procedure for it. A class is finitely controllable iff every satisfiable formula in the class has a finite model. Since we speak only of effectively specified classes, finite controllability implies solvability (but not conversely).The GCI has a curious history. Gödel showed the Gödel Class (without identity) solvable in 1932 [4] and finitely controllable in 1933 [5].
Rabin's uniformization problem
Authors: Gurevich Yuri , Shelah Saharon 
Published: May 2006

AbstractThe set of all words in the alphabet {l, r} forms the full binary tree T. If x ∈ T then xl and xr are the left and the right successors of x respectively. We consider the monadic second-order language of the full binary tree with the two successor relations. This language allows quantification over elements of rand over arbitrary subsets of T. We prove that there is no monadic second-order formula ϕ*(X, y) such that for every nonempty subset X of T there is a unique y ∈ X that satisfies ϕ*(X, y) in T.
Une théorie de Galois imaginaire
Authors: Poizat Bruno 
Published: May 2006

La communauté mathématique doit être reconnaissante à Saharon Shelah pour une invention d'une ingénieuse simplicité, celle d'avoir associé à chaque structure M une structure Meq comprenant, outre les éléments de M, des “éléments imaginaires” qui sont virtuellement présents dans M. La finalité de cette construction est de pourvoir toute formule à paramètres dans M, et même dans Meq, d'un ensemble de définition minimum; tout cela est rappelé dans la première section du présent article.On peut a priori douter de l'utilité d'une construction si innocente, dont la propriété fondamentale est pratiquement évidente; et pourtant elle a été abondamment montrée par son auteur, à qui elle a permis, dans les théorèmes de classification des modèles, une décomposition des types en éléments simples, qu'on ne voit pas dans M.Cette construction d'un plus petit ensemble de définition pour une formule en rappelle une autre, qui est bien connue des algébristes, celle du corps de définition d'un idéal. Et comme la théorie des corps algébriquement clos de caractéristique donnée élimine les quanteurs, on a le sentiment que l'adjonction d'imaginaires aux modèles de cette théorie est inutile, en un mot qu'elle “élimine les imaginaires”; pour vérifier le bien-fondé de ce sentiment, il convient d'abord de préciser ce qu'on entend par là, ce qui est fait dans la deuxième section.
Algebraically closed commutative local rings
Authors: Podewski K.-P. , Reineke Joachim 
Published: May 2006

A commutative ring R with identity is called a local ring if R has only one maximal ideal. This is equivalent to saying that the sum of two nonunits is a non-unit. Therefore the theory of all commutative local rings is axiomatizible by a finite set of A2-sentences. A commutative local ring with identity is said to be an algebraically closed local ring if every finite system of polynomial equations and inequations in one or more variables with coefficients in R which has a solution in some commutative local extension of R already has a solution in R. Much work connected with algebraically closed structures of classes of rings has been done, for example by Cherlin [2], Macintyre [4] and Lipschitz and Saracino [3]. We want to show similar results for commutative local rings with identity. Our main results are the following:Theorem. The theory of commutative local rings with identity has no model-companion.The finitely generic and infinitely generic local rings are algebraically closed local rings.Theorem. There is an A3 sentence which holds for all finitely generic local rings whose negation holds in every infinitely generic local ring.