bluuebunny/crossref_metadata_2025 huggingface dataset:
On Quine's axioms of quantification
Authors: Berry George D. W.
Published: May 2006

In his Mathematical logic, Quine adopts as axioms of quantification all statements specified by the first five of the six metatheorems listed below. The sixth serves as a rule of inference, and is the only primitive rule of inference used. The metatheorems in question are as follows:

The theme of the present paper is that *101 may be eliminated by means of an otherwise trivial shift in the meanings of *100, *102, *103, and *104.

In the statement of the above metatheorems and throughout the paper as a whole, we deviate from Quine's notational conventions only in using double quotes rather than corners and in using English letters rather than Greek ones as syntactical variables. Accordingly, ‘a’, ‘b’, and ‘d’ ambiguously denote variables ‘x’, ‘y’, ‘z’, and so on. The letters ‘p’ and ‘q’ ambiguously denote formulae, i.e. statements, and expressions which become statements when their contained free variables are supplanted by constants. Since we replace Quine's corners with double quotes, “(a)p” (for instance) is not the result of prefixing a parenthesized occurrence of the first letter of the alphabet to an occurrence of the sixteenth: “(a)p” is rather the result of prefixing any parenthesized variable a to any formula p.

Following Quine, we define the closure of p as p itself when p is a statement and as “(a1)(a2)…(an)p” where a1, a2, …, an are the sole variables free in p and where each ai is alphabetically prior to the corresponding ai+1.
The system LD
Authors: Curry Haskell B.
Published: May 2006

In lectures at Notre Dame University in 1948 I presented what was essentially a semantical analysis of the propositions formed from the elementary propositions of a formal system by compounding with propositional connectives and quantifiers. The system LD is one of the systems treated there in the chapter on negation. It is substantially the minimal calculus with excluded middle, and was first considered by Johansson. It corresponds semantically to the situation where we have refutability with completeness, and so it may be regarded as the natural system of strict implication. This paper gives the details of certain results concerning this system which have been reported elsewhere. Some related remarks concerning other systems will also be included. Acquaintance with the lectures cited is presupposed; they are referred to as TFD.
Leibniz's interpretation of his logical calculi
Authors: Rescher Nicholas
Published: May 2006

The historical researches of Louis Couturat saved the logical work of Leibniz from the oblivion of neglect and forgetfulness. They revealed that Leibniz developed in succession several versions of a “logical calculus” (calculus ratiocinatororcalculus universalis). In consequence of Couturat's investigations it has become well known that Leibniz's development of these logical calculi adumbrated the notion of a logistic system; and for these foreshadowings of the logistic treatment of formal logic Leibniz is rightly regarded as the father of symbolic logic.

It is clear from what has been said that it is scarcely possible to overestimate the debt which the contemporary student of Leibniz's logic owes to Couturat. This gratitude must, however, be accompanied by the realization that Couturat's own theory of logic is gravely defective. Couturat was persuaded that the extensional point of view in logic is the only one which is correct, an opinion now quite antiquated, and shared by no one. This prejudice of Couturat's marred his exposition of Leibniz's logic. It led him to battle with windmills: he viewed the logic of Leibniz as rife with shortcomings stemming from an intensional approach.

The task of this paper is a re-examination of Leibniz's logic. It will consider without prejudgment how Leibniz conceived of the major formal systems he developed aslogicalcalculi – that is, these systems will be studied with a view to the interpretation or interpretations which Leibniz himself intends for them. The aim is to undo some of the damage which Couturat's preconception has done to the just understanding of Leibniz's logic and to the proper evaluation of his contribution.
A definition of negation in extended basic logic
Authors: Fitch Frederic B.
Published: May 2006

In a previous paper it was shown that the system K of basic logic could be formulated in a simpler way owing to the fact that the proper ancestral could be defined in terms of the other concepts of that system. In the present paper analogous but more far-reaching results will be obtained for the system K′ of extended basic logic. In particular we will show that negation and the dual of the proper ancestral, as well as the proper ancestral itself, are definable in terms of the other concepts of K′. Hence, in order to define K′, we need to add only a single non-finitary rule to the rules used to define K. This rule was already among the rules originally used to define K′. It asserts that ‘Aa’ is in K′ if (and only if) every ‘b’ is such that ‘ab’ is in K′.

We will also show that a large class of non-finitary classes and relations are represented in K′, among which is K′ itself, just as all finitary syntactical classes and all finitary two- and three-place syntactical relations are represented in K, one of which is the finitary syntactical class K itself. The point is that K′ is adequate to handle the sort of transfinite induction that is essential in formulating K′, just as K is adequate to handle the ordinary finitary mathematical induction required in defining K′.
The recursive irrationality of π
Authors: Goodstein R. L.
Published: May 2006

A primitive-recursive sequence of rational numbers sn is said to be primitive-recursively irrational, if there are primitive recursive functions n(k), i(p, q) > 0 and N(p, q) such that:

1. (k)(n ≥ n(k) → ∣sn – sn(k)∣ < 2−k).

2. (p)(q)(q > 0 & n ≥ N(p, q) → ∣sn ± p/q∣ > 1/i(p, q)).

The object of the present note is to establish the primitive-recursive irrationality of a sequence which converges to π. In a previous paper we proved the primitive-recursive irrationality of the exponential series Σxn/n!, for all rational values of x, and showed that a primitive-(general-) recursively irrational sequence sn is strongly primitive-(general-)recursive convergent in any scale, where a recursive sequence sn is said to be strongly primitive-(general-)recursive convergent in the scale r (r ≥ 2), if there is a non-decreasing primitive-(general-) recursive function r(k) such that

,

where [x] is the greatest integer contained in x, i.e. [x] = i if i ≤ x < i + 1, [x] = —i if i ≤ —x < i+1, where i is a non-negative integer.

A rational recursive sequence sn is said to be recursive convergent, if there is a recursive function n(k) such that

.

If a sequence sn is strongly recursive convergent in a scale r, then it is recursive convergent and its limit is the recursive real number where, for any k ≥ 0,

.
On the theory of types
Authors: Quine W. V.
Published: May 2006

In this paper the theory of logical types will be examined, and certain departures from it will be suggested. Though the purpose of the paper is not primarily expository, an approach has been possible which presupposes no familiarity with special literature. Matters at variance with such an approach have been confined to appendices and footnotes.

In the early pages the logical paradoxes will be considered—an infinite series of them, of which Russell's paradox is the first. Then Russell's simple theory of types will be formulated, in adaptation to a minimal set of logical primitives: inclusion and abstraction. Two aspects of the theory will be distinguished: an ontological doctrine and a formal restriction. It will be found that by repudiating the former we can avoid certain unnatural effects of the type theory—notably the reduplication of logical constants from type to type, and the apparent dependence of finite arithmetic upon an axiom of infinity. But the formal restriction itself has unnatural effects, which survive, even in an aggravated form, after the type ontology has been dropped. A liberalization of the formal restriction will be proposed which removes the more irksome of these anomalies.
On the consistency of an axiom of enumerability
Authors: Beneš Václav Edvard
Published: May 2006

We prove the following theorem: If S is a consistent set of axioms for set theory, among whose consequences are the axioms of pairing and extensionality, and if S′ is the extension of S to all classes of sets of S, then S′ is consistent and remains so upon addition of an axiom expressing that the universal class has a well-ordering wherein every non-initial element has an immediate predecessor.

The basic idea will be use of the denumerable model of S guaranteed by the Skolem-Löwenheim theorem to obtain (i) a model of S′ in the domain of classes of natural numbers, and (ii) a correspondence between representatives (in the model of S′) of sets of S′ and natural numbers. One can then select a class of natural numbers in the model of S′ which will well-order (in the sense of the model of S′) the representatives of sets of S′ according to the numbers corresponding to them.

Specifically, let the formulas of S involve only one kind of variable and the sole predicate ‘ϵ’. The formulas of S′ can be thought of as identical with those of S; but the axioms of S′ will consist of (i) those of S with quantifiers restricted to sets by clauses ‘(∃z)[y ϵ z]’, (ii) those provided by the schema ‘(∃x) ▪ y ϵ x ≡y [(∃z)[y ϵ z] ▪ A]’, where ‘A’ is any formula of S′ in which ‘x is not free, and (iii) the axiom of extensionality.
Modality and description
Authors: Smullyan Arthur Francis
Published: May 2006

There are logicians who maintain that modal logic violates Leibniz's principle that if x and y are identical, then y has every property of x. The alleged difficulty is illustrated in the following example due to Quine.1

A. It is logically necessary that 9 is less than 10.

B. 9 = the number of the planets.

C. Therefore, it is logically necessary that the number of the planets is less than 10.
Set-theoretical basis for real numbers
Authors: Wang Hao
Published: May 2006

In [1] we have considered a certain system L and shown that although its axioms are considerably weaker than those of [2], it suffices for purposes of the topics covered in [2]. The purpose of the present paper is to consider the system L more carefully and to show that with suitably chosen definitions for numbers, the ordinary theory of real numbers is also obtainable in it. For this purpose, we shall indicate that we can prove in L a certain set of twenty axioms used by Tarski which are sufficient for the arithmetic of real numbers and are to the effect that real numbers form a complete ordered field. Indeed, we cannot prove in L all Tarski's twenty axioms in their full generality. One of them, stating in effect that every bounded class of real numbers possesses a least upper bound, can only be proved as a metatheorem which states that every bounded nameable class of real numbers possesses a least upper bound. However, all the other nineteen axioms can be proved in L without any modification.

This result may be of some interest because the axioms of L are considerably weaker than those commonly employed for the same purpose. In L variables need to take as values only classes each of whose members has no more than two members. In other words, only classes each with no more than two members are to be elements. On the other hand, it is usual to assume for the purpose of natural arithmetic that all finite classes are elements, and, for the purpose of real arithmetic, that all enumerable classes are elements.
Solution of a problem of Tarski
Authors: Myhill John
Published: May 2006

We presuppose the terminology of [1], and we give a negative answer to the following problem ([1], p. 19): Does every essentially undecidable axiomatizable theory have an essentially undecidable finitely axiomatizable subtheory?

We use the following theorem of Kleene ([2], p. 311). There exist two recursively enumerable sets α and β such that (1) α and β are disjoint (2) there is no recursive set η for which α ⊂ η, β ⊂ η′. By the definition of recursive enumerability, there are recursive predicates Φ and Ψ for which

We now specify a theory T which will afford a counter-example to the given problem of Tarski. The only non-logical constants of T are two binary predicates P and Q, one unary operation symbol S, and one individual constant 0. As in ([1], p. 52) we define

The only non-logical axioms of T are the formulae P(Δm, Δn) for all pairs of integers m, n satisfying Δ(m, n); the formulae Q(Δm, Δn) for all pairs of integers m, n satisfying Ψ(m, n); and the formula

T is consistent, since it has a model. It remains to show that (1) every consistent extension of T is undecidable (2) if T1 is a finitely axiomatizable subtheory of T, there exists a consistent and decidable extension of T1 which has the same constants as T1.
On predicates in algebraically closed fields
Authors: Robinson Abraham
Published: May 2006

Many properties of curves, surfaces, or other varieties in Algebraic Geometry can be formulated in the lower functional calculus as predicates of the coefficients of the polynomial or polynomials which define the variety (curve, surface) in question. For example, the property of a plane curve of ordernto possess exactlymdouble points, or the property to be of genusp— wheremandpare specified integers — can be formulated in this way. Similarly many statements on the relation between two or more varieties, e.g., concerning the number and type of their intersection points, can be expressed in the lower functional calculus. It is usual to study the properties of a variety in an algebraically closed field. Accordingly, it is of considerable interest to investigate the general structure of the class of predicates mentioned above in relation to algebraically closed fields. The following result will be proved in the present paper.

Main Theorem.LetFbe a commutative algebraic field of arbitrary characteristic, and letF′ = F[x1, …,xn]be the ring of polynomials of n variables with coefficients inF.With every predicate Q{x1, …,xn)which is formulated in the lower functional calculus in terms of the relations of equality, addition, and multiplication and (possibly) in terms of some of the elements ofF,there can be associated an ascending chain of ideals inF′,

such that

for every extensionF*ofFwhich is algebraically closed. In this formula, V0, …, V2k+ 1are the varieties of the ideals J1, …, J2k+iin the coordinate spaceSn: (x1, …xn) over F*, and VQis the set of points ofSnwhich satisfyQ.
Systems of modal logic which are not unreasonable in the sense of Halldén
Authors: McKinsey J. C. C.
Published: May 2006

Halldén, in [1], has recently pointed out that it is highly undesirable, in a system of sentential calculus, for there to exist two formulas α and β such that: (i) α and β contain no variable in common; (ii) neither α nor β is provable; (iii) α ∨ β is provable. We shall call a system unreasonable (in the sense of Halldén) if there exists a pair of formulas α and β having properties (i), (ii), and (iii). Halldén shows (in [1]) that the Lewis systems S1 and S3 are unreasonable in this sense; and that the same is true of any system which is between S1 and S3, as well as of every system which is stronger than S3 but weaker than both S4 and S7. In the present note we shall show that this defect does not occur in S4, nor in S5, nor in any “quasi-normal” extension of S5; we give an example, on the other hand, of an unreasonable system which lies between S4 and S5.

When we speak, in what follows, of a system of modal logic, we shall mean a system having the same class of well-formed formulas as have the various Lewis calculi. Thus the well-formed formulas of a system of modal logic, when written in unabbreviated form, are just those formulas which can be built up from sentential variables by use of the binary connective ‘·’ (conjunction sign), and the two unary connectives ‘˜’ (negation sign) and ‘◇’ (possibility sign). We shall, however, also make use of some of the defined signs of Lewis.
On the independence of the axioms of definiteness (Axiome der Bestimmtheit)
Authors: Robinsohn Abraham
Published: May 2006

The question of the independence of the axioms of the theory of sets has been dealt with in a number of works, although not in a final manner. The writer will be concerned solely with the axiomatic system of Zermelo and Fraenkel, and only with that feature of the system whereby all the objects of the underlying domain are sets (so that there is no difference between objects in general and sets in particular).

A special place among the axioms is occupied by a purely relational one, an axiom of definiteness, which establishes the character of equality within the system.

Zermelo introduces equality intensionally—if two symbolsxandyrepresent the same object, we write = (x, y). According to this there is no necessity for axioms to assure the interchangeability of equal objects as arguments of the primitive relationϵ( , ). For under the intensional interpretation it is clear that:

Similarly it is clear that there is no necessity for a separate axiom that will assure to equality the properties of an equivalence relation. Therefore Zermelo introduces only the followingaxiom of extensionality:

(if one set is a subset of another set, and the second set is also a subset of the first, then the two sets are equal).
A note on transfinite iteration
Authors: Schwarz Gideon
Published: May 2006

For some of the well-known set-theoretic operations a natural definition of transfinite iterations (powers) seems impossible. If, however, an operator D has the property that, for every X, D(X) ⊃ X, we may write the formula Dn(X) = D(Dn−1(X)) (which defines as usual the finite powers of D) in the form . Assuming this formula to be valid when n is any ordinal, we obtain a natural definition of transfinite powers of those operators. Obviously the dual definition would work in the case D(X) ⊂ X.

As an example of the use of this definition, we show how the sets used by von Neumann to represent ordinals can be constructed by means of the operator N(X) = X⋃{X}. Denoting the union of the elements of X by S(X), we have for the set E(ξ), which represents the ordinal ξ, E(ξ) = S(Nξ({ϕ})), as can easily be verified by transfinite induction. As the sets E(ξ) are different for different values of ξ, the powers of N are all different as well.

This is not always the case. The powers of certain operators start repeating themselves from a certain ordinal onward. If an operator has the property that, for every set A of sets a, , then the sequence of its powers becomes constant already from ω on. This is a special case of the following theorem.
The theory of truth tabular connectives, both truth functional and modal
Authors: Massey Gerald J.
Published: May 2006

Briefly, the following things are done in this paper. An informal exposition of the significance of partial truth tables in modal logic is presented. The intuitive concept of a truth tabular sentence connective is examined and made precise. From among a vast assortment of truth tabular connectives, the semantically well-behaved ones (called regular connectives) are singled out for close investigation. The familiar concept of functional completeness is generalized to all sets of regular connectives, and the functional completeness (or incompleteness) of selected sets of connectives is established. Some modal analogues of Sheffer's stroke are presented, i.e., single connectives are introduced which serve to define not only the truth functional connectives but all the regular modal connectives as well. The notion of duality is extended to all regular connectives and a general duality theorem is proved. Lastly, simplified proofs are given of several metatheorems about the system S5.
MIPC as the formalisation of an intuitionist concept of modality
Authors: Bull R. A.
Published: May 2006

In the course of a recent paper on modal' extensions of the intuitionist propositional calculus, [1], I made some suggestions as to the relationships between the system MIPC, the intuitionist predicate calculus, and the question of producing a genuine intuitionist concept of modality. This paper may be regarded as a clarification of those rather inaccurate ideas in the light of Kripke's outstanding analysis of the intuitionist predicate calculus, [2]. (I use Kripke's notation and terminology here without explanation — this work is intended to be read in conjunction with [2].) In particular, I shall adapt his interpretation of his modelling to give an account of MIPC in terms of differing mathematical intuitions.
Decision problems for multiple successor arithmetics
Authors: Thatcher J. W.
Published: May 2006

Let Nk denote the set of words over the alphabet Σk = {1, …, k}. Nk contains the null word which is denoted λ. We consider decision problems for various first-order interpreted predicate languages in which the variables range over Nk (k ≧ 2). Our main result is that there is no decision procedure for truth in the interpreted language which has the subword relation as its only non-logical primitive. This, together with known results summarized in Section 4, settles the decision problem for any language constructed on the basis of the relations and functions listed below.
The consistency of Leśniewski's mereology relative to the real number system
Authors: Clay Robert E.
Published: May 2006

It is known that Leśniewski constructed an interpretation of mereology in the real number system using binary expansions.2 Unfortunately, this construction is no longer extant. The following paper, except for a slight variation, is an attempt to reconstruct this interpretation.

Leśniewski probably considered sequences of 0's and I's (except for the sequence of all 0's) and defined a first sequence as an element of the second if every place in which the first has a I, so also does the second.
Elementary embeddings and infinitary combinatorics
Authors: Kunen Kenneth
Published: May 2006

One of the standard ways of postulating large cardinal axioms is to consider elementary embeddings,j, from the universe,V, into some transitive submodel,M. See Reinhardt–Solovay [7] for more details. Ifjis not the identity, andκis the first ordinal moved byj, thenκis a measurable cardinal. Conversely, Scott [8] showed that wheneverκis measurable, there is suchjandM. If we had assumed, in addition, that, thenκwould be theκth measurable cardinal; in general, the wider we assumeMto be, the largerκmust be.
On systems containing Aristotle's thesis
Authors: Routley R. , Montgomery H.
Published: May 2006

“Apart from merits or defects of PA1, however, its existence demonstrates the feasibility of a new approach to the logic of propositions involving the principle of subjunctive contrariety. We thus have good reason to investigate the effect this principle, and a concept of conditionality compatible with it, might exert if introduced into standard quantification theory, into set theory, into modal logic and into epistemology and the philosophy of science.”
Interpretations of Kleene's metamathematical predicate Γ ∣ a in intuitionistic arithmetic
Authors: Robinson T. Thacher
Published: May 2006

Let Pp, Pd, and N be the intuitionistic systems of prepositional calculus, predicate calculus, and elementary arithmetic, respectively, described in [3].

Kleene [4] introduces a metamathematical predicate Γ ∣ A for each of the systems Pp, Pd, and N, where Γ ranges over finite sequences of wffs, and A ranges over wffs, of that system. In the case of N, if Γ is consistent, then ‘ Γ ∣ A’ is essentially the result of deleting all references to recursive functions from the metamathematical predicate ‘A is realizable-(Γ ⊦)’ described in [3], pp. 502–503.

Through use of this predicate, Kleene [4] obtains elegant constructive proofs of the following results for N:

Metatheorem 0.1. If B ∨ C is a closed theorem of N, then ⊦ B or ⊦ C.

Metatheorem 0.2. If (∃a)D(a) is a closed theorem of N, then there is a numeral n such that ⊦D(n).

Metatheorem 0.3. If A is a closed wff of N, then A ∣ A is a necessary and sufficient condition that, for all closed B, C, (∃a)D(a) inN:

(0.3.1) ⊦ A ⊃ B ∨ C implies ⊦ A ⊃ B or ⊦A ⊃ C

and

(0.3.2) ⊦A ⊃ (∃)D(a) implies there is a numeral n such that ⊦ A ⊃ D(n).
Can there be no nonrecursive functions?
Authors: Moschovakis Joan Rand
Published: May 2006

In 1936 Alonzo Church proposed the following thesis: Every effectively computable number-theoretic function is general recursive. The classical mathematician can easily give examples of nonrecursive functions, e.g. by diagonalizing a list of all general recursive functions. But since no such function has been found which is effectively computable, there is as yet no classical evidence against Church's Thesis.

The intuitionistic mathematician, following Brouwer, recognizes at least two notions of function: the free-choice sequence (or ordinary number-theoretic function, thought of as the ever-finite but ever-extendable sequence of its values) and the sharp arrow (or effectively definable function, all of whose values can be specified in advance).
Reductibilities in intuitionistic topology
Authors: Van Dalen Dirk
Published: May 2006

In intuitionistic mathematics one distinguishes between sets with a constructive character and sets in a more general sense. The first kind consists of spreads and the latter of species. The definition of a spread utilizes so-called choice sequences (in [5] infinitely proceeding sequence or ips), i.e., sequences of well-determined mathematical objects which are chosen more or less freely. One can restrict the choices by some law, which, however, need not be predetermined (changing one's mind is allowed).
Lemmon-style bases for the systems S1°-S4°
Authors: Jay Zeman J.
Published: May 2006

In [1], Lemmon provides us with his now well-known formulations of the Lewis-modal systems S1 through S4. This paper will present similar bases for the related systems S1° and S2° of Feys [2], and S3° and S4° of Sobocinski [3]. Notation and definitions here will be as in [1]. Standard bases for the Lewis-modal systems may be drawn from the following stock of axioms and rules, as is done in [1].
A note on S5
Authors: Castaneda Hector-Neri
Published: May 2006

This is really a note to Wajsberg's [4].

In [3] J. C. C. McKinsey proved the following two completeness theorems: (1) theorem 6: If A is a wff of S2 with just r (proper or improper) sub-wffs, then A is provable in S2 iff A is satisfied by every normal S2-matrix with no more than 22r+1 elements; (2) theorem 13: if A is a wff of S4 with just r sub-wffs, then A is provable in S4 iff A is satisfied by every normal S4-matrix with no more than 22r elements. Now, a similar theorem has not been explicitly formulated for S5, even though a similar, even simpler, theorem has been almost at hand since Wajsberg's [4] was published in 1933, namely:

Theorem. If A is a wff of S5 with just n propositional variables, then A is provable in S5 iff A is satisfied by a normal SS-matrix with 22n elements.
Finite nest structures and propositional logic
Authors: Smullyan Raymond M.
Published: May 2006

Our terminology and notation is the same as that of [1], of which this note is a sequel.

We wish to show that if we take the natural deduction system (N) described in [1], and delete the rules for the quantifiers, we obtain a complete system for propositional logic. [Of course we now construe “X”, “Y”, “Z” as syntactic variables ranging over formulas of propositional logic, rather than sentences of quantification theory.] Moreover the system serves as a neat decision procedure.
Pure three-valued Łukasiewiczian implication
Authors: McCall Storrs , Meyer R. K.
Published: May 2006

The matrix defining Łukasiewicz's three-valued logic, constructed in 1920 and described at length in [1], is the following:

This matrix was axiomatized in 1931 by Wajsberg (see [6]), who showed that the following axioms together with the rules of substitution and modus ponens were sufficient:
On formalizing the distinction between logical and factual truth
Authors: Hanson William H.
Published: May 2006

Semantical systems that distinguish between logically true and factually true formulas are well-known from the work of Carnap. The present paper is concerned with extending the formalization of this distinction in two ways. First, we show how to construct syntactical (i.e., logistic) systems that correspond to semantical systems of the type just mentioned. Such a syntactical system for propositional logic is developed in section 3. Similar systems for first-order logic are sketched in section 5. Second, we show how to extend semantical systems that make the logical-factual distinction to languages containing modal connectives. Carnap's work on modal logic conspicuously lacks this feature. Section 4 contains such semantical systems for four well-known modal logics. It also contains a syntactical equivalent of one of these modal semantical systems.
On initial segments of hyperdegrees
Authors: Thomason S. K.
Published: May 2006

An initial segment of hyperdegrees is a set S of hyperdegrees such that whenever h ∈ S and k ≦ h then k ∈ S. The main results of this paper affirm the existence of initial segments having certain order types. In particular, if L is a finite distributive lattice then L is isomorphic to an initial segment of hyperdegrees [Theorem 1]; as a consequence the elementary theory of the ordering of hyperdegrees is recursively undecidable [Corollary 1].
Axiomatizable theories with few axiomatizable extensions
Authors: Martin D. A. , Pour-El M. B.
Published: May 2006

In this paper we prove two theorems. They answer questions raised by Myhill in 1956. (We recall the well-known fact that Myhill's invention of the maximal set in 1956 [2] stemmed from his attempt to prove I below.)

I. There exists an axiomatizable, essentially undecidable theory in standard formalization such that all axiomatizable extensions of are finite extensions.

II. There exists an axiomatizable but undecidable theory in standard formalization such that

(a) has a consistent, complete, decidable extension ,

(b) If is an axiomatizable extension of then either

(i) is a finite extension of , or

(ii) is a finite extension of .
The Meta-R.E. sets, but not the Π11 sets, can be enumerated without repetition
Authors: Owings James C.
Published: May 2006

In this paper we investigate the possibility of extending Friedberg's enumeration of the recursively enumerable (r.e.) sets without duplication [1, p. 312] to meta-recursion theory. It turns out that all of our proposed extensions are impossible save one: the metarecursively enumerable (meta-r.e.) sets can be enumerated without duplication, but only if all the recursive ordinals are used as indices (Theorems 1 and 2). The sets cannot be so enumerated, even if the index set is all recursive ordinals (Theorems 3 and 4). As a corollary, one proves there is no predicate P(n, x) with the property that for each set A there is exactly one integer n for which A = {x ∣ P(n, x)}. We also discuss enumerations of nonempty, infinite, and coinfinite and meta-r.e. sets.
Nonstandard theories of quantification and identity
Authors: Trew A.
Published: May 2006

In this paper a number of nonstandard systems of predicate logic with or without identity, are translated with subsystems of applied standard system of predicate logic with identity. There are nonstandard theories of quantification which, following [16], are described as inclusive systems; their theorems are valid in all domains, including the empty domain. Theories of quantification which allow for the substitution of denotationless terms for free variables, are described, following [21], as systems of free logic; they are said to be free of the requirement that all singular terms must have denotations. Free logics and inclusive logics may each be of the other type. A nonstandard theory of identity, described, following [12] as a theory of nonreflexive identity, may be combined with a standard or with a nonstandard theory of quantification. Another kind of nonstandard system of predicate logic examined is a nonstandard version of a system of monadic predicate logic in which a distinction is made between sentence and predicate negation, and which is nonstandard in the sense that the laws relating sentence and predicate negation diverge from the standard ones. In the systems examined, this is combined with an inclusive quantification theory.
The Lω1ω1-theory of hilbert spaces
Authors: Kopperman Ralph
Published: May 2006

It will be shown later in this paper that the class of all Hilbert spaces is not an elementary class (in the wider sense) in the lower predicate calculus. It is not difficult to find a type and a sentence in Lω1ω1 (of that type) whose models are precisely the Hilbert spaces (slightly altered to include in their domains the real or complex numbers).
Natural models of ackermann's set theory
Authors: Grewe Rudolf
Published: May 2006

In 1956 W. Ackermann proposed a new axiomatic set theory, that has received some attention in recent years. (See references [3], [4], [6], [7], and [9].) This theory distinguishes between sets and classes. In this paper we study mainly the natural models of this theory. We show, among other results, that the set-theoretical fragment of these models are also models of Zermelo-Fraenkel set theory. This result gives a partial answer to the question, raised by A. Levy, of the relative strength of Ackermann's set theory with respect of Zermelo-Fraenkel's.2
Separation principles in the hierarchy theory of pure first-order logic
Authors: Krom M. R.
Published: May 2006

This paper answers negatively the chief remaining open questions concerning the separation properties of first-order prefix classes of structures (discussed by Addison [2], pp. 26–37).

1. Preliminaries. The first and second separation properties and the reduction property are defined for arbitrary classes of subsets of an arbitrary set.
A theorem on hyperhypersimple sets
Authors: Martin Donald A.
Published: May 2006

Let be the class of recursively enumerable (r.e.) sets with infinite complements. A set M ϵ is maximal if every superset of M which is in is only finitely different from M. In [1] Friedberg shows that maximal sets exist, and it is an easy consequence of this fact that every non-simple set in has a maximal superset. The natural question which arises is whether or not this is also true for every simple set (Ullian [2]). In the present paper this question is answered negatively. However, the main concern of this paper is with demonstrating, and developing a few consequences of, what might be called the “density” of hyperhypersimple sets.
Remarks on some theorems of Keisler
Authors: Lindström Per
Published: May 2006

This paper is an appendix to Keisler's papers [3], [4]. We assume that the reader is fully acquainted with these papers and use their terminology without further explanation. One of the main tools in a number of proofs in [4] is the following result which is all but stated explicitly in [4].
A notion of effectiveness in arbitrary structures
Authors: Lambert W. M.
Published: May 2006

The well-developed theory of recursion has been applied to certain algebraic structures with countable universes to obtain interesting and natural results on the question of effective procedures in such structures ([2], [9], [10], [13]). It has also been applied to structures related to the real numbers, via approximations; we cite [3] as but one example. We are interested, however, in the problem of what operations in an arbitrary algebraic structure, possibly quite large and unnatural, can reasonably be considered “effective” in terms of the underlying operations and relations of the structure.
Many-valued logics of extended Gentzen style II
Authors: Takahashi Moto-o
Published: May 2006

In the monograph [1] of Chang and Keisler, a considerable extent of model theory of the first order continuous logic (that is, roughly speaking, many-valued logic with truth values from a topological space) is ingeniously developed without using any notion of provability.

In this paper we shall define the notion of provability in continuous logic as well as the notion of matrix, which is a natural extension of one in finite-valued logic in [2], and develop the syntax and semantics of it mostly along the line in the preceding paper [2]. Fundamental theorems of model theory in continuous logic, which have been proved with purely model-theoretic proofs (i.e. those proofs which do not use any proof-theoretic notions) in [1], will be proved with proofs which are natural extensions of those in two-valued logic.
The generalized continuum hypothesis is equivalent to the generalized maximization principle
Authors: Friedman Joel I.
Published: May 2006

In spite of the work of Gödel and Cohen, which showed the undecidability of the Generalized Continuum Hypothesis (GCH) from the axioms of set theory, the problem still remains to decide GCH on the basis of new axioms. It is almost 100 years since Cantor first conjectured the Continuum Hypothesis, yet we seem to be no closer to determining its truth (or falsity). Nevertheless, it is a sound methodological principle that given any undecidable set-theoretical statement, we should search for “other (hitherto unknown) axioms of set theory which a more profound understanding of the concepts underlying logic and mathematics would enable us to recognize as implied by these concepts” (see Gödel [7, p. 265]).
Many-one degrees associated with problems of tag
Authors: Hughes C. E.
Published: May 2006

Tag systems were defined by Post [9], [10] and have been studied by a number of researchers including Minsky [7], Maslov [6] and Aanderaa and Belsnes [1]. In their recent paper Aanderaa and Belsnes demonstrated that every r.e. many-one degree (exclusive of the degree of the empty set) is represented by the general halting problem for tag systems, that is, by the family of halting problems ranging over all tag systems. Their result depends upon an informal proof of this property for Turing machines but may be seen to be correct in light of a formal proof due to Overbeek [8]. Our aim is to extend their results to the general word problem for these systems. Specifically, we shall present an effective method which, when applied to an arbitrary r.e. set S, where S is neither empty nor the set of all natural numbers, produces a tag system R′ whose word and halting problems are both of the same many-one degree as the decision problem for S. The proof is realized by first constructing, from the description of an arbitrary Turing machine M, which machine has at least one mortal and one immortal configuration, a 5-register machine R, whose word and halting problems are both of the same many-one degree as the halting problem for M. From R we then construct the desired tag system R′. This construction combined with Overbeek's [8] shows that every r.e. many-one degree (exclusive of the degrees of the empty set and the set of all natural numbers) is represented by the general word and halting problems for tag systems. Moreover our results are seen to be best possible with regard to degrees of unsolvability in that it is not the case that every nonrecursive r.e. one-one degree is represented by either of the general decision problems for tag systems which are considered here. These results were first shown in the author's thesis [3] and were announced in [4], They form part of an extensive study into the many-one equivalence of general decision problems. An overview of the initial findings of this research project may be found in [5].
The diversity of quantifier prefixes
Authors: Keisler H. Jerome , Walkoe Wilbur
Published: May 2006

The Arithmetical Hierarchy Theorem of Kleene [1] states that in the complete theory of the standard model of arithmetic there is for each positive integer r a Σr0 formula which is not equivalent to any Πr0 formula, and a Πr0 formula which is not equivalent to any Πr0 formula. A Πr0 formula is a formula of the form

where φ has only bounded quantifiers; Πr0 formulas are defined dually.

The Linear Prefix Theorem in [3] is an analogous result for predicate logic. Consider the first order predicate logic L with identity symbol, countably many n-placed relation symbols for each n, and no constant or function symbols. A prefix is a finite sequence

of quantifier symbols ∃ and ∀, for example ∀∃∀∀∀∃. By a Q formula we mean a formula of L of the form

where v1, …, vr are distinct variables and φ has no quantifiers. A sentence is a formula with no free variables. The Linear Prefix Theorem is as follows.

Linear Prefix Theorem. Let Q and q be two different prefixes of the same length r. Then there is a Q sentence which is not logically equivalent to any q sentence.

Moreover, for each s there is a Q formula with s free variables which is not logically equivalent to any q formula with s free variables.

For example, there is an ∀∃∀∀∀∃ sentence which is not logically equivalent to any ∀∃∃∀∀∃ sentence, and vice versa. Recall that in arithmetic two consecutive ∃'s or ∀'s can be collapsed; for instance all ∀∃∀∀∀∃ and ∀∃∃∀∀∃ formulas are logically equivalent to Π40 formulas. But the Linear Prefix Theorem shows that in predicate logic the number of quantifiers in each block, as well as the number of blocks, counts.
On degrees of unsolvability and complexity properties
Authors: Marques Ivan
Published: May 2006

In this paper we present two theorems concerning relationships between degrees of unsolvability of recursively enumerable sets and their complexity properties.

The first theorem asserts that there are nonspeedable recursively enumerable sets in every recursively enumerable Turing degree. This theorem disproves the conjecture that all Turing complete sets are speedable, which arose from the fact that a rather inclusive subclass of the Turing complete sets, namely, the subcreative sets, consists solely of effectively speedable sets [2]. Furthermore, the natural construction to produce a nonspeedable set seems to lower the degree of the resulting set.

The second theorem says that every speedable set has jump strictly above the jump of the recursive sets. This theorem is an expected one in view of the fact that all sets which are known to be speedable jump to the double jump of the recursive sets [4].

After this paper was written, R. Soare [8] found a very useful characterization of the speedable sets which greatly facilitated the proofs of the results presented here. In addition his characterization implies that an r.e. degree a contains a speed-able set iff a′ > 0′.
Ordinal spectra of first-order theories
Authors: Schlipf John Stewart
Published: May 2006

The notion of the next admissible set has proved to be a very useful notion in definability theory and generalized recursion theory, a unifying notion that has produced further interesting results in its own right. The basic treatment of the next admissible set above a structure ℳ of urelements is to be found in Barwise's [75] book Admissible sets and structures. Also to be found there are many of the interesting characterizations of the next admissible set. For further justification of the interest of the next admissible set the reader is referred to Moschovakis [74], Nadel and Stavi [76] and Schlipf [78a, b, c].

One of the most interesting single properties of is its ordinal (ℳ). It coincides, for example, with Moschovakis' inductive closure ordinal over structures ℳ with pairing functions—and over some, such as algebraically closed fields of characteristic 0, without pairing functions (by recent work of Arthur Rubin) (although a locally famous counterexample of Kunen, a theorem of Barwise [77], and some recent results of Rubin and the author, show that the inductive closure ordinal may also be strictly smaller in suitably pathological structures). Further justification for looking at (ℳ) alone may be found in the above-listed references. Loosely, we can consider the size of to be a useful measure of the complexity of ℳ. One of the simplest measures of the size of —and yet a very useful measure—is its ordinal, (ℳ). Keisler has suggested thinking of (ℳ) as the information content of a model—the supremum of lengths of wellfounded relations characterizable in the model.
Sets equipollent to their power set in NF
Authors: Boffa Maurice
Published: May 2006

In this note we define a class of properties for which the following holds: If we can prove in NF that the property holds for the universe V, then we can prove in NF that it holds for every set equipollent to its power set.

Definition. For any stratified formula A and any variable υ which does not occur in A, let Aυ be the formula obtained by replacing in A each quantifier (Qx) by the bounded quantifier (Qx ∈ SCi(υ)), where i is the type of x in A. We will say that a property P(υ) is typed when there is a stratified sentence S such that P(υ) ↔ Sυ holds in NF.

Examples of typed properties are: “υ is Dedekind-infinite”, “υ is not well-orderable”. Specker [3] proved that these typed properties hold for the universe V, and C. Ward Henson [1] extended this result to any set equipollent to its power set. We will show that such an extension holds for any typed property.

Theorem. For any typed property P(υ):

Proof. Fix a bijective map h: υ → SC(υ) and define for i = 0, 1, 2, …, n, … a bijective map hi: υ → SCi(υ) as follows:

For every formula A, let A(h) be obtained by replacing in A each atomic part (x ∈ y) by (x ∈ h(y)) and each quantifier (Qx) by (Qx ∈ υ).
Projective algebra and the calculus of relations
Authors: Bednarek A. R. , Ulam S. M.
Published: May 2006

In [1] there were given postulates for an abstract “projective algebra” which, in the words of the authors, represented a “modest beginning for a study of logic with quantifiers from a boolean point of view”. In [5], D. Monk observed that the study initiated in [1] was an initial step in the development of algebraic versions of logic from which have evolved the cylindric and polyadic algebras.

Several years prior to the publication of [1], J. C. C. McKinsey [3] presented a set of postulates for the calculus of relations. Following the publication of [1], McKinsey [4] showed that every projective algebra is isomorphic to a subalgebra of a complete atomic projective algebra and thus, in view of the representation given in [1], every projective algebra is isomorphic to a projective algebra of subsets of a direct product, that is, to an algebra of relations.

Of course there has since followed an extensive development of projective algebra resulting in the multidimensional cylindric algebras [2]. However, what appears to have been overlooked is the correspondence between the Everett–Ulam axiomatization and that of McKinsey.

It is the purpose of this paper to demonstrate the above, that is, we show that given a calculus of relations as defined by McKinsey it is possible to introduce projections and a partial product so that this algebra is a projective algebra and conversely, for a certain class of projective algebras it is possible to define a multiplication so that the resulting algebra is McKinsey's calculus of relations.
Equality in
Authors: Seldin Jonathan P.
Published: May 2006

In [CLg. II, §15B6], the problem of representing equality in the system by means of an ob Q is discussed; it is shown there that if Q is taken to be a canonical atom of degree 2 and if the axiom scheme

is postulated, then it follows by Rule Eq that

and, if no other properties are postulated for Q, then the converse of (1), Q-consistency, also holds. However, it is also desirable to have, in addition, the property

at least for some obs Z, and the statement is made in [CLg. II, §15B6] that no known way of incorporating this principle existed (at the time this statement was written) in such a way that there was a proof of Q-consistency. In this paper it is shown that if Z is restricted to be a basic canob of degree 1, i.e., if Z is restricted to be a predicate of one argument, then a system in which (2) is postulated can be proved Q-consistent.

The notations and conventions of [CLg. II] especially §15B, will be used throughout the paper.