Sets

You can read the LaTeX document online (for the latest updated chapters) from the link: https://pdf.gaomj.cn/?file=get.php?f=set-theory

Sets Before 19th century, sets were not considered to be mathematical objects. The modern study of set theory began with Georg Cantor. The theory developed during the early stage is generally called naive set theory. However, it was soon discovered that naive set theory leads to paradoxes. To resolve these paradoxes, mathematicians proposed axiomatic set theories, the core of which is the postulation of rules by which new sets can be formed from given ones.

In this chapter, we will go through some axioms of set theory, but before the axioms, we discuss some basic operations on sets while assuming a set is well-defined. The definition of a set relies on the axioms, but we can discuss the operations first based on our naive understanding of sets. After that, our selection of axioms will be guided by the principle that they agree with our intuition as much as possible.

Contents
Contents
 1.  Set Relations and Operations
 2.  * Axioms

1. Set Relations and Operations In this section, as is mentioned above, we assume that some sets have already been defined.

If a is an element of set A, we write a\in A; otherwise, we write a\notin A. A set is determined by its elements, so the equality A=B naturally means \forall x \, (x\in A \Leftrightarrow x\in B). It can be seen that we have:
\begin{gather*}
(A\subseteq B):=\forall x \, (x\in A \Rightarrow x\in B),\\
(A=B) \Leftrightarrow (A\subseteq B \wedge B\subseteq A).
\end{gather*}

If every element of set A is also an element of set B, we say A is a subset of B, or B includes/contains A, denoted by A\subseteq B. If A\subseteq B and A\neq B, we say A is a proper subset of B, denoted by A\subsetneq B.

We adopt these notations for subsets and proper subsets in order to avoid confusion with other customary notations. For example, some authors use A\subset B to denote a proper subset, analogous to the notations of inequalities, while some authors use A\subset B to denote a subset. Some authors even use A\subsetneqq B in order to make the distinction clear.
.

Given any sets A,B, we now define the pair set, union set and power set. Their existence and uniqueness are guaranteed by the later axioms.

Alternatively, we can use logical symbols:
\begin{align*}
\{A,B\} & := \{x \mid x=A \vee x=B\},\\
A\cup B & := \{x \mid x\in A \vee x\in B\},\\
\mathcal{P}(A) & := \{x \mid x\subseteq A\}.
\end{align*}

From these definitions, we can define some other finite sets. If A=B, the resulting set is \{A\}:=\{A,B\}. If C is also a set, the union of \{A,B\} and \{C\} is \{A,B,C\}:=\{A,B\}\cup\{C\}. Similarly, we can define \{A _ 1,A _ 2,\dots,A _ n\}.

Suppose P is a property that elements of a set may or may not have. It is known from the axioms that \{x\in A\mid P(x)\} is a set. Furthermore it is a subset of A. Now we can define the intersection and difference (or, relative complement) of two sets:
\begin{align*}
A\cap B & := \{x\in A \mid x\in B\},\\
A\setminus B & := \{x\in A \mid x\notin B\}.
\end{align*}

The "relative complement" of sets is defined, but we cannot define the "absolute complement" \{x\mid x\notin B\} of a set. Otherwise, the union of it and B would be the set of all sets, which fails to be a true set. This is a theorem that we prove now.

It suffices to show that for any set S there is a set not belonging to S. Let A=\{x\in S\mid x\notin x\}. By definition, A\in A if and only if A\in S \wedge A\notin A. If we assume A\in S, then we have A\in A \Leftrightarrow A\notin A, which is a contradiction. Therefore, A\notin S.□

Based on the operations that we have defined, we have the following elementary properties.

\begin{gather*}
A\cup B = B\cup A,\quad A\cap B = B\cap A.\\
A\cup (B\cup C) = (A\cup B)\cup C,\\
A\cap (B\cap C) = (A\cap B)\cap C.\\
A\cup (B\cap C) = (A\cup B)\cap (A\cup C),\\
A\cap (B\cup C) = (A\cap B)\cup (A\cap C),\\
A\setminus (B\cup C) = (A\setminus B)\cap (A\setminus C),\\
A\setminus (B\cap C) = (A\setminus B)\cup (A\setminus C).\\
A\cap\varnothing = \varnothing,\quad A\cup\varnothing = A.
\end{gather*}

It is easy to verify these properties.
2. * Axioms Now some of our axioms are introduced, which justify the definitions and properties in the previous section.

1. Extensionality Axiom: Two sets are equal if they have the same elements, i.e.,
   \[
   \forall A\forall B\, [\forall x\, (x\in A\Leftrightarrow x\in B)\Leftrightarrow A=B].
   \]
2. Empty Set Axiom: There exists a set with no elements, denoted by \varnothing, i.e.,
   \[
   \exists A\, \forall x\, (x\notin A).
   \]
3. Pairing Axiom: For any sets A,B, there is a set whose elements are exactly A and B, i.e.,
   \[
   \forall A\forall B\, \exists C\, \forall x\, (x\in C\Leftrightarrow x=A\vee x=B).
   \]
4. Union Axiom for Two Sets: For any sets A,B, there is a set whose elements are those that belong to A or B, i.e.,
   \[
   \forall A\forall B\, \exists C\, \forall x\, (x\in C\Leftrightarrow x\in A\vee x\in B).
   \]
5. Power Set Axiom: For any set A, there is a set whose elements are all subsets of A, i.e.,
   \[
   \forall A\, \exists B\, \forall x\, (x\in B\Leftrightarrow x\subseteq A).
   \]

.
The Axioms 2--5 ensures the existence of \varnothing, the pair set, the union and the power set respectively, and the Axiom 1 ensures their uniqueness.

It is very common that the empty set is a trivial case that does not worth mentioning. However, it is not recommended to omit, as a number of propositions are false without excluding the empty set. For example, it is false that "every continuous function on a compact set has a maximum point", and that "a real set bounded above has a least upper bound".

Now we want the axioms for the definition of intersection and difference. What we made use of is the property that B=\{x\in A\mid P(x)\} is a set for a property P. Of course the property P cannot take the undefined B as an argument, in order to avoid circular definition.

6. Subset Axioms: For property P not containing B, it is an axiom that \{x\in A\mid P\} is a set, i.e.,
   \[
   \forall A _ 1\dots\forall A _ n\forall A\, \exists B\, \forall x\, (x\in B\Leftrightarrow (x\in A)\wedge P).
   \]

.
There is one axiom for each P, so this is an axiom schema. It is also called the axiom of separation.

Note that the logical formalisation of the axioms are provided as well as natural language descriptions. In fact this is necessary. Consider the following set: \{x\in\mathbb N\mid x\text{ is not definable in under sixty letters}\}. The consideration of the smallest number in this set leads to Berry paradox. On the one hand, it involves a self-referential definition that is not allowed. On the other hand, the property cannot be expressed in the logical formal language so it is not considered to be a legitimate property.

Now we improve the union axiom to the version that allows arbitrary unions. For a set S=\{A _ 1,A _ 2,\dots\}, we need the general union
\[\bigcup S=\bigcup _ i A _ i=\{x\mid (\exists A\in S)\, x\in A\}.\]

We remark that the notation \bigcup S is used much less than \bigcup _ {i}A _ i.

4'. Union Axiom: For any set S, there exists a set B whose elements are the elements of the members of S, i.e.,
\[\forall x\, (x\in B\Leftrightarrow (\exists A\in S)\, x\in A).\]

.
For general intersections, we can define by subset axioms. For a nonempty set S, pick A _ 0\in S. By subset axioms there is a set \{x\in A _ 0\mid (\forall A\in S)\, x\in A\}, and this set is unique by extensionality axiom.

Note that there is an assumption of nonemptyness. We do not define it here, just as we do not define the division of a number by zero.

We have the following equalities.
\begin{gather*}
B\cup\bigcap\mathcal A =\bigcap\{B\cup X\mid X\in\mathcal A\}=:\bigcap _ {X\in\mathcal A}(B\cup X),\\
B\cap\bigcup\mathcal A =\bigcup\{B\cap X\mid X\in\mathcal A\}=:\bigcup _ {X\in\mathcal A}(B\cap X),\\
B\setminus\bigcup\mathcal A=\bigcap\{B\setminus X\mid X\in\mathcal A\},\\
B\setminus\bigcap\mathcal A=\bigcup\{B\setminus X\mid X\in\mathcal A\}.
\end{gather*}

The proofs of the existence of the sets and these equalities are not difficult and therefore omitted. (For intersection we implicitly assume \mathcal A\neq\varnothing.)

Currently six axioms have been introduced to our axiom list.