90 lines
2.8 KiB
TeX
90 lines
2.8 KiB
TeX
\section{Finite and Infinite Sets}
|
|
|
|
\begin{definition}
|
|
\begin{enumerate}
|
|
\item[]
|
|
\item The empty set $\emptyset$ is said to have $0$ \textbf{elements}.
|
|
|
|
\item If $n \in \N$, a set $S$ is said to have $n$ \textbf{elements} if there exists a bijection from the set $\N_n := \{1, 2, \dots, n\}$ onto $S$.
|
|
|
|
\item A set $S$ is said to be \textbf{finite} if it is either empty or it has $n$ elements for some $n \in \N$.
|
|
|
|
\item A set $S$ is said to be \textbf{infinite} if it is not finite.
|
|
\end{enumerate}
|
|
\end{definition}
|
|
|
|
\begin{theorem}[\textbf{Uniqueness Theorem}]
|
|
If $S$ is a finite set, then the number of elements is $S$ is a unique number in $\N$.
|
|
\end{theorem}
|
|
|
|
\begin{theorem}
|
|
The set $\N$ of natural numbers is an infinite set.
|
|
\end{theorem}
|
|
|
|
\begin{theorem}
|
|
\begin{enumerate}
|
|
\item[]
|
|
\item If $A$ is a set with $m$ elements and $B$ is a set with $n$ elements and if $A \cap B = \emptyset$, then $A \cup B$ has $m +n$ elements.
|
|
|
|
\item If $A$ is a set with $m \in \N$ elements and $C \subseteq A$ is a set with $1$ element, then $A \setminus C$ is a set with $m-1$ elements.
|
|
|
|
\item If $C$ is an infinite set and $B$ is a finite set, then $C \setminus B$ is an infinite set.
|
|
\end{enumerate}
|
|
\end{theorem}
|
|
|
|
\begin{theorem}
|
|
Suppose that $S$ and $T$ are sets and that $T \subseteq S$.
|
|
\begin{enumerate}
|
|
\item If $S$ is a finite set, then $T$ is a finite set.
|
|
|
|
\item If $T$ is an infinite set, then $S$ is an infinite set.
|
|
\end{enumerate}
|
|
\end{theorem}
|
|
|
|
\begin{definition}
|
|
\begin{enumerate}
|
|
\item[]
|
|
\item A set $S$ is said to be \textbf{denumerable} (or \textbf{countably infinite}) if there exists a bijection of $\N$ onto $S$.
|
|
|
|
\item A set $S$ is said to be \textbf{countable} if it is either finite or denumerable.
|
|
|
|
\item A set $S$ is said to be \textbf{uncountable} if it is not countable.
|
|
\end{enumerate}
|
|
\end{definition}
|
|
|
|
\begin{theorem}
|
|
The set $\N \times \N$ is denumerable.
|
|
\end{theorem}
|
|
|
|
\begin{theorem}
|
|
Suppose that $S$ and $T$ are sets and that $T \subseteq S$.
|
|
\begin{enumerate}
|
|
\item If $S$ is a countable set, then $T$ is a countable set.
|
|
|
|
\item If $T$ is an uncountable set, then $S$ is an uncountable set.
|
|
\end{enumerate}
|
|
\end{theorem}
|
|
|
|
\begin{theorem}
|
|
The following statements are equivalent:
|
|
\begin{enumerate}
|
|
\item $S$ is a countable set.
|
|
|
|
\item There exists a surjection of $\N$ onto $S$.
|
|
|
|
\item There exists an injection of $S$ into $\N$.
|
|
\end{enumerate}
|
|
\end{theorem}
|
|
|
|
\begin{theorem}
|
|
The set $\Q$ of all rational numbers is denumerable.
|
|
\end{theorem}
|
|
|
|
\begin{theorem}
|
|
If $A_m$ is a countable set for each $m \in \N$, then the union $A:= \bigcup\limits_{m=1}^{\infty} A_m$ is countable.
|
|
\end{theorem}
|
|
|
|
\begin{theorem}[\textbf{Cantor's Theorem}]
|
|
If $A$ is any set, then there is no surjection of $A$ onto the set $\mathcal{P}(A)$ of all subsets of $A$.
|
|
\end{theorem}
|