(************** Content-type: application/mathematica ************** CreatedBy='Mathematica 5.0' Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. *******************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 79219, 2897]*) (*NotebookOutlinePosition[ 94020, 3431]*) (* CellTagsIndexPosition[ 91080, 3311]*) (*WindowFrame->Normal*) Notebook[{ Cell["\[Copyright] K. Sutner 2004", "SmallText"], Cell[CellGroupData[{ Cell["Sets", "Title", CellTags->"c:1"], Cell[CellGroupData[{ Cell["Set Equations", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:2"], Cell[CellGroupData[{ Cell[BoxData[ \(Task\)], "Subsubsection", CellTags->"c:3"], Cell[TextData[{ "a) Explain why for any two sets ", Cell[BoxData[ \(TraditionalForm\`A\)]], " and ", Cell[BoxData[ \(TraditionalForm\`B\)]], " we have ", Cell[BoxData[ \(TraditionalForm\`\((A - B)\)\ \[Union] \ \((B - A)\)\ = \ \((A \[Union] B)\) - \((A \[Intersection] B)\)\)]], ". \nb) Demonstrate the validity of the equation by computing with sets \ (implemented as lists) in ", StyleBox["Mathematica", FontSlant->"Italic"], ". To this end, generate lists of random numbers, and check that the \ equation holds. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Commands\)], "Subsubsection", CellTags->"c:4"], Cell[TextData[{ " ", ButtonBox["Union", ButtonStyle->"RefGuideLink"], ", ", ButtonBox["Intersection", ButtonStyle->"RefGuideLink"], ", ", ButtonBox["Complement", ButtonStyle->"RefGuideLink"], ", ", ButtonBox["==", ButtonStyle->"RefGuideLink"], ", ", ButtonBox["Table", ButtonStyle->"RefGuideLink"], ", ", ButtonBox["Random", ButtonStyle->"RefGuideLink"], ", ", ButtonBox["==", ButtonStyle->"RefGuideLink"], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Solution\)], "Subsection", CellTags->"c:5"], Cell["\<\ The first set consists of all elements that are either in A or in \ B. That is the same as taking all elements of A and B together, and \ eliminating those that occur in both sets. That is exactly the second set. \ \ \>", "Text"], Cell["\<\ We produce random sets of, say, integers and test the assertion. \ Note the Union to get rid of duplicates. \ \>", "Text"], Cell[BoxData[ \(randomNums[] := Union[Table[Random[Integer, {1, 1000}], {50}]]\)], "Input"], Cell[BoxData[ \(randomNums[]\)], "Input"], Cell["\<\ Execute the following cell a number of times, and let me know if \ the answer False ever appears.\ \>", "Text"], Cell[BoxData[{ \(A = randomNums[]; \), "\n", \(B = randomNums[]; \), "\n", \(Complement[A, B] \[Union] Complement[B, A] \[Equal] Complement[A \[Union] B, A \[Intersection] B]\)}], "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Recursive Cartesian Product", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->{"cartesian product", "c:6"}], Cell[CellGroupData[{ Cell[BoxData[ \(Background\)], "Subsubsection", CellTags->"c:7"], Cell[TextData[{ "The Cartesian product of two lists is defined to be the list of all pairs \ of elements where the first element in the pair is from the first list, and \ the second element is from the second list. For example, \n\n ", StyleBox["cart[ {1,2}, {a,b} ] \[DoubleLongRightArrow] \ {{1,a},{1,b},{2,a},{2,b}} \n ", "Input"], "\nThe order of the output list does not matter here. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Task\)], "Subsubsection", CellTags->"c:8"], Cell[TextData[{ "Write a recursive function ", StyleBox["cart[A_List,B_List]", "Input"], " that computes the Cartesian product of two lists A and B. Note that \ there is no need to assume that the lists have the same length (compare to \ the pairing function). " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Commands\)], "Subsubsection", CellTags->"c:9"], Cell[TextData[{ ButtonBox["Join", ButtonStyle->"RefGuideLink"], ", ", ButtonBox["Map", ButtonStyle->"RefGuideLink"], ", ", ButtonBox["Table", ButtonStyle->"RefGuideLink"], ", also see section on pattern matching" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Solution\)], "Subsection", CellTags->"c:10"], Cell["\<\ The easiest way to tackle this problem is to use pattern matching \ on the argument side of the function definition. \ \>", "Text"], Cell[BoxData[{ \(\(cart[A_List, {}] = {};\)\), "\n", \(\(cart[A_List, {bb___, b_}] := Join[cart[A, {bb}], \(({#1, b} &)\) /@ A];\)\)}], "Input"], Cell[BoxData[ \(cart[{1, 2, 3, 4}, {a, b, c}]\)], "Input"], Cell["Of course, you can also give a more procedural solution. ", "Text"], Cell[BoxData[ \(\(cart[A_List, B_List] := If[B === {}, {}, Join[cart[A, Drop[B, \(-1\)]], \(({#1, Last[B]} &)\) /@ A]];\)\)], "Input"], Cell["\<\ And, you can go overboard and try to find some list handling \ command in Mathematica that takes care of Cartesian products. One tempting \ solution is to use Outer, originally designed to compute outer products of \ vectors. \ \>", "Text"], Cell[BoxData[ \(Outer[f, {1, 2, 3}, {a, b}]\)], "Input"], Cell["\<\ The right function f here is simply List, and we have to flatten \ the result by one level to get a plain list of pairs. \ \>", "Text"], Cell[BoxData[{ \(Clear[cart]\), "\n", \(\(cart[A_List, B_List] := Flatten[Outer[List, A, B], 1];\)\)}], "Input"], Cell[BoxData[ \(cart[{1, 2, 3, 4}, {a, b, c}]\)], "Input"], Cell["\<\ This works fine as long as the lists do not contain lists as \ elements, but fails miserably if they do. \ \>", "Text"], Cell[BoxData[ \(cart[{1, 2, 3}, {{}, {a}}]\)], "Input"], Cell["\<\ This problem can be fixed (Outer is designed to handle tensors of \ arbitrary depth, so we have to dissuade it from going below the first level), \ but it's not worth the effort: there is a better solution based on yet \ another cryptic command, namely Distribute. \ \>", "Text"], Cell[BoxData[{ \(Clear[cart]\), "\n", \(\(cart[A_List, B_List] := Distribute[{A, B}, List];\)\)}], "Input"], Cell["Now, everything works. ", "Text"], Cell[BoxData[{ \(cart[{1, 2, 3, 4}, {a, b, c}]\), "\n", \(cart[{1, 2, 3}, {{}, {a}}]\)}], "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Prime Factors", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:11"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", Evaluatable->False, CellTags->"c:12"], Cell[TextData[{ "Recall that every positive integer ", Cell[BoxData[ \(TraditionalForm\`n\)]], " can be written uniquely as a product of powers of primes:\n\n\t\t", Cell[BoxData[ \(TraditionalForm\`n\ = \ \(p\_1\%\(\(\ \)\(e\_\(\(1\)\(\ \)\)\)\)\) \ \(p\_2\%\(\(\ \)\(e\_2\)\)\) \[Ellipsis]\ \ p\_k\%\(\(\ \)\(e\_k\)\)\)]], ".\n\t\t\nFix some prime ", Cell[BoxData[ \(TraditionalForm\`p\)]], ", and define the following relation on the positive integers:\n\n\t\t", Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\ y\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\[Exists] \ k\ \((\ \ p\^k\ divides\ \ y\ \ \[And] \ \ \(p\^\(\(k\)\(\ \)\)\) does\ not\ divide\ x\ )\)\)]] }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:13"], Cell[TextData[{ "(a) Show that the relation ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\)]], " from above is a strict preorder (irreflexive and transitive). \n\n(b) \ What does it mean for two numbers to be incomparable with respect to this \ preorder? \n\n(c) As we will show in the problem on sorting below, being \ incomparable is an equivalence relation. \nDescribe the equivalence class of \ ", Cell[BoxData[ \(TraditionalForm\`x = 100\)]], " for all choices of ", Cell[BoxData[ \(TraditionalForm\`p\)]], ". " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:14"], Cell["Part a", "Subsubsection", CellTags->"c:15"], Cell["Part b", "Subsubsection", CellTags->"c:16"], Cell["Part c", "Subsubsection", CellTags->"c:17"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Set Operations", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:18"], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:19"], Cell[TextData[{ "Which of the following equations hold for all sets ", Cell[BoxData[ \(TraditionalForm\`A, \ B, \ C\)]], " ? \nIn each case, either prove that the equation always holds, or produce \ a (small) counterexample. \n\na) ", Cell[BoxData[ \(TraditionalForm\`A\ \[Intersection] \ B\ = \ B\ \[Intersection] \ A\)]], "\nb) ", Cell[BoxData[ \(TraditionalForm\`\((A\ - \ B)\)\ \[Intersection] \ C\ = \ \(\(\((A \[Intersection] C)\)\(\ \)\)\(-\)\(\ \)\(B\)\(\ \)\)\)]], "\nc) ", Cell[BoxData[ \(TraditionalForm\`\(\(A\)\(\ \)\(-\)\(\ \)\((B\ \[Intersection] \ C)\)\(\ \)\) = \ \((A - B)\) \[Intersection] \((A - C)\)\)]], "\nd) ", Cell[BoxData[ \(TraditionalForm\`A\ \[Intersection] \ \((B\ \[Union] \ C)\)\ = \ \((A \[Intersection] B)\) \[Union] \((A \[Intersection] C)\)\)]], "\ne) ", Cell[BoxData[ \(TraditionalForm\`\(\(A\)\(\ \)\(-\)\(\ \)\((B\ \[Union] \ C)\)\(\ \)\) = \ \((A - B)\) \[Intersection] \((A - C)\)\)]], "\nf) ", Cell[BoxData[ \(TraditionalForm\`\(\(A\)\(\ \)\(-\)\(\ \)\((B - C)\)\(\ \)\) = \ \((A - B)\)\ - \ C\)]], "\ng) ", Cell[BoxData[ \(TraditionalForm\`\(\((A - B)\)\(\ \)\(-\)\(\ \)\(C\)\(\ \)\) = \ \((A - C)\) - B\)]] }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:20"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:21"], Cell["\<\ True. The order of the arguments in intersection does not matter (same as for \ logical \[And] ). \ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:22"], Cell[TextData[{ "True.\nBoth sets describe the collection of all ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ A\)]], " such that:\n\t ", Cell[BoxData[ \(TraditionalForm\`x\ \[NotElement] \ B\)]], " and ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ C\)]], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:23"], Cell[TextData[{ "False.\nLet ", Cell[BoxData[ \(TraditionalForm\`A\ = \ \(B\ = {1}\)\)]], ", and ", Cell[BoxData[ \(TraditionalForm\`C\ = \ \(\(\[EmptySet]\)\(.\)\)\)]], "\nThen RHS ", Cell[BoxData[ \(TraditionalForm\`\(\(=\)\(\ \)\) A\)]], " but LHS ", Cell[BoxData[ \(TraditionalForm\`\(\(=\)\(\ \)\) \[EmptySet]\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part d", "Subsubsection", CellTags->"c:24"], Cell[TextData[{ "True.\nBoth sets describe the collection of all ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ A\)]], " such that:\n\t ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ B\)]], " or ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ C\)]], " " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part e", "Subsubsection", CellTags->"c:25"], Cell[TextData[{ "True.\nBoth sets describe the collection of all ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ A\)]], " such that:\n\t ", Cell[BoxData[ \(TraditionalForm\`x\ \[NotElement] \ B\)]], " and ", Cell[BoxData[ \(TraditionalForm\`x\ \[NotElement] \ C\)]], " " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part f", "Subsubsection", CellTags->"c:26"], Cell[TextData[{ "False.\nLet ", Cell[BoxData[ \(TraditionalForm\`A\ = \ \(B\ = \(C\ = {1}\)\)\)]], ".\nThen RHS ", Cell[BoxData[ \(TraditionalForm\`\(\(=\)\(\ \)\) A\)]], " but LHS ", Cell[BoxData[ \(TraditionalForm\`\(\(=\)\(\ \)\) \[EmptySet]\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part g", "Subsubsection", CellTags->"c:27"], Cell[TextData[{ "True.\nBoth sets describe the collection of all ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ A\)]], " such that:\n\t ", Cell[BoxData[ \(TraditionalForm\`x\ \[NotElement] \ B\)]], " and ", Cell[BoxData[ \(TraditionalForm\`x\ \[NotElement] \ C\)]], " " }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Symmetric Difference", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:28"], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:29"], Cell[TextData[{ "Write ", Cell[BoxData[ \(TraditionalForm\`A\ \[CapitalDelta]\ B\ = \ \((A\ - B)\)\ \[Union] \ \((B\ - \ A)\)\)]], " for the symmetric difference of two sets. \n\na) Show that ", Cell[BoxData[ \(TraditionalForm\`A\ \[CapitalDelta]\ A\ = \ \[EmptySet]\)]], ". \nb) Show that ", Cell[BoxData[ \(TraditionalForm\`\[CapitalDelta]\)]], " is associative: ", Cell[BoxData[ \(TraditionalForm\`A\ \[CapitalDelta]\ \((\ B\ \[CapitalDelta]\ C)\)\ = \ \((A\ \[CapitalDelta]\ B)\)\ \ \[CapitalDelta]\ C\)]], ". \nc) Is symmetric difference monotonic in the sense that \n\t", Cell[BoxData[ \(TraditionalForm\`A\ \[SubsetEqual] \ B\ \ \[Implies] \ \ A\ \[CapitalDelta]\ C\ \ \[SubsetEqual] \ B\ \[CapitalDelta]\ C\)]], "\nfor all sets ", Cell[BoxData[ \(TraditionalForm\`A, \ B, \ C\)]], " ?" }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:30"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:31"], Cell[TextData[{ "This is really obvious from the definition:\n\n\t", Cell[BoxData[ \(TraditionalForm\`A\ \[CapitalDelta]\ A\ \ = \ \(\((A - A)\)\ \[Union] \ \((A - A)\)\ = \ \[EmptySet]\)\)]], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:32"], Cell[TextData[{ " Here is a truth table \n\n ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ A\)]], ", ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ B\)]], ", ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ C\)]], ", ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ A\ \[CapitalDelta]\ B\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\(\(\(\ \)\(\(x\ \[Element] \ B\ \[CapitalDelta]\ C\)\(,\)\)\)\(\ \)\)\)]], " ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ \((A\ \[CapitalDelta]\ B)\)\ \ \[CapitalDelta]\ C\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(x\ \[Element] \ \(\(\(A\)\(\ \)\) \(\ \[CapitalDelta]\)\(\ \)\((B\ \[CapitalDelta]\ C)\)\(\ \)\)\)\)\)]], "\n 0\t 0\t 0\t 0\t 0\t\t 0\t\t 0\n 0\t 0\t 1\t 0\t \ 1\t\t 1\t\t 1\n 0\t 1\t 0\t 1\t 0\t\t 1\t\t 1\n \ 0\t 1\t 1\t 1\t 0\t\t 0\t\t 0\n 1\t 0\t 0\t 1\t \ 0\t\t 1\t\t 1\n 1\t 0\t 1\t 1\t 0\t\t 0\t\t 0\n 1\t \ 1\t 0\t 0\t 1\t\t 0\t\t 0\n 1\t 1\t 1\t 0\t 0\t\t\ 1\t\t 1\n\n The last two columns match, done. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:33"], Cell[TextData[{ "False. \nLet ", Cell[BoxData[ \(TraditionalForm\`A\ = \ \[EmptySet]\)]], ", ", Cell[BoxData[ \(TraditionalForm\`B = \(C\ = \ {1}\)\)]], ".\nThen ", Cell[BoxData[ \(TraditionalForm\`A\ \[CapitalDelta]\ C\ = \ {1}\)]], " but ", Cell[BoxData[ \(TraditionalForm\`B\ \[CapitalDelta]\ C\ = \ \[EmptySet]\)]], ". " }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["4-element Subsets", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:34"], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:35"], Cell[TextData[{ "Let ", Cell[BoxData[ \(TraditionalForm\`A\)]], " be a set of cardinality 10. Find the largest family of 4-element \ subsets of ", Cell[BoxData[ \(TraditionalForm\`A\)]], " with the property that any two subsets in the family overlap in at most \ one element. " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:36"], Cell[TextData[{ "This is a beauty. \n\nLet's write a table with ", Cell[BoxData[ \(TraditionalForm\`n\)]], " rows (where ", Cell[BoxData[ \(TraditionalForm\`n\)]], " is the yet unknown number of 4-element subsets), and 10 columns. In \ position ", Cell[BoxData[ \(TraditionalForm\`\((i, j)\)\)]], " put a zero if ", Cell[BoxData[ \(TraditionalForm\`j\)]], " is not in the ", Cell[BoxData[ \(TraditionalForm\`i\)]], "th subset, and a 1 otherwise. Hence, each row must contain exactly 4 ones. \ The table looks something like this:" }], "Text", Evaluatable->False], Cell[TextData[{ "\t", Cell[BoxData[GridBox[{ {"1", "1", "1", "1", "0", "0", "0", "0", "0", "0"}, {"1", "0", "0", "0", "1", "1", "1", "0", "0", "0"}, {"0", "1", "0", "0", "1", "0", "0", "1", "1", "0"}, {"0", "0", "1", "0", "0", "1", "0", "1", "0", "1"}, {"0", "0", "0", "1", "0", "0", "1", "0", "1", "1"} }]]] }], "Text", Evaluatable->False], Cell[TextData[{ "The strategy chosen to construct this table was to overlap the previous \ sets as much as possible, subject to the \"at most one\" condition. This \ solution is particularly uniform: each column contains exactly 2 ones (each \ element belongs to exactly 2 subsets). Note that there are ", Cell[BoxData[ \(TraditionalForm\`5\ \[CenterDot]\ 4\ /\ 2\ = \ 10\)]], " possible such columns, so this must be the \"canonical\" solution. \n\n\ What's that supposed to mean? \n\nSuppose you have a collection of subsets \ where an element is used three times. Then ", Cell[BoxData[ \(TraditionalForm\`n\ \[LessEqual] \ 3\)]], ". \nTo see this, look at the matrix (by renaming this is the general case, \ the shared element is 1). " }], "Text"], Cell[TextData[{ "\t", Cell[BoxData[GridBox[{ {"1", "1", "1", "1", "0", "0", "0", "0", "0", "0"}, {"1", "0", "0", "0", "1", "1", "1", "0", "0", "0"}, {"1", "0", "0", "0", "0", "0", "0", "1", "1", "1"} }]]] }], "Text", Evaluatable->False], Cell[TextData[{ "There simply is no room for another 4-set. \n\nSo, we may assume that \ every element is used only twice, i.e., that each column contains 2 ones. For \ ", Cell[BoxData[ \(TraditionalForm\`n = 5\)]], " this works out as in the first matrix: there are ", Cell[BoxData[ \(TraditionalForm\`4\[CenterDot]5 = \(20\ = \ 2\[CenterDot]10\)\)]], " ones.\nBut for ", Cell[BoxData[ \(TraditionalForm\`n \[GreaterEqual] 6\)]], " we need at least 24 ones, which is clearly impossible. " }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Kuratowski Pairs", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:37"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", Evaluatable->False, CellTags->"c:38"], Cell[TextData[{ "In lecture we have seen Kuratowski pairs defined by\n\n\t\t", Cell[BoxData[ \(TraditionalForm\`\((\ x, \ y\ )\)\ = \ {\ {x}, \ {x, y}\ }\)]], "\n\t\t\nas a method to produce order with unordered sets. " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:39"], Cell[TextData[{ "Show that this pair really works:\n\n\t\t", Cell[BoxData[ \(TraditionalForm\`\((\ x, \ y\ )\)\ = \ \((u, v)\)\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`x = u\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\ = \ v\)]], "\n" }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Hints:", "Subsubsection", Evaluatable->False, CellTags->"c:40"], Cell[TextData[{ "\nCareful, these are sets, not lists. For example, ", Cell[BoxData[ \(TraditionalForm\`\((x, x)\)\ = \ {{x}}\)]], ". " }], "Text", Evaluatable->False], Cell[TextData[{ "For reference, here is an implementation of the pairing function in \ Mathematica. Note the unions everywhere, they are necessary to make ", StyleBox["Mathematica", FontSlant->"Italic"], " lists behave more or less like real sets. " }], "Text", Evaluatable->False], Cell["kuratowski[x_,y_] := Union[ {{x},Union[{x,y}]} ];", "Input"], Cell["kuratowski[ {1,2}, {1,3,4} ]", "Input"], Cell["kuratowski[ {1,2}, {1,2} ]", "Input"] }, Closed]], Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:41"] }, Closed]], Cell[CellGroupData[{ Cell["Kuratowski Pairs Inverse", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:42"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", Evaluatable->False, CellTags->"c:43"], Cell[TextData[{ "In lecture we have seen that the Kuratowski pairing function\n\n\t\t", Cell[BoxData[ \(TraditionalForm\`\[LeftAngleBracket]\ x, \ y\ \[RightAngleBracket]\ = \ {\ {x}, \ {x, y}\ }\)]], "\n\t\t\nis invertible in the sense that \n\n\t\t", Cell[BoxData[ \(TraditionalForm\`\(\(\(\[LeftAngleBracket]\ x, \ y\ \[RightAngleBracket]\)\(\ \)\)\(=\)\(\ \)\(\[LeftAngleBracket]\ u, \ v\ \[RightAngleBracket]\)\(\ \)\)\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`x\ = \ u\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\ = \ v\)]], ".\n\nHere ", Cell[BoxData[ \(TraditionalForm\`x, \ y, \ u, \ v\)]], " are arbitrary sets. \nThe question arises how one can determine ", Cell[BoxData[ \(TraditionalForm\`x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\)]], ", given a pair ", Cell[BoxData[ \(TraditionalForm\`z\ = \ \[LeftAngleBracket]x, y\[RightAngleBracket]\)]], ". " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:44"], Cell[TextData[{ "(a) Find a function ", Cell[BoxData[ \(TraditionalForm\`p\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`p(\ \[LeftAngleBracket]x, y\[RightAngleBracket]\ )\ = \ x\)]], ". \n(b) Find a function ", Cell[BoxData[ \(TraditionalForm\`q\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`q(\ \[LeftAngleBracket]x, y\[RightAngleBracket]\ )\ = \ y\)]], ". \n(c) Implement and test your functions in Mathematica. \n\n", StyleBox["Hints", FontWeight->"Bold"], ":\nFor (a) and (b), write a purely mathematical definition, something like\ \n\n\t", Cell[BoxData[ \(TraditionalForm\`p( z)\ = \ \(\[Intersection]\ \(\[Intersection]\ z\)\)\)]], " \t\t ", StyleBox["\[WarningSign]", FontSize->16, FontColor->RGBColor[1, 0, 0]], StyleBox["THIS IS NOT RIGHT", FontColor->RGBColor[1, 0, 0]], " ", StyleBox["\[WarningSign]", FontSize->16, FontColor->RGBColor[1, 0, 0]], "\n\t\nThe only operations you will need to do this are unary union, unary \ intersection, complement, emptiness testing, and an if-then-else construct \ (definition by cases, needed only for ", Cell[BoxData[ \(TraditionalForm\`q\)]], "). \n\nThen convert your mathematical definitions into executable code. \n\ Do not use pattern matching, patterns for lists may not make sense for sets. \ " }], "Text", Evaluatable->False], Cell[TextData[{ "\nFor reference, here is an implementation of the pairing function in \ Mathematica. Note the unions everywhere, they are necessary to deal with the \ case ", Cell[BoxData[ \(TraditionalForm\`x = y\)]], ". " }], "Text", Evaluatable->False], Cell["kuratowski[x_,y_] := Union[ {{x},Union[{x,y}]} ];", "Input"], Cell["kuratowski[ {1,2}, {1,3,4} ]", "Input"], Cell["kuratowski[ {1,2}, {1,2} ]", "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Commands", "Subsubsection", CellTags->"c:45"], Cell[TextData[{ StyleBox[" ", FontWeight->"Bold"], ButtonBox["Union", ButtonStyle->"RefGuideLink"], StyleBox[", ", FontFamily->"Courier"], StyleBox[" ", FontWeight->"Bold"], ButtonBox["Intersection", ButtonStyle->"RefGuideLink"], StyleBox[", ", FontFamily->"Courier"], ButtonBox["Complement", ButtonStyle->"RefGuideLink"], StyleBox[", ", FontFamily->"Courier"], ButtonBox["Apply", ButtonStyle->"RefGuideLink"], StyleBox[", ", FontFamily->"Courier"], ButtonBox["If", ButtonStyle->"RefGuideLink"], StyleBox[", ", FontFamily->"Courier"], ButtonBox["With", ButtonStyle->"RefGuideLink"], StyleBox[".", FontFamily->"Courier"] }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:46"], Cell["kuratowski[x_,y_] := Union[ {{x},Union[{x,y}]} ];", "Input"], Cell["\<\ p[z_] := Union@@Intersection@@z q[z_] := With[ {zz = Complement[Union@@z,Intersection@@z]}, \t\t\t\tIf[ zz != {}, Union@@zz, p[z] ] ];\ \>", "Input"], Cell["z1 = kuratowski[{1,2,3},{1,2,3,4}]", "Input"], Cell["z2 = kuratowski[{1,3},{1,3}]", "Input"], Cell["\<\ p[z1] p[z2]\ \>", "Input"], Cell["\<\ q[z1] q[z2]\ \>", "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Countable Sets", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:47"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", Evaluatable->False, CellTags->"c:48"], Cell[TextData[{ "According to our definitions, a set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " is countable iff there is a bijection ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalN]\ \[LongRightArrow]\ A\)]], " (some authors also admit finite sets). \nAlso recall from lecture that \ there are bijections ", Cell[BoxData[ \(TraditionalForm\`\[Pi]\ : \ \[DoubleStruckCapitalN]\ \[Cross]\ \(\(\ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)\(\ \)\)\ \)]], ".\nWrite ", Cell[BoxData[ \(TraditionalForm\`\(\(\(\(\[Pi]\^\(\(\ \)\(-1\)\)\)( z)\)\(\ \)\)\(=\)\(\ \)\((\ \(\[Pi]\_\(\(\ \)\(1\)\)\)( z), \ \(\[Pi]\_\(\(\ \)\(2\)\)\)(z)\ )\)\(\ \)\)\)]], " for the inverse function. " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:49"], Cell[TextData[{ "a) Show that the union of two countable sets is countable. \nb) Show that \ ", Cell[BoxData[ \(TraditionalForm\`A\)]], " uncountable, ", Cell[BoxData[ \(TraditionalForm\`B\)]], " countable implies ", Cell[BoxData[ \(TraditionalForm\`A - B\)]], " uncountable.\nc) Show that any infinite subset of a countable set is \ itself countable. \nd) Suppose we have a countable family of countable sets \ ", Cell[BoxData[ \(TraditionalForm\`\((A\_\(\(\ \)\(i\)\))\)\_\(\(\ \)\(i\ \[Element] \ \ \[DoubleStruckCapitalN]\)\)\)]], ". \nShow that the union ", Cell[BoxData[ \(TraditionalForm\`A\ = \ \(\[Union]\_\(\(\ \)\(i\ \[Element] \ \ \[DoubleStruckCapitalN]\)\)A\_\(\(\ \)\(i\)\)\)\)]], " is also countable. " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:50"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", FontFamily->"Charter", CellTags->"c:51"], Cell[TextData[{ "Suppose ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ X\)]], " and ", Cell[BoxData[ \(TraditionalForm\`g\ : \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ Y\)]], " are both surjective. Define \n\n\t ", Cell[BoxData[ \(TraditionalForm\`h\ : \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ X\ \[Union] \ Y\)]], " by ", Cell[BoxData[ \(TraditionalForm\`h(2 x)\ = \ f(x)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`h(2 x + 1)\ = \ g(x)\)]], ". \n\t \nClearly, ", Cell[BoxData[ \(TraditionalForm\`h\)]], " is surjective. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", FontFamily->"Charter", CellTags->"c:52"], Cell[TextData[{ "\nSince ", Cell[BoxData[ \(TraditionalForm\`A\ = \ \ \((A\ - \ B)\)\ \[Union] \ \((A\ \[Intersection] \ B)\)\)]], " the claim follows immediately from part a): otherwise ", Cell[BoxData[ \(TraditionalForm\`A\)]], " would be countable. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", FontFamily->"Charter", CellTags->"c:53"], Cell[TextData[{ "Suppose ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ X\)]], " and ", Cell[BoxData[ \(TraditionalForm\`Y\ \[SubsetEqual] \ X\)]], " is infinite. Define \n\n\t", Cell[BoxData[ \(TraditionalForm\`g(0)\ = \ \ f(\ min(\ z\ | \ \ f(z)\ \[Element] \ Y)\ )\)]], "\nand\n\t", Cell[BoxData[ \(TraditionalForm\`g(n + 1)\ = \ f(\ \ min(\ z\ | \ \ f(z)\ \[Element] \ Y\ \ \[And] \ \ f(z)\ \[NotEqual] \ \ g(0), \ g(1), \ \[Ellipsis], \ g(n)\ )\ )\)]], ".\n\nSince ", Cell[BoxData[ \(TraditionalForm\`Y\)]], " is infinite, the domain of ", Cell[BoxData[ \(TraditionalForm\`g\)]], " is really all of ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalN]\)]], ". \nMoreover, since ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is surjective, the range of ", Cell[BoxData[ \(TraditionalForm\`g\)]], " is all of ", Cell[BoxData[ \(TraditionalForm\`Y\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part d", "Subsubsection", CellTags->"c:54"], Cell[TextData[{ "Fix surjections ", Cell[BoxData[ \(TraditionalForm\`f\_\(\(\(\ \)\(i\)\)\(\ \)\)\)]], " ", Cell[BoxData[ \(TraditionalForm\`\(\(:\)\(\ \)\) \[DoubleStruckCapitalN]\ \ \[LongRightArrow]\ A\_\(\(\ \)\(i\)\)\)]], " which exist by assumption. \n\nDefine ", Cell[BoxData[ \(TraditionalForm\`F\ : \ \[DoubleStruckCapitalN]\ \ \[LongRightArrow]\ \ A\)]], " by ", Cell[BoxData[ \(TraditionalForm\`F( z)\ = \ \ \(f\_\(\(\[Pi]\_1\)(z)\)\)(\(\[Pi]\_2\)(z))\)]], ". \n\nThen ", Cell[BoxData[ \(TraditionalForm\`F\)]], " is surjective since \[Pi] is surjective: for any ", Cell[BoxData[ \(TraditionalForm\`i\)]], " and ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ A\_\(\(\ \)\(i\)\)\)]], " there is a ", Cell[BoxData[ \(TraditionalForm\`n\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\(\[Pi]\^\(-1\)\)(n) = \((i, x)\)\)]], ". \n", Cell[BoxData[ \(TraditionalForm\`A\)]], " is infinite, since all the ", Cell[BoxData[ \(TraditionalForm\`A\_\(\(\ \)\(i\)\)\)]], " are infinite. Hence, by a theorem in class, ", Cell[BoxData[ \(TraditionalForm\`A\)]], " is countable. " }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Even and Odd Subsets", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:55"], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:56"], Cell[TextData[{ "One can show that the number of even size subsets of any finite set ", Cell[BoxData[ \(TraditionalForm\`A\ \[NotEqual] \ \[EmptySet]\)]], " is the same as the number of all odd size subsets. \n\n(a) Give a proof \ using the binomial theorem. \n(b) Give a direct proof by establishing a \ bijection. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", CellTags->"c:57"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:58"], Cell[TextData[{ "By the binomial theorem\n\n\t ", Cell[BoxData[ \(TraditionalForm\`\((1 + x)\)\^\(\(\ \)\(n\)\) = \ \[Sum]\ \ \(C(n, i)\)\ \ x\^\(\(\ \)\(i\)\)\)]], "\n\t \n\t \t ", Cell[BoxData[ \(TraditionalForm\`\(\(=\)\(\ \)\) \(\[Sum]\ \ \(C(n, 2 i)\)\ \ x\^\(\(\ \)\(2 i\)\)\ + \ \[Sum]\ \ \(C(n, 2 i + 1)\)\ \ x\^\(\(\ \)\(2 i + 1\)\)\)\)]], "\n\t \t \nSetting ", Cell[BoxData[ \(TraditionalForm\`x\ = \ \(-1\)\)]], ", we get \n\t \n\t ", Cell[BoxData[ \(TraditionalForm\`0\ = \ \[Sum]\ \ C(n, 2 i)\ \ \ - \ \[Sum]\(\(\ \)\(\ \)\) C(n, 2 i + 1) \(\(\ \)\(\ \)\)\)]], "\n\ndone.\n\nFor ", Cell[BoxData[ \(TraditionalForm\`n = 0\)]], " this argument fails: we get 1 from \[EmptySet]. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:59"], Cell[TextData[{ "Here is a function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\[ScriptCapitalP]( A)\)\ \[LongRightArrow]\ \(\[ScriptCapitalP](A)\)\)]], ". First, pick an element ", Cell[BoxData[ \(TraditionalForm\`a\ \[Element] \ A\)]], ". \nGiven ", Cell[BoxData[ \(TraditionalForm\`X \[SubsetEqual] \ A\)]], ", let\n\n\t ", Cell[BoxData[ \(TraditionalForm\`f(X)\ = \ X\ - \ {a}\)]], " \tif ", Cell[BoxData[ \(TraditionalForm\`a\ \[Element] \ X\)]], ", and\n\t ", Cell[BoxData[ \(TraditionalForm\`f(X)\ = \ X\ \[Union] \ {a}\)]], " \totherwise. \n\nClearly, ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is a bijection (even an involution): ", Cell[BoxData[ \(TraditionalForm\`f(f(X))\ = \ X\)]], " .\n\nBut ", Cell[BoxData[ \(TraditionalForm\`f\)]], " takes even cardinality sets to odd cardinality sets, and vice versa. \n\ Done.\n" }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Polynomials and Power Series", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:60"], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:61"], Cell[TextData[{ "(a) Consider polynomials \n\t", Cell[BoxData[ \(TraditionalForm\`p( x)\ = \ \(\[Sum]\_\(\(\ \)\(i\ \[LessEqual] \ k\)\)\ \(a\_\(\(\ \ \)\(i\)\)\) x\^\(\(\ \)\(i\)\)\ \ = \ a\_0\ + \ \(a\_\(\(1\)\(\ \)\)\) x\ + \ \[Ellipsis]\ + \ \(a\_n\) x\^\(\(\ \)\(k\)\)\)\)]], " \nwith rational coefficients. Show that there are only countably many \ such polynomials. \n\n(b) Now consider formal power series with rational \ coefficients, expressions of the form \n\t ", Cell[BoxData[ \(TraditionalForm\`p( x)\ = \ \(\[Sum]\_\(0\ \[LessEqual] \ i\)\ \(a\_\(\(\ \)\(i\)\)\) x\^\(\(\ \)\(i\)\)\ \ = \ a\_0\ + \ \(a\_\(\(1\)\(\ \)\)\) x\ + \ \(a\_\(\(\ \)\(2\)\)\) x\^\(\(\ \)\(2\)\)\ + \ \[Ellipsis]\ + \ \(a\_n\) x\^\(\(\ \)\(n\)\)\ + \ \[Ellipsis]\)\)]], " \nShow that there are uncountably many such power series. " }], "Text", Evaluatable->False, AspectRatioFixed->True, Background->GrayLevel[1]] }, Closed]], Cell[CellGroupData[{ Cell["Comment", "Subsubsection", CellTags->"c:62"], Cell[TextData[{ "Do not confuse formal power series with the converging series that are so \ important in calculus, convergence is no issue here. Power series are often \ used to provide a convenient way to express infinite sequences of numbers ", Cell[BoxData[ \(TraditionalForm\`\((a\_\(\(\ \)\(i\)\))\)\)]], ". The algebraic operations that make sense for power series can be very \ helpful in analyzing these sequences (see generating functions). \n\nYou can \ use any result from class, but make sure your arguments are clean. " }], "Text", Evaluatable->False, AspectRatioFixed->True, Background->GrayLevel[1]] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, AspectRatioFixed->True, FontFamily->"Times", FontSize->18, CellTags->"c:63"], Cell[TextData[{ "We know that there is a bijection ", Cell[BoxData[ \(TraditionalForm\`\[LeftAngleBracket]\ \[RightAngleBracket]\ : \ \ \(\ \(\[DoubleStruckCapitalN]\^\(\(\ \)\(*\)\)\[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)\(\ \)\)\)]], " which translates any sequence of natural numbers into a single natural \ number. It is easy to extend this function to sequences of integers. But a \ polynomial over \[DoubleStruckCapitalZ] is essentially just a finite \ sequence of integers: the sequence of the coefficients. Thus, there are only \ countably many polynomials over \[DoubleStruckCapitalZ] " }], "Text"], Cell[TextData[{ "We have seen in class that there are uncountably many infinite Boolean \ sequences. In other words, ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalN]\ \[LongRightArrow]\ {0, 1}\)]], " is uncountable. But each such sequence gives rise to a power series: \ just use the 0's and 1's as coefficients. Hence there are uncountably many \ power series over \[DoubleStruckCapitalZ]." }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Cardinality of Sets of Functions", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:64"], Cell[CellGroupData[{ Cell["Task", "Subsubsection", FontFamily->"Charter", CellTags->"c:65"], Cell[TextData[{ "Determine the cardinality of the following sets of functions, all subsets \ of ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalN]\ \[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)]], ". \na) ", Cell[BoxData[ \(TraditionalForm\`f(n + 2)\ = \ f(n)\)]], "\nb) ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is not a polynomial function ", Cell[BoxData[ \(TraditionalForm\`\[Sum]\_\(i\ \[LessEqual] \ k\)\ a\_i\ x\^\(\(\ \)\(i\)\)\)]], ".\nc) ", Cell[BoxData[ \(TraditionalForm\`f(n + 1)\ > \ f(n)\)]], "\nd) ", Cell[BoxData[ \(TraditionalForm\`f(n + 1)\ \ \[Element] \ {\ \ f(n), \ f(n)\ + \ 1\ }\)]], "\ne) ", Cell[BoxData[ \(TraditionalForm\`f(n + 1)\ \[LessEqual] \ f(n)\)]] }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Hint", "Subsubsection", FontFamily->"Charter", CellTags->"c:66"], Cell[TextData[{ "A very useful fact is that the set ", Cell[BoxData[ \(TraditionalForm\`{0, 1}\^\(\(\ \)\(\[Omega]\)\)\)]], " of all infinite binary sequences is uncountable. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", FontFamily->"Charter", CellTags->"c:67"], Cell[TextData[{ "In each case we write ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalF]\ \[SubsetEqual] \ \ \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)]], " for the set of functions inquestion. " }], "Text"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", FontFamily->"Charter", CellTags->"c:68"], Cell[TextData[{ "Here all the even numbers map to the same value, and all the odd numbers \ map to the same value. Hence, ", Cell[BoxData[ \(TraditionalForm\`f\ \[Element] \ \[DoubleStruckCapitalF]\)]], " is already completely determined by ", Cell[BoxData[ \(TraditionalForm\`f(0)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`f(1)\)]], ". Thus, there are only countably many such functions since ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalN]\ \[Cross]\ \ \[DoubleStruckCapitalN]\)]], " is countable. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", FontFamily->"Charter", CellTags->"c:69"], Cell[TextData[{ "Every function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)]], " whose range is ", Cell[BoxData[ \(TraditionalForm\`{0, 1}\)]], " is in ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalF]\)]], " unless it is the constant 0 or constant 1 function. But we have seen \ that there are uncountably many such functions (binary sequences). Hence ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalF]\)]], " is uncountable. \n\nAlternatively, use that ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalN]\ \[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)]], " is uncountable, but the forbidden functions form a countable set. We \ already know that \n\"uncountable - countable = uncountable\". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", FontFamily->"Charter", CellTags->"c:70"], Cell[TextData[{ "Again consider functions ", Cell[BoxData[ \(TraditionalForm\`g\ : \ \ \[DoubleStruckCapitalN]\ \ \[LongRightArrow]{0, 1}\)]], ". Given ", Cell[BoxData[ \(TraditionalForm\`g\)]], " define \n\n\t", Cell[BoxData[ \(TraditionalForm\`\(f\_g\)(0)\ = 0\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`\(f\_g\)(n + 1)\ = \ \(f\_g\)(n)\ + \ 1\ + \ g(n)\)]], "\n\nBy definition, ", Cell[BoxData[ \(TraditionalForm\`f\_\(\(\ \)\(g\)\)\ \[Element] \ \ \[DoubleStruckCapitalF]\)]], ". \nBut ", Cell[BoxData[ \(TraditionalForm\`g\)]], " can be retrieved from ", Cell[BoxData[ \(TraditionalForm\`f\_\(\(\ \)\(g\)\)\)]], ": \n\t\n\t", Cell[BoxData[ \(TraditionalForm\`g(n)\ = \ \(f\_\(\(\ \)\(g\)\)\)( n + 1)\ - \ \(f\_\(\(\ \)\(g\)\)\)(n)\ - \ 1\)]], ".\n\t\nHence there are uncountably many ", Cell[BoxData[ \(TraditionalForm\`f\_\(\(\ \)\(g\)\)\)]], "'s, and thus ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalF]\)]], " is uncountable. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part d", "Subsubsection", FontFamily->"Charter", CellTags->"c:71"], Cell[TextData[{ "For the umpteenth time, consider functions ", Cell[BoxData[ \(TraditionalForm\`g\ : \ \ \[DoubleStruckCapitalN]\ \ \[LongRightArrow]{0, 1}\)]], ". Given ", Cell[BoxData[ \(TraditionalForm\`g\)]], " define \n\n\t", Cell[BoxData[ \(TraditionalForm\`\(f\_g\)(0)\ = 0\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`\(f\_g\)(n + 1)\ = \ \(f\_g\)(n)\ + \ g(n)\)]], "\n\nBy definition, ", Cell[BoxData[ \(TraditionalForm\`f\_\(\(\ \)\(g\)\)\ \[Element] \ \ \[DoubleStruckCapitalF]\)]], ". \nAs in part (c), ", Cell[BoxData[ \(TraditionalForm\`g\)]], " can be retrieved from ", Cell[BoxData[ \(TraditionalForm\`f\_\(\(\ \)\(g\)\)\)]], ": \n\t\n\t", Cell[BoxData[ \(TraditionalForm\`g(n)\ = \ \(f\_\(\(\ \)\(g\)\)\)( n + 1)\ - \ \(f\_\(\(\ \)\(g\)\)\)(n)\)]], ".\n\t\nHence there are uncountably many ", Cell[BoxData[ \(TraditionalForm\`f\_\(\(\ \)\(g\)\)\)]], "'s, and thus ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalF]\)]], " is uncountable. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part e", "Subsubsection", FontFamily->"Charter", CellTags->"c:72"], Cell[TextData[{ "These functions are non-increasing:\n\n\t", Cell[BoxData[ \(TraditionalForm\`\(\(\(f(0)\)\(\ \)\)\(\[GreaterEqual]\)\(\ \)\(f( 1)\)\(\ \)\(\[GreaterEqual]\)\(\ \)\(f( 2)\)\(\ \)\(\[GreaterEqual]\)\(\ \)\(\[Ellipsis]\)\(\ \)\)\)]], "\n\nBut then, for any choice of ", Cell[BoxData[ \(TraditionalForm\`f(0)\ \[Element] \ \[DoubleStruckCapitalN]\)]], ", there are only countably many possible ways to choose values for ", Cell[BoxData[ \(TraditionalForm\`f(n)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`n > 0\)]], ". \nTo see this, note that we can code ", Cell[BoxData[ \(TraditionalForm\`f\)]], " by a sequence \n\n\t", Cell[BoxData[ \(TraditionalForm\`\((\ \((a\_0, b\_0 = 0)\), \ \((a\_1, b\_1)\), \ \((a\_2, b\_2)\), \ \[Ellipsis], \ \((a\_\(\(\ \)\(s\)\), b\_s)\)\ \ )\)\)]], "\n\t\nwhere ", Cell[BoxData[ \(TraditionalForm\`a\_\(i + 1\) < a\_i\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\_\(\(\ \)\(i\)\)\ \[LessEqual] \ x\ < \ b\_\(i + 1\)\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ a\_\(\(\ \)\(i\)\)\)]], ". Here we tacitily assume ", Cell[BoxData[ \(TraditionalForm\`b\_\(s + 1\) = \ \[Infinity]\)]], ". \n\nThus ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalF]\)]], " is uncountable. " }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Programs are Countable", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:73"], Cell[CellGroupData[{ Cell["Task", "Subsubsection", FontFamily->"Charter", CellTags->"c:74"], Cell["\<\ Show that the set of all Pascal (or Fortran, C, C++, Lisp, \ \[Ellipsis]) programs is countable. You can use all the results from lecture, but make sure that your argument is \ crisp and clear. \ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", FontFamily->"Charter", CellTags->"c:75"], Cell[TextData[{ "Any program is in essence just a sequence or list of ASCII characters. We \ can identify the ASCII characters with integers 0,1,2, \[Ellipsis], 255. But \ the set ", Cell[BoxData[ \(TraditionalForm\`List(\[DoubleStruckCapitalN])\)]], " of all lists of natural numbers is countable, so ", Cell[BoxData[ \(TraditionalForm\`List(\ {0, 1, \[Ellipsis], 255}\ )\)]], " must also be countable. \n\nAlternative proof: think of the program as \ a binary sequence (that's what it really looks like when it is sitting in \ memory). Every such binary sequence can be interpreted as a natural number, \ hence there are only countably many. " }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Cartesian Product", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:76"], Cell[CellGroupData[{ Cell["Task", "Subsubsection", FontFamily->"Charter", CellTags->"c:77"], Cell[TextData[{ "Recall the Kuratowski pair from class:\n\n\t", Cell[BoxData[ \(TraditionalForm\`\((x, y)\)\ = \ {\ {x}, \ {x, y}\ }\)]], "\n\t\nand the Cartesion product ", Cell[BoxData[ \(TraditionalForm\`A\ \[Cross]\ B\)]], " built from this pairing function. \n\na) Is the Cartesian product \ operation associative: ", Cell[BoxData[ \(TraditionalForm\`A\ \[Cross]\ \((\ B\ \[Cross]\ C)\)\ = \ \((A\[Cross]\ B)\)\ \[Cross]\ C\)]], " ?\n\nb) Show that there is a natural bijection between ", Cell[BoxData[ \(TraditionalForm\`\(\(A\ \[Cross]\ \((\ B\ \[Cross]\ C)\)\)\(\ \)\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\((A\[Cross]\ B)\)\ \[Cross]\ C\)\)\)]], ".\n\nc) What does this mean for ", Cell[BoxData[ \(TraditionalForm\`n\)]], "-tuples? " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Comment", "Subsubsection", FontFamily->"Charter", CellTags->"c:78"], Cell["\<\ This is an example of the difference between equality and \ isomorphism. Make sure you understand exactly what is goin on here.\ \>", \ "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", FontFamily->"Charter", CellTags->"c:79"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:80"], Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`A\ \[Cross]\ \((\ B\ \[Cross]\ C)\)\)]], " is not the same as ", Cell[BoxData[ \(TraditionalForm\`\((A\ \[Cross]\ B)\)\ \[Cross]\ C\)]], ".\nMore precisely, the two sets are distinct unless one of ", Cell[BoxData[ \(TraditionalForm\`A, \ B, \ C\)]], " is empty. \nThis is true even if all the three sets consist of just one \ lousy element. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:81"], Cell[TextData[{ "However, there is a straightforward bijection between the two products:\n\n\ \t", Cell[BoxData[ \(TraditionalForm\`f : \ A\ \[Cross]\ \((\ B\ \[Cross]\ C)\)\ \[LongRightArrow]\ \((A\ \[Cross]\ B)\)\ \[Cross]\ C\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`f(\ \ \((\(x\)\(,\)\(\ \)\((y, z)\)\(\ \))\)\ \ )\ = \ \ \((\ \((x, y)\), z\ )\)\)]], "\n\nThe fact that ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is really a bijection follows from the properties of the pairing \ function. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:82"], Cell[TextData[{ "This means that, say, the definition of triples is somewhat random: we \ could either choose ", Cell[BoxData[ \(TraditionalForm\`A\ \[Cross]\ \((\ B\ \[Cross]\ C)\)\)]], " or ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\((A\ \[Cross]\ B)\)\ \[Cross]\ C\)\)\)]], ". However, because of the bijection which exists by part b), either \ choice will work fine. \n\nAlso note that we could use different pairing \ functions to begin with, so there are indeed many different ways to define \ the notion of ", Cell[BoxData[ \(TraditionalForm\`n\)]], "-tuple. " }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Tripling Functions", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:83"], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:84"], Cell[TextData[{ "One can build a definition of triple on top of any definition of a pairing \ function, such as the Kuratowski pair ", Cell[BoxData[ \(TraditionalForm\`\((x, y)\)\)]], ". For example, we could define ", Cell[BoxData[ \(TraditionalForm\`\((x, y, z)\)\ = \ \((x, \((y, z)\))\)\)]], ". \n\nHowever, one could also try to give a direct definition.\n\na) \ Clearly state the property that makes a set function ", Cell[BoxData[ \(TraditionalForm\`\((x, y, z)\)\)]], " a tripling function. \n\nb) Which of the following attempts to defin a \ tripling function are successful:\n1. ", Cell[BoxData[ \(TraditionalForm\`{{x}, {x, y}, {x, y, z}}\)]], "\n2. ", Cell[BoxData[ \(TraditionalForm\`\((x, \((y, z)\))\)\)]], "\n3. ", Cell[BoxData[ \(TraditionalForm\`\((\((z, x)\), y)\)\)]], "\n4. ", Cell[BoxData[ \(TraditionalForm\`{{x, 0}, \ {y, 1}, \ {z, 2}}\)]], " where 0,1,2 are the usual von Neumann ordinals. " }], "Text", Evaluatable->False, AspectRatioFixed->True, Background->GrayLevel[1]] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, AspectRatioFixed->True, FontFamily->"Times", FontSize->18, CellTags->"c:85"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:86"], Cell[TextData[{ "The only condition is ", Cell[BoxData[ \(TraditionalForm\`\((x, y, z)\)\ = \ \((u, v, w)\)\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`x = u, \ y = v, \ z = w\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:87"], Cell[TextData[{ "1. Does not work: ", Cell[BoxData[ \(TraditionalForm\`\((x, y, x)\)\ = \ \((x, \ y, \ y)\)\)]], "." }], "Text"], Cell[TextData[{ "2. Works: Since ", Cell[BoxData[ \(TraditionalForm\`\((\(.\)\(\(,\)\(.\)\))\)\)]], " is a pairing function, ", Cell[BoxData[ \(TraditionalForm\`\((x, y, z)\)\ = \ \((u, v, w)\)\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`z = w\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\((x, y)\)\ = \ \((u, v)\)\)]], ", \nand thus ", Cell[BoxData[ \(TraditionalForm\`x = u\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y = v\)]], ". " }], "Text"], Cell[TextData[{ "3. Works for essentially the same reason as part (b): ", Cell[BoxData[ \(TraditionalForm\`\((\(.\)\(\(,\)\(.\)\))\)\)]], " is a pairing function, so\n", Cell[BoxData[ \(TraditionalForm\`\((x, y, z)\)\ = \ \((u, v, w)\)\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`y = v\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\((z, x)\)\ = \ \((w, u)\)\)]], ", \nand thus ", Cell[BoxData[ \(TraditionalForm\`z = w\)]], " and ", Cell[BoxData[ \(TraditionalForm\`x = u\)]], ". " }], "Text"], Cell[TextData[{ "4. Does not work: ", Cell[BoxData[ \(TraditionalForm\`\((0, 1, 2)\)\ = \ \((2, 0, 1)\)\)]], "." }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Implementing Set Operations", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:88"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", CellTags->"c:89"], Cell[TextData[{ "To represent a set in ", StyleBox["Mathematica", FontSlant->"Italic"], " we use a list, with the understanding that multiple occurences are not \ allowed, and that order does not play a role. E.g. \n\n\t\t", Cell[BoxData[ \(TraditionalForm\`{\ a, \ b, \ c, \ a, \ d\ }\)]], " is not allowed\n\t\t", Cell[BoxData[ \(TraditionalForm\`{\ a, \ b, \ c\ }\)]], " is the same as ", Cell[BoxData[ \(TraditionalForm\`{\ c, \ b, \ a\ }\)]], ". \n\t\t\nYou have seen in class how to implement a member query, and a \ polyadic union operation from scratch. Here are some more problems of this \ type. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:90"], Cell[TextData[{ "(a) Implement a ", StyleBox["complement", "Input"], " operation that mimics the behavior of the system function \n ", ButtonBox["Complement", ButtonStyle->"RefGuideLink"], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True, Background->GrayLevel[1]], Cell[TextData[{ "(b) Implement a ", StyleBox["intersection", "Input"], " operation that mimics the behavior of the system function \n ", ButtonBox["Intersection", ButtonStyle->"RefGuideLink"], ". Make sure that your function can deal with a variable number of \ arguments. " }], "Text", Evaluatable->False, AspectRatioFixed->True, Background->GrayLevel[1]], Cell[TextData[{ "(c) Implement a ", StyleBox["powerset", "Input"], " operation as defined in class. Pattern matching might come in handy." }], "Text", Evaluatable->False, AspectRatioFixed->True, Background->GrayLevel[1]] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Solution\)], "Subsection", Evaluatable->False, AspectRatioFixed->True, FontFamily->"Times", FontSize->18, CellTags->"c:91"], Cell[CellGroupData[{ Cell[BoxData[ \(Part\ a\)], "Subsubsection", CellTags->"c:92"], Cell[BoxData[ \(complement[A_List, B_List] := Select[A, \(! MemberQ[B, #1]\) &]; \)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Part\ b\)], "Subsubsection", CellTags->"c:93"], Cell[BoxData[{ \(intersection[A_List, B_List] := Select[A, MemberQ[B, #1] &]; \), "\n", \(intersection[A_List, B_List, C___List] := intersection[intersection[A, B], C]; \)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(intersection[{1, 2, 3}, {2, 3, 5}, {3, 4, 5}]\)], "Input"], Cell[BoxData[ \({3}\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Part\ c\)], "Subsubsection", CellTags->"c:94"], Cell[BoxData[{ \(powerset[{}] = {{}}; \), "\n", \(powerset[{a_, xx___}] := With[{p = powerset[{xx}]}, Join[p, \((Prepend[#1, a] &)\) /@ p]]; \)}], "Input"], Cell["The order is a bit funny, but it works:", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(powerset[{1, 2, 3}]\), "\n", \(Sort[%]\)}], "Input"], Cell[BoxData[ \({{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}}\)], "Output"], Cell[BoxData[ \({{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}\)], "Output"] }, Closed]] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Cartesian Products", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:95"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", CellTags->"c:96"], Cell[TextData[{ "To represent a set in ", StyleBox["Mathematica", FontSlant->"Italic"], " we use a list, with the understanding that multiple occurences are not \ allowed, and that order does not play a role. E.g. \n\n\t\t", Cell[BoxData[ \(TraditionalForm\`{\ a, \ b, \ c, \ a, \ d\ }\)]], " is not allowed\n\t\t", Cell[BoxData[ \(TraditionalForm\`{\ a, \ b, \ c\ }\)]], " is the same as ", Cell[BoxData[ \(TraditionalForm\`{\ c, \ b, \ a\ }\)]], ". \n\t\t\nYou have seen in class how to implement a member query, and a \ polyadic union operation from scratch. Here are some more problems of this \ type. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:97"], Cell[TextData[{ "Implement a ", StyleBox["cartprod", "Input"], " operation that computes the Cartesian product of its arguments (all \ presumed to be sets). Make sure that your function can deal with a variable \ number of arguments, including degenerate cases. Here are some examples:" }], "Text", Evaluatable->False, AspectRatioFixed->True, Background->GrayLevel[1]], Cell["\<\ cartprod[{a,b},{1,2,3}] \t\t\[DoubleLongRightArrow] {{a,1},{a,2},{a,3},{b,1},{b,2},{b,3}} \t\t cartprod[{a,b},{1,2,3},{c,d}] \t\t\[DoubleLongRightArrow] \ {{a,1,c},{a,1,d},{a,2,c},{a,2,d},{a,3,c},{a,3,d},{b,1,c},\t\t\t\ {b,1,d},{b,2,c},{b,2,d},{b,3,c},{b,3,d}} \t\t cartprod[{a,b},{},{c,d}] \[DoubleLongRightArrow] {} \t\t cartprod[{a,b}] \[DoubleLongRightArrow] {{a},{b}} \t\t cartprod[] \[DoubleLongRightArrow] {{}}\ \>", "Text", FontFamily->"Courier"], Cell["\<\ Explain how and why your function works. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True, Background->GrayLevel[1]] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Solution\)], "Subsection", Evaluatable->False, AspectRatioFixed->True, FontFamily->"Times", FontSize->18, CellTags->"c:98"], Cell["\<\ Note that it is a bit tricky to deal with a variable number of \ arguments here, the trick from part (b) of the previous problem will not \ work:\ \>", "Text"], Cell[BoxData[{ \(Clear[cp]\), "\n", \(cp[A_List, B_List] := Flatten[Table[{A\[LeftDoubleBracket]i\[RightDoubleBracket], B\[LeftDoubleBracket]j\[RightDoubleBracket]}, {i, Length[A]}, {j, Length[B]}], 1]; \), "\n", \(cp[A_List, B_List, C___List] := cp[cp[A, B], C]; \)}], "Input"], Cell[BoxData[ \(Clear[a, b, A, B]\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(cp[{1, 2, 3}, {a, b}]\)], "Input"], Cell[BoxData[ \({{1, a}, {1, b}, {2, a}, {2, b}, {3, a}, {3, b}}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(cp[{1, 2, 3}, {a, b}, {A, B}]\)], "Input"], Cell[BoxData[ \({{{1, a}, A}, {{1, a}, B}, {{1, b}, A}, {{1, b}, B}, {{2, a}, A}, {{2, a}, B}, {{2, b}, A}, {{2, b}, B}, {{3, a}, A}, {{3, a}, B}, {{3, b}, A}, {{3, b}, B}}\)], "Output"] }, Closed]], Cell[TextData[{ "But, we cannot simply flatten the output either, because then we would get \ the wrong answer for \n\n\t", StyleBox["cp[ cp[{1,2,3},{a,b}], {A,B} ]", "Input"] }], "Text"], Cell[TextData[{ "The trick is to avoid building the list structures by hand, but to let \ Mathematica take over. We can think of the Cartesian product as a type of \ multiplication, where ", StyleBox["List[a,b,...]", "Input"], " corresponds to ", StyleBox["Plus[a,b,...]", "Input"], ". But for additive terms there is a function that handles \"multiplying \ out\" there terms: ", StyleBox["Distribute", "Input"], ". \n\nA look at the help browser shows that ", StyleBox["Distribute", "Input"], " works on arbitrary expressions, not just sums. " }], "Text"], Cell[BoxData[ \(Distribute[{{1, 2, 3}, {a, b}}, List]\)], "Input"], Cell["We can wrap this up into a one-liner:", "Text"], Cell[BoxData[ \(cartprod[LL___List] := Distribute[{LL}, List]; \)], "Input"], Cell[BoxData[ \(cartprod[{1, 2, 3}, {a, b}]\)], "Input"], Cell[BoxData[ \(cartprod[{1, 2, 3}, {a, b}, {A, B}]\)], "Input"], Cell["Actually, there still is a glitch:", "Text"], Cell[BoxData[ \(cartprod[{1, 2, 3}, {}, {A, B}]\)], "Input"], Cell["But, we can easily fix the special case:", "Text"], Cell[BoxData[{ \(Clear[cartprod]\), "\n", \(cartprod[___, {}, ___] = {}; \), "\n", \(cartprod[LL___List] := Distribute[{LL}, List]; \)}], "Input"], Cell[BoxData[ \(cartprod[{1, 2, 3}, {}, {A, B}]\)], "Input"], Cell["This implementation is quite fast:", "Text"], Cell[BoxData[{ \(Timing[L = cartprod[Range[100], Range[100]]; ]\), "\n", \(Length[L]\)}], "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["The Cantor Set", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:99"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", Evaluatable->False, CellTags->"c:100"], Cell["\<\ It is easy to see that countable unions of countable sets are \ countable. Here is a much more complicated situation: a set of reals that is \ the countable intersection of uncountable sets, that contains no intervals, \ but is still uncountable. This set was discovered by G. Cantor around 1890, \ and is an example of what he calls a monster set. The Cantor set and \ similar monsters have become very important recently with the discovery of \ fractal geometry. As it turns out, Cantor's monsters are important for \ example in chemistry to describe the behavior of catalytic sponges. \ \>", \ "Text", Evaluatable->False], Cell[TextData[{ "We begin by defining a countable family of sets of real numbers, each of \ which is a (finite) collection of intervals on the real line. \n\n\[Bullet] \ The first set is the half-open interval ", Cell[BoxData[ \(TraditionalForm\`C\_\(\(\ \)\(0\)\) = \ \(\(\([\)\(0, 1\)\)\()\)\)\ \[SubsetEqual] \ \[DoubleStruckCapitalR]\)]], ". \n\n\[Bullet] ", Cell[BoxData[ \(TraditionalForm\`C\_\(\(\(\ \)\(n + 1\)\)\(\ \)\)\)]], " is constructed by removing the middle third of all intervals in ", Cell[BoxData[ \(TraditionalForm\`C\_\(\(\ \)\(n\)\)\)]], ". \n\n\[Bullet] The Cantor set ", Cell[BoxData[ \(TraditionalForm\`C\)]], " is the intersection of all the ", Cell[BoxData[ \(TraditionalForm\`C\_\(\(\ \)\(n\)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`n\ \[GreaterEqual] \ 0\)]], ". \n\nLess informally, for any half-open interval ", Cell[BoxData[ \(TraditionalForm\`I\ = \ \(\(\([\)\(a, b\)\)\()\)\)\)]], " let ", Cell[BoxData[ \(TraditionalForm\`d\ = \ \(\(\(b\ - a\)\(\ \)\)\(>\)\(\ \)\(0\)\(\ \)\)\)]], " and define \n\n\t", Cell[BoxData[ \(TraditionalForm\`\(\(\(\(f\_0\)(I)\)\(\ \)\)\(=\)\(\ \)\(\(\([\)\(a, a + d/3\)\)\()\)\)\(\ \)\)\)]], " \n\t", Cell[BoxData[ \(TraditionalForm\`\(\(\(\(f\_1\)( I)\)\(\ \)\)\(=\)\(\ \)\(\(\([\)\(a + d/3, a + 2 d/3\)\)\()\)\)\(\ \)\)\)]], " \n\t", Cell[BoxData[ \(TraditionalForm\`\(\(\(\(f\_2\)( I)\)\(\ \)\)\(=\)\(\ \)\(\(\([\)\(a + 2 d/3, b\)\)\()\)\)\(\ \)\)\)]], " \n\t\nThen ", Cell[BoxData[ \(TraditionalForm\`C\_\(\(\ \)\(n + 1\)\)\)]], " is the result of applying ", Cell[BoxData[ \(TraditionalForm\`f\_0\)]], " and ", Cell[BoxData[ \(TraditionalForm\`f\_2\)]], " (but not ", Cell[BoxData[ \(TraditionalForm\`f\_1\)]], ") to all the intervals in ", Cell[BoxData[ \(TraditionalForm\`C\_n\)]], ", and \n", Cell[BoxData[ \(TraditionalForm\`C\ = \ \(\[Intersection]\ C\_n\)\)]], ". \n\nHere is a picture for the first few levels of the construction. " }], "Text", Evaluatable->False], Cell[BoxData[{ \(next[{a_, b_}] := With[{d = b - a}, {{a, a + d\/3}, {a + \(2\ d\)\/3, b}}]\), "\n", \(nextL[L_List] := Flatten[next /@ L, 1]\), "\n", \(\(strip[n_] := Apply[Rectangle, N[Thread /@ Pairs[Table[{n, n + 1}, {2\^n}], Nest[nextL, {{0, 1}}, n]]], {1}];\)\), "\n", \(\(Show[ Graphics[{Blue, Flatten[strip /@ Range[0, 5]]}], \[IndentingNewLine]\t AspectRatio \[Rule] 1, \ Background \[Rule] Yellow];\)\)}], "Input"], Cell[CellGroupData[{ Cell["Nest[ nextL, {{0,1}}, 2 ]", "Input"], Cell[BoxData[ \({{0, 1\/9}, {2\/9, 1\/3}, {2\/3, 7\/9}, {8\/9, 1}}\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:101"], Cell[TextData[{ "(a) Show that the total length of ", Cell[BoxData[ \(TraditionalForm\`C\_\(\(\ \)\(n\)\)\)]], " (the sum of the lengths of all intervals) tends to 0 as ", Cell[BoxData[ \(TraditionalForm\`n \[Rule] \ \[Infinity]\)]], ". \n\n(b) Think of the set of all words (finite sequences) over ", Cell[BoxData[ \(TraditionalForm\`{0, 1, 2}\)]], " as an infinite ternary tree: \nThe root is represented by the empty \ sequence ", Cell[BoxData[ \(TraditionalForm\`\[CurlyEpsilon]\)]], " and each node ", Cell[BoxData[ \(TraditionalForm\`u\)]], " has three children ", Cell[BoxData[ \(TraditionalForm\`u\ 0\)]], ", ", Cell[BoxData[ \(TraditionalForm\`u\ 1\)]], ", ", Cell[BoxData[ \(TraditionalForm\`u\ 2\)]], ". \nThus, the children of the root are 0, 1, 2, and their children are \ 00, 01, 02; 10, 11, 12; 10, 11, 12, respectively. \n\nAssociate an interval \ ", Cell[BoxData[ \(TraditionalForm\`I(u)\ \[SubsetEqual] \ \[DoubleStruckCapitalR]\)]], " with each node in the tree as follows:\n\n\t", Cell[BoxData[ \(TraditionalForm\`I(\[CurlyEpsilon])\ = \ \(\(\([\)\(0, 1\)\)\()\)\)\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`I(u\ i)\ = \ \(f\_\(\(\ \)\(i\)\)\)(\ I(u)\ )\)]], "\n\nSo, for example, ", Cell[BoxData[ \(TraditionalForm\`I(0)\ = \ \(\(\([\)\(0, 1/3\)\)\()\)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`I(2)\ = \ \(\(\([\)\(2/3, 1\)\)\()\)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`I(00)\ = \ \(\(\([\)\(0, 1/9\)\)\()\)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`I(02)\ = \ \(\(\([\)\(2/9, 1/3\)\)\()\)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`I(11)\ = \ \(\(\([\)\(4/9, 5/9\)\)\()\)\)\)]], ", and so on. \n\nIf you feel uncertain about trees, read chapter 6.2 in \ your book.\n\nAt long last, here is the problem: \n\tGive a definition of the \ sets ", Cell[BoxData[ \(TraditionalForm\`C\_\(\(\ \)\(n\)\)\)]], " in terms of the ", Cell[BoxData[ \(TraditionalForm\`I(u)\)]], ". \n\n(c) Conclude that a real number ", Cell[BoxData[ \(TraditionalForm\`x\)]], ", ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ x\ < \ 1\)]], ", lies in ", Cell[BoxData[ \(TraditionalForm\`C\)]], " iff the ternary (base 3) expansion of ", Cell[BoxData[ \(TraditionalForm\`x\)]], " does not contain the digit 1. E.g., all numbers with expansion ", Cell[BoxData[ \(TraditionalForm\`x\ = \ 0.1 \[Ellipsis]\)]], " fail to be in ", Cell[BoxData[ \(TraditionalForm\`C\_1\)]], ". All numbers with expansion ", Cell[BoxData[ \(TraditionalForm\`x\ = \ 0.01 \[Ellipsis]\)]], " or ", Cell[BoxData[ \(TraditionalForm\`x\ = \ 0.21 \[Ellipsis] \(\(\ \)\(\ \)\)\)]], "fail to be in ", Cell[BoxData[ \(TraditionalForm\`C\_2\)]], ", and so on. \n\nAssume that ternary expansions do not have infinitely \ many trailing 2's.\n\n(d) Conclude from (c), and results from class, that ", Cell[BoxData[ \(TraditionalForm\`C\)]], " is uncountable. " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:102"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:103"], Cell[TextData[{ "An easy induction shows that there are ", Cell[BoxData[ \(TraditionalForm\`2\^\(\(\(\ \)\(n\)\)\(\ \)\)\)]], " intervals in ", Cell[BoxData[ \(TraditionalForm\`C\_\(\(\ \)\(n\)\)\)]], ", and the length of each is ", Cell[BoxData[ \(TraditionalForm\`3\^\(\(\ \)\(-n\)\)\)]], ". \nHence the total length is ", Cell[BoxData[ \(TraditionalForm\`\((2/3)\)\^\(\(\ \)\(n\)\) \[Rule] \ 0\)]], " as ", Cell[BoxData[ \(TraditionalForm\`n\ \[Rule] \ \[Infinity]\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:104"], Cell[TextData[{ "An easy induction shows that for ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(u\)\(|\)\)\ = \ n\)]], " \n\n\t", Cell[BoxData[ \(TraditionalForm\`\(\(\(I(u)\)\(\ \)\)\(=\)\(\ \)\({\ x\ \[Element] \ \(\(\([\)\(0, 1\)\)\()\)\)\ | \ \ \ 0. u\ \ \[LessEqual] \ x\ < \ 0. u\ + \ 3\^\(-n\)}\)\(\ \)\)\)]], "\n\nHere the numbers ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(0. u\)\)\)]], " are considered to be in ternary notation. \n\nHence, the sets ", Cell[BoxData[ \(TraditionalForm\`C\_n\)]], " are the union of all the intervals ", Cell[BoxData[ \(TraditionalForm\`I(u)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`u\)]], " has length ", Cell[BoxData[ \(TraditionalForm\`n\)]], " and does not contain the digit 1. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:105"], Cell[TextData[{ "A number ", Cell[BoxData[ \(TraditionalForm\`x = \ 0. \(x\_1\) \(x\_2\) \(x\_3\) \[Ellipsis] \(\(\ \)\(\ \)\)\)]], "(in ternary) lies in ", Cell[BoxData[ \(TraditionalForm\`C\)]], " iff the truncation to ", Cell[BoxData[ \(TraditionalForm\`n\)]], " digits ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(0. \(x\_1\) \(x\_2\) \(x\_3\) \[Ellipsis]\ \ x\_\(n \(\(\ \)\(\ \)\)\)\)\)\)]], " lies in ", Cell[BoxData[ \(TraditionalForm\`C\_n\)]], " for all ", Cell[BoxData[ \(TraditionalForm\`n\ \[GreaterEqual] \ 1\)]], ". But by part (b) this means that none of the ternary digits can be 1. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part d", "Subsubsection", CellTags->"c:106"], Cell[TextData[{ "We know that the power set of \[DoubleStruckCapitalN] is uncountable. \ Equivalently, the set of all infinite sequences of over ", Cell[BoxData[ \(TraditionalForm\`{0, 1}\)]], " is uncountable. But then the set of all infinite sequences of over ", Cell[BoxData[ \(TraditionalForm\`{0, 2}\)]], " is also uncountable. The latter correspond to infinite words whose \ finite prefices are not eliminated at any level. Hence, each infinite word ", Cell[BoxData[ \(TraditionalForm\`U\)]], " corresponds to a point in the Cantor set:\n\n\t\t", Cell[BoxData[ \(TraditionalForm\`\(\(\(g( U)\)\(\ \)\)\(=\)\(\ \)\(\[Intersection]\ {\ I(u)\ | \ \ u\ \ finite\ prefix\ of\ U\ }\)\(\ \)\)\)]], "\n\t\t\nand ", Cell[BoxData[ \(TraditionalForm\`g\ : \ {0, 2}\^\(\(\(\ \)\(\[Omega]\)\)\(\ \)\)\ \[LongRightArrow]\ C\)]], " is a bijection.\n\nNote that it is not completely clear that the \ intersection consists of ecactly one point. However, one can see that the \ number with infinite ternary expansion ", Cell[BoxData[ \(TraditionalForm\`x\ = \ 0. U\)]], " lies in the intersection, and no other point can be in there. \n\ Alternatively, one could use topology to conclude that the intersection is \ not empty. " }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Bypassing Schr\[ODoubleDot]der-Bernstein", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:107"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", Evaluatable->False, CellTags->"c:108"], Cell["\<\ The Schr\[ODoubleDot]der-Bernstein theorem is a powerful tool to \ show that certain sets have the same cardinality. However, often one can construct a bijection directly, albeit with more \ effort. \ \>", "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:109"], Cell[TextData[{ "Show that all the following subsets of the reals have the same cardinality \ as \[DoubleStruckCapitalR], by directly constructing bijections without \ appeal to the Schr\[ODoubleDot]der-Bernstein theorem. Do them in this order, \ they are increasingly more difficult. \n\n(a) ", Cell[BoxData[ FormBox[ FormBox[\(\[DoubleStruckCapitalR]\^+\), "TraditionalForm"], TraditionalForm]]], "\n(b) ", Cell[BoxData[ \(TraditionalForm\`\((0, 1)\)\)]], "\n(c) ", Cell[BoxData[ \(TraditionalForm\`\(\([0, 1\)\()\)\)\)]], "\n(d) ", Cell[BoxData[ FormBox[Cell["[0,1]"], TraditionalForm]]], "\n\nNeedless to say, you have to specify your alleged bijections \ carefully, and make sure they really are bijections. " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:110"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:111"], Cell[TextData[{ "That's easy: ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ e\^\(\(\ \)\(x\)\)\)]], " does the job." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:112"], Cell[TextData[{ "This one is also easy: ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ tan(\ \[Pi]\ x\ - \ \[Pi]/2)\)]], " does it." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:113"], Cell[TextData[{ "This is a bit harder. We split the interval into infinitely many \ half-open parts, and map each part separately to a half-open interval in the \ reals. The necessary maps can easily be obtained from a hyperbola ", Cell[BoxData[ \(TraditionalForm\`1\/x\)]], " and linear functions ", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\ x\ + \ \[Beta]\)]], ". \n\nChoose a sequence ", Cell[BoxData[ \(TraditionalForm\`0\ = \ a\_0\ < \ a\_1 < \ a\_2\ < \ \[Ellipsis]\)]], " where ", Cell[BoxData[ \(TraditionalForm\`a\_n\ \[Rule] \ 1\)]], " as ", Cell[BoxData[ \(TraditionalForm\`n \[Rule] \ \[Infinity]\)]], ", and \n a sequence ", Cell[BoxData[ \(TraditionalForm\`\(-\[Infinity]\)\ = \ b\_0\ < \ b\_1 < \ b\_2\ < \ \[Ellipsis]\)]], " where ", Cell[BoxData[ \(TraditionalForm\`b\_n\ \[Rule] \ \(+\[Infinity]\)\)]], " as ", Cell[BoxData[ \(TraditionalForm\`n \[Rule] \ \[Infinity]\)]], ".\n \n Fix a bijection ", Cell[BoxData[ \(TraditionalForm\`\(\(\(\(f\_\(n : \ \(\(\([\)\(a\_n, \ a\_\(n + 1\)\)\)\()\)\)\)\)\(\ \)\)\(\[Rule]\)\)\(\ \)\)\)]], Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox[ FormBox[\((b\_n, b\), "TraditionalForm"], \(n + 1\)], "]"}], TraditionalForm]]], " for all ", Cell[BoxData[ \(TraditionalForm\`n \[GreaterEqual] \ \ 0\)]], " and set ", Cell[BoxData[ \(TraditionalForm\`f = \(\[Union]\ f\_n\)\)]], ". \n \n It is not hard to check that the domain of ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is ", Cell[BoxData[ \(TraditionalForm\`\(\(\([\)\(0, 1\)\)\()\)\)\)]], ", and the range is all of \[DoubleStruckCapitalR].\n Moreover, ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is a bijection. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part d", "Subsubsection", CellTags->"c:114"], Cell[TextData[{ "Exploit parts (a) and (c), and the trivial fact that ", Cell[BoxData[ \(TraditionalForm\`\(\[DoubleStruckCapitalR]\^+\)\)]], " has the same cardinality as ", Cell[BoxData[ \(TraditionalForm\`\(\[DoubleStruckCapitalR]\^-\)\)]], ". \nSplit the interval into ", Cell[BoxData[ \(TraditionalForm\`\(\(\([\)\(0, 1/2\)\)\()\)\)\ , \ 1\/2, \ \(\((1/2, \ 1\)\(]\)\)\)]], ". \nMap ", Cell[BoxData[ \(TraditionalForm\`1\/2\)]], " to 0, ", Cell[BoxData[ \(TraditionalForm\`\(\(\([\)\(0, 1/2\)\)\()\)\)\)]], " to ", Cell[BoxData[ \(TraditionalForm\`\(\[DoubleStruckCapitalR]\^-\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(\((1/2, 1\)\(]\)\)\)]], " to ", Cell[BoxData[ \(TraditionalForm\`\(\[DoubleStruckCapitalR]\^+\)\)]], " ." }], "Text"] }, Closed]] }, Closed]] }, Closed]] }, Open ]] }, FrontEndVersion->"5.0 for X", ScreenRectangle->{{0, 1280}, {0, 1024}}, WindowSize->{862, 887}, WindowMargins->{{Automatic, 59}, {0, Automatic}}, PrintingStartingPageNumber->219, StyleDefinitions -> "Default.nb" ] (******************************************************************* Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. *******************************************************************) (*CellTagsOutline CellTagsIndex->{ "c:1"->{ Cell[1828, 55, 40, 1, 98, "Title", CellTags->"c:1"]}, "c:2"->{ Cell[1893, 60, 99, 3, 74, "Section", Evaluatable->False, CellTags->"c:2"]}, "c:3"->{ Cell[2017, 67, 64, 2, 27, "Subsubsection", CellTags->"c:3"]}, "c:4"->{ Cell[2710, 93, 68, 2, 27, "Subsubsection", CellTags->"c:4"]}, "c:5"->{ Cell[3303, 125, 65, 2, 37, "Subsection", CellTags->"c:5"]}, "cartesian product"->{ Cell[4283, 163, 136, 3, 44, "Section", Evaluatable->False, CellTags->{"cartesian product", "c:6"}]}, "c:6"->{ Cell[4283, 163, 136, 3, 44, "Section", Evaluatable->False, CellTags->{"cartesian product", "c:6"}]}, "c:7"->{ Cell[4444, 170, 70, 2, 27, "Subsubsection", CellTags->"c:7"]}, "c:8"->{ Cell[4973, 186, 64, 2, 27, "Subsubsection", CellTags->"c:8"]}, "c:9"->{ Cell[5360, 201, 68, 2, 27, "Subsubsection", CellTags->"c:9"]}, "c:10"->{ Cell[5719, 220, 66, 2, 37, "Subsection", CellTags->"c:10"]}, "c:11"->{ Cell[7870, 296, 100, 3, 44, "Section", Evaluatable->False, CellTags->"c:11"]}, "c:12"->{ Cell[7995, 303, 77, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:12"]}, "c:13"->{ Cell[8905, 333, 71, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:13"]}, "c:14"->{ Cell[9597, 358, 72, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:14"]}, "c:15"->{ Cell[9672, 362, 51, 1, 70, "Subsubsection", CellTags->"c:15"]}, "c:16"->{ Cell[9726, 365, 51, 1, 70, "Subsubsection", CellTags->"c:16"]}, "c:17"->{ Cell[9780, 368, 51, 1, 70, "Subsubsection", CellTags->"c:17"]}, "c:18"->{ Cell[9880, 375, 101, 3, 44, "Section", Evaluatable->False, CellTags->"c:18"]}, "c:19"->{ Cell[10006, 382, 49, 1, 70, "Subsubsection", CellTags->"c:19"]}, "c:20"->{ Cell[11480, 425, 72, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:20"]}, "c:21"->{ Cell[11577, 431, 51, 1, 70, "Subsubsection", CellTags->"c:21"]}, "c:22"->{ Cell[11790, 443, 51, 1, 70, "Subsubsection", CellTags->"c:22"]}, "c:23"->{ Cell[12203, 462, 51, 1, 70, "Subsubsection", CellTags->"c:23"]}, "c:24"->{ Cell[12682, 484, 51, 1, 70, "Subsubsection", CellTags->"c:24"]}, "c:25"->{ Cell[13090, 503, 51, 1, 70, "Subsubsection", CellTags->"c:25"]}, "c:26"->{ Cell[13505, 522, 51, 1, 70, "Subsubsection", CellTags->"c:26"]}, "c:27"->{ Cell[13903, 541, 51, 1, 70, "Subsubsection", CellTags->"c:27"]}, "c:28"->{ Cell[14342, 562, 107, 3, 44, "Section", Evaluatable->False, CellTags->"c:28"]}, "c:29"->{ Cell[14474, 569, 71, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:29"]}, "c:30"->{ Cell[15526, 603, 72, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:30"]}, "c:31"->{ Cell[15623, 609, 51, 1, 70, "Subsubsection", CellTags->"c:31"]}, "c:32"->{ Cell[15954, 623, 51, 1, 70, "Subsubsection", CellTags->"c:32"]}, "c:33"->{ Cell[17292, 662, 51, 1, 70, "Subsubsection", CellTags->"c:33"]}, "c:34"->{ Cell[17795, 686, 104, 3, 44, "Section", Evaluatable->False, CellTags->"c:34"]}, "c:35"->{ Cell[17924, 693, 71, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:35"]}, "c:36"->{ Cell[18371, 713, 72, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:36"]}, "c:37"->{ Cell[21125, 796, 103, 3, 44, "Section", Evaluatable->False, CellTags->"c:37"]}, "c:38"->{ Cell[21253, 803, 77, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:38"]}, "c:39"->{ Cell[21636, 818, 71, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:39"]}, "c:40"->{ Cell[22066, 839, 73, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:40"]}, "c:41"->{ Cell[22800, 867, 72, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:41"]}, "c:42"->{ Cell[22909, 874, 111, 3, 44, "Section", Evaluatable->False, CellTags->"c:42"]}, "c:43"->{ Cell[23045, 881, 77, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:43"]}, "c:44"->{ Cell[24217, 921, 71, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:44"]}, "c:45"->{ Cell[26219, 988, 53, 1, 70, "Subsubsection", CellTags->"c:45"]}, "c:46"->{ Cell[27027, 1025, 72, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:46"]}, "c:47"->{ Cell[27559, 1055, 101, 3, 44, "Section", Evaluatable->False, CellTags->"c:47"]}, "c:48"->{ Cell[27685, 1062, 77, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:48"]}, "c:49"->{ Cell[28618, 1091, 71, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:49"]}, "c:50"->{ Cell[29538, 1123, 72, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:50"]}, "c:51"->{ Cell[29635, 1129, 76, 2, 70, "Subsubsection", CellTags->"c:51"]}, "c:52"->{ Cell[30459, 1161, 76, 2, 70, "Subsubsection", CellTags->"c:52"]}, "c:53"->{ Cell[30885, 1179, 76, 2, 70, "Subsubsection", CellTags->"c:53"]}, "c:54"->{ Cell[32126, 1227, 51, 1, 70, "Subsubsection", CellTags->"c:54"]}, "c:55"->{ Cell[33485, 1278, 107, 3, 44, "Section", Evaluatable->False, CellTags->"c:55"]}, "c:56"->{ Cell[33617, 1285, 49, 1, 70, "Subsubsection", CellTags->"c:56"]}, "c:57"->{ Cell[34050, 1300, 50, 1, 70, "Subsection", CellTags->"c:57"]}, "c:58"->{ Cell[34125, 1305, 51, 1, 70, "Subsubsection", CellTags->"c:58"]}, "c:59"->{ Cell[35054, 1335, 51, 1, 70, "Subsubsection", CellTags->"c:59"]}, "c:60"->{ Cell[36138, 1376, 115, 3, 44, "Section", Evaluatable->False, CellTags->"c:60"]}, "c:61"->{ Cell[36278, 1383, 49, 1, 70, "Subsubsection", CellTags->"c:61"]}, "c:62"->{ Cell[37414, 1413, 52, 1, 70, "Subsubsection", CellTags->"c:62"]}, "c:63"->{ Cell[38142, 1433, 137, 5, 70, "Subsection", Evaluatable->False, CellTags->"c:63"]}, "c:64"->{ Cell[39410, 1468, 119, 3, 44, "Section", Evaluatable->False, CellTags->"c:64"]}, "c:65"->{ Cell[39554, 1475, 74, 2, 70, "Subsubsection", CellTags->"c:65"]}, "c:66"->{ Cell[40478, 1510, 74, 2, 70, "Subsubsection", CellTags->"c:66"]}, "c:67"->{ Cell[40793, 1524, 75, 2, 70, "Subsection", CellTags->"c:67"]}, "c:68"->{ Cell[41157, 1538, 76, 2, 70, "Subsubsection", CellTags->"c:68"]}, "c:69"->{ Cell[41851, 1563, 76, 2, 70, "Subsubsection", CellTags->"c:69"]}, "c:70"->{ Cell[42832, 1593, 76, 2, 70, "Subsubsection", CellTags->"c:70"]}, "c:71"->{ Cell[44050, 1638, 76, 2, 70, "Subsubsection", CellTags->"c:71"]}, "c:72"->{ Cell[45274, 1682, 76, 2, 70, "Subsubsection", CellTags->"c:72"]}, "c:73"->{ Cell[46859, 1734, 109, 3, 44, "Section", Evaluatable->False, CellTags->"c:73"]}, "c:74"->{ Cell[46993, 1741, 74, 2, 70, "Subsubsection", CellTags->"c:74"]}, "c:75"->{ Cell[47327, 1756, 75, 2, 70, "Subsection", CellTags->"c:75"]}, "c:76"->{ Cell[48139, 1779, 104, 3, 44, "Section", Evaluatable->False, CellTags->"c:76"]}, "c:77"->{ Cell[48268, 1786, 74, 2, 70, "Subsubsection", CellTags->"c:77"]}, "c:78"->{ Cell[49251, 1818, 77, 2, 70, "Subsubsection", CellTags->"c:78"]}, "c:79"->{ Cell[49521, 1831, 75, 2, 70, "Subsection", CellTags->"c:79"]}, "c:80"->{ Cell[49621, 1837, 51, 1, 70, "Subsubsection", CellTags->"c:80"]}, "c:81"->{ Cell[50147, 1856, 51, 1, 70, "Subsubsection", CellTags->"c:81"]}, "c:82"->{ Cell[50841, 1881, 51, 1, 70, "Subsubsection", CellTags->"c:82"]}, "c:83"->{ Cell[51573, 1906, 105, 3, 44, "Section", Evaluatable->False, CellTags->"c:83"]}, "c:84"->{ Cell[51703, 1913, 49, 1, 28, "Subsubsection", CellTags->"c:84"]}, "c:85"->{ Cell[52877, 1950, 137, 5, 41, "Subsection", Evaluatable->False, CellTags->"c:85"]}, "c:86"->{ Cell[53039, 1959, 51, 1, 28, "Subsubsection", CellTags->"c:86"]}, "c:87"->{ Cell[53362, 1975, 51, 1, 28, "Subsubsection", CellTags->"c:87"]}, "c:88"->{ Cell[54878, 2041, 114, 3, 44, "Section", Evaluatable->False, CellTags->"c:88"]}, "c:89"->{ Cell[55017, 2048, 55, 1, 28, "Subsubsection", CellTags->"c:89"]}, "c:90"->{ Cell[55775, 2073, 49, 1, 28, "Subsubsection", CellTags->"c:90"]}, "c:91"->{ Cell[56777, 2113, 153, 6, 41, "Subsection", Evaluatable->False, CellTags->"c:91"]}, "c:92"->{ Cell[56955, 2123, 68, 2, 27, "Subsubsection", CellTags->"c:92"]}, "c:93"->{ Cell[57168, 2134, 68, 2, 27, "Subsubsection", CellTags->"c:93"]}, "c:94"->{ Cell[57630, 2155, 68, 2, 27, "Subsubsection", CellTags->"c:94"]}, "c:95"->{ Cell[58297, 2185, 105, 3, 44, "Section", Evaluatable->False, CellTags->"c:95"]}, "c:96"->{ Cell[58427, 2192, 55, 1, 28, "Subsubsection", CellTags->"c:96"]}, "c:97"->{ Cell[59185, 2217, 49, 1, 28, "Subsubsection", CellTags->"c:97"]}, "c:98"->{ Cell[60272, 2259, 153, 6, 41, "Subsection", Evaluatable->False, CellTags->"c:98"]}, "c:99"->{ Cell[63208, 2364, 101, 3, 44, "Section", Evaluatable->False, CellTags->"c:99"]}, "c:100"->{ Cell[63334, 2371, 78, 2, 28, "Subsubsection", Evaluatable->False, CellTags->"c:100"]}, "c:101"->{ Cell[67005, 2477, 72, 2, 28, "Subsubsection", Evaluatable->False, CellTags->"c:101"]}, "c:102"->{ Cell[70318, 2580, 73, 2, 39, "Subsection", Evaluatable->False, CellTags->"c:102"]}, "c:103"->{ Cell[70416, 2586, 52, 1, 28, "Subsubsection", CellTags->"c:103"]}, "c:104"->{ Cell[71054, 2611, 52, 1, 28, "Subsubsection", CellTags->"c:104"]}, "c:105"->{ Cell[72019, 2645, 52, 1, 28, "Subsubsection", CellTags->"c:105"]}, "c:106"->{ Cell[72805, 2675, 52, 1, 28, "Subsubsection", CellTags->"c:106"]}, "c:107"->{ Cell[74246, 2714, 128, 3, 44, "Section", Evaluatable->False, CellTags->"c:107"]}, "c:108"->{ Cell[74399, 2721, 78, 2, 28, "Subsubsection", Evaluatable->False, CellTags->"c:108"]}, "c:109"->{ Cell[74763, 2736, 72, 2, 28, "Subsubsection", Evaluatable->False, CellTags->"c:109"]}, "c:110"->{ Cell[75688, 2766, 73, 2, 39, "Subsection", Evaluatable->False, CellTags->"c:110"]}, "c:111"->{ Cell[75786, 2772, 52, 1, 28, "Subsubsection", CellTags->"c:111"]}, "c:112"->{ Cell[76022, 2785, 52, 1, 28, "Subsubsection", CellTags->"c:112"]}, "c:113"->{ Cell[76274, 2798, 52, 1, 28, "Subsubsection", CellTags->"c:113"]}, "c:114"->{ Cell[78260, 2861, 52, 1, 28, "Subsubsection", CellTags->"c:114"]} } *) (*CellTagsIndex CellTagsIndex->{ {"c:1", 79859, 2914}, {"c:2", 79934, 2917}, {"c:3", 80037, 2921}, {"c:4", 80120, 2924}, {"c:5", 80203, 2927}, {"cartesian product", 80298, 2930}, {"c:6", 80426, 2934}, {"c:7", 80554, 2938}, {"c:8", 80638, 2941}, {"c:9", 80722, 2944}, {"c:10", 80807, 2947}, {"c:11", 80890, 2950}, {"c:12", 80997, 2954}, {"c:13", 81109, 2958}, {"c:14", 81221, 2962}, {"c:15", 81330, 2966}, {"c:16", 81416, 2969}, {"c:17", 81502, 2972}, {"c:18", 81588, 2975}, {"c:19", 81695, 2979}, {"c:20", 81782, 2982}, {"c:21", 81892, 2986}, {"c:22", 81979, 2989}, {"c:23", 82066, 2992}, {"c:24", 82153, 2995}, {"c:25", 82240, 2998}, {"c:26", 82327, 3001}, {"c:27", 82414, 3004}, {"c:28", 82501, 3007}, {"c:29", 82609, 3011}, {"c:30", 82722, 3015}, {"c:31", 82832, 3019}, {"c:32", 82919, 3022}, {"c:33", 83006, 3025}, {"c:34", 83093, 3028}, {"c:35", 83201, 3032}, {"c:36", 83314, 3036}, {"c:37", 83424, 3040}, {"c:38", 83532, 3044}, {"c:39", 83645, 3048}, {"c:40", 83758, 3052}, {"c:41", 83871, 3056}, {"c:42", 83981, 3060}, {"c:43", 84089, 3064}, {"c:44", 84202, 3068}, {"c:45", 84315, 3072}, {"c:46", 84402, 3075}, {"c:47", 84513, 3079}, {"c:48", 84622, 3083}, {"c:49", 84736, 3087}, {"c:50", 84850, 3091}, {"c:51", 84961, 3095}, {"c:52", 85049, 3098}, {"c:53", 85137, 3101}, {"c:54", 85225, 3104}, {"c:55", 85313, 3107}, {"c:56", 85422, 3111}, {"c:57", 85510, 3114}, {"c:58", 85595, 3117}, {"c:59", 85683, 3120}, {"c:60", 85771, 3123}, {"c:61", 85880, 3127}, {"c:62", 85968, 3130}, {"c:63", 86056, 3133}, {"c:64", 86168, 3137}, {"c:65", 86277, 3141}, {"c:66", 86365, 3144}, {"c:67", 86453, 3147}, {"c:68", 86538, 3150}, {"c:69", 86626, 3153}, {"c:70", 86714, 3156}, {"c:71", 86802, 3159}, {"c:72", 86890, 3162}, {"c:73", 86978, 3165}, {"c:74", 87087, 3169}, {"c:75", 87175, 3172}, {"c:76", 87260, 3175}, {"c:77", 87369, 3179}, {"c:78", 87457, 3182}, {"c:79", 87545, 3185}, {"c:80", 87630, 3188}, {"c:81", 87718, 3191}, {"c:82", 87806, 3194}, {"c:83", 87894, 3197}, {"c:84", 88003, 3201}, {"c:85", 88091, 3204}, {"c:86", 88203, 3208}, {"c:87", 88291, 3211}, {"c:88", 88379, 3214}, {"c:89", 88488, 3218}, {"c:90", 88576, 3221}, {"c:91", 88664, 3224}, {"c:92", 88776, 3228}, {"c:93", 88864, 3231}, {"c:94", 88952, 3234}, {"c:95", 89040, 3237}, {"c:96", 89149, 3241}, {"c:97", 89237, 3244}, {"c:98", 89325, 3247}, {"c:99", 89437, 3251}, {"c:100", 89547, 3255}, {"c:101", 89663, 3259}, {"c:102", 89779, 3263}, {"c:103", 89892, 3267}, {"c:104", 89982, 3270}, {"c:105", 90072, 3273}, {"c:106", 90162, 3276}, {"c:107", 90252, 3279}, {"c:108", 90363, 3283}, {"c:109", 90479, 3287}, {"c:110", 90595, 3291}, {"c:111", 90708, 3295}, {"c:112", 90798, 3298}, {"c:113", 90888, 3301}, {"c:114", 90978, 3304} } *) (*NotebookFileOutline Notebook[{ Cell[1754, 51, 49, 0, 27, "SmallText"], Cell[CellGroupData[{ Cell[1828, 55, 40, 1, 98, "Title", CellTags->"c:1"], Cell[CellGroupData[{ Cell[1893, 60, 99, 3, 74, "Section", Evaluatable->False, CellTags->"c:2"], Cell[CellGroupData[{ Cell[2017, 67, 64, 2, 27, "Subsubsection", CellTags->"c:3"], Cell[2084, 71, 589, 17, 68, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[2710, 93, 68, 2, 27, "Subsubsection", CellTags->"c:4"], Cell[2781, 97, 485, 23, 32, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[3303, 125, 65, 2, 37, "Subsection", CellTags->"c:5"], Cell[3371, 129, 239, 5, 50, "Text"], Cell[3613, 136, 132, 3, 32, "Text"], Cell[3748, 141, 102, 2, 27, "Input"], Cell[3853, 145, 45, 1, 27, "Input"], Cell[3901, 148, 121, 3, 32, "Text"], Cell[4025, 153, 209, 4, 59, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[4283, 163, 136, 3, 44, "Section", Evaluatable->False, CellTags->{"cartesian product", "c:6"}], Cell[CellGroupData[{ Cell[4444, 170, 70, 2, 27, "Subsubsection", CellTags->"c:7"], Cell[4517, 174, 419, 7, 121, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[4973, 186, 64, 2, 27, "Subsubsection", CellTags->"c:8"], Cell[5040, 190, 283, 6, 50, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[5360, 201, 68, 2, 27, "Subsubsection", CellTags->"c:9"], Cell[5431, 205, 251, 10, 32, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[5719, 220, 66, 2, 37, "Subsection", CellTags->"c:10"], Cell[5788, 224, 141, 3, 32, "Text"], Cell[5932, 229, 162, 3, 43, "Input"], Cell[6097, 234, 62, 1, 27, "Input"], Cell[6162, 237, 73, 0, 32, "Text"], Cell[6238, 239, 173, 4, 27, "Input"], Cell[6414, 245, 250, 5, 50, "Text"], Cell[6667, 252, 60, 1, 27, "Input"], Cell[6730, 255, 145, 3, 32, "Text"], Cell[6878, 260, 121, 2, 43, "Input"], Cell[7002, 264, 62, 1, 27, "Input"], Cell[7067, 267, 129, 3, 32, "Text"], Cell[7199, 272, 59, 1, 27, "Input"], Cell[7261, 275, 289, 5, 68, "Text"], Cell[7553, 282, 116, 2, 43, "Input"], Cell[7672, 286, 39, 0, 32, "Text"], Cell[7714, 288, 107, 2, 43, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[7870, 296, 100, 3, 44, "Section", Evaluatable->False, CellTags->"c:11"], Cell[CellGroupData[{ Cell[7995, 303, 77, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:12"], Cell[8075, 307, 793, 21, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[8905, 333, 71, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:13"], Cell[8979, 337, 581, 16, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[9597, 358, 72, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:14"], Cell[9672, 362, 51, 1, 70, "Subsubsection", CellTags->"c:15"], Cell[9726, 365, 51, 1, 70, "Subsubsection", CellTags->"c:16"], Cell[9780, 368, 51, 1, 70, "Subsubsection", CellTags->"c:17"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[9880, 375, 101, 3, 44, "Section", Evaluatable->False, CellTags->"c:18"], Cell[CellGroupData[{ Cell[10006, 382, 49, 1, 70, "Subsubsection", CellTags->"c:19"], Cell[10058, 385, 1385, 35, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[11480, 425, 72, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:20"], Cell[CellGroupData[{ Cell[11577, 431, 51, 1, 70, "Subsubsection", CellTags->"c:21"], Cell[11631, 434, 122, 4, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[11790, 443, 51, 1, 70, "Subsubsection", CellTags->"c:22"], Cell[11844, 446, 322, 11, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[12203, 462, 51, 1, 70, "Subsubsection", CellTags->"c:23"], Cell[12257, 465, 388, 14, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[12682, 484, 51, 1, 70, "Subsubsection", CellTags->"c:24"], Cell[12736, 487, 317, 11, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[13090, 503, 51, 1, 70, "Subsubsection", CellTags->"c:25"], Cell[13144, 506, 324, 11, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[13505, 522, 51, 1, 70, "Subsubsection", CellTags->"c:26"], Cell[13559, 525, 307, 11, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[13903, 541, 51, 1, 70, "Subsubsection", CellTags->"c:27"], Cell[13957, 544, 324, 11, 70, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[14342, 562, 107, 3, 44, "Section", Evaluatable->False, CellTags->"c:28"], Cell[CellGroupData[{ Cell[14474, 569, 71, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:29"], Cell[14548, 573, 941, 25, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[15526, 603, 72, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:30"], Cell[CellGroupData[{ Cell[15623, 609, 51, 1, 70, "Subsubsection", CellTags->"c:31"], Cell[15677, 612, 240, 6, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[15954, 623, 51, 1, 70, "Subsubsection", CellTags->"c:32"], Cell[16008, 626, 1247, 31, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[17292, 662, 51, 1, 70, "Subsubsection", CellTags->"c:33"], Cell[17346, 665, 388, 14, 70, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[17795, 686, 104, 3, 44, "Section", Evaluatable->False, CellTags->"c:34"], Cell[CellGroupData[{ Cell[17924, 693, 71, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:35"], Cell[17998, 697, 336, 11, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[18371, 713, 72, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:36"], Cell[18446, 717, 618, 20, 70, "Text", Evaluatable->False], Cell[19067, 739, 406, 10, 70, "Text", Evaluatable->False], Cell[19476, 751, 777, 14, 70, "Text"], Cell[20256, 767, 282, 8, 70, "Text", Evaluatable->False], Cell[20541, 777, 535, 13, 70, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[21125, 796, 103, 3, 44, "Section", Evaluatable->False, CellTags->"c:37"], Cell[CellGroupData[{ Cell[21253, 803, 77, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:38"], Cell[21333, 807, 266, 6, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[21636, 818, 71, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:39"], Cell[21710, 822, 319, 12, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[22066, 839, 73, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:40"], Cell[22142, 843, 183, 6, 70, "Text", Evaluatable->False], Cell[22328, 851, 294, 7, 70, "Text", Evaluatable->False], Cell[22625, 860, 66, 0, 70, "Input"], Cell[22694, 862, 45, 0, 70, "Input"], Cell[22742, 864, 43, 0, 70, "Input"] }, Closed]], Cell[22800, 867, 72, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:41"] }, Closed]], Cell[CellGroupData[{ Cell[22909, 874, 111, 3, 44, "Section", Evaluatable->False, CellTags->"c:42"], Cell[CellGroupData[{ Cell[23045, 881, 77, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:43"], Cell[23125, 885, 1055, 31, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[24217, 921, 71, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:44"], Cell[24291, 925, 1454, 42, 70, "Text", Evaluatable->False], Cell[25748, 969, 271, 8, 70, "Text", Evaluatable->False], Cell[26022, 979, 66, 0, 70, "Input"], Cell[26091, 981, 45, 0, 70, "Input"], Cell[26139, 983, 43, 0, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[26219, 988, 53, 1, 70, "Subsubsection", CellTags->"c:45"], Cell[26275, 991, 715, 29, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[27027, 1025, 72, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:46"], Cell[27102, 1029, 66, 0, 70, "Input"], Cell[27171, 1031, 159, 4, 70, "Input"], Cell[27333, 1037, 51, 0, 70, "Input"], Cell[27387, 1039, 45, 0, 70, "Input"], Cell[27435, 1041, 36, 3, 70, "Input"], Cell[27474, 1046, 36, 3, 70, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[27559, 1055, 101, 3, 44, "Section", Evaluatable->False, CellTags->"c:47"], Cell[CellGroupData[{ Cell[27685, 1062, 77, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:48"], Cell[27765, 1066, 816, 20, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[28618, 1091, 71, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:49"], Cell[28692, 1095, 809, 23, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[29538, 1123, 72, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:50"], Cell[CellGroupData[{ Cell[29635, 1129, 76, 2, 70, "Subsubsection", CellTags->"c:51"], Cell[29714, 1133, 708, 23, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[30459, 1161, 76, 2, 70, "Subsubsection", CellTags->"c:52"], Cell[30538, 1165, 310, 9, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[30885, 1179, 76, 2, 70, "Subsubsection", CellTags->"c:53"], Cell[30964, 1183, 1125, 39, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[32126, 1227, 51, 1, 70, "Subsubsection", CellTags->"c:54"], Cell[32180, 1230, 1244, 41, 70, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[33485, 1278, 107, 3, 44, "Section", Evaluatable->False, CellTags->"c:55"], Cell[CellGroupData[{ Cell[33617, 1285, 49, 1, 70, "Subsubsection", CellTags->"c:56"], Cell[33669, 1288, 344, 7, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[34050, 1300, 50, 1, 70, "Subsection", CellTags->"c:57"], Cell[CellGroupData[{ Cell[34125, 1305, 51, 1, 70, "Subsubsection", CellTags->"c:58"], Cell[34179, 1308, 838, 22, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[35054, 1335, 51, 1, 70, "Subsubsection", CellTags->"c:59"], Cell[35108, 1338, 969, 31, 70, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[36138, 1376, 115, 3, 44, "Section", Evaluatable->False, CellTags->"c:60"], Cell[CellGroupData[{ Cell[36278, 1383, 49, 1, 70, "Subsubsection", CellTags->"c:61"], Cell[36330, 1386, 1047, 22, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[37414, 1413, 52, 1, 70, "Subsubsection", CellTags->"c:62"], Cell[37469, 1416, 636, 12, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[38142, 1433, 137, 5, 70, "Subsection", Evaluatable->False, CellTags->"c:63"], Cell[38282, 1440, 634, 11, 70, "Text"], Cell[38919, 1453, 442, 9, 70, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[39410, 1468, 119, 3, 44, "Section", Evaluatable->False, CellTags->"c:64"], Cell[CellGroupData[{ Cell[39554, 1475, 74, 2, 70, "Subsubsection", CellTags->"c:65"], Cell[39631, 1479, 810, 26, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[40478, 1510, 74, 2, 70, "Subsubsection", CellTags->"c:66"], Cell[40555, 1514, 201, 5, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[40793, 1524, 75, 2, 70, "Subsection", CellTags->"c:67"], Cell[40871, 1528, 261, 6, 70, "Text"], Cell[CellGroupData[{ Cell[41157, 1538, 76, 2, 70, "Subsubsection", CellTags->"c:68"], Cell[41236, 1542, 578, 16, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[41851, 1563, 76, 2, 70, "Subsubsection", CellTags->"c:69"], Cell[41930, 1567, 865, 21, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[42832, 1593, 76, 2, 70, "Subsubsection", CellTags->"c:70"], Cell[42911, 1597, 1102, 36, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[44050, 1638, 76, 2, 70, "Subsubsection", CellTags->"c:71"], Cell[44129, 1642, 1108, 35, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[45274, 1682, 76, 2, 70, "Subsubsection", CellTags->"c:72"], Cell[45353, 1686, 1445, 41, 70, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[46859, 1734, 109, 3, 44, "Section", Evaluatable->False, CellTags->"c:73"], Cell[CellGroupData[{ Cell[46993, 1741, 74, 2, 70, "Subsubsection", CellTags->"c:74"], Cell[47070, 1745, 220, 6, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[47327, 1756, 75, 2, 70, "Subsection", CellTags->"c:75"], Cell[47405, 1760, 685, 13, 70, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[48139, 1779, 104, 3, 44, "Section", Evaluatable->False, CellTags->"c:76"], Cell[CellGroupData[{ Cell[48268, 1786, 74, 2, 70, "Subsubsection", CellTags->"c:77"], Cell[48345, 1790, 869, 23, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[49251, 1818, 77, 2, 70, "Subsubsection", CellTags->"c:78"], Cell[49331, 1822, 153, 4, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[49521, 1831, 75, 2, 70, "Subsection", CellTags->"c:79"], Cell[CellGroupData[{ Cell[49621, 1837, 51, 1, 70, "Subsubsection", CellTags->"c:80"], Cell[49675, 1840, 435, 11, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[50147, 1856, 51, 1, 70, "Subsubsection", CellTags->"c:81"], Cell[50201, 1859, 603, 17, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[50841, 1881, 51, 1, 70, "Subsubsection", CellTags->"c:82"], Cell[50895, 1884, 617, 15, 70, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[51573, 1906, 105, 3, 44, "Section", Evaluatable->False, CellTags->"c:83"], Cell[CellGroupData[{ Cell[51703, 1913, 49, 1, 28, "Subsubsection", CellTags->"c:84"], Cell[51755, 1916, 1085, 29, 230, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[52877, 1950, 137, 5, 41, "Subsection", Evaluatable->False, CellTags->"c:85"], Cell[CellGroupData[{ Cell[53039, 1959, 51, 1, 28, "Subsubsection", CellTags->"c:86"], Cell[53093, 1962, 232, 8, 32, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[53362, 1975, 51, 1, 28, "Subsubsection", CellTags->"c:87"], Cell[53416, 1978, 143, 5, 32, "Text"], Cell[53562, 1985, 535, 20, 50, "Text"], Cell[54100, 2007, 575, 20, 68, "Text"], Cell[54678, 2029, 139, 5, 32, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[54878, 2041, 114, 3, 44, "Section", Evaluatable->False, CellTags->"c:88"], Cell[CellGroupData[{ Cell[55017, 2048, 55, 1, 28, "Subsubsection", CellTags->"c:89"], Cell[55075, 2051, 663, 17, 158, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[55775, 2073, 49, 1, 28, "Subsubsection", CellTags->"c:90"], Cell[55827, 2076, 296, 10, 50, "Text", Evaluatable->False], Cell[56126, 2088, 378, 11, 50, "Text", Evaluatable->False], Cell[56507, 2101, 233, 7, 32, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[56777, 2113, 153, 6, 41, "Subsection", Evaluatable->False, CellTags->"c:91"], Cell[CellGroupData[{ Cell[56955, 2123, 68, 2, 27, "Subsubsection", CellTags->"c:92"], Cell[57026, 2127, 105, 2, 27, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[57168, 2134, 68, 2, 27, "Subsubsection", CellTags->"c:93"], Cell[57239, 2138, 199, 3, 43, "Input"], Cell[CellGroupData[{ Cell[57463, 2145, 78, 1, 27, "Input"], Cell[57544, 2148, 37, 1, 27, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[57630, 2155, 68, 2, 27, "Subsubsection", CellTags->"c:94"], Cell[57701, 2159, 180, 4, 43, "Input"], Cell[57884, 2165, 55, 0, 32, "Text"], Cell[CellGroupData[{ Cell[57964, 2169, 78, 2, 43, "Input"], Cell[58045, 2173, 88, 1, 27, "Output"], Cell[58136, 2176, 88, 1, 27, "Output"] }, Closed]] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[58297, 2185, 105, 3, 44, "Section", Evaluatable->False, CellTags->"c:95"], Cell[CellGroupData[{ Cell[58427, 2192, 55, 1, 28, "Subsubsection", CellTags->"c:96"], Cell[58485, 2195, 663, 17, 158, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[59185, 2217, 49, 1, 28, "Subsubsection", CellTags->"c:97"], Cell[59237, 2220, 381, 9, 68, "Text", Evaluatable->False], Cell[59621, 2231, 468, 15, 218, "Text"], Cell[60092, 2248, 143, 6, 50, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[60272, 2259, 153, 6, 41, "Subsection", Evaluatable->False, CellTags->"c:98"], Cell[60428, 2267, 169, 4, 50, "Text"], Cell[60600, 2273, 325, 6, 59, "Input"], Cell[60928, 2281, 50, 1, 27, "Input"], Cell[CellGroupData[{ Cell[61003, 2286, 54, 1, 27, "Input"], Cell[61060, 2289, 82, 1, 27, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[61179, 2295, 62, 1, 27, "Input"], Cell[61244, 2298, 208, 3, 43, "Output"] }, Closed]], Cell[61467, 2304, 192, 4, 68, "Text"], Cell[61662, 2310, 579, 13, 104, "Text"], Cell[62244, 2325, 70, 1, 27, "Input"], Cell[62317, 2328, 53, 0, 32, "Text"], Cell[62373, 2330, 80, 1, 27, "Input"], Cell[62456, 2333, 60, 1, 27, "Input"], Cell[62519, 2336, 68, 1, 27, "Input"], Cell[62590, 2339, 50, 0, 32, "Text"], Cell[62643, 2341, 64, 1, 27, "Input"], Cell[62710, 2344, 56, 0, 32, "Text"], Cell[62769, 2346, 160, 3, 59, "Input"], Cell[62932, 2351, 64, 1, 27, "Input"], Cell[62999, 2354, 50, 0, 32, "Text"], Cell[63052, 2356, 107, 2, 43, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[63208, 2364, 101, 3, 44, "Section", Evaluatable->False, CellTags->"c:99"], Cell[CellGroupData[{ Cell[63334, 2371, 78, 2, 28, "Subsubsection", Evaluatable->False, CellTags->"c:100"], Cell[63415, 2375, 641, 11, 86, "Text", Evaluatable->False], Cell[64059, 2388, 2222, 63, 338, "Text", Evaluatable->False], Cell[66284, 2453, 518, 11, 110, "Input"], Cell[CellGroupData[{ Cell[66827, 2468, 42, 0, 27, "Input"], Cell[66872, 2470, 84, 1, 43, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[67005, 2477, 72, 2, 28, "Subsubsection", Evaluatable->False, CellTags->"c:101"], Cell[67080, 2481, 3201, 94, 446, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[70318, 2580, 73, 2, 39, "Subsection", Evaluatable->False, CellTags->"c:102"], Cell[CellGroupData[{ Cell[70416, 2586, 52, 1, 28, "Subsubsection", CellTags->"c:103"], Cell[70471, 2589, 546, 17, 50, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[71054, 2611, 52, 1, 28, "Subsubsection", CellTags->"c:104"], Cell[71109, 2614, 873, 26, 140, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[72019, 2645, 52, 1, 28, "Subsubsection", CellTags->"c:105"], Cell[72074, 2648, 694, 22, 50, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[72805, 2675, 52, 1, 28, "Subsubsection", CellTags->"c:106"], Cell[72860, 2678, 1325, 29, 212, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[74246, 2714, 128, 3, 44, "Section", Evaluatable->False, CellTags->"c:107"], Cell[CellGroupData[{ Cell[74399, 2721, 78, 2, 28, "Subsubsection", Evaluatable->False, CellTags->"c:108"], Cell[74480, 2725, 246, 6, 50, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[74763, 2736, 72, 2, 28, "Subsubsection", Evaluatable->False, CellTags->"c:109"], Cell[74838, 2740, 813, 21, 176, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[75688, 2766, 73, 2, 39, "Subsection", Evaluatable->False, CellTags->"c:110"], Cell[CellGroupData[{ Cell[75786, 2772, 52, 1, 28, "Subsubsection", CellTags->"c:111"], Cell[75841, 2775, 144, 5, 32, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[76022, 2785, 52, 1, 28, "Subsubsection", CellTags->"c:112"], Cell[76077, 2788, 160, 5, 32, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[76274, 2798, 52, 1, 28, "Subsubsection", CellTags->"c:113"], Cell[76329, 2801, 1894, 55, 201, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[78260, 2861, 52, 1, 28, "Subsubsection", CellTags->"c:114"], Cell[78315, 2864, 852, 27, 76, "Text"] }, Closed]] }, Closed]] }, Closed]] }, Open ]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)