math-foundations.ipynb

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