\documentclass{article}

\usepackage[english]{babel}

\usepackage{amsmath}
% for symbols such as /implies
\usepackage{amssymb}
% for symbols such as /subsetneq
\usepackage{amsthm}
% for commands such as \newtheorem

\theoremstyle{definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{axiom}{Axiom}

\begin{document}

\section{Sets}

In mathematics, everything is a set. This page serves as an introduction to sets.

% set/element
\begin{definition}
  A \emph{set} is a collection of \emph{elements}, subject to the axioms that follow. Every element of a set is a set.
  We denote that a set $x$ is an element of a set $A$ by writing $x\in A$. If a set $x$ is not an element of a set $A$, we write $x\notin A$.
  If all elements of a set are known, it may be denoted as its elements separated by commas and surrounded by curly braces.
\end{definition}

\begin{axiom}[Extensionality]
  Sets $A$ and $B$ are \emph{equal}, denoted $A=B$, if they have the same elements.
  $$
    \forall A \ \forall B \quad (\forall x \ (x \in A \iff x \in B)) \implies A = B
  $$
\end{axiom}

% unequal
\begin{definition}
  Sets $A$ and $B$ are \emph{unequal} if they are not equal, denoted $A\neq B$.
  $$
    A\neq B \iff \lnot (A=B)
  $$
\end{definition}

\begin{example}
  If a set $A$ satisfies $x\in A$, $y\in A$, and for all sets $z$ one has $z=x$ or $z=y$ or $z\notin A$, then $A$ may be denoted as $\{x,y\}$. Moreover, the axiom of extensionality yields
  $$
    A = \{x,y\}
  $$
\end{example}

% subset
\begin{definition}
  A set $B$ is a \emph{subset} of a set $A$ if every element of $B$ is an element of $A$.
  This is denoted as $B \subseteq A$.
  $$
    B \subseteq A \iff \forall x \ (x \in B \implies x \in A)
  $$
  If $B \subseteq A$, then $A$ \emph{contains} $B$. This is denoted as $A \supseteq B$.
  $$
    A \supseteq B \iff B \subseteq A
  $$
  A set $B$ is a \emph{proper subset} of a set $A$ if $A\subseteq B$ and $B\neq A$.
  This is denoted as $B \subset A$.
  $$
    B \subset A \iff (B\subseteq A) \land (B\neq A)
  $$
  If $B \subset A$, then $A$ \emph{properly contains} $B$. This is denoted as $A \supset B$.
  $$
    A \supset B \iff B \subset A
  $$
\end{definition}

\begin{theorem}
  If $A$ and $B$ are sets, then $A\subseteq B$ and $B\subseteq A$ if and only if $A=B$.
  $$
    (A\subseteq B) \land (B\subseteq A) \iff A=B
  $$
  \begin{proof}
    Let $A$ and $B$ be sets. 
    
    One has $A\subseteq B$ if and only if
    $$
      \forall x \ (x \in A \implies x \in B).
    $$
    One has $B\subseteq A$ if and only if
    $$
      \forall x \ (x \in B \implies x \in A).
    $$
    Then $A\subseteq B$ and $B\subseteq A$ if and only if
    $$
      \forall x \ (x \in A \iff x \in B).
    $$
    By the axiom of extensionality, one has $A=B$ if and only if
    $$
      \forall x \ (x \in A \iff x \in B).
    $$
    Therefore
    $$
      (A\subseteq B) \land (B\subseteq A) \iff A=B.
    $$
  \end{proof}
\end{theorem}

% empty set / nonempty
\begin{definition}
  A set $A$ is \emph{empty} if there are no elements in $A$, denoted $A=\emptyset$.
  $$
    A=\emptyset \iff \lnot \exists x \ (x\in A)
  $$
  A set $A$ is \emph{nonempty} if it is not empty, denoted $A\neq\emptyset$.
  $$
    A\neq\emptyset \iff \exists x \ (x\in A)
  $$
\end{definition}

\begin{axiom}[Regularity]
  Every nonempty set $A$ contains an element $x$ such that $A$ and $x$ are disjoint sets.
  $$
    \forall A \ ((\exists a \ (a \in A)) \implies \exists x \ (x \in A \land \lnot \exists z \ (z \in A \land z \in x)))
  $$
  Equivalently,
  $$
    \forall A \ (A \neq \emptyset \implies \exists x \ ((x \in A) \land (A \cap x = \emptyset)))
  $$
\end{axiom}

\begin{axiom}[Specification] 
  Given a set $A$ and a statement $P$, there is a set $B$ containing elements of $A$ satisfying $P$. That is
  $$
    \forall A \ \exists B \ \forall x \quad x \in B \iff ((x \in A) \land P)
  $$
\end{axiom}

% set builder notation
\begin{definition}
  \emph{Set builder notation} is a way of writing the set $B$ in the axiom of specification, namely
  $$
    B = \{ x\in A : P\}
  $$
\end{definition}

% without
\begin{definition}
  If $A$ and $B$ are sets, the set $A$ \emph{whithout} $B$ is the set existing by the axiom of specification
  $$
    A\setminus B = \{x\in A : x\notin B\}
  $$
\end{definition}

\begin{example}
  If $\{x,y\}$ and $\{x\}$ are sets, then the set $\{x,y\}\setminus\{x\}=\{y\}$ exists.
\end{example}

\begin{axiom}[Pairing]
  If $x$ and $y$ are sets, there exists a set containing $x$ and $y$ as elements.
  $$
    \forall x \ \forall y \ \exists A \quad (x \in A) \land (y \in A)
  $$
\end{axiom}

\begin{example}
  If $x$ and $y$ are sets, then the set $\{x,y\}$ exists.
  \begin{proof}
    Let $x$ and $y$ be sets. By the axiom of pairing, there is a set $A$ with $x\in A$ and $y\in A$. By the axiom of specification, the set
    $$
      B = \{ a\in A : (a = x) \lor (a = y) \}
    $$
    exists. If $b\in B$, then $b=x$ or $b=y$ so that $b\in\{x,y\}$ and $B\subseteq\{x,y\}$. Since $x\in A$ and $x=x$, we have $x\in B$. Since $y\in A$ and $y=y$, we have $y\in B$. Then $\{x,y\}\subseteq B$. It follows that $B = \{x,y\}$. Since $B$ exists, so does $\{x,y\}$.
  \end{proof}
\end{example}

\begin{example}
  If $x$ is a set, then the set $\{x\}$ exists.
  \begin{proof}
    Let $x$ be a set. Let $y=x$. Then the set $\{x,y\}$ exists. One can check that $\{x,y\}=\{x\}$.
  \end{proof}
\end{example}

\begin{axiom}[Union]
  For any set $\mathcal{A}$, there is a set containing every element that is an element of some element of $\mathcal{A}$.
  $$
    \forall \mathcal{A} \ \exists B \ \forall A \ \forall x \ (((A \in \mathcal{A}) \land (x \in A)) \implies x \in B)
  $$
\end{axiom}

% union
\begin{definition}
  For any set $\mathcal{A}$, the \emph{union} of the elements in $\mathcal{A}$ is the set existing by the axiom of specification
  $$
    \cup \mathcal{A} = \{x \in B : \exists A \ ((A \in \mathcal{A}) \land (x \in A))\}
  $$
  where $B$ is a set existing by the axiom of union. We often denote $\cup\mathcal{A}$ by
  $$
    \bigcup_{A\in\mathcal{A}} A
  $$
  If all elements of $\mathcal{A}$ are known, we may denote $\cup\mathcal{A}$ as the elements of $\mathcal{A}$ separated by the symbol $\cup$.
\end{definition}

\begin{example}
  If $\{x\}$ and $\{y\}$ are sets, then $\{x\}\cup \{y\} = \{x,y\}$.
  \begin{proof}
    Let $\{x\}$ and $\{y\}$ be sets. Let $\mathcal{A} = \{\{x\},\{y\}\}$.
    One can check that $\cup\mathcal{A} = \{x,y\}$.
  \end{proof}
\end{example}

% intersection
\begin{definition}
  For any set $\mathcal{A}$, the \emph{intersection} of the element in $\mathcal{A}$ is the set existing by the axiom of specification
  $$
    \cap\mathcal{A} = \{ x\in\cup\mathcal{A} : \forall A \ (A\in\mathcal{A} \implies x\in A)\}
  $$
  We often denote $\cap\mathcal{A}$ by
  $$
    \bigcap_{A\in\mathcal{A}} A
  $$
  If all elements of $\mathcal{A}$ are known, we may denote $\cap\mathcal{A}$ as the elements of $\mathcal{A}$ separated by the symbol $\cap$.
\end{definition}

\begin{example}
  If $\{x,y\}$ and $\{x\}$ are sets, then $\{x,y\}\cap\{x\} = \{x\}$.
\end{example}

\begin{theorem}[Laws of De Morgan]
  Let $X$ and $\mathcal{A}$ be sets such that $\cup\mathcal{A}\subseteq X$. Then
  $$
    X \setminus \cup \mathcal{A} = \bigcap_{A\in\mathcal{A}} (X\setminus A)
  $$
  and
  $$
    X \setminus \cap \mathcal{A} = \bigcup_{A\in\mathcal{A}} (X\setminus A)
  $$
  \begin{proof}
    Let $x\in X\setminus\cup\mathcal{A}$. Then $x\in X$ and $x\notin\cup\mathcal{A}$. Then for each $A\in\mathcal{A}$, one has $x\notin A$ and so $x\in X\setminus A$. Then $x\in \bigcap_{A\in\mathcal{A}} (X\setminus A)$. Hence
    $$
      X \setminus \cup \mathcal{A} \subseteq \bigcap_{A\in\mathcal{A}} (X\setminus A).
    $$
    Let $x\in\bigcap_{A\in\mathcal{A}} (X\setminus A)$. Then for each $A\in\mathcal{A}$, one has $x\in X\setminus A$ and so $x\in X$ and $x\notin A$. Then $x\notin\cup\mathcal{A}$ and $x\in X\setminus\mathcal{A}$. Hence
    $$
      \bigcap_{A\in\mathcal{A}} (X\setminus A) \subseteq X\setminus\cup\mathcal{A}.
    $$
    It follows that
    $$
      X \setminus \cup \mathcal{A} = \bigcap_{A\in\mathcal{A}} (X\setminus A).
    $$
    Let $x\in X\setminus\cap\mathcal{A}$. Then $x\in X$ and $x\notin\cap\mathcal{A}$. Then there is $A\in\mathcal{A}$ such that $x\notin A$. Then $x\in X\setminus A$ and so $x\in\bigcup_{A\in\mathcal{A}} (X\setminus A)$. Hence
    $$
      X \setminus \cap \mathcal{A} \subseteq \bigcup_{A\in\mathcal{A}} (X\setminus A).
    $$
    Let $x\in \bigcup_{A\in\mathcal{A}} (X\setminus A)$. Then there is $A\in\mathcal{A}$ such that $x\in X\setminus A$. Then $x\in X$ and $x\notin A$. Then $x\notin\cap\mathcal{A}$ and so $x\in X\setminus\cap\mathcal{A}$. Hence
    $$
      \bigcup_{A\in\mathcal{A}} (X\setminus A) \subseteq X \setminus \cap \mathcal{A}.
    $$
    It follows that
    $$
      X \setminus \cap \mathcal{A} = \bigcup_{A\in\mathcal{A}} (X\setminus A).
    $$
  \end{proof}
\end{theorem}

\begin{axiom}[Replacement]
  Given a set $A$ and a statement $P$, if for each $x\in A$ there is a unique set $y$ satisfying $P$, then there is a set containing all of the $y$s associated with all of the $x$s in $A$.
  $$
    \forall A \ ((\forall x \ (x \in A \implies \exists!y \ P)) \implies \exists B \ \forall x \ (x \in A \implies \exists y \ ((y \in B) \land P)))
  $$
\end{axiom}

\begin{definition}
  If $x$ is a set, the \emph{successor} of $x$ is the set $x \cup \{x\}$. We denote this set as $s(x)$.
\end{definition}

\begin{axiom}[Infinity]
  There exists a set $X$ containing an empty set such that if $x\in X$, then $s(x)\in X$.
  $$
        \exists X \ (\exists e \ (\forall z \ \lnot (z \in e) \land e \in X) \land \forall y \ (y \in X \implies s(y) \in X))
  $$
  Equivalently,
  $$
    \exists X \ ((\exists e \ (e\in X \land e=\emptyset)) \land \forall y \ (y \in X \implies s(y) \in X))
  $$
\end{axiom}

% empty set
\begin{theorem}
  There exists an empty set and it is unique. It is denoted by $\emptyset$.
  \begin{proof}
    (Existence) By the axiom of infinity, there exists a set $X$. By the axiom of specification, the set
    $$
      Z = \{x\in X : x\notin X\}
    $$
    exists. Since for any set $x$, either $x\in X$ or $x\notin X$, it follows that $Z$ is empty. Hence an empty set exists.
    
    (Uniqueness) Suppose $A$ and $B$ are empty sets. Then for any set $x$, one has $x\notin A$ and $x\notin B$. Then
    $$
      \forall x \quad x\in A \iff x\in B.
    $$
    It follows that $A=B$.
  \end{proof}
\end{theorem}

\begin{axiom}[Power set]
  For any set $A$, there is a set $S$ that contains every subset of $A$.
  $$
    \forall A \ \exists S \ \forall B \ (B \subseteq A \implies B \in S)
  $$
\end{axiom}

\begin{definition}
  For any set $A$, the \emph{power set} of $A$ is the set existing by the axiom of specification
  $$      
    \mathcal{P}(A) = \{B \in S : B \subseteq A \}
  $$
  where $S$ is a set existing by the axiom of power set.
\end{definition}

\begin{definition}
  If $x$ and $y$ are sets, the \emph{ordered pair} of $x$ and $y$ is the set $\{x,\{y\}\}$. We denote this set as $(x,y)$.
\end{definition}

\begin{definition}
  For any sets $A$ and $B$, the \emph{cartesian product} of $A$ and $B$ is the set of ordered pairs
  $$
    A\times B = \{x\in \mathcal{P}(A\cup\mathcal{P}(B)) : \exists a \ \exists b \ (a\in A \land b\in B \land x=(a,b))\}
  $$
  existing by the axioms of specification, union, and power set.
\end{definition}
    
\end{document}