\documentclass[12pt]{article}
 \usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry} 
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{lgarron}
\usepackage{color}
\usepackage{ stmaryrd }

\def\markatright#1{\leavevmode\unskip\nobreak\quad\hspace*{\fill}{#1}}
\def\qed{$\markatright{\square}$}


\def\d#1#2{{d_{#1}\Big({#2}\Big)}}
\def\dn#1#2{{d_{#1}({#2})}}
\def\dtn#1#2{{\tilde{d}_{#1}({#2})}}
\def\dt#1#2{{\tilde{d}_{#1}\Big({#2}\Big)}}
\def\rr{\rule{0cm}{0.6cm}}



\usepackage{fancyhdr}
\pagestyle{fancy}



\title{Math 171 WIM}
\author{Lucas Garron}
\fancyhead[CO,CE]{Math 171 WIM - Lucas Garron}
\fancyhead[LO,LE]{}

\def\und#1#2{{\underset{#1}{\underbrace{#2}}}}

\begin{document} 

\maketitle

\section*{Is there something bigger than infinity{?}}

If you have ever thought about the concept of ``infinity'', the preceding question might seem natural to ask. Perhaps the next inquiry might be ``Does that even make sense?'' or ``Can infinity even exist?'' Although they might seem like childish questions, the math behind answering these questions is rather subtle, and it was not until about a century ago that mathematicians developed a good system to describe concepts related to infinity. A modern mathematician might answer these questions like this:

\begin{itemize}
\item In short: Yes, there is something bigger than ``infinity''.
\item No, the question doesn't quite make sense to ask, because there isn't a single ``infinity''. However, we can define infinite things that exist about as much as the number 5 does.
\end{itemize}

The most important thing to note is there is not a single value of ``infinity''. Even though mathematicians use it as a shortcut to mean ``more than anything you can count to'', infinity is not really a number. Instead, it is more accurate to say that things \emph{can be infinite}. (You might express this by saying that the concept of infinity is actually an adjective, not a noun.) A better way to answer our questions might be:

\begin{itemize}
\item We can define things that are infinite.
\item Indeed, some infinite things are bigger than others. (In fact, if you name any infinite thing, there is \emph{always} a bigger one.)
\end{itemize}

Once we have these things, it can be instructive to think of different infinities existing, in the sense that each infinity is the size of something that is infinite.

\section*{Infinite Sets}
A set is simply a collection of things. You are probably familiar with the set containing the numbers you can use to count things: $\{0, 1, 2, 3, 4, ...\}$. This is the set of natural numbers, called $\N$. It seems clear that $\N$ should have an infinite number of elements; if we try to count the elements of $\N$ in order, we always have more to go, no matter how far we have counted.

First of all: if we can't write it all down, why should we be content in believing that $\N$ exists? There are a few reasons why $\N$ should be a set that exists, but it turns out simply to be useful to assume that it exists and that we can call it by a name (see Appendix A for a more thorough explanation of set theory). It turns out to cause no problems to think of $\N$ as existing, and once we've defined it and start using it, $\N$ is just as useful as the number $5$ in helping us use mathematics to describe things. This answers one of our questions: Yes, there things that are infinite, such as the set $\N$.

If we tried to describe the number of elements in $\N$, it could not be any finite number. If we take this as a defining property of infinite sets, there are also other infinite sets. A simple example might be th even natural numbers: $2\N = \{0, 2, 4, 6, ...\}$. Although we could never finish, we can count up to any particular element of $\N$ (or of $2\N$), and for this reason sets like this are called \emph{countable} infinite sets. There is also a special name for the number of elements in a countable set, and it is called ``aleph-nought'' and written as $\aleph_0$. Mathematicians consider $\aleph_0$ an infinite kind of number, and it is perhaps the closest number we have to the most common meaning of ``infinity'' (more on that later).

So, there are different infinite sets. Are they all countable? The surprising answer is that no, not all infinite sets are countable. A good example of this is a set you're probably familiar with: the set of real numbers, called $\R$. This set contains all the numbers on the real number line, such as $0$ and $-2.5$ and ${1\/3}$ and $\pi$ and $10^{100}$. Although we have to be careful to assume the real numbers can be collected into a set (see Appendix A), there are mathematically sound ways to do this, and $\R$ is a set.

If we try simple approaches to counting up the elements of $\R$, we run into issues: $\{0, 1, 2, ...\}$ skips all the numbers between $0$ and $1$, but if we spend infinitely long counting up the numbers from $0$ to $1$, we might not get anywhere else. If we try a few approaches, it seems that there is no way to count the elements of $\R$. But how could we know for sure that there is no way to do this, no matter how clever we are?

\section*{Cantor's Diagonalization Proof}
The famous way to show that $\R$ is uncountable this is called a \emph{diagonalization proof}, named for \emph{Georg Cantor}, who introduced it exactly for exactly this reason. It proves that there is a set that is infinite but ``even larger'' than $\N$, and therefore that there are different ``sizes of infinity''.

Cantor's proof uses a technique called \emph{proof by contradiction}: Suppose the real numbers are countable. If we can show that this leads to a contradiction (and it's generally a good to insist that contradictions should be impossible), our assumption must have been bad. This would mean that the real numbers are not countable.

In order to simplify the proof, let's say we don't have to list every real number, but only the ones from $0$ to $1$, i.e. the numbers belonging to the set $C = [0, 1]$. If we can count the real numbers, we should surely be able to count $C$. For this proof, $C$ is more convenient because we can write out every number uniquely as an infinite sequence of digits after the decimal point, and every such number is in $C$. (See Appendix B.)

What would it mean for $C$ to be countable? It would mean that we could write the numbers in $C$ down, one by one, in a single list: a first element, a second element, and so on, with every element at a position we can count to. If we assume that the $C$ are countable, there must be a particular ordering that does this. Let's call it $\{O_n\}$ and keep in mind that $\{O_n\}$ must exist if $C$ is countable, and that $\{O_n\}$ cannot change; it is a particular ordering that exists once we assume that it exists.

Now, let's write $O$. It doesn't matter what the order is, but as an example, let's suppose it was the following order:

\begin{center}
\begin{tabular}{cccccccccccc}
$O_1$ & $=$ & 0 & . & $\fbox{1}$ & 0 & 1 & 0 & 1 & 0 & 1 & ... \\
$O_2$ & $=$ & 0 & . & 1 & $\fbox{2}$ & 3 & 4 & 3 & 2 & 1 & ... \\
$O_3$ & $=$ & 0 & . & 9 & 9 & $\fbox{9}$ & 9 & 9 & 9 & 9 & ... \\
$O_4$ & $=$ & 0 & . & 3 & 8 & 4 & $\fbox{7}$ & 5 & 6 & 3 & ... \\
$O_5$ & $=$ & 0 & . & 2 & 1 & 9 & 3 & $\fbox{4}$ & 5 & 2 & ... \\
$O_6$ & $=$ & 0 & . & 6 & 5 & 4 & 5 & 6 & $\fbox{2}$ & 7 & ... \\
\end{tabular}
\end{center}

Now, we will take all the digits that are boxed, which lie on the ``diagonal'' of the list. We will use them to make a new number that differs from all the numbers that are already on the list. One way to do this would be to take the $n$th digit from the $n$th number of the list, and change the digit from its value $d$ to $9-d$ (which is always going to be a different digit). The process could be visualized like this:

\begin{center}
\begin{tabular}{cccccccccccc}
& & 0 & . & $\fbox{1}$ & $\fbox{2}$ & $\fbox{9}$ & $\fbox{7}$ & $\fbox{4}$ & $\fbox{2}$ & ... \\
& & &  & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ &  \\
$D$ & $=$ & 0 & . & 8 & 7 & 0 & 2 & 5 & 7 & ...
\end{tabular}
\end{center}

Let us call our new number $D$ ($= 0.870257...$). $D$ is clearly in $[0, 1]$ because every digit is still from $0$ to $9$. However, $D$ differs from the $O_n$ in the $n$th digit for every value of $n$. This means that $D \neq O_1$ (because they have representations that differ in the first digit, and there fore must be different numbers), and that $D \neq O_n$ for any $n \in \N$. This means that $D$ could not have been anywhere on our list. This is impossible if we believe our assumption. Therefore, our assumption must be false, and $[0, 1]$ is not countable.

Many people have tried to raise objections to this argument. Some of these miss the point that some representations have to be infinite. Others try to deny the conclusion that $D$ was not in the list, because we assumed that the list \emph{was} complete. There are some good articles on the internet countering such arguments. In any case most mathematicians agree that Cantor's proof can be made rigorous enough to be a valid proof of the uncountability of $[0, 1]$. There are also other proofs of this fact, and a lot of mathematical results rely on the fact that such a proof holds.


\section*{Cardinal and Ordinal Numbers}




\newpage
\section*{Appendix A: Motivations for Set Theory}

In mathematics, infinity is closely related to the idea of ``sets''. A set is basically a collection of various things, where the only thing that matters is whether something is in it or not. You can think of it as a list of things, except that it doesn't matter how often something is in the list, or in what order the list is. We could write $\{5, \pi, carrot\}$ to describe a set that contains $5$, $\pi$, and ``carrot'', but $\{\pi, carrot, \pi, 5\}$ would mean the same set. Anything can be in a set; even sets can be contained in other sets! If something is contained in a set, we say that it is an \emph{element} of the set, and once have a set where we can tell what is an element it (and what is not), we can give it a name. If we give our set with three elements the name $X$, we can say that

\begin{itemize}
\item $5 \in X$ ($5$ is \emph{in} $X$, or $5$ is \emph{an element of} $X$), but
\item $music \not\in X$ (the item $music$ is not in $X$).
\end{itemize}

We could try to describe every set from scratch, but many important sets have names that every mathematician uses: for example, the set of ``natural numbers'' is $\{0, 1, 2, 3, ...\}$ and it is written as $\N$.\\
Since a set is determined by what is in it, we could also describe a set using a sentence like ``something is in our set (let's call it $X$) if it is a counting number between $0$ and $100$''. A mathematician would write it like this\footnote{This is called \emph{set-builder notation}, which is a way to describe \emph{set comprehension}.}:

\[Y = \{i : 0 < i < 100\}\]

In this case, it means ``$Y$ is the set of all elements $i$ for which $0 < i < 100$ is true''. We can tell that $5 \in Y$, but
$1000 \not \in Y$. What about $carrot$? We'd have to be able to tell whether $0 < carrot < 100$.

This is an issue, but our definitions of sets so far have a bigger issue: Russell's Paradox. Russell's Paradox comes from the following definition:

\[Z = \{S: S \not\in S\}\]

$Z$ is a set. What's in it? Well, any set (let's call it $S$) is in $Z$ if \emph{$S$ does not contain itself}. How can a set contain itself? Well, $A = \{\{5\}\}$ (the set containing the set that contains $5$) contains the set $\{5\}$ (the set that contains $5$ itself), but $A$ doesn't contain $A$ itself. If we had a set that could be written as $X = \{X, 4, \pi\}$, then $X \in X$, so $X$ would contain itself. The main issue arises when we ask: is $Z$ in $Z$? If so, then it doesn't satisfy the definition it has to satisfy to be a member of itself (that $Z \not \in Z$). If not, then it \emph{does} satisfy the definition is has to satisfy to be a member of itself. Regardless of whether $Z$ is in itself or not, the opposite must be true because of the definition of $Z$ itself. Thus, we have a contradiction, and we cannot tell whether $Z$ is in $Z$. If we don't want to get in deep trouble, $Z$ cannot exist.

Although a lot of formal details have been left out, our exploration roughly parallels European mathematics in the late 1800's. Georg Cantor came up with formal ways to describe mathematical objects as sets, and used this to prove fundamental things that were previously vague or informal. Cantor's newly created ``set theory'' was wonderful, but in 1895, Bertrand Russell pointed out the paradox that is now named after him. ``Naive'' set theory was in trouble because it contained a fundamental contradiction that undermined all of it.

Mathematicians came up with a clever way around this. The most common approach, \emph{Zermelo-�Fraenkel set theory} (ZF) starts with just the empty set and has axioms that define what other sets exist. You can show that certain sets exist by building them from other sets, but you cannot define things like $Z = \{S: S \not\in S\}$ anymore; instead, you would have to build it out of sets $S$ that you already know to exist (e.g. if you have a set $T$, you could define $Z = \{S: (S \in T$ and $S \not\in S)\}$). If we want ZF not to have any contradictions, then $Z = \{S: S \not\in S\}$ is not a valid definition, and it is not a set. This also has other repercussions, like the fact that the ``set of all sets'' cannot exist. However, very many sets do exist, and  mathematicians believe that this approach doesn't produce any contradictions.
This is called the set of \emph{natural numbers}, which is called $\N$. It seems obvious that $\N$ is infinite, but what does that mean?

Generally, finite can be taken to mean ``bigger than anything finite''. You might say that the length of a line is infinite because it is longer than any finite length. In our case, $\N$ is infinite because you can count more elements of $\N$ than elements of any finite set (which you can do by counting to $0$ or $1$ or $2$... i.e. any element of $\N$ itself!). This concept is such a fundamental expression of being infinite that when mathematicians informally refer to ``infinity'', they generally mean $\N$ or ``a set with everything that we could if we counted far enough''. 

A mathematical way to define infinite sets in ZF would be to start by building some finite sets. $\{0\}$ is finite, and so is $\{0, 1\}$, and so is $\{0, 1, 2\}$, and so on. In each case, we can count the number of elements in the set. But what if we take this process ``to infinity''? Set theory provides a way for us to do this: there is an axiom (i.e. a rule) that says that there is a set that contains any element that is either in $\{0\}$, or in $\{0, 1\}$, or in $\{0, 1, 2\}$, and so on. In other words, this axiom lets us state that the set $\N$ exists. The axiom has a sensible name: the Axiom of Infinity.

This might seem a little silly. Isn't it cheating to say that something infinite like $\N$ exists just because we say it exists? Perhaps so. However, the careful approach of ZF requires us to build up all sets. It turns out that the only reasonable way to build up a set that contains an infinite number of elements... is to say that it can be done. This gives us a definition we can work with. As long as we can use it to produce a useful theory (ideally, one without contradictions), the Axiom of Infinity is useful, and modern mathematicians are generally content to assume that things are defined this way.

\newpage
\section*{Appendix B: Unique Representations of Reals}

Grade school students learning mathematics are often surprised (or repulsed) to be told that $0.9999... = 1$. There are numbers proofs suggesting why this should be true, such as:

\begin{center}
\begin{tabular}{rcl}
$X$ & $=$ & $0.99999...$ \\
$10X$ & $=$ & $9.99999...$ \\
$10X - X$ & $=$ & $9.00000....$ \\
$9X$ & $=$ & $9$ \\
$X$ & $=$ & $1$ \\
\end{tabular}
\end{center}

This tends to bring up heated arguments about what it means for a number to have a value, and what it means for two numbers to be the same. Here, we will assume that the reader accepts that the most reasonable ways to approach arithmetic with a real value for $0.99999...$ means that $0.99999... = 1$.





%\newpage\section*{Leftover}

%define bigger
%always bigger one

%bigger than everything




\end{document}