Lesson 01 Introduction to sets.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ This Jupyter notebook<sup>[1]</sup> is part of the Klopper Letures on Discrete Matheamtics and covers *the concept of a set*\n",
    "+ Created by me, Dr Juan H Klopper\n",
    "    + Head of Acute Care Surgery\n",
    "    + Groote Schuur Hospital\n",
    "    + University Cape Town\n",
    "    + <a href=\"mailto:juan.klopper@uct.ac.za\">Email me with your thoughts, comments, suggestions and corrections</a> \n",
    "<a rel=\"license\" href=\"http://creativecommons.org/licenses/by-nc/4.0/\"><img alt=\"Creative Commons Licence\" style=\"border-width:0\" src=\"https://i.creativecommons.org/l/by-nc/4.0/88x31.png\" /></a><br /><span xmlns:dct=\"http://purl.org/dc/terms/\" href=\"http://purl.org/dc/dcmitype/InteractiveResource\" property=\"dct:title\" rel=\"dct:type\">The Klopper Lectures on Discrete Mathematics</span> <span xmlns:cc=\"http://creativecommons.org/ns#\" property=\"cc:attributionName\"></span> study notes is licensed under a <a rel=\"license\" href=\"http://creativecommons.org/licenses/by-nc/4.0/\">Creative Commons Attribution-NonCommercial 4.0 International License</a>.\n",
    "\n",
    "+ [1] Fernando Pérez, Brian E. Granger, IPython: A System for Interactive Scientific Computing, Computing in Science and Engineering, vol. 9, no. 3, pp. 21-29, May/June 2007, doi:10.1109/MCSE.2007.53. URL: http://ipython.org"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<link href='http://fonts.googleapis.com/css?family=Alegreya+Sans:100,300,400,500,700,800,900,100italic,300italic,400italic,500italic,700italic,800italic,900italic' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=Arvo:400,700,400italic' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=PT+Mono' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=Shadows+Into+Light' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=Philosopher:400,700,400italic,700italic' rel='stylesheet' type='text/css'>\n",
       "\n",
       "<style>\n",
       "\n",
       "@font-face {\n",
       "    font-family: \"Computer Modern\";\n",
       "    src: url('http://mirrors.ctan.org/fonts/cm-unicode/fonts/otf/cmunss.otf');\n",
       "}\n",
       "\n",
       "#notebook_panel { /* main background */\n",
       "    background: #ddd;\n",
       "    color: #000000;\n",
       "}\n",
       "\n",
       "\n",
       "\n",
       "/* Formatting for header cells */\n",
       ".text_cell_render h1 {\n",
       "    font-family: 'Philosopher', sans-serif;\n",
       "    font-weight: 400;\n",
       "    font-size: 2.2em;\n",
       "    line-height: 100%;\n",
       "    color: rgb(0, 80, 120);\n",
       "    margin-bottom: 0.1em;\n",
       "    margin-top: 0.1em;\n",
       "    display: block;\n",
       "}\t\n",
       ".text_cell_render h2 {\n",
       "    font-family: 'Philosopher', serif;\n",
       "    font-weight: 400;\n",
       "    font-size: 1.9em;\n",
       "    line-height: 100%;\n",
       "    color: rgb(200,100,0);\n",
       "    margin-bottom: 0.1em;\n",
       "    margin-top: 0.1em;\n",
       "    display: block;\n",
       "}\t\n",
       "\n",
       ".text_cell_render h3 {\n",
       "    font-family: 'Philosopher', serif;\n",
       "    margin-top:12px;\n",
       "    margin-bottom: 3px;\n",
       "    font-style: italic;\n",
       "    color: rgb(94,127,192);\n",
       "}\n",
       "\n",
       ".text_cell_render h4 {\n",
       "    font-family: 'Philosopher', serif;\n",
       "}\n",
       "\n",
       ".text_cell_render h5 {\n",
       "    font-family: 'Alegreya Sans', sans-serif;\n",
       "    font-weight: 300;\n",
       "    font-size: 16pt;\n",
       "    color: grey;\n",
       "    font-style: italic;\n",
       "    margin-bottom: .1em;\n",
       "    margin-top: 0.1em;\n",
       "    display: block;\n",
       "}\n",
       "\n",
       ".text_cell_render h6 {\n",
       "    font-family: 'PT Mono', sans-serif;\n",
       "    font-weight: 300;\n",
       "    font-size: 10pt;\n",
       "    color: grey;\n",
       "    margin-bottom: 1px;\n",
       "    margin-top: 1px;\n",
       "}\n",
       "\n",
       ".CodeMirror{\n",
       "        font-family: \"PT Mono\";\n",
       "        font-size: 100%;\n",
       "}\n",
       "\n",
       "</style>\n",
       "\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.core.display import HTML\n",
    "#css_file = 'numericalmoocstyle.css'\n",
    "#css_file = \"custom.css\"\n",
    "css_file = 'style.css'\n",
    "HTML(open(css_file, 'r').read())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The concept of a set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## In this lesson"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Follow these links\n",
    "- [The universal set](#The-universal-set)\n",
    "- [A set](#A-set)\n",
    "- [A subset](#A-subset)\n",
    "- [A Superset](#A-superset)\n",
    "- [The empty set](#The-empty-set)\n",
    "- [More math notation](#More-math-notation)\n",
    "- [A power set of a set](#A-power-set-of-a-set)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The universal set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Discrete mathematics is built around the concept of a set.  Quite simply, a set is a group or a list or elements.  Typically these are numbers, as in the set of integers between $ -2 $ and $ 2 $ (inclusive), where the elements are the whole numbers $ -2, -1, 0, 1, 2 $.<p/>\n",
    "The elements of a set are seen as belonging to some **universal set**, which is typically called $ U $.  The elements of a universal set are called **objects**.  The objects of the universal set of all integers, $ \\mathbb{Z} $, are then $ -\\infty, \\dots, -3, -2, -1, 0, 1, 2, 3,\\dots, \\infty $.  (Note: at first we will only be concerned with universal sets of finite size and not concern ourselves too much with infinity)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Back to the top](#In-this-lesson)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Not a strict definition, we will nonetheless call a collection of elements from a universal set, a **set**.  So if our universal set was called $ S $, with $ S = \\mathbb{Z} $, we could select only the even integers.  These numbers will constitute a set.  So, we first defined a universal set and then chose elements from all of the onjects in the universal set to create a set.  Note, that a set might contain all the objects in the universal set."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Back to the top](#In-this-lesson)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A subset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we create two sets, $ A $ and $ B $, from a universal set, $ U $, we can call one a **subset** of the other if all the elemnts in one of the two sets also appear in the other.  This is denoted as $ A\\subseteq B $ or also $ B\\supseteq A $ if all the elements in $ A $ also appear in $ B $.  So, in this case, $ A $ is a subset of $ B $.<p/>\n",
    "There is also a **proper subset**, $ A \\subset B $, which is defined if there are elements in $ B $ that are not in $ A $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have to become familiar with the mathematical way of stating things, so we would summarize the above as follows:  *For all sets $ A,B $ taken from a universal set, $ U $, if $ A \\subseteq B $, then for all $ x $, $ x $ in $ A $ implies $ x $ in $ B $.*  Here we are using $ x $ as a general placeholder for all the elements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's another crack at it: $ \\forall x, x\\in C \\Rightarrow  x\\in D $, where $ \\forall $ means *for all*, $ \\in $ means *an element of* and $ \\Rightarrow $ means *implies that*.  Neat!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are two other commonly used mathematical symbol, $ \\exists $, which means *there exists* nas $ | $ which means *such that*.  So, for proper subsets we could write: $ A\\subset B\\Rightarrow \\exists x\\in B | x\\notin A $, which reads: *$ A $ is a proper subset of $ B $, inplies that there exists an element / elements, $ x $, that belong to B, but not to $ A $.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This brings us naturally to the equality of sets.  If we have two sets, $ A $ and $ B $ taken from a universal set $ U $, they are equal if and only if $ A \\subseteq B $ and $ B \\subseteq A $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now for a **Theorem**: For a given universal set $ U $ and sets $ A, B, C $ taken from the objects of $ U $ we have the following\n",
    "- If $ A \\subseteq B $ and $ B \\subseteq C $ then $ A \\subseteq C $\n",
    "- If $ A \\subset B $ and $ B \\subseteq C $ then $ A \\subset C $\n",
    "- If $ A \\subseteq B $ and $ B \\subset C $ then $ A \\subset C $\n",
    "- If $ A \\subset B $ and $ B \\subset C $ then $ A \\subset C $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Back to the top](#In-this-lesson)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A superset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If a set $ B $ is a subset of a set $ A $, then the set $ A $ is a **superset** of set $ B $, $ A\\supseteq B $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fors the set $ A $ to be a **proper superset** of $ B $ it must contain elements that are not in $ B $, $ A\\supset B $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Back to the top](#In-this-lesson)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The empty set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **empty set** is also called the **null set**.  It is a special set that contains no elements.  It is denoted by the symbols $ \\emptyset $ or sometimes simply $ \\left\\{ \\right\\} $.  It is typical to place elements of sets inside of curly braces as we will se below ([More math notation](#More-math-notation))."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Back to the top](#In-this-lesson)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## More math notation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Theorem** time: For a set $ A $ which is a subset of some universal set $ U $, we have $ \\emptyset \\subseteq A $ and if $ A \\ne \\emptyset $ then $ \\emptyset \\subset A $.  As a matter of fact the empty set is a subset of all sets."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sets and subsets can be very large (contain many elements).  There are some ways to represent these in notation that is more concise.  After setting a universal set, $ U $, for instance $ U \\in \\mathbb{Z} $, we might have something like this $$ S = \\left\\{ x \\in \\mathbb{Z} | 1 \\le x \\le 10 \\right\\} $$\n",
    "This would be the same as $ S = \\left\\{ 1,2,3,4,5,6,7,8,9,10 \\right\\} $.<p/>\n",
    "If you are familiar with linear algebra we might have the set of all $ 2 \\times 2 $ matrices that have an inverse like this $$ I = \\left\\{ \\begin{pmatrix} a & b \\\\ c & d \\end{pmatrix}|a,b,c,d\\in \\mathbb{R} ,ad-bc\\neq 0 \\right\\} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Back to the top](#In-this-lesson)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A power set of a set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we have a set $ A \\subseteq U $, the **power set** of $ A $ is the set of all subsets of $ A $, denoted as $ \\mathcal{P} \\left( A \\right) $. So is $ A = \\left\\{ a, b, c \\right\\} $ then $$ \\mathcal{P} \\left( A \\right) = \\left\\{ \\emptyset , \\left\\{ a \\right\\} ,\\left\\{ b \\right\\} ,\\left\\{ c \\right\\} ,\\left\\{ a,b \\right\\} ,\\left\\{ a,c \\right\\} ,\\left\\{ b,c \\right\\} ,\\left\\{ a,b,c \\right\\}  \\right\\} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that there are $ 8 $ elements in the power set.  We write $ \\left| \\mathcal{P} \\left( A \\right) \\right| = 8 = {2}^{3} $.  So, $ \\left| A \\right| = 3 $.  It is easy to show that if a set has $ n $ elements, then its power set will have $ {2}^{n} $ elements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Back to the top](#In-this-lesson)"
   ]
  },
  {
   "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}