Set Theory and Foundations of Mathematics: An Introduction to Mathematical Logic

The following sections are included:

• Preface
• About the Authors
• Contents

The goal of this book and its companion volume [4] on set theory is to provide an introduction to mathematical logic and the foundations of mathematics for students of mathematics. Mathematical logic is a flourishing area of research with specialties including computability theory, model theory, proof theory, and set theory, and all of these areas are covered. An effort is made to connect foundations with topics covered in the mathematics major, including algebra, analysis, geometry, and topology. Thus we have chapters on Boolean algebras, on nonstandard analysis, and on the foundations of geometry. We hope that this book can provide a broader perspective for all students interested in mathematics, including prospective logic students…

The following sections are included:

• Basic Definitions
• Truth Interpretations
• The Disjunctive Normal Form Theorem
• The Deductive Calculus
• The Soundness Theorem
• The Completeness Theorem
• Completeness, Consistency, and Independence
• Logical vs. Topological Compactness

Propositional logic treats a basic part of the language of mathematics, building more complicated sentences from simple with connectives. However, it is inadequate as it stands to express the richness of mathematics. Consider for example the properties of the natural numbers ℕ = {0, 1, 2,…} equipped with a linear ordering < and binary operations of addition and multiplication. To say that 0 is the least element, we need to write (∀x)¬(x < 0). To say that there is no greatest element, we need to write (∀x)(∃y)x < y. To test whether an arbitrary structure (A, <) satisfies these properties, we need to know how to interpret < in the set A.

Predicate logic, also called first-order logic, is an enrichment of propositional logic to include predicates, individuals and quantifiers, and is widely accepted as the standard language of mathematics. Axiomatic predicate logic was established by Gottlob Frege [12] in the late 19th century, who formalized the notion of quantified variable which we will present here.

In this chapter, we will prove Gödel’s Completeness Theorem for predicate logic by showing how to build a model for a consistent first-order theory.

Gödel first proved this result in 1929 [13] in his doctoral dissertation. We will also discuss several consequences of the Compactness Theorem for first-order logic and consider several relations that hold between various models of a given first-order theory, namely isomorphism and elementary equivalence.

For a more thorough introduction to the subject of model theory, books by Marker [25], Hodges [19], and Chang and Keisler [6].

The following sections are included:

• Properties and Examples of Boolean Algebras
• The Partial Ordering on a Boolean Algebra
• Filters and Ideals
• Ultraproducts

The theory of computability traces back to the work of Gödel, Church, Tulring and others in the 1930s. There are many different approaches to defining the collection of computable number-theoretic functions. The intuitive idea is that a function F : ℕ → ℕ (or more generally F : ℕ^k → ℕ) is computable if there is an algorithm or effective procedure for determining the output F (m) from the input m. To demonstrate that a particular function F is computable, it suffices to give the corresponding algorithm. We will begin by considering examples of intuitively computable functions; we will later consider formal definitions of computable functions (and it will follow that the functions given below are all computable in this formal sense).

In this chapter, we bring together the two major strands that we have considered thus far: logical systems (and, in particular, their syntax and semantics) and computability theory. We will briefly discuss decidable and undecidable logical systems, but our primary focus will be decidable and undecidable first-order theories. The notion of decidability was one of the key ideas of 20th century mathematics, and was given impetus by the famous Hilbert’s Problems [15] presented at the 1900 International Conference of Mathematics in Paris. The second problem was to prove that the axioms of arithmetic are consistent. This was shown to be unattainable by Gödel’s Incompleteness Theorem, presented in Section 7.3 below. A related question posed by Hilbert and Ackermann in [17], known as the Entscheidungsproblem, asked for an algorithm for deciding the truth or falsity of any statement of predicate logic. This was answered in the negative by Church’s Undecidability Theorem (Theorem 7.3.12), which is also proved in this chapter. These results as presented here make use of a number of results from computability theory as outlined in Chapter 5.

In this chapter, we will briefly the discuss the basics of the theory of algorithmically random strings. Although this is not a topic typically covered in an introduction to the foundations of mathematics, the theory of algorithmic randomness provides interesting examples of the phenomena of undecidability and incompleteness that we considered in the previous two chapters…

In this chapter, we explore the structure of nonstandard models of ℕ and ℝ. Such structures exist by the Compactness Theorem. The primary focus here will be on the construction of nonstandard models using ultraproducts. Nonstandard models of the reals include so-called infinitesimal elements which provide an alternative approach to the study of calculus…

Plane geometry is an area of mathematics that has been studied since ancient times. The roots of the word geometry are the Greek words ge, meaning “earth”, and metria, meaning “measuring”. This name reflects the computational approach to geometric problems, that had been used before the time of Euclid, (ca. 300 BC), who introduced the axiomatic approach in his book, Elements. Euclid did not limit himself to plane geometry in the Elements, but also included chapters on algebra, ratio, proportion and number theory. His book set a new standard for the way mathematics was done.

The following sections are included:

• Bibliography
• Index