Set Theory
Set theory is the study of sets. A set is an unordered collection of distinct objects, where objects in pure set theory are themselves sets.
Set language
A set is denoted as a brace-delimited, comma-separated list of member sets. The set with no members, known as the empty or null set, is denoted as \emptyset.
The language of set theory uses as a foundation the first-order predicate logic with equality. Set variables are denoted by lower-case Roman letters, such as x and y.
Expressions in the set language are constructed from set variables and first-order logic, and are called formulas. Formulas in the basic language are denoted by lower-case Greek letters, such as \phi and \psi.
A free variable of a formula is a variable which has not been quantified, and so can be substituted for any value. A formula with free variables says something about each specific value over which those variables can vary.
A bound variable of a formula is a variable which has been quantified, and so the range of values over which the variable varies is constrained. A formula with no free variables makes a statement about the universe which the language describes. Such a formula is called a sentence.
When a formula with free variables is used as an axiom or a theorem, it is meant that the formula holds for all possible values given to its free variables. Therefore, the formula \exists z ( z = x \cup y ) is taken to mean \forall x \forall y \exists z ( z = x \cup y ).
The set language comprises the following quantifiers, relations, and connectives:
| Symbol | Quantifier | Derivation |
|---|
| \exists | Existential | primitive |
| \exists! | Unique existential | \exists! x (\phi) \iff \exists x \forall y (\phi (y) \iff y = x) |
| \forall | Universal | \forall x (\phi) \iff \lnot \exists x (\lnot \phi) |
| Symbol | Relation | Derivation |
|---|
| = | Equality | primitive |
| \in | Membership | primitive |
| \ne | Inequality | (\phi \ne \psi) \iff \lnot(\phi = \psi) |
| \notin | Non-membership | (\phi \notin \psi) \iff \lnot(\phi \in \psi) |
| Symbol | Connective | Derivation |
|---|
| \lnot | Negation | primitive |
| \lor | Disjunction | primitive |
| \land | Conjunction | (\phi \land \psi) \iff (\lnot \phi \lor \lnot \psi) |
| \implies | Implication | (\phi \implies \psi) \iff (\lnot \phi \lor \psi) |
| \iff | Bidirection | (\phi \iff \psi) \iff (\phi \implies \psi \land \psi \implies \phi) |
Axioms
Axiom of Extensionality
\forall x (x \in y \iff x \in z) \implies y=z
A set is determined solely by its members. If two sets have the same members, they are equal.
Axiom of Comprehension
\exists y \forall x (x \in y \iff \phi (x))
A set can be constructed from any formula (of the language of set theory) \phi.
The axiom of comprehension is an axiom schema, with which instances of the axiom are constructed by letting the free variable \phi vary over all possible formulas.
This axiom is inconsistent. A refutation of an inconsistent instance of the axiom of comprehension is called an antinomy. The simplest possible such antinomy is Russel’s antinomy:
\lnot \exists y \forall x (x \in y \iff x \notin x)
This says that there is no such set which contains all sets which do not contain themselves.
Russel’s antinomy can be proven by contradiction. Suppose y is a set such that \forall x (x \in y \iff x \notin x), then, since what holds for every x must necessarily hold in particular for y, we have y \in y \iff y \notin y, a contradiction.
The existence of antinomies show that not every collection of sets is, in itself, a set. To avoid the antinomies, we take as sets only the collections of objects which are specifiable in the set language.
If there does exist a y such that \forall x (x \in y \iff \phi(x)) then this y is unique, via the axiom of extensionality.
Scrap
The extended language (classes)
A class is a general specifiable collection, which may or may not be a set. Class notation adds no expressive power to our set language, it only serves to make the language more concise.
A class x is the class of all objects for which a given formula \phi (x) holds, denoted as \{ x : \phi (x)\}. This is called a class term. The formula \phi (x) can optionally contain free variables other than x, these are called parameters. Different values of the parameters may yield different classes. For example, the class \{ x : x \in \mathbb{N} \land x < y \} is a class with no members if y=0, and has a single member if y=1.
All sets are classes, because a class is a specifiable collection and all sets are specifiable. The set y is the class \{ x : x \in y \}.
| Extended language | Basic language | Description |
|---|
| y \in \{ x : \phi (x) \} | \phi (y) | Membership of a set in a class |
| \{ x : \phi (x) \} = \{ y : \psi (y) \} | \forall z ( \phi (z) \iff \psi (z) ) | Equivalence of two classes |
| x = \{ y : \phi (y) \}, \{ y : \phi (y) \} = x | \forall z ( z \in x \iff \phi (z)) | Equivalence of a set and a class |
| \{ x : \phi (x) \} \in \{ y : \psi (y) \} | \exists z ( z = \{ x : \phi (x) \} \land z \in \{ y : \psi (y) \}) | Membership of a class in a class |
| \{ x : \phi (x) \} \in y | \exists z ( z = \{ x : \phi (x) \} \land z \in y) | Membership of a class in a set |
Class variables are represented by upper-case Roman letters, and are used to show that a formula holds for all classes (in other words, for a general class). We are restricted from using quantifiers to bind class variables, because this would introduce semantics that are unrepresentable in the underlying basic language, so all class variables must appear in formulas as free variables.
Upper-case Greek letters stand for general class formulas. A class variable A is equivalent to the class term \{ x : \Phi (x) \}, for all class formulas \Phi.
| Character set | Example | Meaning |
|---|
| Lower-case Roman letters | x, y, z | Set variables |
| Upper-case Roman letters | A, B, C | Class variables |
| Lower-case Greek letters | \phi, \psi | Set formulas |
| Upper-case Greek letters | \Phi, \Psi | Class formulas |
| Lower-case German letters | \frak {a, b, c} | Either class or set variables |
Atomic formulas are constructed from class terms, class variables, and set variables by means of the equalty and membership relation symbols.
All other formulas are constructed from atomic formulas over the logical connectives, and also by quantification over set variables only.
Class terms are expressions in the form \{ x : \Phi (x) \} where \Phi is an arbitrary formula.
The Rule of Substitution of Sets for Classes
From \Phi (A) infer \Phi (x). All sets are classes, but not all classes are sets.
y \in \{ x : \Phi (x) \} \iff \Phi (y)
A = B \iff \forall x (x \in A \iff x \in B)
A \in B \iff \exists x (x = A \land x \in B)
Remember that the class variables can be substituted for set variables.
Terminology
“A is a set” means \exists x (x = A).
“A is a proper class” means \lnot \exists x (x = A)
\{ x \in A : \Phi(x) \} is short for \{ x : x \in A \land \Phi(x) \}
Relation definition
A relation R(\frak{a_{1}, ..., a_{n}}) is defined as R(\frak{a_{1}, ..., a_{n}}) \iff \Phi(\frak{a_{1}, ..., a_{n}}), where \Phi is a formula with no free variables other than \frak{a_{1}, ..., a_{n}}.
A relation always returns a truth value.
Functions
Let \Phi(\frak a_{1}, ..., a_{n}, \rm y) be a formula with no free variables other than \frak a_{1}, ..., a_{n}, \rm y, such that \exists! y \Phi(\frak a_{1}, ..., a_{n}, \rm y)
A function always returns exactly one set, when passed the same variables (via axiom of extensionality).
Union
\cup A is the class of all members of the members of A, and is called the union of A.
\cup A = \{ x : ( \exists u \in A) (x \in u)\}
Intersection
\cap A is the class of all common members of all members of A, and is called the interection of A.
\cap A = \{ x : ( \forall u \in A) (x \in u)\}
The Axioms of Set Theory
We have abandoned the axiom schema of comprehension, because of the antinomies.
Axiom of Union
\forall z \exists y \forall x ( x \in y \iff \exists u (x \in u \land u \in z))
For every set z there is a set y which consists of the members of the members of set z.
Also written as \{ x : \exists u (x \in u \land u \in z)\}, or abbreviated further as “\cup z is a set”
Axiom of Power-Set
\forall z \exists y \forall x (x \in y \iff x \subseteq z)