{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Mathematical Preliminaries\n", "\n", "This chapter presents some basic mathematical notions, along with some more advanced results from probability, focusing on useful inequalities.\n", "\n", "It illustrates some of the mathematical notions using R, in some cases illustrating different algorithmic approaches\n", "to the same problem.\n" ] }, { "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", "+ $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", "+ ${\\mathbf Z} \\equiv \\{ \\ldots, -2, -1, 0, 1, 2, \\ldots \\}$: the integers.\n", "+ ${\\mathbf N} \\equiv \\{1, 2, 3, \\ldots \\}$: the natural (counting) numbers.\n", "+ $\\Re \\equiv (-\\infty, \\infty)$: the real numbers.\n", "+ $\\Re^+ \\equiv [-\\infty, \\infty]$: the extended real numbers.\n", "+ ${\\mathbf C} \\equiv \\{ a + bi: a, b \\in \\Re \\}$, where $i = \\sqrt{-1}$: the complex numbers.\n", "+ ${\\mathbf Q} \\equiv \\{ a/b: a, b \\in {\\mathbf Z}, b \\ne 0\\}$: 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 ${\\mathbf N} \\subset {\\mathbf Z} \\subset {\\mathbf Q} \\subset \\Re \\subset {\\mathbf 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_ or _set 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 ${\\mathbf R}$:\n", "$$\n", "[a, b] \\equiv \\{x \\in \\Re : a \\le x \\le b\\}\n", "$$\n", "$$\n", "(a, b] \\equiv \\{x \\in \\Re : a < x \\le b\\}\n", "$$\n", "$$\n", "[a, b) \\equiv \\{x \\in \\Re : a \\le x < b\\}\n", "$$\n", "$$\n", "(a, b) \\equiv \\{x \\in \\Re : a < x < b\\}.\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 ${\\mathbf Z}$, usually we write $A_i$ or $A_j$, etc.,\n", "rather than $A_\\beta$.\n", "If $B = {\\mathbf N}$, we usually write $\\{A_j\\}_{j=1}^\\infty$ rather than\n", "$\\{A_\\beta : \\beta \\in {\\mathbf 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 ${\\mathbf 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 {\\mathbf N}$.\n", "If a set is not finite, it is infinite.\n", "${\\mathbf N}$, ${\\mathbf Z}$, and ${\\mathbf Q}$ are infinite but countable;\n", "${\\mathbf 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 ${\\mathbf N}$), then $\\# A = \\aleph_0$ (aleph-null).\n", "If the elements of $A$ can be put in one-to-one correspondence with the elements of $\\mathbf{R}$, then\n", "$\\#A = c$, _the cardinality of the continuum_.\n", "\n", "The _power set_ of a set $A$, denoted $2^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 ${\\mathbf 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", "$$\n", "\n", "Suppose $A = A_1 \\cup A_2$, but that possibly $A_1 A_2 \\ne \\emptyset$,\n", "so $\\{A_1, A_2\\}$ might not be a partition of $A$, because\n", "$A_1$ and $A_2$ are not necessarily disjoint.\n", "Then still \n", "$$\\#A = \\#A_1 + \\#A_2 - \\#A_1A_2.$$\n", "\n", "This is seen most easily using a Venn diagram, and can be proved\n", "by constructing a partition of $A$,\n", "$A = A_1A_2^c \\cup A_1^cA_2 \\cup A_1A_2$, and noting that\n", "$\\#A_1 + \\#A_2 = \\#A_1A_2^c + \\#A_1^cA_2 + 2\\#A_1A_2$.\n", "\n", "If \n", "$A = A_1 \\cup A_2 \\cup A_3$ but $\\{A_1, A_2, A_3\\}$ are not necessarily disjoint,\n", "then still\n", "\n", "$$\\#A = \\#A_1 + \\#A_2 + \\#A_3 - \\#A_1A_2 - \\#A_1A_3 - \\#A_2A_3 + \\#A_1A_2A_3.$$\n", "\n", "More generally, if $A = \\cup_{i=1}^n A_i$, then the _Inclusion-Exclusion Principle_ holds:\n", "\n", "$$ \\#A = \\sum_{i=1}^n \\#A_i - \\sum_{1 \\le i_1 < i_2 \\le n} \\#(A_{i_1}A_{i_2}) +\n", "\\sum_{1 \\le i_1 < i_2 < i_3 \\le n} \\#(A_{i_1}A_{i_2}A_{i_3}) - \\cdots \n", "+(-1)^{k-1} \\sum_{1 \\le i_1 < i_2 < \\cdots < i_k \\le n} \\# (A_{i_1}A_{i_2} \\cdots A_{i_k}) + \\cdots\n", "$$\n", "\n", "### Some useful set relations\n", "\n", "+ If $A\\subset B$ and $B\\subset A$ then $A = B$. (If two sets are subsets of each other, they are the same set.)\n", "\n", "+ $\\emptyset \\subset A$. (The empty set is a subset of every set.)\n", "\n", "+ $\\emptyset \\cup A = A$.\n", "(The union of the empty set and any other set is that set.)\n", "\n", "+ $\\emptyset \\cap A = \\emptyset$.\n", "(The intersection of the empty set and any other set is empty.)\n", "\n", "+ If $A \\subset B$ and $B \\subset C$ then $A \\subset C$. (The subset relation is transitive.)\n", "\n", "+ If $A \\subset B$ then $B^c \\subset A^c$.\n", "(Complementation reverses the subset relation.)\n", "\n", "+ $A \\cap B \\subset A$. Moreover, $A\\cap B = A$ if and only if $A \\subset B$.\n", "\n", "+ $A \\subset A\\cup B$. Moreover, $A = A\\cup B$ if and only if $B \\subset A$.\n", "\n", "+ $(A\\cap B)^c = A^c \\cup B^c$. (de Morgan)\n", "\n", "+ $(A\\cup B)^c = A^c\\cap B^c$. (de Morgan)\n", "\n", "+ $A \\cap B = B \\cap A$. (Intersection is commutative.)\n", "\n", "+ $A\\cup B = B\\cup A$. (Union is commutative.)\n", "\n", "+ $A\\cap (B\\cap C) = (A\\cap B)\\cap C$. (Intersection is associative.)\n", "\n", "+ $A\\cup (B\\cup C) = (A\\cup B)\\cup C$. (Union is associative.)\n", "\n", "+ $A\\cap (B\\cup C) = (A\\cap B)\\cup (A\\cap C)$. (Distribution of intersection over union.)\n", "\n", "+ $A\\cup (B\\cap C) = (A\\cup B)\\cap (A\\cup C)$. (Distribution of union over intersection.)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Sets in R" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "A: 1 2 3 3 \n", "A as a set (duplicates removed): 1 2 3 \n", "1 is in A: TRUE \n", "1 is in A (2nd method): TRUE \n", "\"green\" is in A: FALSE \n", "\"green\" is in B: TRUE \n" ] } ], "source": [ "# Make three sets, A = {1, 2, 3}, B = {\"a\", \"b\", \"green\", 3}, C = {1, 2}\n", "A <- c(1, 2, 3, 3); # this is a list but not a set, because 3 is listed twice\n", "cat('A:',A,'\\n')\n", "A <- unique(A); # this is a set containing the unique elements of A\n", "cat('A as a set (duplicates removed):',A,'\\n')\n", "B <- c(\"a\", \"b\", \"green\", 3);\n", "C <- 1:2; #a different construction\n", "#\n", "# Set membership\n", "cat('1 is in A:',1 %in% A,'\\n') # is 1 an element of A?\n", "# another way to check set membership\n", "cat('1 is in A (2nd method):',is.element(1, A),'\\n')\n", "cat('\"green\" is in A:',\"green\" %in% A,'\\n')\n", "cat('\"green\" is in B:',\"green\" %in% B,'\\n')\n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "C a subset of A: TRUE \n", "C a subset of B: FALSE \n", "C is a subset of C: TRUE \n", "C a subset of A: TRUE \n", "C a subset of B: FALSE \n", "C a subset of C: TRUE \n" ] } ], "source": [ "# Subsets. We will look at two approaches:\n", "\n", "# A is a subset of B if a is an element of B for every a in A\n", "cat('C a subset of A:',all(C %in% A),'\\n') # C is a subset of A\n", "cat('C a subset of B:',all(C %in% B),'\\n') # C is not a subset of B\n", "cat('C is a subset of C:',all(C %in% C),'\\n') # C is a subset of itself\n", "\n", "# A is a subset of B if A\\B is empty\n", "cat('C a subset of A:',length(setdiff(C,A)) == 0,'\\n') # C is a subset of A\n", "cat('C a subset of B:',length(setdiff(C,B)) == 0,'\\n') # C is not a subset of B\n", "cat('C a subset of C:',length(setdiff(C, C)) == 0,'\\n') # C is a subset of itself\n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "AUB: 1 2 3 a b green \n", "AB: 3 \n", "A\\B: 1 2 \n" ] } ], "source": [ "# unions and intersections\n", "cat('AUB:',union(A,B), '\\n') # union of A and B\n", "cat('AB:',intersect(A, B), '\\n') # intersection of A and B\n", "\n", "# set difference\n", "cat('A\\\\B:',setdiff(A,B), '\\n') # A \\ B" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "3" ], "text/latex": [ "3" ], "text/markdown": [ "3" ], "text/plain": [ "[1] 3" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "4" ], "text/latex": [ "4" ], "text/markdown": [ "4" ], "text/plain": [ "[1] 4" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Cardinality of a finite set\n", "\n", "length(unique(A)) # A has 3 (unique) elements\n", "length(unique(B)) # B has 4 (unique) elements" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "'2^A:'" ], "text/latex": [ "'2^A:'" ], "text/markdown": [ "'2^A:'" ], "text/plain": [ "[1] \"2^A:\"" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
Var1 | Var2 | Var3 | |
---|---|---|---|
1 | 1 | a | 1 |
2 | 2 | a | 1 |
3 | 3 | a | 1 |
4 | 1 | b | 1 |
5 | 2 | b | 1 |
6 | 3 | b | 1 |
7 | 1 | green | 1 |
8 | 2 | green | 1 |
9 | 3 | green | 1 |
10 | 1 | 3 | 1 |
11 | 2 | 3 | 1 |
12 | 3 | 3 | 1 |
13 | 1 | a | 2 |
14 | 2 | a | 2 |
15 | 3 | a | 2 |
16 | 1 | b | 2 |
17 | 2 | b | 2 |
18 | 3 | b | 2 |
19 | 1 | green | 2 |
20 | 2 | green | 2 |
21 | 3 | green | 2 |
22 | 1 | 3 | 2 |
23 | 2 | 3 | 2 |
24 | 3 | 3 | 2 |