{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Infinities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "A set can be either **finite** or **infinite**, meaning it has a finite number of elements or an infinite number."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "The set of natural numbers is the set containing the whole positive numbers:\n",
    "\n",
    "$$ \\mathbb{N} = \\{1, 2, 3, 4, 5, \\ldots \\} $$\n",
    "\n",
    "Sometimes we include zero and denote this with a subscript zero on the $\\mathbb{N}$:\n",
    "\n",
    "$$ \\mathbb{N}_0 = \\{ 0, 1, 2, 3, 4, 5, \\ldots \\} $$\n",
    "\n",
    "Note it is an infinite set."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "We have a natural ordering of the natural numbers, in the sense that everyone knows that $1 < 2$ and $2 < 3$ and therefore $1 < 3$.\n",
    "\n",
    "The set doesn't know about this ordering, we impose it on the set.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "A finite set can be put into a one-to-one correspondance with a single subset of $ \\mathbb{N} $ starting at $1$ and containing consecutive numbers.\n",
    "\n",
    "For example, the set containing my fingers can be put into a one-to-one correspondance with the subset $ \\{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \\} $.\n",
    "\n",
    "This is a very formal way to think of counting."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "## Counting infinity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "We can apply the same idea to infinite sets.\n",
    "\n",
    "Suppose we could put a set in one-to-one correspondance with the natural numbers: would you agree they have the same size?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "Take the even natural numbers $ 2 \\mathbb{N} = \\{ 2, 4, 6, 8, 10, \\ldots \\} $:\n",
    "\n",
    "|$\\mathbb{N}$|$2 \\mathbb{N}$|\n",
    "|---:|---:|\n",
    "|     $1$|     $2$|\n",
    "|     $2$|     $4$|\n",
    "|     $3$|     $6$|\n",
    "|     $4$|     $8$|\n",
    "|$\\vdots$|$\\vdots$|\n",
    "\n",
    "Every element in $\\mathbb{N}$ is paired with a distinct element of $2 \\mathbb{N}$ - no two elements of $\\mathbb{N}$ are paired with the same element of $2 \\mathbb{N}$ - and vice versa.\n",
    "\n",
    "The sets must have the same number of elements in some sense.\n",
    "\n",
    "Does this work for all infinite sets?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "## Real numbers\n",
    "\n",
    "Let's look at the set of real numbers $\\mathbb{R}$.\n",
    "\n",
    "Take the number line - a line where two points have been marked as 0 and 1:\n",
    "\n",
    "![The number line](https://upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Real_number_line.svg/500px-Real_number_line.svg.png)\n",
    "\n",
    "Any point on the that line represents a real number which is it's distance from 0.\n",
    "\n",
    "You can measure the distance because 1 has been marked off.\n",
    "\n",
    "The set $\\mathbb{R}$ is the set of all of these numbers.\n",
    "\n",
    "It includes $-123$, $-1.55$, $0$, $0.00001$, $\\frac{1}{3}$, $\\pi$, $1000000$, $1234567.89$ and all the other numbers (except complex numbers, obvs).\n",
    "\n",
    "It's an infinite set."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "## Different infinities\n",
    "\n",
    "Here's the punchline of this section: $\\mathbb{R}$ and $\\mathbb{N}$ are not the same size even though they're both infinite.\n",
    "\n",
    "We'll prove this by contradiction: suppose they are the same size.\n",
    "\n",
    "Then we put them into one-to-one correspondance - for every natural number we can write a single, unique real number beside it that it is paired with.\n",
    "\n",
    "Imagine the list of these numbers (as above with $\\mathbb{Z}$ - I'll pick a few real numbers myself just as an example.\n",
    "\n",
    "I'll write the real numbers as having an infinite number of decimal places after them, so I'll write $1$ as $1.00000\\ldots$.\n",
    "\n",
    "|$\\mathbb{N}$|$\\ $|$\\mathbb{R}$            |\n",
    "|:----------:|:--:|:----------------------:|\n",
    "|         $1$|$\\ $|$0.12352623623324\\ldots$|\n",
    "|         $2$|$\\ $|$2.23425617987665\\ldots$|\n",
    "|         $3$|$\\ $|$9.84575574572342\\ldots$|\n",
    "|         $4$|$\\ $|$2.12452623623324\\ldots$|\n",
    "|    $\\vdots$|$\\ $|$\\vdots$                |\n",
    "\n",
    "Now, if $\\mathbb{N}$ and $\\mathbb{R}$ have been paired off then every natural number is paired with a unique real number and vice versa.\n",
    "\n",
    "Here's the contradiction: I can find a real number that hasn't been paired.\n",
    "\n",
    "Let's write that nubmer down - start with a 0 and a decimal point:\n",
    "\n",
    "$$0.$$\n",
    "\n",
    "Now take the first decimal place of the real number paired with $1$.\n",
    "If it's a 0, write a 1 down, if it's a 1 write a 2 down, and so on.\n",
    "If it's a 9 then write a 0 down.\n",
    "So just add 1 (mod 10) to the first decimal place in the number paired with the natural number 1.\n",
    "\n",
    "The second decimal place of the new number will be the second decimal place of the number paired with the natural number 2 plus 1 mod 10.\n",
    "\n",
    "The third will be the third decimal place of the number paired with 3, and so on.\n",
    "\n",
    "This guarantees that the new number is different from all the numbers paired with the natural numbers.\n",
    "\n",
    "So there is an extra real number and you don't have a one-to-one correspondance between the natural and real numbers.\n",
    "\n",
    "The infinite set $\\mathbb{R}$ is bigger than the infinite set $\\mathbb{N}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "## Does this matter?\n",
    "\n",
    "![Alan Turing](https://upload.wikimedia.org/wikipedia/commons/thumb/a/a1/Alan_Turing_Aged_16.jpg/176px-Alan_Turing_Aged_16.jpg)\n",
    "\n",
    "It does - Turing used this basic argument to prove that there are some problems that computers can't solve.\n",
    "\n",
    "Consider the problem of determining if a given whole number is a prime number.\n",
    "We know of algorithms that will answer this question: given enough time and memory the algorithm can output True if the whole number you give it is a prime and False otherwise and it will finish its job in a finite number of steps.\n",
    "\n",
    "However, there is no algorithm that takes as input any program (which is just a finite string of 0's and 1's) and outputs True if the program halts in a finite number of steps and False otherwise in a finite number of steps.\n",
    "This is called the halting problem and it os undecidable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "\n",
    "## End"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}