math-foundations.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Mathematical Foundations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sets\n",
    "A set is a collection of objects, called _members_ or _elements_ of the set, without\n",
    "regard for their order.\n",
    "$a \\in A$, pronounced \"$a$ is an element of $A$,\"  \"$a$ is in $A$,\" or \"$a$ is a member of\n",
    "$A$\" means that $a$ is an element of the set $A$.\n",
    "This is the same as writing $A \\ni a$, which is pronounced \"$A$ contains $a$.\"\n",
    "If $a$ is not an element of $A$, we write $a \\not \\in A$.\n",
    "Sets may be described explicitly by listing their contents, or implicitly\n",
    "by specifying a property that all elements of the set share, or a condition\n",
    "that they satisfy.\n",
    "The contents of sets are enclosed in curly braces: $\\{ \\}$.\n",
    "Examples:\n",
    "\n",
    "\n",
    "+ $A = \\{a, b, c, d \\}$: the set containing the four elements $a$, $b$, $c$, and $d$.\n",
    "+ $\\emptyset = \\{ \\}$: the empty set, the set that contains no elements.\n",
    "+ ${\\mathbb Z} \\equiv \\{ \\ldots, -2, -1, 0, 1, 2, \\ldots \\}$: the integers.\n",
    "+ ${\\mathbb N} \\equiv \\{1, 2, 3, \\ldots \\}$: the natural (counting) numbers.\n",
    "+ ${\\mathbb R} \\equiv (-\\infty, \\infty)$: the real numbers.\n",
    "+ ${\\mathbb R}^+ \\equiv [-\\infty, \\infty]$: the extended real numbers.\n",
    "+ ${\\mathbb C} \\equiv \\{ a + bi: a, b \\in {\\mathbb R} \\}$, where $i = \\sqrt{-1}$: the complex numbers.\n",
    "+ ${\\mathbb Q} \\equiv \\{ a/b: a, b \\in {\\mathbb Z}\\}$: the rational numbers.\n",
    "\n",
    "\n",
    "$B$ is a _subset_ of $A$, written $B \\subset A$ or $A \\supset B$, if every element\n",
    "of the set $B$ is also an element of the set $A$.\n",
    "Thus ${\\mathbb N} \\subset {\\mathbb Z} \\subset {\\mathbb Q} \\subset {\\mathbb R} \\subset {\\mathbb C}$.\n",
    "The empty set $\\emptyset$ is a subset of every set.\n",
    "If $A \\subset B$ and $B \\subset A$, $A$ and $B$ are the same set, and we write $A = B$.\n",
    "If $B$ is not a subset of $A$, we write $B \\not \\subset A$ or $A \\not \\supset B$.\n",
    "$B$ is a _proper subset_ of $A$ if $B \\subset A$ but\n",
    "$A \\not \\subset B$.\n",
    "\n",
    "The _complement_ of $A$ (with respect to the universe $\\mathcal{X}$), written $A^c$ or $A'$,\n",
    "is the set of all objects under consideration ($\\mathcal{X}$) that are not elements of $A$.\n",
    "That is, $A^c \\equiv \\{ a \\in \\mathcal{X} : a \\not \\in A\\}$.\n",
    "\n",
    "The _intersection_ of $A$ and $B$, written $A \\cap B$ or $AB$, is the set of all objects that\n",
    "are elements of both $A$ and $B$:\n",
    "\\begin{equation*} \n",
    "        A \\cap B \\equiv \\{a: a \\in A \\mbox{ and } a \\in B \\}.\n",
    "\\end{equation*}\n",
    "If $A \\cap B = \\emptyset$, we say $A$ and $B$ are _disjoint_ or _mutually\n",
    "exclusive_.\n",
    "\n",
    "The _union_ of $A$ and $B$, written $A \\cup B$, is the set of all objects that\n",
    "are elements of $A$ or of $B$ (or both):\n",
    "\\begin{equation*} \n",
    "        A \\cup B \\equiv \\{a: a \\in A \\mbox{ or } a \\in B \\mbox{ or both} \\}.\n",
    "\\end{equation*}\n",
    "\n",
    "The _difference_ of $A$ and $B$, $A \\setminus B$, pronounced \"$A$ minus $B$,\" is\n",
    "the set of all elements of $A$ that are not elements of $B$:\n",
    "\\begin{equation*} \n",
    "        A \\setminus B \\equiv \\{a \\in A : a \\not \\in B \\} = A \\cap B^c.\n",
    "\\end{equation*}\n",
    "\n",
    "_Intervals_ are special subsets of ${\\mathbb R}$:\n",
    "\\begin{eqnarray*}\n",
    "        [a, b] &\\equiv& \\{x \\in {\\mathbb R} : a \\le x \\le b\\}\\cr\n",
    "        (a, b] &\\equiv& \\{x \\in {\\mathbb R} : a < x \\le b\\}\\cr\n",
    "        [a, b) &\\equiv& \\{x \\in {\\mathbb R} : a \\le x < b\\}\\cr\n",
    "        (a, b) &\\equiv& \\{x \\in {\\mathbb R} : a < x < b\\}.\n",
    "\\end{eqnarray*}\n",
    "\n",
    "Sometimes we have a collection of sets, indexed by elements of another\n",
    "set: $\\{A_\\beta : \\beta \\in B \\}$.\n",
    "Then $B$ is called an _index set_.\n",
    "If $B$ is a subset of the integers ${\\mathbb Z}$, usually we write $A_i$ or $A_j$, etc.,\n",
    "rather than $A_\\beta$.\n",
    "If $B = {\\mathbb N}$, we usually write $\\{A_j\\}_{j=1}^\\infty$ rather than\n",
    "$\\{A_\\beta : \\beta \\in {\\mathbb N} \\}$.\n",
    "\\begin{equation*} \n",
    "        \\bigcap_{\\beta \\in B} A_\\beta \\equiv \\{a: a \\in A_\\beta \\;\\;\\forall \\beta \\in B \\}.\n",
    "\\end{equation*}\n",
    "($\\forall$ means \"for all.\")\n",
    "If $B = \\{1, 2, \\ldots, n\\}$, we usually write $\\bigcap_{j=1}^n A_j$ rather than\n",
    "$\\bigcap_{j \\in \\{1, 2, \\ldots, n\\}} A_j$.\n",
    "The notation $\\bigcup_{\\beta \\in B} A_\\beta$ and $\\bigcup_{j=1}^n A_j$ are defined analogously.\n",
    "\n",
    "A collection of sets $\\{A_\\beta : \\beta \\in B \\}$ is _pairwise disjoint_\n",
    "if $A_\\beta \\cap A_{\\beta'} = \\emptyset$ whenever $\\beta \\ne \\beta'$.\n",
    "The collection $\\{A_\\beta : \\beta \\in B\\}$ _exhausts_ or _covers_\n",
    "the set $A$ if $A \\subset \\bigcup_{\\beta \\in B} A_\\beta$.\n",
    "The collection $\\{A_\\beta : \\beta \\in B \\}$ is a _partition_ of the\n",
    "set $A$ if $A = \\cup_{\\beta \\in B} A_\\beta$ and the sets $\\{A_\\beta : \\beta \\in B \\}$\n",
    "are pairwise disjoint.\n",
    "If $\\{A_\\beta : \\beta \\in B \\}$ are pairwise disjoint and exhaust $A$, then\n",
    "$\\{A_\\beta \\cap A : \\beta \\in B \\}$ is a partition of $A$.\n",
    "\n",
    "A set is _countable_ if its elements can be put in one-to-one correspondence with\n",
    "a subset of ${\\mathbb N}$.\n",
    "A set is _finite_ if its elements can be put in one-to-one correspondence with\n",
    "$\\{1, 2, \\ldots, n\\}$ for some $n \\in {\\mathbb N}$.\n",
    "If a set is not finite, it is infinite.\n",
    "${\\mathbb N}$, ${\\mathbb Z}$, and ${\\mathbb Q}$ are infinite but countable; ${\\mathbb R}$ is infinite and uncountable.\n",
    "\n",
    "The notation $\\# A$, pronounced \"the cardinality of $A$\" is the size of the set $A$.\n",
    "If $A$ is finite, $\\# A$ is the number of elements in $A$.\n",
    "If $A$ is not finite but $A$ is countable (if its elements can be put in one-to-one\n",
    "correspondence with the elements of ${\\mathbb N}$), then $\\# A = \\aleph_0$ (aleph-null).\n",
    "\n",
    "The _power set_ of a set $A$ is the set of all subsets of the set $A$.\n",
    "For example, the power set of $\\{a, b, c\\}$ is\n",
    "\\begin{equation*} \n",
    "        \\{ \\emptyset, \\{a\\}, \\{b\\}, \\{c\\}, \\{a, b\\}, \\{a, c\\}, \\{b, c\\}, \\{a, b, c\\} \\}.\n",
    "\\end{equation*}\n",
    "If $A$ is a finite set, the cardinality of the power set of $A$ is $2^{\\# A}$.\n",
    "This can be seen as follows: suppose $\\# A = n$ is finite.\n",
    "Consider the elements of $A$ to be written in some canonical order.\n",
    "We can specify an element of the power set by an $n$-digit binary number.\n",
    "The first digit is 1 if the first element of $A$ is in the subset, and 0 otherwise.\n",
    "The second digit is 1 if the second element of $A$ is in the subset, and 0 otherwise,\n",
    "etc.\n",
    "There are $2^n$ $n$-digit binary numbers, so there are $2^n$ subsets.\n",
    "The cardinality of the power set of ${\\mathbb N}$ is not $\\aleph_0$.\n",
    "\n",
    "If $A$ is a finite set, $B$ is a countable set\n",
    "and $\\{A_j : \\beta \\in B \\}$ is a partition of $A$, then\n",
    "\\begin{equation*} \n",
    "        \\# A = \\sum_{\\beta \\in B} \\# A_\\beta.\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Multisets\n",
    "\n",
    "A _multiset_ or _bag_ is like a set, except it can contain more than one \"copy\" of a given element.\n",
    "\n",
    "For instance, the sets $\\{0, 1\\}$ and $\\{0, 1, 1\\}$ are the same, because they contain the same two elements, namely, 0 and 1. \n",
    "But viewed as _multisets_, they are different, because the second contains the element 1 twice.\n",
    "One can think of a multiset as a set of ordered pairs, the first element of which is one of the distinct elements of the multiset, and the second of which is the multiplicity of that element.\n",
    "For instance, the multiset $\\{0, 1, 1\\}$ could be represented $ \\{ (0, 1), (1, 2) \\}$.\n",
    "We will sometimes use $\\llcorner \\cdot \\lrcorner$ to denote a bag.\n",
    "\n",
    "Two bags are equal if they contain the same elements with the same multiplicities, that is, set of distinct\n",
    "elements of the first multiset is equal to the set of distinct elements of the second, and the multiplicity function of the first is equal to the multiplicity function of the second (i.e., the multiplicity of each item is the same in both multisets).\n",
    "For instance, the multisets $\\llcorner 0, 1, 1\\lrcorner$ and $\\llcorner 1, 0, 1 \\lrcorner$ are equal.\n",
    "\n",
    "A set amounts to a multiset in which the multiplicity of every element is 1.\n",
    "\n",
    "Generally I will not make a notational distinction between sets and multisets (I use curly braces to denote both sets and multisets).\n",
    "\n",
    "If $(x_j)_{j=1}^n$ is an ordered n-tuple, $\\{x_j\\}_{j=1}^n$ and $\\llcorner x_j \\lrcorner_{j=1}^n$ will denote the multiset containing all\n",
    "$n$ of its components."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cartesian Products\n",
    "The notation $(s_1, s_2, \\ldots, s_n) \\equiv (s_j)_{j=1}^n$ denotes an \n",
    "_ordered $n$-tuple_ consisting of \n",
    "$s_1$ in the first position, $s_2$ in the second position, etc.\n",
    "The parentheses are used instead of curly braces to distinguish \n",
    "$n$-tuples from sets: $(s_j)_{j=1}^n \\ne \\{s_j\\}_{j=1}^n$.\n",
    "The $k$th\n",
    "_component_ of the $n$-tuple $s = (s_j)_{j=1}^n$, is $s_k$, \n",
    "$k = 1, 2, \\ldots, n$.\n",
    "Two $n$-tuples are equal if their components are equal.\n",
    "That is, $(s_j)_{j=1}^n = (t_j)_{j=1}^n$ means that\n",
    "$s_j = t_j$ for $j = 1, \\ldots, n$.\n",
    "In particular, $(s, t) \\ne (t, s)$ unless $s=t$.\n",
    "In contrast, $\\{s, t \\} = \\{ t, s \\}$ always.\n",
    "\n",
    "The _Cartesian product of $S$ and $T$_ is\n",
    "$S \\times T \\equiv \\{(s, t): s \\in S \\mbox{ and } t \\in T\\}$.\n",
    "Unless $S = T$, $S \\times T \\ne T \\times S$.\n",
    "${\\mathbb R}^n$ is the Cartesian product of ${\\mathbb R}$ with itself, $n$ times; its elements\n",
    "are $n$-tuples of real numbers.\n",
    "If $s$ is the $n$-tuple $(s_1, s_2, \\ldots, s_n) = (s_j)_{j=1}^n$, \n",
    "\n",
    "Let $A$ be a finite set with $\\# A = n$.\n",
    "A _permutation_ of (the elements of) $A$ is an element $s$ of \n",
    "$\\times_{j=1}^n A = A^n$\n",
    "whose components are distinct elements of $A$.\n",
    "That is, $s = (s_j)_{j=1}^n \\in A^n$ is a permutation of $A$ if\n",
    "$\\# \\{s_j\\}_{j=1}^n = n$.\n",
    "There are $n! = n(n-1)\\cdots 1$ permutations of a set with $n$ elements:\n",
    "there are $n$ choices for the first component of the permutation, $n-1$ choices for\n",
    "the second (whatever the\n",
    "first might be), $n-2$ for the third (whatever the first two might be), etc.\n",
    "This is an illustration of the _fundamental rule of counting_:\n",
    "in a sequence of $n$ choices, if there are $m_1$ possibilites for the first choice,\n",
    "$m_2$ possibilities for the second choice (no matter which was chosen in the first place),\n",
    "$m_3$ possibilities for the third choice \n",
    "(no matter which were chosen in the first two places),\n",
    "and so on, then there are $m_1 m_2 \\cdots m_n = \\prod_{j=1}^n m_j$ possible sequences\n",
    "of choices in all.\n",
    "\n",
    "The number of permutations of $n$ things taken $k$ at a time, ${}_nP_k$,\n",
    "is the number of ways there are of selecting $k$ of $n$ things, then permuting\n",
    "those $k$ things.\n",
    "There are $n$ choices for the object that will be in the first place in the permutation,\n",
    "$n-1$ for the second place (regardless of which is first), etc., and $n-k+1$ choices\n",
    "for the item that will be in the $k$th place.\n",
    "By the fundamental rule of counting, it follows that\n",
    "${}_nP_k = n(n-1)\\cdots(n-k+1) = n!/(n-k)!$.\n",
    "\n",
    "The number of subsets of size $k$ that can be formed from $n$ objects is\n",
    "\\begin{equation*} \n",
    "        {}_nC_k = {{n}\\choose{k}} = \n",
    "        {}_nP_k/k! = n(n-1)\\cdots(n-k+1)/k! = \\frac{n!}{k!(n-k)!}.\n",
    "\\end{equation*}\n",
    "Because the power set of a set with $n$ elements can be partitioned as\n",
    "\\begin{equation*} \n",
    "        \\cup_{k=0}^n \\left \\{ \\mbox{all subsets of size } k\n",
    "        \\right \\},\n",
    "\\end{equation*}\n",
    "it follows that\n",
    "\\begin{equation*} \n",
    "        \\sum_{j=0}^n {}_nC_k = 2^n.\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mappings and Functions\n",
    "Functions are subsets of Cartesian products.\n",
    "We write $f: \\mathcal{X} \\rightarrow \\mathcal{Y}$, pronounced \"$f$ maps $\\mathcal{X}$ into $\\mathcal{Y}$\"\n",
    "or \"$f$ is a function with domain $\\mathcal{X}$ and co-domain $\\mathcal{Y}$\" if\n",
    "$f \\subset \\mathcal{X} \\times \\mathcal{Y}$ such that for each $x \\in \\mathcal{X}$, $\\exists 1 y \\in \\mathcal{Y}$\n",
    "such that $(x, y) \\in f$.\n",
    "(The notation $\\exists 1 y$ means that there exists exactly one value of $y$.)\n",
    "The set $\\mathcal{X}$ is called the _domain_ of $f$ and $\\mathcal{Y}$ is called the co-domain of $f$.\n",
    "If the $\\mathcal{X}$-component of an element of $f$ is $x$, we denote the $\\mathcal{Y}$-component of that\n",
    "element of $f$ by $fx$ or $f(x)$, so that $(x, fx) \\in f$; we write $f: x \\mapsto y=f(x)$.\n",
    "The functions $f$ and $g$ are equal if they are the same subset of $\\mathcal{X} \\times \\mathcal{Y}$,\n",
    "which means that they have the same domain $\\mathcal{X}$, and $fx = gx$ $\\forall x \\in \\mathcal{X}$.\n",
    "\n",
    "Let $A \\subset \\mathcal{X}$.\n",
    "The _image_ of $A$ under $f$ is\n",
    "\\begin{equation*} \n",
    "        fA = f(A) \\equiv \\{ y \\in \\mathcal{Y} : (x, y) \\in f \\mbox{ for some } x \\in A\\}.\n",
    "\\end{equation*}\n",
    "More colloquially, we would write this as\n",
    "\\begin{equation*} \n",
    "        fA = \\{ y \\in \\mathcal{Y} : f(x) = y \\mbox{ for some } x \\in A \\}.\n",
    "\\end{equation*}\n",
    "If $f\\mathcal{X}$ is a proper subset of $\\mathcal{Y}$, $f$ is _into_.\n",
    "If $f\\mathcal{X} = \\mathcal{Y}$, $f$ is _onto_.\n",
    "For $B \\subset \\mathcal{Y}$, the _inverse image of $B$ under $f$_ or\n",
    "_pre-image of $B$ under $f$_ is\n",
    "\\begin{equation*} \n",
    "        f^{-1}B \\equiv \\{ x \\in \\mathcal{X} : fx \\in B \\}.\n",
    "\\end{equation*}\n",
    "Similarly, $f^{-1}y \\equiv \\{ x \\in \\mathcal{X} : fx = y \\}$\n",
    "If $\\forall y \\in \\mathcal{Y}$, $\\# \\{ f^{-1} y \\} \\le 1$, $f$ is _one-to-one_ (1:1).\n",
    "If $f$ is one-to-one and onto, i.e., if $\\forall y \\in \\mathcal{Y}$, $\\# \\{ f^{-1}y \\} = 1$,\n",
    "$f$ is a _bijection_."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Relations and Orders\n",
    "\n",
    "A _relation_ $R$ on the set $A$ is a collection of ordered pairs of elements of $A$, that is,\n",
    "$R  \\subset A \\times A$.\n",
    "Notationally, if $(a,b) \\in R $, we write $a R b$.\n",
    "\n",
    "A relation can also be thought of as a function from $A \\times A$ to $\\{0, 1\\}$ such\n",
    "that the function takes the value 1 if an only if (iff) $(a,b) \\in R $.\n",
    "\n",
    "For instance, consider the \"divides\" relation on the positive integers $\\mathbb N$.\n",
    "We say that $j \\in \\mathbb N$ \"divides\" $k \\in \\mathbb N$ if $k$ is an integer multiple of\n",
    "$j$. \n",
    "As an example, 3 divides 102.\n",
    "If we let $R$ denote the relation \"divides,\" then $(3, 102) \\in R $ and we would write $3 R 102$ \n",
    "\n",
    "A _partial order_ $\\le $ on the set $A$ is a relation on $A$ such that:\n",
    "\n",
    "+ for every $a \\in A$, $ a \\le a $ (_reflexivity_)\n",
    "+ if $ a \\le b $ and $ b \\le a $, then $ a = b $ (_antisymmetry_)\n",
    "+ if $ a \\le b $ and $ b \\le c $, then $ a \\le c $ (_transitivity_)\n",
    "\n",
    "If in addition, for every $ (a, b) \\in A \\times A $ either $ a \\le b $ or $ b \\le a $ (_comparability_), then  $ \\le $ is a _total order_.\n",
    "\n",
    "An _equivalence relation_ $ \\sim $ on the set $A$ is a relation on $A$ such that:\n",
    "+ for every $a \\in A$, $ a \\sim a $ (_reflexivity_)\n",
    "+ if $ a \\sim b $ then $ b \\sim a $ (_symmetry_)\n",
    "+ if $ a \\sim b $ and $ b \\sim c $, then $ a \\sim c $ (_transitivity_)\n",
    "\n",
    "The _equivalence class_ of $a$ under $\\sim$ is $[a] \\equiv \\{b \\in A : b \\sim a \\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Groups\n",
    "A _group_ is an ordered pair $(\\mathcal{G}, \\times)$, where $\\mathcal{G}$ is\n",
    "        a collection of objects (the elements of the group) and $\\times$ is a mapping\n",
    "        from $\\mathcal{G} \\times \\mathcal{G}$ onto $\\mathcal{G}$,\n",
    "        \\begin{eqnarray*}\n",
    "                \\times : & \\mathcal{G} \\times \\mathcal{G} & \\rightarrow \\mathcal{G} \\\\\n",
    "                         & (g, h) & \\mapsto g \\times h,\n",
    "        \\end{eqnarray*}\n",
    "        satisfying the following axioms:\n",
    "\n",
    "+ $\\exists e \\in \\mathcal{G}$ s.t. $\\forall g \\in \\mathcal{G}$, $e \\times g = g$. The element $e$ is called the _identity_.\n",
    "+ For each $g \\in \\mathcal{G}$, $\\exists g^{-1} \\in \\mathcal{G}$ s.t. $g^{-1}\\times g = e$. (Every element has an inverse.)\n",
    "+ If $f, g, h \\in \\mathcal{G}$, then $f \\times (g \\times h) = (f \\times g)\\times h$. (The group operation is associative.)\n",
    "\n",
    "If, in addition, for every $g, h \\in \\mathcal{G}$,  $g \\times h = h \\times g$ (if the group\n",
    "operation commutes), we say that $(\\mathcal{G}, \\times)$ is an _Abelian group_\n",
    "or _commutative group_.\n",
    "\n",
    "In an abuse of terminology, we will often call $\\mathcal{G}$ a group, with the group operation $\\times$\n",
    "understood from context.\n",
    "\n",
    "---\n",
    "\n",
    "Examples of groups include the real numbers together with ordinary addition, $({\\mathbf R}, +)$;\n",
    "the real numbers other than zero together with ordinary multiplication,\n",
    "$({\\mathbf R} \\setminus \\{0\\}, *)$; the rational numbers together with ordinary addition,\n",
    "$({\\mathbf Q}, +)$; and the integers 0 to $p-1$, $p$ prime, together with addition modulo $p$,\n",
    "$( \\{0, 1, \\ldots, p-1\\}, +)$;\n",
    "and the set of all permutations of $n$ distinct objects (called _the symmetric group of degree $n$_, \n",
    "denoted $\\mathcal{S}_n$).\n",
    "\n",
    "It is common to omit the symbol $\\times$ from the group notation, and write $g \\times h$ as $gh$,\n",
    "when $\\mathcal{G}$ is an abstract group.\n",
    "\n",
    "---\n",
    "\n",
    "Suppose $\\mathcal{H} \\subset \\mathcal{G}$, where $(\\mathcal{G}, \\times)$ is a group.  \n",
    "If $(\\mathcal{H}, \\times)$ is also a group, it is called a _subgroup_ of $(\\mathcal{G}, \\times)$.\n",
    "\n",
    "---\n",
    "\n",
    "Consider a subset $A$ of elements of a group $\\mathcal{G}$. \n",
    "The _subgroup generated by $A$_ is the smallest group that contains $A$ (using the same multiplication\n",
    "operator as $\\mathcal{G}$), that is, every element\n",
    "of $\\mathcal{G}$ that can be written as a product of elements of $A$ and inverses of elements of\n",
    "$A$.\n",
    "If the subgroup generated by $A$ is equal to $\\mathcal{G}$, then $A$ _is a generating set_ of $\\mathcal{G}$.\n",
    "\n",
    "For example, consider $\\mathcal{S}_n$, the symmetric group of permutations of $n$ objects.\n",
    "This group can be generated from just two of its elements, a _transposition_ $\\pi = (2, 1, 3, \\ldots, n)$\n",
    "and a _circular shift_ $\\eta = (n, 1, 2, 3, \\ldots, n-1)$.\n",
    "\n",
    "---\n",
    "\n",
    "<!-- [FIX ME! Not correct. ]\n",
    "A _cycle_ is the sequence of permutations that results from repeatedly applying the same permutation,\n",
    "until it returns to the starting point.\n",
    "For the permutation $\\pi$, a cycle is $\\pi, \\pi^2, \\ldots, \\pi$: since $\\mathcal{G}$ has a finite number of\n",
    "elements, any sequence of elements must eventually repeat.\n",
    "The identity permutation $\\pi = e$, is equal to every power of itself. In particular, $e^2 = e$.\n",
    "Thus $e$ gives a cycle of length 1.\n",
    "For instance, consider the permutation $\\pi = (2, 1, 3, \\ldots, n)$. \n",
    "The permutation exchanges the first and second elements. Applying it twice exchanges them back,\n",
    "producing the identity permutation. This permutation produces a cycle of length 2.\n",
    "For another example, consider the permutation $\\pi = (n, 1, 2, \\ldots, n-1)$.\n",
    "If we apply this permutation to $(1, 2, 3, \\ldots, n)$, we get $(n, 1, 2, \\ldots, n-1)$.\n",
    "Applying it repeatedly yields $(n-1, n, 1, \\ldots, n-2)$, $(n-2, n-1, n, 1, \\ldots, n-3)$, etc.\n",
    "After $n$ applications, we get back to $(1, 2, 3, \\ldots, n)$. \n",
    "This permutation gives a cycle of length $n$.\n",
    "--> \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fields\n",
    "\n",
    "An ordered triple $(\\mathcal{F}, \\times, +)$ is a _field_ if $\\mathcal{F}$ is\n",
    "        a collection of objects and $\\times$ and $+$ are operations on $\\mathcal{F} \\times \\mathcal{F}$\n",
    "        such that\n",
    "        \n",
    "+ $\\mathcal{F}$ is an Abelian group under the operation $+$, with identity element denoted 0.\n",
    "+ $\\mathcal{F} \\setminus \\{0\\}$ is an Abelian group under the operation $\\times$, with identity element denoted $1$.\n",
    "+ $\\times$ is distributive over $+$. I.e., for any $f$, $g$, $h \\in \\mathcal{F}$,\n",
    "$f \\times (g+h) = f \\times g + f \\times h$ and\n",
    "$(f+g) \\times h = f\\times h + g \\times h$.\n",
    "\n",
    "The additive inverse of $g$ is denoted $-g$; the multiplicative inverse of $g$ is\n",
    "$g^{-1} = 1/g$.\n",
    "\n",
    "---\n",
    "\n",
    "Examples:\n",
    "$({\\mathbf R}, \\times, +)$, where $\\times$ is ordinary (real) multiplication and $+$ is ordinary\n",
    "(real) addition.\n",
    "The complex numbers ${\\mathbf C}$, with complex multiplication and addition.\n",
    "\n",
    "These (and the extended reals) are the only fields we will use."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Arithmetic with $\\infty$\n",
    "We shall use the following conventions:\n",
    "\n",
    "+ $0 \\cdot \\infty = \\infty \\cdot 0 = 0$\n",
    "+ $x + \\infty = \\infty + x = \\infty$, $x \\in {\\mathbf R}$\n",
    "+ $x \\cdot \\infty = \\infty \\cdot x = \\infty$, $x > 0$\n",
    "\n",
    "With these conventions, $([-\\infty, \\infty], \\times, +)$ is a field."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Groups of transformations on a set\n",
    "\n",
    "Let $ \\mathcal{G} $ be a group (with the group operation implicit) with identity element\n",
    "$e \\in \\mathcal{G} $ and let $\\mathcal X$ be a set.\n",
    "Then a _group action_ of $\\mathcal G$ on $\\mathcal X$ is a function from $ {\\mathcal G} \\times {\\mathcal X}$ into $\\mathcal X$ such that\n",
    "(if we denote the image of $(g, x)$ under this transformation as $g.x$),\n",
    "\n",
    "+ $e.x = x$ for every $x \\in \\mathcal{X}$ (the _identity_ element of the group is an identity transformation on the set)\n",
    "+ for every $g \\in \\mathcal{G}$ and $h \\in \\mathcal{G}$ and every $x \\in \\mathcal{X}$,\n",
    "$g.(h.x) = (gh).x$ (the group operation is _compatible_ with the composition of transformations on the set).\n",
    "\n",
    "Then we call $\\mathcal{G}$ a _group of transformations of_ $\\mathcal{X}$.\n",
    "\n",
    "---\n",
    "\n",
    "The _orbit_ of the point $ x \\in \\mathcal{X} $ under $\\mathcal{G}$ is the set\n",
    "$\\mathcal{G}.x \\equiv \\{ g.x : g \\in \\mathcal{G} \\}$.\n",
    "\n",
    "If we write $ x \\sim y $ when $ y \\in \\mathcal{G}.x $, then $\\sim$ is an equivalence\n",
    "relation on $\\mathcal{G}$; that is, orbits define equivalence classes.\n",
    "Moreover, the set of distinct orbits partitions a set into equivalence classes.\n",
    "\n",
    "For example, let $\\mathcal{X} $ be 2-dimensional Euclidean space,\n",
    "and let $\\mathcal{G} $ be rotations around the origin.\n",
    "Such rotations comprise a group, if the group operation is defined as composition: \n",
    "if $g$ is rotation by the angle $\\theta$ and $h$ is rotation by the angle $\\omega$,\n",
    "then $gh$ is defined to be rotation by the angle $\\theta + \\omega$, equivalently, rotation by \n",
    "$\\theta$ followed by rotation by $\\omega$.\n",
    "The identity element is rotation by 0.\n",
    "The orbit of the point $ x = (x_1, x_2)$ is a circle centered at the origin, with\n",
    "radius $r = \\sqrt{x_1^2 + x_2^2}$.\n",
    "The entire Euclidean plane can be partitioned into an uncountable union of circles of different radii.\n",
    "\n",
    "As another example, let $\\mathcal{X}$ be the set of ordered $n$-tuples of real numbers, \n",
    "elements of $\\mathbb{R}^n$.\n",
    "Let $\\pi$ denote a permutation of $\\{1, \\ldots, n\\}$, an $n$-tuple of integers\n",
    "between 1 and $n$ with no duplicates: $\\pi_j$ is a number between\n",
    "1 and $n$ and $\\{\\pi_1, \\pi_2, \\ldots, \\pi_n \\} = \\{1, 2, \\ldots, n\\}$.\n",
    "If $\\pi$ and $\\phi$ are two permutations, define $\\pi \\phi$ to be the permutation that\n",
    "results from composing the two permutations.\n",
    "For instance, if $\\pi = (1,3,2,4)$ and $\\phi = (2,4,3,1)$, then $\\pi \\phi = (2,3,4,1)$.\n",
    "Such permutations comprise a group with identity element $e = (1,2,3,4)$.\n",
    "If we define the action of a permutation on an element $ x \\in \\mathcal{X}$ to be an\n",
    "$n$-tuple that results from re-ordering the components of $x$ according to $\\pi$,\n",
    "then this group \n",
    "For instance, if $x = (x_1, x_2, \\ldots, x_n) $ and $ \\pi = (\\pi_1, \\ldots, \\pi_n)$\n",
    "then $ \\pi x = (x_{\\pi_1}, \\ldots x_{\\pi_n})$.\n",
    "Even more concretely, let $x = (x_1, x_2, x_2, x_4) $ and let $ \\pi = (1, 4, 3, 2)$.\n",
    "Then $ \\pi x = (x_1, x_4, x_3, x_2)$.\n",
    "The orbit of a point $x$ is the collection of all elements of $\\mathcal{X}$ \n",
    "with the same components as $x$, but in all $n!$ possible orders.\n",
    "(The orbit will contain fewer than $n!$ distinct elements of $\\mathcal{X}$ if the values\n",
    "of the components of $x$ are not all distinct.)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Topologies and topological spaces\n",
    "\n",
    "Let $\\Omega$ be a set and $\\tau$ be a collection of subsets of $\\Omega$ (the _open sets_) such that:\n",
    "\n",
    "+ $\\Omega \\in \\tau$ and $\\emptyset \\in \\tau$\n",
    "+ If $A_j \\in \\tau$, $j \\in \\mathbb{N}$, then $\\cup_{j \\in \\mathbb{N}} A_j \\in \\tau$.\n",
    "+ If $A_j \\in \\tau$, $j=1, \\ldots, n$, then $\\cap_{j=1}^n A_j \\in \\tau$.\n",
    "Then $\\tau$ is a _topology_ on $\\Omega$, and $(\\Omega, \\tau)$ is a topological space.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Set algebras and sigma-algebras\n",
    "\n",
    "Let $\\Omega$ be a set and $\\mathcal{F}$ be a collection of subsets of $\\Omega$.\n",
    "$(\\Omega, \\mathcal{F})$ is an _algebra of sets over $\\Omega$_ if\n",
    "+ $\\emptyset \\in \\mathcal{F}$\n",
    "+ $\\mathcal{F}$ is closed under complementation: if $A \\in \\mathcal{F}$ then $A^c := \\Omega \\setminus A \\in \\mathcal{F}$\n",
    "+ $\\mathcal{F}$ is closed under binary unions or binary intersections: when $A$, $B \\in \\mathcal{F}$, then $A \\cup B \\in \\mathcal{F}$ (equivalently, when $A$, $B \\in \\mathcal{F}$, then $A \\cap B \\in \\mathcal{F}$), \n",
    "\n",
    "$(\\Omega, \\mathcal{F})$ is a _sigma-algebra of sets over $\\Omega$_ ($\\mathcal{F}$ is a _sigma-algebra_) if, in addition, whenever $A_j \\in \\mathcal{F}$ for all $j \\in \\mathbb{N}$, $\\cup_{j\\in \\mathbb{N}} A_j \\in \\mathcal{F}$\n",
    "(equivalently, $\\cap_{j\\in \\mathbb{N}} A_j \\in \\mathcal{F}$), i.e., $\\mathcal{F}$ is closed under countable unions or countable intersections.\n",
    "\n",
    "**Example.** The Borel sigma-algebra on $\\Re$ is the smallest sigma-algebra that contains all intervals in\n",
    "$\\Re$. \n",
    "\n",
    "Let $\\mathcal{B}$ be a collection of subsets of $\\Omega$. The _sigma algebra generated by $\\mathcal{B}$, $\\sigma(\\mathcal{B}$_, is the smallest sigma-algebra that contains every element of $\\mathcal{B}$.\n",
    "\n",
    "Suppose $f$ is a real-valued function on the set $\\Omega$.\n",
    "The _sigma-algebra generated by $f$, $\\sigma(f)$_ is the smallest sigma-algebra on $\\Omega$ that contains the pre-image of every Borel subset of $\\Re$. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Measurable spaces, measurable functions\n",
    "\n",
    "$(\\Omega, \\mathcal{F})$ ...\n",
    "TBD\n",
    "\n",
    "## Measures and probability measures\n",
    "\n",
    "TBD\n",
    "\n",
    "## Probability spaces\n",
    "\n",
    "TBD"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Measurable functions\n",
    "\n",
    "Let $f$ be a function from a measurable space $(\\Omega, \\mathcal{F})$ to a topological space\n",
    "$\\mathcal{X}$ with Borel sigma-algebra $\\mathcal{B}$.\n",
    "If $\\{ \\omega \\in \\Omega : f(\\omega) \\in B \\} \\in \\mathcal{F}$ for every $B \\in \\mathcal{B}$,\n",
    "then $f$ is a _measurable function_. \n",
    "That is, $f$ is measurable if the pre-image of every Borel set is a measurable set.\n",
    "\n",
    "## Random variables\n",
    "\n",
    "A _(real-valued) random variable $X$_ is a measurable function from a probability space $(\\Omega, \\mathcal{F}, \\mathbb{P})$ to $\\Re$.\n",
    "\n",
    "## Stochastic processes\n",
    "\n",
    "TBD\n",
    "\n",
    "## Filtrations\n",
    "Let $(\\Omega, \\mathcal{F}, \\mathbb{P})$ be a probability space.\n",
    "Let $\\mathcal{I}$ be a totally ordered set with order relation $\\le$.\n",
    "Suppose that for all $i \\in \\mathcal{I}$, $\\mathcal{F}_i$ is a sub-sigma-algebra of $\\mathcal{F}$,\n",
    "and that if $i < j$, $\\mathcal{F}_i \\subset \\mathcal{F}_j$.\n",
    "Then $\\mathbb{F} := \\{\\mathcal{F}_i\\}_{i \\in \\mathcal{I}}$ is a _filtration_ and $(\\Omega, \\mathcal{F}, \\mathbb{F}, \\mathbb{P})$ is\n",
    "a _filtered probability space_.\n",
    "\n",
    "Filtrations arise naturally in studying stochastic processes.\n",
    "Let $\\sigma(X)$ be the sigma-algebra generated by the random variable $X$ (the smallest sigma-algebra for which $X$ is measurable, i.e., the smallest sigma algebra that contains the pre-image $X^{-1}(B)$\n",
    "of every Borel subset $B \\subset \\mathcal{B}$), and let  $\\sigma(X_j : j \\le i) := \\sigma(\\cup_{j \\le i} \\sigma(X_j))$.\n",
    "As the process evolves, a richer and richer set of events becomes measurable.\n",
    "Let $(X_i)_{i \\in \\mathbb{N}}$ be a stochastic process on the probability space $(\\Omega, \\mathcal{F}, \\mathbb{P})$,\n",
    "and define $\\mathcal{F}_i := \\sigma(X_j : j \\le i)$.\n",
    "Then $\\mathbb{F} := \\{\\mathcal{F}_i\\}_{i \\in \\mathcal{I}}$ is a filtration."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Transformations of probability distributions\n",
    "\n",
    "Let $\\mathbb{P}$ be a probability distribution on a (measurable) set $\\mathcal{X}$ and let\n",
    "$\\mathcal{G}$ be a group of transformations of $\\mathcal{X}$ with the property that\n",
    "for every $ A \\subset \\mathcal{X}$ for which $\\mathbb{P}(A)$ is defined and every $ g \\in \\mathbb{G} $, \n",
    "$\\mathbb{P}(g.A)$ is also defined (i.e., $\\mathcal{G}$ preserves the measurability of sets).\n",
    "\n",
    "A probability distribution $\\mathbb{P}$ on a (measurable) set $\\mathcal{X}$\n",
    "is _invariant under the group of transformations_ $\\mathcal{G}$ if for every \n",
    "$ A \\subset \\mathcal{X}$ for which $\\mathbb{P}(A)$ is defined and every $ g \\in \\mathcal{G}$,\n",
    "$\\mathbb{P}(g.A)$ is also defined, and $\\mathbb{P}(A) = \\mathbb{P}(g.A)$.\n",
    "\n",
    "For example, the multivariate normal distribution with IID components is invariant with respect to rotations about its mean.\n",
    "\n",
    "A collection of random variables is _exchangeable_ if every permutation of the variables has the same\n",
    "joint probability distribution, that is, if the joint distribution is invariant under the permutation\n",
    "group. Any collection of random variables that are independent and identically distributed (IID) is exchangeable, but IID is a stronger property than exchangeability."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Real Linear Vector Spaces\n",
    "\n",
    "Let $\\mathcal{X}$ be a set (the \"vectors\") with two relations, $+$ (vector addition) and $\\cdot$ (scalar multiplication), \n",
    "such that for all $x, y \\in \\mathcal{X}$ and all $\\alpha, \\beta \\in \\mathbb{R}$,\n",
    "\n",
    "+ $x+y \\in \\mathcal{X}$ ($\\mathcal{X}$ is closed under $+$)\n",
    "+ $\\exists 0 \\in \\mathcal{X}$ such that $\\forall x \\in \\mathcal{X}$, $0+x = x$ ($0$ is the identity element for $+$)\n",
    "+ For each $x \\in \\mathcal{X}$, $\\exists -x \\in \\mathcal{X}$ such that $-x + x = 0$ (every element has an additive inverses\n",
    "+ $x+y = y+x$ ($+$ is commutative)\n",
    "+ $x + (y+z) = (x+y) + z$ ($+$ is associative)\n",
    "+ $\\alpha \\cdot x \\in \\mathcal{X}$ (closure under $\\cdot$)\n",
    "+ $1 \\cdot x = x$ ($1$ is the identity element for scalar multiplication)\n",
    "+ $(\\alpha + \\beta)\\cdot x = \\alpha\\cdot x + \\beta \\cdot x$ (scalar addition distributes over multiplication)\n",
    "+ $(\\alpha \\beta) \\cdot x = \\alpha\\cdot(\\beta \\cdot x)$ (scalar multiplication is associative)\n",
    "+ $\\alpha \\cdot (x+y) = \\alpha \\cdot x + \\beta \\cdot y$ (scalar multiplication distributes over vector addition)\n",
    "\n",
    "Then $(\\mathcal{X}, +, \\cdot)$ is a real linear vector space.\n",
    "\n",
    "One generally omits the $\\cdot$ notation and just writes $\\alpha x$ rather than $\\alpha \\cdot x$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Linear Independence and Algebraic Bases\n",
    "\n",
    "A set of vectors $S \\subset \\mathcal{X}$ of a linear vector space $\\mathcal{X}$ is _linearly independent_ if for every finite subset $\\{s_1, \\ldots, s_n \\} \\subset S$, and every set of scalars $\\{\\alpha_1, \\ldots, \\alpha_n\\}$ if $\\sum_{j=1}^n \\alpha_js_j = 0$, then $\\alpha_1 = \\cdots = \\alpha_n = 0$.\n",
    "\n",
    "An _algebraic basis_ $B \\subset \\mathcal{X}$ for a linear vector space $\\mathcal{X}$ is a linearly independent collection of vectors such that for any $x \\in \\mathcal{X}$, there exists a finite subset $\\{b_j\\}_{j=1}^n$ and a set of scalars $\\{\\alpha_j \\}_{j=1}^n$\n",
    "such that $ x = \\sum_{j=1}^n \\alpha_j b_j$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Real Inner Product Spaces\n",
    "\n",
    "Let $\\mathcal{X}$ be a real linear vector space and let $\\langle \\cdot, \\cdot \\rangle : \\mathcal{X} \\times \\mathcal{X}\n",
    "\\to \\mathbb{R}$ such that for all $x, y, z \\in \\mathcal{X}$ and all $\\alpha, \\beta \\in \\mathbb{R}$,\n",
    "\n",
    "+ $\\langle x, y \\rangle = \\langle y, x \\rangle$ (symmetry)\n",
    "+ $\\langle \\alpha x, y \\rangle = \\alpha \\langle y, x \\rangle$ (scalar homogeneity)\n",
    "+ $\\langle x+y, z \\rangle = \\langle x, z \\rangle + \\langle y, z \\rangle $ (additive)\n",
    "+ $\\langle x, x \\rangle  \\ge 0 $ (positive semi-definite)\n",
    "+ $\\langle x, x \\rangle  = 0 $ if and only if $x = 0$ (positive definite)\n",
    "\n",
    "Then $(\\mathcal{X}, \\langle, \\rangle)$ is a real inner product space."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Norms\n",
    "\n",
    "Let $\\mathcal{X}$ be a real linear vector space and let $\\| \\cdot \\|: \\mathcal{X} \\to \\mathbb{R}^+$ such\n",
    "that for all $x, y, x \\in \\mathcal{X}$ and all $\\alpha \\in \\mathbb{R}$,\n",
    "\n",
    "+ $\\|x \\| = 0$ if and only if $x = 0$ (positive definite)\n",
    "+ $\\| \\alpha x \\| = |\\alpha| \\|x\\|$ (positive scalar homogeneity)\n",
    "+ $\\| x + y \\| \\le \\| x \\| + \\| y \\|$ (triangle inequality)\n",
    "\n",
    "Then $\\| \\cdot \\|$ is a _norm_ on $\\mathcal{X}$, and we call $\\mathcal{X}$ a _normed vector space_.\n",
    "\n",
    "### Cauchy sequences\n",
    "\n",
    "Suppose $\\mathcal{X}$ is a normed vector space with norm $\\| \\cdot \\|$, and let $x_1, x_2, \\ldots $\n",
    "be a sequence of elements of $\\mathcal{X}$.\n",
    "\\begin{equation*} \n",
    "   \\| x_{j+1} - x_j \\| \\rightarrow 0\n",
    "\\end{equation*}\n",
    "as $j \\rightarrow \\infty$, then $x_1, x_2, \\ldots $ is a _Cauchy sequence_.\n",
    "\n",
    "### Completeness\n",
    "\n",
    "A normed vector space is _complete_ if every Cauchy sequence in $\\mathcal{X}$ has a limit in $\\mathcal{X}$.\n",
    "That is, if $x_1, x_2, \\ldots $ is a Cauchy sequence, then there exists $x \\in \\mathcal{X}$ such that\n",
    "\\begin{equation*} \n",
    "   \\lim_{j \\rightarrow \\infty} \\| x_j - x \\| = 0.\n",
    "\\end{equation*}\n",
    "\n",
    "### Balls\n",
    "\n",
    "In a normed vector space $\\mathcal{X}$, the _closed ball of radius $\\epsilon > 0$ centered at $x \\in \\mathcal{X}$_ is\n",
    "\n",
    "\\begin{equation*}  B_\\epsilon [x_0] \\equiv \\{ x \\in \\mathcal{X}: \\|x - x_0\\| \\le \\epsilon \\}.\\end{equation*}\n",
    "\n",
    "The  the _open ball of radius $\\epsilon > 0$ centered at $x \\in \\mathcal{X}$_ is\n",
    "\n",
    "\\begin{equation*}  B_\\epsilon(x_0) \\equiv \\{ x \\in \\mathcal{X}: \\|x - x_0\\| < \\epsilon \\}.\\end{equation*}\n",
    "\n",
    "The (open) _unit ball_ in $\\mathcal{X}$ is $B_1[0]$ ($B_1(0)$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hilbert Space\n",
    "\n",
    "A _Hilbert space_ is an inner product space $(\\mathcal{X}, \\langle , \\rangle)$, endowed with the norm $\\|x \\| \\equiv \\sqrt{\\langle x, x \\rangle}$, that is complete with respect to that norm.\n",
    "\n",
    "### The Riesz Representation Theorem\n",
    "\n",
    "In a Hilbert space, every bounded linear functional can be represented as the inner product with some element of the space.\n",
    "\n",
    "That is, suppose $L$ is a bounded linear functional on a Hilbert space $\\mathcal{H}$:  $L(\\alpha x + \\beta y) = \\alpha L(x) + \\beta L(y)$ for all $x, y \\in \\mathcal{H}$ and all scalars $\\alpha$ and $\\beta$, and there exists a real number $C \\ge 0$ such that for all $x \\in \\mathcal{H}$, $|L(x)| \\le C \\|x\\|$.\n",
    "\n",
    "Then there exists $\\ell \\in \\mathcal{H}$ such that for all $x \\in \\mathcal{H}$, $L(x) = \\langle \\ell, x \\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Some useful sums \n",
    "\n",
    "### Finite arithmetic series\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{j=1}^N j = N(N+1)/2.\n",
    "\\end{equation}\n",
    "\n",
    "### Sum of squares\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{j=1}^N j^2 = N(N+1)(2N+1)/6.\n",
    "\\end{equation}\n",
    "\n",
    "### Sum of cubes\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{j=1}^N j^3 = (N(N+1)/2)^2.\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "### Geometric series\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{j=0}^\\infty a^j = \\frac{1}{1-a}, \\;\\; |a| < 1.\n",
    "\\end{equation}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}