bluuebunny/crossref_metadata_2025 huggingface dataset:
Existence of classes and value specification of variables
Authors: Wang Hao
Published: May 2006

In mathematics, when we want to introduce classes which fulfill certain conditions, we usually prove beforehand that classes fulfilling such conditions do exist, and that such classes are uniquely determined by the conditions. The statements which state such unicity and existence of classes are in mathematical logic consequences of the principles of extensionality and class existence. In order to illustrate how these principles enable us to introduce classes into systems of mathematical logic, let us consider the manner in which Gödel introduces classes in his book on set theory.

For instance, before introducing the definition of the non-ordered pair of two classes

Gödel puts down as its justification the following two axioms:

By A4, for every two classesyandzthere exists at least one non-ordered pairwof them; and by A3,wis uniquely determined in A4.
m-valued sub-system of (m + n)-valued propositional calculus
Authors: Hoo Tzu-Hua
Published: May 2006

An (m + n)-valued propositional calculus2 may happen to be a subsystem of an m-valued propositional calculus , though the converse is never true. This fact may give us the impression that, as m grows, the content of becomes meagre. The present treatment is intended to remove this impression by constructing a complete, m-valued sub-system of any (m + n)-valued propositional calculus.

In the following we adopt the customary, autonymous mode of speech according to which symbols belonging to the object calculi or languages are used in the syntactic language as names for themselves, and juxtaposition serves to denote juxtaposition.

2.1 = df stands for definational identity in the syntactic language.

2.11 ≡ stands for definational identity in the object calculi.

2.2 ∊, ⊂, ∩, {x1, …, xn} are used in their meanings as customarily employed in the theory of sets—∊ for class membership, ⊂ for proper inclusion, ∩ for the product operation of classes, {x1, …, xn} for the class with x1, …, xn as its only elements.

2.3 x, y, z are used as unspecified natural numbers including 0. m, n, i, j are used as unspecified natural numbers other than 0.

2.401 Definition. δ = df as the function of two variables defined for any x, y such that

2.41 Definition. For m ≧ 2, ιm = df the function of two variables denned on the set {0, …, m − 1} such that ιm (x, y) = y − x for x ≦ y and ιn(x, y) = 0 for x > y.
The formalization of mathematics
Authors: Wang Hao
Published: May 2006

Zest for both system and objectivity is the formal logician's original sin. He pays for it by constant frustrations and by living ofttimes the life of an intellectual outcaste. The task of squeezing a large body of stubborn facts into a more or less rigid system can be a painful one, especially since the facts of mathematics are among the most stubborn of all facts. Moreover, the more general and abstract we get, the farther removed we are from the raw mathematical experience. As intuition ceases to operate effectively, we fall into many unexpected traps. The formal logician gets little sympathy for his frustrations. He is regarded as too rigid by his philosophical colleagues and too speculative by his mathematical friends. The life of an intellectual outcaste may be a result partly of temperament and partly of the youthfulness of the logic profession. The unfortunate lack of wide appeal of logic may, however, be prolonged partly on account of the fact that very little of the well-established techniques of mathematics seems applicable to the treatment of serious problems of logic.

The axiomatic method is well suited to provide results which are both exact and systematic. How attractive would it be if we could get an axiom system in which all the axioms and deductions were intuitively clear and all theorems of mathematics were provable? Such a system would undoubtedly satisfy Descartes who admits solely intuition and deduction, which are, for him, the only “mental operations by which we are able, wholly without fear of illusion, to arrive at the knowledge of things.” Indeed, according to Descartes, intuition and deduction “are the most certain routes to knowledge, and the mind should admit no others. All the rest should be rejected as suspect of error and dangerous.”
Distributivity and an axiom of choice
Authors: Collins George E.
Published: May 2006

In this paper a theorem will be established which states that a particular axiom of choice is equivalent to complete distributivity of union and intersection. The theorem will be formulated and proved in the system of logic of [4]. In addition to definitions of [4], the following will be used.

In terms of these definitions, the theorem can be formulated as follows.

The dual of this statement, obtained by interchanging I and U, is also a theorem and has a similar proof.
The consistency of the ramified Principia
Authors: Fitch Frederic B.
Published: May 2006

When the axioms of infinity and choice are added to the system of logic of the second edition of Whitehead and Russell's Principia mathematica, and when, as in the second edition, the axiom of reducibility is omitted (so that the ramified nature of Russell's theory of types, especially his distinction between “orders,” is not in effect obliterated), the resulting system will hereafter be referred to as “the ramified Principia.” It will be shown that a certain system S, slightly stronger than the ramified Principia, is consistent, so that the ramified Principia itself is consistent. From Gödel's theorem it will then follow that the sort of mathematical induction employed in the consistency proof of S cannot be adequately handled within S or within the ramified Principia.

The method of proving the consistency of S will be roughly as follows: A consistent non-constructive system S′ will be defined by means of induction with respect to a serial well-ordering of all the propositions of S. It will then be shown that every true proposition of S is a true proposition of S′, so that S must also be consistent.

1. Preliminary conventions.

1.1. Definition. By a “symbol” is to be understood any typographical expression which does not consist of a horizontal collinear sequence of expressions. Expressions formed by adding indices to either of the two upper or two lower corners of a symbol will also be considered symbols.
On the number of complete extensions of the Lewis systems of sentential calculus
Authors: McKinsey J. C. C.
Published: May 2006

We say that a system S of sentential calculus is an extension of a system R, if R and S have the same class of (meaningful) sentences, and every provable sentence of R is also provable in S. If the two classes of provable sentences do not coincide, we call S a proper extension of R.

By a complete system of sentential calculus is meant one which is itself consistent, but has no consistent proper extensions. Thus one cannot add a new independent primitive sentence to a complete system without obtaining an inconsistent system. The usual two-valued sentential calculus is complete in the sense defined.

It has been shown by Lindenbaum that every incomplete system of sentential calculus possesses at least one complete extension. In this paper we shall examine how many complete extensions there are of some of the Lewis systems of sentential calculus. We shall show that there is only one complete extension of S4 (and hence also of S5, which is an extension of S4), and that there are infinitely many complete extensions of S2 (and hence also of S1, since S2 is an extension of S1). We leave open the question how many complete extensions there are of S3.
Proof of the independence of the primitive symbols of Heyting's calculus of propositions
Authors: McKinsey J. C. C.
Published: May 2006

In this paper I shall show that no one of the four primitive symbols of Heyting's calculus of propositions is definable in terms of the other three. So as to make the paper self-contained, I begin by stating the rules and primitive sentences given by Heyting.

The primitive symbols of the calculus are “⅂”, “∨”, “∧”, and “⊃”, which may be read, respectively, as “not,” “either…or,” “and,” and “if…then.” The symbol “⊃⊂”, which may be read “if and only if,” is defined in terms of these as follows:

The rule of substitution is assumed, and the rule that S2 follows from S1 and S1⊃S2; in addition it is assumed that S1∧S2 follows from S1 and S2. The primitive sentences are as follows:
The hypothesis that infinite classes are similar
Authors: Fitch Frederic B.
Published: May 2006

Let “the hypothesis of similarity” be the hypothesis that all infinite classes are similar (have the same power or cardinal number). It will be shown that the system of logic of Whitehead and Russell's Principia mathematica (without the axiom of reducibility) is consistent when to its axioms are added all the following:

(1). The hypothesis of similarity.

(2). The axiom of infinity.

(3). The axiom of choice.

(4). The contradictory of the axiom of reducibility.

If (2) – (4) but not (1) are employed in Principia, it must therefore be the case that Cantor's theorem is not deducible, since it contradicts (1). If (2) and (3) but not (1) and (4) are employed, then a proof of Cantor's theorem must require the use of some sort of reducibility principle.

The first step in the required consistency proof is to modify in certain respects the system S of a previous paper. Immediately after definition 3.5 the following definition is to be added:

3.5.1. If a is of the form (b,c), where x is an S-variable and where b and c are S-constants neither of which is of higher order than that of x, then a is an S-proposition.
Arithmetical representation of recursively enumerable sets
Authors: Robinson Raphael M.
Published: May 2006

A set S of natural numbers is called recursively enumerable if there is a general recursive function F(x, y) such that

In other words, S is the projection of a two-dimensional general recursive set. Actually, it is no restriction on S to assume that F(x, y) is primitive recursive. If S is not empty, it is the range of the primitive recursive function

where a is a fixed element of S. Using pairing functions, we see that any non-empty recursively enumerable set is also the range of a primitive recursive function of one variable.

We use throughout the logical symbols ⋀ (and), ⋁ (or), → (if…then…), ↔ (if and only if), ∧ (for every), and ∨(there exists); negation does not occur explicitly. The variables range over the natural numbers, except as otherwise noted.

Martin Davis has shown that every recursively enumerable set S of natural numbers can be represented in the form

where P(y, b, w, x1 …, xλ) is a polynomial with integer coefficients. (Notice that this would not be correct if we replaced ≤ by <, since the right side of the equivalence would always be satisfied by b = 0.) Conversely, every set S represented by a formula of the above form is recursively enumerable. A basic unsolved problem is whether S can be defined using only existential quantifiers.
On ω-inconsistency and a so-called axiom of infinity
Authors: Quine W. V.
Published: May 2006

The purpose of the present paper is to dispel such mystery as may be traceable to use of the ill-chosen term ‘ω-inconsistency’ and to a certain application of the term ‘axiom of infinity’. The application of ‘axiom of infinity’ which I have in mind is made by Rosser in his penetrating studies of the system of my New foundations. Let me begin with a synopsis of that system, which I shall call NF.

NF assumes as primitive just the membership connective ‘ϵ’, the truth functions, and quantification over a single style of variables ‘x’, ‘y’, etc. without type distinctions. The axioms, superimposed on standard quantification theory, comprise the axiom of extensionality ‘(x)(x ϵ y · = · x ϵ z) · y ϵ w · ⊃· z ϵ w’ and the axioms of abstraction, these latter being all sentences of the form ‘(∃y)(x)(x ϵ y · = Fx)’ in which the sentence supplanting ‘Fx’ is stratified (i.e., adaptable to type theory by some assignment of types to variables).
Some proofs of independence in axiomatic set theory
Authors: Mendelson Elliott
Published: May 2006

1. Gödel's theorem that sufficiently strong formal systems cannot prove their own consistency and Tarski's method for constructing truth-definitions can be combined to give several independence results in axiomatic set theory. In substance, the following theorems can be obtained: (a) The existence of inaccessible ordinals is not provable from the axioms of set theory, if these axioms are consistent, (b) The axiom of infinity is independent of the other axioms, if these other axioms are consistent, (c) The axiom of replacement is independent of the other axioms, if these other axioms are consistent. In all cases, V = L will be included as an axiom.

The result (a) concerning inaccessible ordinals already has been proved in Shepherdson [10] and Mostowski [6], but their proofs are somewhat different from the one given here. According to Mostowski [6], Kuratowski essentially had a proof of (a) in 1924. Propositions (b) and (c) have been proved, for axiomatic set theory without the axiom V = L, by Bernays [1] pp. 65–69. The method of proof used in this paper is due to Firestone and Rosser [2].

An outline of a similar proof along these lines is given in Rosser [7] pp. 60–62.

As our system G of set theory, we choose Gödel's system A, B, C, as given in [4], except for the following changes.
A further consistent extension of basic logic
Authors: Fitch Frederic B.
Published: May 2006

1.1. In two previous papers a consistent theory of real numbers has been outlined by the author, using a system K′. This latter system is an extension of a system K, which is “basic” in the sense that every finitary (recursively enumerable) subclass of its well-formed expressions is in a certain sense represented in it. The system L described below is a further extension of K. The system K′ lacks two important features possessed by L: a symbol for a special kind of implication (or “conditionality”) and a symbol for the modal concept “necessity.” The presence of the implication symbol, and the additional assumptions that go with it, make available in L various kinds of restricted universal quantification not available in K′, for example, universal quantification restricted to the real numbers of the author's theory of real numbers.

1.2. If ‘~[a & ~a]’ is a theorem of L, then the proposition expressed by ‘a’ may be said to L-satisfy the principle of excluded middle. I t is always the case that ‘a’ L-satisfies the principle of excluded middle (or rather that the proposition expressed by ‘a’ does so) if and only if ‘a’ or ‘~a’ is a theorem of L. An example of a proposition that does not L-satisfy the principle of excluded middle is that expressed by ‘’, namely the proposition that asserts that the class of classes that are not members of themselves is a member of itself.
A note on nominalistic syntax
Authors: Martin R. M.
Published: May 2006

In this note two independent comments are offered concerning nominalistic syntax.

If one has a nominalistic theory of natural numbers (or positive integers) at one's disposal, one can of course readily formulate a nominalistic syntax by the familiar method of arithmetization. A nominalistic theory of natural numbers is formulated in a previous paper by the author, and thus a basis for a nominalistic syntax is already provided. (The objection that this theory is infinitistic would appear without force, because it provides the only known nominalistic basis for the theory of general recursive functions. On a finitistic basis one merely throws out this vital domain of mathematical theory.)

The second comment is concerned with nominalistic syntax as formulated by Goodman and Quine. The nominalistic construction of natural numbers alluded to above owes much of its power to a primitive device of ancestral quantification. This device is somewhat more powerful than the notions Goodman and Quine allow themselves. Now nominalistic syntax in their somewhat narrower sense can be formulated by utilizing a relation akin to the relation L of the theory of ordered individuals developed elsewhere by the author. ‘L’ here is to designate the relation between inscriptions of being wholly to the left of.

The Goodman-Quine primitive ‘C’, designating a relation of concatenation, and their primitive ‘Part’ with its field confined to inscriptions, can be defined in terms of ‘L’. Thus:

.

(This definition is essentially that of ‘P’ in O.I.)
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.
Modifications of Quine's ML and inclusive quantification systems
Authors: Goe George
Published: May 2006

In a paper that was written some time ago but appeared only recently [1], I indicated that Quine's system of quantification in [2], as well as his inclusive system of [3] can be modified so as to make it possible to prove *119 of [2] by another method than the one discovered by Berry. The reason originally given in [1, p. 136] for preferring the modified systems was wrong. (See [1, p. 158] for correction of previous remark.) But, at the cost of a slight complication of one of the axiom schemata, a considerable simplification of the proof of *119 is achieved in the modified systems, by dispensing with the use of *115 and *117 as intermediaries.
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.)
A system of implicit quantification
Authors: Jay Zeman J.
Published: May 2006

The “traditional” method of presenting the subject-matter of symbolic logic involves setting down, first of all, a basis for a propositional calculus—which basis might be a system of natural deduction, an axiom system, or a rule concerning tautologous formulas. The next step, ordinarily, consists of the introduction of quantifiers into the symbol-set of the system, and the stating of axioms or rules for quantification. In this paper I shall propose a system somewhat different from the ordinary; this system has rules for quantification and is, indeed, equivalent to classical quantification theory. It departs from the usual, however, in that it has no primitive quantifiers.
S3(S) = S3.5
Authors: Rennie M. K.
Published: May 2006

In this note a proof is supplied of a fairly easily-made conjecture: that the system S3.5, formulated by Åqvist in [1] and proved complete with respect to some Kripke-style semantics by Cresswell in [2], is indeed the same system as S3(S), formulated by Lemmon in [3]. Any otherwise unexplained terms and notation are taken from the latter two papers.
Implicit definability and infinitary languages
Authors: Kunen Kenneth
Published: May 2006

In this paper we define the notions of invariant implicit definability (i.i.d.) and semi-invariant implicit definability (s.i.i.d.) on ε-models, A, of a certain weak set theory. These notions are intended to be the analogs of recursiveness and recursive enumerability, respectively. Following Barwise, with each A is associated an infinitary language whose formulas are elements of A.
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.
A cornucopia of minimal degrees
Authors: Sasso Leonard P.
Published: May 2006

The first minimal degree construction is due to Spector [7]. To this Sacks [5] has added the priority method of Friedberg [1] and Muchnik [4] to obtain a minimal degree less than 0′. Sacks' methods have been modified in several directions to obtain minimal degrees satisfying various incomparability conditions.
Finite sets in Quine's new foundations
Authors: Ward Henson C.
Published: May 2006

In this paper we consider some axiomatic systems of set theory related to the system NF (New Foundations) of Quine. In particular we discuss the possible relations of cardinality between a finite set x and its subset class SC(x) = {y | y ∩ x} and also between x and its unit set class USC(x) = {{y} | y ε x}. Specker [5] has shown that in NF the cardinal of a finite set x can never be the same as the cardinal of SC(x).
Nonfinitizability of classes of representable cylindric algebras
Authors: Donald Monk J.
Published: May 2006

Cylindric algebras were introduced by Alfred Tarski about 1952 to provide an algebraic analysis of (first-order) predicate logic. With each cylindric algebra one can, in fact, associate a certain, in general infinitary, predicate logic; for locally finite cylindric algebras of infinite dimension the associated predicate logics are finitary. As with Boolean algebras and sentential logic, the algebraic counterpart of completeness is representability. Tarski proved the fundamental result that every locally finite cylindric algebra of infinite dimension is representable.
Bases and α-dimensions of countable vector spaces with recursive operations
Authors: Hamilton Alan G.
Published: May 2006

This paper is based on the notions originally described by Dekker [2], [3], and the reader is referred to these for explanation of notation etc. Briefly, we are concerned with a countably infinite dimensional countable vector space Ū with recursive operations, regarded as being coded as a set of natural numbers. Necessarily, then, Ū must be a vector space over a field which itself is in some sense recursively enumerable and has recursive operations.
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.1

An 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 α.
A minimal pair of Π10 classes
Authors: Jockusch Carl G. , Soare Robert I.
Published: May 2006

A pair of sets (A0, A1) forms a minimal pair if A0 and A1 are nonrecursive, and if whenever a set B is recursive both in A0 and in A1 then B is recursive. C. E. M. Yates [8] and independently A. H. Lachlan [4] proved the existence of a minima] pair of recursively enumerable (r.e.) sets thereby establishing a conjecture of G. E. Sacks [6]. We simplify Lachlan's construction, and then generalize this result by constructing two disjoint pairs of r.e. sets (A0, B0) and (A1B1) such that if C0 separates (A0, A1 and C1 separates (B0, B1), then C0 and C1 form a minimal pair. (We say that C separates (A0, A1) if A0 ⊂ C and C ∩ = ∅.) The question arose in our study of (Turing) degrees of members of certain classes, where we proved the weaker result [2, Theorem 4.1] that the above pairs may be chosen so that C0 and C2 are merely Turing incomparable. (There we used a variation of the weaker result to improve a result of Scott and Tennenbaum that no complete extension of Peano arithmetic has minimal degree.)
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 defining

wheref∣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] if

The set C is said to separate A and B. The class Γ is said to have the second separation property [3] if

We 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.
Construction of models from groups of permutations
Authors: Benda Miroslav
Published: May 2006

In [3] we have associated to a structure an ordinal which gives us information about elementary substructures of the structure. For example a structure whose ascending chain number (as we call the ordinal) is ω could be called Noetherian since all ascending elementary chains inside it are finite (and there are arbitrarily large finite chains). Theorem 2 shows that such structures exist. In fact we prove that for any α < ω1 there is a structure whose ascending chain number is α. The construction is based on the existence of a certain group of permutations of ω (see Theorem 1). The second part of this paper deals with the relevance of the chain number to the study of Jonsson algebras.
The pure part of HYP(ℳ)
Authors: Nadel Mark , Stavi Jonathan
Published: May 2006

Let ℳ 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 α < β < ω1

For 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].
The positive properties of isolic integers
Authors: Ellentuck Erik
Published: May 2006

In this paper we show (cf. Theorem 22) that in a language L* with equality, whose relation symbols denote arbitrary relations over ω* (=rational integers) and whose function symbols denote (= ∃∀ definable in the arithmetic hierarchy) functions over ω*, (i) a positive sentence is true in Λ* (= isolic integers) iff some Horn reduct is true in ω* with Skolem functions. We also show (cf Theorem 20) that (ii) a universally quantified sentence is true in Λ* iff some Horn reduct is true in Λ*.The latter result is nontrivial because our relations are arbitrary and our functions are In order to obtain (i) it was necessary to generalize the frame extensions of [7]. This is done in §2. Our extension procedure agrees with that of [7] for recursive relations (cf. Theorem 12), and is certainly more general for − relations. What happens in the case is still open. In §3 we develop the basic properties of our extension so that in §4 we can prove a metatheorem (cf. Theorems 8 and 10) about Λ (=isols), in a language L with equality whose relation symbols denote arbitrary relations over ω (=nonnegative integers) and whose function symbols denote almost R↑ combinatorial functions. In Theorem 11 this is generalized to infinitary universal sentences. In §5 generic isols are introduced. These are used (cf. Theorems 16–19) to generalize and simplify the “fundamental lemma” of [8]. The basic induction is patterned after Lemma 4.1 of [8], but is stronger in that any sufficiently generic assignment attainable from a frame yields Skolem functions. Finally in §6 these results are applied to Λ*, yielding the titled result (i) of our paper. Immediately following Theorem 15 there is a discussion which attempts to justify the way we extend relations to Λ.
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 setting

is 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 imply

for 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].