bluuebunny/crossref_metadata_2025_split huggingface dataset:
Set-theoretic foundations for logic
Authors: Quine W. V. 
Published: May 2006

1. Introduction. In his set theory Zermelo uses the variables “x”, “y”, etc. for the representation of “things” generally. Among these things he includes sets, or, as I shall say henceforth, classes. He adopts the connective “ϵ” of membership as his sole special primitive; thus the elementary formulae of his system are describable simply as expressions of the form “xϵy”, with any thing-variables ”x”, “y”, “z”, etc. supplanting “x” and “y”. The postulates of his system are so fashioned as to avoid the logical paradoxes without use of the theory of types. One of the postulates, the so-called Aussonderungsaxiom, may be stated in familiar logical notation aswhere is understood as any statement about y which is definite in a certain sense which Zermelo introduces informally for the purpose. Skolem has pointed out that it is adequate here to construe “definite” statements as embracing just the elementary formulae and all formulae thence constructible by the truth functions and by quantification with respect to thing-variables. A second of Zermelo's postulates is the principle of extensionality; this asserts that mutually inclusive classes are identical, i.e. are members of just the same classes. There are further postulates which provide for the existence of the null class, the class of all subclasses of any given class, the class of all members of members of any given class, the unit class of any given thing, and the class whose sole members are any two given things. Finally the multiplicative axiom (Auswahlprinzip) and the axiom of infinity are adopted.
An undecidable problem in the algebra of truth-tables
Authors: Kalicki Jan 
Published: May 2006

In a previous paper I have described a decision method for testing whether or not two arbitrary finite truth-tables are “equal”, i.e., determine the same set of tautologies. The same problem for the case of infinite truth-tables remained open.In the present note we shall show that the answer to the problem in the case of infinite truth-tables is negative; in fact we shall prove that there exists neither a decision method for testing the equality of arbitrary truth-tables, nor even one for testing the equality of what we call “recursive” truth-tables.The terminology of Kalicki [3] will be used; for brevity's sake the discussion involving the notions of recursiveness and recursive enumerability uses the informal terminology and mode of argumentation employed by Post in [9].
The theory of classes A modification of von Neumann's system
Authors: Robinson Raphael M. 
Published: May 2006

1. The theory of classes presented in this paper is a simplification of that presented by J. von Neumann in his paper Die Axiomatisierung der Mengenlehre. However, this paper is written so that it can be read independently of von Neumann's. The principal modifications of his system are the following.(1) The idea of ordered pair is defined in terms of the other primitive concepts of the system. (See Axiom 4.3 below.)(2) A much simpler proof of the well-ordering theorem, based on von Neumann's equivalence axiom (Axiom 2.2 below) is given. (More exactly, the theory of ordinal numbers, on which the proof of the well-ordering theorem is based, is simplified—see §8.)(3) Functions are not assumed to be defined for all arguments. In place of “ = A” we have “is undefined.” This makes possible a constructive interpretation of the system. (See §2.)2. We wish first to give a rough picture of the system which we are trying to construct. Suppose that we have the idea “class,” but no material from which to construct classes. Nevertheless, we can construct the class 0 having no elements. And then the class 1 having 0 as its only element. And then the classes {1}, and {0, 1}, etc., using always the previously constructed classes as elements. To extend this method to infinite classes, we must give rules telling what elements are to be included. Since the nature of the rules which we can use is not altogether clear, we try to formalize the whole system; that is, to set up a system of axioms which seems to characterize this system of classes. Now in this set of axioms we find it necessary to use the idea of function (in the “Axiom of Replacement”).
On the relative consistency of set theory
Authors: Orey Steven 
Published: May 2006

We present a method for demonstrating the consistency of von Neuman-Gödel set theory Σ (or Zermelo set theory Σ′) relative to various other formal set theories. When a model for a logic L1is constructed, there are two other logics involved: L2, the system which contains the model, and L3, the metalogic in which the argument that L2contains a model for L1is carried out. These three systems need not of course all be distinct. In [2] L1is Σ strengthened by the axiom ∨ = L, L2is Σ, and L3is unformalized. In the present paper L1will be either Σ or Σ′. The basic idea for proving the relative consistency of L1with respect to some other system L2is to construct in L2a model for L1similar to the model constructed in [2]. Since L2may be some kind of type theory, the function corresponding to Gödel's function F must be modified in a suitable manner. In verifying the relativized versions of axioms of L1in L2, we shall have to overcome certain special problems depending on the system L2and not met with in [2]. Except for the remarks at the end of Section 2, we shall not consider the question of formalizing L3, i.e. we use intuitive logic as our metalogic.In Section 1 we illustrate the method by demonstrating the consistency of Σ relative to the system ML″ obtained by adding E of [4] as an axiom to ML′ of [4]. We use the notation and results of [4] and [7].Section 2 discusses the use of certain other systems for L2. It will be noted that the systems used for L2are always slightly strengthened versions of well known systems ([5], [6], and the simple theory of types); it is of course to be hoped that modifications may be discovered which would make the method work in the original, unstrengthened systems, or that the relative consistency of the strengthened systems with respect to the original systems can be established.
On completely recursively enumerable classes and their key arrays
Authors: Rice H. G. 
Published: May 2006

The two results of this paper (a theorem and an example) are applications of a device described in section 1. Our notation is that of [4], with which we assume familiarity. It may be worth while to mention in particular the function Φ(n, x) which recursively enumerates the partial recursive functions of one variable, the Cantor enumerating functions J(x, y), K(x), L(x), and the classes F and Q of r.e. (recursively enumerable) and finite sets respectively.It is possible to “give” a finite set in a way which conveys the maximum amount of information; this may be called “giving explicitly”, and it requires that in addition to an effective enumeration or decision procedure for the set we give its cardinal number. It is sometimes desired to enumerate effectively an infinite class of finite sets, each given explicitly (e.g., [4] p. 360, or Dekker [1] p. 497), and we suggest here a device for doing this.We set up an effective one-to-one correspondence between the finite sets of non-negative integers and these integers themselves: the integer , corresponds to the set αi, = {a1, a2, …, an} and inversely. α0 is the empty set. Clearly i can be effectively computed from the elements of αi and its cardinal number.
Non-null implication
Authors: Nelson David 
Published: May 2006

An implication A ⊃ B is said to be null in case A is false in all instances. This note describes several formal systems for first-order predicate logic and arithmetic in which null implications do not occur. In fact, the most restrictive systems avoid the occurrences of any formulas which represent null predicates. The precise sense of this avoidance is explained below.An intuitionistic negation is a statement of the form A ⊃ F where F is a contradiction. The absence of null implications among true statements entails the absence of intuitionistic negations, and hence systems described here might be called negationless intuitionistic systems.
Trial and error predicates and the solution to a problem of Mostowski
Authors: Putnam Hilary 
Published: May 2006

The purpose of this paper is to present two groups of results which have turned out to have a surprisingly close interconnection. The first two results (Theorems 1 and 2) were inspired by the following question: we know what sets are “decidable” — namely, the recursive sets (according to Church's Thesis). But what happens if we modify the notion of a decision procedure by (1) allowing the procedure to “change its mind” any finite number of times (in terms of Turing Machines: we visualize the machine as being given an integer (or an n-tuple of integers) as input. The machine then “prints out” a finite sequence of “yesses” and “nos”. The last “yes” or “no” is always to be the correct answer.); and (2) we give up the requirement that it be possible to tell (effectively) if the computation has terminated? I.e., if the machine has most recently printed “yes”, then we know that the integer put in as input must be in the set unless the machine is going to change its mind; but we have no procedure for telling whether the machine will change its mind or not.The sets for which there exist decision procedures in this widened sense are decidable by “empirical” means — for, if we always “posit” that the most recently generated answer is correct, we will make a finite number of mistakes, but we will eventually get the correct answer. (Note, however, that even if we have gotten to the correct answer (the end of the finite sequence) we are never sure that we have the correct answer.)
A universal embedding property of the RETs
Authors: Nerode Anil , Manaster Alfred B. 
Published: May 2006

Recursive equivalence types are an effective or recursive analogue of cardinal numbers. They were introduced by Dekker in the early 1950's. The richness of various theories related to the recursive equivalence types is demonstrated in this paper by showing that the theory of any countable relational structure can be embedded in or interpreted in these theories. A more complete summary is presented in the last paragraph of this section.Let E = {0,1, 2, …} be the natural numbers. If α ⊆ E, β ⊆ E, and there is a 1-1 partial recursive function f such that the image under f of α is β, α and β are called recursively equivalent (see [3]). The recursive equivalence type or RET of α, denoted 〈α〉, is the class of all β recursively equivalent to α. Addition of RETs is defined by 〈α〉 + 〈β〉 = 〈{2x ∣ x ∈ α} ∪ 〈{2x + 1 ∣ x ∈ β}〉. The partial ordering ≤ is defined on the RETs by A ≤ B iff (EC)(A + C = B). An RET, X, is called an isol if X ≠ X + 1 or, equivalently, if no representative of X is recursively equivalent to a proper subset of itself. The isols are thus the recursive analogue of the Dedekind-finite cardinals.
Functions which remain partial recursive under all similarity transformations
Authors: Shapiro Norman 
Published: May 2006

This note will characterize those partial functions which are partial recursive under an arbitrary “renaming” of the integers.The formal result. Let I be the non-negative integers. For any partial function f on I into I, and for any permutation σ of I, let fσ be the partial function which f becomes when the integers are renamed according to σ. That is, let fσ = σfσ−1 in the sense that fσ(x) is defined whenever σ−1(х) ∊ Dom f.
Remark on a system of bernays
Authors: Myhill John 
Published: May 2006

In [1], Bemays gives an axiomatization of set-theory which represents the furthest development to date of the Zermelo-Frankel-Gödel tradition. The purpose of this note is to show that one of his axioms is redundant.Primitives are ∈, set-abstraction (denoted [x/A(x)]) and the Hilbert selector (denoted σ). Different styles are used for free variables (a, b,c, …) and bound variables (x, y, z, …); both kinds of variables range over both sets and classes. Quantifiers and connectives are classical.
Some undecidable problems involving elementary functions of a real variable
Authors: Richardson Daniel 
Published: May 2006

Let E be a set of expressions representing real, single valued, partially defined functions of one real variable. E* will be the set of functions represented by expressions in E.If A is an expression in E, A(x) is the function denoted by A.It is assumed that E* contains the identity function and the rational numbers as constant functions and that E* is closed under addition, subtraction, multiplication and composition.
Some consequences of an infinite-exponent partition relation
Authors: Henle J. M. 
Published: May 2006

Beginning with Ramsey's theorem of 1930, combinatorists have been intrigued with the notion of large cardinals satisfying partition relations. Years of research have established the smaller ones, weakly ineffable, Erdös, Jonsson, Rowbottom and Ramsey cardinals to be among the most interesting and important large cardinals in set theory. Recently, cardinals satisfying more powerful infinite-exponent partition relations have been examined with growing interest. This is due not only to their inherent qualities and the fact that they imply the existence of other large cardinals (Kleinberg [2], [3]), but also to the fact that the Axiom of Determinacy (AD) implies the existence of great numbers of such cardinals (Martin [5]).That these properties are more often than not inconsistent with the full Axiom of Choice (Kleinberg [4]) somewhat increases their charm, for the theorems concerning them tend to be a little odd, and their proofs, circumforaneous. The properties are, as far as anyone knows, however, consistent with Dependent Choice (DC).Our basic theorem will be the following: If k > ω and k satisfies k→(k)k then the least cardinal δ such that has a δ-additive, uniform ultrafilter. In addition, if ACω is assumed, we will show that δ is greater than ω, and hence a measurable cardinal. This result will be strengthened somewhat when we prove that for any k, δ, if then .
Independent Gödel sentences and independent sets
Authors: Dawes A. M. , Florence J. B. 
Published: May 2006

In this paper we investigate some of the recursion-theoretic problems which are suggested by the logical notion of independence.A set S of natural numbers will be said to be k-independent (respectively, ∞-independent) if, roughly speaking, in every correct system there is a k-element set (respectively, an infinite set) of independent true sentences of the form x ∈ S. S will be said to be effectively independent (respectively, absolutely independent) if given any correct system we can generate an infinite set of independent (respectively, absolutely independent) true sentences of the form x ∈ S.We prove that(a) S is absolutely independent ⇔S is effectively independent ⇔S is productive;(b) for every positive integer k there is a Π1 set which is k-independent but not (k + 1)-independent;(c) there is a Π1 set which is k-independent for all k but not ∞-independent;(d) there is a co-simple set which is ∞-independent.We also give two new proofs of the theorem of Myhill [1] on the existence of an infinite set of Σ1 sentences which are absolutely independent relative to Peano arithmetic. The first proof uses the existence of an absolutely independent Π1 set of natural numbers, and the second uses a modification of the method of Gödel and Rosser.
Saturated ideals
Authors: Kunen Kenneth 
Published: May 2006

In this paper, we give consistency proofs for the existence of a κ-saturated ideal on an inaccessible κ, and for the existence of an ω2-saturated ideal on ω1. We also include an historical survey outlining other known results on saturated ideals.§1. Forcing. We assume that the reader is familiar with the usual techniques in forcing and Boolean-valued models (see Jech [3] or Rosser [11]), so we shall just specify here some of the less standard notation.“cBa” abbreviates “complete Boolean algebra”.If P (= ‹P, <›) is a notion of forcing, is the associated cBa. We write VP for .Notions like κ-closed, κ-complete, etc. always mean < κ. Thus, P is κ-closed iff every decreasing chain of length less than κ has a lower bound, and a Boolean algebra is κ-complete iff sups of subsets of of cardinality less than κ always exist.If is a cBa, x̌ is the object in representing x in V. In many cases, especially with ordinals, the ̌ is dropped. V̌ is the Boolean-valued class representing V — i.e.,
The model theory of ordered differential fields
Authors: Singer Michael F. 
Published: May 2006

In this paper, we show that the theory of ordered differential fields has a model completion. We also show that any real differential field, finitely generated over the rational numbers, is isomorphic to some field of real meromorphic functions. In the last section of this paper, we combine these two results and discuss the problem of deciding if a system of differential equations has real analytic solutions. The author wishes to thank G. Stengle for some stimulating and helpful conversations and for drawing our attention to fields of real meromorphic functions.§ 1. Real and ordered fields. A real field is a field in which −1 is not a sum of squares. An ordered field is a field F together with a binary relation < which totally orders F and satisfies the two properties: (1) If 0 < x and 0 < y then 0 < xy. (2) If x < y then, for all z in F, x + z < y + z. An element x of an ordered field is positive if x > 0. One can see that the square of any element is positive and that the sum of positive elements is positive. Since −1 is not positive, an ordered field is a real field. Conversely, given a real field F, it is known that one can define an ordering (not necessarily uniquely) on F [2, p. 274]. An ordered field F is a real closed field if: (1) every positive element is a square, and (2) every polynomial of odd degree with coefficients in F has a root in F. For example, the real numbers form a real closed field. Every ordered field can be embedded in a real closed field. It is also known that, in a real closed field K, polynomials satisfy the intermediate value property, i.e. if f(x) ∈ K[x] and a, b ∈ K, a < b, and f(a)f(b) < 0 then there is a c in K such that f(c) = 0.
Existentially complete torsion-free nilpotent groups
Authors: Saracino D. 
Published: May 2006

This paper continues the study of existentially complete nilpotent groups initiated in [6]. Following [6], we let Kn denote the theory of groups nilpotent of class ≤ n and let Kn+ denote the theory of torsion-free groups nilpotent of class ≤ n. The principal results of [6] were that for n ≥ 2, neither Kn nor Kn+ has a model companion, and the classes E, F, and G of existentially complete, finitely generic and infinitely generic models of Kn are all distinct. The question of the relationships between these classes in the context of Kn was left open, however, and the proof of their distinctness for Kn+ obviously did not carry over to Kn+, because it made strong use of torsion elements.In this paper we establish the relationships between E, F, and G for K2+. We show that all three classes are distinct. We also show that there is only one countable finitely generic model, and only one countable infinitely generic model, and that all the countable existentially complete models can be arranged in a sequence N1 ⊆ N2 ⊆ N3 ⊆ … ⊆ Nω, where Z(Nn) is the direct sum of n copies of Q. Another result is that the finite and infinite forcing companions of K2+ differ by an ∀∃∀ sentence. Finally, we show that there exist finitely generic models of K2+ in all infinite cardinalities.
Degrees of classes of RE sets
Authors: Shoenfield J. R. 
Published: May 2006

In [3], Martin computed the degrees of certain classes of RE sets. To state the results succinctly, some notation is useful.If A is a set (of natural numbers), dg(A) is the (Turing) degree of A. If A is a class of sets, dg(A) = {dg(A): A ∈ A). Let M be the class of maximal sets, HHS the class of hyperhypersimple sets, and DS the class of dense simple sets. Martin showed that dg(M), dg(HHS), and dg(DS) are all equal to the set H of RE degrees a such that a′ = 0″.Let M* be the class of coinfinite RE sets having no superset in M; and define HHS* and DS* similarly. Martin showed that dg(DS*) = H. In [2], Lachlan showed (among other things) that dg(M*)⊆K, where K is the set of RE degrees a such that a″ > 0″. We will show that K ⊆ dg (HHS*). Since maximal sets are hyperhypersimple, this gives dg(M*) = dg (HHS*) = K.These results suggest a problem. In each case in which dg(A) has been calculated, the set of nonzero degrees in dg(A) is either H or K or the empty set or the set of all nonzero RE degrees. Is this always the case for natural classes A? Natural here might mean that A is invariant under all automorphisms of the lattice of RE sets; or that A is definable in the first-order theory of that lattice; or anything else which seems reasonable.
Strict-Π11 predicates on countable and cofinality ω transitive sets
Authors: Grant Philip W. 
Published: May 2006

Throughout the paper A will be a transitive set closed under finite subsets and the formulas in various classes mentioned are allowed to contain parameters from A (or from B in §2).By use of a refinement of Moschovakis' notion of the game-quantifier [13], [14], [15] we are able to obtain a game-theoretic description of s-Π11 predicates over countable sets which then leads to a classification of positive Σ1 inductive sets.Similar results are then proved for certain sets of cofinality ω. As a consequence we obtain the compactness results of Green [8], [11], Nyberg [16] and Makkai [12].The use of games to classify inductive sets was initiated by Moschovakis [13], [14], [15] and has been extended to Q-inductive sets by Aczel [2]. Games were also used in a slightly different setting by Vaught [18] and Makkai [12]. In fact, Vaught's proof of the compactness theorem is very close to our proof in §1 and Makkai's extension to cofinality ω sets uses a result similar to Theorem 3 in §2.We are indebted to the referee for many helpful suggestions, in particular, for bringing to our attention the related works of Vaught and Makkai cited above.
The use of Kripke's schema as a reduction principle
Authors: van Dalen D. 
Published: May 2006

The comprehension principle of second order arithmetic asserts the existence of certain species (sets) corresponding to properties of natural numbers. In the intuitionistic theory of sequences of natural numbers there is an analoguous principle, implicit in Brouwer's writing and explicitly stated by Kripke, which asserts the existence of certain sequences corresponding to statements. The justification of this principle, Kripke's Schema, makes use of the concept of the so-called creative subject. For more information the reader is referred to Troelstra [5].Kripke's Schema readsThere is a weaker versionThe idea to reduce species to sequences via Kripke's schema occurred several years ago (cf. [2, p. 128], [5, p. 104]). In [1] the reduction technique was applied in the construction of a model for HAS.On second thought, however, I realized that there is a straightforward, simpler way to exploit Kripke's schema, avoiding models altogether. The idea to present this material separately was forced on the author by C. Smorynski.Consider a second order arithmetic with both species and sequence variables. By KS we have(for convenience we restrict ourselves in KS to 0-1-sequences). An application of AC-NF givesOf course ξ is not uniquely determined. This is the key to the reduction of full second order arithmetic, or HAS, to a theory of sequences.We now introduce a translation τ to eliminate species variables. It is no restriction to suppose that the formulae contain only the sequence variables ξ1, ξ3, ξ5, …Note that by virtue of the definition of τ the axiom of extensionality is automatically verified after translation. The translation τ eliminates the species variables and leaves formulae without species variables invariant.