bluuebunny/crossref_metadata_2025_split huggingface dataset:
Paradox of the class of all grounded classes
Authors: Yuting Shen 
Published: May 2006

A class A for which there is an infinite progression of classes A1, A2, … (not necessarily all distinct) such thatis said to be groundless. A class which is not groundless is said to be grounded. Let K be the class of all grounded classes.Let us assume that K is a groundless class. Then there is an infinite progression of classes A1, A2, … such thatSince A1 ϵ K, A1 is a grounded class; sinceA1 is also a groundless class. But this is impossible.Therefore K is a grounded class. Hence K ϵ K, and we haveTherefore K is also a groundless class.This paradox forms a sort of triplet with the paradox of the class of all non-circular classes and the paradox of the class of all classes which are not n-circular (n a given natural number). The last of the three includes as a special case the paradox of the class of all classes which are not members of themselves (n = 1).More exactly, a class A1 is circular if there exists some positive integer n and classes A2, A3, …, An such thatFor any given positive integer n, a class A1 is n-circular if there are classes A2, …, An, such thatQuite obviously, by arguments similar to the above, we get a paradox of the class of all non-circular classes and a paradox of the class of all classes which are not n-circular, for each positive integer n.
A note on the Entscheidungsproblem
Authors: Church Alonzo 
Published: May 2006

In a recent paper the author has proposed a definition of the commonly used term “effectively calculable” and has shown on the basis of this definition that the general case of the Entscheidungsproblem is unsolvable in any system of symbolic logic which is adequate to a certain portion of arithmetic and is ω-consistent. The purpose of the present note is to outline an extension of this result to the engere Funktionenkalkul of Hilbert and Ackermann.In the author's cited paper it is pointed out that there can be associated recursively with every well-formed formula a recursive enumeration of the formulas into which it is convertible. This means the existence of a recursively defined function a of two positive integers such that, if y is the Gödel representation of a well-formed formula Y then a(x, y) is the Gödel representation of the xth formula in the enumeration of the formulas into which Y is convertible.Consider the system L of symbolic logic which arises from the engere Funktionenkalkül by adding to it: as additional undefined symbols, a symbol 1 for the number 1 (regarded as an individual), a symbol = for the propositional function = (equality of individuals), a symbol s for the arithmetic function x+1, a symbol a for the arithmetic function a described in the preceding paragraph, and symbols b1, b2, …, bk for the auxiliary arithmetic functions which are employed in the recursive definition of a; and as additional axioms, the recursion equations for the functions a, b1, b2, …, bk (expressed with free individual variables, the class of individuals being taken as identical with the class of positive integers), and two axioms of equality, x = x, and x = y →[F(x)→F(y)].
Subformula theorems for N-sequents
Authors: Leblanc Hugues 
Published: May 2006

With all seven of ‘∼’, ‘⊃’, ‘&’, ‘ν’, ‘≡’, ‘∀’, and ‘∃’ understood to serve as primitive signs, let an expression of the sortA1, A2, … , An → B1, B2, … , Bm,where A1, A2, …, Aη (η≥ 0), B1, B2, …, and Bm (m > 0 if n = 0, otherwise m ≥ 0) are wffs of the first-order quantificational calculus (QC), count as an L-sequent of QC; let an L-sequent of QC of the sortA1, A2, … , An → Bcount as an N-sequent of QC;2 and let an L-sequent S of QC count as a Gentzen L-sequent of QC if no individual variable of QC occurs both bound and free in S.
On the Craig-Lyndon interpolation theorem
Authors: Oberschelp Arnold 
Published: May 2006

In his paper [3] Henkin proved for a first order language with identity symbol but without operation symbols the following version of the Craig-Lyndon interpolation theorem:Theorem 1. If Γ╞Δ then there is a formula θ such that Γ ├Δand(i) any relation symbol with a positive (negative) occurrence in θ has a positive (negative) occurrence in some formula of Γ.
Two interpolation theorems for a predicate calculus
Authors: Maehara Shoji , Takeuti Gaisi 
Published: May 2006

A second order formula is called Π1 if, in its prenex normal form, all second order quantifiers are universal. A sequent F1, … Fm → G1 …, Gn is called Π1 if a formulais Π1If we consider only Π1 sequents, then we can easily generalize the completeness theorem for the cut-free first order predicate calculus to a cut-free Π1 predicate calculus.In this paper, we shall prove two interpolation theorems on the Π1 sequent, and show that Chang's theorem in [2] is a corollary of our theorem. This further supports our belief that any form of the interpolation theorem is a corollary of a cut-elimination theorem. We shall also show how to generalize our results for an infinitary language. Our method is proof-theoretic and an extension of a method introduced in Maehara [5]. The latter has been used frequently to prove the several forms of the interpolation theorem.
The inadequacy of Kripke's semantical analysis of D2 and D3
Authors: Routley R. , Montgomery H. 
Published: May 2006

Kripke's model structure for D2 is a quadruple (G, K, R, N) where N is the set of normal elements, i.e., the subset of K such that for every H in N, HRH. (See [1, p. 220, p. 211].) In fact, however, this structure provides a model for E2, as the work of Lemmon shows ([2, pp. 58–62]).To show the inadequacy of Kripke's model structure, we show that the E2 thesis □B ⊃ B, not a thesis of D2, is valid under Kripke's modelling for D2. Suppose, for a reductio argument, that □ B ⊃ B is false for some valuation ϕ in some D2 model structure. Thenyϕ(□B ⊃ B, G) = F; so by truth-functional assignments
Defining algebraic elements
Authors: Bacsich Paul D. 
Published: May 2006

This paper is a survey and a synthesis of the various approaches to defining algebraic elements. Most of it is devoted to proving the following result.Let T be a universal theory with the Amalgamation Property. Then for T the notions of algebraic element introduced by Robinson, Jónsson, and Morley are identical. Furthermore, they extend in a natural way the notion of algebraic element introduced by Park, and used by Lachlan and Baldwin and by Kueker.In the course of proving this we shall construct the algebraic closure as a suitable injective hull and prove a unique factorisation theorem for algebraic predicates.We shall also show (in §3) that if T is closed under products then algebraic elements all have degree 1. Thus in algebra, algebraic elements reduce to epimorphisms.To demonstrate the remarkable stability of the notion we shall show (at the end of §5) that defining algebraic elements by infinitary formulas yields no new ones.Let L be a language. The cardinality of the set of formulas of L is denoted by ∣L∣. An L-theory is a deductively closed set of L-sentences. We let denote the category of models of T and (L-structure) homomorphisms between them. If A is a substructure of B we write A ≤ B. We call u: A → B an injection if u is an isomorphism of A with a substructure of B, and let denote the subcategory of consisting of all injections.
A survey of partial degrees
Authors: Sasso Leonard P. 
Published: May 2006

Partial degrees are equivalence classes of partial natural number functions under some suitable extension of relative recursiveness to partial functions. The usual definitions of relative recursiveness, equivalent in the context of total functions, are distinct when extended to partial functions. The purpose of this paper is to compare the upper semilattice structures of the resulting degrees.Relative partial recursiveness of partial functions was first introduced in Kleene [2] as an extension of the definition by means of systems of equations of relative recursiveness of total functions. Kleene's relative partial recursiveness is equivalent to the relation between the graphs of partial functions induced by Rogers' [10] relation of relative enumerability (called enumeration reducibility) between sets. The resulting degrees are hence called enumeration degrees. In [2] Davis introduces completely computable or compact functionals of partial functions and uses these to define relative partial recursiveness of partial functions. Davis' functionals are equivalent to the recursive operators introduced in Rogers [10] where a theorem of Myhill and Shepherdson is used to show that the resulting reducibility, here called weak Turing reducibility, is stronger than (i.e., implies, but is not implied by) enumeration reducibility. As in Davis [2], relative recursiveness of total functions with range ⊆{0, 1} may be defined by means of Turing machines with oracles or equivalently as the closure of initial functions under composition, primitive re-cursion, and minimalization (i.e., relative μ-recursiveness). Extending either of these definitions yields a relation between partial functions, here called Turing reducibility, which is stronger still.
An algebraic characterization of power set in countable standard models of ZF
Authors: Metakides George , Plotkin J. M. 
Published: May 2006

The following is a classical result:Theorem 1.1. A complete atomic Boolean algebra is isomorphic to a power set algebra [2, p. 70].One of the consequences of [3] is: If M is a countable standard model of ZF and is a countable (in M) model of a complete ℵ0-categorical theory T, then there is a countable standard model N of ZF and a Λ ∈ N such that the Boolean algebra of definable (in T with parameters from ) subsets of is isomorphic to the power set algebra of Λ in N. In particular if and T the theory of equality with additional axioms asserting the existence of at least n distinct elements for each n < ω, then there is an N and Λ ∈ N with 〈PN(Λ), ⊆〉 isomorphic to the countable, atomic, incomplete Boolean algebra of the finite and cofinite subsets of ω.From the above we see that some incomplete Boolean algebras can be realized as power sets in standard models of ZF.Definition 1.1. A countable Boolean algebra 〈B, ≤〉 is a pseudo-power set if there is a countable standard model of ZF, N and a set Λ ∈ N such thatIt is clear that a pseudo-power set is atomic.
Degrees of sensible lambda theories
Authors: Barendregt Henk , Bergstra Jan , Klop Jan Willem , Volken Henri 
Published: May 2006

SummaryA λ-theory T is a consistent set of equations between λ-terms closed under derivability. The degree of T is the degree of the set of Gödel numbers of its elements. is the λ-theory axiomatized by the set {M = N∣ M, N unsolvable}. A λ-theory is sensible iff T ⊃ ; for a motivation see [6] and [4].In §1 it is proved that the theory is Σ20-complete. We present Wadsworth's proof that its unique maximal consistent extension * (= Th(D∞)) is Π20-complete. In §2 it is proved that η (= λη-calculus + ) is not closed under the ω-rule (see [1]). In §3 arguments are given to conjecture that is Π11-complete. This is done by representing recursive sets of sequence numbers as λ-terms and by connecting wellfoundedness of trees with provability in ω. In §4 an infinite set of equations independent over η will be constructed. From this it follows that there are 2ℵ0 sensible theories T such that and 2ℵ0 sensible hard models of arbitrarily high degrees. In §5 some nonprovability results needed in §§1 and 2 are established. For this purpose one uses the theory η extended with a reduction relation for which the Church–Rosser theorem holds. The concept of Gross reduction is used in order to show that certain terms have no common reduct.
Sets which do not have subsets of every higher degree
Authors: Simpson Stephen G. 
Published: May 2006

Let A be a subset of ω, the set of natural numbers. The degree of A is its degree of recursive unsolvability. We say that A is rich if every degree above that of A is represented by a subset of A. We say that A is poor if no degree strictly above that of A is represented by a subset of A. The existence of infinite poor (and hence nonrich) sets was proved by Soare [9].Theorem 1. Suppose that A is infinite and not rich. Then every hyperarith-metical subset H of ω is recursive in A.In the special case when H is arithmetical, Theorem 1 was proved by Jockusch [4] who employed a degree-theoretic analysis of Ramsey's theorem [3]. In our proof of Theorem 1 we employ a similar, degree-theoretic analysis of a certain generalization of Ramsey's theorem. The generalization of Ramsey's theorem is due to Nash-Williams [6]. If A ⊆ ω we write [A]ω for the set of all infinite subsets of A. If P ⊆ [ω]ω we let H(P) be the set of all infinite sets A such that either [A]ω ⊆ P = ∅. Nash-Williams' theorem is essentially the statement that if P ⊆ [ω]ω is clopen (in the usual, Baire topology on [ω]ω) then H(P) is nonempty. Subsequent, further generalizations of Ramsey's theorem were proved by Galvin and Prikry [1], Silver [8], Mathias [5], and analyzed degree-theoretically by Solovay [10]; those results are not needed for this paper.
The work of Kurt Gödel
Authors: Kleene Stephen C. 
Published: May 2006

I first heard the name of Kurt Gödel when, as a graduate student at Princeton in the fall of 1931, I attended a colloquium at which John von Neumann was the speaker, von Neumann could have spoken on work of his own; but instead he gave an exposition of Gödel's results of formally undecidable propositions [1931].Today I shall begin with Gödel's paper [1930] onThe completeness of the axioms of the functional calculus of logic, or of what we now often call “the first-order predicate calculus”, using “predicate” as synonymous with “propositional function”.Alonzo Church wrote ([1944, p. 62] and [1956, pp. 288–289]), “the first explicit formulation of the functional calculus of first order as an independent logistic system is perhaps in the first edition of Hilbert and Ackermann'sGrundzüge der theoretischen Logik(1928).” Clearly, this formalism is not complete in the sense that each closed formula or its negation is provable. (Aclosed formula, orsentence, is a formula without free occurrences of variables.) But Hilbert and Ackermann observe, “Whether the system of axioms is complete at least in the sense that all the logical formulas which are correct for each domain of individuals can actually be derived from them is still an unsolved question.” [1928, p. 68].This question Gödel answered in the affirmative in his Ph.D. thesis (Vienna, 1930), of which the paper under discussion is a rewritten version.I shall not describe Gödel's proof. Perhaps no theorem in modern logic has been proved more often than Gödel's completeness theorem for the first-order predicate calculus. It stands at the focus of a complex of fundamental theorems, which different scholars have approached from various directions (e.g. Kleene [1967, Chapter VI]).
Describing ordinals using functionals of transfinite type
Authors: Aczel Peter 
Published: May 2006

Bachmann, in [2] shows how certain ordinals <Ω(Ω = Ω1 where Ωξ is the (1 + ξ)th infinite initial ordinal) may be described from below using suitable descriptions of ordinals <Ω2. The aim of this paper is to consider another approach to describing ordinal <Ω and compare it with the Bachmann method. Our approach will use functionals of transfinite type based on Ω.The Bachmann method consists in denning a hierarchy of normal functions ϕδ: Ω → Ω (i.e. continuous and strictly increasing) for δ ≤ η0 < Ω2, starting with ϕ0(λ) = ω1 + λ. The definition of depends on a suitable description of the ordinals ≤ η0. This is obtained by defining a hierarchy 〈Fδ ∣ δ ≤ Ω2〉 of normal functions Fδ: Ω2 → Ω2 analogously to the definition of the initial segment 〈ϕδ ∣ δ ≤ Ω〉 of . The ordinal η0 is .Note. Our description of Bachmann's hierarchies will differ slightly from those in Bachmann's paper. Let and denote the hierarchies in [2]. Then as Bachmann's normal functions are not defined at 0 we let for λ, δ < Ω2. Bachmann defines for 0 < λ < Ω2 but it seems more natural to omit this so that we let . The situation is analogous for and leads to the following definitions:where n < ω and ξ is a limit number of cofinality Ω, and
Computational speed-up by effective operators
Authors: Meyer Albert R. , Fischer Patrick C. 
Published: May 2006

The complexity of a computable function can be measured by considering the time or space required to compute its values. Particular notions of time and space arising from variants of Turing machines have been investigated by R. W. Ritchie [14], Hartmanis and Stearns [8], and Arbib and Blum [1], among others. General properties of such complexity measures have been characterized axiomatically by Rabin [12], Blum [2], Young [16], [17], and McCreight and Meyer [10].In this paper the speed-up and super-speed-up theorems of Blum [2] are generalized to speed-up by arbitrary total effective operators. The significance of such theorems is that one cannot equate the complexity of a computable function with the running time of its fastest program, for the simple reason that there are computable functions which in a very strong sense have no fastest programs.Let φi be the ith partial recursive function of one variable in a standard Gödel numbering of partial recursive functions. A family Φ0, Φ1, … of functions of one variable is called a Blum measure on computation providing(1) domain (φi) = domain (Φi), and(2) the predicate [Φi(x) = m] is recursive in i, x and m.Typical interpretations of Φi(x) are the number of steps required by the ith Turing machine (in a standard enumeration of Turing machines) to converge on input x, the space or number of tape squares required by the ith Turing machine to converge on input x (with the convention that Φi(x) is undefined even if the machine fails to halt in a finite loop), and the length of the shortest derivation of the value of φi(x) from the ith set of recursive equations.
A transfinite sequence of ω-models
Authors: Mostowski Andrzej 
Published: May 2006

Let A2 be the axiomatic system of second order arithmetic as described in [2]. One of the models of A2 is the “principal model” Mpr consisting of all integers and all sets of integers. Obviously there exist many denumerable ω-models elementarily equivalent to Mpr and we shall deal in this paper with some questions pertaining to this family which we denote by .In §1 we define a rather natural relation ε between two denumerable families of sets of integers. From the upward Skolem-Löwenheim theorem it follows easily that there exists a family ordered by ε in the type ω1, but it is not immediately obvious whether there exist a subfamily of not well-ordered by ε. In the present paper we construct such a family of type η. ω1 where η is the order type of rationals and indicate some applications to hyperdegrees.We adopt the terminology and notation of [2], with the only change that we adjoin to the language of A2 the constants ν0, ν1, … for the consecutive numerals 0, 1, 2, … and axioms which characterise them:Also we modify the axioms of A2 given in [2] by prefixing them by general quantifiers bounded either to S or to N.
On the inadequacy of inner models
Authors: Blass Andreas 
Published: May 2006

The method of inner models, used by Gödel to prove the (relative) consistency of the axiom of choice and the generalized continuum hypothesis [2], cannot be used to prove the (relative) consistency of any statement which contradicts the axiom of constructibility (V = L). A more precise statement of this well-known fact is:(*)For any formula θ(x) of the language of ZF, there is an axiom α of the theory ZF + V ≠ L such that the relativization α(θ) is not a theorem of ZF.On p. 108 of [1], Cohen gives a proof of (*) in ZF assuming the existence of a standard model of ZF, and he indicates that this assumption can be avoided. However, (*) is not a theorem of ZF (unless ZF is inconsistent), because (*) trivially implies the consistency of ZF. What assumptions are needed to prove (*)? We know that the existence of a standard model implies (*) which, in turn, implies the consistency of ZF. Is either implication reversible?From our main result, it will follow that, if the converse of the first implication is provable in ZF, then ZF has no standard model, and if the converse of the second implication is provable in ZF, then so is the inconsistency of ZF. Thus, it is quite improbable that either converse is provable in ZF.
Simple and hyperhypersimple vector spaces
Authors: Retzlaff Allen 
Published: May 2006

AbstractLet V∞ be a fixed, fully effective, infinite dimensional vector space. Let be the lattice consisting of the recursively enumerable (r.e.) subspaces of V∞, under the operations of intersection and weak sum (see §1 for precise definitions). In this article we examine the algebraic properties of .Early research on recursively enumerable algebraic structures was done by Rabin [14], Frölich and Shepherdson [5], Dekker [3], Hamilton [7], and Guhl [6]. Our results are based upon the more recent work concerning vector spaces of Metakides and Nerode [12], Crossley and Nerode [2], Remmel [15], [16], and Kalantari [8].In the main theorem below, we extend a result of Lachlan from the lattice of r.e. sets to . We define hyperhypersimple vector spaces, discuss some of their properties and show if A, B ∈ , and A is a hyperhypersimple subspace of B then there is a recursive space C such that A + C = B. It will be proven that if V ∈ and the lattice of superspaces of V is a complemented modular lattice then V is hyperhypersimple. The final section contains a summary of related results concerning maximality and simplicity.
Ordinal bounds for κ-consistency
Authors: Goldfarb Warren D. 
Published: May 2006

In [1] the ω-consistency of arithmetic was proved by a method which yields fine ordinal bounds for κ-consistency, κ ≥ 1. In this paper these bounds are shown to be best possible. The ω-consistency of a number-theoretic system S can be expressed thus: for all sentences ∃xM,where ProvS is the proof predicate for S, if n is a nonnegative integer then n is the formal numeral (of S) for n, and if G is a formula then ˹G˺ is the Gödel number of G. The κ-consistency of S is the restriction of (1) to Σκ0 sentences ∃xM. The proof in [1] establishes the no-counterexample interpretation of (1), that is, the existence of a constructive functional Φ such that, for all sentences ∃xM, all numbers p, and all functions f,(see [1, §2]). A functional Φ is an ω-consistency functional for S if it satisfies (2) for all sentences ∃xM, and a κ-consistency functional for S if it satisfies (2) for all Σκ0 sentences ∃xM.The systems considered in [1] are those obtained from classical first-order arithmetic Z, including the schema for definition of primitive recursive (p.r.) functions, by adjoining, for some p.r. well-founded ordering ≺ of the nonnegative integers, the axiom schemathat is, the least number principle on ≺; it is equivalent to the schema of transfinite induction on ≺.
Prime model extensions for differential fields of characteristic p ≠ 0
Authors: Wood Carol 
Published: May 2006

The main purpose of this paper is to show that there exists a prime differentially closed extension over each differentially perfect field. We do this in a roundabout manner by first giving new and simple axioms for the theory of differentially closed fields (in the manner of Blum [1] for characteristic 0) and by proving that this theory is the model completion of the theory of differentially perfect fields. This paper can be read independently from [10], where we gave more complicated axioms for the same theory (in the manner of Robinson [6] for characteristic 0).I am indebted to E. R. Kolchin for answering many questions and for making the manuscript of his forthcoming book [2] available to me.