bluuebunny/crossref_metadata_2025_split huggingface dataset:
Completeness in the theory of types
Authors: Henkin Leon 
Published: May 2006

The first order functional calculus was proved complete by Gödel in 1930. Roughly speaking, this proof demonstrates that each formula of the calculus is a formal theorem which becomes a true sentence under every one of a certain intended class of interpretations of the formal system.For the functional calculus of second order, in which predicate variables may be bound, a very different kind of result is known: no matter what (recursive) set of axioms are chosen, the system will contain a formula which is valid but not a formal theorem. This follows from results of Gödel concerning systems containing a theory of natural numbers, because a finite categorical set of axioms for the positive integers can be formulated within a second order calculus to which a functional constant has been added.By a valid formula of the second order calculus is meant one which expresses a true proposition whenever the individual variables are interpreted as ranging over an (arbitrary) domain of elements while the functional variables of degree n range over all sets of ordered n-tuples of individuals. Under this definition of validity, we must conclude from Gödel's results that the calculus is essentially incomplete.It happens, however, that there is a wider class of models which furnish an interpretation for the symbolism of the calculus consistent with the usual axioms and formal rules of inference. Roughly, these models consist of an arbitrary domain of individuals, as before, but now an arbitrary class of sets of ordered n-tuples of individuals as the range for functional variables of degree n. If we redefine the notion of valid formula to mean one which expresses a true proposition with respect to every one of these models, we can then prove that the usual axiom system for the second order calculus is complete: a formula is valid if and only if it is a formal theorem.
The elimination of contextually defined predicates in a modal system
Authors: Marcus Ruth Barcan 
Published: May 2006

In a recent note Bergmann states that “nonextensional languages may contain sentences from which contextually denned predicates are not eliminable.” A restatement of his argument is as follows. Suppose L is a functional calculus of fourth order. Included among the definitions occurring in L isLet ϕ occur in A (where A represents a well-formed formula of L) without an argument. The elimination of ϕ from A in accordance with (1) requiresThe proof of (2) depends on the principle of extensionalityHence Bergmann's conclusion “no such general elimination rule can be constructed for nonextensional languages.”
The M-valued calculus of non-contradiction
Authors: Rose Alan 
Published: May 2006

The 2-valued calculus of non-contradiction of Dexter has been extended to 3-valued logic. The methods used were, however, too complicated to be capable of generalisation to m-valued logics. The object of the present paper is to give an alternative method of generalising Dexter's work to m-valued logics with one designated truth-value. The rule of procedure is generalised in the same way as before, but the deductive completeness of the system is proved by applying results of Rosser and Turquette. The system has an infinite set of primitive functions, written n(P1, P2, …, Pr) (r = 1,2, …). With the notation of Post, n(P1, P2, …, Pr) has the same truth-value as ~(P1 & P2 & … & Pr). Thus n(P) is Post's primitive ~P, and we can define & byWe use n2(P1, P2, …, Pr) as an abbreviation for n(n(P1, P2, …, Pr)); similarly for higher powers of n. But if we set up the 1-1 correspondence of truth-values i ↔ m−i+1, then & corresponds to ∨ and ~m−1 corresponds to ~. Hence the functional completeness of our system follows from a theorem of Post.We define the functions N(P), N(P, Q) byThus the truth-value of N(P) is undesignated if and only if the truth-value of P is designated, and the truth-value of N(P, Q) is undesignated if and only if the truth-values of P and Q are both designated.
Proof of a conjecture of Goodman
Authors: Fine N. J. 
Published: May 2006

In Chapter X of The Structure of appearance the concept of linear array is given in terms of a two-place predicate “M” for matching. Also given in terms of “M” is the two-place predicate “B” for besideness. It is unnecessary to discuss here the formal definitions, since Goodman has proved that they are adequate to describe our presystematic ideas of linear array and besideness. Thus, we shall be concerned with a finite collection of elements with an assigned order satisfying:This order is not uniquely defined by the relation M; either of the two end points may be taken as the ‘first.’ We shall represent the order in diagrams by the convention that x is to the left of y if x < y. For x ≠ y, we shall define S(x, y), the distance between x and y, as one more than the number of elements strictly between them, in the order <; also, S(x, x) = 0. Thus S(x, y) = 1 if and only if x is beside y. The order is connected with the reflexive and symmetric matching relation M by the conditions(2) Bx, y ⊃ Mx, y,(3) Mx, y▪x ≤; u ≤ ν ≤ y▪ ⊃ ▪Mu, ν.Condition (3) is what Goodman calls the weak mapping rule. All arrays considered here must satisfy (3). To avoid trivial cases, we shall assume that not all elements match. There is a strong mapping rule,(4) Mx, y▪ ∼Mu, ν▪ ▪ ▪S(x, y) < S(u, ν),which it is desirable, but not necessary, for arrays to satisfy. An array which does satisfy (4) is called regular.
On notation for ordinal numbers
Authors: Kleene S. C. 
Published: May 2006

Consider a system of formal notations for ordinal numbers in the first and second number classes, with the following properties. Given a notation for an ordinal, it can be decided effectively whether the ordinal is zero, or the successor of an ordinal, or the limit of an increasing sequence of ordinals. In the second case, a notation for the preceding ordinal can be determined effectively. In the third case, notations for the ordinals of an increasing sequence of type ω with the given ordinal as limit can be determined effectively.Are there systems of this sort which extend farthest into the second number class? When the conditions for the systems have been made precise, the question will be answered in the affirmative. There is an ordinal ω1in the second number class such that there are systems of notations of the sort described which extend to all ordinals less than ω1, but none in which ω1itself is assigned a notation.1. An effective or constructive operation on the objects of an enumerable class is one for which a fixed set of instructions can be chosen such that, for each of the infinitely many objects (orn-tuples of objects), the operation can be completed by a finite process in accordance with the instructions. This notion is made exact by specifying the nature of the process and set of instructions. It appears possible to do so without loss of generality.
A homogeneous system for formal logic
Authors: Martin R. M. 
Published: May 2006

Two more or less standard methods exist for the systematic, logical construction of classical mathematics, the so-called theory of types, due in the main to Russell, and the Zermelo axiomatic set theory. In systems based upon either of these, the connective of membership, “ε”, plays a fundamental role. Usually although not always it figures as a primitive or undefined symbol.Following the familiar simplification of Russell's theory, let us mean by alogical typein the strict sense any one of the following: (i) the totality consisting exclusively of individuals, (ii) the totality consisting exclusively of classes whose members are exclusively individuals, (iii) the totality consisting exclusively of classes whose members are exclusively classes whose members in turn are exclusively individuals, and so on. Any entity from (ii) is said to beone type higherthan any entity from (i), any entity from (iii), one type higher than any entity from (ii), and so on. In systems based upon this simplified theory of types, the only significant atomic formulae involving “ε” are those asserting the membership of an entity in an entity one type higher. Thus any expression of the form “(x∈y)” is meaningless except where “y” denotes an entity of just one type higher than the type of the entity denoted by “x” It is by means of general type restrictions of this kind that the Russell and other paradoxes are avoided.
Independence of the primitive symbols of Lewis's calculi of propositions
Authors: Alban M. J. 
Published: May 2006

In this paper it will be shown that the three primitive symbols used by Lewis are independent in each one of his systems S1–S6.Lemma I. “·” is not definable in terms of “∼” and “◊” in any one of the systems S1–S6.Proof. This is obvious, since no binary operation can be defined by unary operations alone.Lemma II. “∼” is not definable in terms of “˙” and “◊” in any one of the systems S1–S5.
Recursive functions in basic logic
Authors: Fitch Frederic B. 
Published: May 2006

1.1 The system K* of basic logic, as presented in a previous paper, will be shown to be formalizable in an alternative way according to which the rule [E],is replaced by the rule [F],1.2. General recursive functions will be shown to be definable in K* in a way that retains functional notation, so that the equation,will be formalized in K* by the formula,where ‘f’, ‘p1’, … ‘pn’ respectively denote φ, x1, …, xn, and where ‘≐’ plays the role of numerical equality. Partial recursive functions may be handled in a similar way. The rule [E] is not required for dealing with primitive recursive functions by this method.1.3. An operator ‘G’ will be defined such that ‘[Ga ≐ p]’ is a theorem of K* if and only if ‘p’ denotes the Gödel number of ‘a’.1.4. In reformulating K* we assume ‘o0’, ‘o1,’ ‘o2’, …, have been so chosen that we can determine effectively whether or not a given U-expression is the mth member of the above series. The revised rules for K* are then as follows. (Double-arrow forms of these rules are derivable, except in the case of rule [V].)
A generalization of the antilogism
Authors: Dotterer Ray H. 
Published: May 2006

The Ladd-Franklin “antilogism” provides a very convenient procedure for testing syllogistic arguments, especially when they are expressed algebraically. It is well known, however, that the antilogism test indicates the invalidity of certain moods which the traditional logic regards as valid. These are the moods in which a particular conclusion is inferred from two universal premises. It is the aim of this paper to show that the antilogism can be generalized in such a way as to cover these moods, and also to be applicable to certain forms of “immediate inference” and “sorites,” as these designations have been traditionally employed.We shall find that when generalized in this fashion there are two principal kinds of antilogisms: (1) those which include an inequation of the form ab≠0, and (2) those which include an inequation of the form a≠0.Definition. An antilogism is a group of propositions so constructed that the contradictory of any one of them is implied by the logical product of the others.
A generalization of the concept of ω-consistency
Authors: Henkin Leon 
Published: May 2006

In this paper we consider certain formal properties of deductive systems which, in special cases, reduce to the property of ω-consistency; and we then seek to understand the significance of these properties by relating them to the use of models in providing interpretations of the deductive systems.The notion of ω-consistency arises in connection with deductive systems of arithmetic. For definiteness, let us suppose that the system is a functional calculus whose domain of individuals is construed as the set of natural numbers, and that the system possesses individual constants ν0, ν1, ν2, … such that νi functions as a name for the number i. Such a system is called ω-consistent, if there is no well-formed formula A(x) (in which x is the only free variable) such that A(ν0), A(ν1), A(ν2), … and ∼(x)A(x) are all formal theorems of the system, where A(νi) is the formula resulting from A(x) by substituting the constant νi for each free occurrence of the individual variable x.Now consider an arbitrary applied functional calculus F, and let Γ be any non-empty set of its individual constants. In imitation of the definition of ω-consistency, we may say that the system F is Γ-consistent, if it contains no formula A(x) (in which x is the only free variable) such that ⊦ A (α) for every constant α in Γ, and also ⊦ ∼(x)A(x) (where an occurrence of “⊦” indicates that the formula which it precedes is a formal theorem). We easily see that the condition of Γ-consistency is equivalent to the condition that the system F contain no formula B(x) such that ⊦ ∼ B(α) for each α in Γ, and also ⊦ (∃x)B(x).
Modalities in the Survey system of strict implication
Authors: Parry William Tuthill 
Published: May 2006

Professor C. I. Lewis, in Lewis and Langford's Symbolic logic, designates the system (S2) determined by the postulates used in Chapter VI—namely, 11.1–7 (B1–7) andas the system of strict implication. For certain reasons, he prefers it to either the earlier system (S3) determined by the stronger set of postulates of his Survey of symbolic logic, as emended, namely, A1–7 andor the system (S1) determined by the weaker set of postulates B1–7 or A1–7.But Lewis and others, following O. Becker, have also given consideration to systems which contain some additional principle effecting the reduction of complex modalities to simpler ones. Notable are the system (S4) determined by B1–7 pluswhich includes (is stronger than) S3; and the system (S5) determined by B1–7 pluswhich includes S4.It seems worth while to investigate further the system of the Survey (emended), S3, which is intermediate between S2 and S4. This is the purpose of the present paper. We first prove some additional theorems in S2 and S3. These enable us to reduce all the complex modalities in S3 to a finite number, viz. 42; and it is shown that no further reduction is possible. Finally, several systems which include S3 are considered.
A new approach to semantics – Part II
Authors: Kemeny John G. 
Published: May 2006

I will give precise versions of the foregoing verbal definitions, by formalizing them within a formal metalanguage.In order to avoid the necessity of formulating a meta-language, I will make use of VI 112, (i.e., Gödel's The consistency of the continuum hypothesis). Actually, the system there developed is unnecessarily strong for the limited purpose of this illustration. It will suffice to choose for the system of VI 112 without axioms C4 and E (axioms of replacement and choice); this system will be the logical basis of , and to this I will add some set-constants and some meaning postulates. The logical basis is roughly as strong as Zermelo's system with an axiom of infinity.Within I will set up analogues of the previous definitions, applicable to a wide variety of object-languages. For the sake of concreteness it will be convenient to think of as having Zermelo set theory, without the axiom of infinity, as its logical basis – but it must be kept in mind that this is not an essential feature of the forthcoming definitions.Our is certainly strong enough to have all primitive recursive functions calculable within it. This supplies us with the needed tool for talking about , within , by introducing a number of primitive recursive functions, properties, and relations describing the structure of . The exact definitions of these will depend on the exact form of , but for the forthcoming definitions it will suffice to know that these functions, properties, and relations are representable in for the given . This makes the resulting definitions most useful, since they can be applied to any of the type described.
Arithmetic with creative definitions by induction
Authors: Myhill John 
Published: May 2006

The purpose of this paper is to present a system of arithmetic stronger than those usually employed, and to prove some syntactical theorems concerning it.We presuppose the lower functional calculus with identity and functions, and we start with three of Peano's axioms.The other two (0 ϵ N and x ϵ N .⊃. x′ ϵ N) we do not need since our variables are anyhow restricted to natural numbers. Sometimes in the interest of a uniform notation for functions, we write Sx instead of x′.Next we have two axioms for μ (the smallest number such that) as follows.A third axiom for μ must wait until we have defined ≤.Now we introduce the central feature of the system, the following rule of definition.RD. Let Φ be a previously unused symbol. Then we can introduce it by a pair of definitions of the following form (n ≥ 0),where F(x1, …, xn) is a wff in which no symbol occurs which was not previously defined (in particular, not Φ), and in which no free variables occur other than x1, …, xn (and possibly not all of these), and G(x1, …, xn, y) is a wff in which no free variables occur other than x1, …, xn, y (and possibly not all of these), and in which no symbol occurs which was not previously defined, except that Φ may occur but only if its last argument is y.
A note on nominalism and recursive functions
Authors: Martin R. M. 
Published: May 2006

The purpose of this note is (i) to point out an important similarity between the nominalistic system discussed by Quine in his recent paper On universals and the system of logic (the system н) developed by the author in A homogeneous system for formal logic, (ii) to offer certain corrections to the latter, and (iii) to show that that system (н) is adequate for the general theory of ancestrale and for the definition of any general recursive function of natural numbers.Nominalism as a thesis in the philosophy of science, according to Quine, is the view that it is possible to construct a language adequate for the purposes of science, which in no wise admits classes, properties, relations, or other abstract objects as values for variables.
Extensions of some theorems of Gödel and Church
Authors: Rosser Barkley 
Published: May 2006

We shall say that a logic is “simply consistent” if there is no formula A such that both A and ∼ A are provable. “ω-consistent” will be used in the sense of Gödel. “General recursive” and “primitive recursive” will be used in the sense of Kleene, so that what Gödel calls “rekursiv” will be called “primitive recursive.” By an “Entscheidungsverfahren” will be meant a general recursive function ϕ(n) such that, if n is the Gödel number of a provable formula, ϕ(n) = 0 and, if n is not the Gödel number of a provable formula, ϕ(n) = 1. In specifying that ϕ must be general recursive we are following Church in identifying “general recursiveness” and “effective calculability.”First, a modification is made in Gödel's proofs of his theorems, Satz VI (Gödel, p. 187—this is the theorem which states that ω-consistency implies the existence of undecidable propositions) and Satz XI (Gödel, p. 196—this is the theorem which states that simple consistency implies that the formula which states simple consistency is not provable). The modifications of the proofs make these theorems hold for a much more general class of logics. Then, by sacrificing some generality, it is proved that simple consistency implies the existence of undecidable propositions (a strengthening of Gödel's Satz VI and Kleene's Theorem XIII) and that simple consistency implies the non-existence of an Entscheidungsverfahren (a strengthening of the result in the last paragraph of Church).
Finite combinatory processes—formulation
Authors: Post Emil L. 
Published: May 2006

The present formulation should prove significant in the development of symbolic logic along the lines of Gödel's theorem on the incompleteness of symbolic logics and Church's results concerning absolutely unsolvable problems.We have in mind a general problem consisting of a class of specific problems. A solution of the general problem will then be one which furnishes an answer to each specific problem.In the following formulation of such a solution two concepts are involved: that of a symbol space in which the work leading from problem to answer is to be carried out, and a fixed unalterable set of directions which will both direct operations in the symbol space and determine the order in which those directions are to be applied.In the present formulation the symbol space is to consist of a two way infinite sequence of spaces or boxes, i.e., ordinally similar to the series of integers …, − 3, − 2, − 1, 0, 1, 2, 3, …. The problem solver or worker is to move and work in this symbol space, being capable of being in, and operating in but one box at a time. And apart from the presence of the worker, a box is to admit of but two possible conditions, i.e., being empty or unmarked, and having a single mark in it, say a vertical stroke.
Constructibility as a criterion for existence
Authors: Rosser Barkley 
Published: May 2006

Problems of construction have engaged the attention of mathematicians from the earliest times. The three famous unsolved problems of the Greeks were problems of construction. Apparently the attitude of the Greeks toward these problems was that, if a geometric entity exists, it must be constructible. For example they believed that given an arbitrary angle, there is another one equal to a third of the first. Hence there must be a way of constructing the second angle, that is, a way of trisecting the first angle. This attitude is very similar in formulation but vastly different in content from the attitude of the modern intuitionists, who say that a mathematical entity does not exist unless it is constructible. Had Brouwer been a Greek, he would probably have declared that, given an angle, it is non-sense to speak of another angle equal to a third of it until such a second angle has been constructed.However, it seems scarcely necessary to remind the reader that, for the Greeks, constructibility meant a special kind of constructibility, namely, constructibility by ruler and compass. Other methods of constructing geometric entities are known, and by use of them, the problems of the Greeks can be solved. More than that, it is now known that ruler and compass constructions alone do not suffice to solve any one of the three famous problems of the Greeks. Therefore, we see that the Greeks erred in restricting themselves to ruler and compass constructions, even though they may have felt justified in making these restrictions, due to considerations of mathematical elegance, or to ignorance of other methods.
Universally free logic and standard quantification theory
Authors: Meyer Robert K. , Lambert Karel 
Published: May 2006

Interest has steadily increased among logicians and philosophers in versions of quantification theory which meet the following criteria: (1) no existence assumptions are made with respect to individual constants, and (2) theorems are valid in every domain including the empty domain. Logics meeting the former of these criteria are called free logics by Lambert and have been investigated in a series of papers by him and by van Fraassen, and by Leblanc and Thomason.1Although it is natural to impose (2) in the presence of (1), the criteria are independent.2 Hence we baptize logics which meet both criteria universally free.