\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{Omar Elsayed \\ ID: 900183884 \\ 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 containing all the subsets from the set $S$\\ $\mathcal{P}(S)=\{x\mid x\subseteq S \}$}.
\end{definition}

\begin{example}
\textcolor{blue}{let $A=\{1,2,3\}$ then $\mathcal{P}(A)=\{\phi,\{1\},\{2\},\{3\}, \{1,2\}\, \{1,3\}\, \{2,3\}\, \{1,2,3\}\}$ \\
                     $B=\{0\}$ then $\mathcal{P}(B)=\{\phi, 0 \}$  }
\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}{ $bijective$ 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}{ $injective$ 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}{we can find at least one bijective function from the Natural Numbers set to this set. It means that: $|\mathbb{N}| = |S|$}
\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}{Suppose the domain of the function is the set of the Natural Numbers $\mathbb {N}$ and suppose the codomain as the set of integers $\mathbb {Z}$, we are trying to find a bijective function such that $f \colon \mathbb {N} \to \mathbb {Z} $ : \\
\(f(x) =\[ \begin{cases}
     \frac{x+1}{2}, & $x is odd$\\
     \frac{-x}{2}, & $x is even\\
  \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}{For the sake of contradiction, assume that h is a surjective function. Now, suppose that there is a set called $A$ that contains all the elements in the set $S$ and these elements have no pre-images in the domain.\\
$A=\{s\in S \land s\notin h(x)\}$, so $A\in\mathcal{P}(S) $ and we know from our assumption that h is a surjective funtion, $A=h(x)$ for some elements in the domain. Thus, we hit a contradiction as we assumed that $A$ only contains the elements which are in $S$ but do not have images in the codomain. Therefore $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 $A$ is an uncountable set, we need to prove that there is no bijection from the set of Natural Numbers \mathbb{N} to the set $A$. Now, we need to show that there is no bijection from the set of Natural Numbers to the power set of the Natural Numbers $\mathcal{P}(\mathbb{N})$. By using Cantor's theorem, given any set $S$, $|S| < |\mathcal{P}(S)|$. Then we can apply this rule for the set of the Natural Numbers as follows: $|\mathbb{N}|<|\mathcal{P}(\mathbb{N})|$ This means that $|\mathbb{N}|\leq|\mathcal{P}(\mathbb{N})|$ and $|\mathbb{N}|\neq|\mathcal{P}(\mathbb{N})|$ Thus, we find an injection function from the set of the Natural Numbers to the power set of Natural Numbers, but we cannot find a bijection between them. It means that, $f\colon $\mathbb{N} \to \mathcal{P}(\mathbb{N})$ Thus, 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}