discrete Project

\documentclass[12pt, a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsthm}
\usepackage{amsmath, amssymb}
\usepackage{xcolor}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}

\parindent=0mm
\parskip=1.9mm
\linespread{1.1}

\renewcommand\qedsymbol{$\blacksquare$}
\renewcommand{\restriction}{\mathord{\upharpoonright}}

\binoppenalty=\maxdimen
\relpenalty=\maxdimen

\title{Cantor's Paradise}
\author{Your Name \\ ID: xxxxxxx \\ The American University in Cairo}
%\email{@aucegypt.edu}
%\address{The American University in Cairo}


\begin{document}
\maketitle

\textcolor{red}{Dear student, remarks in RED like this one is meant to guide you through the project and you have to delete them at the end. Please write this paper in your own words and style, using well-formed complete English sentences and correct use of punctuation marks.\\
As described below, this paper has two sections: Cantor's Life and Cantor's Theorem. Your task is to complete and develop these two sections.}

\textbf{Abstract.}

\textcolor{red}{Write here a brief summary describing your article in 4-6 lines. You write the abstract once you finish the paper.}

\section{Cantor's Life}

\textcolor{blue}{In this section, we are asked to introduce us to the life of Cantor, his ideas, mental health, and final years by summarising the article "The Nature of Infinity - and Beyond".
Please ignore the technical mathematics in the article, just extract a story about the life and work of Cantor in 2 to 3 pages only.}

We will present the life story of Cantor based on Veisdal's article \cite{Veisdal}.

\textcolor{red}{You have to cite any references you use in this paper, see the line above. Check the end of this latex code to see how to add more references.}

\section{Cantor's Theorem}
\textcolor{red}{In this section you are asked to prove Cantor's Theorem (see below). Introduce all the definitions and notation you need here to state and prove the theorem. For example, you need to define a set, a subset, the power set of a set, an injective function, a bijective function, $|A|<|B|$, etc.}

\textcolor{red}{Whenever you need to write mathematical symbols you have to write them between dollar signs. For example see the latex code for:\\
$x \leq y$ and $a \in A$ and $b\notin A$ and $x^2, x^{27}, a_1, a_2, \ldots, a_n$ and
$f:A \to B$ and $A\subseteq B$ and
$\mathbb{N, Z, Q, R}$.}

We start by defining a set.

\begin{definition}\rm
A \textit{set} is a collection of objects.
\end{definition}

\begin{definition}\rm
Let $A$ and $B$ be sets. We say that $A$ is a \textit{subset} of $B$, and write $A
\subseteq B$ if \textcolor{blue}{$\forall x (x\in A \implies x\in B)$ }
\end{definition}

\begin{example}\rm The following are examples of subsets.
\textcolor{red}{[Give more examples of subsets]}
\begin{enumerate}
    \item The set of natural numbers is a subset of the set of integers.
    \item The set of integers is a subset of the set rational numbers
    \item The set of rational numbers is a subset of the real numbers
\end{enumerate}
\end{example}

We are now ready to introduce the notion of a power set.
\begin{definition}\rm
The \textit{power set} $\mathcal{P}(S)$ of a set $S$ is \textcolor{blue}{the set that contains the all the subsets of the subset $S$\\ $\mathcal{P}(S)=\{x\mid x\subseteq S \}$}.
\end{definition}

\begin{example}
\textcolor{blue}{let $A=\{1,2\}$ then $\mathcal{P}(A)=\{1,2,\phi, \{1,2\}\}$ \\
                      $B=\{1\}$ then $\mathcal{P}(B)=\{1,\phi \}$  }
\end{example}

\begin{definition}\rm Let $A$ and $B$ be sets.
\begin{itemize}
    \item We say that the cardinality of $A$ is equal to the cardinality of $B$, and write $|A|=|B|$, if there is a \textcolor{blue}{ $bijection$ function f \colon A \to B}

    \item We say that the cardinality of $A$ is less than or equal to the cardinality of $B$, and write $|A|\leq |B|$, if there is an \textcolor{blue}{ $injection$ function f \colon A \to B }

    \item We say that the cardinality of $A$ is strictly less than the cardinality of $B$, and write $|A|<|B|$, if \textcolor{blue}{$|A|\leq|B| \hspace {0.1cm} and \hspace {0.1cm} |A|\neq|B|$}.

    \item We say a set is \textit{countably infinite} if \textcolor{blue}{$|\mathbb{N}|=|S|$ (there is a bijection function from the set of natural numbers $\mathbb {N}$ to the set)}
\end{itemize}
\end{definition}

We will now show that the set of integers is a countably infinite set.

\begin{theorem}
The set of integers $\mathbb{Z}$ is countably infinite.
\end{theorem}

\begin{proof}
\textcolor{blue}{Let Assume the domain of a function is $\mathbb {N}$ and its codomain is $\mathbb {Z}$, we can obtain a bijection function where $f \colon \mathbb {N} \to \mathbb {Z} $ as following: \\
\(f(n) =\[ \begin{cases}
      \frac{-n}{2} & $n is even$\\
      \frac{n+1}{2} & $n is odd$\\
   \end{cases}
\]\\
It is clear that the two branches of the function are both bijective keeping in mind the domain and the codomain, so there is a bijection from $\mathbb {N}$ to $\mathbb {Z}$, which means that the set of integers is countably infinite.
\end{proof}
}
We will now present the main theorem of the article, Cantor's Theorem, which states that it is impossible to have a bijection between any set and its powerset.

\begin{theorem}[Cantor's Theorem]
Let $S$ be any (finite or infinite) set. Then $|S|<|\mathcal{P}(S)|$.
\end{theorem}
\begin{proof}
Let $S$ be any set.

First, we will show that $S\leq \mathcal{P}(S)$ by constructing an injective function $g:S\to \mathcal{P}(S)$ where f is the set of identity function:  $\(f(x)=\{x\}$ and as no element is repeated in the domain and the codomain (power set) contains all the elements of the set, every element in the domain has exactly one image.

\textcolor{red}{[continue ...]}

Second, we will prove that $|S|\neq |\mathcal{P}(S)|$. For the sake of contradiction, assume that there is a bijection $h:S\to \mathcal{P}(S)$.

\textcolor{blue}{Suppose that h is surjective for the sake of contradiction, so it is surjective. Let assume a set containing all the elements in the set itself, but it is not in an image of the function where:\\
$B=\{s\in S \land s\notin h(x)\}$, so $B\in\mathcal{P}(S) $ and as h is surjective, $B=h(x)$ for some elements in the domain, and this contradicts our assumption that $B$ contains only the elements which is in $S$ and not in the range of the function, so $h$ is not surjective}

Therefore, we have shown that $|S| < |\mathcal{P}(S)|$.
\end{proof}



From Cantor's theorem we can deduce the following consequences.



\begin{corollary}
The power set of the natural numbers is uncountable.
\end{corollary}

\begin{proof}
\textcolor{blue}{To prove that a set is uncountable we first prove that there is no bijection from the set of the natural numbers to the set. Using Cantor's theorom, $|S| < |\mathcal{P}(S)|$. Then $|\mathbb{N}|<|\mathcal{P}(\mathbb{N})|$, which means there is injection and there is no bijection $f\colon \mathbb{N} \to \mathcal{P}(\mathbb{N})$, therefore the power set of the natural numbers is uncountable.}
\end{proof}


\begin{corollary}
There is an infinite sequence $A_0, A_1, A_2, \ldots$ of infinite sets such that $|A_i|<|A_{i+1}|$ for all $i\in \mathbb{N}$. In other words, there is an infinity hierarchy of infinities.
\end{corollary}
\begin{proof}
\textcolor{blue}{Using Cantor's theorom, $|S| < |\mathcal{P}(S)|$. Therefore,  the power set of the power set of the set has cardinality that is strictly bigger than the power set of the set, and we keep doing this to have infinte secuence where every element is the power set of the previous element.\\
$|S| < |\mathcal{P}(S)|<|\mathcal{P}(\mathcal{P}(S))|<|\mathcal{P}(\mathcal{P}(\mathcal{P}(S)))|<........$\\
Therefore, we proved that there is an infinite sequence $A_0, A_1, A_2, \ldots$ of infinite sets such that $|A_i|<|A_{i+1}|$ for all $i\in \mathbb{N}$
}
\end{proof}


\begin{thebibliography}{9}

\bibitem{Veisdal}
Jorgen Veisdal. \textit{The Nature of Infinity - and Beyond}. Medium, 2018.

\end{thebibliography}

\end{document}