Set Theory And Foundations Of Mathematics: An Introduction To Mathematical Logic - Volume I: Set Theory. Douglas Cenzer

that is, one set x being a member or element of a second set y; this is written x ∈ y. Then one set x is a subset of another set y, written x ⊆ y, if every element of x is also an element of y.

      Chapter 3 introduces the axioms of Zermelo–Fraenkel (ZF). A set should be determined by its elements. Thus the Axiom of Extensionality states that two sets are equal if and only if they contain exactly the same elements. Some basic axioms provide the existence of simple sets. For example, the Empty Set Axiom asserts the existence of the set

with no elements. The Axiom of Pairing provides, for any two sets x and y, a set {x, y} with exactly the two members x and y. The Union Axiom provides the union x∪y of any two given sets, as well as the more general union ⋃A of a family A of sets. With these we can create sets with three or more elements, for example {a, b, c} = {a, b} ∪ {b, c}. The Power Set Axiom collects together into one set

(A) all subsets of a given set A. The Axiom of Infinity postulates the existence of an infinite set and thus provides for the existence of the set

of natural numbers. The Axiom of Comprehension provides the existence of the definable subset {x ∈ A : P(x)} of elements of a given set A which satisfy a property P. For example, given the set

of natural numbers, we can define the set of even numbers as {x : (∃y)x = y + y}. The Axiom of Replacement provides the existence of the image F[A] of a given set A under a definable function. The somewhat controversial Axiom of Choice states that for any family {Ai : i ∈ I} of nonempty sets, there is a function F with domain I such that F(i) ∈ Ai for all i ∈ I. This might seem to be an obvious fact, but it has very strong consequences. In particular, the Axiom of Choice implies the Well-Ordering Principle that every set can be well-ordered. A well-ordering ⊲ of a set A is an ordering with no descending sequences a₁ ⊳ a₂ ⊳ · · · . So the integers can be well-ordered by 0 ⊲ 1 ⊲ − 1 ⊲ 2 ⊲ · · · . However, any attempt to well-ordered set of real numbers will reveal that this is not so obvious after all. Finally, the Axiom of Regularity states that every set A contains a ∈-minimal element, that is, a set x ∈ A such that, for all y ∈ A, y ∉ x. In particular, this implies that no set can belong to itself, and therefore there can be no universal set of all sets. The Axiom of Regularity implies that there is no chain of sets A₀, A₁, . . . such that A_n+1 ∈ An for all n. This principle is needed to prove theorems by induction on sets, in the same way that the standard well-ordering on the natural numbers leads to the principle of induction.

      Chapter 4 introduces the notion of cardinality, including finite versus infinite, and countable versus uncountable sets. We define the von Neumann natural numbers — N = {0, 1, 2, . . . } — in the context of set theory. The Induction Principle for natural numbers is established. The methods of recursive and inductive definability over the natural numbers are used to define operations including addition and multiplication on the natural numbers. These methods are also used to define the transitive closure of a set A as the closure of A under the union operator and to define the hereditarily finite sets as the closure of 0 under the Power Set operator. The Schröder–Bernstein theorem is presented, as well as Cantor’s theorem, which shows that the set of subsets of natural numbers is uncountable, and thus the set of reals is also uncountable.

      Chapter 5 covers ordinal numbers and their connection with well-orderings. The notions of recursive definitions and the principle of induction on the ordinals are developed. The hierarchy Vα of sets is developed and the notion of rank is defined. The standard operations of addition, multiplication, and exponentiation of ordinal arithmetic are defined by transfinite recursion. Various properties of ordinal arithmetic, such as the commutative, associative, and distributive laws, are proved using transfinite induction. This culminates in the Cantor Normal Form Theorem. Well-ordered subsets of the standard real ordering are studied. It is shown that every countable well-ordering is isomorphic to a subset of the rationals, and that any well-ordered set of reals is countable.

      Chapter 6 is focused on cardinal numbers and the Axiom of Choice. Zorn’s lemma and the Well-Ordering Principle are shown to be equivalent to the Axiom of Choice. Zorn’s lemma is used to prove the Prime Ideal Theorem and to show that every vector space has a basis. Cardinal numbers are defined and it is shown that, under the Axiom of Choice, every set has a unique cardinality. Hartogs’ lemma that every cardinal number has a successor is proved, thus establishing the existence of uncountable cardinals. The operations of cardinal arithmetic are defined. The Continuum Hypothesis that the reals have cardinality ℵ₁ is formulated. It is shown that the reals cannot have cardinality ℵω. The notion of cofinality and regular cardinals are defined, as well as weakly and strongly inaccessible.

      Chapter 7 makes the connection between set theory and the standard mathematical topics of algebra, analysis, and topology. The integers, rationals, and real numbers are constructed inside of the universe of sets, starting from the natural numbers. The rationals are characterized, up to isomorphism, as the unique countable dense linear order without endpoints. The reals are characterized, up to isomorphism, up as the unique complete dense order without endpoints containing a countable dense subset. The notions of accumulation point and point of condensation are discussed. There is a careful proof of the Cantor–Bendixson theorem that every closed set of reals can be expressed as a disjoint union of a countable set and a perfect closed set. There is a brief introduction to topological spaces. The Cantor space 2 ^{and Baire space}

are studied. It is shown that a subset of 2 is closed if and only if it can be represented as the set of infinite paths through a tree.

      Chapter 8 introduces the notion of a model of set theory. Conditions are given under which a given set A can satisfy certain of the axioms, such as the Union Axiom, the Power Set Axiom, and so on. It is shown that the hereditarily finite sets satisfy all axioms except for the Axiom of Infinity. The topic of the possible models of fragments of the axioms is examined. In particular, we consider the axioms that are satisfied by Vα when α is for example a limit cardinal, or an inaccessible cardinal. The hereditarily finite and hereditarily countable, and more generally hereditarily < κ, sets are also studied in this regard. The hereditarily finite sets are shown to satisfy all axioms except regularity. This culminates in the proof that Vκ is a model of ZF if and only if κ is a strongly inaccessible cardinal.

      Chapter 9 is a brief introduction to Ramsey theory, which studies partitions. This begins with some finite versions of Ramsey’s theorem and related results. There is a proof of Ramsey’s theorem for the natural numbers as well as the Erdős–Rado theorem for pairs. Uncountable partitions are also studied.

      This additional material gives the instructor options for creating a course which provides the basic elements of set theory and logic, as well as making a solid connection with many other areas of mathematics.

       Chapter 2

       Review of Sets and Logic

      In this chapter, we review some of the basic notions of set theory