This page collects some basic set-theoretic notions used in mathematical logic, especially sets, products, finite sequences, relations, functions, and indexed families. It is not intended as a full “tutorial”, but rather as a compact “dictionary” of definitions and notation. An introduction to the Peano natural number system is given here; for the theory of countable sets, see here.
The body structure of this page is inherited from Wang, pp. 3–8.
Remark.
Strictly speaking, the notions of sets, functions, the Peano axioms, and the theory of countable sets do not stand prior to mathematical logic. Nevertheless, we introduce them as part of the surrounding metamathematical language to describe the theory of mathematical logic to provide a natural and efficient way to speak about symbols, formulas, finite sequences, assignments, relations, structures, and recursive definitions. One can remove all these tools out of the descriptions and work in a more austere, purely syntactic manner, but it usually obscures the main discussions.
Remark.
In principle, it is not impossible to prove every mathematical theorem by the most primitive formal logical derivations. However, the study of mathematical logic, as well as axiomatic set theory, does not require us to reduce all mathematical results to such fundamental logic formulae. These derivations are often extremely long, mechanical, and lacking in intuition. This is just like we never use machine language to “talk” with computers — we use Python instead. In Principia Mathematica, Whitehead and Russell attempted to reconstruct mathematics from first principles; however, the proof of the somehow “simplest” proposition “\(1+1=2\)” begins on p. 379, vol. 1 and is only completed on p. 86, vol. 2.
The real significance of mathematical logic is: we know it is there, we know all we have done and will do in mathematics are okay; then it’s over.
1. Sets
1.1 Membership, Equality, and Inclusion
A set may be understood as a collection of objects; these objects are called elements of this set. The basic characteristic of a set is: for any object, it is clear that this object belongs or does not belong to this set.
For a set \(A\) and an element \(x\), we denote \(x\in A\) if \(x\) belongs to \(A\), and \(x\notin A\) if \(x\) does not belong to \(A\).
A set is uniquely determined by all its elements. In other words, two sets are equal if and only if they contain identical elements. Given sets \(A\), \(B\), we say
\[
A=B\quad\iff\quad \text{for any element } x,\ x\in A \iff x\in B.
\]
Given sets \(A\), \(B\), we say \(A\) is a subset of \(B\), denoted \(A\subseteq B\), if all elements of \(A\) are elements of \(B\):
\[
A\subseteq B\quad\iff\quad \text{for any element \(x\), if \(x\in A\), then \(x\in B\).}
\]
Therefore, two sets are equal if they are subsets of each other:
Let $A$, $B$ be sets. Then
$$
A=B\quad\iff\quad A\subseteq B\text{ and } B\subseteq A.
$$
The empty set, denoted $\varnothing$, is the set that contains no element. The empty set is a subset of all sets.
1.2 Basic Set Operations
Let $A$ be a set. The power set of $A$, denoted $\cP(A)$, is defined to be the set of all subsets of $A$:
$$
\cP(A)=\{a\colon a\subseteq A\}.
$$
Given sets $A$, $B$. The union of $A$ and $B$, denoted $A\cup B$, is defined to be the set of all elements of $A$ and $B$:
$$
x\in A\cup B\quad\iff\quad x\in A\text{ or } x\in B.
$$
The intersection of $A$ and $B$, denoted $A\cap B$, is defined to be the set of elements that both belong to $A$ and $B$:
$$
x\in A\cap B\iff \quad x\in A\text{ and } x\in B.
$$
Two sets $A$, $B$ are called disjoint if $A\cap B=\varnothing$.
This also works for finite collection of sets: given sets $A_1,\dots,A_n$, the union and intersection of them are denoted $\bigcup_{k=1}^n A_k=A_1\cup \dots\cup A_n$, $\bigcap_{k=1}^n A_k=A_1\cap \dots\cap A_n$, respectively.
For a sequence of sets $A_0,A_1,A_2,\dots$, we denote
\bigcup_{k=0}^\infty A_k &= \{x\colon \text{There exists $k$ such that $x\in A_k$}\};\\
\bigcap_{k=0}^\infty A_k &= \{x\colon \text{For all $k$, $x\in A_k$}\}.
\end{aligned}\]
Or, more generally, given an indexed family (see section 5. for detailed definition) $(A_i)_{i\in I}$ of sets, its union and intersection is defined by
\bigcup_{i\in I} A_i &= \{x\colon \text{There exists $i\in I$ such that $x\in A_i$}\};\\
\bigcap_{i\in I} A_i &= \{x\colon \text{For all $i\in I$, $x\in A_i$}\}.
\end{aligned}\]
An indexed family of sets $(A_i)_{i\in I}$ is said to be pairwise disjoint, or simply disjoint, if for any $i,j\in I$ and $i\neq j$, $A_i\cap A_j=\varnothing$.
The difference of two sets $A$ and $B$, denoted $A\setminus B$, is the set of all elements that belong to $A$ but does not belong to $B$:
$$
A\setminus B=\{x\colon x\in A\text{ and }x\notin B\}.
$$
2. Ordered Pairs, Tuples, and Cartesian Products
2.1 Ordered Pairs and Tuples
We come to a core definition used for mathematical logic.
Let $a$, $b$ be elements. The ordered pair of $a$ and $b$ is defined by
(a,b)=\{\{a\},\{a,b\}\}.
\]
It is not necessary to memorize the precise structure in Equation 2.1. The following proposition is all we need about ordered pairs:
Let $(a_1,b_1)$, $(a_2,b_2)$ be ordered pairs. Then
$$
(a_1,b_1)=(a_2,b_2)\quad\iff \quad a_1=a_2\text{ and } b_1=b_2.
$$
Proof. The forward implication is immediate:
$$a_1=a_2\text{ and } b_1=b_2\quad\implies \quad (a_1,b_1)=(a_2,b_2)
$$
It suffices to show the converse.
Suppose $(a_1,b_1)=(a_2,b_2)$, then
$$\{\{a_1\},\{a_1,b_1\}\} = \{\{a_2\},\{a_2,b_2\}\},
$$
which means at least one of the following is true:
- $\{a_1\} = \{a_2\}$ and $\{a_1,b_1\} = \{a_2,b_2\}$;
- $\{a_1\} = \{a_2,b_2\}$ and $\{a_1,b_1\}=\{a_2\}$.
For case a., from $\{a_1\}=\{a_2\}$, we obtain $a_1=a_2$; from $\{a_1,b_1\} = \{a_2,b_2\}$ and $a_1=a_2$, we have $b_1=b_2$.
For case b., from $\{a_1\}=\{a_2,b_2\}$, we have $a_1=a_2=b_2$; from $\{a_1,b_1\}=\{a_2\}$, we have $a_1=b_1=a_2$. This means $a_1=a_2=b_1=b_2$.
Therefore, $a_1=a_2$ and $b_1=b_2$ is true for all possible cases.
We can inductively define the ordered tuple of elements $a_1,\dots,a_n$ for $n\ge 2$:
(a_1,a_2,a_3) &= ((a_1,a_2),a_3);\\
(a_1,\dots,a_{n-1},a_n) &= ((a_1,\dots,a_{n-1}),a_n)\quad\text{for $n\geq 3$}.
\end{aligned}\]
An ordered tuple of $n$ elements is also called an $n$-tuple. Easy verification implies that:
Let $a_1,\dots,a_n$, $b_1,\dots,b_n$ be elements. Then
$$
(a_1,\dots,a_n)=(b_1,\dots,b_n)\quad\iff\quad a_1=b_1,\dots,a_n=b_n.
$$
2.2 Cartesian Products
The (Cartesian) product of two sets $A$ and $B$, denoted $A\times B$, is defined by the set of all ordered pairs of two elements, where the first one belongs to $A$ and the second one belongs to $B$:
$$
A\times B = \{(a,b)\colon a\in A\text{ and } b\in B\}.
$$
We can also define the product of $n$ sets $A_1,\dots,A_n$:
$$
A_1\times \dotsb \times A_n = \prod_{k=1}^n A_k = \{(a_1,\dots,a_n)\colon \text{for each $k=1,\dots,n$, $a_k\in A_k$}\}.
$$
If $A_1=\dotsb=A_n=A$ ($n>1$), then their product is also denoted by $A^n$. By convention, we let $A^0=\{()\}$, where $()$ is the unique empty tuple, and $A^1=A$. An element of $A^n$ is called a finite sequence over $A$ of length $n$. The length of a sequence $s\in A^n$ is $n$, denoted $\operatorname{lh}(s)=n$.
2.3 Projection Maps
Let $A_1,\dots,A_n$ be sets. For each $k\in \{1,\dots,n\}$, define the $k$-th projection map
$$
\pi_k\colon A_1\times \dotsb\times A_n\to A_k
$$
by
$$
\pi_k(a_1,\dots,a_n) = a_k
$$
for each $(a_1,\dots,a_n)\in A_1\times \dotsb\times A_n$.
If $A_1=\dots=A_n=A$, then we may also write $\pi_k\colon A^n\to A$ as a projection map.
For each set $A$, the set
$$
A^{<\omega} = \bigcup_{0\leq n<\infty} A^n
$$
denotes the set of all finite sequences over $A$. An element of $A^{<\omega}$ is called a finite sequence over $A$.
The notions of relation and function will be built on subsets of Cartesian products.
3. Relations
Given sets $A$ and $B$, a relation from $A$ to $B$ is a subset of $A\times B$. In other words, it is a collection of part of ordered pairs $(a,b)$, where $a\in A$ and $b\in B$. If $A=B$, then $R\subseteq A\times A$ is called a binary relation on $A$.
If $R\subseteq A^n$, then $R$ is called an $n$-ary relation on $A$.
A binary relation $R\subseteq A\times A$ is called an equivalence relation if it satisfies the following conditions:
- Reflexivity: For all $x\in A$, $(x,x)\in R$;
- Symmetry: For all $x,y\in A$, if $(x,y)\in R$, then $(y,x)\in R$;
- Transitivity: For all $x,y,z\in A$, if $(x,y)\in R$ and $(y,z)\in R$, then $(x,z)\in R$.
Given an equivalence relation $R$ on $A$, if $(a,b)\in R$, then we say that $a$ and $b$ are equivalent and denote $a\sim b$. The equivalence class of $a\in A$, denoted by $[a]$, is the set of all elements of $A$ that are equivalent to $a$:
$$
[a] = \{x\colon x\in A\text{ and } x\sim a\}.
$$
Two equivalence classes on a set $A$ is either equal or disjoint. In other words, given $a,b\in A$, $\eqc{a}=\eqc{b}$ or $\eqc{a}\cap \eqc{b}=\es$.
Given set $A$ and an equivalence relation $R$ on $A$, the set of all equivalence classes on $A$ is called the quotient set or quotient class, denoted by $A/R$.
4. Functions
Let $X$, $Y$ be sets. A relation $f\subseteq X\times Y$ is called a function or mapping from $X$ to $Y$, if for all $x\in X$, there exists a unique $y\in Y$ such that $(x,y)\in f$; we denote $f\colon X\to Y$ in this case.
Let $f\colon X\to Y$ be a function. If $(x_0,y_0)\in f$, then $y_0$ is called the image of $x_0$, and $x_0$ is called a preimage of $y_0$; we denote $f(x_0)=y_0$ or $x_0\mapsto y_0$.
For a function $f\colon X\to Y$, the set $X$ is called the domain of $f$; the set
$$
\{y\in Y\colon \text{there exists $x\in X$ such that $f(x)=y$}\}
$$
is called the range or image of $f$.
For a function $f\colon X\to Y$ and set $A\subseteq X$, $B\subseteq Y$, the image of $f$ over $A$, denoted by $f[A]$, is the set
$$
f[A] = \{f(x)\colon x\in A\};
$$
The preimage of $f$ over $B$, denoted $f^{-1}[B]$, is the set
$$
f^{-1}[B] = \{x\in X\colon f(x)\in B\}.
$$
For a function $f\colon X\to Y$ and set $A\subseteq X$, the restriction of $f$ over $A$, denoted $f\vert_A$, is a function from $A$ to $Y$, such that $f\vert_A(x) = f(x)$ for all $x\in A$.
If the range of $f$ is exactly $Y$, then $f$ is called surjective, or a surjection from $X$ to $Y$.
If function $f\colon X\to Y$ satisfies that for all $x_1,x_2\in X$,
$$
x_1\neq x_2\implies f(x_1)\neq f(x_2),
$$
then $f$ is called injective, or an injection from $X$ to $Y$.
If function $f\colon X\to Y$ is both injective and surjective, then $f$ is called bijective or a bijection from $X$ to $Y$, in which case we call that there exists a one-to-one correspondence from $X$ to $Y$, or just $X$ and $Y$ are equivalent. We also define the inverse function $f^{-1}\colon Y\to X$ for any bijection $f$, defined by
$$
f^{-1}(y)=x \iff f(x)=y.
$$
Given functions $f\colon X\to Y$ and $g\colon Y\to Z$, we define the composite of $g$ and $f$ by
$$
g\circ f(x) = g(f(x)).
$$
Moreover, if $f$ and $g$ are both bijections, then so do $g\circ f$.
A $n$-ary function $f\colon A^n\to A$ on a set $A$ is called an $n$-ary operator on $A$.
Let $I$ and $A$ be sets. An $I$-indexed family of elements of $A$ is a function $f\colon I\to A$. We usually write $a_i=f(i)$, and denote the family by $\{a_i\}_{i\in I}$ or $(a_i)_{i\in I}$. Different indices may correspond to the same value.