notebooks/ordinal_arithmetic_basics.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ordinal arithmetic: the basics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This a brief (and non-rigorous, non-set-theoretic) overview of ordinals and their arithmetic. All the code examples here use the [`transfinite`](https://github.com/ajcr/transfinite) module.\n",
    "\n",
    "## What are ordinals?\n",
    "\n",
    "*Finite* ordinals can be considered to be very much like positive integers. Ordinals can be used to count, the ordinal $1$ denotes one 'stick'. The ordinal $2$ denotes two successive sticks, and so on:\n",
    "\n",
    "$$ 1 = | $$\n",
    "$$ 2 = |\\ | $$\n",
    "$$ 3 = |\\ |\\ | $$\n",
    "$$ \\vdots $$\n",
    "\n",
    "What if we were given an *infinite* collection of these sticks, and we arranged them one after the other in a sequence than extended forever?\n",
    "\n",
    "This is a new ordinal, denoted using the Greek letter $\\omega$ (*omega*):\n",
    "\n",
    "$$ \\omega = |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\dots $$\n",
    "\n",
    "We can introduce this new infinite ordinal into our Python session:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from transfinite import w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega$"
      ],
      "text/plain": [
       "\\omega"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you may have already guessed, $\\omega$ is greater than any finite ordinal we can ever describe:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "99991234689995343742 < w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ordinal addition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once we've transcended the finite ordinals and hit $\\omega$, can we go further?\n",
    "\n",
    "Yes! We just add more sticks to to the end of our \"never-ending\" sequence of sticks:\n",
    "\n",
    "$$ \\omega + \\color{red}{1} = |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\dots\\ \\color{red}{|} $$\n",
    "$$ \\omega + \\color{red}{2} = |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\dots\\ \\color{red}{|\\ |} $$\n",
    "$$ \\omega + \\color{red}{3} = |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\dots\\ \\color{red}{|\\ |\\ |} $$\n",
    "$$ \\vdots $$\n",
    "\n",
    "Unlike $\\omega$, these ordinals have a \"last\" stick. We've created new ordinals through ordinal addition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega + 3$"
      ],
      "text/plain": [
       "\\omega + 3"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w + 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each of these ordinals is greater than the last:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w+1 < w+2 < w+3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So far this looks very similar to arithmetic on integers: adding integers together creates a new larger integer.\n",
    "\n",
    "Ordinal arithmetic however, is not quite the same. It is *non-commutative*: the order we add ordinals together matters.\n",
    "\n",
    "For instance, if we start with the ordinal $1$ and add $\\omega$ what do we get?\n",
    "\n",
    "$$ \\color{red}{1} + \\omega = \\color{red}{|\\ } |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\dots $$\n",
    "\n",
    "This ordering of sticks looks exactly like the ordering we had for $\\omega$: it is a never-ending sequence of sticks with no \"last\" stick. We have the same ordinal, not a larger one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega$"
      ],
      "text/plain": [
       "\\omega"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 + w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(This demonstrates that a collection of items arranged in the order $\\omega + 1$ dose **not** contain more items than collection arranged in the order $\\omega$. These two ordinals have the same *cardinality*, but that's a separate topic.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The largest ordinal we've seen so far is $\\omega + 3$. We can continue to add sticks onto the end to create larger ordinals. Where do end up?\n",
    "\n",
    "$$ \\omega + \\color{red}{\\omega} = |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\dots\\ \\color{red}{|\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\ |\\dots}$$\n",
    "\n",
    "A larger ordinal!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega\\cdot2$"
      ],
      "text/plain": [
       "\\omega\\cdot2"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w + w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "...and we can keep going:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega\\cdot2 + 1$"
      ],
      "text/plain": [
       "\\omega\\cdot2 + 1"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w + w + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ordinal multiplication\n",
    "\n",
    "You may have noticed that $\\omega + \\omega$ was also displayed as $\\omega \\cdot 2$ above. This is ordinal multiplation.\n",
    "\n",
    "You can think of $\\omega \\cdot n$ as meaning \"make $n$ copies of $\\omega$\". The more copies of $\\omega$ you place after one-another, the larger the ordinal:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w*3 < w*4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Like addition, multiplication of ordinals is not commutative in general. For example $ 2 \\cdot \\omega$ can be read as \"make $\\omega$ copies of $2$\":\n",
    "\n",
    "$$ 2 \\cdot \\omega = |\\ |\\ \\ \\color{red}{|\\ |\\ }\\ |\\ |\\ \\ \\color{red}{|\\ |\\ }\\dots$$\n",
    "\n",
    "This sequence of sticks is indistinguishable from $\\omega$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega$"
      ],
      "text/plain": [
       "\\omega"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 * w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What happens if we demand $\\omega$ many copies of the ordinal $\\omega$? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega^{2}$"
      ],
      "text/plain": [
       "\\omega^{2}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w * w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or $\\omega$ copies of this ordinal?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega^{3}$"
      ],
      "text/plain": [
       "\\omega^{3}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w * w * w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Even larger ordinals! Larger than any number of finite copies of $\\omega$. And of course, we can go further than merely $\\omega$ copies:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega^{3} + \\omega^{2}$"
      ],
      "text/plain": [
       "\\omega^{3} + \\omega^{2}"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(w*w) * (w+1) # w+1 many copies of w*w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Again, watch out for lack of commutativity:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega^{3}$"
      ],
      "text/plain": [
       "\\omega^{3}"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(w+1) * (w*w) # w*w many copies of w+1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ordinal exponentiation\n",
    "\n",
    "The results from the computation bring to exponentiation. Ordinals can be raised to the power of any other ordinals:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega^{7}$"
      ],
      "text/plain": [
       "\\omega^{7}"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w ** 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega^{\\omega}$"
      ],
      "text/plain": [
       "\\omega^{\\omega}"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w ** w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega^{\\omega + 9}$"
      ],
      "text/plain": [
       "\\omega^{\\omega + 9}"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w ** (w + 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega^{\\omega^{\\omega}}$"
      ],
      "text/plain": [
       "\\omega^{\\omega^{\\omega}}"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w**w**w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The intuition is easier to see with fininite ordinals.\n",
    "\n",
    "For example, $2 ^ \\omega$ is the same as doubling a sequence of two sticks $\\omega$-many times:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega$"
      ],
      "text/plain": [
       "\\omega"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2**w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\omega\\cdot2$"
      ],
      "text/plain": [
       "\\omega\\cdot2"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 ** (w+1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also double the sequence $\\omega + 1$ times. You can see that this last result holds since $ 2^{\\omega + 1} = 2^{\\omega}\\cdot2^1 = \\omega \\cdot 2 $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a question to check our understanding so far: what is the result of $2^{\\omega ^ {\\omega}}$ and why?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}