bluuebunny/crossref_metadata_2025_split huggingface dataset:
Type-raising operations on cardinal and ordinal numbers in Quine's “New foundations”
Authors: Henson C. Ward 
Published: May 2006

In this paper we develop certain methods of proof in Quine's set theory NF which have no counterparts elsewhere. These ideas were first used by Specker [5] in his disproof of the Axiom of Choice in NF. They depend on the properties of two related operations, T(n) on cardinal numbers and U(α) on ordinal numbers, which are defined by the equationsfor each set x and well ordering R. (Here and below we use Rosser's notation [3].) The definitions insure that the formulas T(x) = y and U(x) = y are stratified when y is assigned a type one higher than x. The importance of T and U stems from the following facts: (i) each of T and U is a 1-1, order preserving operation from its domain onto a proper initial section of its domain; (ii) Tand U commute with most of the standard operations on cardinal and ordinal numbers.These basic facts are discussed in §1. In §2 we prove in NF that the exponential function 2n is not 1-1. Indeed, there exist cardinal numbers m and n which satisfyIn §3 we prove the following technical result, which has many important applications. Suppose f is an increasing function from an initial segment S of the set NO of ordinal numbers into NO and that f commutes with U.
Measurable cardinals and a combinatorial principle of Jensen
Authors: Devlin Keith J. 
Published: May 2006

At the end of his paper [2], Silver shows how methods developed by Jensen and Solovay in order to prove results about the constructible universe L may be adapted to prove corresponding results for the universe L[μ], where μ is a normal measure on some uncountable cardinal ρ. In this paper we pursue this in greater depth. Jensen proved, in fact, much stronger results than those considered in [2], and we shall show that all of these carry over from L to L[μ], More precisely, we show that if V = L[μ] is assumed, then for any regular uncountable cardinal κ and any uncountable λ < κ, + (κ, λ) holds, and that + (κ, κ) holds just in the case κ is not ineffable. This result was proved to hold in L by Jensen, who first formulated the principles + (κ, λ).Our proof differs in detail from Jensen's, and at one point (in choosing the set B of + ) differs fundamentally from his argument. However, the fact remains that our argument is modelled closely upon Jensen's, and it should be made clear that in many parts it is a straightforward adaption of his proof to the L[μ] situation. It is regrettable that, at the time of our writing this, Jensen's proof still only exists in the rough, handwritten form of [1]; so we shall give our argument in some detail, even those parts which are merely “translations” of Jensen's original arguments.
On splitting stationary subsets of large cardinals
Authors: Baumgartner James E. , Taylor Alan D. , Wagon Stanley 
Published: May 2006

AbstractLet κ denote a regular uncountable cardinal and NS the normal ideal of nonstationary subsets of κ. Our results concern the well-known open question whether NS fails to be κ+-saturated, i.e., are there κ+ stationary subsets of κ with pairwise intersections nonstationary? Our first observation is:Theorem. NS isκ+-saturated iff for every normal ideal J on κ there is a stationary set A ⊆ κsuch that J = NS∣A = {X ⊆ κ: X ∩ A ∈ NS}.Turning our attention to large cardinals, we extend the usual (weak) Mahlo hierarchy to define “greatly Mahlo” cardinals and obtain the following:Theorem. If κ is greatly Mahlo then NS is notκ+-saturated.Theorem. If κ is ordinal Π11-indescribable (e.g., weakly compact), ethereal (e.g., subtle), or carries aκ-saturated ideal, thenκis greatly Mahlo. Moreover, there is a stationary set of greatly Mahlo cardinals below any ordinal Π11-indescribable cardinal.These methods apply to other normal ideals as well; e.g., the subtle ideal on an ineffable cardinal κ is not κ+-saturated.
Complete theories with countably many rigid nonisomorphic models
Authors: Malitz Jerome 
Published: May 2006

Here we prove the following:Theorem. For every N ≤ ω there is a complete theory Tn having exactly n nonisomorphic rigid models and no uncountable rigid models. Moreover, each non-rigid model admits a nontrivial automorphism.The Tn are theories in the first-order predicate calculus and a rigid structure is a structure with no nontrivial endomorphisms, i.e., the only endomorphism of the structure into itself is the identity. The theorem answers a question of A. Ehrenfeucht.For the most part we use standard model theoretic notation with Th denoting the set of sentences true in and meaning . A complete set of sentences is one of the form Th for some . The universe of a structure may be denoted by ∣∣. An n-ary relation on X is a set of n tuples (x0, …, xn−1) with each xi ∈ X. All the structures encounted here will be relational. If P is an n-ary relation then P ↾ Y, the restriction of P to Y, is {(x0, …, xn−1): (x0, …, xn−1) ∈ P and x0, …, xn−1Y}.
On models of arithmetic—Answers to two problems raised by H. Gaifman
Authors: Wilkie Alex 
Published: May 2006

In a recent paper [3] H. Gaifman investigated some model theoretic consequences of Matijasevič's theorem [5], and posed some further problems which naturally arise. We provide here partial answers to two of these problems, the results having been previously announced in the postscript of [3].Firstly, it is shown in [3] that if M1 and M2 are models of the Peano axioms P and M1 ⊆ M2, then M1 is closed under the recursive functions of M2. The converse of this statement is false. Moreover, Gaifman asks: Is every initial segment of a model M of P which is closed under the recursive functions of M (or the ∑n-definable functions) also a model of P? We show that this is false and our method gives, en route, another proof of a theorem of Rabin [7] stating the P is not implied by any consistent set of ∑n sentences for any n.Secondly, we partially answer a question posed on p. 129 of [3] by proving (some-what more than) every countable nonstandard model of P has an end extension in which a diophantine equation, not solvable in the original model, has a solution. We can, in fact, take the new model to be isomorphic to the original one. This generalises (apart from the countability restriction) a theorem of Rabin [6].
Transfinite extensions of Friedberg's completeness criterion
Authors: Macintyre John M. 
Published: May 2006

In [3] Friedberg showed that every Turing degree ≥ 0′ is the jump of some degree. Using the relativized version of this theorem it can be shown by finite induction that if a ≥ 0(n)0(n) then there is a b such that b(n) = a (our notation is defined in §1). It is natural to ask whether these results can be extended into the transfinite. Is it true for example, that whenever a ≥ 0(ω) there is a b such that = b(ω)= a? In §2 we use forcing to prove this result. (The usefulness of forcing in answering questions involving the jump operation on degrees of unsolvability has been previously demonstrated in Selman [5] where, for example, forcing was used to construct degrees a and b such that a(ω) = b(ω) = a ∪ b = 0(ω).) In §3 we generalize the methods of §2 to show that if α is a recursive ordinal and a ≥ 0(α) then there is a bsuch that b(α) = a, i.e. the Friedberg result can be extended to all recursive ordinal levels.Thomason [6] used a forcing argument to show: If (the Kleene set of notations for the recursive ordinals) then there is a B such that (the set of notations for ordinals recursive in B). In §4 we show this result holds when hyperarithmetic reducibility is replaced by Turing reducibility: If then there is a B such that .
On generalized computational complexity
Authors: Jacobs Barry E. 
Published: May 2006

If one regards an ordinal number as a generalization of a counting number, then it is natural to begin thinking in terms of computations on sets of ordinal numbers. This is precisely what Takeuti [22] had in mind when he initiated the study of recursive functions on ordinals. Kreisel and Sacks [9] too developed an ordinal recursion theory, called metarecursion theory, which specialized to the initial segment of the ordinals bounded by(the first nonconstructive ordinal).The notion of admissibility was introduced by Kripke [11] and Platek [14] and served to generalize metarecursion theory. Kripke called ordinal α admissible if it satisfied certain closure properties of infinitary computations. It was shown that admissibility could be equivalently formulated in terms of the replacement schema of ZF set theory and that α =is an admissible ordinal. The study of a recursion theory on an initial segment of the ordinals bounded by some arbitrary admissible α became known as α-recursion theory.Kripke [10] employed a Gödel numbering scheme to perform an arithmetiza-tion of α -recursion theory and created an analogue to Kleene'sT-predicate (cf. [8]) of ordinary recursion theory (o.r.t.). TheT-predicate then served as the basis for showing that analogues of the major results of unrelativized o.r.t. held in α-recursion theory; namely, the α-Enumeration Theorem,T Theorem, α-Recursion Theorem, and α-Universal Function Theorem.
A hierarchy for the 1-section of any type two object
Authors: Wainer S. S. 
Published: May 2006

Shoenfield [6] constructed a hierarchy for any type two object F in which 2E is recursive by generalizing the hyperarithmetical hierarchy, using a jump operation jF defined by(A similar hierarchy was constructed independently by Hinman [3].) In order to construct a hierarchy for an arbitrary type two F we must first associate with F an operator which, on one hand will always be recursive in F, and on the other hand will generate all the functions recursive in F when iterated over a simultaneously generated set of ordinal notations OF. Clearly the use of 2E in the above definition of jF(f) can be avoided if, instead of diagonalizing F over all functions recursive in f, we only diagonalize F over, say, the functions primitive recursive in f. If furthermore we code in a function which enumerates all functions primitive recursive in f then the resulting operation will certainly generate a primitive recursively expanding hierarchy of functions recursive in F. The problem that remains is whether this hierarchy will exhaust the 1-section of F. But this reduces to an effectiyized version of the following problem: If g is recursive in some level of the hierarchy, is g primitive recursive in some higher level ? An affirmative answer is suggested by the completeness results of Feferman [2], and our main theorem below will be proved by combining his ideas with those of Shoenfield [6]. The result is a hierarchy which applies to all type two objects, and which replaces the notion of recursion in F by the simpler notion of primitive recursion in certain functions generated by F. Unfortunately, in contrast with the Shoenfield hierarchy, the hierarchy developed here cannot always be expected to have the uniqueness property (even w.r.t. ≤T), and for this reason the proof of our main theorem is rather more complicated than the corresponding proof in [6].
Projective model completeness
Authors: Sacerdote George S. 
Published: May 2006

The concept of model completeness has been very useful in model theory. In this article we obtain a new model theoretic tool by “reversing the arrows.” Specifically, model completeness deals with the relations between a model of a theory and its extensions; in this paper we shall be concerned with the relation between a model of a theory and its homomorphic pre-images.This work is based on the intuitive principle that metamathematical theorems about universal sentences of the lower predicate calculus and substructures can be translated in a truth-preserving way to theorems about positive sentences and homomorphic images. From model completeness and the completeness theorems which depend on it, this translation gives new criteria for completeness.Special thanks are due to Professor A. Robinson whose encouragement and suggestions have contributed much to these results.
Products of two-sorted structures
Authors: Olin Philip 
Published: May 2006

First order properties of direct products and direct sums (weak direct products) of relational systems have been studied extensively. For example, in Feferman and Vaught [3] an effective procedure is given for reducing such properties of the product to properties of the factors, and thus in particular elementary equivalence is preserved. We consider here two-sorted relational systems, with the direct product and sum operations keeping one of the sorts stationary. (See Feferman [4] for a similar definition of extensions.)These considerations are motivated by the example of direct products and sums of modules [8], [9]. In [9] examples are given to show that the direct product of two modules (even having only a finite number of module elements) does not preserve two-sorted (even universal) equivalence for any finite or infinitary language Lκ, λ. So we restrict attention here to direct powers and multiples (many copies of one structure). Also in [9] it is shown (for modules, but the proofs generalize immediately to two-sorted structures with a finite number of relations) that the direct multiple operation preserves first order ∀E-equivalence and the direct power operation preserves first order ∀-equivalence. We show here that these results for general two-sorted structures in a finite first order language are, in a sense, best-possible. Examples are given to show that does not imply , and that does not imply .
Applications of trees to intermediate logics
Authors: Gabbay Dov M. 
Published: May 2006

We investigate extensions of Heyting's predicate calculus (HPC). We relate geometric properties of the trees of Kripke models (see [2]) with schemas of HPC and thus obtain completeness theorems for several intermediate logics defined by schemas. Our main results are:(a) ∼(∀x ∼ ∼ϕ(x) Λ ∼∀xϕ(x)) is characterized by all Kripke models with trees T with the property that every point is below an endpoint. (From this we shall deduce Glivenko type theorems for this extension.)(b) The fragment of HPC without ∨ and ∃ is complete for all Kripke models with constant domains.We assume familiarity with Kripke [2]. Our notation is different from his since we want to stress properties of the trees. A Kripke model will be denoted by (Aα, ≤ 0), α ∈ T where (T, ≤, 0) is the tree with the least member 0 ∈ T and Aα, α ∈ T, is the model standing at the node α. The truth value at α of a formula ϕ(a1 … an) under the indicated assignment at α is denoted by [ϕ(a1 … an)]α.A Kripke model is said to be of constant domains if all the models Aα, α ∈ T, have the same domain.
On existence proofs of Hanf numbers
Authors: Friedman Harvey 
Published: May 2006

This paper refines some results of Barwise [1] as well as answering the open question posed at the end of [1] about the Hanf number of positively. We conclude by showing that the existence of a Hanf bound for cannot be proved in the natural formally intuitionistic set theories with bounded predicates decidable of [3], [4] and [5].All notation not explained below is taken from [1]. In the Appendix, we give the axioms of ZF0, ZF1, and T in full. We remark that an important point about the axiom of foundation was not emphasized in [1]. This axiom was intended to be the axiom scheme (∀x)((∀y ∈ x)(A(y)) → A(x)) → (∀x)(A(x)), where y does not occur in A = A(x), instead of the more customary (∀x)(∀y)(y ∈ x → (∃z ∈ x)(∀w ∈ z) (w ∉ x)). This is of no consequence in the presence of full separation, but is vital when considering ZF0 and the T below, for with the customary form of foundation, these cannot even prove the existence of Rω+ω.In [1], a proof of the following is sketched.
An elementary sentence which has ordered models
Authors: Schmerl James H. 
Published: May 2006

Let < and ≼ be two distinguished binary relation symbols. A structure is κ-like iff is a linear ordering of A, card(A) = κ, and every proper initial segment of A has cardinality < κ. A structure is α-ordered iff is a (reflexive) linear ordering of type α with field a subset of A. We define when a cardinal κ is α-inaccessible. (In this paper, inaccessible always means weakly inaccessible.) The 0-inaccessible cardinals are just the inaccessible cardinals; if α > 0, then κ is α-inaccessible iff for each β < α, each closed, cofinal subset of κ contains a β-inaccessible. (The (1 + α)-inaccessibles are just the ρα cardinals of Mahlo.) This paper is concerned with the proof of the following theorem.Main Theorem. There is an elementary sentence σ with the property that whenever α is an ordinal and κ an infinite cardinal, then σ has an α-ordered κ-like model iff κ is not α-inaccessible.This theorem gives some additional answers to a question of Mostowski about languages with generalized quantifiers. Fuhrken [1] showed that this question is equivalent to the following one: For which cardinals κ and λ is it true that if an elementary sentence has a κ-like model, then it has a λ-like model? It is actually this question to which the theorem refers. The theorem limits the possible pairs κ, λ of cardinals which answer the question. In fact, if the question is generalized so as to permit sentences from some more extensive language, then the theorem still limits the possible answers. For a more thorough introduction to this problem, the reader is referred to the aforementioned article of Fuhrken as well as Keisler [2] and Vaught [6].
Generalizing special Aronszajn trees
Authors: Schmerl James H. 
Published: May 2006

In this paper we define by means of a partition property a decreasing sequence N = ‹Nα: α is an ordinal› of classes of ordinals. This property is a generalization of the nonexistence of special Aronszajn trees: the successor cardinal κ+ is in N0 iff there does not exist a special Aronszajn κ+-tree.The interest in the classes Nα stems from their applicability in model theory, in particular to that aspect of model theory dealing with ordered and two-cardinal models. A model is κ-like iff < is a linear ordering of A of cardinality κ but such that every proper initial segment has cardinality < κ. is α-ordered iff ≼ is a reflexive, linear ordering of some subset of A with order type α. The sequence N can be characterized by a first-order sentence σ in the following manner: The sentence σ has a κ-like α-ordered model iff κ ∉ Nα. This characterization will allow us to translate various independence statements regarding the sequence N to statements about the independence of transfer properties. We say that the transfer property κ → λ holds iff every first-order sentence which has a κ-like model also has a λ-like model. κ ⇸ λ is the negation of κ → λ.
Ramsey's theorem in the hierarchy of choice principles
Authors: Blass Andreas 
Published: May 2006

Ramsey's theorem [5] asserts that every infinite set X has the following partition property (RP): For every partition of the set [X]2 of two-element subsets of X into two pieces, there is an infinite subset Y of X such that [Y]2 is included in one of the pieces. Ramsey explicitly indicated that his proof of this theorem used the axiom of choice. Kleinberg [3] showed that every proof of Ramsey's theorem must use the axiom of choice, although rather weak forms of this axiom suffice. J. Dawson has raised the question of the position of Ramsey's theorem in the hierarchy of weak axioms of choice.In this paper, we prove or refute the provability of each of the possible implications between Ramsey's theorem and the weak axioms of choice mentioned in Appendix A.3 of Jech's book [2]. Our results, along with some known facts which we include for completeness, may be summarized as follows (the notation being as in [2]):A. The following principles do not (even jointly) imply Ramsey's theorem, nor does Ramsey's theorem imply any of them:the Boolean prime ideal theorem,the selection principle,the order extension principle,the ordering principle,choice from wellordered sets (ACW),choice from finite sets,choice from pairs (C2).B. Each of the following principles implies Ramsey's theorem, but none of them follows from Ramsey's theorem:the axiom of choice,wellordered choice (∀kACk),dependent choice of any infinite length k (DCk),countable choice (ACN0),nonexistence of infinite Dedekind-finite sets (WN0).
Linear sampling and the ∀∃∀ case of the decision problem
Authors: Aanderaa Stål O. , Lewis Harry R. 
Published: May 2006

Let Q be the class of closed quantificational formulas ∀x∃u∀yM without identity such that M is a quantifier-free matrix containing only monadic and dyadic predicate letters and containing no atomic subformula of the form Pyx or Puy for any predicate letter P. In [DKW] Dreben, Kahr, and Wang conjectured that Q is a solvable class for satisfiability and indeed contains no formula having only infinite models. As evidence for this conjecture they noted the solvability of the subclass of Q consisting of those formulas whose atomic subformulas are of only the two forms Pxy, Pyu and the fact that each such formula that has a model has a finite model. Furthermore, it seemed likely that the techniques used to show this subclass solvable could be extended to show the solvability of the full class Q, while the syntax of Q is so restricted that it seemed impossible to express in formulas of Q any unsolvable problem known at that time.In 1966 Aanderaa refuted this conjecture. He first constructed a very complex formula in Q having an infinite model but no finite model, and then, by an extremely intricate argument, showed that Q (in fact, the subclass Q2 defined below) is unsolvable ([Aa1], [Aa2]). In this paper we develop stronger tools in order to simplify and extend the results of [Aa2]. Specifically, we show the unsolvability of an apparently new combinatorial problem, which we shall call the linear sampling problem (defined in §1.2 and §2.3). From the unsolvability of this problem there follows the unsolvability of two proper subclasses of Q, which we now define. For each i ≥ 0, let Pi be a dyadic predicate letter and let Ri be a monadic predicate letter.
A combinatorial property of pκλ
Authors: Menas Telis K. 
Published: May 2006

In a paper on combinatorial properties and large cardinals [2], Jech extended several combinatorial properties of a cardinal κ to analogous properties of the set of all subsets of λ of cardinality less than κ, denoted by “pκλ”, where λ is any cardinal ≤κ. We shall consider in this paper one of these properties which is historically rooted in a theorem of Ramsey [10] and in work of Rowbottom [12].As in [2], define [pκλ]2 = {{x, y}: x, y ∈ pκλ and x ≠ y}. An unbounded subset A of pκλ is homogeneous for a function F: [pκλ]2 → 2 if there is a k < 2 so that for all x, y ∈ A with either x ⊊ y or y ⊊ x, F({x, y}) = k. A two-valued measure ü on pκλ is fine if it is κ-complete and if for all α < λ, ü({x ∈ pκλ: α ∈ x}) = 1, and ü is normal if, in addition, for every function f: pκλ → λsuch that ü({x ∈ pκλ: f(x) ∈ x}) = 1, there is an α < λ such that ü({x ∈ pκλ: f(x) = α}) = 1. Finally, a fine measure on pκλ has the partition property if every F: [pκλ]2 → 2 has a homogeneous set of measure one.