Mathematical Logic in the 20th Century

The following sections are included:

• Introduction

• Contents

This is the first of two notes in which we outline a proof of the fact that the Continuum Hypothesis cannot be derived from the other axioms of set theory, including the Axiom of Choice. Since Gödel³ has shown that the Continuum Hypothesis is consistent with these axioms, the independence of the hypothesis is thus established. We shall work with the usual axioms for Zermelo-Fraenkel set theory,² and by Z-F we shall denote these axioms without the Axiom of Choice, (but with the Axiom of Regularity). By a model for Z-F we shall always mean a collection of actual sets with the usual ε-relation satisfying Z-F. We use the standard definitions³ for the set of integers ω, ordinal, and cardinal numbers…

This paper is a continuation of reference 1, in which we began a proof of the fact that the Continuum Hypothesis cannot be derived from the other axioms of set theory, including the Axiom of Choice. We use the same notation as employed in reference 1.

The following sections are included:

• Introduction

• The approach

• Fine structure lemmas

• The non ω cofinal case

• Vicious sequences

• The ω cofinal case

• Bibliography

In this paper we shall prove three theorems about recursively enumerable sets. The first two answer questions posed by Myhill [1].

The three proofs are independent and can be presented in any order. Certain notations will be common to all three. We shall denote by “R_e” the set enumerated by the procedure of which e is the Gödel number. In describing the construction for each proof, we shall suppose that a clerk is carrying out the simultaneous enumeration of R₀, R₁, R₂,…, in such a way that at each step only a finite number of sets have begun to be enumerated and only a finite number of the members of any set have been listed. (One plan the clerk can follow is to turn his attention at Step a to the enumeration of R_e where e + 1 is the number of prime factors of a. Then each R_e receives his attention infinitely often.) We shall denote by “R_e^a” the set of numbers which, at or before Step a, the clerk has listed as members of R_e. Obviously, all the R_e^a are finite sets, recursive uniformly in e and a. For any a we can determine effectively the highest e for which R_e^a is not empty, and for any a, e we can effectively find the highest member of R_e^a, just by scanning what the clerk has done by Step a. Additional notations will be introduced in the proofs to which they pertain.

The following sections are included:

• Introduction

• Section 1

• Section 2

• Section 3

• Section 4

• References

The following sections are included:

• SYSTEMS OF DENOTATIONS

• DILATORS

• THE ALGEBRAIC THEORY OF DILATORS

• DILATORS AS WELL-ORDERED CLASSES

• Λ AND TRADITIONAL PROOF-THEORY

• β-PROOFS

• INDUCTIVE LOGIC

• APPLICATIONS TO GENERALIZED RECURSION

• DESCRIPTIVE SET-THEORY

• BIBLIOGRAPHY

If M is an arbitrary domain of things in which a binary relation ε is defined, call “propositional function over M” any expression φ containing (besides brackets) only the following symbols: 1. Variables x, y …. whose range is M. 2. Symbols a₁ … a_n denoting² individual elements of M (referred to in the sequel as “the constants of φ”). 3. ε. 4. ∼ (not), ∨ (or). 5. Quantifiers for the above variables x, y …^* Denote by M′ the set of all subsets of M defined by prop. funct. φ(x) over M. Call a function f with s variables a “function in M” if for any elements x₁ … x_s of Mf(x₁ … x_s) is defined and is an element of M…

We give a proof of the geometric Mordell-Lang conjecture, in any characteristic. Our method involves a model-theoretic analysis of the kernel of Manin's homomorphism and of a certain analog in characteristic p.

The following sections are included:

• Introduction

• Basic Notions

• Invariants

• Applications

The following sections are included:

• Primitive recursive functions

• Alterations of quantifiers

• Partial and general recursive functions

• Construction of indices

• Reduction of the inductive definition of {z}(a) ≃ w to an explicit definition

• Reduction in type of a quantifier

• Predicates of order r

• μ-recursiveness versus general recursiveness

• Bibliography

The following sections are included:

• Introduction

• Formulation of the problem

• The priority tree and the construction

• Properties of the construction

• Verification of Propositions 1 to 10

• References

The following sections are included:

• Introduction

• Definitions

• The determinateness of analytic sets

• Further results

• What games are determined?

• References

Hilbert's tenth problem has the following formulation (cf. [1]):

Specify a procedure which in a finite number of steps enables one to determine whether or not a given diophantine equation with an arbitrary number of indeterminates and with rational integer coefficients has a solution in rational integers…

The following sections are included:

• Introduction

• Preliminaries

• Transcendence in rank

• Results depending on Ramsey's theorem

• Models of totally transcendental theories

• Saturated models and categoricity in power

• References

The following sections are included:

• A hyperanalytic function not recursive in any

• Functions recursive in a type-3 object

• The hyperanalytic hierarchy

• Minimum functions

• Predicates r.e. in ³E

• Normal forms for predicates r.e. in ³E

• An extension of the hyperanalytic hierarchy

• Comments on results for types other than 3

• Bibliography

The following sections are included:

• Introduction

• Functional Representation of Partial Recursive Operators
  • Sequences and Quasisequences
  • Functional Representation of Operators
  • A Universal Partial Recursive Operator
  • The Calculus of M-problems

• Decision Problems of Recursively Enumerable Sets
  • The Semilattice
  • Post's Reducibility Problem

• BIBLIOGRAPHY

The following sections are included:

• Introduction

• Recursive versus recursively enumerable sets

• A form of Gödel's theorem

• The complete set K; creative sets

• One-one reductibility, to K; many-one reducibility

• Simple sets

• Reducibility by truth-tables

• Non-reducibility of creative sets to simple sets by bounded truth-tables

• Counter-example for unbounded truth-tables

• Hyper-simple sets

• Non-reducibility of creative sets to hyper-simple sets by truth-tables unrestricted

• General (Turing) reducibility

• Bibliography

The following sections are included:

• Introduction

• Non-standard analysis and non-archimedean fields

• Examples in non-standard Analysis

• References

Our main result is: if b and c are recursively enumerable degrees such that b < c, then there exists a recursively enumerable degree d such that b < d < c. By degree we mean degree of recursive unsolvability as denned by Kleene and Post [2]. A degree is called recursively enumerable if it is the degree of a recursively enumerable set. The upper semi-lattice of recursively enumerable degrees has a least member, 0, the degree of all recursive sets, and a greatest member, 0′, the degree of all complete sets. Post [4] asked: does there exist a recursively enumerable degree d such that 0 < d < 0′? Friedberg [1] and Muchnik [3] answered Post's question in the affirmative. Sacks [5] showed that every countable, partially ordered set is imbeddable in the upper semi-lattice of recursively enumerable degrees. Muchnik [3] announced that if c is a non-zero, recursively enumerable degree, then there exists a recursively enumerable degree d such that 0 < d < c…

A cardinal number m will be called measurable if and only if there is a set X of cardinality m and a non-trivial, real-valued, countably additive measure μ defined on all subsets of X. (The term non-trivial can be taken to mean that μ(X) = 1 and μ({x}) = 0, for all χ ɛ X). If 2^ℵ₀ = ℵ₁, Banach and Kuratowski [1] proved that ℵ₁ is not measurable. Ulam [12] proved that if there is a measurable cardinal, then either 2^ℵ₀ is measurable or there exists a 2-valued measurable cardinal (2-valued in the sense that the measure μ can be assumed to take on only the values 0 and 1). Ulam and Tarski showed that no cardinal less than the first strengly inaccessible cardinal beyond ℵ₀ can be 2-valued measurable (cf. [12], esp. footnote 1, p. 146). Last year, using some new results of Hanf, Tarski proved [11] that many inaccessibles, in particular the first beyend ℵ₀, are not 2-valued measurable (for other proofs cf. [6] and [2]). Even though the least 2-valued measurable cardinal, if it exists at all, now appears to be incredibly large since Tarski's results apply to a seemingly inexhaustible number of inaccessible cardinals, it still seems plausible to many people including the author to assume that such cardinals do exist. However, this assumption has some surprising consequences, for, as shall be outlined below, we can show that the existence of measurable cardinals contradiets Gödel's axiom of constructibility…

We study K_T(λ) = sup{| S(A) | : | A | ≦ λ} and extend some results for totally transcendental theroies to the case of stable theories. We then investigate categoricity of elementary and pseudo-elementary classes.

One of the principal objectives of the foundations of mathematics is to “explain”, as far as possible, the basic concepts of mathematics. In the simplest case, concepts are explained in terms of other concepts. Thus the concept of rational number is explained in terms of the simpler concepts of integer and ordered pair. The object is not to reduce all problems about rational numbers to problems about integers and ordered pairs, but to be able to say that we understand the notion of a rational number as fully as we understand the notions of integer and ordered pair…

The following sections are included:

• Model-theoretic preliminaries

• The main theorems

• Bibliography

The following sections are included:

• Introduction

• Background material

• Automorphisms and maximal sets

• Satisfying condition (2.2) and the hypotheses of the Extension Theorem

• Proof of the Extension Theorem Part I: Motivation

• Proof of the Extension Theorem Part II: Covering

• Proof of the Extension Theorem Part III: Mappings

• Conclusion

• References

The following sections are included:

• The Model
  • Generic filters
  • Some lemmas on genericity
  • Description of the model
  • An important lemma

• The Concept of a Random Real
  • Extending Borel sets

• Proof of Theorems 1–3
  • Proof of Theorem 2
  • Proof of Theorem 1
  • Proof of Theorem 3
  • An extension of Theorems 1 through 3

• Bibliography

The following sections are included:

• Relations involving both join and jump operations

• Sets of degrees without g.l.b. or without l.u.b.

• Non-density

• References

The following sections are included:

• INTRODUCTION

• SECTION 1. THE SYSTEM OF ELEMENTARY ALGEBRA

• SECTION 2. DECISION METHOD FOR ELEMENTARY ALGEBRA

• SECTION 3. EXTENSIONS TO RELATED SYSTEMS

• NOTES

• BIBLIOGRAPHY

• SUPPLEMENTARY NOTES

The following sections are included:

• Introduction

• Preliminaries

• Existence of models

• Prime models

• Saturated models

• ℵ_{1 ÷ a}-categorical theories

• The number of non-isomorphic denumerable models

• References

The following sections are included:

• Introduction

• Towards the proof of the first main theorem

• Results of Khovanskii and van den Dries

• Differentiable germs in arbitrary expansions of

• Definable points on components and the proof of Lemma 2.7

• One dimensional varieties

• The proof of Lemma 2.8

• The proof of Lemma 2.9

• Towards the proof of the second main theorem

• Smooth 0-minimal theories

• Bounding the solutions to exponential-polynomial equations and the completion of the proof of the second main theorem

• References

It is shown that if there exists a supercompact cardinal then every set of reals, which is an element of L(ℝ), is the projection of a weakly homogeneous tree. As a consequence of this theorem and recent work of Martin and Steel [Martin, D. A. & Steel, J. R. (1988) Proc. Nail. Acad. Sci. USA 85, 6582–6586], it follows that (if there is a supercompact cardinal) every set of reals in L(ℝ) is determined.

The following sections are included:

• Proofs

• References

The following sections are included:

• Permissions