Search

An immune set is found such that the recursive equivalence type of its infinite subsets are universal in a very strong sense.

Our results concern the natural models of Ackermann-type set theories, but they can also be viewed as results about the definability of ordinals in certain sets.Ackermann's set theory A was introduced in [1] and it is now formulated in the first order predicate calculus with identity, using ∈ for membership and an individual constant V for the class of all sets. We use the letters ϕ, χ, θ, and χ to stand for formulae which do not contain V and capital Greek letters to stand for any formulae. Then, the axioms of A* are the universal closures ofwhere all the free variables are shown in A4 and z does not occur in the Θ of A2. A is the theory A* − A5.Most of our notation is standard (for instance, α, β, γ, δ, κ, λ, ξ are variables ranging over ordinals) and, in general, we follow the notation of [7]. When x ⊆ Rα, we use Df(Rα, x) for the set of those elements of Rα which are definable in 〈Rα, ∈〉, using a first order ∈-formula and parameters from x.We refer the reader to [7] for an outline of the results which are known about A, but we shall summarise those facts which are frequently used in this paper.

This paper is the third in a series collectively entitled Formal systems of intuitionistic analysis. The first two are [4] and [5] in the bibliography; in them I attempted to codify Brouwer's mathematical practice. In the present paper, which is independent of [4] and [5], I shall do the same for Bishop's book [1]. There is a widespread current impression, due partly to Bishop himself (see [2]) and partly to Goodman and the author (see [3]) that the theory of Gödel functionals, with quantifiers and choice, is the appropriate formalism for [1]. That this is not so is seen as soon as one really tries to formalize the mathematics of [1] in detail. Even so simple a matter as the definition of the partial function 1/x on the nonzero reals is quite a headache, unless one is prepared either to distinguish nonzero reals from reals (a nonzero real being a pair consisting of a real x and an integer n with ∣x∣ > 1/n) or, to take the Dialectica interpretation seriously, by adjoining to the Gödel system an axiom saying that every formula is equivalent to its Dialectica interpretation. (See [1, p. 19], [2, pp. 57–60] respectively for these two methods.) In more advanced mathematics the complexities become intolerable.

We give a number of simple proofs of results in model theory using the set theoretical result of Levy thatH(μ) is a Σ-submodel of the Universe.

Ackermann introduced in [1] a system of axiomatic set theory. The quantifiers of this set theory range over a universe of objects which we call classes. Among the classes we distinguish the sets. Here we shall show that, in some sense, all the theorems of Ackermann's set theory can be proved in Zermelo-Fraenkel's set theory. We shall also show that, on the other hand, it is possible to prove in Ackermann's set theory very strong theorems of the Zermelo-Fraenkel set theory.

A strongly implicit procedure is described which solves the system of 13 point finite difference equations associated with the biharmonic and similar fourth order elliptic equations. No factorization of the equation is required, and for the majority of problems, a universal set of iteration parameters provide rapid rates of convergence. In a comparison with another solution procedure for the biharmonic equation, the new method appears to reduce the computation required to about one-third.

This paper deals with a simple Geiger-Muller counter circuit, the essential feature of which is the application of a special characteristic curve of a pentode valve. This {ia, eg} curve has a saturation portion in the negative grid region. The output pulses from the circuit are equalized, free from secondary disturbances, and of shortened duration. By means of an appropriate resistance-capacity coupling to the thyratrons a back pulse is generated, so that the final pulse-shape is more suitable for triggering the thyratrons. A description of the simple pentode circuit is given and also of a universal set, consisting of four valves, which is suitable for coincidence counting. The special characteristic curve when applied to the coincidence circuit leads to improved discrimination between total and partial coincidences.

Let ZF be the usual Zermelo-Fraenkel set theory formulated without identity, and with the collection axiom scheme. Let ZF−-extensionality be obtained from ZF by using intuitionistic logic instead of classical logic, and dropping the axiom of extensionality. We give a syntactic transformation of ZF into ZF−-extensionality.Let CPC, HPC respectively be classical, intuitionistic predicate calculus without identity, whose only homological symbol is ∈. We use the ~ ~-translation, a basic tool in the metatheory of intuitionistic systems, which is defined byThe two fundamental lemmas about this ~ ~ -translation we will use areFor proofs, see Kleene [3, Lemma 43a, Theorem 60d].This - would provide the desired syntactic transformation at least for ZF into ZF− with extensionality, if A− were provable in ZF− for each axiom A of ZF. Unfortunately, the ~ ~-translations of extensionality and power set appear not to be provable in ZF−. We therefore form an auxiliary classical theory S which has no extensionality and has a weakened power set axiom, and show in §2 that the ~ ~-translation of each axiom of Sis provable in ZF−-extensionality. §1 is devoted to the translation of ZF in S.

In an earlier paper (Molecular Set Theory: I.Bull. Math. Biophysics,22, 285–307, 1960) the author proposed a “Molecular Set Theory” as a formal mathematical meta-theoretic system for representing complex reactions not only of biological interest, but also of general chemical interest. The present paper is a refinement and extension of the earlier work along more formal algebraic lines. For example the beginnings of an algebra of molecular transformations is presented. It also emphasizes that this development, together with the genetical set theory of Woodger's and Rashevsky's set-theoretic contributions to Relational Biology, points to the existence of a biomathematical theory of sets which is not deducible from the general mathematical, abstract theory of sets.

A constructive version of Morse set theory is given, based on Heyting's predicate calculus and with countable rather than full choice. An elaboration of the method of [5] is used to show that the theory is combinator-realizable in the sense defined there. The proof depends on the assumption of the syntactic consistency of the theory.The method is introduced by first treating a subtheory without countable choice of foundation.It is intended that the work can be read either classically or constructively, though whether the word constructive is correctly used as a description of either the theory or the metatheory is of course a matter of opinion.

The foundation of analysis does not require the full generality of set theory but can be accomplished within a more restricted frame. Just as for number theory we need not introduce a set of all finite ordinals but only a class of all finite ordinals, all sets which occur being finite, so likewise for analysis we need not have a set of all real numbers but only a class of them, and the sets with which we have to deal are either finite or enumerable.We begin with the definitions of infinity and enumerability and with some consideration of these concepts on the basis of the axioms I—III, IV, V a, V b, which, as we shall see later, are sufficient for general set theory. Let us recall that the axioms I—III and V a suffice for establishing number theory, in particular for the iteration theorem, and for the theorems on finiteness.

The most important thing for a set theory seems to be that it can generate new mathematical objects, and I think that there must be an underlying principle, simple and unique, which unifies the acts of generating. The naive set theory has a unique generating principle, which defines, by any proposition on a variablex, the set of allx’ssatisfying the proposition. Certainly, we must restrict this generating principle so as to exclude all contradictions it contains, without losing its essential rôle as logic of mathematics, and at the same time we would like to keep its uniqueness and simplicity.

We have still to consider the extension of the methods of number theory to infinite ordinals—or to transfinite numbers as they may also, as usual, be called.The means for establishing number theory are, as we know, recursive definition, complete induction, and the “principle of the least number.” The last of these applies to arbitrary ordinals as well as to finite ordinals, since every nonempty class of ordinals has a lowest element. Hence immediately results also the following generalization of complete induction, called transfinite induction: If A is a class of ordinals such that (1) ΟηA, and (2) αηA → α′ηA, and (3) for every limiting number l, (x)(xεl → xηA) → lηA, then every ordinal belongs to A.

1. Introduction and summary. The theory of hierarchies deals with the classification of objects according to some measure of their complexity. Such classifications have been fruitful in several areas of mathematics: analysis (descriptive set theory), recursion theory, and the theory of models. Although much of the hierarchy theory of each of these areas was developed independently of the others, Addison, in the series of papers [Ad 1-6], has shown not only that there are deep-seated analogies among these theories, but that indeed many of their results can be derived from those of a general theory of hierarchies. Toward a further consolidation of these theories, this paper will study the relationships and analogies between certain classical hierarchies of descriptive set theory and their counterparts in recursion theory. The roots of modern hierarchy theory lie in the investigations of Baire, Borel, Lebesgue, and others around the turn of the century. As analysts with a concern for the foundations of their subject, they felt that constructions effected by means of the axiom of choice or the set of all countable ordinals were less secure than those carried out by more elementary means. They sought to discover what role these suspect constructions played in analysis and whether or not they could be avoided altogether. Thus descriptive set theory arose with the goal of identifying, classifying, and studying those sets (of real numbers) which were of interest for analysis and for which an "explicit" construction could be given. Needless to say, there was vigorous disagreement as to just what constituted an explicit construction. The first large class of sets studied were the Borel sets. Since each Borel set can be constructed by iteration of the elementary operations of countable union and

This paper draws its title from the recent symposium of which it was part; it attempts to respond to the question raised by that title, taking current work in set theory into account. To this end the paper contrasts set theory with number theory, examines a severe brand of set-theoretic realism that is suggested by a passage from Gödel, and sketches a first-order way of looking at the results about competing extensions of Zermelo-Fraenkel set theory. A formalistic sentiment may be detectable in some portions of the paper.

Dedekind’s pigeon-hole principle, also known as the box argument or the chest of drawers argument (Schubfachprinzip) can be described, rather vaguely, as follows. If sufficiently many objects are distributed over not too many classes, then at least one class contains many of these objects. In 1930 F. P. Ramsey [12] discovered a remarkable extension of this principle which, in its simplest form, can be stated as follows. Let S be the set of all positive integers and suppose that all unordered pairs of distinct elements of S are distributed over two classes.

We examine n-dimensional complex varieties of fundamental type. We prove the existence of a universal set of algebraic deformations of a canonically polarized variety over a field of characteristic zero.

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

It is natural, given the usual iterative description of the universe of sets, to investigate set theories which in some way take account of the unfinished character of the universe. We do not here consider any arguments aimed at justifying one system over another, or at clarifying the basic philosophy. Rather, we look at an obvious candidate which is similar to a system discussed by L. Pozsgay in [1]. Pozsgay sketched the development of the ordinary theorems in such a system and attempted to show it equiconsistent with ZF. In this paper we show that the consistency of the system we call IZF can be proved in the usual ZF set theory.

The frequencies for the various numbers of charged secondaries emitted from $\mathrm{pp}$, ${\ensuremath{\pi}}^{\ifmmode\pm\else\textpm\fi{}}p$, $\mathrm{pn}$, ${\ensuremath{\pi}}^{\ifmmode\pm\else\textpm\fi{}}n$, and $\mathrm{nn}$ collisions from below production threshold to 27-BeV primary energy were found to define a single set of curves which can be expressed by a universal set of "multiplicity distribution functions" constructed from Poisson terms when conservation laws are suitably incorporated. The distribution functions so obtained contain no adjustable parameter and fit well the $\mathrm{NN}$ cosmic-ray jets at 100-250 BeV, the highest energy at which $\mathrm{NN}$ collision data are available. The $\ensuremath{\Lambda}K\ifmmode^\circ\else\textdegree\fi{}$ accompanying the pions produced by ${\ensuremath{\pi}}^{\ensuremath{-}}p$ were also found to follow the same distribution. The multiplicity regularity found points immediately to the existence of a number of nearly identical regions or "cells" inside the nucleon and the fireball.

In this paper evidence is presented for the Jakobsonian acoustic feature Grave. Data from African languages show that languages group labial and velar consonants + back vowels, and dental and palatal consonants + front vowels, into natural classes. Thus, this feature (discarded by Chomsky & Halle, 1968) must be reincorporated into the universal set of distinctive features used by languages.

In this note we shall prove a certain relative recursiveness lemma concerning countable models of set theory (Lemma 5). From this lemma will follow two results about special types of such models.Kreisel [5] and Mostowski [6] have shown that certain (finitely axiomatized) systems of set theory, formulated by means of the ϵ relation and certain additional non-logical constants, do not possess recursive models. Their purpose in doing this was to construct consistent sentences without recursive models. As a first corollary of Lemma 5, we obtain a very simple proof, not involving any formal constructions within the system of the notions of truth and satisfiability, of an extension of the Kreisel-Mostowski theorems. Namely, set theory with the single non-logical constant ϵ does not possess any recursively enumerable model. Thus we get, as a side product, an easy example of a consistent sentence containing a single binary relation which does not possess any recursively enumerable model; this sentence being the conjunction of the (finitely many) axioms of set theory.

We work in a Zermelo-Fraenkel set theory without the Axiom of Choice. In the appendix to his paper “Sur les ensembles finis”, Tarski proposed a finiteness criterion that we have called “C-finiteness”: a nonempty set is called “C-finite” if it cannot be partitioned into two blocks, each block being equivalent to the whole set. Despite the fact that this criterion can be shown to possess several features that are undesirable in a finiteness criterion, it has a fair amount of intrinsic interest. In Section 1 of this paper we look at a certain class of C-finite sets; in Section 2 we derive a few consequences from the negation of C-finiteness; and in Section 3 we show that not every C-infinite set necessarily possesses a linear ordering. Any unexplained notation is given in my paper, “Some definitions of finiteness”, Bull. Austral. Math. Soc. 5 (1971).

The omitting types theorem of infinitary logic is used to prove that every small Il set of analysis or any small T. set of set -theory is constructible. In what follows we could use either the omitting types theorem for infinitary logic or the same theorem for what Grilliot [2] calls (EA)-logic. I find the latter more appealing. Suppose 2 is a finitary logical language containing the symbols of set theory as well as a constant symbol a for each a in the transitive set A. For this language we will use only (EA)-models, that is to say, end extensions of the model (A, E). Corresponding to this restricted notion of model is a strengthened notion of proof, (EA)-logic. In addition to the usual finitary rules of proof, this logic contains rules Ra for each a in A. Rule Ra says "From b(b) for each b in a, you may conclude Vx e W x)." This logic satisfies bbth the completeness and omitting types theorems. If A is admissible and T is E on A, the predicate T FEA 0 is also on A. Proofs follow easily from the corresponding theorems of infinitary logic. A Ill set is small if it has no perfect subsets. Using the theorem that every set I' in the parameter a having a member not hyperarithmetic in a has a perfect subset, a number of people' have observed that every small set is contained in the set S defined as follows: a e S iff a is hyperarithmetic in every / with oGL < OJ)8 Here GL) is the first ordinal not recursive in a. It has also been observed that S = Q, where Q is the set of a which are constructible by stage o4L) in the constructible hierarchy. Since Q C L, in order to prove that no small Ill set has a nonconstructible element,2 Received by the editors June 15, 1973. AMS (MOS) subject classifications (1970). Primary 02K30.

Ackermann's set theory A* is usually formulated in the first order predicate calculus with identity, ∈ for membership and V, an individual constant, for the class of all sets. We use small Greek letters to represent formulae which do not contain V and large Greek letters to represent any formulae. The axioms of A* are the universal closures ofwhere all free variables are shown in A4 and z does not occur in the Θ of A2.A+ is a generalisation of A* which Reinhardt introduced in [3] as an attempt to provide an elaboration of Ackermann's idea of “sharply delimited” collections. The language of A+ is that of A*'s augmented by a new constant V′, and its axioms are A1–A3, A5, V ⊆ V′ and the universal closure ofwhere all free variables are shown.Using a schema of indescribability, Reinhardt states in [3] that if ZF + ‘there exists a measurable cardinal’ is consistent then so is A+, and using [4] this result can be improved to a weaker large cardinal axiom. It seemed plausible that A+ was stronger than ZF, but our main result, which is contained in Theorem 5, shows that if ZF is consistent then so is A+, giving an improvement on the above results.

We are concerned here with the set theory given in [1], which we call BL (Bernays-Levy). This theory can be given an elegant syntactical presentation which allows most of the usual axioms to be deduced from the reflection principle. However, it is more convenient here to take the usual Von Neumann-Bernays set theory [3] as a starting point, and to regard BL as arising from the addition of the schema where S is the formal definition of satisfaction (with respect to models which are sets) and ┌φ┐ is the Gödel number of φ which has a single free variable X.

All the ordinary mathematical systems are constructed in terms of sets. If we wish to study the reasoning used in mathematics, our model of mathematics must include some form of set theory, for otherwise our study must be restrictive. For example, Elementary Group Theory formalises almost nothing of group theory. The pervasive role of set theory in mathematics implies that any reasonable model of set theory will in effect contain a model of all of mathematics (including the mathematics of this book).

A Universal Logic Module (ULM) is a combinational logic module with m input terminals that is capable of realizing every n -variable switching function, n m , where function specialization is achieved by distributing the n variables, their complements, and the constants 0 and 1 freely among the m input terminals. Several methods for constructing ULM's are described in this chapter as well as formulas that show the dependency of m on n . In particular a lower bound for m is derived that shows that it grows as 2 n /log 2 n . An upper bound on m is obtained from the Preparata–Muller construction technique that yields modules for which m grows as 2 n /log 2 n , although the actual number of terminals is slightly greater than the number predicted by the lower bound. For small n , ULM's in three and four variables are given. The 3-variable ULM is known to have the minimum number of terminals while the 4-variable ULM is not known to be optimum. Related studies by Lechner, Yau, and Tang are also reported. Lechner's approach is to use a universal set of modules rather than a single module. Yau and Tang modify the basic ULM assumptions somewhat and allow terminal to terminal jumpers on their universal modules. Such modules have a number of terminals that approach 2 n / n asymptotically which is somewhat better than the Preparata–Muller modules. However, for n in the range of practical interest the Preparata–Muller modules have fewer terminals.