bluuebunny/crossref_metadata_2025_split huggingface dataset:
An improvement in the theory of simplicity
Authors: Goodman Nelson 
Published: May 2006

The present note suggests how the computation of complexity-values outlined in The logical simplicity of predicates may be so modified as to satisfy a more stringent requirement than was there imposed.By the method of computation described in that article, a basis consisting of two two-place predicates has in general the value 6. Any such basis may be replaced by one four-place predicate that is self-complete with respect to two of its places and also with respect to the remaining two. Such a predicate has but one “joint,” and therefore a value of 5. The consolidation of the two predicates into one thus results in a basis having a lower complexity-value. This does not violate the cardinal rule laid down in that article for testing proposed ways of assigning complexity-values; for, conversely, a four-place predicate that is self-complete in the way described can always be replaced by two two-place prediates. The rule requires a four-place predicate of the kind described to have a higher value than two two-place predicates only if replacement of two two-place predicates by such a four-place predicate is always possible, while replacement of such a four-place predicate by two two-place predicates is not.However, we might reasonably strengthen our cardinal rule for complexity-valuation by adding as a second requirement:If each basis of kind A is always replaceable by some basis of kind B, and each basis of kind B is always replaceable by some basis of kind A, then a basis of kind A and a basis of kind B must, in the absence of contrary indications, have the same complexity-value.
On the scope of the classical deduction theorem
Authors: Pogorzelski Witold A. 
Published: May 2006

§1. The set Cn(R, A + X) is the set of all expressions deducible, on the ground of formulas A, from the class X of formulas of the implicational propositional calculus, by means of rules belonging to the set R. In other words, Cn(R, A + X) is the set of expressions obtained from the set X by the help of a two-parameter function Cn[R, A]. The formula

is called the classical deduction theorem.The classical deduction theorem is true for the system 〈R, A〉 (where R is the set of primitive rules, A is the set of axioms of the propositional calculus) if it holds for the function Cn[R, A].
A note on recursive relations
Authors: Fitch Frederic B. 
Published: May 2006

Given a class U which is the result of closing a finite class of expressions with respect to a binary mode of combination, there exists, according to RFBL,1 a recursively enumerable subclass K* of U, and concepts of representation (5.3) and complete representation (6.2) such that:(a) A relation among members of U is recursively enumerable if and only if it is represented in K*. (6.7.)(b) A relation among members of U is recursive if and only if it is completely represented in K*. (6.10.)
Satisfaction for n-th order languages defined in n-th order languages
Authors: Craig William 
Published: May 2006

In this paper we show that for n-th order languages L′ with p nonlogical constants, 2 ≦ n < ω, 0 ≦ p < ω, a notion of satisfaction can be defined in an n-th order language containing one additional nonlogical constant, say S. By the usual methods we also show that this notion cannot be defined in L′. Hence, in its present formulation, Beth's Theorem in [1] for first order languages has no analogue for L′.Our defining expression is such that, given any values of the other nonlogical constants and any appropriate m-tuple, it allows us to determine whether or not the m-tuple belongs to the value S of S without considering the totality of objects which are of the same type as S. Whether every definition in an n-th order language is equivalent to one thus “predicative”, and hence whether there is a formulation of Beth's Theorem which generalizes to higher orders, we do not know.The falsehood for L′ of the analogue of Beth's Theorem implies the falsehood of an analogue of an interpolation theorem for first order languages. The above definability of satisfaction for L′ implies a result on finite axiomatizability in slightly richer languages. Details are given in § 4.
A reduction theorem for normal algorithms
Authors: Swanson J. W. 
Published: May 2006

Markov's [2] notion of Normal Algorithm (NA), with which we assume familiarity, is the simplest of the better known ways of expressing the concept of algorithmicity. An NA consists of an ordered finite list of replacement formulae
The dots in parentheses indicate that a given replacement formula may be either simple (P → Q), or terminal (P → .Q). No restrictions are imposed on the lengths of the Pi and Qi in the replacement formulae, and the only rule of order of application is a priority rule to the effect that of several replacement formulae applicable to a word W at a given step, the earliest one is used.
Note on a system of Åqvist
Authors: Cresswell M. J. 
Published: May 2006

In [1, pp. 82–84] L. Åqvist considers a modal system which he calls S3.5 obtained by adding to S3 the axiom ∼□p⊃□∼□p. This system becomes S5 when the rule ├A→├□A is added to it. S3.5 is put forward to stand to S5 as S3 stands to S4 and S2 to T. In this note we show how a natural extension of the modelling for S3 in [2] can give a suitable semantics for S3.5.1An S3 model2 is an ordered quadruple (GKRφ) where Κ is a set, G ε K and R is transitive and quasi-reflexive over K.
Binary connectives functionally complete by themselves in S5 modal logic
Authors: Massey Gerald J. 
Published: May 2006

This paper answers affirmatively the open question of Massey [1] concerning the existence of binary connectives functionally complete by themselves in two-valued truth tabular logic, i.e. in the modal theory S5. Since {∼, ⊃, ◊} is a functionally complete set of connectives (Massey [1, § 4]), the following definitions show that the binary operator ф, the semantics of which is given below, is functionally complete by itself:
It is left to the reader to verify, by means of complete sets of truth tables (see Massey [1, §§ 1 and 3]), that the foregoing definitions are correct.
Trees
Authors: Jech Thomas J. 
Published: May 2006

This is an attempt to give a survey of recent results concerning trees. The article is an extended version of our talk in Oberwolfach (Schwarzwald) last May; the forests surrounding the Forschungsinstitut turned out to be a good inspiration.A tree is a partially ordered set T = (T, ≤) such that for every x ∈ T, the set = {y ∈ T: y < x} is well-ordered. The order type of is called the order of x, o(x), and the length of T is sup {o(x) + 1: x ∈ T}; an α-tree (where α is an ordinal) is a tree of length α. The αth level of T is the set Uα of all elements of T whose order is α. T∣α is the union of all Uβ, β < α; its length is α. A tree (T2, ≤2) is called an extension of (T1, ≤1) if ≤1 = ≤2 ∩ (T1 × T1); T2 is on end-extension of (T1 if T1 = T2∣α for some α. A maximal linearly ordered subset of a tree T is called a branch of T; an α-branch is a branch of length α.
The foundations of Suslin logic
Authors: Ellentuck Erik 
Published: May 2006

LetLbe a first order logic andthe infinitary logic (as described in [K, p. 6] overL. Suslin logicis obtained fromby adjoining new propositional operatorsand. Letfrange over elements ofωωandnrange over elements of ω.Seqis the set of all finite sequences of elements of ω. If θ:Seq→is a mapping into formulas ofthenandareformulasofLA. Ifis a structure in which we can interpretandhis an-assignment then we extend the notion ofsatisfactionfromtoby definingwheref∣nis the finite sequence consisting of the firstnvalues off. We assume thathasωsymbols for relations, functions, constants, andω1variables. θ isvalid ifθ ⊧ [h] for everyhand isvalidif-valid for every. We address ourselves to the problem of finding syntactical rules (or nearly so) which characterize validity.
Separation principles and the axiom of determinateness
Authors: van Wesep Robert A. 
Published: May 2006

Let Γ be a class of subsets of Baire space (ωω) closed under inverse images by continuous functions. We say such a Γ is continuously closed. Let , the class dual to Γ, consist of the complements relative to ωω of members of Γ. If Γ is not selfdual, i.e., , then let . A continuously closed nonselfdual class Γ of subsets of ωΓ is said to have the first separation property [2] ifThe set C is said to separate A and B. The class Γ is said to have the second separation property [3] ifWe shall assume the axiom of determinateness and show that if Γ is a continuously closed class of subsets of ωω and then(1) Γ has the first separation property iff does not have the second separation property, and(2) either Γ or has the second separation property.Of course, (1) and (2) taken together imply that Γ and cannot both have the first separation property.
The theory of the Gödel functionals
Authors: Goodman Nicolas D. 
Published: May 2006

In [2] we described an arithmetic theory of constructions (ATC) and showed that first-order intuitionistic arithmetic (HA) could be interpreted in it. In [3] we went on to show that the interpretation of HA in ATC is faithful. The purpose of the present paper is to apply these ideas to intuitionistic arithmetic in all finite types. Tait has shown [6] that a conservative extension of HA is obtained by adding the Gödel functionals with intuitionistic logic and intensional identity in all finite types. Below we show that this extension remains conservative on the addition of certain axioms of choice which are evident on the intended interpretation of the intuitionistic logical connectives. This theorem (Corollary 6.2 below) was first obtained by a more complicated argument in our dissertation [1]. Some of its implications are discussed in Goodman and Myhill [4].We assume that the reader is familiar with [2] and [3].
The set theoretical foundations of nonstandard analysis
Authors: Phillips N. C. K. 
Published: May 2006

Nonstandard analysis was developed in [1] within a logic which has a language with finite types. In [2] and [3] the logic is first order and the language is that of set theory. The set theoretical approach can be described in the following setting.Let be a relational structure (A, ∈) where A is a nonempty set and ∈ is a restriction of the elementhood relation of set theory.Let Ext be the wf (∀x)[(∃w)[w ∈ x] → [(∀y)(∀z) [z ∈ x ↔ z ∈ y] → x = y]]. Call a fragment of set theory if ⊧ Ext. By forming a nontrivial ultrapower of one obtains a structure which, after canonically embedding in , becomes a proper elementary extension of .Let j embed canonically in . Let be the substructure (B′, ∈′) of where B′ is the ∈′-closure of j(A) in B. That is, B′ is the smallest subset of B containing j(A) such that if b ∈ B, b′ ∈ B′ and ⊧ b ∈ b′ then b ∈ B′.
Mitotic recursively enumerable sets
Authors: Ladner Richard E. 
Published: May 2006

A recursively enumerable (r.e.) set is mitotic if it is the disjoint union of two r.e. sets both of the same degree of unsolvability. A. H. Lachlan has shown in [3] that there exists a nonmitotic r.e. set. In this paper we make an initial investigation into the class of mitotic sets.The following results are proved, (i) An r.e. set is mitotic if and only if it is auto-reducible, (ii) There is a nonmitotic r.e. set of degree 0′, (iii) If d is an arbitrary non-recursive r.e. degree then there exists a nonmitotic r.e. set of degree ≤d. (iv) There exists a maximal set which is mitotic and a maximal set which is nonmitotic.Albert R. Meyer had independently proved (ii) and (iii) for nonautoreducible sets before (i) was known.
The pure part of HYP(ℳ)
Authors: Nadel Mark , Stavi Jonathan 
Published: May 2006

AbstractLet ℳ be a structure for a language ℒ on a set M of urelements. HYP(ℳ) is the least admissible set above ℳ. In §1 we show that pp(HYP(ℳ)) [= the collection of pure sets in HYP(ℳ)] is determined in a simple way by the ordinal α = ° (HYP(ℳ)) and the ℒxω theory of ℳ up to quantifier rank α. In §2 we consider the question of which pure countable admissible sets are of the form pp(HYP(ℳ)) for some ℳ and show that all sets Lα (α admissible) are of this form. Other positive and negative results on this question are obtained.
Definability problems for modules and rings
Authors: Sabbagh Gabriel , Eklof Paul 
Published: May 2006

This paper is concerned with questions of the following kind: let L be a language of the form Lαω and let be a class of modules over a fixed ring or a class of rings; is it possible to define in L? We will be mainly interested in the cases where L is Lωω or L∞ω and is a familiar class in homologic algebra or ring theory.In Part I we characterize the rings Λ such that the class of free (respectively projective, respectively flat) left Λ-modules is elementary. In [12] we solved the corresponding problems for injective modules; here we show that the class of injective Λ-modules is definable in L∞ω if and only if it is elementary. Moreover we identify the right noetherian rings Λ such that the class of projective (respectively free) left Λ-modules is definable in L∞ω.
The completeness theorem for infinitary logic
Authors: Mansfield Richard 
Published: May 2006

It will be proven that a set of sentences of infinitary logic is satisfiable iff it is proof theoretically consistent. Since this theorem is known to be false, it must be quickly added that an extended notion of model is being used; truth values may be taken from an arbitrary complete Boolean algebra. We shall give a Henkin style proof of this result which generalizes easily to Boolean valued sets of sentences.For each infinite candinal number κ the language Lκ is built up from a set of relation symbols together with a constant symbol cα and a variable υα for each α in κ. It contains atomic formulas and is closed under the following rules:(1) If Γ is a set of formulas of power < κ ∧ Γ is a set of formulas.(2) If φ is a formula, ¬ φ is also.(3) If φ is a formula and A Is a subset of κ of power < κ then Aφ is a formula.∧Γ is meant to be the conjunction of all the formulas in Γ, while Aφ is the universal quantification of all the variables υα for α in A. We let C denote the set of constant symbols in Lκ, the parameter κ must be discovered from the context.A model is identified with its truth function. Thus a model is a function mapping the sentences of Lκ into a complete Boolean algebra which satisfies the following conditions:
On nonregular ultrafilters
Authors: Ketonen Jussi 
Published: May 2006

In this paper we shall construct nonregular ultrafilters showing many of the model-theoretic properties of their regular counterparts. The crucial idea in these constructions is to replace the use of regularity by independent functions. We shall use the notation and terminology of [1], our fundamental concepts being defined as follows:Definition 1.1. (1) A uniform ultrafilter D over a cardinal κ is regular if there is a family {Xα ∣ α < κ} so that every infinite intersection of these Xα's is empty.(2) A filter F over a cardinal κ is ω1-saturated if there is no family of sets {aα ∣ α < ω1} so that for every α < β < ω1For more on regular ultrafilters, see [2]. The germinal theorem on the subject of nonregular ultrafilters is the following well-known result of Jack Silver:Theorem 1.2 [1, Theorem 1.39]. If F is an ω1-saturated κ-complete filter over κ, then any ultrafilter extending F is nonregular.This result will be the cornerstone of our constructions. Of course, the existence of a filter of the above type depends on large cardinal axioms. For more on un ω1-saturated κ-complete filters, see [1].
A noninitial segment of index sets
Authors: Hay Louise 
Published: May 2006

Let {Wk}k ≥ 0 be a standard enumeration of all recursively enumerable (r.e.) sets. If A is any class of r.e. sets, let θA denote the index set of A, i.e., θA = {k ∣ Wk ∈ A}. The one-one degrees of index sets form a partial order ℐ which is a proper subordering of the partial order of all one-one degrees. Denote by ⌀ the one-one degree of the empty set, and, if b is the one-one degree of θB, denote by the one-one degree of . Let . Let {Ym}m≥0 be the sequence of index sets of nonempty finite classes of finite sets (classified in [5] and independently, in [2]) and denote by am the one-one degree of Ym. As shown in [2], these degrees are complete at each level of the difference hierarchy generated by the r.e. sets. It was proved in [3] that, for each m ≥ 0,(a) am+1 and ām+1 are incomparable immediate successors of am and ām, and(b) .For m = 0, since Y0 = θ{⌀}, it follows from (a) that(c) .Hence it follows that(d) {⌀, , ao, ā0, a1, ā1 is an initial segment of ℐ.
Some relations between classical and constructive mathematics
Authors: Beeson Michael 
Published: May 2006

This paper is devoted to the general question, which assertions φ have the property,if φ is provable classically, then φ is(*) provable constructively.More generally, we consider the question, what is the “constructive content” of a given classical proof? Our aim is to formulate rules in a form applicable to mathematical practice. Often a mathematician has the feeling that there will be no difficulty constructivizing a certain proof, only a number of routine details; although it can be quite laborious to set them all out. We believe that most such situations will come quite easily under the scope of the rules given here; the metamathematical machinery will then take care of the details.This basic idea is not new; it has been discussed by Gödel and by Kreisel. Kreisel's investigations [Kr] were based on Herbrand's theorem; in unpublished memoranda he has also used Gödel's methods on some examples. These methods of Gödel (the double-negation and Dialectica interpretations) lie at the root of our work here. Previous work, however, has been limited to traditional formal systems of number theory and analysis. It is only recently that formal systems adequate to formalize constructive mathematics as a whole have been developed. Thus, for the first time we are in a position to formulate logical theorems which are easily applicable to mathematical practice. It is this program which we here carry out.Now that the work has been placed in some historical context, let us return to the main question: which φ have the property (*)? Upon first considering the problem, one might guess that any φ which makes no existential assertions (including disjunctions) should have the property (*).
Implicational formulas in intuitionistic logic
Authors: Urquhart Alasdair 
Published: May 2006

In [1] Diego showed that there are only finitely many nonequivalent formulas in n variables in the positive implicational propositional calculus P. He also gave a recursive construction of the corresponding algebra of formulas, the free Hilbert algebra In on n free generators. In the present paper we give an alternative proof of the finiteness of In, and another construction of free Hilbert algebras, yielding a normal form for implicational formulas. The main new result is that In is built up from n copies of a finite Boolean algebra. The proofs use Kripke models [2] rather than the algebraic techniques of [1].Let V be a finite set of propositional variables, and let F(V) be the set of all formulas built up from V ⋃ {t} using → alone. The algebra defined on the equivalence classes , by settingis a free Hilbert algebra I(V) on the free generators . A set T ⊆ F(V) is a theory if ⊦pA implies A ∈ T, and T is closed under modus ponens. For T a theory, T[A] is the theory {B ∣ A → B ∈ T}. A theory T is p-prime, where p ∈ V, if p ∉ T and, for any A ∈ F(V), A ∈ T or A → p ∈ T. A theory is prime if it is p-prime for some p. Pp(V) denotes the set of p-prime theories in F(V), P(V) the set of prime theories. T ∈ P(V) is minimal if there is no theory in P(V) strictly contained in T. Where X = {A1, …, An} is a finite set of formulas, let X → B be A1 →····→·An → B (ϕ → B is B). A formula A is a p-formula if p is the right-most variable occurring in A, i.e. if A is of the form X → p.
Some results in modal model theory
Authors: Mortimer Michael 
Published: May 2006

This paper is concerned with extending some basic results from classical model theory to modal logic.In §1, we define the majority of terms used in the paper, and explain our notation. A full catalogue would be excessive, and we cite [3] and [7] as general references.Many papers on modal logic that have appeared are concerned with (i) introducing a new modal logic, and (ii) proving a weak completeness theorem for it. Theorem 1, in §2, in many cases allows us to conclude immediately that a strong completeness theorem holds for such a logic in languages of arbitrary cardinality. In particular, this is true of S4 with the Barcan formula.In §3 we strengthen Theorem 1 for a number of modal logics to deal with the satisfaction of several sets of sentences, and so obtain a realizing types theorem. Finally, an omitting types theorem, generalizing the result for classical logic (see [5]) is proved in §4.Several consequences of Theorem 1 are already to be found in the literature. [2] gives a proof of strong completeness in languages of arbitrary cardinality of various logics without the Barcan formula, and [8] for some logics in countable languages with it. In the latter case, the result for uncountable languages is cited, without proof, in [1], and there credited to Montague. Our proof was found independently.
An intuitiomstic completeness theorem for intuitionistic predicate logic
Authors: Veldman Wim 
Published: May 2006

The problem of treating the semantics of intuitionistic logic within the framework of intuitionistic mathematics was first attacked by E. W. Beth [1]. However, the completeness theorem he thought to have obtained, was not true, as was shown in detail in a report by V. H. Dyson and G. Kreisel [2]. Some vague remarks of Beth's, for instance in his book, The foundations of mathematics, show that he sustained the hope of restoring his proof. But arguments by K. Gödel and G. Kreisel gave people the feeling that an intuitionistic completeness theorem would be impossible [3]. (A (strong) completeness theorem would implyfor any primitive recursive predicate A of natural numbers, and one has no reason to believe this for the usual intuitionistic interpretation.) Nevertheless, the following contains a correct intuitionistic completeness theorem for intuitionistic predicate logic. So the old arguments by Godel and Kreisel should not work for the proposed semantical construction of intuitionistic logic. They do not, indeed. The reason is, loosely speaking, that negation is treated positively.Although Beth's semantical construction for intuitionistic logic was not satisfying from an intuitionistic point of view, it proved to be useful for the development of classical semantics for intuitionistic logic. A related and essentially equivalent classical semantics for intuitionistic logic was found by S. Kripke [4].