• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# discrete Project Roshdy

Maco153 Dec 9th, 2019 126 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. \documentclass[12pt, a4paper]{article}
2. \usepackage[utf8]{inputenc}
3. \usepackage{amsthm}
4. \usepackage{amsmath, amssymb}
5. \usepackage{xcolor}
6.
7. \theoremstyle{plain}
8. \newtheorem{theorem}{Theorem}[section]
9. \newtheorem{corollary}[theorem]{Corollary}
10. \newtheorem{definition}[theorem]{Definition}
11. \newtheorem{example}[theorem]{Example}
12.
13. \parindent=0mm
14. \parskip=1.9mm
16.
17. \renewcommand\qedsymbol{$\blacksquare$}
18. \renewcommand{\restriction}{\mathord{\upharpoonright}}
19.
20. \binoppenalty=\maxdimen
21. \relpenalty=\maxdimen
22.
24. \author{Mohamed Roshdy \\ \\ The American University in Cairo}
25. %\email{@aucegypt.edu}
26. %\address{The American University in Cairo}
27.
28.
29. \begin{document}
30. \maketitle
31.
32. \textcolor{red}{}
33.
34. \textbf{Abstract.}
35.
36. \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.}
37.
38. \section{Cantor's Life}
39.
41. .}
42.
43.
44. \section{Cantor's Theorem}
45.
46. \textcolor{red}{}
47.
48. We start by defining a set.
49.
50. \begin{definition}\rm
51. A \textit{set} is a collection of objects.
52. \end{definition}
53.
54. \begin{definition}\rm
55. Let $A$ and $B$ be sets. We say that $A$ is a \textit{subset} of $B$, and write $A 56. \subseteq B$ if \textcolor{blue}{$\forall x (x\in A \implies x\in B)$ }
57. \end{definition}
58.
59. \begin{example}\rm The following are examples of subsets.
60. \textcolor{red}{}
61. \begin{enumerate}
62.   \item The set of natural numbers is a subset of the set of integers.
63.   \item The set of integers is a subset of the set of real numbers.
64.   \item The empty set is a subset of any other set.
65. \end{enumerate}
66. \end{example}
67.
68. We are now ready to introduce the notion of a power set.
69. \begin{definition}\rm
70. 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}.
71. \end{definition}
72.
73. \begin{example}
74. \textcolor{blue}{let $A=\{5,10\}$ then $\mathcal{P}(A)=\{\{5\},\{10\},\phi, \{5,10\}\}$ \\
75.                     $B=\{b\}$ then $\mathcal{P}(B)=\{b,\phi \}$  }
76. \end{example}
77.
78. \begin{definition}\rm Let $A$ and $B$ be sets.
79. \begin{itemize}
80.   \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}
81.
82.   \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 }
83.
84.   \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|$}.
85.
86.   \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}
87. \end{itemize}
88. \end{definition}
89.
90. We will now show that the set of integers is a countably infinite set.
91.
92. \begin{theorem}
93. The set of integers $\mathbb{Z}$ is countably infinite.
94. \end{theorem}
95.
96. \begin{proof}
97. \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: \\
98. \(f(n) =$\begin{cases} 99. \frac{-n}{2} &  when n is even\\ 100. \frac{n+1}{2} & when n is odd\\ 101. \end{cases} 102.$\\
103. 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.
104. \end{proof}
105. }
106.
107. \begin{theorem}[Cantor's Theorem]
108. Let $S$ be any (finite or infinite) set. Then $|S|<|\mathcal{P}(S)|$.
109. \end{theorem}
110. \begin{proof}
111. Let $S$ be any set.
112.
113. 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.
114.
115. \textcolor{red}{}
116.
117. 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)$.
118.
119. \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:\\
120. $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}
121.
122. Therefore, we have shown that $|S| < |\mathcal{P}(S)|$.
123. \end{proof}
124.
125.
126.
127. From Cantor's theorem we can deduce the following consequences.
128.
129.
130.
131. \begin{corollary}
132. The power set of the natural numbers is uncountable.
133. \end{corollary}
134.
135. \begin{proof}
136. \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.}
137. \end{proof}
138.
139.
140. \begin{corollary}
141. 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.
142. \end{corollary}
143. \begin{proof}
144. \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)$.\\
145. \\
146. 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}$
147. }
148. \end{proof}
149.
150.
151. \begin{thebibliography}{9}
152.
153. \bibitem{Veisdal}
154. Jorgen Veisdal. \textit{The Nature of Infinity - and Beyond}. Medium, 2018.
155.
156. \end{thebibliography}
157.
158. \end{document}
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top