\documentclass[12pt]{amsart}
\usepackage{amssymb,graphicx}
\theoremstyle{plain}    
%\numberwithin{chapter}{section} %% Comment out for sequentially-numbered
%\numberwithin{figure}{section} %% Comment out for sequentially-numbered
\newtheorem*{definition}{Definition}
\newtheorem*{example}{Example}
\newtheorem*{exercise}{Exercise}
\newtheorem*{conjecture}{Conjecture}
\newtheorem*{theorem}{Theorem}
\newtheorem*{lemma}{Lemma}
\newtheorem*{remark}{Remark}
\thispagestyle{empty}
\pagestyle{empty}
\begin{document}
\title{Set Theory Review}
\section{Basic Definitions}
The approach we will take is sometimes called "Naive Set Theory" because we do not attempt to give a rigorous definition of a set (this is considered impossible).  So we'll think of a set as a collection of objects, and consider a set $S$ to be well-defined if, given an arbitrary object $x$, we can determine whether or not it is in the set.
\par\vspace{0.3 cm}
\begin{definition}[subset] Let $A$ and $S$ be sets.  We say that $A$ is a \textbf{subset} of $S$ and write $A\subseteq S$ 
if every element of $A$ also belongs to $S$, that is,
\[
x\in A\Rightarrow x\in S
\]
Equivalently, we can say
\[
x\in S\quad\forall\quad x\in A
\]
or
\[
\nexists x\in A\quad\mbox{such that}\quad x\notin S
\]
\end{definition}

\par\vspace{0.5 cm}
\begin{definition}[equality of sets] Two sets $A$ and $B$ are defined to be equal if 
\[
A\subseteq B\quad\mbox{and}\quad B\subseteq A
\]
This means every element of $A$ belongs to $B$ and vice-versa.  
\end{definition}
The definition is a way of stating that $A$ and $B$ have the same elements, without getting tangled up in a definition of elementwise equality, which could be quite tricky considering that the elements of a set can be anything.
\par\vspace{0.5 cm}
\begin{definition}[proper subset] Let $A$ and $S$ be sets.  We say that $A$ is a \textbf{proper subset} of $S$ and write $A\subset S$ if 
\[
A\subseteq S\quad\mbox{and}\quad A\neq S
\]
\end{definition}
\par\vspace{0.5 cm}
\begin{definition}[null set] The \textbf{null set} or \textbf{empty set} denoted by
\[
\emptyset\quad\mbox{or}\quad \{\}
\]
is the set which contains no elements.
\end{definition}
\par\vspace{0.5 cm}
Note that $\emptyset\subseteq S$ for any set $S$ because
\[
\nexists x\in\emptyset\quad\mbox{such that}\quad x\notin S
\] 
\par\vspace{0.5 cm}
\begin{definition}[cardinality; equivalence] The \textbf{cardinality} of a set $S$, denoted by $n(S)$, is the number of elements in $S$.  Two sets $A$ and $B$ that have the same cardinality (that is, $n(A)=n(B)$), are said to be \textbf{equivalent} and we denote this by $A\sim B$.
\end{definition}
\par\vspace{0.5 cm}
\begin{definition}[power set] The \textbf{power set} of a set $S$, denoted by $\mathcal{P}(S)$, is the set of all possible subsets of $S$ (including $S$ itself and $\emptyset$).
\end{definition}
\par\vspace{0.5 cm}
A finite set $S$ has $2^{n(S)}$ subsets.
\par\vspace{0.5 cm}
\begin{example} Let $S=\{1,3,5\}$. Then the power set $\mathcal{P}(S)$ consists of the following $2^{n(S)}=2^3$ subsets:
\[
\mathcal{P}(S)=\{\{1\},\{3\},\{5\},\{1,3\},\{1,5\},\{3,5\},\{1,3,5\},\emptyset\}
\]
\end{example}

\section{Set Operations}
We define the following constructs:
\begin{definition}[set union] The $\textbf{union}$ of two sets $A$ and $B$, denoted by $A\cup B$, is the set consisting of all elements that belong to $A$, or belong to $B$, or belong to both $A$ and $B$:
\[
A\cup B=\{x | x\in A\quad\mbox{or}\quad x\in B\}
\]
\par\vspace{0.5 cm}
\end{definition}
\begin{definition}[set intersection] The $\textbf{intersection}$ of two sets $A$ and $B$, denoted by $A\cap B$, is the set consisting of all elements that belong to \textbf{both} $A$ and $B$:
\[
A\cup B=\{x | x\in A\quad\mbox{and}\quad x\in B\}
\]
\end{definition}
\par\vspace{0.5 cm}
\begin{definition}[set compliment] The $\textbf{compliment}$ of a set $A$, denoted by $A^c$, is the set consisting of all elements that \textbf{do not} belong to $A$.  Implicit in this definition is the notion of a universal set $U$, which may be given or may be clear from the context.  Somewhat more precisely, we can say that the compliment of $A$ relative to $U$, denoted by $U\setminus A$, consists of all elements of $U$ that do not belong to $A$:
\[
A^c=U\setminus A=\{x | x\in U\quad\mbox{and}\quad x\notin A\}
\]
\end{definition}
\par\vspace{0.5 cm}
The following useful identities, which relate these constructs, are know as the \textit{DeMorgan Laws}:
\[
(A\cup B)^c=A^c\cap B^c\quad\mbox{and}\quad (A\cap B)^c=A^c\cup B^c
\]
\par\vspace{0.5 cm}
\begin{definition}[Cartesian product] The $\textbf{Cartesian product}$ of a two sets $A$ and $B$, denoted by $A\times B$, is the set of all possible ordered pairs having the first entry belonging to $A$ and the second belonging to $B$:
\[
A\times B=\{ (a,b)\;|\; a\in A\quad\mbox{and}\quad b\in B\}
\]
\end{definition}
\section{Rigorous definition of a function}
Although we are all familiar with the notion of a function, the definitions one usually encouters early on are not sufficiently general for more abstract settings.  Here we present an equivalent definition that possesses the necessary generality:
\begin{definition}[function] If $A$ and $B$ are sets, a \textbf{function} mapping $A$ to $B$, denoted by $f:A\rightarrow B$, is a subset of the Cartesian product $A\times B$ with the property that every element of $A$ appears as the first element of exactly one ordered pair in the subset.
\end{definition}
In keeping with the spirit of casting Mathematics in the language of set theory, we note in passing that with this definition a function is in fact a set.  Denoting the subset of $A\times B$ that defines our function by $f$, we can write:
\[
f(a)=b\quad\Leftrightarrow\quad (a,b)\in f
\]
\par\vspace{0.5 cm}
A bit of thought should convince you that this definition covers everything the earlier definitions we encouter covers.
\par\vspace{0.5 cm}

\begin{definition}[image of a set under a function; range] If $f:A\rightarrow B$ is a function and $E\subseteq A$, the \textbf{image of $E$ under $f$}, denoted by $f[E]$, is defined to be the set of all $b\in B$ such that $(a,b)\in f$ for some $a\in E$:
\[
f[E]=\{b\;|\;(a,b)\in f\quad\mbox{for some}\quad a\in E\}
\]
\end{definition}

In the special case where $E=A$, $f[A]$ is called the \textbf{range} of $f$.  A function $f:A\rightarrow B$ with the property that $f[A]=B$ is said to be \textbf{onto} or \textbf{surjective}.
\par\vspace{0.5 cm}
Now we define the inverse image of a set under a function, which plays an important role in many areas:
\begin{definition}[inverse image of a set under a function; range] If $f:A\rightarrow B$ is a function and $G\subseteq B$, the \textbf{inverse image of $G$ under $f$}, denoted by $f^{-1}[G]$, is defined to be the set of all $a\in A$ such that $(a,b)\in f$ for some $b\in G$:
\[
f^{-1}[G]=\{a\;|\;(a,b)\in f\quad\mbox{for some}\quad b\in G\}
\]
\end{definition}
A function with the property that $f^{-1}[b]$ consists of a single element of $A$ for every $b$ in the range $f[A]$ is said to be \textbf{one-to-one} or \textbf{injective}.    
\par\vspace{0.3 cm}
A function that is both injective and surjective is called a \textbf{bijection} or a \textbf{one-to-one correspondence}.
\par\vspace{0.3 cm}
It is important to note that these are the only functions that have a \textbf{function inverse} defined by
\[
f:A\rightarrow B,\;f^{-1}:B\rightarrow A\quad\mbox{such that}\quad\left\{\begin{array}{lcl}
f^{-1}(f(x))=x &\forall& x\in A\\
f(f^{-1}(y))=y &\forall& y\in B\\
\end{array}\right.
\]
Be careful to distinguish between the function inverse $f^{-1}(y)$ and the inverse image $f^{-1}[G]$ for $G\subseteq B$.
\par\vspace{0.3 cm}
The function inverse only exists for a special class of functions, but the inverse image of any $G\subseteq B$ always exists for any function $f:A\rightarrow B$. 
\par\vspace{0.5 cm}
As it turns out, inverse images have the nicest set of properties one could ask for with regard to unions, intersections, 
and compliments:  If $f:A\rightarrow B$ is a function and $E,G\subseteq B$, the following identities hold:
\[
\begin{array}{c}\\
f^{-1}[E\cup G]=f^{-1}[E]\cup f^{-1}[G]\\\\
f^{-1}[E\cap G]=f^{-1}[E]\cap f^{-1}[G]\\\\
f^{-1}[E^c]=f^{-1}[B\setminus E]=\left(f^{-1}[E]\right)^c = A\setminus f^{-1}[E]\\
\end{array}
\]
In the preceding, for $E^c$ the universal set is understood to be $B$, and for $f^{-1}[E]$ the universal set is $A$:
\[
\begin{array}{c}\\
E^c=B\setminus E\\\\
(f^{-1}[E])^c=A\setminus f^{-1}[E]\\
\end{array}
\]
\par\vspace{0.3 cm}
The forward image $f[G]$ for $G\subseteq A$ does not quite have the same set of properties.  While it is true that
\[
f[E\cup G]=f[E]\cup f[G]\quad\mbox{for any}\quad E,G\subseteq A
\]
the most we can say for the intersection is
\[
f[E\cap G]\subseteq f[E]\cap f[G]\quad\mbox{for any}\quad E,G\subseteq A
\]
\end{document}



