discrete Project Roshdy

\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{Mohamed Roshdy \\ \\ The American University in Cairo}
%\email{@aucegypt.edu}
%\address{The American University in Cairo}


\begin{document}
\maketitle

\textcolor{red}{}

\textbf{Abstract.}

\textcolor{blue}{In this paper, we will begin by a summary of Cantor's life and highlights of his most significant theorems. Then we will introduce some definitions about sets and countability of sets. After that, we will prove one of Cantor's theorem and two corollaries using the previous theorem.}

\section{Cantor's Life}

\textcolor{blue}{ Georg Cantor was born in Saint Petersburg on the 3rd of March 1845 to Danish parents. His mother Marie came from a family famous for music. His father Georg Woldemar was a very successful businessman who helped his son in may situations with his great advice, however, he also tried to convince him to study engineering rather than mathematics as he thought it was more promising. His education was not much different of the education of all the great minds, he showed early signs of excellence, which resulted in an early recognition of his talent at a very early age. At first, he received private tutoring lessons in Saint Petersburg, then he attended private school in Frankfurt at the Darmstadt nonclassical school, that was before he got into the Wiesbaden Gymnasium in 1860. He graduated from the Realshule in Darmstadt in 1862 to begin his university studies. He actually started his university education as an engineering student, he studied engineering for two years at Höheren Gewerbschule, before switching to the Swiss Federal Politechnic to study mathematics, then after his father died he transferred to the University of Berlin. In Berlin, he attended lectures by some great mathematicians. His huge interest in math affected his earliest work hugely. After receiving his PH.D he left Berlin to work as a Privatdozent at Hale University to work under Eduard Heine the professor of mathematics there. Some people claimed that the reason for Cantor’s groundbreaking work can be actually traced back to his very early post graduation publications. As a matter of fact, one could actually find traces of his early work in his later work. His first paper titled “On a theorem concerning the trigonometric series” was completed and published in march of 1870. In this paper he presented Cantor’s Uniqueness Theorem, which states that every function can only have a maximum of one representation by a trigonometric series. In 1871, he strengthen his theorem by proving that it holds even if the series diverges at a finite number of points in any given interval, this result was attempted by a handful of known mathematicians before him, but none of them could prove to be true. His second paper, which was published in 1872, extended the results of his first paper and strengthened it further. He proved that his theorem holds even if the trigonometric series diverges at an infinite number of points. In the same year, he provided a definition of real numbers, which earned him a promotion to associate professor at Halle University in the same year. Later in the same year, Cantor met Richard Dedekind for the first time. Richard was a mathematics professor at the Technische Hochshule at Brunswick. He previously published a paper related to the topic of real numbers. Cantor and him exchanged letters over the years. In one of their letters in 1973, Cantor sent a letter to Dedekind, which contained a proof, which states that the real numbers cannot be put in one-to-one correspondence with the natural numbers. Two days later, Cantor sent him a simpler proof, Dedekind approved of the proof. Cantor’s work in the period between 1873-1884 led to the creation of the set theory. The origins of set theory is traced back to some of his earlier work, mainly a single paper he published in 1874 titled “On a Property of the Collection of All Real Algebraic Numbers.”. The paper was published just before Cantor turned 30 years old, this shows how successful he was at such a young age. His paper introduced three main points, which are the set of algebraic numbers is countable, in every interval [a,b] there are infinitely many numbers not included in sequence, which means that the set of rea numbers are uncountably infinite. Cantor provided a definition of the concept of a set, his definition basically stated that a set is a collection of elements. He also provided the concept of countability, which stated that a countable set has the same cardinality as one of the subsets of the set of the natural numbers, which led to the definition of a countable set. He defines a set S to be countable if there exists an injective function from it (S) to the set of Natural numbers. In 1873, Cantor proved that the set of rational numbers are countable. A year later in 1874, Cantor proved that the set of real algebraic numbers are countable. In 1874, Cantor published his most fruitful work regarding the topic of countability, he published the paper that proves the uncountability of real numbers, which he was exchanging letter with Dedekind as mentioned earlier. In 1891, Cantor presented his diagonal argument, which is a simpler proof of the uncountability of the set of real numbers. Cantoor’s gave a definition of infinite sets, stating that a set is infinite only of there is a one-toone correspondence between A and a set X which is a proper set oof A. in 1878, Cantor provided a definition of cardinal numbers. Cantor also introduced the continuum hypothesis. He spent many years of his life attempting to prove the truth of his continuum hypothesis, he tried many different strategies, provided many proofs, but all of them were false. Cantor suffered his first serious mental breakdown in 1884, he had just returned from a trip to paris, most historians believe the breakdown occurred as a result of his dispute with Leopold Kronecker who had been refusing Cantor’s work and trying to hold him back. After his 1884 hospitalization, there was no record to show that he has been hospitalized again until 1899. That was the year his youngest son died and he reportedly lost his passion for mathematics then. In 1903, Julios Konig presented a paper which attempted to disprove the basic tenants of transfinite set theory, Cantor descriped it as public humiliation and it shook his believe in God, after he was a devout Christian his whole life. He was hospitalized many times in the following two to three years, he spent the last 20 years in depression and bad mental health until he died in 1918 of a heart attack. He never left Halle University.
.}


\section{Cantor's Theorem}

\textcolor{red}{}

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}{}
\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 of real numbers.
   \item The empty set is a subset of any other set.
\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}.
\end{definition}

\begin{example}
\textcolor{blue}{let $A=\{5,10\}$ then $\mathcal{P}(A)=\{\{5\},\{10\},\phi, \{5,10\}\}$ \\
                     $B=\{b\}$ then $\mathcal{P}(B)=\{b,\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}{ 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 the domain of a function is $\mathbb {N}$ and the codomain is $\mathbb {Z}$,  where $f \colon \mathbb {N} \to \mathbb {Z} $ defined in the next line: \\
\(f(n) =\[ \begin{cases}
     \frac{-n}{2} & $ when n is even$\\
     \frac{n+1}{2} & $when n is odd$\\
  \end{cases}
\]\\
Both branches of the function are both bijective in this domain, so there is a bijection from $\mathbb {N}$ to $\mathbb {Z}$, so we proved that the set of integers is countably infinite.
\end{proof}
}

\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 deriving an injective function $g:S\to \mathcal{P}(S)$ where  $\(f(x)=\{x\}$ and as the codomain (power set) contains all the elements of the domain, all elements in the domain have exactly one image.

\textcolor{red}{}

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}{First we assume that h is bijective for the sake of contradiction, so by definition it is surjective. Let us define a new set where:\\
$B=\{s\in S \land s\notin h(x)\}$, so $B\in\mathcal{P}(S) $ and using surjectivity, $B=h(x)$ for some $x$ in the domain, and this creates a contradiction 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}{Applying Cantor's theorom, $|\mathbb{N}|<|\mathcal{P}(\mathbb{N})|$, so there is injection and there is no bijection $f\colon \mathbb{N} \to \mathcal{P}(\mathbb{N})$, for a set to be uncountable, there must not be any bijection, 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}{Applying Cantor's theorom, $|S| < |\mathcal{P}(S)|$. Therefore,  whenever we get the power set of a set, we will have greater cardinality. if we keep getting the power set, we will have infinte secuence where the $nth term =\mathcal{P}(n-1) $.\\
\\
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}