This new series is primarily a continuation of the old series Test Logic with a slightly different flavour, namely it focuses on a very concrete and special axiom system - ZF set theory.

Note that old chapters might be updated as well.

0.0 Introduction (WIP)

Consistency problems in set theory have a long history, tracing back to the birth of naive set theory. Georg Cantor, the father of set theory, in his entire life believed that continuum hypothesis - that there is no set X with |\mathbb N|<|X|<|\mathbb R| - follows from basic principles and axiom of choice, yet he could not find a proof; later, the independence of continuum hypothesis became the first problem on Hilbert's renowned list. Meanwhile, many people start to doubt the consistency of axiom of choice, as it could lead to counter-intuitive constructions, like Banach-Tarski's paradoxical decomposition of 3-sphere. In practice you may also often find people entertaining themselves by finding proofs of certain theorems using minimal strength of choice. In 1938, after inventing a way a language can talk about itself in his famous Incompleteness Theorem, Kurt Gödel constructed a well-behaved model - Gödel's constructible universe, denoted as L - in which both axiom of choice and continuum hypothesis holds. The independence of these two statements remains open until 25 years later when Paul Cohen came up with the method of forcing, which later became the standard method to prove consistency of negations.

Besides these two almost foundational statements, many suspicious conjectures arise naturally in analysis, topology, and algebra as well, which are later proved to be independent from \text{ZF} or even \text{ZFC}; one of the most surprising results is Whitehead's problem, whose statement is very simple and purely algebraic. Therefore, the methods for consistency problems are not nonsensical mind games but practical skills.

This note serves as a detailed and interactive (!) introduction to such methods. The structure basically follows Set theory by Thomas Jech.

In section 1, we would begin with a revision of V and present several important constructions and results between transitive models.

In section 2, we would dive into the construction of L, which still serves as a canonical model where many statement we desire holds. This section would take two distinct approaches: one utilizes Gödel operations and provides an explicitly construction, while the other one follows from the same idea in Gödel incompleteness theorem. The primary results in this section would be the consistency of \text{AC} and \text{GCH}.

In section 3, we would present the notion of forcing and prove some basic results about Boolean algebras so that forcing methods are actually usable. We will then apply forcing to prove the negation of \text{CH}. We would move onto a digression of a highly nonstandard axiom system \text{ZFA} and negate \text{AC} there. The "standard" method of negating \text{AC} would be left as exercise.

In section 4, we would develop several ways to apply forcing for "infinitely many times". The primary result in this section would be Easton's theorem, which illustrates how messy cardinal exponentiation could be. Then we would move onto Martin's axiom - a standard axiom to prove consistency of advanced negations.

Section 5 is purely interactive. It invites the reader to demonstrate the independence of Whitehead's problem themselves following the classic route: proving Whitehead's conjecture holds in L, and then disproving it in a model of \lnot\text{CH}+\text{MA}.

The preliminaries required are (i) a basic understanding of first order logic and their models, (ii) knowing what \text{ZF} axioms are and the elementary properties of ordinals.

Most of the preliminaries can be found in Test Logic series.

0.1 Notations (WIP)

0.2 Recap of logic and ZFC

In this section we will carefully define the version of axiom of separation schema, axiom of replacement schema, and axiom of choice we use. All first order languages used in this section are the language of set, i.e. the language with a single relation \in and no function or constants.

0.2.1 Axiom of separation schema

As indicated by the word "schema", this is not one particular axiom, but an infinite (but recursive) set of axioms. To be more specific, let \phi(x_0,x_1,...,x_n) be a first order formula whose free variables are among x_i, then the following formula is an axiom

\forall\bar y\forall z\exists u(\forall x(x\in u\leftrightarrow x\in z\land\phi(x,\bar y)))

This formula is written in a standard abbreviation: \bar y is a tuple of variables (y_1,...,y_n), which can be read from the substitution \phi(x,\bar y), which conventionally means substituting x in instances of free x_0 and \bar y in instances of free \bar x, i.e. substituting y_i in instances of free x_i for all 1\le i\le n, as we indicated explicitly in the notation of \phi(x_0,x_1,...,x_n) that there are n spaces to substitute after substituting x in place of x_0. This formula reads in human language as "for any sets y_1,...,y_n, and any set z, there is a set u in the form \lbrace x\in z:\phi(x,y_1,...,y_n)\rbrace.

Some examples of the application of this formula are like this:

(1) Assume we are given that y is a set. Then for any set z there is a set whose elements are precisely elements of z contained in y, i.e. there is \lbrace x\in z:x\in y\rbrace; in other words y\cap z exists (without mentioning axiom of pairing and union).

(2) For any set x, the intersection of all elements in x exists: it is \lbrace u\in\cup x:\forall y\in x(u\in y)\rbrace.

(3) Exercise: prove that for any set X and Y, the set of all functions from X to Y exists. We would denote this set as Y^X.

(4) Exercise: a set X is called inductive if (i) \emptyset\in X; (ii) \forall x\in X(x\cup\lbrace x\rbrace\in X). Axiom of infinity asserts that an inductive set exists. Prove that the smallest inductive set \mathbb N exists; that is, \mathbb N is inductive and for any inductive set X we have \mathbb N\subset X. By axiom of extensionality \mathbb N is unique, which we would call "the set of natural numbers".

Note that axiom of separation is basically the only way we can prove sets like \lbrace x:\phi(x)\rbrace exists. On one hand, there is an obvious constrain that the set the axiom guarantees to exist must be a subset of an existing set; on the other hand, it also constrains what kind of subset can exist. Here is a classic example: there is no set

\lbrace x\in\mathbb N: x \text{ cannot be defined in English in less than 1e9 characters}\rbrace

If such set exists, it must be nonempty as 1e9 characters can only form finitely many "definitions" but \mathbb N is infinite; nonetheless, as \mathbb N is well-ordered, we can absurdly define this set's minimal element in less than 1e9 characters by "the minimal element of the subset of \mathbb N which contains precisely elements that cannot be defined in English in less than 1e9 characters".

0.2.2 Axiom of replacement schema

This is also an infinite set of axioms, which roughly says that "the image of a set under a 'function' defined by a first order formula is a set". Here the 'function' is not what we define in set theory. To make more sense of this axiom, we firstly introduce some convenient meta-linguistic notions.

Definition 0.2.2.1 A class C is a formal meta-linguistic object \lbrace x:\phi(x,\bar y)\rbrace, where \phi(x_0,x_1,...,x_n) is a formula whose free variables are among x_i, and \bar y is a tuple of sets. Let z be a variable in first order set language (so in particular z is not meta-linguistic), we interpret the "formula" z\in C exactly as \phi(z,\bar y).

Definition 0.2.2.2 Let C and D be classes. We intepret the "formula" C\subset D as \forall x(x\in C\rightarrow x\in D). We then intepret the "formula" C=D as C\subset D\land D\subset C.

Here are a few examples of classes:

(1)(sets are classes) For any set x, there is a class \lbrace y:y\in x\rbrace, which is essentially x. Therefore by abusing notation we would write denote the class \lbrace y:y\in x\rbrace by x too.

(2) There is a "class of all sets" V^*=\lbrace x:x=x\rbrace.

(3) \text{On} is a class: recall the definition of ordinal - x is ordinal if x is transitive and well-ordered by \in. One can formulate the definition in one first order formula.

(4) Given any set x, we can form the class |x| to be all sets which has a bijection to x. This |x| is called the cardinality of x (without mentioning \text{AC}). With this notation |x|=|y| iff there is a bijection between x and y.

Definition 0.2.2.3 Let C and D be classes. We define C\times D to be the class

\lbrace u:u=(x,y)\land x\in C\land y\in D\rbrace

Definition 0.2.2.4 Let C, D and F be classes. The "formula" that "F is a class term from C to D", abbreviated as "F:C\rightarrow D is a class term", is the conjunction of the following two formulas:
(i) F\subset C\times D
(ii) \forall x\in C(\exists! y\in D((x,y)\in F))
One may abbreviate (x,y)\in F as F(x)=y if F is a candidate of class term.

Finally we can present the formulation of axiom of replacement: for any set X, if F:X\rightarrow V^* is a class term, then there is a set Y=\lbrace y:\exists x\in X((x,y)\in F)\rbrace

Exercise: unravel the definition to write axiom of replacement as a schema of first order formulas.

Remark: actually axiom of separation is implied by axiom of replacement and axiom of empty set. The rough idea goes as follows: for any set z,\bar y and formula \phi(x_0,x_1,...,x_n), either \exists x\in z\phi(x,\bar y) holds (it needs some care here, but we will not go into detail as we would include axiom of separation for convenience), then one can consider the class term F:z\rightarrow V^* by F(x)=x if \phi(x,\bar y), and otherwise F(x)=u for any u such that \phi(u,\bar y). Then the image of F is exactly the set in axiom of separation. Or \exists x\in z\phi(x,\bar y) does not hold, and axiom of separation implies the existence of empty set, which is guaranteed by axiom of empty set.

0.2.3 Axiom of choice

We will use the following statement of axiom of choice (always abbreviated as \text{AC}), which can be easily translated into one first order formula:
For any set X, if its elements are nonempty and pairwise disjoint, then there is a set C such that C\cap x has precisely one element for all x\in X, i.e. C "chooses" one element from each element of X.

Although the statement of \text{AC} is much simpler than the two schemas above, beginners might get confused when to use it. Actually, the power of \text{AC} comes from the fact that it allows us to make choice infinitely many times. This is essentially due to the intrinsic feature of human language: every sentence can only be finitely long, so we can use the language to make finitely many choices, but not infinitely many. That is also why there is the axiom of countable choice but never an "axiom of finite choice".

To be more specific, in practice, the ability to choose one element from a nonempty set (or more often class) is guaranteed by the tautology

\forall \bar x(\phi(\bar x)\rightarrow\exists \bar y\psi(\bar y))\rightarrow(\exists \bar x\phi(\bar x)\rightarrow\exists \bar y\psi(\bar y))\quad (*)

For example, if we want to prove that "if X and Y are countable, then X\cup Y is countable", what we essentially need to demonstrate is the existence of an injection h:X\cup Y\rightarrow\mathbb N. If we use the tautology (*) to prove this, we would let \bar x=(f,g) and \phi(\bar x) to be "f:X\rightarrow\mathbb N and g:Y\rightarrow\mathbb N are injective", while \bar y=h and \psi(\bar y) to be "h:X\cup Y\rightarrow\mathbb N" is injective. Then we can safely fix a particular instance of injections f and g, as we would firstly argue that \forall \bar x(\phi(\bar x)\rightarrow\exists \bar y\psi(\bar y)) holds, then use the deduction rule \text{MP}.

The ability to choose finitely many times is indicated by the following exercise, which we encourage every reader to have a try.

Exercise: let X be a finite set, i.e. there exists n\in\mathbb N and a bijection f:X\rightarrow n. If elements of X are nonempty and pairwise disjoint, then there is set C such that C\cap x contains precisely one element for all x\in X.
Hint: induction.