bluuebunny/crossref_metadata_2025_split huggingface dataset:
On Meyer and Lambert's quantificational calculus FQ
Authors: Leblanc Hugues 
Published: May 2006

The semantical account that Meyer and Lambert give in [7] of their quantificational calculus FQ can be considerably simplified, and—supposing as the authors do at the close of their paper that ‘ = ’ counts as a primitive sign—so can their axiom system for FQ.(1) As the authors remark, axiom schema 102 can be simplified to read : A ⊃ (∀Χ)A, where Χ does not occur free in A. Following Tarski's [9], it can be further simplified: A ⊃ (∀Χ)A, where Χ does not occur in A.
Functionals defined by transfinite recursion
Authors: Tait W. W. 
Published: May 2006

This paper deals mainly with quantifier-free second order systems (i.e., with free variables for numbers and functions, and constants for numbers, functions, and functionals) whose basic rules are those of primitive recursive arithmetic together with definition of functionals by primitive recursion and explicit definition. Precise descriptions are given in §2. The additional rules have the form of definition by transfinite recursion up to some ordinal ξ (where ξ is represented by a primitive recursive (p.r.) ordering). In §3 we discuss some elementary closure properties (under rules of inference and definition) of systems with recursion up to ξ. Let Rξ denote (temporarily) the system with recursion up to ξ. The main results of this paper are of two sorts:Sections 5–7 are concerned with less elementary closure properties of the systems Rξ. Namely, we show that certain classes of functional equations in Rη can be solved in Rη for some explicitly determined η < ε(η) (the least ε-number > ξ). The classes of functional equations considered all have roughly the form of definition by recursion on the partial ordering of unsecured sequences of a given functional F, or on some ordering which is obtained from this by simple ordinal operations. The key lemma (Theorem 1) needed for the reduction of these equations to transfinite recursion is simply a sharpening of the Brouwer-Kleene idea.
Interpretations of set theory and ordinal number theory
Authors: Yasugi Mariko 
Published: May 2006

In [3], Takeuti developed the theory of ordinal numbers (ON) and constructed a model of Zermelo-Fraenkel set theory (ZF), using the primitive recursive relation ∈ of ordinal numbers. He proved:(1) If A is a ZF-provable formula, then its interpretation A0 in ON is ON-provable;(2) Let B be a sentence of ordinal number theory. Then B is a theorem of ON if and only if the natural translation B* of B in set theory is a theorem of ZF;(3) (V = L)° holds in ON.
Intensional interpretations of functionals of finite type I
Authors: Tait W. W. 
Published: May 2006

T0 will denote Gödel's theory T[3] of functionals of finite type (f.t.) with intuitionistic quantification over each f.t. added. T1 will denote T0 together with definition by bar recursion of type o, the axiom schema of bar induction, and the schemaof choice. Precise descriptions of these systems are given below in §4. The main results of this paper are interpretations of T0 in intuitionistic arithmetic U0 and of T1 in intuitionistic analysis is U1. U1 is U0 with quantification over functionals of type (0,0) and the axiom schemata AC00 and of bar induction.
Controlling the dependence degree of a recursively enumerable vector space
Authors: Shore Richard A. 
Published: May 2006

Early work combining recursion theory and algebra had (at least) two different sets of motivations. First the precise setting of recursion theory offered a chance to make formal classical concerns as to the effective or algorithmic nature of algebraic constructions. As an added benefit the formalization gives one the opportunity of proving that certain constructions cannot be done effectively even when the original data is presented in a recursive way. One important example of this sort of approach is the work of Frohlich and Shepardson [1955] in field theory. Another motivation for the introduction of recursion theory to algebra is given by Rabin [1960]. One hopes to mathematically enrich algebra by the additional structure provided by the notion of computability much as topological structure enriches group theory. Another example of this sort is provided in Dekker [1969] and [1971] where the added structure is that of recursive equivalence types. (This particular structural view culminates in the monograph of Crossley and Nerode [1974].)More recently there is the work of Metakides and Nerode [1975], [1977] which combines both approaches. Thus, for example, working with vector spaces they show in a very strong way that one cannot always effectively extend a given (even recursive) independent set to a basis for a (recursive) vector space.
Model existence theorems for modal and intuitionistic logics
Authors: Fitting Melvin 
Published: May 2006

In classical logic a collection of sets of statements (or equivalently, a property of sets of statements) is called a consistency property if it meets certain simple closure conditions (a definition is given in §2). The simplest example of a consistency property is the collection of all consistent sets in some formal system for classical logic. The Model Existence Theorem then says that any member of a consistency property is satisfiable in a countable domain. From this theorem many basic results of classical logic follow rather simply: completeness theorems, the compactness theorem, the Lowenheim-Skolem theorem, and the Craig interpolation lemma among others. The central position of the theorem in classical logic is obvious. For the infinitary logic the Model Existence Theorem is even more basic as the compactness theorem is not available; [8] is largely based on it.In this paper we define appropriate notions of consistency properties for the first-order modal logics S4, T and K (without the Barcan formula) and for intuitionistic logic. Indeed we define two versions for intuitionistic logic, one deriving from the work of Gentzen, one from Beth; both have their uses. Model Existence Theorems are proved, from which the usual known basic results follow. We remark that Craig interpolation lemmas have been proved model theoretically for these logics by Gabbay ([5], [6]) using ultraproducts. The existence of both ultra-product and consistency property proofs of the same result is a common phenomena in classical and infinitary logic. We also present extremely simple tableau proof systems for S4, T, K and intuitionistic logics, systems whose completeness is an easy consequence of the Model Existence Theorems.
Bases of countable Boolean algebras
Authors: Pierce R. S. 
Published: May 2006

The purpose of this note is to give a short proof of a conjecture of Feiner that every countable Boolean algebra has an ordered basis that is a lexicographic sum of well-ordered sets over the ordered set η of all rational numbers. Actually, we prove a slightly more precise fact, which is formulated below as Theorem 3. An earlier proof of Feiner's conjecture was obtained by David Cossack (unpublished), using a different method.Our proof will use the following property of Cantor's dyadic discontinuum D.
A finite arithmetic
Authors: Shepard Philip T. 
Published: May 2006

In this paper I shall argue that the presumption of infinitude may be excised from the area of mathematics known as natural number theory with no substantial loss. Except for a few concluding remarks, I shall restrict my concern in here arguing the thesis to the business of constructing and developing a first-order axiomatic system for arithmetic (called ‘FA’ for finite arithmetic) that contains no theorem to the effect that there are infinitely many numbers.The paper will consist of five parts. Part I characterizes the underlying logic of FA. In part II ordering of natural numbers is developed from a restricted set of axioms, induction schemata are proved and a way of expressing finitude presented. A full set of axioms are used in part III to prove working theorems on comparison of size. In part IV an ordinal expression is defined and characteristic theorems proved. Theorems for addition and multiplication are derived in part V from definitions in terms of the ordinal expression of part IV. The crucial final constructions of part V present a new method of replacing recursive characterizations by strict definitions.In view of our resolution not to assume that there are infinitely many numbers, we shall have to deal with the situation where singular arithmetic terms of FA may fail to refer. For I know of no acceptable and systematic way of avoiding such situations. As a further result, singular-term instances of universal generalizations of FA are not to be inferred directly from the generalizations themselves. Nevertheless, (i) (x)(y)(x + y = y + x), for example, and all its instances are provable in FA.
Some models for intuitionistic finite type arithmetic with fan functional
Authors: Troelstra A. S. 
Published: May 2006

In this note we shall assume acquaintance with [T4] and the parts of [T1] which deal with intuitionistic arithmetic in all finite types. The bibliography just continues the bibliography of [T4].The principal purpose of this note is the discussion of two models for intuitionistic finite type arithmetic with fan functional (HAω+ MUC). The first model is needed to correct an oversight in the proof of Theorem 6 [T4, §5]: the model ECF+as defined there cannot be shown to have the required properties inEL+ QF-AC, the reason being that a change in the definition ofW12alone does not suffice—if one wishes to establish closure under the operations of HAωthe definitions ofW1σfor other σ have to be adopted as well. It is difficult to see how to do this directly in a uniform way — but we succeed via a detour, which is described in §2.For a proper understanding, we should perhaps note already here thaton the assumption of the fan theorem, ECF+as defined in [T4] and the new model of this note coincide (since then the definition ofW12[T4, p. 594] is equivalent to the definition forW12in the case of ECF); but inELit is impossible to prove this (and under assumption of Church's thesis the two models differ).
Sheaves and normal submodels
Authors: Mansfield Richard 
Published: May 2006

Ellerman, Comer, and Macintyre have all observed that sheaves are an interesting generalization of models and are deserving of model theoretic attention. Scott has pointed out that sheaves are Heyting algebra valued models. The reverse does not hold however since almost no genuine Boolean valued model is a sheaf.In §1 we shall review the definition of a sheaf and prove a theorem about Boolean valued models using the sheaf construction. In §2 we shall be concerned with the set of sentences preserved by global sections. Our principal result is that global section sentences are also normal submodel sentences. (We define as a normal submodel of if is a submodel of and every point of B − A can be moved by an automorphism of which fixes each point of A.) In §3 we prove that every normal submodel sentence is the negation of a disjunction of Horn sentences and that the set of normal submodel sentences is r.e. but not recursive. §3 involves only traditional model theory and can be read independently of the first two sections.
A model theoretic approach to Malcev conditions
Authors: Baldwin John T. , Berman Joel 
Published: May 2006

A varietyV(equational class of algebras) satisfies a strong Malcev condition ∃f1,…, ∃fnθ(f1, …,fn,x1, …,xm) where θ is a conjunction of equations in the function variablesf1, …,fnand the individual variablesx1, …,xm, if there are polynomial symbolsp1, …,pnin the language ofVsuch that ∀x1, …,xmθ(p1…,pn,x1, …,xm) is a law ofV. Thus a strong Malcev condition involves restricted second order quantification of a strange sort. The quantification is restricted to functions which are “polynomially definable”. This notion was introduced by Malcev [6] who used it to describe those varieties all of whose members have permutable congruence relations. The general formal definition of Malcev conditions is due to Grätzer [1]. Since then and especially since Jónsson's [3] characterization of varieties with distributive congruences there has been extensive study of strong Malcev conditions and the related concepts: Malcev conditions and weak Malcev conditions.In [9], Taylor gives necessary and sufficient semantic conditions for a class of varieties to be defined by a (strong) Malcev condition. A key to the proof is the translation of the restricted second order concepts into first order concepts in a certain many sorted language. In this paper we show that, given this translation, Taylor's theorem is an easy consequence of a result of Tarski [8] and the standard preservation theorems of first order logic.
L(Q)-preservation theorems
Authors: Flum Jörg 
Published: May 2006

Much effort has been spent to prove that the reduced product operation preserves, and sometimes even strengthens the L-equivalence of structures, where L is some infinitary language. A similar result is suggested by the following well-known fact:Assume D is a nonprincipal ultrafilter on ω and, for n Є ω, Cn is a set. If the ultra-product ΠωCn/D is infinite, it has a cardinality ≥ Hence, by Łos' theorem, (i) if and φ(x) is a first-order formula, then iff where Q is the unary quantifier “there are many.”We shall prove some generalizations of (i). In particular, we show(ii) if D is a nonprincipal ultrafilter over I = ω, and then where L(Q) is the language obtained from the first-order language by adding the quantifier Q.(ii) remains true, if D is an ω-regular or an atomless filter over a set I.Lipner [7] proved that if is regular, then the L(Q)-equivalence is preserved under direct products. We show that the assumption “ is regular” is necessary.
Types of simple α-recursively enumerable sets
Authors: Lerman Manuel 
Published: May 2006

Let α be an admissible ordinal, and let (α) denote the lattice of α-r.e. sets, ordered by set inclusion. An α-r.e. set A is α*-finite if it is α-finite and has ordertype less than α* (the Σ1 projectum of α). An a-r.e. set S is simple if (the complement of S) is not α*-finite, but all the α-r.e. subsets of are α*-finite. Fixing a first-order language ℒ suitable for lattice theory (see [2, §1] for such a language), and noting that the α*-finite sets are exactly those elements of (α), all of whose α-r.e. subsets have complements in (α) (see [4, p. 356]), we see that the class of simple α-r.e. sets is definable in ℒ over (α). In [4, §6, (Q22)], we asked whether an admissible ordinal α exists for which all simple α-r.e. sets have the same 1-type. We were particularly interested in this question for α = ℵ1L (L is Gödel's universe of constructible sets). We will show that for all α which are regular cardinals of L (ℵ1L is, of course, such an α), there are simple α-r.e. sets with different 1-types.The sentence exhibited which differentiates between simple α-r.e. sets is not the first one which comes to mind. Using α = ω for intuition, one would expect any of the sentences “S is a maximal α-r.e. set”, “S is an r-maximal α-r.e. set”, or “S is a hyperhypersimple α-r.e. set” to differentiate between simple α-r.e. sets. However, if α > ω is a regular cardinal of L, there are no maximal, r-maximal, or hyperhypersimple α-r.e. sets (see [4, Theorem 4.11], [5, Theorem 5.1] and [1,Theorem 5.21] respectively). But another theorem of (ω) points the way.
Weak liberated versions of T and S4
Authors: Morgan Charles G. 
Published: May 2006

AbstractThe usual semantics for the modal systems T, S4, and S5 assumes that the set of possible worlds contains at least one member. Recently versions of these modal systems have been developed in which this assumption is dropped. The systems discussed here are obtained by slightly weakening the liberated versions of T and S4. The semantics does not assume the existence of possible worlds, and the accessibility relation between worlds is only required to be quasi-reflexive instead of reflexive. Completeness and independence results are established.
Embedding theorems for boolean algebras and consistency results on ordinal definable sets
Authors: Štěpánek Petr , Balcar Bohuslav 
Published: May 2006

The existence of complete rigid Boolean algebras was first proved by McAloon [8] who also showed that every Boolean algebra can be completely embedded in a rigid complete Boolean algebra. McAloon was interested in consistency results on ordinal definable sets. His approach was based on forcing. Recently, Shelah [10] proved that for every uncountable cardinal κ there exists a Boolean algebra of power κ with rigid completion. Extending his method, we get the following theorems.Theorem 1. Any Boolean algebra B can be completely embedded in a complete Boolean algebra C with no nontrivial σ-complete one-one endomor-phism. If B satisfies the κ-chain condition for an uncountable cardinal κ, the same holds true for C.Since every automorphism is a complete endomorphism, it follows from Theorem 1 that C is rigid. The other extreme case of Boolean algebras are homogeneous algebras. It was proved by Kripke [7] that every Boolean algebra can be completely embedded in a homogeneous complete Boolean algebra. In his proof, the homogeneous algebra contains antichains of cardinality equal to the power of the embedded Boolean algebra. The following result shows that this is essential: the analogue of Theorem 1 is not provable in set theory even for Boolean algebras with a very weak homogeneity property. We use a Suslin tree with particular properties constructed by Jensen [6] in conjunction with a forcing argument.
An abstract Church-Rosser theorem. II: Applications
Authors: Hindley R. 
Published: May 2006

This paper is a continuation of An abstract form of the Church-Rosser theorem. I (this Journal, vol. 35 (1969), pp. 545–560). In Part I, the Church-Rosser property was deduced from abstract premises (A1)–(A8). The original draft of Part II contained some applications of this result, and a fairly simple abstract result by which the Church-Rosser property could be extended from λβ-reduction to λβη-reduction (Curry's notation [3, Chapter 3]). But since this draft was written, these results have been obtained independently and improved by other workers, and a simple and natural new proof for λβ-reduction has been discovered by W. W. Tait and P. Martin-Löf (see §11 later, and [17, §2.4.3]).So the main purpose of the present Part II is merely to justify the claim in Part I that the abstract theorem does cover the case of λβ-reduction (and various modifications). I shall also include a summary of the main kinds of Church-Rosser proofs. The paragraph and theorem numbers in Part II will continue from those of Part I.In §§5 and 6 below, Theorem 1 will be specialised to reductions defined by replacements of parts of expressions by others (Theorems 2 and 2A). At the end of §6 an important subclass of such reductions will be treated (Theorem 3).In §7, Theorem 3 will be applied to prove the Church-Rosser property for combinatory weak reduction [10, §11B], with or without type-restrictions and extra “arithmetical” reduction-rules (Theorems 4 and 5). (In the original draft Theorem 5 was deduced directly from Theorem 2A; the present intervening Theorem 3 is an independent result of B. Rosen [7].)
Some remarks on changing cofinalities
Authors: Devlin Keith J. 
Published: May 2006

AbstractIn [2], Prikry showed that if κ is a weakly inaccessible cardinal which carries a Rowbottom filter, then there is a Boolean extension of V (the universe), having the same cardinals as V, in which cf(κ) = ω. In this note, we obtain necessary and sufficient conditions which a filter D on κ must possess in order that this may be done.
A proof theoretic proof of Scott's general interpolation theorem
Authors: Africk Henry 
Published: May 2006

In [5] Scott asked if there was a proof theoretic proof of his interpolation theorem. The purpose of this paper is to provide such a proof, working with the first order system LK of Gentzen [2]. Our method is an extension of the one in Maehara [3] for Craig's interpolation theorem. We will also sketch the original model theoretic proof and show how Scott used his result to obtain a definability theorem of Svenonius [7].A language for LK contains the usual logical symbols: , ∧, ∨, ⊃, ∀, ∃; countably many free variables a0, a1, … and bound variables x0, x1, …; and some or all of the following nonlogical symbols: n-ary predicates ; n-ary functions ; and individual constants c0, c1, …. Semiterms are defined as follows: (1) Free variables, bound variables and individual constants are semiterms. (2) If f is an n-ary function and s1 …, sn are semiterms, then f(s1 …, sn), is a semiterm. A term is a semiterm that does not contain a bound variable. Formulas are defined as follows: (1) If R is an n-ary predicate and t1 …, tn are terms, then R(t1 …, tn) is a formula. (2) If A and B are formulas, then A, A ∧ B, A ∨ B and A ⊃ B are formulas. (3) If A(t) is a formula which has zero or more occurrences of the term t, and if x is a bound variable not contained in A(t), then ∀xA(x) and ∃xA(x) are formulas where A(x) is obtained from A(t) by substituting x for t at all indicated places.
Forcing for the impredicative theory of classes
Authors: Chuaqui Rolando 
Published: May 2006

The purpose of this work is to formulate a general theory of forcing with classes and to solve some of the consistency and independence problems for the impredicative theory of classes, that is, the set theory that uses the full schema of class construction, including formulas with quantification over proper classes. This theory is in principle due to A. Morse [9]. The version I am using is based on axioms by A. Tarski and is essentially the same as that presented in [6, pp. 250–281] and [10, pp. 2–11]. For a detailed exposition the reader is referred there. This theory will be referred to as .The reflection principle (see [8]), valid for other forms of set theory, is not provable in . Some form of the reflection principle is essential for the proofs in the original version of forcing introduced by Cohen [2] and the version introduced by Mostowski [10]. The same seems to be true for the Boolean valued models methods due to Scott and Solovay [12]. The only suitable form of forcing for found in the literature is the version that appears in Shoenfield [14]. I believe Vopěnka's methods [15] would also be applicable. The definition of forcing given in the present paper is basically derived from Shoenfield's definition. Shoenfield, however, worked in Zermelo-Fraenkel set theory.I do not know of any proof of the consistency of the continuum hypothesis with assuming only that is consistent. However, if one assumes the existence of an inaccessible cardinal, it is easy to extend Gödel's consistency proof [4] of the axiom of constructibility to .
A note on frame extensions
Authors: Hay Louise 
Published: May 2006

In [2] “recursive frames” were introduced as a means of extending relations R on the nonnegative integers to relations RΛ on the isols. In [1], this extension procedure was generalized by the introduction of “partial recursive frames”; the resulting extended relation on the isols was called RΛ. It was shown in [1] that the two extension procedures agree for recursive relations R, while RΛ ⊇ RΛ if R is . The case when R is , nonrecursive was left open. We show in this note that the extension procedures in fact agree for all relations R.In the following, the notation and terminology is that of [1] and [2].Theorem. If R ⊆ XκQ is a recursively enumerable (r.e.) relation, then RΛ = RΛ.Proof. Clearly RΛ ⊆ RΛ, since every recursive frame is partial recursive. To prove RΛ ⊆ RΛ, we give a uniform effective method for expanding any partial recursiveR-frame F to a recursiveR-frame G such that F ⊆ G, so that So let F be a (nonempty) partial recursive R-frame, with CF(α) generated by . Let Rn denote the result of performing n steps in a fixed recursive enumeration of R. If g(α) is a partial recursive function, “g(α) is defined in n steps” means that in whichever coding of recursive computations is being used, a terminating computation for g with argument α has length ≤ n.