{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Mathematical Preliminaries" ] }, { "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", "$$\n", " A \\cap B \\equiv \\{a: a \\in A \\mbox{ and } a \\in B \\}.\n", "$$\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", "$$\n", " A \\cup B \\equiv \\{a: a \\in A \\mbox{ or } a \\in B \\mbox{ or both} \\}.\n", "$$\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", "$$\n", " A \\setminus B \\equiv \\{a \\in A : a \\not \\in B \\} = A \\cap B^c.\n", "$$\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", "$$\n", " \\bigcap_{\\beta \\in B} A_\\beta \\equiv \\{a: a \\in A_\\beta \\;\\;\\forall \\beta \\in B \\}.\n", "$$\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", "$$\n", " \\{ \\emptyset, \\{a\\}, \\{b\\}, \\{c\\}, \\{a, b\\}, \\{a, c\\}, \\{b, c\\}, \\{a, b, c\\} \\}.\n", "$$\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", "$$\n", " \\# A = \\sum_{\\beta \\in B} \\# A_\\beta.\n", "$$" ] }, { "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", "$$\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 set of a set with $n$ elements can be partitioned as\n", "$$\n", " \\cup_{k=0}^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", "$$" ] }, { "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", "$$\n", " fA = f(A) \\equiv \\{ y \\in \\mathcal{Y} : (x, y) \\in f \\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 $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", "$$\n", " f^{-1}B \\equiv \\{ x \\in \\mathcal{X} : fx \\in B \\}.\n", "$$\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": [ "## 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. But viewed as _multisets_, they are different, because the second contains the element 1 twice.\n", "One can think of a multiset as an ordered pair, the first element of which is itself the set of distinct elements of the multiset, and the second of which is a function that assigns a natural number to each element of the set of elements. For instance, the multiset $\\{0, 1, 1\\}$ would be represented $ (\\{0, 1\\}, \\{(0, 1), (1, 2) \\})$.\n", "\n", "Two multisets 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 $\\{0, 1, 1\\}$ and $\\{1, 0, 1\\}$ 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$ will denote the multiset containing all\n", "$n$ of its coordinates." ] }, { "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", " \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": { "collapsed": true }, "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": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "anaconda-cloud": {}, "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.1" } }, "nbformat": 4, "nbformat_minor": 1 }