(************** 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[ 135988, 4953]*) (*NotebookOutlinePosition[ 158989, 5763]*) (* CellTagsIndexPosition[ 154309, 5583]*) (*WindowFrame->Normal*) Notebook[{ Cell["\[Copyright] K. Sutner 2004", "SmallText"], Cell[CellGroupData[{ Cell["Relations and Functions", "Title", CellTags->"c:1"], Cell[CellGroupData[{ Cell["Strict Orders", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:2"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", CellTags->"c:3"], Cell[TextData[{ "A relation \[Rho] is a pre-order if it is reflexive and transitive, a \ partial order if it is in addition antisymmetric. A partial order is a \ (total) order if it satisfies the comparability property: ", Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\ y\ \[Or] \ x\ \[Rho]\^c\ y\)]], " for all ", Cell[BoxData[ \(TraditionalForm\`x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\)]], " in the carrier set. \n\nOften it is useful to use an irreflexive version \ of the order instead: ", Cell[BoxData[ \(TraditionalForm\`x\ \[Sigma]\ y\ \ iff\ \ x\ \[Rho]\ y\ \ \[And] \ x\ \[NotEqual] \ y\)]], ". In arithmetic, this correspond to the two standard orders ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " and ", Cell[BoxData[ \(TraditionalForm\` < \)]], ". \n\nHence we define a ", StyleBox["strict pre-order", FontColor->RGBColor[0, 0, 1]], " to be any irreflexive transitive relation. The question arises what \ properties one should have for strict partial orders and strict total orders. \ \n\nIn the following, we write ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\_I = \ \[Rho]\ \[Union] \ I\)]], " for the reflexive closure of a relation. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:4"], Cell[TextData[{ "Let \[Rho] be a strict preorder. \n\n(a) Show that \[Rho] is also \ asymmetric. \n(b) Show that ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\_I\)]], " is antisymmetric. \n(c) Show that ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\_I\)]], " is a total order if, and only if, ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ x, \ y\ \((\ \ x\ \[Rho]\ y\ \ \[Or] \ x\ = \ y\ \[Or] \ x\ \(\[Rho]\^c\) y\ )\)\)]], ". \n\t" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", CellTags->"c:5"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:6"], Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\ y\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\ \[Rho]\ x\)]], " by trinsitivity implies ", Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\ x\)]], ", contradicting irreflexivity." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:7"], Cell[TextData[{ "Suppose ", Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\_I\ y\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\ \[Rho]\_I\ x\)]], ". Then by definition of ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\_I\)]], " we have \n\t", Cell[BoxData[ \(TraditionalForm\`\((x\ \[Rho]\ y\ \[Or] \ x\ = y)\)\ \[And] \ \((\ x\ \(\[Rho]\^c\) y\ \[Or] \ x\ = \ y)\)\)]], ". \nBy distributing we get \n\t", Cell[BoxData[ \(TraditionalForm\`\((x\ \[Rho]\ y\ \[And] \ x\ \(\[Rho]\^c\) y)\)\ \[Or] \ \((\ x\ \[Rho]\ y\ \[And] \ x\ = \ y)\)\ \[Or] \ \((x\ = \ y\ \[And] \ x\ \[Rho]\^c\ y\ )\)\ \[Or] \ \((\ x\ = \(y\ \[And] \ x\ = \ y\))\)\)]], ".\nSince both ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^c\)]], " are irreflexive, and \[Rho] is asymmetric, this is implies ", Cell[BoxData[ \(TraditionalForm\`x = y\)]], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:8"], Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`\[Rho]\_I\)]], " total means ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\ \)\) \(x\ \[Rho]\_I\ y\ \ \[Or] \ \ x\ \(\[Rho]\_I\^c\) y\)\)]], " for all ", Cell[BoxData[ \(TraditionalForm\`x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\)]], ". \nEquivalently, \n\t", Cell[BoxData[ \(TraditionalForm\`\((x\ \[Rho]\ y\ \[Or] \ x\ = y)\)\ \[Or] \ \((\ x\ \(\[Rho]\^c\) y\ \[Or] \ x\ = \ y)\)\)]], "\nwhich in turn is equivalent to \n\t", Cell[BoxData[ \(TraditionalForm\`\((x\ \[Rho]\ y\ \[Or] \ x\ = y\ \[Or] \ x\ \(\[Rho]\^c\) y\ )\)\)]], "\nDone." }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Classifying Orders", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:9"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", CellTags->"c:10"], Cell[TextData[{ "For a prime number ", Cell[BoxData[ \(TraditionalForm\`p\)]], " write ", Cell[BoxData[ \(TraditionalForm\`\(o\_p\)(n)\)]], " for the exponent of ", Cell[BoxData[ \(TraditionalForm\`p\)]], " in the prime decomposition of ", Cell[BoxData[ \(TraditionalForm\`n\)]], ", assuming it is 0 when ", Cell[BoxData[ \(TraditionalForm\`p\)]], " does not divide ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". For example, ", Cell[BoxData[ \(TraditionalForm\`\(o\_3\)(18)\ = \ 2\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(o\_3\)(100)\ = \ 0\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:11"], Cell[TextData[{ "For each of the following relations \[Rho] determine whether \[Rho] is a \ preorder, a partial order, or a total order. Also state whether the order is \ strict or not. Explain your answer (if some part is obvious, just say so). \n\ \n\t(a) \"less-than\" on the natural numbers\n\t(b) \"divides\" on the \ natural numbers\n\t(c) the empty relation on the natural numbers\n\t(d) \ the universal relation on the natural numbers\n\t(e) \"subset-of\" on the \ powerset of the natural numbers\n\t(f) ", Cell[BoxData[ \(TraditionalForm\`\(o\_p\)(x)\ < \ \(o\_p\)(y)\)]], " on the natural numbers for some fixed prime ", Cell[BoxData[ \(TraditionalForm\`p\)]], "\n\t" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", CellTags->"c:12"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:13"], Cell["\<\ Less-than is clearly irreflexive, asymmetric and transitive. Hence, \ we have a strict total order.\ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:14"], Cell[TextData[{ "Write ", Cell[BoxData[ \(TraditionalForm\`x | y\)]], " for ", Cell[BoxData[ \(TraditionalForm\`x\)]], " divides ", Cell[BoxData[ \(TraditionalForm\`y\)]], ". \nThe relation is clearly reflexive. It is antisymmetric since ", Cell[BoxData[ \(TraditionalForm\`x | y\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`x \[LessEqual] y\)]], " and ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " is antisymmetric. Transitivity is also clear. There are incomparable \ elements, e.g., 2 and 3 are incomparable. Hence, we have a non-strict partial \ order." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:15"], Cell["\<\ Clearly, the empty relation is irreflexive, so we are dealing with \ the strict situation. It is also asymmetric and transitive, take a look at the set versions of the \ definitions if you find this confusing. But everybody is incomparable to \ everbody else, so we have a strict partial order. This is actually not as useless as it may seem, take a course in domain \ theory. \ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part d", "Subsubsection", CellTags->"c:16"], Cell["\<\ By contrast, the universal relation is reflexive and transitive, \ hence a preorder. But it is not antisymmetric, so it is not a partial order. \ \ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part e", "Subsubsection", CellTags->"c:17"], Cell[TextData[{ "Subset of is reflexive (as opposed to proper subset) and antisymmetric, \ see the notes on sets. It's also transitive by definition. There certainly \ are incomparable sets such as ", Cell[BoxData[ \(TraditionalForm\`{0}\)]], " and ", Cell[BoxData[ \(TraditionalForm\`{1}\)]], ", so we have a non-strict partial order. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part f", "Subsubsection", CellTags->"c:18"], Cell[TextData[{ "The point here is the following. We already have a strict total order on \ the natural numbers ", Cell[BoxData[ \(TraditionalForm\`\[LeftAngleBracket]\ \[DoubleStruckCapitalN], < \ \[RightAngleBracket]\)]], ". Now suppose we take some set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " and a function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ A\ \[LongRightArrow]\ \[DoubleStruckCapitalN]\)]], ", and then use ", Cell[BoxData[ \(TraditionalForm\`f\)]], " to define a relation on ", Cell[BoxData[ \(TraditionalForm\`A\)]], " by setting\n\n\t\t", Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\ y\ \ \ iff\ \ \(f(x)\)\ < \ f(y)\)]], ". \n\nNote that the answer depends on ", Cell[BoxData[ \(TraditionalForm\`f\)]], ". For example, if ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is the identity we simply get ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ = \ < \)]], ". But if ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is constant, we get the empty relation. Nonetheless, no matter what ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is, \[Rho] is always irreflexive, transitive and asymmetric. E.g., ", Cell[BoxData[ \(TraditionalForm\`f(x)\ < \ f(y)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`f(y) < f(z)\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`f(x) < \ f(z)\)]], ", so \[Rho] is transitive. So, we always get a strict partial order. \n\n\ In our case, ", Cell[BoxData[ \(TraditionalForm\`f = o\_p\)]], ". Then \[Rho] is not total: we have ", Cell[BoxData[ \(TraditionalForm\`\(o\_p\)(p)\ = \ \(\(o\_p\)(p\ q)\ = \ 1\)\)]], " for any prime ", Cell[BoxData[ \(TraditionalForm\`q\)]], " other than ", Cell[BoxData[ \(TraditionalForm\`p\)]], ". But ", Cell[BoxData[ \(TraditionalForm\`p\ q\ \[NotEqual] \ p\)]], ", and we don't get a total order" }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Rotating Lists", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:19"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", Evaluatable->False, CellTags->"c:20"], Cell[TextData[{ "The transitive closure ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^+\)\)]], " is an equivalence relation provided that \[Rho] is already reflexive and \ symmetric. The following examples shows that we may get an equvilance \ relation even if \[Rho] is far from reflexive or symmetric. \nConsider as \ carrier set all binary lists of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". Define a relation \[Rho] as follows:\n\n\t", Cell[BoxData[ \(TraditionalForm\`L\ \[Rho]\ K\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`L\)]], " is the cyclic left-shift of ", Cell[BoxData[ \(TraditionalForm\`K\)]], ". \n\t\nIt is easy to visualize this in Mathematica, at least for small \ values of ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". \n" }], "Text", Evaluatable->False], Cell[BoxData[{ \(\(A = Tuples[2, 6] - 1;\)\), "\n", \(\(rho[L_List, K_List] := L \[Equal] RotateLeft[K];\)\), "\n", \(\(R = RelationToMatrix[A, rho];\)\), "\n", \(\(PlotMatrix[R];\)\)}], "Input"], Cell[BoxData[{ \(RR = TransitiveClosure[R]; \), "\n", \(PlotMatrix[RR]; \)}], "Input"], Cell["\<\ Note that it is easy to see that the closure is reflexive and \ symmetric, but transitivity itself is invisible. \ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:21"], Cell[TextData[{ "(a) Show that the relation ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^+\)\)]], " from above is indeed reflexive and symmetric, for any ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". \n\n(b) By hand, compute the equivalence classes for the concrete cases \ ", Cell[BoxData[ \(TraditionalForm\`n = 4\)]], " and ", Cell[BoxData[ \(TraditionalForm\`n = 5\)]], ". In particular, determine the number of equivalence classes, and their \ sizes. \n\n(c) By computer, do the same for ", Cell[BoxData[ \(TraditionalForm\`n = 10\)]], ". " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:22"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:23"], Cell[TextData[{ "To see that ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^+\)\)]], " is reflexive, note that ", Cell[BoxData[ \(TraditionalForm\`L\ \(\[Rho]\^\(\(\ \)\(n\)\)\) L\)]], " for any list of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". \nSymmetry follows from ", Cell[BoxData[ \(TraditionalForm\`K\ \[Rho]\ L\ \ \[DoubleLeftRightArrow] \ \ L\ \(\[Rho]\^\(\(\ \)\(n - 1\)\)\) K\)]], ": a right shift is the same as ", Cell[BoxData[ \(TraditionalForm\`n - 1\)]], " left shifts. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:24"], Cell[TextData[{ "From part a it follows that the equivalence class of ", Cell[BoxData[ \(TraditionalForm\`L\)]], " can have at most ", Cell[BoxData[ \(TraditionalForm\`n\)]], " elements: ", Cell[BoxData[ \(TraditionalForm\`L = \((0, 0 \[Ellipsis], 0, 1)\)\)]], " has ", Cell[BoxData[ \(TraditionalForm\`n\)]], " equivalent lists. But, the class may well be smaller: ", Cell[BoxData[ \(TraditionalForm\`L = \((1, 1, \[Ellipsis], 1)\)\)]], " is alone in its class. \nThe classes for ", Cell[BoxData[ \(TraditionalForm\`n = 4\)]], " are\n\n0000\n1111\n0101, 1010\n0001, 0010, 0100, 1000\n0011, 0110, 1100, \ 1001\n0111, 1110, 1101, 1011\n\nThus, there are 6 classes, of sizes 1, 1, 2, \ 4, 4, 4, respectively. \n\nFor ", Cell[BoxData[ \(TraditionalForm\`n = 5\)]], " we have \n\n00000\n11111\n00001, 00010, 00100, 01000, 10000\n00011, \ 00110, 01100, 11000, 10001,\n00101, 01010, 10100, 01001, 10010\n00111, 01110, \ 11100, 11001, 10011\n01011, 10110, 01101, 11010, 10101\n01111, 11110, 11101, \ 11011, 10111\n\nHence, there are 8 classes of size 1, 1, 5, 5, 5, 5, 5, 5, \ respectively. \n\nOne might suspect that it is no coincidence that the sizes \ of the equivalence classes are all divisors of ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". A little bit of work shows that indeed there is an equivalence class of \ size ", Cell[BoxData[ \(TraditionalForm\`m\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`m\)]], " divides ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". Counting the number of classes of a given size is a bit harder. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:25"], Cell["\<\ Hence, there will be more than 256/8 = 32 classes, and we should do this by \ computer, not by hand. First, a brute force function to check equivalence of two lists. \ \>", "Text"], Cell[BoxData[ \(equ[L_List, K_List] := MemberQ[\((RotateLeft[L, #1] &)\) /@ Range[Length[L]], K]\)], "Input"], Cell["We can select all the lists equivalent to a given one:", "Text"], Cell[BoxData[{ \(A = Tuples[2, 10] - 1; \), "\n", \(Length[A]\)}], "Input"], Cell[BoxData[ \(Select[A, equ[{1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, #1] &]\)], "Input"], Cell[BoxData[ \(Select[A, equ[{1, 0, 0, 0, 0, 1, 0, 0, 0, 0}, #1] &]\)], "Input"], Cell["\<\ Here is a little function that extracts equivalent lists until \ nothing is left. This will take a bit. \ \>", "Text"], Cell[BoxData[{ \(AA = A; \), "\n", \(\(classes = {};\)\), "\n", \(\(While[ AA \[NotEqual] {}, \[IndentingNewLine]L = First[AA]; \[IndentingNewLine]cl = Select[AA, equ[L, #1] &]; \[IndentingNewLine]AA = Complement[AA, cl]; \[IndentingNewLine]AppendTo[classes, cl]\[IndentingNewLine]];\)\ \ // \ AbsoluteTiming\)}], "Input"], Cell[BoxData[{ \(Length[classes]\), "\n", \(Length /@ classes\)}], "Input"], Cell[BoxData[ \(TableForm[Frequencies[%]]\)], "Input"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Sorting Algorithms", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:26"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", Evaluatable->False, CellTags->"c:27"], Cell[TextData[{ "C++ libraries such as the STL provide sorting algorithms that take as \ optional input a user defined comparison function of type \n\n\t\t", StyleBox["bool cmp( const T& x, const T& y ); ", "Input"], "\n\t\t\nNeedless to say, there are some minimal requirements the function \ must satisfy in order for the algorithm to work. Here is a description of \ these requirements taken verbatim from Stroustrup's book. \n \n(1) cmp(x,x) \ is false.\n(2) If cmp(x,y) and cmp(y,z), then cmp(x,z).\n(3) Define \ equiv(x,y) to be !(cmp(x,y) || cmp(y,x)). If equiv(x,y) and equiv(y,z), then \ equiv(x,z).\n" }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:28"], Cell["\<\ (a) Translate Stroustrup's description into the language of \ relations. (b) Show that equiv is indeed an equivalence relation provided that \ conditions (1), (2) and (3) hold. (c) Come up with a natural user-defined comparison function that satisfies \ Stroustrup's criteria. (d) Come up with a natural user-defined comparison function that fails to \ satisfy Stroustrup's criteria. \ \>", "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:29"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:30"], Cell[TextData[{ "(1): cmp is irreflexive\n(2): cmp is transitive\n(3): Let equiv ", Cell[BoxData[ \(TraditionalForm\`\(\(=\)\(\(\ \)\(\ \)\) \(\(cmp\ \[Union] \ cmp\^\(\(\ \)\(c\)\)\)\&_\)\)\)]], ". Then equiv is transitive. \n\nNote that equiv is none other than the \ incomparability relation associated with cmp. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:31"], Cell[TextData[{ "By (3), equiv is transitive. \nTo see reflexivity, note that ", Cell[BoxData[ \(TraditionalForm\`\[Not] \ x\ equiv\ x\)]], " means ", Cell[BoxData[ \(TraditionalForm\`x\ \((cmp\ \[Union] \ cmp\^c)\)\ x\)]], ", which is impossible since by (1) both cmp and ", Cell[BoxData[ \(TraditionalForm\`cmp\^\(\(\ \)\(c\)\)\)]], " are irreflexive. \nFor symmetry note that ", Cell[BoxData[ \(TraditionalForm\`cmp\ \[Union] \ cmp\^c\)]], " is symmetric by brute force. \nBut the complement of any symmetric \ relation is again symmetric:\n\n\t", Cell[BoxData[ \(TraditionalForm\`x\ \(\[Rho]\&_\) y\ \ \[DoubleLeftRightArrow] \ \ \(\[Not] \ \((\ x\ \[Rho]\ y\ )\)\ \[DoubleLeftRightArrow] \ \(\[Not] \ \((\ y\ \[Rho]\ x\ )\)\ \[DoubleLeftRightArrow] \ y\ \(\(\(\[Rho]\)\(\ \)\)\&_\) x\)\)\)]], ". \n\t\nDone." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:32"], Cell["\<\ Suppose we are dealing with lists of integers and compare them by \ length. Then the sorting algorithm will work properly, but we do not know how \ lists of the same length will be arranged. \ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part d", "Subsubsection", CellTags->"c:33"], Cell[TextData[{ "Suppose we are dealing with binary lists of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], " and compare them by set-inclusion: think of the lists as bitvectors. \ In other words, ", Cell[BoxData[ \(TraditionalForm\`K\ cmp\ L\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\(\(L\)\(\ \)\)\)]], " can be obtained from ", Cell[BoxData[ \(TraditionalForm\`K\)]], " by turning on a few bits (at least one). Then cmp is clearly irreflexive \ and transitive, but equiv fails to be transitive: \n\n\t", Cell[BoxData[ \(TraditionalForm\`x = \ \((1, 0, 0)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`y = \ \((0, 1, 0)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`z = \ \((1, 0, 1)\)\)]], "." }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["TRC and Union", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:34"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", Evaluatable->False, CellTags->"c:35"], Cell[TextData[{ "Recall the notation ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^*\)\)]], " for transitive reflexive closure. \nThus, ", Cell[BoxData[ \(TraditionalForm\`x\ \(\[Rho]\^*\) y\)]], " iff there is a chain of related elements \n\n\t\t", Cell[BoxData[ \(TraditionalForm\`x\ = \ \(x\_0\ \[Rho]\ x\_1\ \[Rho]\ x\_\(\(\ \)\(2\ \)\)\ \[Ellipsis]\ \(x\_\(n - 1\)\) \[Rho]\ x\_n\ = \ y\)\)]], " \n\t\t\nIn terms of the associated graph this simply means: \"there is a \ path from ", Cell[BoxData[ \(TraditionalForm\`x\)]], " to ", Cell[BoxData[ \(TraditionalForm\`y\)]], "\". " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:36"], Cell[TextData[{ "Show that for binary relations \[Rho] and \[Sigma] on some set ", Cell[BoxData[ \(TraditionalForm\`A\)]], "\n\n\t ", Cell[BoxData[ \(TraditionalForm\`\(\(\(\((\[Rho]\ \[Union] \ \[Sigma])\)\^*\)\(\ \ \)\) \(\((\(\[Rho]\^*\)\ \[CenterDot]\ \(\[Sigma]\^*\))\)\^*\)\(\ \)\)\)]], "\n\nMake sure to translate this statement into one about the corresponding \ graphs so you can see what it really means." }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Hint", "Subsubsection", Evaluatable->False, CellTags->"c:37"], Cell[TextData[{ "First show that ", Cell[BoxData[ \(TraditionalForm\`\[Tau]\_1 \[SubsetEqual] \ \[Tau]\_2\ \ \[DoubleLongRightArrow]\ \ \(\[Tau]\_1\^*\) \[SubsetEqual] \ \(\[Tau]\_2\^*\)\ \)]], ". \n\nThen argue about chains. A serious proof would use induction. " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:38"], Cell[TextData[{ "Assume ", Cell[BoxData[ \(TraditionalForm\`\[Tau]\_1 \[SubsetEqual] \ \[Tau]\_2\)]], ". A simple induction shows that ", Cell[BoxData[ FormBox[ RowBox[{" ", FormBox[\(\[Tau]\_1\%\(\(\ \)\(k\)\) \[SubsetEqual] \ \[Tau]\_2\%\(\ \(\ \)\(k\)\)\), "TraditionalForm"]}], TraditionalForm]]], " for all ", Cell[BoxData[ \(TraditionalForm\`k\ \[GreaterEqual] \ 0\)]], ". But then ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\ \)\) \(\(\[Tau]\_1\^*\) \[SubsetEqual] \ \ \(\[Tau]\_2\^*\)\)\)]], ".\n\nBut ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[Union] \ \[Sigma]\ = \[Rho]\ \ \[CenterDot]\ I\ \[Union] I\ \[CenterDot]\ \[Sigma]\ \[SubsetEqual] \(\(\(\[Rho]\^*\)\ \ \[CenterDot]\ \(\[Sigma]\^*\)\)\(\ \)\)\)]], ", so we only have to show\n\n\t", Cell[BoxData[ \(TraditionalForm\`\(\((\(\[Rho]\^*\)\ \[CenterDot]\ \(\[Sigma]\^*\))\)\ \^*\)\ \[SubsetEqual] \ \(\((\[Rho]\ \[Union] \ \[Sigma])\)\^*\)\)]], ". \n\nTo this end we show by induction on ", Cell[BoxData[ \(TraditionalForm\`k\)]], " that \n\n\t", Cell[BoxData[ \(TraditionalForm\`\((\(\[Rho]\^*\)\ \[CenterDot]\ \(\[Sigma]\^*\))\)\^\ \(\(\ \)\(k\)\)\ \[SubsetEqual] \ \(\((\[Rho]\ \[Union] \ \ \[Sigma])\)\^*\)\)]], ". \n\nThe claim is obvious for ", Cell[BoxData[ \(TraditionalForm\`k = 0\)]], ". Now\n\t\n\t", Cell[BoxData[ \(TraditionalForm\`\((\(\[Rho]\^*\)\ \[CenterDot]\ \(\[Sigma]\^*\))\)\^\ \(k + 1\)\ = \ \((\(\[Rho]\^*\)\ \[CenterDot]\ \(\[Sigma]\^*\))\)\^k\ \[CenterDot]\ \((\(\[Rho]\^*\)\ \[CenterDot]\ \(\[Sigma]\^*\))\)\ \ \[SubsetEqual] \ \(\(\(\((\[Rho]\ \[Union] \ \[Sigma])\)\^*\)\[CenterDot]\ \ \((\(\[Rho]\^*\)\ \[CenterDot]\ \(\[Sigma]\^*\))\)\)\(\ \)\)\)]], " \n\nby IH and by transitivity it suffices to show that ", Cell[BoxData[ \(TraditionalForm\`\((\(\[Rho]\^*\)\ \[CenterDot]\ \(\[Sigma]\^*\))\)\ \ \[SubsetEqual] \ \(\((\[Rho]\ \[Union] \ \[Sigma])\)\^*\)\)]], ".\nBut ", Cell[BoxData[ \(TraditionalForm\`x\ \((\(\[Rho]\^*\)\ \[CenterDot]\ \ \(\[Sigma]\^*\))\) y\)]], " means that there is a chain \n\n\t", Cell[BoxData[ \(TraditionalForm\`x\ = \ \(x\_0\ \[Rho]\ \(x\_1\) \[Rho]\ \[Ellipsis]\ \ \[Rho]\ \ \(x\_r\) \[Sigma]\ \(y\_1\) \[Sigma]\ y\_2\ \[Ellipsis]\ \[Sigma]\ \ y\_s = \ y\)\)]], ". \n\t\nThis chain shows that ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(x\ \(\((\[Rho]\ \[Union] \ \[Sigma])\)\^*\ \) y\)\)\)]], "." }], "Text", Evaluatable->False], Cell["\<\ If the ellipsis horrifies you, replace it by yet another induction \ argument. \ \>", "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["List Reversal", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:39"], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:40"], Cell[TextData[{ "Recall our recursive definition of reversal of a list:\n\n\t", Cell[BoxData[ \(TraditionalForm\`rev(\[Epsilon])\ = \ \[Epsilon]\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`rev(\ a\ \[CenterDot]\ L\ )\ = \ \(rev(L)\)\ \[CenterDot]a\)]], "\n\t\nWe showed in class that ", Cell[BoxData[ \(TraditionalForm\`rev(\ L\ \[CenterDot]\ a\ )\ = \ a\ \[CenterDot]\ \(rev(L)\)\)]], ". " }], "Text", Evaluatable->False], Cell[TextData[{ "\nEstablish all the following claims by induction on lists.\n", "\n", "a) ", Cell[BoxData[ \(TraditionalForm\`rev(\ L\ \[CenterDot]\ K\ )\ = \ \(rev(K)\)\ \[CenterDot]\ \(rev( L)\)\)]], "\n\nb) ", Cell[BoxData[ \(TraditionalForm\`rev(\ rev(L)\ )\ = L\)]], "\n\nc) All palindromes of even length are of the form ", Cell[BoxData[ \(TraditionalForm\`L\ \[CenterDot]\ \(rev(L)\)\)]], ". \n" }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:41"], Cell[TextData[{ "a) Induction on ", Cell[BoxData[ \(TraditionalForm\`K\)]], ". \n\n", Cell[BoxData[ \(TraditionalForm\`\(\(\(rev(\ \ L\ \[CenterDot]\ \[Epsilon]\ )\)\(\ \)\)\(=\)\(\ \)\(rev( L)\ = \ \(\[Epsilon]\ \[CenterDot]\ \(rev( L)\)\ \ = \ \(rev(\[Epsilon])\)\ \[CenterDot]\ \(rev( L)\)\)\)\(\ \)\)\)]], "\n\n", Cell[BoxData[ \(TraditionalForm\`\(\(\(rev(\ \ L\ \[CenterDot]\ K\ \[CenterDot]\ a\ )\)\(\ \)\)\(=\)\(\ \)\(a\ \[CenterDot]\ \(rev( L\[CenterDot]K)\)\ = \ \(a\ \[CenterDot]\ \(rev( K)\)\ \[CenterDot]\ \(rev(L)\)\ \ = \ \(rev( K\[CenterDot]a)\)\ \[CenterDot]\ \(rev(L)\)\)\)\(\ \)\)\)]] }], "Text"], Cell[TextData[{ "b) Induction on ", Cell[BoxData[ \(TraditionalForm\`L\)]], ". \n\n", Cell[BoxData[ \(TraditionalForm\`\(\(\(rev( rev(\ \ \[Epsilon]\ ))\)\(\ \)\)\(=\)\(\ \)\(rev(\[Epsilon])\ = \ \ \[Epsilon]\)\(\ \)\)\)]], "\n\n", Cell[BoxData[ \(TraditionalForm\`\(\(rev(\ rev(\ \ a\ \[CenterDot]\ L\ )\ )\)\(=\)\(\ \)\(rev(\ \ \(rev(L)\)\ \ \[CenterDot] a\ \ ) = \ \(a\ \[CenterDot]\ \(rev(rev(L))\)\ \ = a\ \[CenterDot]L\)\)\(\ \)\)\)]] }], "Text"], Cell[TextData[{ "c) First consider a list ", Cell[BoxData[ \(TraditionalForm\`K\ = \ L\ \[CenterDot]\ \(rev(L)\)\)]], ". Then, by a) and b), we have\n\n\t", Cell[BoxData[ \(TraditionalForm\`rev( K)\ = \ \(rev(\ L\ \[CenterDot]\ \(rev(L)\)\ )\ = \ \(\(rev( rev(L))\)\ \[CenterDot]\ \(rev( L)\)\ = \ \(L\ \[CenterDot]\ \(rev(L)\)\ = \ K\)\)\)\)]], ",\n\t\nso that ", Cell[BoxData[ \(TraditionalForm\`K\)]], " is an even length palindrome. \nOn the other hand, assume ", Cell[BoxData[ \(TraditionalForm\`K\ = \ rev(K)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`K\ = \ A\[CenterDot]\ B\)]], ", say, with ", Cell[BoxData[ \(TraditionalForm\`A\)]], " and ", Cell[BoxData[ \(TraditionalForm\`B\)]], " lists of length ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(K\)\(|\)\(\(/\)\(2\)\)\)\)]], ". \nAgain using a) and b) we have \n\n\t", Cell[BoxData[ \(TraditionalForm\`A\ \[CenterDot]\ B\ = \ \(K\ = \ \(rev( K)\ = \ \(rev( A\[CenterDot]B)\ = \ \(rev(B)\)\ \[CenterDot]\ \(rev( A)\)\)\)\)\)]], ". \n\nHence, ", Cell[BoxData[ \(TraditionalForm\`B\ = \ rev(A)\)]], ", done." }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Divisibility on [100]", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:42"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", CellTags->"c:43"], Cell[TextData[{ "For the next problem, fix the carrier set ", Cell[BoxData[ \(TraditionalForm\`\(\([\)\(100\)\(]\)\)\ = \ {1, 2, 3, \[Ellipsis], 100}\)]], ". \nDefine a relation \[Rho] as follows:\n\n\t", Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\ y\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`x\)]], " divides ", Cell[BoxData[ \(TraditionalForm\`y\)]], " and ", Cell[BoxData[ \(TraditionalForm\`1 < x < y\)]], ". \n" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:44"], Cell[TextData[{ "(a) Show that the relation ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\)]], " from above is transitive. \n\n(b) Argue that there must be a ", Cell[BoxData[ \(TraditionalForm\`k\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^\(\(\ \)\(k\)\) = \ \[EmptySet]\)]], ". \n\n(c) Let ", Cell[BoxData[ \(TraditionalForm\`k\_\(\(\ \)\(0\)\)\)]], " be the least ", Cell[BoxData[ \(TraditionalForm\`k\)]], " as in part (b), and determine ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^\(\(\ \)\(k\_\(\(\ \)\(0\)\) - 1\)\)\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", CellTags->"c:45"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:46"], Cell[TextData[{ "Transitivity is easy\n\n\t", Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\ y\ \[Rho]\ z\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`x\)]], " divides ", Cell[BoxData[ \(TraditionalForm\`y\)]], " and ", Cell[BoxData[ \(TraditionalForm\`1 < x < y\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\)]], " divides ", Cell[BoxData[ \(TraditionalForm\`z\)]], " and ", Cell[BoxData[ \(TraditionalForm\`1 < y < z\)]], " \n\t\nfrom which it follows that ", Cell[BoxData[ \(TraditionalForm\`x\)]], " divides ", Cell[BoxData[ \(TraditionalForm\`z\)]], " and ", Cell[BoxData[ \(TraditionalForm\`1 < x < z\)]], ". \n" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:47"], Cell[TextData[{ "Here, divisibility is a red herring: only order is needed for the \ argument. \n\nAn easy induction shows that ", Cell[BoxData[ \(TraditionalForm\`x\ \(\[Rho]\^\(\(\ \)\(k\)\)\) y\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`y\ \[GreaterEqual] \ x\ + \ k\)]], ", so clearly ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^100 = \ \[EmptySet]\)]], ". \n" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:48"], Cell["\<\ But now we have to really deal with divisibility since it lowers \ the bound significantly. First, a picture.\ \>", "Text"], Cell["\<\ rho[x_,y_] := Mod[y,x]==0 && 1 < x < y; PlotRelation[ rho, 100, 5 ];\ \>", "Input"], Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`\[Rho]\^\(\(\ \)\(5\)\)\)]], " is not empty. \n\nBut ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^6\)]], " is:" }], "Text"], Cell["PlotRelation[ rho, 100, 6 ];", "Input"], Cell[TextData[{ "The \"curves\" in the first picture are exponential: they correspond to \ multiplication by 2 and 3. Since ", Cell[BoxData[ \(TraditionalForm\`2\^7 > 100\)]], " it follows that ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^6\)]], " is indeed empty (on domain ", Cell[BoxData[ \(TraditionalForm\`\(\([\)\(100\)\(]\)\)\)]], ", mind you), so ", Cell[BoxData[ \(TraditionalForm\`k\_0 = \ 6\)]], ".\n\nWhat is ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^5\)]], "? \nA little experimentation shows ", Cell[BoxData[ \(TraditionalForm\`{\ \((2, 64)\), \ \((2, 96)\), \((3, 96)\)\ }\)]], " since ", Cell[BoxData[ \(TraditionalForm\`64\ = \ 2\ \[CenterDot]\ 2\^5\)]], " and ", Cell[BoxData[ \(TraditionalForm\`96\ = \ 2\ \[CenterDot]\ 3\[CenterDot]\ 2\^4\)]], "." }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Relatively Prime Numbers", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:49"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", CellTags->"c:50"], Cell["\<\ A relation on a finite set can be represented by data structures, \ and one can write programs to check if the relation has certain properties. \ For infinite carrier sets, only direct reasoning helps. \ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:51"], Cell[TextData[{ "Consider the relation \[Rho] defined on the natural numbers by \n\n\t", Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\ y\ \ iff\ \ \ \(gcd(x, y)\)\ = \ 1\)]], ".\n\nI.e., two numbers are related if they have no common prime factor. \n\ \n(a) Determine if \[Rho] is symmetric,\n(b) Determine if \[Rho] is \ reflexive,\n(c) Determine if \[Rho] is transitive.\n(d) Compute ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^\(\(\ \)\(2\)\)\)]], "." }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:52"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:53"], Cell[TextData[{ "\[Rho] is symmetric since the GCD is: ", Cell[BoxData[ \(TraditionalForm\`gcd(x, y)\ = \ gcd(y, x)\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:54"], Cell[TextData[{ "\[Rho] is not reflexive since ", Cell[BoxData[ \(TraditionalForm\`gcd(x, x)\ = x\ \[NotEqual] \ 1\)]], " for any ", Cell[BoxData[ \(TraditionalForm\`x \[NotEqual] 1\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:55"], Cell[TextData[{ "\[Rho] is not transitive since ", Cell[BoxData[ \(TraditionalForm\`gcd(2, 3)\ = 1\)]], ", ", Cell[BoxData[ \(TraditionalForm\`gcd(3, 4)\ = 1\)]], " but ", Cell[BoxData[ \(TraditionalForm\`gcd(2, 4)\ = 2\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part d", "Subsubsection", CellTags->"c:56"], Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`\[Rho]\^2 = \ U\_\[DoubleStruckCapitalN]\)]], " : for any pair of numbers ", Cell[BoxData[ \(TraditionalForm\`x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\)]], " pick a prime ", Cell[BoxData[ \(TraditionalForm\`p\)]], " that divides neither ", Cell[BoxData[ \(TraditionalForm\`x\)]], " nor ", Cell[BoxData[ \(TraditionalForm\`y\)]], " (this is always possible since there are infinitely many primes). But \ then ", Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\ p\)]], " and ", Cell[BoxData[ \(TraditionalForm\`p\ \[Rho]\ y\)]], ", whence ", Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\^\(\(\ \)\(2\)\)\ y\)]], ". " }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["TRC and Union", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:57"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", Evaluatable->False, CellTags->"c:58"], Cell[TextData[{ "For any relation \[Rho] write ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^\(\(\ \)\(*\)\)\)]], " for the relation: \"there is a \[Rho]-chain\". \n\nIn other words, ", Cell[BoxData[ \(TraditionalForm\`x\ \(\[Rho]\^*\) y\)]], " iff there is a chain of related elements \n\n\t\t", Cell[BoxData[ \(TraditionalForm\`x\ = \ \(x\_0\ \[Rho]\ x\_1\ \[Rho]\ x\_\(\(\ \)\(2\ \)\)\ \[Ellipsis]\ \(x\_\(n - 1\)\) \[Rho]\ x\_n\ = \ y\)\)]], " \n\t\t\nIn terms of the associated graph this simply means: \"there is a \ path from ", Cell[BoxData[ \(TraditionalForm\`x\)]], " to ", Cell[BoxData[ \(TraditionalForm\`y\)]], "\". " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:59"], Cell[TextData[{ "Show that for binary relations \[Rho] and \[Sigma] on some set ", Cell[BoxData[ \(TraditionalForm\`A\)]], "\n\n\t ", Cell[BoxData[ \(TraditionalForm\`\(\(\(\((\[Rho]\ \[Union] \ \[Sigma])\)\^*\)\(\ \ \)\) \(\((\(\[Rho]\^*\)\ \[CenterDot]\ \(\[Sigma]\^*\))\)\^*\)\(\ \)\)\)]], "\n\nMake sure to translate this statement into one about the corresponding \ graphs so you can see what it really means." }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Hint", "Subsubsection", Evaluatable->False, CellTags->"c:60"], Cell[TextData[{ "First show that ", Cell[BoxData[ \(TraditionalForm\`\[Tau]\_1 \[SubsetEqual] \ \[Tau]\_2\ \ \[DoubleLongRightArrow]\ \ \(\[Tau]\_1\^*\) \[SubsetEqual] \ \(\[Tau]\_2\^*\)\ \)]], ". \nThen argue about chains. A real serious proof would use induction. " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:61"], Cell[TextData[{ "First the hint:\n\n", StyleBox["Claim", FontWeight->"Bold"], ": ", Cell[BoxData[ \(TraditionalForm\`\[Tau]\_1 \[SubsetEqual] \ \[Tau]\_2\ \ \[DoubleLongRightArrow]\ \ \(\[Tau]\_1\^*\) \[SubsetEqual] \ \(\[Tau]\_2\^*\)\ \)]], ". \n\nTo prove this, use induction on ", Cell[BoxData[ \(TraditionalForm\`k\)]], " to show ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\ \)\) \(\[Tau]\_1\^k \[SubsetEqual] \ \ \[Tau]\_2\^k\)\)]], ".\n", Cell[BoxData[ \(TraditionalForm\`k = 0\)]], ": holds by definition since ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\[Tau]\_1\^0 = \ \(\[Tau]\_2\^0 = \ I\_A\)\)\)\)]], ". \nStep: ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\ \)\) \(x\ \(\[Tau]\_1\^\(k + 1\)\) y\)\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(x\ \(\[Tau]\_1\) z\)\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(z\ \(\[Tau]\_1\^k\) y\)\)\)]], " for some ", Cell[BoxData[ \(TraditionalForm\`z\)]], ". \nBut then by our assumption ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(x\ \(\[Tau]\_2\) z\)\)\)]], " , and ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(z\ \(\[Tau]\_2\^k\) y\)\)\)]], " by IH. \nIt follows that ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\ \)\) \(x\ \(\[Tau]\_2\^\(k + 1\)\) y\)\)]], ", as required. " }], "Text", Evaluatable->False], Cell[TextData[{ "\nNow note that ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[Union] \ \[Sigma]\ \[SubsetEqual] \ \(\ \[Rho]\^*\) \[Union] \ \(\[Sigma]\^*\)\)]], " by definition of the closure operation. \n\nSo by the hint, ", Cell[BoxData[ \(TraditionalForm\`\(\(\(\((\[Rho]\ \[Union] \ \[Sigma])\)\^*\)\(\ \ \)\)\(\[SubsetEqual]\)\(\((\(\[Rho]\^*\)\ \[CenterDot]\ \(\[Sigma]\^*\))\)\^*\ \)\(\ \)\)\)]], " and we only have to establish the opposite direction.\n\n", StyleBox["Claim", FontWeight->"Bold"], ": ", Cell[BoxData[ FormBox[ RowBox[{" ", RowBox[{ FormBox[\(\(\((\(\[Rho]\^*\)\ \[CenterDot]\ \(\[Sigma]\^*\))\)\^*\ \)\(\ \)\), "TraditionalForm"], "\[SubsetEqual]", " ", FormBox[\(\(\((\[Rho]\ \[Union] \ \[Sigma])\)\^*\)\(\ \)\), "TraditionalForm"]}]}], TraditionalForm]]], "\n\nWe use induction on ", Cell[BoxData[ \(TraditionalForm\`k\)]], " to show that ", Cell[BoxData[ FormBox[ RowBox[{" ", FormBox[ RowBox[{" ", RowBox[{ FormBox[\(\((\(\[Rho]\^*\)\ \[CenterDot]\ \ \(\[Sigma]\^*\))\)\^\(\(\(\ \)\(k\)\)\(\ \)\)\), "TraditionalForm"], "\[SubsetEqual]", " ", FormBox[\(\(\((\[Rho]\ \[Union] \ \[Sigma])\)\^*\)\(\ \)\), "TraditionalForm"]}]}], "TraditionalForm"]}], TraditionalForm]]], ".\nFor ", Cell[BoxData[ \(TraditionalForm\`k = 0\)]], " there is nothing to show. \nSo assume ", Cell[BoxData[ \(TraditionalForm\`\(\(x\) \(\(\ \)\(\ \)\) \(\((\(\[Rho]\^*\)\ \ \[CenterDot]\ \(\[Sigma]\^*\))\)\^\(\(\ \)\(k + 1\)\)\)\(\ \)\(y\)\(\ \)\)\)]], ". \nBy definition, ", Cell[BoxData[ \(TraditionalForm\`x \(\(\ \)\(\ \)\) \((\(\[Rho]\^*\)\ \[CenterDot]\ \ \(\[Sigma]\^*\))\)\ z \(\(\ \)\(\ \)\)\)]], " and ", Cell[BoxData[ FormBox[ RowBox[{" ", FormBox[\(z \(\(\ \)\(\ \)\) \((\(\[Rho]\^*\)\ \[CenterDot]\ \(\ \[Sigma]\^*\))\)\^\(\(\ \)\(k\)\)\ y \(\(\ \)\(\ \)\)\), "TraditionalForm"]}], TraditionalForm]]], " for some ", Cell[BoxData[ \(TraditionalForm\`z\)]], ". \nBut then ", Cell[BoxData[ \(TraditionalForm\`x \(\(\ \)\(\ \)\) \[Rho]\^\(\(\ \)\(s\)\)\ u \(\(\ \ \)\(\ \)\)\)]], " and ", Cell[BoxData[ FormBox[ RowBox[{" ", FormBox[\(u \(\(\ \)\(\ \)\) \(\[Sigma]\^t\) z \(\(\ \)\(\ \)\)\), "TraditionalForm"]}], TraditionalForm]]], " for some ", Cell[BoxData[ \(TraditionalForm\`u\)]], " and suitable values of ", Cell[BoxData[ \(TraditionalForm\`s\)]], " and ", Cell[BoxData[ \(TraditionalForm\`t\)]], ".\n(OK, if you really want to be serious: use subinduction on ", Cell[BoxData[ \(TraditionalForm\`s\)]], " and ", Cell[BoxData[ \(TraditionalForm\`t\)]], "). \nBut then ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"x", " ", FormBox[\(\(\((\[Rho]\ \[Union] \ \[Sigma])\)\^*\)\(\ \)\), "TraditionalForm"], " ", "u"}], " "}], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ RowBox[{" ", FormBox[ RowBox[{"u", " ", FormBox[\(\(\((\[Rho]\ \[Union] \ \[Sigma])\)\^*\)\(\ \)\), "TraditionalForm"], "z"}], "TraditionalForm"]}], TraditionalForm]]], ", and, by transitivity, ", Cell[BoxData[ FormBox[ RowBox[{"x", " ", FormBox[\(\(\((\[Rho]\ \[Union] \ \[Sigma])\)\^*\)\(\ \)\), "TraditionalForm"], " ", "z"}], TraditionalForm]]], ". \nBy IH, ", Cell[BoxData[ FormBox[ RowBox[{"z", " ", FormBox[\(\(\((\[Rho]\ \[Union] \ \[Sigma])\)\^*\)\(\ \)\), "TraditionalForm"], "y"}], TraditionalForm]]], ", and again by transitivity, ", Cell[BoxData[ FormBox[ RowBox[{" ", FormBox[ RowBox[{"x", " ", FormBox[\(\(\((\[Rho]\ \[Union] \ \[Sigma])\)\^*\)\(\ \)\), "TraditionalForm"], " ", "y"}], "TraditionalForm"]}], TraditionalForm]]], ".\n\nHello? " }], "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Relations on [4]", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:62"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", CellTags->"c:63"], Cell[TextData[{ "We have seen that binary relations on a finite set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " of cardinality ", Cell[BoxData[ \(TraditionalForm\`n\)]], " can be conveniently represented as Boolean ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(n\)\)\)]], " by ", Cell[BoxData[ \(TraditionalForm\`n\)]], " matrices. We have also seen how to use matrix operations to manipulate \ these matrices in various ways. For example, matrix multiplication can be \ used to represent relational composition. Likewise, one can write functions \ that test properties of a relation by testing corresponding properties of the \ matrix. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:64"], Cell[TextData[{ "(a) Generate a list of all relations on ", Cell[BoxData[ \(TraditionalForm\`A\ = \ \(\(\([\)\(4\)\(]\)\)\ = \ {1, 2, 3, 4}\)\)]], ", represented by Boolean matrices.\n(b) Use your list to count the number \ of \n\t- reflexive\n\t- symmetric\n\t- transitive \n relations on ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". \n (c) Try to come up with general formulas for these counts for ", Cell[BoxData[ \(TraditionalForm\`\(\([\)\(n\)\(]\)\)\)]], " , but only for reflexive and symmetric relations (transitive is much \ harder). " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Hints", "Subsubsection", CellTags->"c:65"], Cell[TextData[{ "Make sure that the macro package is properly loaded before you start \ computing. \nYou can use ", StyleBox["CartesianProduct", "Input"], " or ", StyleBox["IntegerDigits", "Input"], " to produce a list of all binary lists of a given length. Then convert \ those binary lists into binary (aka Boolean) matrices. \nThen concoct test \ functions that test for the various properties.\nDo not use real Boolean \ matrices with ", StyleBox["True", "Input"], " and ", StyleBox["False", "Input"], " entries, the macros listed below expect binary input. \n\n", StyleBox["You should expect the transitivity test to take around 1 minute \ or so. ", FontColor->RGBColor[1, 0, 0]] }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Commands", "Subsubsection", CellTags->"c:66"], Cell[TextData[{ StyleBox[" ", FontWeight->"Bold"], ButtonBox["IntegerDigits", ButtonStyle->"RefGuideLink"], StyleBox[", ", FontFamily->"Courier"], StyleBox[" ", FontWeight->"Bold"], ButtonBox["Partition", ButtonStyle->"RefGuideLink"], StyleBox[", ", FontFamily->"Courier"], ButtonBox["Length", ButtonStyle->"RefGuideLink"], StyleBox[", ", FontFamily->"Courier"], ButtonBox["Select", ButtonStyle->"RefGuideLink"], StyleBox[", ", FontFamily->"Courier"], StyleBox[" ", FontWeight->"Bold"], ButtonBox["Transpose", ButtonStyle->"RefGuideLink"], StyleBox[", ", FontFamily->"Courier"], StyleBox[" ", FontWeight->"Bold"], ButtonBox["Part", ButtonStyle->"RefGuideLink"], StyleBox[".\n\n", FontFamily->"Courier"], "The following are defined in the macro package:\n", StyleBox["\nCartesianProduct, BooleanIntersection, BooleanComplement, \ BooleanPower, BooleanComposition, BooleanUnion, BooleanConverse, \ TransitiveClosure.", FontFamily->"Courier"] }], "Text"], Cell["\<\ These do not have Help Browser entries (at present), but you can \ get some help using the ? command:\ \>", "Text"], Cell[BoxData[ \(\(?CartesianProduct\)\)], "Input"], Cell[BoxData[ \(\(?TransitiveClosure\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", CellTags->"c:67"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:68"], Cell["\<\ There are several ways this problem can be tackled, here is perhaps \ the easiest one. First, we produce a list of all binary lists of length 16. \ \ \>", "Text"], Cell["L = IntegerDigits[ Range[0,2^16-1],2,16];", "Input"], Cell["\<\ We use Partition to transform the lists into 3 by 3 matrices.\ \>", \ "Text"], Cell["LL = Map[ Partition[#,4]&, L ];", "Input"], Cell["Check:", "Text"], Cell["LL[[55]] // MatrixForm", "Input"], Cell["LL[[555]] // MatrixForm", "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:69"], Cell[TextData[{ "Now we need test functions for reflexivity, symmetry and transitivity. \n\n\ The second one is a disgusting hack. Unless you are a ", StyleBox["Mathematica", FontSlant->"Italic"], " expert your code will look different for reflexivity testing. Look up ", ButtonBox["Transpose", ButtonStyle->"RefGuideLink"], " in the help browser, see if you can figure out what's going on. " }], "Text"], Cell["\<\ testsym[R_] := Transpose[R]==R; testref[R_] := Transpose[R,{1,1}]=={1,1,1,1}; testtra[R_] := BooleanUnion[BooleanComposition[R,R],R]==R;\ \>", "Input"], Cell["Select the good matrices, and count:", "Text"], Cell["\<\ Select[ LL, testsym ] // Length // Timing Select[ LL, testref ] // Length // Timing Select[ LL, testtra ] // Length // Timing\ \>", "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:70"], Cell["\<\ To count the number of relations in general, it is best to think \ about the corresponding Boolean matrices. \ \>", "Text"], Cell[TextData[{ "A relation is reflexive iff all the diagonal entries in the matrix are 1. \ Hence, there remain ", Cell[BoxData[ \(TraditionalForm\`n\^\(\(\ \)\(2\)\) - n = n(n - 1)\)]], " entries that can be chosen arbitrarily. Thus, the total number of \ reflexive relations on ", Cell[BoxData[ \(TraditionalForm\`\(\([\)\(n\)\(]\)\)\)]], " is ", Cell[BoxData[ \(TraditionalForm\`2\^\(\(\ \)\(n(n - 1)\)\)\)]], ". " }], "Text"], Cell[TextData[{ "A relation is symmetric iff the matrix is symmetric. Hence, we can \ choose the ", Cell[BoxData[ \(TraditionalForm\`\(n(n + 1)\)/2\)]], " entries below or on the diagonal. The total number of reflexive \ relations on ", Cell[BoxData[ \(TraditionalForm\`\(\([\)\(n\)\(]\)\)\)]], " is ", Cell[BoxData[ \(TraditionalForm\`2\^\(\(\ \)\(\(n(n + 1)\)/2\)\)\)]], ". " }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Closures And Equivalences", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:71"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", Evaluatable->False, CellTags->"c:72"], Cell[TextData[{ "The transitive closure ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^+\)\)]], " is an equivalence relation provided that \[Rho] is already reflexive and \ symmetric. The following examples shows that we may get an equvilance \ relation even if \[Rho] is far from reflexive or symmetric. \nConsider as \ carrier set all binary lists of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". Define a relation \[Rho] as follows:\n\n\t", Cell[BoxData[ \(TraditionalForm\`L\ \[Rho]\ K\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`L\)]], " is the cyclic left-shift of ", Cell[BoxData[ \(TraditionalForm\`K\)]], ". \n\t\nIt is easy to visualize this in Mathematica, at least for small \ values of ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". \n" }], "Text", Evaluatable->False], Cell[BoxData[{ \(A = Tuples[2, 6] - 1; \), "\n", \(rho[L_List, K_List] := L \[Equal] RotateLeft[K]; \), "\n", \(\(R = RelationToMatrix[A, rho];\)\), "\n", \(\(PlotMatrix[R];\)\)}], "Input"], Cell[BoxData[{ \(RR = TransitiveClosure[R]; \), "\n", \(PlotMatrix[RR]; \)}], "Input"], Cell["\<\ Note that it is easy to see that the closure is reflexive and \ symmetric, but transitivity itself is invisible. Let's take a look at the equivalence classes.\ \>", "Text"], Cell[BoxData[{ \(class = ToClasses[A, RR, Type \[Rule] Matrix]; \), "\n", \(Length /@ class\)}], "Input"], Cell["\<\ Note that all divisors of 6 appear. Could that be coincidence? Look at some of the classes.\ \>", "Text"], Cell[BoxData[{ \(class\[LeftDoubleBracket]1\[RightDoubleBracket]\), "\n", \(class\[LeftDoubleBracket]4\[RightDoubleBracket]\), "\n", \(class\[LeftDoubleBracket]\(-1\)\[RightDoubleBracket]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:73"], Cell[TextData[{ "(a) Show that the relation ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^+\)\)]], " from above is indeed reflexive and symmetric, for any ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". \n(b) Compute the equivalence classes for the concrete case ", Cell[BoxData[ \(TraditionalForm\`n = 6\)]], ". " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:74"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:75"], Cell[TextData[{ "Consider lists of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". Then ", Cell[BoxData[ \(TraditionalForm\`L\ \(\[Rho]\^\(\(\ \)\(n\)\)\) L\)]], ", so ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^\(\(\ \)\(n\)\)\)]], " and therefore ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^+\)\ is\ \(\(reflexive\)\(.\)\)\)]], "\n\nSymmetry is a bit harder to see: let ", Cell[BoxData[ FormBox[ RowBox[{" ", FormBox[\(L\ \[Rho]\ K\), "TraditionalForm"]}], TraditionalForm]]], ". Then ", Cell[BoxData[ FormBox[ RowBox[{" ", FormBox[\(K\ \(\[Rho]\^\(\(\ \)\(n - 1\)\)\) L\), "TraditionalForm"]}], TraditionalForm]]], ". Rotating to the right is the same as rotating to the left ", Cell[BoxData[ \(TraditionalForm\`n - 1\)]], " times. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:76"], Cell[TextData[{ "The equivalence classes are \"cyclic lists\". The number of cyclic lists \ associated with a given linear list depends strongly on the linear list. \ E.g., cyclic list (1,1,\[Ellipsis],1) has just one corresponding linear \ list. But (0,1,0,1,\[Ellipsis],0,1) has two: (0,1,0,1,\[Ellipsis],0,1) \ and (1,0,1,\[Ellipsis],0,1,0), assuming ", Cell[BoxData[ \(TraditionalForm\`n\)]], " is even.\nAnd (0,0,1,0,0,1,\[Ellipsis],0,1) has three: (0,0,1,0,0,1,\ \[Ellipsis],0,1) and (0,1,0,0,1,\[Ellipsis],0,1,0) and (1,0,0,1,\ \[Ellipsis],0,1,0,0), assuming ", Cell[BoxData[ \(TraditionalForm\`n\)]], " is divisible by 3.\n\nIn general, whenever ", Cell[BoxData[ \(TraditionalForm\`d\)]], " divides ", Cell[BoxData[ \(TraditionalForm\`n\)]], ", we can produce a cyclic list that is associated with exactly ", Cell[BoxData[ \(TraditionalForm\`d\)]], " linear lists. More work shows that this is if and only if. \n\nAt any \ rate, for ", Cell[BoxData[ \(TraditionalForm\`{0, 1}\^\(\(\ \)\(8\)\)\)]], " the 128 lists are grouped as follows:\n\n" }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Classifying Functions (20 pts)", "Section", Evaluatable->False, PageBreakAbove->True, AspectRatioFixed->True, CellTags->"c:77"], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:78"], Cell[TextData[{ "For each of the following well-known functions from calculus, determine \ whether the function is injective and/or surjective. In each case, the \ codomain is ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalR]\)]], ", but the domain may be a proper subset of ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalR]\)]], ". \n\na) ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ 1/x\)]], "\nb) ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ sin(x)\)]], "\nc) ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ tan(x)\)]], "\nd) ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ e\^\(\(\ \)\(x\)\)\)]], "\ne) ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ log(x)\)]], "\nf) ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x\^\(\(\ \)\(5\)\)\)]], "\ng) ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x\^\(\(\ \)\(3\)\) - \ x\)]], "\n\nMake sure to a give a reason for your answer, but feel free to use any \ tool from calculus you like (e.g., derivatives are fair game). " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", FontColor->RGBColor[0, 0, 1], CellTags->"c:79"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:80"], Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ 1/x\)]], " is a hyperbola. It is clearly injective: ", Cell[BoxData[ \(TraditionalForm\`1/x\ = \ \(1/y\ \[Implies] \ x\ = \ y\)\)]], " but not surjective: 0 is not in the range. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:81"], Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ sin(x)\)]], " is not injective: ", Cell[BoxData[ \(TraditionalForm\`sin(0)\ = \ \(0\ = \ sin(2 \[Pi])\)\)]], ". Also, ", Cell[BoxData[ \(TraditionalForm\`\(-1\)\ \[LessEqual] \ sin(x)\ \[LessEqual] \ 1\)]], ", so the function is not surjective. " }], "Text"], Cell[BoxData[ \(Plot[Sin[x], {x, \(-2\)\ \[Pi], 2\ \[Pi]}]; \)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:82"], Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ tan(x)\)]], " is not injective: ", Cell[BoxData[ \(TraditionalForm\`tan(0)\ = \ \(0\ = \ tan(2 \[Pi])\)\)]], ". But, the function is surjective. Indeed, ", Cell[BoxData[ FormBox[ RowBox[{\(tan \((\((\(-\[Pi]\), \[Pi])\))\)\), "=", " ", RowBox[{"\[DoubleStruckCapitalR]", Cell[""]}]}], TraditionalForm]]], ". " }], "Text"], Cell[BoxData[ \(\(Plot[\ Tan[x], \ {x, \(-2\) Pi, 2 Pi}\ ];\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Part d", "Subsubsection", CellTags->"c:83"], Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ e\^\(\(\ \)\(x\)\)\)]], " is injective: since ", Cell[BoxData[ \(TraditionalForm\`\(f\^\[Prime]\)(x)\ = \ f(x)\ > \ 0\)]], " the function is strictly increasing. But, the function is not \ surjective, its range is ", Cell[BoxData[ \(TraditionalForm\`\(\[DoubleStruckCapitalR]\^+\)\)]], ". ", Cell[BoxData[ FormBox[Cell[""], TraditionalForm]]] }], "Text"], Cell[BoxData[ \(Plot[\[ExponentialE]\^x, {x, \(-2\), 2}]; \)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Part e", "Subsubsection", CellTags->"c:84"], Cell[TextData[{ "For rationals, first consider ", Cell[BoxData[ \(TraditionalForm\`x = \ 1/n\)]], ". \nWe have ", Cell[BoxData[ \(TraditionalForm\`f(1)\ = \ \(f(n\ \[CenterDot]\ 1/n)\ = \ n\ \(f(1/n)\)\)\)]], ", so that ", Cell[BoxData[ \(TraditionalForm\`f(1/n) = \(f(1)\)/n\)]], ". \nTogether with part a) this implies\nAlso, ", Cell[BoxData[ \(TraditionalForm\`f( a/b)\ \ = \ \(f(a\ \[CenterDot]\ 1/b)\ = \ \(a\ \(f(1/b)\)\ = a/b\ \ \(f(1)\)\)\)\)]], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part f", "Subsubsection", CellTags->"c:85"], Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x\^\(\(\ \)\(5\)\)\)]], " is injective: since ", Cell[BoxData[ \(TraditionalForm\`\(f\^\[Prime]\)(x)\ = \ x\^\(\(\ \)\(4\)\)\ \[GreaterEqual] \ 0\)]], " the function is strictly increasing (careful with ", Cell[BoxData[ \(TraditionalForm\`x = 0\)]], "). Furthermore, it is surjective since every non-negative real number has \ a real 5th root, and the function is symmetric around the origin: ", Cell[BoxData[ \(TraditionalForm\`f(\(-x\))\ = \ \(-\(f(x)\)\)\)]], ". ", Cell[BoxData[ FormBox[Cell[""], TraditionalForm]]] }], "Text"], Cell[BoxData[ \(Plot[x\^5, {x, \(-1\), 1}]; \)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Part g", "Subsubsection", CellTags->"c:86"], Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x\^\(\(\ \)\(3\)\) - x\)]], " is not injective: since ", Cell[BoxData[ \(TraditionalForm\`f(0)\ = \ \(0\ = \ f(1)\)\)]], ". The function is continuous, and has \n", Cell[BoxData[ \(TraditionalForm\`lim\_\(x \[Rule] \[Infinity]\)f( x)\ = \ \[Infinity]\)]], " but ", Cell[BoxData[ \(TraditionalForm\`lim\_\(x \[Rule] \(-\[Infinity]\)\)f( x)\ = \ \(-\[Infinity]\)\)]], ". By the Mean Value Theorem, it must be surjective. \n\nThis is a whole \ lot easier than trying to argue algebraically that the equation ", Cell[BoxData[ \(TraditionalForm\`\(\(x\^3\)\(-\)\(x\)\(\ \)\) = \ a\)]], " has a solution for each real number ", Cell[BoxData[ \(TraditionalForm\`a\)]], ". ", Cell[BoxData[ FormBox[Cell[""], TraditionalForm]]] }], "Text"], Cell[BoxData[ \(Plot[x\^3 - x, {x, \(-2\), 2}]; \)], "Input"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Composition and In/surjectivity", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:87"], Cell[CellGroupData[{ Cell["Task:", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, Background->GrayLevel[1], CellTags->"c:88"], Cell[TextData[{ "Consider functions ", Cell[BoxData[ \(TraditionalForm\`\(\(\(f\ : \ A\)\(\ \)\)\(\[Rule]\)\(\ \)\(B\)\(\ \)\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`g : \ B \[Rule] \ C\)]], ". Let ", Cell[BoxData[ \(TraditionalForm\`h\ = \ g\ \[SmallCircle]\ f\)]], " be their composition. \nFor each of the following statements, give a \ proof or a counterexample.\nMake sure that your proofs and/or counterexamples \ are crisp and clear. \n\n(a) ", Cell[BoxData[ \(TraditionalForm\`h\)]], " injective implies ", Cell[BoxData[ \(TraditionalForm\`f\)]], " injective.\n(b) ", Cell[BoxData[ \(TraditionalForm\`h\)]], " injective implies ", Cell[BoxData[ \(TraditionalForm\`g\)]], " injective.\n(c) ", Cell[BoxData[ \(TraditionalForm\`h\)]], " surjective implies ", Cell[BoxData[ \(TraditionalForm\`f\)]], " surjective.\n(d) ", Cell[BoxData[ \(TraditionalForm\`h\)]], " surjective implies ", Cell[BoxData[ \(TraditionalForm\`g\)]], " surjective." }], "Text", Evaluatable->False, AspectRatioFixed->True, Background->GrayLevel[1]] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, AspectRatioFixed->True, FontFamily->"Times", FontSize->18, CellTags->"c:89"], Cell[TextData[{ "a) True. \nIf ", Cell[BoxData[ \(TraditionalForm\`f(a)\ = \ f(b)\)]], ", then ", Cell[BoxData[ \(TraditionalForm\`h(a)\ = \ h(b)\)]], ", so ", Cell[BoxData[ \(TraditionalForm\`f\)]], " must be injective whenever ", Cell[BoxData[ \(TraditionalForm\`h\)]], " is. \n\nb) False.\nLet ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\([\)\(1\)\(]\)\)\ \[LongRightArrow]\ \ \(\([\)\(2\)\(]\)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`g\ : \ \(\([\)\(2\)\(]\)\)\ \[LongRightArrow]\ \ \(\([\)\(1\)\(]\)\)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`f(1) = 1\)]], ", ", Cell[BoxData[ \(TraditionalForm\`g(1) = \(g(2) = 1\)\)]], ". \n", Cell[BoxData[ \(TraditionalForm\`h\)]], " is injective, but ", Cell[BoxData[ \(TraditionalForm\`g\)]], " is not.\n\nc) False.\nSame counterexample as for b): ", Cell[BoxData[ \(TraditionalForm\`h\)]], " is surjective, but ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is not. \n\nd) True. \nLet ", Cell[BoxData[ \(TraditionalForm\`c\ \[Element] C\)]], ". Since ", Cell[BoxData[ \(TraditionalForm\`h\)]], " is surjective, we must have ", Cell[BoxData[ \(TraditionalForm\`c\ = \ \(h(a)\ = \ g(f(a))\)\)]], ". Hence ", Cell[BoxData[ \(TraditionalForm\`g\)]], " is surjective. " }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Characterizing Surjectivity", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:90"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", Evaluatable->False, CellTags->"c:91"], Cell[TextData[{ "In class, you saw a four different ways of describing injective \ functions. Here is the counterpart for surjectivity. \n\nYou might find it \ expedient on occasion to write ", Cell[BoxData[ \(TraditionalForm\`x\ f\ y\)]], " rather than ", Cell[BoxData[ \(TraditionalForm\`f(x) = y\)]], ". " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:92"], Cell[TextData[{ "Show that the following are equivalent. \n\n(a) A function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ A\ \ \[LongRightArrow]\ B\)]], " is surjective. \n\n(b) ", Cell[BoxData[ \(TraditionalForm\`I\_\(\(\ \)\(B\)\)\ \[SubsetEqual] \ \(\(f\^\(\(\ \ \)\(c\)\)\)\(\ \)\) \[Bullet]\ f \(\(\ \)\(\ \)\)\)]], "\n\n(c) ", Cell[BoxData[ \(TraditionalForm\`\[Exists] \ \(F\ \ : \ B\ \[LongRightArrow]\ A\ \ \((\ \ \ f\ \[SmallCircle]\ F\ = \ I\_\(\(B\)\(\ \)\))\)\)\)]], "\n\n(d) ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ g, h\ : \ B\ \[LongRightArrow]\ C\ \ \((\ \ \ g\ \[SmallCircle]\ f\ = \ \(h\ \[SmallCircle]\ f\ \[DoubleLongRightArrow]\ g\ = \ h\)\ )\)\)]] }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:93"], Cell[CellGroupData[{ Cell["a \[Implies] b", "Subsubsection", CellTags->"c:94"], Cell[TextData[{ "Since ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is surjective, for any ", Cell[BoxData[ \(TraditionalForm\`y\ \[Element] \ B\)]], " there is an ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ A\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`f(x) = y\)]], ". \nBut then ", Cell[BoxData[ \(TraditionalForm\`y\ \(f\^\(\(c\)\(\ \)\)\) x\)]], " and it follows that ", Cell[BoxData[ \(TraditionalForm\`\(\(\(y\)\(\ \)\) \((\ \(f\^c\) \[Bullet]\ f)\) \(\(\ \ \)\(\ \)\) \(y\)\(\ \)\)\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["b \[Implies] c", "Subsubsection", CellTags->"c:95"], Cell[TextData[{ "We need to define ", Cell[BoxData[ \(TraditionalForm\`F\)]], ". Let ", Cell[BoxData[ \(TraditionalForm\`y\ \[Element] \ B\)]], " arbitrary. \nBy our assumption there is an ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ A\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`y\ f\^\(\(\ \)\(c\)\)\ x\ f\ y\)]], ". \nThe problem is that this witness ", Cell[BoxData[ \(TraditionalForm\`x\)]], " may not be unique.\nSo, for any ", Cell[BoxData[ \(TraditionalForm\`y\ \[Element] \ B\)]], ", consider ", Cell[BoxData[ \(TraditionalForm\`A\_\(\(y\)\(\ \)\)\ = \ \(f\^\(-1\)\)(\ {y})\ \ \[NotEqual] \ \[EmptySet]\)]], ". \nChoose one element ", Cell[BoxData[ \(TraditionalForm\`a\_\(\(y\)\(\ \)\) \[Element] \ A\_y\)]], " for each ", Cell[BoxData[ \(TraditionalForm\`y\)]], ", and set ", Cell[BoxData[ \(TraditionalForm\`F(y) = a\_y\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["c \[Implies] d", "Subsubsection", CellTags->"c:96"], Cell[TextData[{ "Suppose ", Cell[BoxData[ FormBox[ RowBox[{" ", FormBox[\(\(\ \)\(g\ \[SmallCircle]\ f\ = \ h\ \[SmallCircle]\ f\)\), "TraditionalForm"]}], TraditionalForm]]], ". \n\nComposing with ", Cell[BoxData[ \(TraditionalForm\`F\)]], ", we get (composition is associative)\n\n\t", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(g\ \[SmallCircle]\ f\ \[SmallCircle]\ F\ = \ h\ \[SmallCircle]\ f\ \[SmallCircle]\ F\)\)\)]], " \n\t\nand therefore\n\t", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(g\ \[SmallCircle]\ I\_B\ = \ h\ \[SmallCircle]\ I\_B\)\)\)]], " \n\t\nand ", Cell[BoxData[ \(TraditionalForm\`g = h\)]], " follows immediately. \n" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["d \[Implies] a", "Subsubsection", CellTags->"c:97"], Cell[TextData[{ "Suppose ", Cell[BoxData[ \(TraditionalForm\`y\ \[Element] \ B\)]], ". \nLet ", Cell[BoxData[ \(TraditionalForm\`C = \ {0, 1}\)]], " and define ", Cell[BoxData[ \(TraditionalForm\`g, h : \ B\ \[LongRightArrow]\ C\)]], " by\n", Cell[BoxData[ \(TraditionalForm\`g(z)\ = \ 0\)]], " for all ", Cell[BoxData[ \(TraditionalForm\`z\ \[Element] \ B\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(\(\(h(z)\)\(\ \)\)\(=\)\(\ \)\(0\)\(\ \)\)\)]], " for all ", Cell[BoxData[ \(TraditionalForm\`z \[NotEqual] \ y\)]], ", but ", Cell[BoxData[ \(TraditionalForm\`h(y) = 1\)]], ". \nHence, ", Cell[BoxData[ \(TraditionalForm\`g \[NotEqual] h\)]], ". \nBut then ", Cell[BoxData[ \(TraditionalForm\`y\)]], " must be in the range of ", Cell[BoxData[ \(TraditionalForm\`f\)]], ", for otherwise ", Cell[BoxData[ \(TraditionalForm\`g\[SmallCircle]f = h\[SmallCircle]f\)]], ", \nwhich implies that ", Cell[BoxData[ \(TraditionalForm\`g = h\)]], ". " }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Inverse Functions", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:98"], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:99"], Cell[TextData[{ "For each of the following functions, find their inverse.\n\n(a) ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalR]\ \ \[LongRightArrow]\ \ \[DoubleStruckCapitalR]\^\(\(\ \)\(+\)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ e\^\(\(\ \)\(x\)\)\)]], "\n\n(b) ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \((\(-\[Pi]\)/2, \[Pi]/ 2)\)\ \ \[LongRightArrow]\ \[DoubleStruckCapitalR]\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ tan\ x\)]], "\n\n(c) ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalR]\ \ \[LongRightArrow]\ \ \[DoubleStruckCapitalR]\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x\^3\ + \ 1\)]] }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:100"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:101"], Cell[TextData[Cell[BoxData[ \(TraditionalForm\`g(y)\ = \ ln\ y\)]]], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:102"], Cell[TextData[Cell[BoxData[ \(TraditionalForm\`g( y)\ = \ \(\(\(arctan\)\(\ \)\) \(y\)\(\ \)\)\)]]], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:103"], Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`g( y)\ = \ \((y - 1)\)\^\(\(\(\ \)\(1/3\)\)\(\ \)\)\)]], " for ", Cell[BoxData[ \(TraditionalForm\`y\ \[GreaterEqual] \ 1\)]], "\n", Cell[BoxData[ \(TraditionalForm\`\(\(\(g( y)\)\(\ \)\)\(=\)\(\ \)\(-\((1 - y)\)\^\(\(\ \)\(1/3\)\)\)\(\ \ \)\)\)]], " for ", Cell[BoxData[ \(TraditionalForm\`y\ < \ 1\)]] }], "Text"], Cell["Plot[ If[z>=1,(z-1)^(1/3),-(1-z)^(1/3)], {z,-1,2} ];", "Input"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Decomposition", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:104"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", Evaluatable->False, CellTags->"c:105"], Cell[TextData[{ "We have shown that any function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ A\ \[LongRightArrow]\ B\)]], " can be decomposed into a surjective and an injective part in the sense \ that there are functions ", Cell[BoxData[ \(TraditionalForm\`g\ : \ A\[LongRightArrow]\ C\)]], " and ", Cell[BoxData[ \(TraditionalForm\`h\ : \ C\ \[LongRightArrow]\ B\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`f\ = \ h\ \[SmallCircle]\ g\)]], ", ", Cell[BoxData[ \(TraditionalForm\`g\)]], " is surjective, and ", Cell[BoxData[ \(TraditionalForm\`h\)]], " is injective. The proof of this result is constructive, it provides a \ complete definition of the two functions. However, in a concrete situation \ it may still be a bit difficult to figure out what ", Cell[BoxData[ \(TraditionalForm\`g\)]], " and ", Cell[BoxData[ \(TraditionalForm\`h\)]], " are. Here is an example from calculus. " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:106"], Cell[TextData[{ "Decompose the following functions into a surjective and an injective part. \ Use the method introuduced in class.\n\n(a) ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalR]\ \ \[LongRightArrow]\ \ \[DoubleStruckCapitalR]\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ sin\ x\)]], "\n\n(b) ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalR]\ \ \[LongRightArrow]\ \ \[DoubleStruckCapitalR]\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ \((\ x\^\(\(\ \)\(2\)\)\ - \ 2\ x\ )\)\)]] }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Hint", "Subsubsection", Evaluatable->False, CellTags->"c:107"], Cell[TextData[{ "You might find it helpful to plot the functions just to make sure your \ intuition is on target, see ", ButtonBox["Plot", ButtonStyle->"RefGuideLink"], ". " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:108"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:109"], Cell["\<\ Plot a picture of the sin function so one can read off the \ equivalence classes:\ \>", "Text"], Cell["Plot[ Sin[x], {x,-8,8} ];", "Input"], Cell[TextData[{ "The part from ", Cell[BoxData[ \(TraditionalForm\`\(-\[Pi]\)/2\)]], " to ", Cell[BoxData[ \(TraditionalForm\`\[Pi]/2\)]], " is injective, and the range of values is already ", Cell[BoxData[ \(TraditionalForm\`\(\([\)\(\(-1\), 1\)\(]\)\)\)]], ", so for any ", Cell[BoxData[ \(TraditionalForm\`x\)]], " there must be a ", Cell[BoxData[ \(TraditionalForm\`z\ \[Element] \ \(\([\)\(\(-\[Pi]\)/2, \[Pi]/ 2\)\(]\)\)\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`sin\ x\ = \ sin\ z\)]], ". But it is a little tricky to write down the correspondence.\n\nThe easy \ part is ", Cell[BoxData[ \(TraditionalForm\`sin\ x\ = \ \(\(\(sin\)\(\ \)\) \((\ x\ + \ 2 k\ \[Pi]\ )\)\(\ \)\)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`k\)]], " is any integer, ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ \(\([\)\(\(-\[Pi]\)/2, \[Pi]/ 2\)\(]\)\)\)]], " .\nThe other part is ", Cell[BoxData[ \(TraditionalForm\`sin\ x\ = \ \(\(\(sin\)\(\ \)\) \((\ \(-x\)\ + \ \ \((2 k + 1)\) \[Pi]\ )\)\(\ \)\)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`k\)]], " is any integer.\nThe equivalence classes are \n\n\t", Cell[BoxData[ \(TraditionalForm\`\(\({\ x\ + \ 2\ k\ \[Pi]\ \ | \ \(k\ \[Element] \ \ \[DoubleStruckCapitalZ]\)\ }\)\(\ \)\) \[Union] {\ \(-x\)\ + \ \((2 k + 1)\)\ \[Pi]\ \ | \ \(k\ \[Element] \ \ \[DoubleStruckCapitalZ]\)\ } \(\(\ \)\(\ \)\(\ \)\)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ \ \(\([\)\(\(-\[Pi]\)/2, \[Pi]/ 2\)\(]\)\)\)]], ". \n\t\nHence, we can set\n\n\t", Cell[BoxData[ \(TraditionalForm\`g\ : \ \[DoubleStruckCapitalR]\ \[LongRightArrow]\ \ \ \(\([\)\(\(-\[Pi]\)/2, \[Pi]/2\)\(]\)\)\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`\(\(\(g(x)\)\(\ \)\)\(=\)\(\ \)\(z\)\(\ \)\)\)]], " iff \n\t\t ", Cell[BoxData[ \(TraditionalForm\`\[Exists] \ k\ \[Element] \ \[DoubleStruckCapitalZ]\)]], ", ", Cell[BoxData[ \(TraditionalForm\`z\ \[Element] \ \ \(\([\)\(\(-\[Pi]\)/2, \[Pi]/ 2\)\(]\)\)\)]], " ( ", Cell[BoxData[ \(TraditionalForm\`z - x = \ 2 k\ \[Pi]\)]], " \[Or] ", Cell[BoxData[ \(TraditionalForm\`z + x = \ \((2 k + 1)\)\ \[Pi]\)]], " ) \n\t\n\t\nThe second function is \n\n\t", Cell[BoxData[ \(TraditionalForm\`h\ : \(\([\)\(\(-\[Pi]\)/2, \[Pi]/ 2\)\(]\)\)\ \[LongRightArrow]\ \[DoubleStruckCapitalR]\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`g(z)\ = sin\ z\)]], ". \n" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:110"], Cell["Look at a plot to see what the equivalence classes are:", "Text"], Cell["Plot[ x^2 - 2 x, {x,-1,3} ];", "Input"], Cell[TextData[{ "For ", Cell[BoxData[ \(TraditionalForm\`u \[NotEqual] \ v\)]], ", we have ", Cell[BoxData[ \(TraditionalForm\`f(u)\ = \ f(v)\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(\ \)\) \(\(u + v\)\(|\)\)\ = \ 2\)]], ". \nIn fact, assuming ", Cell[BoxData[ \(TraditionalForm\`u < v\)]], " we get ", Cell[BoxData[ \(TraditionalForm\`f(u)\ = \ f(v)\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\(\(u\)\(\ \)\(+\)\(\ \)\(v\)\(\ \)\) = \ 2\)]], ". \nNote that the global minimum is at ", Cell[BoxData[ \(TraditionalForm\`\((1, \(-1\))\)\)]], ". \n" }], "Text"], Cell[TextData[{ "Hence, we can set\n\n\t", Cell[BoxData[ \(TraditionalForm\`g\ : \ \[DoubleStruckCapitalR]\ \[LongRightArrow]\ \ \(\(\([\)\(\(-1\), \[Infinity]\)\)\()\)\)\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`\(\(\(g( x)\)\(\ \)\)\(=\)\(\(\ \)\(\ \)\) \(x\)\(\ \)\)\)]], " for ", Cell[BoxData[ \(TraditionalForm\`1\ \[LessEqual] \ x\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`g(x)\ = \ \ \(\(2\)\(-\)\(x\)\(\ \)\)\)]], " for ", Cell[BoxData[ \(TraditionalForm\`1\ \[LessEqual] \ x\)]], "\n\t\nand \n\n\t", Cell[BoxData[ \(TraditionalForm\`h\ : \(\(\([\)\(\(-1\), \[Infinity]\)\)\()\)\)\ \ \[LongRightArrow]\ \[DoubleStruckCapitalR]\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`h(u)\ = u\^\(\(\ \)\(2\)\) - 2 u\)]], ". \n\t\nLet's try this out:" }], "Text"], Cell["\<\ Clear[f,g,h] f[x_] := x^2 - 2 x; g[x_] := x /; 1 <= x; g[x_] := 2-x; h[x_] := x^2 - 2 x;\ \>", "Input"], Cell["\<\ Plot[ {f[x],h[g[x]],g[x]}, {x,-1,3}, PlotStyle->{Blue,Red,Green} ];\ \ \>", "Input"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Relations on Lists", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->{"relation", "c:111"}], Cell[CellGroupData[{ Cell["Background", "Subsubsection", CellTags->"c:112"], Cell[TextData[{ "Let ", Cell[BoxData[ \(TraditionalForm\`B(n)\)]], " denote all binary lists of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". Fix ", Cell[BoxData[ \(TraditionalForm\`n\)]], ", and define the following two relations on ", Cell[BoxData[ \(TraditionalForm\`B(n)\)]], ".\n\n- ", Cell[BoxData[ \(TraditionalForm\`K\ \[Rho]\ L\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`L\)]], " can be rotated to obtain ", Cell[BoxData[ \(TraditionalForm\`K\)]], ": \n\t", Cell[BoxData[ \(TraditionalForm\`\[Exists] \ i, \ 0\ \[LessEqual] \ i\ < \ n\ \ \((\ \ K\ = \ RotateLeft[\ L, \ i\ ]\ )\)\)]], "\n\n- ", Cell[BoxData[ \(TraditionalForm\`K\ \[Sigma]\ L\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`K\)]], " is bitwise no greater than ", Cell[BoxData[ \(TraditionalForm\`L\)]], ": ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ i\ = \ 1, \[Ellipsis], n\ \((\ \ K\[LeftDoubleBracket]i\[RightDoubleBracket]\ \[LessEqual] \ L\[LeftDoubleBracket]i\[RightDoubleBracket]\ )\)\)]] }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:113"], Cell[TextData[{ "a)Show that \[Rho] is an equivalence relation on ", Cell[BoxData[ \(TraditionalForm\`B(n)\)]], ".\n\nb) For ", Cell[BoxData[ \(TraditionalForm\`n \[LessEqual] \ 11\)]], ", determine all the equivalence classes. \nAny observations? (No proofs \ required). \n\nc) Show that \[Sigma] is a partial order on ", Cell[BoxData[ \(TraditionalForm\`B(n)\)]], ".\n\nd) Explain what the meaning of ", Cell[BoxData[ \(TraditionalForm\`K\ \[Sigma]\ L\)]], " is if one thinks of an element of ", Cell[BoxData[ \(TraditionalForm\`B(n)\)]], " as a bit-vector of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:114"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:115"], Cell[TextData[{ "To see that R is an equivalence relation, we have to verify the following \ three properties. \n- Reflexivity: \[Rho] is reflexive since ", Cell[BoxData[ \(TraditionalForm\`L\ = \ RotateLeft[L, 0]\)]], ".\n- Symmetry: \[Rho] is symmetric, since ", Cell[BoxData[ \(TraditionalForm\`K\ = \ RotateLeft[L, i]\)]], " implies\n\t ", Cell[BoxData[ \(TraditionalForm\`L\ = \ \(RotateLeft[\ K, \ \(-i\)\ ]\ = \ RotateLeft[\ K, \ n - i\ ]\)\)]], ".\n- Transitiviy: Suppose ", Cell[BoxData[ \(TraditionalForm\`K\ = \ RotateLeft[L, i]\)]], " and ", Cell[BoxData[ \(TraditionalForm\`L\ = \ RotateLeft[M, j]\)]], ". \nThen ", Cell[BoxData[ FormBox[Cell[TextData[Cell[BoxData[ \(TraditionalForm\`K\ = \ RotateLeft[\ M, \ i + j\ ]\)]]]], TraditionalForm]]], ", and if ", Cell[BoxData[ \(TraditionalForm\`\(\(i\)\(+\)\(j\)\(\ \)\) > \ n\)]], " we can replace it by ", Cell[BoxData[ \(TraditionalForm\`i + j - n\)]], ". " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:116"], Cell["\<\ Now for the equivalence classes. We will brute-force compute all \ the lists equivalent to a given one, do this for all lists, and the eliminate \ duplicates. This is not very elegant, but it works fine. Here is \ \>", "Text", Evaluatable->False], Cell[BoxData[{ \(Clear[B, class, classes]\), "\n", \(B[n_]\ := Distribute[Table[{0, 1}, {n}], List]; \), "\n", \(class[L_List] := \[IndentingNewLine]\t Union[\ \(RotateLeft[L, #] &\)\ /@ \ Range[Length[L]]]\)}], "Input"], Cell[BoxData[{ \(class[{1, 1, 1, 0, 0, 0, 0, 0}]\), "\n", \(class[{1, 1, 0, 0, 1, 1, 0, 0}]\)}], "Input"], Cell[BoxData[ \(classes[n_]\ := \ Union[\ Map[\ class, \ B[n]\ ]\ ]; \)], "Input"], Cell[TextData[{ "Here are the classes up to ", Cell[BoxData[ \(TraditionalForm\`n = 11\)]], ":" }], "Text"], Cell[BoxData[{ \(C\ = \ classes[1]\), "\n", \(Length[C]\), "\n", \(Length\ /@ \ C\)}], "Input"], Cell[BoxData[{ \(C\ = \ classes[2]\), "\n", \(Length[C]\), "\n", \(Length\ /@ \ C\)}], "Input"], Cell[BoxData[{ \(C\ = \ classes[3]\), "\n", \(Length[C]\), "\n", \(Length\ /@ \ C\)}], "Input"], Cell[BoxData[{ \(C\ = \ classes[4]\), "\n", \(Length[C]\), "\n", \(Length\ /@ \ C\)}], "Input"], Cell[BoxData[{ \(C\ = \ classes[5]; \), "\n", \(Length[C]\), "\n", \(Length\ /@ \ C\)}], "Input"], Cell[BoxData[{ \(C\ = \ classes[6]; \), "\n", \(Length[C]\), "\n", \(Length\ /@ \ C\)}], "Input"], Cell[BoxData[{ \(C\ = \ classes[7]; \), "\n", \(Length[C]\), "\n", \(Length\ /@ \ C\)}], "Input"], Cell[BoxData[{ \(C\ = \ classes[8]; \), "\n", \(Length[C]\), "\n", \(Length\ /@ \ C\)}], "Input"], Cell[BoxData[{ \(C\ = \ classes[9]; \), "\n", \(Length[C]\), "\n", \(Length\ /@ \ C\)}], "Input"], Cell[BoxData[{ \(C\ = \ classes[10]; \), "\n", \(Length[C]\), "\n", \(Length\ /@ \ C\)}], "Input"], Cell[BoxData[{ \(C\ = \ classes[11]; \), "\n", \(Length[C]\), "\n", \(Length\ /@ \ C\)}], "Input"], Cell[TextData[{ "Notice how the calculations slow down quite a bit. \n\nAt any rate, \ judging from the computational evidence, it looks like the sizes of the \ equivalence classes are precisely the divisors of ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". In particular for ", Cell[BoxData[ \(TraditionalForm\`n\)]], " prime we have two classes of size 1 (the constant 0 and constant 1 \ lists), all other classes have size ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". \n\nNote that this would imply ", Cell[BoxData[ \(TraditionalForm\`\(\(2\^\(\(\ \)\(p\)\)\)\(-\)\(2\)\(\ \)\)\)]], " is a multiple of ", Cell[BoxData[ \(TraditionalForm\`p\)]], ". We will see in a while that this is in fact true. Here is experimental \ verification." }], "Text"], Cell["\<\ p = Prime[10000] PowerMod[ 2, p, p ]\ \>", "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:117"], Cell[TextData[{ "Now for the second relation \[Sigma]. We have to check that \[Sigma] is \ reflexive, anti-symmetric, and transitive. But all these properties follow \ immediately from the fact that ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " is an order on ", Cell[BoxData[ \(TraditionalForm\`{0, 1}\)]], ". \[Sigma] is what is called a product order: it is the ", Cell[BoxData[ \(TraditionalForm\`n\)]], "-fold product of ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " on ", Cell[BoxData[ \(TraditionalForm\`{0, 1}\)]], " with itself. The same trick works for any order as starting point. \ However, unlike ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " the order \[Sigma] is no longer total: the lists ", Cell[BoxData[ \(TraditionalForm\`{1, 0, \[Ellipsis]}\)]], " and ", Cell[BoxData[ \(TraditionalForm\`{0, 1, \[Ellipsis]}\)]], " for example are not comparable. " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:118"], Cell[TextData[{ "If we think of ", Cell[BoxData[ \(TraditionalForm\`B(n)\)]], " as the set of all bit-vectors of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], ", i.e., the power set of ", Cell[BoxData[ \(TraditionalForm\`{1, 2, ... , n}\)]], ", then \[Sigma] is simply the subset relation: ", Cell[BoxData[ \(TraditionalForm\`L\ \[Sigma]\ K\)]], " iff the set (corresponding to) ", Cell[BoxData[ \(TraditionalForm\`L\)]], " is a subset of the set (corresponding to) ", Cell[BoxData[ \(TraditionalForm\`K\)]], ". " }], "Text", Evaluatable->False] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Three Relations on Lists", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->{"relation", "c:119"}], Cell[CellGroupData[{ Cell["Background", "Subsubsection", CellTags->"c:120"], Cell[TextData[{ "Let ", Cell[BoxData[ \(TraditionalForm\`B(n)\)]], " denote all binary lists of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], " and think of these lists as bit-vectors. With this interpretation in \ mind, define the following three relations on ", Cell[BoxData[ \(TraditionalForm\`B(n)\)]], ".\n\n- ", Cell[BoxData[ \(TraditionalForm\`K\ \[Rho]\ L\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`L\)]], " and ", Cell[BoxData[ \(TraditionalForm\`K\)]], " are disjoint: \n\t", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ i = \ 1, \[Ellipsis], n\ \ \((\ \ K\[LeftDoubleBracket]i\[RightDoubleBracket]\ + \ L\[LeftDoubleBracket]i\[RightDoubleBracket]\ \[LessEqual] \ 1\ )\)\)]], "\n\n- ", Cell[BoxData[ \(TraditionalForm\`K\ \[Sigma]\ L\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`L\)]], " and ", Cell[BoxData[ \(TraditionalForm\`K\)]], " are complementary: \n\t", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ i = \ 1, \[Ellipsis], n\ \ \((\ \ K\[LeftDoubleBracket]i\[RightDoubleBracket]\ + \ L\[LeftDoubleBracket]i\[RightDoubleBracket]\ \[GreaterEqual] \ 1\ )\)\)]], "\n\n- ", Cell[BoxData[ \(TraditionalForm\`K\ \[Tau]\ L\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`K\)]], " is bitwise no greater than ", Cell[BoxData[ \(TraditionalForm\`L\)]], ":\n\t ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ i\ = \ 1, \[Ellipsis], n\ \((\ \ K\[LeftDoubleBracket]i\[RightDoubleBracket]\ \[LessEqual] \ L\[LeftDoubleBracket]i\[RightDoubleBracket]\ )\)\)]], "\n\t \nHere are implementations of the relations, and a plot for lists of \ length 6." }], "Text", Evaluatable->False], Cell[BoxData[{ \(disjoint[L_, K_] := L . K \[Equal] 0; \), "\n", \(compl[L_, K_] := Union[Sign[L + K]] \[Equal] {1}; \), "\n", \(ListLessEqual[L_, K_] := And @@ Thread[L \[LessEqual] K]; \), "\n", \(lge[K_, L_] := ListLessEqual[L, K]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(B6 = Tuples[2, 6] - 1; \)], "Input"], Cell[BoxData[{ \(\(gr1 = PlotMatrix[RelationToMatrix[B6, disjoint], DisplayFunction \[Rule] Identity];\)\), "\n", \(\(gr2 = PlotMatrix[RelationToMatrix[B6, compl], DisplayFunction \[Rule] Identity];\)\), "\n", \(gr3 = PlotMatrix[RelationToMatrix[B6, ListLessEqual], DisplayFunction \[Rule] Identity]; gr4 = PlotMatrix[RelationToMatrix[B6, lge], DisplayFunction \[Rule] Identity];\)}], "Input"], Cell[BoxData[ \(\(gr\ = \ ShowArray[{gr3, gr4, gr1, gr2}];\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:121"], Cell[TextData[{ "a) Which of these relations are partial orders on ", Cell[BoxData[ \(TraditionalForm\`B(n)\)]], "?\nb) Explain the pictures in the background section." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:122"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:123"], Cell[TextData[{ "Claim: Only the third relation \[Tau] is a partial order. \n\nWe have to \ check that \[Tau] is reflexive, anti-symmetric, and transitive. But all \ these properties follow immediately from the fact that ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " is an order on ", Cell[BoxData[ \(TraditionalForm\`{0, 1}\)]], ". \[Tau] is what is called a product order: it is the ", Cell[BoxData[ \(TraditionalForm\`n\)]], "-fold product of ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " on ", Cell[BoxData[ \(TraditionalForm\`{0, 1}\)]], " with itself. The same trick works for any order as starting point. \ However, unlike ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " the order \[Tau] is no longer total: the lists ", Cell[BoxData[ \(TraditionalForm\`{1, 0, \[Ellipsis]}\)]], " and ", Cell[BoxData[ \(TraditionalForm\`{0, 1, \[Ellipsis]}\)]], " for example are not comparable. \n\nAs far as \[Rho] and \[Sigma] are \ concerned, note that neither of these relations are transitive. E.g., ", Cell[BoxData[ \(TraditionalForm\`{0, 1}\ \[Rho]\ {1, 0}\ \[Rho]\ {0, 1}\)]], ", but ", Cell[BoxData[ \(TraditionalForm\`\[Not] \ {0, 1}\ \[Rho]\ {0, 1}\)]], ". The same counterexample works for \[Sigma]." }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:124"], Cell[TextData[{ "We have to explain the symmetries in the pictures. \n\nFirst note the \ enumeration of ", Cell[BoxData[ \(TraditionalForm\`B(k)\ = \ {L\_0, L\_1, \ \[Ellipsis], L\_\(n - 1\)}\)]], ", where ", Cell[BoxData[ \(TraditionalForm\`n = 2\^\(\(\ \)\(k\)\)\)]], ", that is used implicitely: the binary expansions of numbers 0 through ", Cell[BoxData[ \(TraditionalForm\`n - 1\)]], ", padded to ", Cell[BoxData[ \(TraditionalForm\`k\)]], " binary digits. Hence ", Cell[BoxData[ \(TraditionalForm\`L\_k\)]], " is the bitwise complement of ", Cell[BoxData[ \(TraditionalForm\`L\_\(n - k - 1\)\)]], ". \nFor example, ", Cell[BoxData[ \(TraditionalForm\`L\_\(\(\ \)\(9\)\)\)]], " is the complement of ", Cell[BoxData[ \(TraditionalForm\`L\_\(\(\ \)\(54\)\)\)]], " in ", Cell[BoxData[ \(TraditionalForm\`B(6)\)]], ". Since ", StyleBox["Mathematica", FontSlant->"Italic"], " uses 1-indexing, so we have to add 1 to obtain the proper positions:" }], "Text", Evaluatable->False], Cell[BoxData[{ \(B6[\([\)\(10\)\(]\)]\), "\n", \(B6[\([\)\(55\)\(]\)]\)}], "Input"], Cell[TextData[{ "Thinking of binary lists as bit-vectors and thus as subsets of the \ universal set ", Cell[BoxData[ \(TraditionalForm\`\(\([\)\(n\)\(]\)\)\)]], " the set ", Cell[BoxData[ \(TraditionalForm\`L\_k\)]], " is simply the complement of ", Cell[BoxData[ \(TraditionalForm\`L\_\(n - k - 1\)\)]], ": ", Cell[BoxData[ \(TraditionalForm\`L\_k = \ \(L\_\(n - k - 1\)\)\&_\)]], ". \nIn this subset interpretation we can describe the 3 relations as \ follows:\n\t", Cell[BoxData[ \(TraditionalForm\`K\ \[Rho]\ L\ \ \ \[DoubleLeftRightArrow] \ K\ \[Intersection] \ L\ = \ \[EmptySet]\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`K\ \[Sigma]\ L\ \ \[DoubleLeftRightArrow] \ K\ \[Union] \ L\ = \ \(\([\)\(n\)\(]\)\)\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`K\ \[Tau]\ L\ \ \ \[DoubleLeftRightArrow] \ K\ \[SubsetEqual] \ L\)]], "\nBut then \n\t", Cell[BoxData[ \(TraditionalForm\`K\ \[Sigma]\ L\ \ \[DoubleLeftRightArrow] \ K\&_\ \[Intersection] \ L\&_\ = \ \[EmptySet]\ \ \[DoubleLeftRightArrow] \ K\&_\ \[Rho]\ L\&_\)]], "\nand \n\t", Cell[BoxData[ \(TraditionalForm\`K\ \[Tau]\ L\ \ \[DoubleLeftRightArrow] \ K\ \[Intersection] \ L\&_\ = \ \[EmptySet]\ \ \[DoubleLeftRightArrow] \ K\ \[Rho]\ L\&_\)]], ".\n\nThus, the pictures for \[Sigma] and \[Tau] are just reflections of \ the picture for \[Rho]." }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["rotLess", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->{"relation", "c:125"}], Cell[CellGroupData[{ Cell["Background", "Subsubsection", CellTags->"c:126"], Cell[TextData[{ "Let ", Cell[BoxData[ \(TraditionalForm\`B(n)\)]], " denote all binary lists of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], " and think of these lists as bit-vectors. With this interpretation in \ mind, define the following family of relations on ", Cell[BoxData[ \(TraditionalForm\`B(n)\)]], ":\n\n\t", Cell[BoxData[ \(TraditionalForm\`K\ \(\[Rho](s)\)\ L\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`L\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(rot\_s\)(K)\)]], " are disjoint.\n\nHere ", Cell[BoxData[ \(TraditionalForm\`\(rot\_s\)(K)\)]], " denotes the list ", Cell[BoxData[ \(TraditionalForm\`K\)]], ", cyclically rotated by ", Cell[BoxData[ \(TraditionalForm\`s\)]], " places to the left. We assume ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] s < n\)]], ". \nHere is an implementation of the relations, and a plot for lists of \ length 6." }], "Text", Evaluatable->False], Cell[BoxData[{ \(Clear[gr]\), "\n", \(\(rotLess[s_Integer]\)[L1_, L2_] := ListLess[L1, RotateLeft[L2, s]]; \), "\n", \(B6 = Tuples[2, 6] - 1; \), "\n", \(\(gr[s_] := PlotMatrix[RelationToMatrix[B6, rotLess[s]], DisplayFunction \[Rule] Identity];\)\), "\n", \(\(ShowArray[gr /@ Range[0, 5]];\)\)}], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:127"], Cell[TextData[{ "a) Which of the relations ", Cell[BoxData[ \(TraditionalForm\`\[Rho](s)\)]], " are partial orders on ", Cell[BoxData[ \(TraditionalForm\`B(n)\)]], "?\nb) Explain the first two pictures in the background section. More \ precisely, how is the plot for ", Cell[BoxData[ \(TraditionalForm\`\[Rho](1)\)]], " related to the plot for ", Cell[BoxData[ \(TraditionalForm\`\[Rho](0)\)]], "?" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:128"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:129"], Cell[TextData[{ "Claim: Only ", Cell[BoxData[ \(TraditionalForm\`\[Rho](0)\)]], " is a partial order. \n\nWe have to check that ", Cell[BoxData[ \(TraditionalForm\`\[Rho](0)\)]], " is reflexive, anti-symmetric, and transitive. But all these properties \ follow immediately from the fact that ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " is an order on ", Cell[BoxData[ \(TraditionalForm\`{0, 1}\)]], ". ", Cell[BoxData[ \(TraditionalForm\`\[Rho](0)\)]], " is what is called a product order: it is the ", Cell[BoxData[ \(TraditionalForm\`n\)]], "-fold product of ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " on ", Cell[BoxData[ \(TraditionalForm\`{0, 1}\)]], " with itself. The same trick works for any order as starting point. \ However, unlike ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " the order ", Cell[BoxData[ \(TraditionalForm\`\[Rho](0)\)]], " is no longer total: the lists ", Cell[BoxData[ \(TraditionalForm\`{1, 0, \[Ellipsis]}\)]], " and ", Cell[BoxData[ \(TraditionalForm\`{0, 1, \[Ellipsis]}\)]], " for example are not comparable. \n\nFor ", Cell[BoxData[ \(TraditionalForm\`s > 0\)]], " the relations ", Cell[BoxData[ \(TraditionalForm\`\[Rho](s)\)]], " fail to be partial orders for a number of reasons: they are not reflexive \ as can be seen by considering ", Cell[BoxData[ \(TraditionalForm\`{1, 0, \[Ellipsis], 0}\)]], ". For ", Cell[BoxData[ \(TraditionalForm\`n/\(gcd(n, s)\) \[GreaterEqual] \ 3\)]], " they also fail to be transitive. For ", Cell[BoxData[ \(TraditionalForm\`s\ = \ n/2\)]], " anti-symmetry fails. " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:130"], Cell[TextData[{ "From the definition, \n\n\t", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(\ \)\) {L\ | \ K\ \(\[Rho](0)\)\ L\ }\ | \ = \ \(\(|\)\(\ \)\) {\ L\ | \ K\ \(\[Rho](s)\)\ L\ }\ | \)]], "\n\t\nfor each ", Cell[BoxData[ \(TraditionalForm\`s\)]], ". Each row of the second matrix is thus a rearrangement of the \ corresponding row of the first matrix. The permutation describing the \ rearrangement is the same throughout. " }], "Text"], Cell[BoxData[{ \(\(R0\ = \ RelationToMatrix[B6, rotLess[0]];\)\), "\n", \(\(R1\ = \ RelationToMatrix[B6, rotLess[1]];\)\)}], "Input"], Cell[BoxData[{ \(R0[\([33]\)]\), "\n", \(R1[\([33]\)]\)}], "Input"], Cell[BoxData[{ \(R0[\([32]\)]\), "\n", \(R1[\([32]\)]\)}], "Input"], Cell[BoxData[{ \(R0[\([21]\)]\), "\n", \(R1[\([21]\)]\)}], "Input"], Cell[TextData[{ "So the problem really is to determine how the operation ", Cell[BoxData[ \(TraditionalForm\`rot\_1\)]], " affects the position of a list ", Cell[BoxData[ \(TraditionalForm\`L\)]], " in the enumeration that underlies the pictures: ", Cell[BoxData[ \(TraditionalForm\`B(k)\ = \ {L\_0, L\_1, \ \[Ellipsis], L\_\(n - 1\)}\)]], ", where ", Cell[BoxData[ \(TraditionalForm\`n = 2\^\(\(\ \)\(k\)\)\)]], ". This corresponds to the binary expansions of numbers 0 through ", Cell[BoxData[ \(TraditionalForm\`n - 1\)]], ", padded to ", Cell[BoxData[ \(TraditionalForm\`k\)]], " binary digits. \n\nHere is the effect of rotation on the position of a \ list in ", Cell[BoxData[ \(TraditionalForm\`B(6)\)]], "." }], "Text"], Cell[BoxData[ \(pos = Flatten[\((Position[B6, RotateLeft[#1]] &)\) /@ B6]\)], "Input"], Cell[TextData[{ "This is somewhat like the famous ", Cell[BoxData[ \(TraditionalForm\`2\ x\ mod\ 1\)]], " map in the continuous case. " }], "Text"], Cell[BoxData[ \(\(ListPlot[pos, PlotStyle \[Rule] {Blue, PointSize[0.02]}];\)\)], "Input"], Cell[BoxData[ \(\(Plot[Mod[2 x, 1], {x, 0, 1}, PlotStyle \[Rule] Blue];\)\)], "Input"], Cell["The permutation has the desired effect.", "Text"], Cell[BoxData[ \(Map[\ #[\([pos]\)] &, \ R0\ ] \[Equal] \ R1\)], "Input"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Rearrangements", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:131"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", CellTags->"c:132"], Cell[TextData[{ StyleBox["Consider the set ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\_\(\(\ \)\(n\)\)\)]], " of ", StyleBox["all lists (of some type) of length ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[". Define a relation \[Rho] on ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\_\(\(\ \)\(n\)\)\)]], StyleBox[" as follows. \n\n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\ \[Rho]\ K\)]], StyleBox[" iff there is a permutation \[Pi] of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\([\)\(n\)\(]\)\)\)]], " ", StyleBox["such that ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\ = \ K[\([\)\(\[Pi]\)\(]\)]\)]], ".", StyleBox["\n\nHere we think of \[Pi] as a Mathematica type list, rather \ than as a function. \nFor example, the following two list are related by \ \[Rho] via \[Pi]:", FontFamily->"Times"] }], "Text"], Cell[BoxData[{ \(Clear[K, L, a, b, d, c, d, e, p]\), "\n", \(K = {a, e, d, d, b}; \), "\n", \(L = {e, b, d, a, d}; \), "\n", \(p = {2, 5, 3, 1, 4}; \), "\n", \(L == K\[LeftDoubleBracket]p\[RightDoubleBracket]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:133"], Cell[TextData[{ StyleBox["(a", FontFamily->"Times", FontWeight->"Bold"], StyleBox[") Show that \[Rho] is an equivalence relation. \n\n(b) Now \ consider in particular binary list, i.e., lists over the ground set ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`{0, 1}\)]], ". ", StyleBox["What are the equivalence classes of \[Rho] on ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\_\(\(\ \)\(n\)\)\)]], "?", StyleBox[" In particular, how many are there? \n\n(c) If you think of a \ list in ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\_\(\(\ \)\(n\)\)\)]], " ", StyleBox["as a bit-vector, what are the equivalence classes from part (b)? \ ", FontFamily->"Times"] }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", CellTags->"c:134"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:135"], Cell[TextData[{ "Reflexivity: \nLet ", Cell[BoxData[ \(TraditionalForm\`p\ = \ {1, 2, ... , n}\)]], ", then ", Cell[BoxData[ \(TraditionalForm\`L\ = \ L[\([\)\(p\)\(]\)]\)]], ". \nSymmetry: \n", Cell[BoxData[ \(TraditionalForm\`L\ = \ K[\([\)\(p\)\(]\)]\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(K\ = \ L[\([\)\(q\)\(]\)]\)\)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`q\)]], " is the inverse permutation of ", Cell[BoxData[ \(TraditionalForm\`p\)]], ". \nTransitivity: \nIntuitively, ", Cell[BoxData[ \(TraditionalForm\`L\ \[Rho]\ K\)]], " means that ", Cell[BoxData[ \(TraditionalForm\`L\)]], " is a rearrangement of ", Cell[BoxData[ \(TraditionalForm\`K\)]], ". But a rearrangement of an rearrangement is a rearrangement. More \ formally, \.13assume ", Cell[BoxData[ \(TraditionalForm\`L\ = \ K[\([\)\(p\)\(]\)]\)]], " and ", Cell[BoxData[ \(TraditionalForm\`K\ = \ M[\([\)\(q\)\(]\)]\)]], ". Then ", Cell[BoxData[ \(TraditionalForm\`L\ = \ M[\([\)\(r\)\(]\)]\)]], " where ", Cell[BoxData[ \(TraditionalForm\`r\)]], " is the composition of ", Cell[BoxData[ \(TraditionalForm\`p\)]], " and ", Cell[BoxData[ \(TraditionalForm\`q\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:136"], Cell[TextData[{ "Two binary lists ", Cell[BoxData[ \(TraditionalForm\`L\)]], " and ", Cell[BoxData[ \(TraditionalForm\`K\)]], " are related by \[Rho] iff they contain the same number of 1's. \n\ Hence, there are ", Cell[BoxData[ \(TraditionalForm\`n + 1\)]], " equivalence classes. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:137"], Cell[TextData[{ "With the bit-vector interpretation, ", Cell[BoxData[ \(TraditionalForm\`L\ \[Rho]\ K\)]], " means that ", Cell[BoxData[ \(TraditionalForm\`L\)]], " and ", Cell[BoxData[ \(TraditionalForm\`K\)]], " have the same cardinality. " }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Lexicographic Order", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->{"lexicographic order", "c:138"}], Cell[CellGroupData[{ Cell["Background", "Subsubsection", CellTags->"c:139"], Cell["\<\ If one sorts a list of strings in Mathematica, the order chosen is \ the standard lexicographic order (or dictionary order). \ \>", "Text", Evaluatable->False], Cell[BoxData[{ \(L = {"\", "\", "\", "\", "\", "\", "\", "\", "\", "\", "\"}\), "\n", \(Sort[L]\)}], "Input"], Cell[TextData[{ "Here is a precise definition of lexicographic order on strings. A string \ ", Cell[BoxData[ \(TraditionalForm\`u\)]], " is a ", StyleBox["prefix", FontColor->RGBColor[0, 0, 1]], " of ", Cell[BoxData[ \(TraditionalForm\`v\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`v\)]], " can be obtained from ", Cell[BoxData[ \(TraditionalForm\`u\)]], " by adding some characters at the end. In other words, we can write ", Cell[BoxData[ \(TraditionalForm\`v\ = \ u\ x\)]], ", where ", Cell[BoxData[ \(TraditionalForm\`x\)]], " is some string. Note that this includes the case ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(u = v\)\)\)]], " (in which case ", Cell[BoxData[ \(TraditionalForm\`x\)]], " is the empty string). \nA string ", Cell[BoxData[ \(TraditionalForm\`u\)]], " is lexigraphically less than or equal to a string ", Cell[BoxData[ \(TraditionalForm\`v\)]], " iff one of the two following conditions holds: \n", StyleBox["(LO 1) ", FontColor->RGBColor[0, 0, 1]], " ", Cell[BoxData[ \(TraditionalForm\`u\)]], " is a prefix of ", Cell[BoxData[ \(TraditionalForm\`v\)]], ", or \n", StyleBox["(LO 2) ", FontColor->RGBColor[0, 0, 1]], " there are strings ", Cell[BoxData[ \(TraditionalForm\`w, \ x, \ y\)]], ", and characters ", Cell[BoxData[ \(TraditionalForm\`a\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\)]], " such that \n - ", Cell[BoxData[ \(TraditionalForm\`u\ = \ w\ a\ x\)]], ",\n - ", Cell[BoxData[ \(TraditionalForm\`v\ = \ w\ b\ y\)]], ",\n - ", Cell[BoxData[ \(TraditionalForm\`a\ < \ b\)]], " in the standard order on characters. \nAll the strings ", Cell[BoxData[ \(TraditionalForm\`w, \ x, \ y\)]], " in (LO 2) are allowed to be empty. " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:140"], Cell[TextData[{ "a) Show that lexicographic order as defined here is a total order on \ strings. \n\nb) Implement a recursive function ", StyleBox[" ", FontWeight->"Bold"], StyleBox["lexQ[u_String, v_String ]", "Input", FontWeight->"Bold"], " which tests whether string ", Cell[BoxData[ \(TraditionalForm\`u\)]], " is lexigraphically less than or equal ", Cell[BoxData[ \(TraditionalForm\`v\)]], ". \nTest your function by running the command ", StyleBox["Sort[ L, lexQ ]", "Input"], " with the list L from above. \n\nc) Show that your implementation is \ correct. Assume the recursive calls produce the right answer, and show that \ the whole function also produces the right answer." }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Commands", "Subsubsection", Evaluatable->False, CellTags->"c:141"], Cell[TextData[{ "There are a variety of string related commands in Mathematica starting \ with String (do a ", StyleBox["?String*", "Input"], "). You will only need ", ButtonBox["StringTake", ButtonStyle->"RefGuideLink"], " and ", ButtonBox["StringDrop", ButtonStyle->"RefGuideLink"], ".\nYou cannot use <= in Mathematica to check order on two characters, \ use ", ButtonBox["OrderedQ", ButtonStyle->"RefGuideLink"], " instead. Needless to say, ", StyleBox["OrderedQ", "Input"], StyleBox[" ", "Input"], "solves the problem, but it is not recursive, so you have to work a little \ harder." }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:142"], Cell[CellGroupData[{ Cell["Order", "Subsubsection", Evaluatable->False, CellTags->"c:143"], Cell[TextData[{ "Let us write <= for the lexicographic order on strings. \n- It is clear \ that <= is ", StyleBox["reflexive", FontColor->RGBColor[0, 0, 1]], ": u is a prefix of u, so (LO 1) holds. \n- For", StyleBox[" anti-symmetry", FontColor->RGBColor[0, 0, 1]], " suppose that u <= v and v <= u. \nWe have to distinguish four \ cases, depending on wheter the relation holds because of (LO 1) or (LO 2). \ \nIf in both cases (LO 1) holds, i.e., if u is a prefix of v which is in \ turn a prefix of u, then u == v. For x prefix of y implies that Length[x] \ <= Length[y], so u and v must have the same length, and therefore u == v. \n\ So assume u <= v because of (LO 1), but v <= u because of (LO 2). Then \ for some strings w,x,y and characters a < b: v == wax and u == wby. But u \ is prefix of v, so a == b, contradiction. The case (LO 2) and (LO 1) is \ entirely similar. \nLastly, suppose u <= v and v <= u because of (LO 2) \ and (LO 2). Then u == wax, v == wby, v == w'b'y' and u == w'a'x' \ where a < b and b' < a'. Suppose w is shorter than w'. Then a==b, \ contradiction. If w is longer than w', then a'==b', contraction. But if \ w has the same length as w', then a==a' and b==b', contradicting aRGBColor[0, 0, 1]], " assume u <= v and v <= s. Again, there are 4 cases. \nIf in both \ cases (LO 1) holds, i.e., if u is a prefix of v which is in turn a prefix of \ s, then clearly u is a prefix of s, and we are done. \nSo suppose u is a \ prefix of v, but v <= s because of (LO 2). Then for some strings w,x,y \ and characters a < b: v == wax and s == wby. If u is a prefix of w, then \ it is also a prefix of s. Otherwise, by truncating x, we can see that (LO 2) \ forces u <= s. \nThe remaining cases are similar. \n- ", StyleBox["Comparability", FontColor->RGBColor[0, 0, 1]], ". Consider two arbitrary strings u and v, and suppose neither is a prefix \ of the other. Then, there must be a maximal prefix w that is shared by u and \ v (possibly empty), and we can write u == wax and v == wby, for some \ strings x and y, and characters a and b. Since w is maximal, a != b. But then \ u <= v of v <= u according as a < b or b < a. " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Implementation", "Subsubsection", Evaluatable->False, CellTags->"c:144"], Cell[TextData[{ "Now for the ", StyleBox["implementation", FontColor->RGBColor[0, 0, 1]], ". " }], "Text", Evaluatable->False], Cell[BoxData[{ \(lexQ["\<\>", v_String] := True; \), "\n", \(lexQ[u_String, "\<\>"] := False; \), "\n", \(lexQ[u_String, v_String] := Module[{u1, v1}, u1 = StringTake[u, 1]; v1 = StringTake[v, 1]; If[u1 == v1, lexQ[StringDrop[u, 1], StringDrop[v, 1]], OrderedQ[{u1, v1}]]]\)}], "Input"], Cell[BoxData[ \(Trace[lexQ["\", "\"], lexQ[__String]]\)], "Input"], Cell[BoxData[{ \(L = {"\", "\", "\", "\", "\", "\", "\", "\", "\", "\", "\"}; \), "\n", \(Sort[L]\), "\n", \(Sort[L, lexQ]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Correctness", "Subsubsection", Evaluatable->False, CellTags->"c:145"], Cell[TextData[{ "Here is a ", StyleBox["correctness proof", FontColor->RGBColor[0, 0, 1]], " for this implementation. Clearly, the first two cases of the definition \ of lexQ are fine: \n- the empty string \"\" is a prefix of every string, \n- \ in case two, u is not empty (right?), so u <= \"\" is always false. \nIn \ the third part of the definition, we have u and v non-empty. Hence, both \ can be written as \n\tu == u1 uu, u1 = StringTake[u,1], uu = \ StringDrop[u,1],\n\tv == v1 vv, v1 = StringTake[v,1], vv = \ StringDrop[v,1].\t\nCase 1: u1 == v1. \nThen u is a prefix of v iff uu \ is a prefix of vv, which takes care of (LO 1). \nAlso, u and v satisfy (LO \ 2) iff uu and vv do. So, the recurisive call returns the right answer.\n\ Case 2: u1 != v1. \nThen u is not a prefix of v, and v not a prefix of u. \ However, we are in the situation described in (LO 2), in the special case \ where w == \"\". Thus, the call to OrderedQ[{u1,v1}] determines which of \ the two characters is smaller (in the standard ordering of ASCII symbols), \ and returns the correct answer. " }], "Text", Evaluatable->False] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Constructing the Rationals", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:146"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", Evaluatable->False, CellTags->"c:147"], Cell[TextData[{ "Rational numbers are intuitively familiar, but if need be they can be \ formally constructed from the integers (which in turn can be constructed from \ the natural numbers) as follows. \n\nDefine an equivalence relation ", Cell[BoxData[ \(TraditionalForm\`~\)]], " on ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalZ]\ \[Cross]\ \ \[DoubleStruckCapitalN]\^\(\(\ \)\(+\)\)\)]], " as follows: \n\t", Cell[BoxData[ \(TraditionalForm\`\((a, b)\)~\ \((c, d)\)\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`a\ d\ = \ b\ c\)]], " \nThus, the pair ", Cell[BoxData[ \(TraditionalForm\`\((a, b)\)\)]], " stands for the fraction ", Cell[BoxData[ \(TraditionalForm\`a\/b\)]], ", and equivalence is simply equality of the corresponding fractions. \ However, the only operation needed in our setting is multiplication of \ integers. " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:148"], Cell[TextData[{ "a) Show that the relation ", Cell[BoxData[ \(TraditionalForm\`~\)]], " is indeed an equivalence relation. \n\nb) Find a way do define addition \ and multiplication on the equivalence classes of ", Cell[BoxData[ \(TraditionalForm\`~\)]], ". \nIn particular, make sure that your operations are well-defined. " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:149"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:150"], Cell[TextData[{ "~ is clearly reflexive and symmetric.\n\nTransitivity: \n\n\t", Cell[BoxData[ \(TraditionalForm\`\((a, b)\)~\ \((c, d)\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\((c, d)\)~\((e, f)\)\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`a\ d\ = \ b\ c\)]], " and ", Cell[BoxData[ \(TraditionalForm\`c\ f\ = \ e\ d\)]], ". \n\tHence ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(a\ d\ c\ f\ = \ b\ c\ e\ d\)\)\)]], " and thus ", Cell[BoxData[ \(TraditionalForm\`a\ f\ = \ b\ e\)]], ", and therefore ", Cell[BoxData[ \(TraditionalForm\`\((a, b)\)\ ~\ \((e, f)\)\)]], ".\n\t\nThe equivalence class of ", Cell[BoxData[ \(TraditionalForm\`\((a, b)\)\)]], " is the collection of all ", Cell[BoxData[ \(TraditionalForm\`\((c, d)\)\)]], " such that over \[DoubleStruckCapitalQ]: ", Cell[BoxData[ \(TraditionalForm\`a\/b = \ c\/d\)]], ". \n\nNote that there is a normal form, a natural representative of each \ class: ", Cell[BoxData[ \(TraditionalForm\`a\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\)]], " relatively prime (in lowest common terms). The natural numbers are \ imbedded by ", Cell[BoxData[ \(TraditionalForm\`n\ \[Rule] \ \((n, 1)\)\)]], ". " }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:151"], Cell[TextData[{ "Multiplication is a bit easier than addition:\n\t", Cell[BoxData[ \(TraditionalForm\`\(\((a, b)\)\(\ \)\(*\)\(\ \)\((c, d)\)\(\ \)\) = \ \((\ a\ c, \ b\ d\ )\)\)]], "\nWe have to check that this operation is well-defined. For simplicity, \ we only check that we can replace ", Cell[BoxData[ \(TraditionalForm\`\((a, b)\)\)]], " by an equivalent ", Cell[BoxData[ \(TraditionalForm\`\((\[Alpha], \[Beta])\)\)]], ". Hence ", Cell[BoxData[ \(TraditionalForm\`a\ \[Beta]\ = \ \[Alpha]\ b\)]], ". But then ", Cell[BoxData[ \(TraditionalForm\`a\ c\ \[Beta]\ d\ = \(\(\(\[Alpha]\)\(\ \)\) \ \(c\)\(\ \)\(b\)\(\ \)\(d\)\(\ \)\)\)]], ", and so ", Cell[BoxData[ \(TraditionalForm\`\((a\ c, b\ d)\)\ ~\ \((\ \[Alpha]\ c, \ \[Beta]\ d\ )\)\)]], ", as required." }], "Text"], Cell[TextData[{ "For addition, we define\n\n\t", Cell[BoxData[ \(TraditionalForm\`\(\((a, b)\)\(\ \)\(+\)\(\ \)\((c, d)\)\(\ \)\) = \ \((\ a\ d\ + \ b\ c, \ b\ d\ )\)\)]], "\n\nAgain, it is not hard to check that the operation is well-defined. " }], "Text"], Cell[TextData[{ "Note that this addition and multiplication extend the same operations on \ the integers when we embed ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalZ]\ \[LongRightArrow]\ \ \[DoubleStruckCapitalZ]\ \[Cross]\ \[DoubleStruckCapitalN]\^\(\(\ \)\(+\)\)/~\ \)]], ", ", Cell[BoxData[ \(TraditionalForm\`z\ \[Rule] \ \((z, 1)\)\)]], ". " }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Functions on Sets", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:152"], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:153"], Cell[TextData[{ "Let ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \ A\ \[Rule] \ B\)]], " be a function, and consider two subsets ", Cell[BoxData[ \(TraditionalForm\`X, \ Y\ \[SubsetEqual] \ A\)]], ". \nDetermine whether the following assertions are true, and give reasons \ for your answer.\n\n(a) ", Cell[BoxData[ \(TraditionalForm\`f(X \[Union] \ Y)\ = \ f(X)\ \[Union] f(Y)\)]], "\n\n(b) ", Cell[BoxData[ \(TraditionalForm\`f(X \[Intersection] \ Y)\ = \ f(X)\ \[Intersection] f(Y)\)]], "\n" }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:154"], Cell[TextData[{ "(a) True. \n ", Cell[BoxData[ \(TraditionalForm\`\(\(\(f(X \[Union] \ Y)\)\(\ \)\)\(=\)\(\ \)\({\ f(z)\ | \ z\ \[Element] \ X\ \[Union] \ Y\ }\)\(\ \)\)\)]], "\n ", Cell[BoxData[ \(TraditionalForm\`\(\(=\)\(\ \)\) \({\ f(z)\ | \ z\ \[Element] \ X\ }\ \[Union] \ {\ f(z)\ | \ z\ \[Element] \ Y\ }\ = \ f(X)\ \[Union] f(Y)\)\)]] }], "Text", Evaluatable->False], Cell[TextData[{ "(b) False.\nLet ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\([\)\(2\)\(]\)\)\ \[Rule] \ \(\([\)\(2\)\ \(]\)\)\)]], " be the function ", Cell[BoxData[ \(TraditionalForm\`f(1) = \(f(2) = \ 1\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`X = {1}\)]], ", and ", Cell[BoxData[ \(TraditionalForm\`Y = {2}\)]], ".\nThen ", Cell[BoxData[ \(TraditionalForm\`f( X \[Intersection] \ Y)\ = \ \(f(\[EmptySet])\ = \ \[EmptySet]\)\)]], " but ", Cell[BoxData[ \(TraditionalForm\`f(X)\ \[Intersection] f(Y) = \ {1}\)]], ". " }], "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Reflexivity", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:155"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", Evaluatable->False, CellTags->"c:156"], Cell[TextData[{ "Finding flaws in alleged proofs is an important skill, and sometimes \ extremely difficult. \nHere is an example: a \"proof\" that every symmetric \ and transitive relation is also reflexive. \n\nSuppose \[Rho] on ", Cell[BoxData[ \(TraditionalForm\`A\)]], " is symmetric and transitive. Let ", Cell[BoxData[ \(TraditionalForm\`a\ \[Element] \ A\)]], ", and pick ", Cell[BoxData[ \(TraditionalForm\`b\ \[Element] \ A\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`a\ \[Rho]\ b\)]], ". By symmetry ", Cell[BoxData[ \(TraditionalForm\`b\ \[Rho]\ a\)]], ", and by transitivity ", Cell[BoxData[ \(TraditionalForm\`a\ \[Rho]\ a\)]], ", as required. \n" }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", Evaluatable->False, CellTags->"c:157"], Cell["\<\ a) Find the flaw in the proof. b) What information can be salvaged from the argument? \ \>", "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", Evaluatable->False, CellTags->"c:158"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:159"], Cell[TextData[{ "There may not be any ", Cell[BoxData[ \(TraditionalForm\`b\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`a\ \[Rho]\ b\)]], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:160"], Cell[TextData[{ "\[Rho] is reflexive on all the elements in \[RawEscape]", Cell[BoxData[ \(TraditionalForm\`{\ a\ \[Element] \ A\ | \ \ \[Exists] \ b\ \[Element] \ A\ \((\ a\ \[Rho]\ b\ )\)\ }\)]], ". \nConfusingly, this set is sometimes called the domain of \[Rho]." }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Additive Functions", "Section", Evaluatable->False, PageBreakAbove->True, AspectRatioFixed->True, CellTags->"c:161"], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:162"], Cell[TextData[{ "As usual, ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalQ]\)]], " denotes the set of rational numbers. Suppose we have an additive \ function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalQ]\ \[LongRightArrow]\ \ \[DoubleStruckCapitalQ]\)]], ", i.e., a function with the property that\n\n\t ", Cell[BoxData[ \(TraditionalForm\`f(x + y)\ = \ f(x)\ + \ f(y)\)]], ". \n\na) Show that for any integer ", Cell[BoxData[ \(TraditionalForm\`z\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(z)\ = \ z\ \[CenterDot]\ \(f(1)\)\)]], ". \nb) Show that for any rational number ", Cell[BoxData[ \(TraditionalForm\`x\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x\ \[CenterDot]\ \(f(1)\)\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", FontColor->RGBColor[0, 0, 1], CellTags->"c:163"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:164"], Cell[TextData[{ "We have ", Cell[BoxData[ \(TraditionalForm\`f(0)\ = \ \(f(0 + 0)\ = \ f(0)\ + \ f(0)\)\)]], ", so that ", Cell[BoxData[ \(TraditionalForm\`f(0) = 0\)]], ". \nAlso, ", Cell[BoxData[ \(TraditionalForm\`\(\(f( x)\)\(\ \)\(\ \)\(+\)\(\ \)\(f(\(-x\))\)\(\ \)\) = \ \(f( x - x)\ = \ \(f(0)\ = \ 0\)\)\)]], ", so that ", Cell[BoxData[ \(TraditionalForm\`f(\(-x\))\ = \ \(-\(f(x\ )\)\)\)]], ".\nBut an easy induction on ", Cell[BoxData[ \(TraditionalForm\`n\ \[GreaterEqual] \ 1\)]], " shows that ", Cell[BoxData[ \(TraditionalForm\`f(n)\ = \ n\ \(f(1)\)\)]], ", so we are done with integers." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:165"], Cell[TextData[{ "For rationals, first consider ", Cell[BoxData[ \(TraditionalForm\`x = \ 1/n\)]], ". \nWe have ", Cell[BoxData[ \(TraditionalForm\`f(1)\ = \ \(f(n\ \[CenterDot]\ 1/n)\ = \ n\ \(f(1/n)\)\)\)]], ", so that ", Cell[BoxData[ \(TraditionalForm\`f(1/n) = \(f(1)\)/n\)]], ". \nTogether with part a) this implies\nAlso, ", Cell[BoxData[ \(TraditionalForm\`f( a/b)\ \ = \ \(f(a\ \[CenterDot]\ 1/b)\ = \ \(a\ \(f(1/b)\)\ = a/b\ \ \(f(1)\)\)\)\)]], "." }], "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["The Max CA", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:166"], Cell[CellGroupData[{ Cell["Background", "Subsubsection", CellTags->"c:167"], Cell[TextData[{ StyleBox["Consider the elementary CA given by the local map\n\n\t\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(x, y, z)\ = \ max(x, y, z)\)]], ".", StyleBox["\n\nIncidentally, this is CA number 254. Let ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`C\_n\)]], StyleBox[" denote the transition diagram of this CA for configurations of \ length ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], ". Here is one example of an orbit. Admittedly, a bit boring, but easy to \ analyze." }], "Text"], Cell[BoxData[ \(\(EvolutionCA[\ CA[254]\ ];\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Task", "Subsubsection", CellTags->"c:168"], Cell[TextData[{ StyleBox["(a) Determine all the cycles in ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`C\_n\)]], ". ", StyleBox["\n\n(b) Determine how many configurations lead to each of these \ cycles. \n\n(c) What is the longest possible transient in ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`C\_n\)]], StyleBox["?\n\n(d) What would happen if the max were replaced by min?", FontFamily->"Times"] }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Comment", "Subsubsection", CellTags->"c:169"], Cell[TextData[{ StyleBox["You can use Mathematica to answer all these questions by brute \ force for some small values of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[", but in the end you have to reason that about the general case. \ ", FontFamily->"Times"] }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Solution", "Subsection", CellTags->"c:170"], Cell[CellGroupData[{ Cell["Part a", "Subsubsection", CellTags->"c:171"], Cell[TextData[{ StyleBox["There are exactly two cycles in ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`C\_n\)]], StyleBox[": the fixed points ", FontFamily->"Times"], StyleBox["0", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" and ", FontFamily->"Times"], StyleBox["1", FontFamily->"Times", FontWeight->"Bold"], StyleBox[". \nTo see that no other configuration lies on a cycle, note \ that the number of 1's in a configuration cannot decrease under application \ of G, the global map of CA 254. In fact, \n\n\t\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`X \((i)\)\ = \ 1\)]], StyleBox[" implies ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`G \((X)\) \((i)\)\ = \ 1\)]], StyleBox[". \n\nMoreover, the number of 1's increases for all \ configurations X other than ", FontFamily->"Times"], StyleBox["0", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" and ", FontFamily->"Times"], StyleBox["1", FontFamily->"Times", FontWeight->"Bold"], StyleBox[": somewhere in ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`X\)]], StyleBox[" there must be a cell in state 0 adjacent to a cell in state 1. \ Than cell will be in state 1 in ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`G \((X)\)\)]], StyleBox[". ", FontFamily->"Times"] }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part b", "Subsubsection", CellTags->"c:172"], Cell[TextData[{ StyleBox["All configurations other than ", FontFamily->"Times"], StyleBox["0", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" lead to the cycle ", FontFamily->"Times"], StyleBox["1", FontFamily->"Times", FontWeight->"Bold"], StyleBox[". Hence, only one configuration is attracted to ", FontFamily->"Times"], StyleBox["0", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" (namely ", FontFamily->"Times"], StyleBox["0", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" itself), all ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`2\^\(\(\ \)\(n\)\)\ - \ 1\)]], StyleBox[" others are attracted to ", FontFamily->"Times"], StyleBox["1", FontFamily->"Times", FontWeight->"Bold"], StyleBox[". ", FontFamily->"Times"] }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Part c", "Subsubsection", CellTags->"c:173"], Cell[TextData[{ StyleBox["From the comment about the number of 1's in ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`G \((X)\)\)]], StyleBox[" above it follows that the transient of any configuration cannot \ be any longer than ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\[LeftFloor]n/2\[RightFloor]\)]], StyleBox[". This bound is reached for any one-point initial configuration. \ ", FontFamily->"Times"] }], "Text"] }, Closed]] }, Closed]] }, Closed]] }, Open ]] }, FrontEndVersion->"5.0 for X", ScreenRectangle->{{0, 1280}, {0, 1024}}, WindowSize->{923, 996}, WindowMargins->{{Automatic, 1}, {Automatic, 0}}, PrintingStartingPageNumber->189, Magnification->1.5, 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, 59, 1, 145, "Title", CellTags->"c:1"]}, "c:2"->{ Cell[1912, 60, 99, 3, 111, "Section", Evaluatable->False, CellTags->"c:2"]}, "c:3"->{ Cell[2036, 67, 54, 1, 60, "Subsubsection", CellTags->"c:3"]}, "c:4"->{ Cell[3413, 107, 48, 1, 60, "Subsubsection", CellTags->"c:4"]}, "c:5"->{ Cell[4007, 129, 49, 1, 64, "Subsection", CellTags->"c:5"]}, "c:6"->{ Cell[4081, 134, 50, 1, 60, "Subsubsection", CellTags->"c:6"]}, "c:7"->{ Cell[4455, 152, 50, 1, 60, "Subsubsection", CellTags->"c:7"]}, "c:8"->{ Cell[5584, 191, 50, 1, 60, "Subsubsection", CellTags->"c:8"]}, "c:9"->{ Cell[6413, 223, 104, 3, 64, "Section", Evaluatable->False, CellTags->"c:9"]}, "c:10"->{ Cell[6542, 230, 55, 1, 60, "Subsubsection", CellTags->"c:10"]}, "c:11"->{ Cell[7298, 264, 49, 1, 60, "Subsubsection", CellTags->"c:11"]}, "c:12"->{ Cell[8119, 286, 50, 1, 64, "Subsection", CellTags->"c:12"]}, "c:13"->{ Cell[8194, 291, 51, 1, 60, "Subsubsection", CellTags->"c:13"]}, "c:14"->{ Cell[8408, 302, 51, 1, 60, "Subsubsection", CellTags->"c:14"]}, "c:15"->{ Cell[9151, 332, 51, 1, 60, "Subsubsection", CellTags->"c:15"]}, "c:16"->{ Cell[9645, 349, 51, 1, 60, "Subsubsection", CellTags->"c:16"]}, "c:17"->{ Cell[9907, 361, 51, 1, 60, "Subsubsection", CellTags->"c:17"]}, "c:18"->{ Cell[10372, 379, 51, 1, 60, "Subsubsection", CellTags->"c:18"]}, "c:19"->{ Cell[12492, 452, 101, 3, 64, "Section", Evaluatable->False, CellTags->"c:19"]}, "c:20"->{ Cell[12618, 459, 77, 2, 39, "Subsubsection", Evaluatable->False, CellTags->"c:20"]}, "c:21"->{ Cell[14050, 508, 71, 2, 39, "Subsubsection", Evaluatable->False, CellTags->"c:21"]}, "c:22"->{ Cell[14798, 537, 72, 2, 44, "Subsection", Evaluatable->False, CellTags->"c:22"]}, "c:23"->{ Cell[14895, 543, 51, 1, 39, "Subsubsection", CellTags->"c:23"]}, "c:24"->{ Cell[15562, 569, 51, 1, 28, "Subsubsection", CellTags->"c:24"]}, "c:25"->{ Cell[17324, 620, 51, 1, 28, "Subsubsection", CellTags->"c:25"]}, "c:26"->{ Cell[18771, 675, 105, 3, 64, "Section", Evaluatable->False, CellTags->"c:26"]}, "c:27"->{ Cell[18901, 682, 77, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:27"]}, "c:28"->{ Cell[19673, 702, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:28"]}, "c:29"->{ Cell[20221, 724, 72, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:29"]}, "c:30"->{ Cell[20318, 730, 51, 1, 60, "Subsubsection", CellTags->"c:30"]}, "c:31"->{ Cell[20774, 745, 51, 1, 60, "Subsubsection", CellTags->"c:31"]}, "c:32"->{ Cell[21813, 775, 51, 1, 60, "Subsubsection", CellTags->"c:32"]}, "c:33"->{ Cell[22120, 787, 51, 1, 60, "Subsubsection", CellTags->"c:33"]}, "c:34"->{ Cell[23027, 822, 100, 3, 64, "Section", Evaluatable->False, CellTags->"c:34"]}, "c:35"->{ Cell[23152, 829, 77, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:35"]}, "c:36"->{ Cell[23945, 858, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:36"]}, "c:37"->{ Cell[24531, 878, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:37"]}, "c:38"->{ Cell[24954, 895, 72, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:38"]}, "c:39"->{ Cell[27794, 977, 100, 3, 64, "Section", Evaluatable->False, CellTags->"c:39"]}, "c:40"->{ Cell[27919, 984, 49, 1, 60, "Subsubsection", CellTags->"c:40"]}, "c:41"->{ Cell[28995, 1024, 72, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:41"]}, "c:42"->{ Cell[31763, 1113, 108, 3, 64, "Section", Evaluatable->False, CellTags->"c:42"]}, "c:43"->{ Cell[31896, 1120, 55, 1, 60, "Subsubsection", CellTags->"c:43"]}, "c:44"->{ Cell[32496, 1146, 49, 1, 60, "Subsubsection", CellTags->"c:44"]}, "c:45"->{ Cell[33207, 1174, 50, 1, 64, "Subsection", CellTags->"c:45"]}, "c:46"->{ Cell[33282, 1179, 51, 1, 60, "Subsubsection", CellTags->"c:46"]}, "c:47"->{ Cell[34120, 1219, 51, 1, 60, "Subsubsection", CellTags->"c:47"]}, "c:48"->{ Cell[34632, 1239, 51, 1, 60, "Subsubsection", CellTags->"c:48"]}, "c:49"->{ Cell[36096, 1299, 111, 3, 64, "Section", Evaluatable->False, CellTags->"c:49"]}, "c:50"->{ Cell[36232, 1306, 55, 1, 60, "Subsubsection", CellTags->"c:50"]}, "c:51"->{ Cell[36554, 1318, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:51"]}, "c:52"->{ Cell[37180, 1338, 72, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:52"]}, "c:53"->{ Cell[37277, 1344, 51, 1, 60, "Subsubsection", CellTags->"c:53"]}, "c:54"->{ Cell[37519, 1357, 51, 1, 60, "Subsubsection", CellTags->"c:54"]}, "c:55"->{ Cell[37838, 1373, 51, 1, 60, "Subsubsection", CellTags->"c:55"]}, "c:56"->{ Cell[38208, 1392, 51, 1, 60, "Subsubsection", CellTags->"c:56"]}, "c:57"->{ Cell[39095, 1431, 100, 3, 64, "Section", Evaluatable->False, CellTags->"c:57"]}, "c:58"->{ Cell[39220, 1438, 77, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:58"]}, "c:59"->{ Cell[40058, 1467, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:59"]}, "c:60"->{ Cell[40644, 1487, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:60"]}, "c:61"->{ Cell[41070, 1504, 72, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:61"]}, "c:62"->{ Cell[47025, 1692, 103, 3, 64, "Section", Evaluatable->False, CellTags->"c:62"]}, "c:63"->{ Cell[47153, 1699, 55, 1, 60, "Subsubsection", CellTags->"c:63"]}, "c:64"->{ Cell[47943, 1725, 49, 1, 60, "Subsubsection", CellTags->"c:64"]}, "c:65"->{ Cell[48639, 1747, 50, 1, 60, "Subsubsection", CellTags->"c:65"]}, "c:66"->{ Cell[49450, 1772, 53, 1, 60, "Subsubsection", CellTags->"c:66"]}, "c:67"->{ Cell[50841, 1829, 50, 1, 64, "Subsection", CellTags->"c:67"]}, "c:68"->{ Cell[50916, 1834, 51, 1, 60, "Subsubsection", CellTags->"c:68"]}, "c:69"->{ Cell[51491, 1861, 51, 1, 60, "Subsubsection", CellTags->"c:69"]}, "c:70"->{ Cell[52377, 1892, 51, 1, 60, "Subsubsection", CellTags->"c:70"]}, "c:71"->{ Cell[53527, 1935, 112, 3, 64, "Section", Evaluatable->False, CellTags->"c:71"]}, "c:72"->{ Cell[53664, 1942, 77, 2, 39, "Subsubsection", Evaluatable->False, CellTags->"c:72"]}, "c:73"->{ Cell[55592, 2007, 71, 2, 39, "Subsubsection", Evaluatable->False, CellTags->"c:73"]}, "c:74"->{ Cell[56082, 2028, 72, 2, 44, "Subsection", Evaluatable->False, CellTags->"c:74"]}, "c:75"->{ Cell[56179, 2034, 51, 1, 60, "Subsubsection", CellTags->"c:75"]}, "c:76"->{ Cell[57163, 2071, 51, 1, 60, "Subsubsection", CellTags->"c:76"]}, "c:77"->{ Cell[58423, 2108, 141, 4, 64, "Section", Evaluatable->False, PageBreakAbove->True, CellTags->"c:77"]}, "c:78"->{ Cell[58589, 2116, 49, 1, 39, "Subsubsection", CellTags->"c:78"]}, "c:79"->{ Cell[59780, 2156, 82, 2, 44, "Subsection", CellTags->"c:79"]}, "c:80"->{ Cell[59887, 2162, 51, 1, 39, "Subsubsection", CellTags->"c:80"]}, "c:81"->{ Cell[60256, 2177, 51, 1, 28, "Subsubsection", CellTags->"c:81"]}, "c:82"->{ Cell[60792, 2199, 51, 1, 39, "Subsubsection", CellTags->"c:82"]}, "c:83"->{ Cell[61411, 2223, 51, 1, 39, "Subsubsection", CellTags->"c:83"]}, "c:84"->{ Cell[62038, 2247, 51, 1, 39, "Subsubsection", CellTags->"c:84"]}, "c:85"->{ Cell[62684, 2272, 51, 1, 28, "Subsubsection", CellTags->"c:85"]}, "c:86"->{ Cell[63495, 2300, 51, 1, 39, "Subsubsection", CellTags->"c:86"]}, "c:87"->{ Cell[64573, 2337, 118, 3, 64, "Section", Evaluatable->False, CellTags->"c:87"]}, "c:88"->{ Cell[64716, 2344, 126, 4, 60, "Subsubsection", Evaluatable->False, CellTags->"c:88"]}, "c:89"->{ Cell[66064, 2396, 137, 5, 72, "Subsection", Evaluatable->False, CellTags->"c:89"]}, "c:90"->{ Cell[67664, 2461, 114, 3, 64, "Section", Evaluatable->False, CellTags->"c:90"]}, "c:91"->{ Cell[67803, 2468, 77, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:91"]}, "c:92"->{ Cell[68289, 2488, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:92"]}, "c:93"->{ Cell[69242, 2518, 72, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:93"]}, "c:94"->{ Cell[69339, 2524, 59, 1, 60, "Subsubsection", CellTags->"c:94"]}, "c:95"->{ Cell[70035, 2553, 59, 1, 60, "Subsubsection", CellTags->"c:95"]}, "c:96"->{ Cell[71121, 2594, 59, 1, 60, "Subsubsection", CellTags->"c:96"]}, "c:97"->{ Cell[72009, 2626, 59, 1, 60, "Subsubsection", CellTags->"c:97"]}, "c:98"->{ Cell[73234, 2677, 104, 3, 64, "Section", Evaluatable->False, CellTags->"c:98"]}, "c:99"->{ Cell[73363, 2684, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:99"]}, "c:100"->{ Cell[74272, 2716, 73, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:100"]}, "c:101"->{ Cell[74370, 2722, 52, 1, 60, "Subsubsection", CellTags->"c:101"]}, "c:102"->{ Cell[74543, 2731, 52, 1, 60, "Subsubsection", CellTags->"c:102"]}, "c:103"->{ Cell[74756, 2741, 52, 1, 60, "Subsubsection", CellTags->"c:103"]}, "c:104"->{ Cell[75373, 2768, 101, 3, 64, "Section", Evaluatable->False, CellTags->"c:104"]}, "c:105"->{ Cell[75499, 2775, 78, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:105"]}, "c:106"->{ Cell[76641, 2814, 72, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:106"]}, "c:107"->{ Cell[77386, 2841, 72, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:107"]}, "c:108"->{ Cell[77715, 2857, 73, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:108"]}, "c:109"->{ Cell[77813, 2863, 52, 1, 60, "Subsubsection", CellTags->"c:109"]}, "c:110"->{ Cell[80768, 2957, 52, 1, 60, "Subsubsection", CellTags->"c:110"]}, "relation"->{ Cell[82748, 3035, 120, 3, 64, "Section", Evaluatable->False, CellTags->{"relation", "c:111"}], Cell[91176, 3353, 126, 3, 64, "Section", Evaluatable->False, CellTags->{"relation", "c:119"}], Cell[98922, 3610, 109, 3, 64, "Section", Evaluatable->False, CellTags->{"relation", "c:125"}]}, "c:111"->{ Cell[82748, 3035, 120, 3, 64, "Section", Evaluatable->False, CellTags->{"relation", "c:111"}]}, "c:112"->{ Cell[82893, 3042, 56, 1, 60, "Subsubsection", CellTags->"c:112"]}, "c:113"->{ Cell[84183, 3092, 50, 1, 60, "Subsubsection", CellTags->"c:113"]}, "c:114"->{ Cell[84964, 3121, 73, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:114"]}, "c:115"->{ Cell[85062, 3127, 52, 1, 60, "Subsubsection", CellTags->"c:115"]}, "c:116"->{ Cell[86245, 3166, 52, 1, 60, "Subsubsection", CellTags->"c:116"]}, "c:117"->{ Cell[89316, 3284, 52, 1, 60, "Subsubsection", CellTags->"c:117"]}, "c:118"->{ Cell[90442, 3322, 52, 1, 60, "Subsubsection", CellTags->"c:118"]}, "c:119"->{ Cell[91176, 3353, 126, 3, 64, "Section", Evaluatable->False, CellTags->{"relation", "c:119"}]}, "c:120"->{ Cell[91327, 3360, 56, 1, 39, "Subsubsection", CellTags->"c:120"]}, "c:121"->{ Cell[94219, 3454, 50, 1, 39, "Subsubsection", CellTags->"c:121"]}, "c:122"->{ Cell[94501, 3467, 73, 2, 58, "Subsection", Evaluatable->False, CellTags->"c:122"]}, "c:123"->{ Cell[94599, 3473, 52, 1, 39, "Subsubsection", CellTags->"c:123"]}, "c:124"->{ Cell[96081, 3518, 52, 1, 28, "Subsubsection", CellTags->"c:124"]}, "c:125"->{ Cell[98922, 3610, 109, 3, 64, "Section", Evaluatable->False, CellTags->{"relation", "c:125"}]}, "c:126"->{ Cell[99056, 3617, 56, 1, 39, "Subsubsection", CellTags->"c:126"]}, "c:127"->{ Cell[100568, 3671, 50, 1, 39, "Subsubsection", CellTags->"c:127"]}, "c:128"->{ Cell[101110, 3694, 73, 2, 44, "Subsection", Evaluatable->False, CellTags->"c:128"]}, "c:129"->{ Cell[101208, 3700, 52, 1, 39, "Subsubsection", CellTags->"c:129"]}, "c:130"->{ Cell[103100, 3765, 52, 1, 39, "Subsubsection", CellTags->"c:130"]}, "c:131"->{ Cell[105504, 3852, 102, 3, 64, "Section", Evaluatable->False, CellTags->"c:131"]}, "c:132"->{ Cell[105631, 3859, 56, 1, 60, "Subsubsection", CellTags->"c:132"]}, "c:133"->{ Cell[107004, 3906, 50, 1, 60, "Subsubsection", CellTags->"c:133"]}, "c:134"->{ Cell[107873, 3938, 51, 1, 64, "Subsection", CellTags->"c:134"]}, "c:135"->{ Cell[107949, 3943, 52, 1, 60, "Subsubsection", CellTags->"c:135"]}, "c:136"->{ Cell[109393, 3999, 52, 1, 60, "Subsubsection", CellTags->"c:136"]}, "c:137"->{ Cell[109821, 4019, 52, 1, 60, "Subsubsection", CellTags->"c:137"]}, "lexicographic order"->{ Cell[110226, 4040, 132, 3, 64, "Section", Evaluatable->False, CellTags->{"lexicographic order", "c:138"}]}, "c:138"->{ Cell[110226, 4040, 132, 3, 64, "Section", Evaluatable->False, CellTags->{"lexicographic order", "c:138"}]}, "c:139"->{ Cell[110383, 4047, 56, 1, 60, "Subsubsection", CellTags->"c:139"]}, "c:140"->{ Cell[112800, 4136, 50, 1, 60, "Subsubsection", CellTags->"c:140"]}, "c:141"->{ Cell[113655, 4163, 76, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:141"]}, "c:142"->{ Cell[114432, 4192, 73, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:142"]}, "c:143"->{ Cell[114530, 4198, 73, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:143"]}, "c:144"->{ Cell[117019, 4246, 82, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:144"]}, "c:145"->{ Cell[117906, 4278, 79, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:145"]}, "c:146"->{ Cell[119209, 4308, 114, 3, 64, "Section", Evaluatable->False, CellTags->"c:146"]}, "c:147"->{ Cell[119348, 4315, 78, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:147"]}, "c:148"->{ Cell[120417, 4350, 72, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:148"]}, "c:149"->{ Cell[120909, 4369, 73, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:149"]}, "c:150"->{ Cell[121007, 4375, 52, 1, 70, "Subsubsection", CellTags->"c:150"]}, "c:151"->{ Cell[122460, 4427, 52, 1, 70, "Subsubsection", CellTags->"c:151"]}, "c:152"->{ Cell[124133, 4482, 105, 3, 64, "Section", Evaluatable->False, CellTags->"c:152"]}, "c:153"->{ Cell[124263, 4489, 72, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:153"]}, "c:154"->{ Cell[124968, 4515, 73, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:154"]}, "c:155"->{ Cell[126225, 4563, 99, 3, 64, "Section", Evaluatable->False, CellTags->"c:155"]}, "c:156"->{ Cell[126349, 4570, 78, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:156"]}, "c:157"->{ Cell[127239, 4602, 72, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:157"]}, "c:158"->{ Cell[127485, 4615, 73, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:158"]}, "c:159"->{ Cell[127583, 4621, 52, 1, 70, "Subsubsection", CellTags->"c:159"]}, "c:160"->{ Cell[127859, 4637, 52, 1, 70, "Subsubsection", CellTags->"c:160"]}, "c:161"->{ Cell[128292, 4654, 130, 4, 64, "Section", Evaluatable->False, PageBreakAbove->True, CellTags->"c:161"]}, "c:162"->{ Cell[128447, 4662, 50, 1, 70, "Subsubsection", CellTags->"c:162"]}, "c:163"->{ Cell[129370, 4695, 83, 2, 70, "Subsection", CellTags->"c:163"]}, "c:164"->{ Cell[129478, 4701, 52, 1, 70, "Subsubsection", CellTags->"c:164"]}, "c:165"->{ Cell[130285, 4731, 52, 1, 70, "Subsubsection", CellTags->"c:165"]}, "c:166"->{ Cell[130956, 4758, 98, 3, 64, "Section", Evaluatable->False, CellTags->"c:166"]}, "c:167"->{ Cell[131079, 4765, 56, 1, 39, "Subsubsection", CellTags->"c:167"]}, "c:168"->{ Cell[131841, 4793, 50, 1, 39, "Subsubsection", CellTags->"c:168"]}, "c:169"->{ Cell[132409, 4814, 53, 1, 39, "Subsubsection", CellTags->"c:169"]}, "c:170"->{ Cell[132821, 4831, 51, 1, 44, "Subsection", CellTags->"c:170"]}, "c:171"->{ Cell[132897, 4836, 52, 1, 39, "Subsubsection", CellTags->"c:171"]}, "c:172"->{ Cell[134443, 4891, 52, 1, 39, "Subsubsection", CellTags->"c:172"]}, "c:173"->{ Cell[135402, 4931, 52, 1, 39, "Subsubsection", CellTags->"c:173"]} } *) (*CellTagsIndex CellTagsIndex->{ {"c:1", 136647, 4971}, {"c:2", 136723, 4974}, {"c:3", 136827, 4978}, {"c:4", 136910, 4981}, {"c:5", 136994, 4984}, {"c:6", 137075, 4987}, {"c:7", 137159, 4990}, {"c:8", 137243, 4993}, {"c:9", 137327, 4996}, {"c:10", 137433, 5000}, {"c:11", 137519, 5003}, {"c:12", 137605, 5006}, {"c:13", 137688, 5009}, {"c:14", 137774, 5012}, {"c:15", 137860, 5015}, {"c:16", 137946, 5018}, {"c:17", 138032, 5021}, {"c:18", 138118, 5024}, {"c:19", 138205, 5027}, {"c:20", 138313, 5031}, {"c:21", 138426, 5035}, {"c:22", 138539, 5039}, {"c:23", 138649, 5043}, {"c:24", 138736, 5046}, {"c:25", 138823, 5049}, {"c:26", 138910, 5052}, {"c:27", 139018, 5056}, {"c:28", 139131, 5060}, {"c:29", 139244, 5064}, {"c:30", 139354, 5068}, {"c:31", 139441, 5071}, {"c:32", 139528, 5074}, {"c:33", 139615, 5077}, {"c:34", 139702, 5080}, {"c:35", 139810, 5084}, {"c:36", 139923, 5088}, {"c:37", 140036, 5092}, {"c:38", 140149, 5096}, {"c:39", 140259, 5100}, {"c:40", 140367, 5104}, {"c:41", 140454, 5107}, {"c:42", 140565, 5111}, {"c:43", 140674, 5115}, {"c:44", 140762, 5118}, {"c:45", 140850, 5121}, {"c:46", 140935, 5124}, {"c:47", 141023, 5127}, {"c:48", 141111, 5130}, {"c:49", 141199, 5133}, {"c:50", 141308, 5137}, {"c:51", 141396, 5140}, {"c:52", 141510, 5144}, {"c:53", 141621, 5148}, {"c:54", 141709, 5151}, {"c:55", 141797, 5154}, {"c:56", 141885, 5157}, {"c:57", 141973, 5160}, {"c:58", 142082, 5164}, {"c:59", 142196, 5168}, {"c:60", 142310, 5172}, {"c:61", 142424, 5176}, {"c:62", 142535, 5180}, {"c:63", 142644, 5184}, {"c:64", 142732, 5187}, {"c:65", 142820, 5190}, {"c:66", 142908, 5193}, {"c:67", 142996, 5196}, {"c:68", 143081, 5199}, {"c:69", 143169, 5202}, {"c:70", 143257, 5205}, {"c:71", 143345, 5208}, {"c:72", 143454, 5212}, {"c:73", 143568, 5216}, {"c:74", 143682, 5220}, {"c:75", 143793, 5224}, {"c:76", 143881, 5227}, {"c:77", 143969, 5230}, {"c:78", 144106, 5235}, {"c:79", 144194, 5238}, {"c:80", 144279, 5241}, {"c:81", 144367, 5244}, {"c:82", 144455, 5247}, {"c:83", 144543, 5250}, {"c:84", 144631, 5253}, {"c:85", 144719, 5256}, {"c:86", 144807, 5259}, {"c:87", 144895, 5262}, {"c:88", 145004, 5266}, {"c:89", 145119, 5270}, {"c:90", 145231, 5274}, {"c:91", 145340, 5278}, {"c:92", 145454, 5282}, {"c:93", 145568, 5286}, {"c:94", 145679, 5290}, {"c:95", 145767, 5293}, {"c:96", 145855, 5296}, {"c:97", 145943, 5299}, {"c:98", 146031, 5302}, {"c:99", 146140, 5306}, {"c:100", 146255, 5310}, {"c:101", 146368, 5314}, {"c:102", 146458, 5317}, {"c:103", 146548, 5320}, {"c:104", 146638, 5323}, {"c:105", 146749, 5327}, {"c:106", 146865, 5331}, {"c:107", 146981, 5335}, {"c:108", 147097, 5339}, {"c:109", 147210, 5343}, {"c:110", 147300, 5346}, {"relation", 147393, 5349}, {"c:111", 147740, 5359}, {"c:112", 147865, 5363}, {"c:113", 147955, 5366}, {"c:114", 148045, 5369}, {"c:115", 148158, 5373}, {"c:116", 148248, 5376}, {"c:117", 148338, 5379}, {"c:118", 148428, 5382}, {"c:119", 148518, 5385}, {"c:120", 148643, 5389}, {"c:121", 148733, 5392}, {"c:122", 148823, 5395}, {"c:123", 148936, 5399}, {"c:124", 149026, 5402}, {"c:125", 149116, 5405}, {"c:126", 149241, 5409}, {"c:127", 149331, 5412}, {"c:128", 149422, 5415}, {"c:129", 149536, 5419}, {"c:130", 149627, 5422}, {"c:131", 149718, 5425}, {"c:132", 149830, 5429}, {"c:133", 149921, 5432}, {"c:134", 150012, 5435}, {"c:135", 150100, 5438}, {"c:136", 150191, 5441}, {"c:137", 150282, 5444}, {"lexicographic order", 150387, 5447}, {"c:138", 150524, 5451}, {"c:139", 150661, 5455}, {"c:140", 150752, 5458}, {"c:141", 150843, 5461}, {"c:142", 150960, 5465}, {"c:143", 151074, 5469}, {"c:144", 151191, 5473}, {"c:145", 151308, 5477}, {"c:146", 151425, 5481}, {"c:147", 151537, 5485}, {"c:148", 151654, 5489}, {"c:149", 151771, 5493}, {"c:150", 151885, 5497}, {"c:151", 151976, 5500}, {"c:152", 152067, 5503}, {"c:153", 152179, 5507}, {"c:154", 152296, 5511}, {"c:155", 152410, 5515}, {"c:156", 152521, 5519}, {"c:157", 152638, 5523}, {"c:158", 152755, 5527}, {"c:159", 152869, 5531}, {"c:160", 152960, 5534}, {"c:161", 153051, 5537}, {"c:162", 153191, 5542}, {"c:163", 153282, 5545}, {"c:164", 153370, 5548}, {"c:165", 153461, 5551}, {"c:166", 153552, 5554}, {"c:167", 153663, 5558}, {"c:168", 153754, 5561}, {"c:169", 153845, 5564}, {"c:170", 153936, 5567}, {"c:171", 154024, 5570}, {"c:172", 154115, 5573}, {"c:173", 154206, 5576} } *) (*NotebookFileOutline Notebook[{ Cell[1754, 51, 49, 0, 41, "SmallText"], Cell[CellGroupData[{ Cell[1828, 55, 59, 1, 145, "Title", CellTags->"c:1"], Cell[CellGroupData[{ Cell[1912, 60, 99, 3, 111, "Section", Evaluatable->False, CellTags->"c:2"], Cell[CellGroupData[{ Cell[2036, 67, 54, 1, 60, "Subsubsection", CellTags->"c:3"], Cell[2093, 70, 1283, 32, 296, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[3413, 107, 48, 1, 60, "Subsubsection", CellTags->"c:4"], Cell[3464, 110, 506, 14, 171, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[4007, 129, 49, 1, 64, "Subsection", CellTags->"c:5"], Cell[CellGroupData[{ Cell[4081, 134, 50, 1, 60, "Subsubsection", CellTags->"c:6"], Cell[4134, 137, 284, 10, 46, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[4455, 152, 50, 1, 60, "Subsubsection", CellTags->"c:7"], Cell[4508, 155, 1039, 31, 146, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[5584, 191, 50, 1, 60, "Subsubsection", CellTags->"c:8"], Cell[5637, 194, 715, 22, 171, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[6413, 223, 104, 3, 64, "Section", Evaluatable->False, CellTags->"c:9"], Cell[CellGroupData[{ Cell[6542, 230, 55, 1, 60, "Subsubsection", CellTags->"c:10"], Cell[6600, 233, 661, 26, 71, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[7298, 264, 49, 1, 60, "Subsubsection", CellTags->"c:11"], Cell[7350, 267, 732, 14, 271, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[8119, 286, 50, 1, 64, "Subsection", CellTags->"c:12"], Cell[CellGroupData[{ Cell[8194, 291, 51, 1, 60, "Subsubsection", CellTags->"c:13"], Cell[8248, 294, 123, 3, 46, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[8408, 302, 51, 1, 60, "Subsubsection", CellTags->"c:14"], Cell[8462, 305, 652, 22, 121, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[9151, 332, 51, 1, 60, "Subsubsection", CellTags->"c:15"], Cell[9205, 335, 403, 9, 146, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[9645, 349, 51, 1, 60, "Subsubsection", CellTags->"c:16"], Cell[9699, 352, 171, 4, 71, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[9907, 361, 51, 1, 60, "Subsubsection", CellTags->"c:17"], Cell[9961, 364, 374, 10, 71, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[10372, 379, 51, 1, 60, "Subsubsection", CellTags->"c:18"], Cell[10426, 382, 2005, 63, 296, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[12492, 452, 101, 3, 64, "Section", Evaluatable->False, CellTags->"c:19"], Cell[CellGroupData[{ Cell[12618, 459, 77, 2, 39, "Subsubsection", Evaluatable->False, CellTags->"c:20"], Cell[12698, 463, 860, 25, 246, "Text", Evaluatable->False], Cell[13561, 490, 214, 4, 108, "Input"], Cell[13778, 496, 95, 2, 62, "Input"], Cell[13876, 500, 137, 3, 46, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[14050, 508, 71, 2, 39, "Subsubsection", Evaluatable->False, CellTags->"c:21"], Cell[14124, 512, 637, 20, 171, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[14798, 537, 72, 2, 44, "Subsection", Evaluatable->False, CellTags->"c:22"], Cell[CellGroupData[{ Cell[14895, 543, 51, 1, 39, "Subsubsection", CellTags->"c:23"], Cell[14949, 546, 576, 18, 71, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[15562, 569, 51, 1, 28, "Subsubsection", CellTags->"c:24"], Cell[15616, 572, 1671, 43, 746, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[17324, 620, 51, 1, 28, "Subsubsection", CellTags->"c:25"], Cell[17378, 623, 192, 6, 121, "Text"], Cell[17573, 631, 120, 2, 62, "Input"], Cell[17696, 635, 70, 0, 46, "Text"], Cell[17769, 637, 84, 2, 62, "Input"], Cell[17856, 641, 85, 1, 39, "Input"], Cell[17944, 644, 85, 1, 39, "Input"], Cell[18032, 647, 128, 4, 71, "Text"], Cell[18163, 653, 399, 8, 200, "Input"], Cell[18565, 663, 84, 2, 62, "Input"], Cell[18652, 667, 58, 1, 39, "Input"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[18771, 675, 105, 3, 64, "Section", Evaluatable->False, CellTags->"c:26"], Cell[CellGroupData[{ Cell[18901, 682, 77, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:27"], Cell[18981, 686, 655, 11, 321, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[19673, 702, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:28"], Cell[19747, 706, 437, 13, 196, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[20221, 724, 72, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:29"], Cell[CellGroupData[{ Cell[20318, 730, 51, 1, 60, "Subsubsection", CellTags->"c:30"], Cell[20372, 733, 365, 7, 146, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[20774, 745, 51, 1, 60, "Subsubsection", CellTags->"c:31"], Cell[20828, 748, 948, 22, 246, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[21813, 775, 51, 1, 60, "Subsubsection", CellTags->"c:32"], Cell[21867, 778, 216, 4, 71, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[22120, 787, 51, 1, 60, "Subsubsection", CellTags->"c:33"], Cell[22174, 790, 792, 25, 146, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[23027, 822, 100, 3, 64, "Section", Evaluatable->False, CellTags->"c:34"], Cell[CellGroupData[{ Cell[23152, 829, 77, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:35"], Cell[23232, 833, 676, 20, 171, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[23945, 858, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:36"], Cell[24019, 862, 475, 11, 171, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[24531, 878, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:37"], Cell[24605, 882, 312, 8, 96, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[24954, 895, 72, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:38"], Cell[25029, 899, 2588, 66, 521, "Text", Evaluatable->False], Cell[27620, 967, 125, 4, 46, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[27794, 977, 100, 3, 64, "Section", Evaluatable->False, CellTags->"c:39"], Cell[CellGroupData[{ Cell[27919, 984, 49, 1, 60, "Subsubsection", CellTags->"c:40"], Cell[27971, 987, 482, 14, 171, "Text", Evaluatable->False], Cell[28456, 1003, 502, 16, 246, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[28995, 1024, 72, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:41"], Cell[29070, 1028, 774, 19, 134, "Text"], Cell[29847, 1049, 547, 16, 134, "Text"], Cell[30397, 1067, 1317, 40, 296, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[31763, 1113, 108, 3, 64, "Section", Evaluatable->False, CellTags->"c:42"], Cell[CellGroupData[{ Cell[31896, 1120, 55, 1, 60, "Subsubsection", CellTags->"c:43"], Cell[31954, 1123, 505, 18, 146, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[32496, 1146, 49, 1, 60, "Subsubsection", CellTags->"c:44"], Cell[32548, 1149, 622, 20, 146, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[33207, 1174, 50, 1, 64, "Subsection", CellTags->"c:45"], Cell[CellGroupData[{ Cell[33282, 1179, 51, 1, 60, "Subsubsection", CellTags->"c:46"], Cell[33336, 1182, 747, 32, 171, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[34120, 1219, 51, 1, 60, "Subsubsection", CellTags->"c:47"], Cell[34174, 1222, 421, 12, 121, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[34632, 1239, 51, 1, 60, "Subsubsection", CellTags->"c:48"], Cell[34686, 1242, 135, 5, 96, "Text"], Cell[34824, 1249, 93, 3, 58, "Input"], Cell[34920, 1254, 193, 7, 96, "Text"], Cell[35116, 1263, 45, 0, 38, "Input"], Cell[35164, 1265, 871, 27, 146, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[36096, 1299, 111, 3, 64, "Section", Evaluatable->False, CellTags->"c:49"], Cell[CellGroupData[{ Cell[36232, 1306, 55, 1, 60, "Subsubsection", CellTags->"c:50"], Cell[36290, 1309, 227, 4, 71, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[36554, 1318, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:51"], Cell[36628, 1322, 515, 11, 271, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[37180, 1338, 72, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:52"], Cell[CellGroupData[{ Cell[37277, 1344, 51, 1, 60, "Subsubsection", CellTags->"c:53"], Cell[37331, 1347, 151, 5, 46, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[37519, 1357, 51, 1, 60, "Subsubsection", CellTags->"c:54"], Cell[37573, 1360, 228, 8, 46, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[37838, 1373, 51, 1, 60, "Subsubsection", CellTags->"c:55"], Cell[37892, 1376, 279, 11, 46, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[38208, 1392, 51, 1, 60, "Subsubsection", CellTags->"c:56"], Cell[38262, 1395, 772, 29, 71, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[39095, 1431, 100, 3, 64, "Section", Evaluatable->False, CellTags->"c:57"], Cell[CellGroupData[{ Cell[39220, 1438, 77, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:58"], Cell[39300, 1442, 721, 20, 196, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[40058, 1467, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:59"], Cell[40132, 1471, 475, 11, 171, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[40644, 1487, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:60"], Cell[40718, 1491, 315, 8, 71, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[41070, 1504, 72, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:61"], Cell[41145, 1508, 1487, 48, 246, "Text", Evaluatable->False], Cell[42635, 1558, 4341, 128, 446, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[47025, 1692, 103, 3, 64, "Section", Evaluatable->False, CellTags->"c:62"], Cell[CellGroupData[{ Cell[47153, 1699, 55, 1, 60, "Subsubsection", CellTags->"c:63"], Cell[47211, 1702, 695, 18, 121, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[47943, 1725, 49, 1, 60, "Subsubsection", CellTags->"c:64"], Cell[47995, 1728, 607, 14, 221, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[48639, 1747, 50, 1, 60, "Subsubsection", CellTags->"c:65"], Cell[48692, 1750, 721, 17, 196, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[49450, 1772, 53, 1, 60, "Subsubsection", CellTags->"c:66"], Cell[49506, 1775, 1055, 38, 167, "Text"], Cell[50564, 1815, 125, 3, 46, "Text"], Cell[50692, 1820, 54, 1, 39, "Input"], Cell[50749, 1823, 55, 1, 39, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[50841, 1829, 50, 1, 64, "Subsection", CellTags->"c:67"], Cell[CellGroupData[{ Cell[50916, 1834, 51, 1, 60, "Subsubsection", CellTags->"c:68"], Cell[50970, 1837, 172, 4, 71, "Text"], Cell[51145, 1843, 58, 0, 38, "Input"], Cell[51206, 1845, 87, 3, 46, "Text"], Cell[51296, 1850, 48, 0, 38, "Input"], Cell[51347, 1852, 22, 0, 46, "Text"], Cell[51372, 1854, 39, 0, 38, "Input"], Cell[51414, 1856, 40, 0, 38, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[51491, 1861, 51, 1, 60, "Subsubsection", CellTags->"c:69"], Cell[51545, 1864, 423, 9, 121, "Text"], Cell[51971, 1875, 161, 4, 78, "Input"], Cell[52135, 1881, 52, 0, 46, "Text"], Cell[52190, 1883, 150, 4, 78, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[52377, 1892, 51, 1, 60, "Subsubsection", CellTags->"c:70"], Cell[52431, 1895, 135, 3, 46, "Text"], Cell[52569, 1900, 465, 13, 71, "Text"], Cell[53037, 1915, 429, 13, 71, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[53527, 1935, 112, 3, 64, "Section", Evaluatable->False, CellTags->"c:71"], Cell[CellGroupData[{ Cell[53664, 1942, 77, 2, 39, "Subsubsection", Evaluatable->False, CellTags->"c:72"], Cell[53744, 1946, 860, 25, 246, "Text", Evaluatable->False], Cell[54607, 1973, 208, 4, 108, "Input"], Cell[54818, 1979, 95, 2, 62, "Input"], Cell[54916, 1983, 184, 5, 96, "Text"], Cell[55103, 1990, 114, 2, 62, "Input"], Cell[55220, 1994, 117, 3, 71, "Text"], Cell[55340, 1999, 215, 3, 85, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[55592, 2007, 71, 2, 39, "Subsubsection", Evaluatable->False, CellTags->"c:73"], Cell[55666, 2011, 379, 12, 71, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[56082, 2028, 72, 2, 44, "Subsection", Evaluatable->False, CellTags->"c:74"], Cell[CellGroupData[{ Cell[56179, 2034, 51, 1, 60, "Subsubsection", CellTags->"c:75"], Cell[56233, 2037, 893, 29, 121, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[57163, 2071, 51, 1, 60, "Subsubsection", CellTags->"c:76"], Cell[57217, 2074, 1145, 27, 321, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[58423, 2108, 141, 4, 64, "Section", Evaluatable->False, PageBreakAbove->True, CellTags->"c:77"], Cell[CellGroupData[{ Cell[58589, 2116, 49, 1, 39, "Subsubsection", CellTags->"c:78"], Cell[58641, 2119, 1102, 32, 346, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[59780, 2156, 82, 2, 44, "Subsection", CellTags->"c:79"], Cell[CellGroupData[{ Cell[59887, 2162, 51, 1, 39, "Subsubsection", CellTags->"c:80"], Cell[59941, 2165, 278, 7, 46, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[60256, 2177, 51, 1, 28, "Subsubsection", CellTags->"c:81"], Cell[60310, 2180, 365, 11, 71, "Text"], Cell[60678, 2193, 77, 1, 39, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[60792, 2199, 51, 1, 39, "Subsubsection", CellTags->"c:82"], Cell[60846, 2202, 446, 13, 71, "Text"], Cell[61295, 2217, 79, 1, 39, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[61411, 2223, 51, 1, 39, "Subsubsection", CellTags->"c:83"], Cell[61465, 2226, 458, 13, 71, "Text"], Cell[61926, 2241, 75, 1, 41, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[62038, 2247, 51, 1, 39, "Subsubsection", CellTags->"c:84"], Cell[62092, 2250, 555, 17, 121, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[62684, 2272, 51, 1, 28, "Subsubsection", CellTags->"c:85"], Cell[62738, 2275, 656, 17, 96, "Text"], Cell[63397, 2294, 61, 1, 47, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[63495, 2300, 51, 1, 39, "Subsubsection", CellTags->"c:86"], Cell[63549, 2303, 895, 24, 146, "Text"], Cell[64447, 2329, 65, 1, 47, "Input"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[64573, 2337, 118, 3, 64, "Section", Evaluatable->False, CellTags->"c:87"], Cell[CellGroupData[{ Cell[64716, 2344, 126, 4, 60, "Subsubsection", Evaluatable->False, CellTags->"c:88"], Cell[64845, 2350, 1182, 41, 221, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[66064, 2396, 137, 5, 72, "Subsection", Evaluatable->False, CellTags->"c:89"], Cell[66204, 2403, 1411, 52, 321, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[67664, 2461, 114, 3, 64, "Section", Evaluatable->False, CellTags->"c:90"], Cell[CellGroupData[{ Cell[67803, 2468, 77, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:91"], Cell[67883, 2472, 369, 11, 96, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[68289, 2488, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:92"], Cell[68363, 2492, 842, 21, 246, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[69242, 2518, 72, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:93"], Cell[CellGroupData[{ Cell[69339, 2524, 59, 1, 60, "Subsubsection", CellTags->"c:94"], Cell[69401, 2527, 597, 21, 71, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[70035, 2553, 59, 1, 60, "Subsubsection", CellTags->"c:95"], Cell[70097, 2556, 987, 33, 146, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[71121, 2594, 59, 1, 60, "Subsubsection", CellTags->"c:96"], Cell[71183, 2597, 789, 24, 296, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[72009, 2626, 59, 1, 60, "Subsubsection", CellTags->"c:97"], Cell[72071, 2629, 1102, 41, 171, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[73234, 2677, 104, 3, 64, "Section", Evaluatable->False, CellTags->"c:98"], Cell[CellGroupData[{ Cell[73363, 2684, 71, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:99"], Cell[73437, 2688, 798, 23, 196, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[74272, 2716, 73, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:100"], Cell[CellGroupData[{ Cell[74370, 2722, 52, 1, 60, "Subsubsection", CellTags->"c:101"], Cell[74425, 2725, 81, 1, 40, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[74543, 2731, 52, 1, 60, "Subsubsection", CellTags->"c:102"], Cell[74598, 2734, 121, 2, 40, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[74756, 2741, 52, 1, 60, "Subsubsection", CellTags->"c:103"], Cell[74811, 2744, 429, 15, 71, "Text"], Cell[75243, 2761, 69, 0, 38, "Input"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[75373, 2768, 101, 3, 64, "Section", Evaluatable->False, CellTags->"c:104"], Cell[CellGroupData[{ Cell[75499, 2775, 78, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:105"], Cell[75580, 2779, 1024, 30, 121, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[76641, 2814, 72, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:106"], Cell[76716, 2818, 633, 18, 146, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[77386, 2841, 72, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:107"], Cell[77461, 2845, 217, 7, 46, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[77715, 2857, 73, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:108"], Cell[CellGroupData[{ Cell[77813, 2863, 52, 1, 60, "Subsubsection", CellTags->"c:109"], Cell[77868, 2866, 105, 3, 46, "Text"], Cell[77976, 2871, 42, 0, 38, "Input"], Cell[78021, 2873, 2710, 79, 546, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[80768, 2957, 52, 1, 60, "Subsubsection", CellTags->"c:110"], Cell[80823, 2960, 71, 0, 46, "Text"], Cell[80897, 2962, 45, 0, 38, "Input"], Cell[80945, 2964, 660, 23, 121, "Text"], Cell[81608, 2989, 864, 26, 321, "Text"], Cell[82475, 3017, 115, 6, 118, "Input"], Cell[82593, 3025, 94, 3, 38, "Input"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[82748, 3035, 120, 3, 64, "Section", Evaluatable->False, CellTags->{"relation", "c:111"}], Cell[CellGroupData[{ Cell[82893, 3042, 56, 1, 60, "Subsubsection", CellTags->"c:112"], Cell[82952, 3045, 1194, 42, 171, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[84183, 3092, 50, 1, 60, "Subsubsection", CellTags->"c:113"], Cell[84236, 3095, 691, 21, 221, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[84964, 3121, 73, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:114"], Cell[CellGroupData[{ Cell[85062, 3127, 52, 1, 60, "Subsubsection", CellTags->"c:115"], Cell[85117, 3130, 1091, 31, 171, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[86245, 3166, 52, 1, 60, "Subsubsection", CellTags->"c:116"], Cell[86300, 3169, 262, 7, 121, "Text", Evaluatable->False], Cell[86565, 3178, 242, 4, 108, "Input"], Cell[86810, 3184, 114, 2, 62, "Input"], Cell[86927, 3188, 87, 1, 39, "Input"], Cell[87017, 3191, 119, 5, 46, "Text"], Cell[87139, 3198, 111, 3, 85, "Input"], Cell[87253, 3203, 111, 3, 85, "Input"], Cell[87367, 3208, 111, 3, 85, "Input"], Cell[87481, 3213, 111, 3, 85, "Input"], Cell[87595, 3218, 113, 3, 85, "Input"], Cell[87711, 3223, 113, 3, 85, "Input"], Cell[87827, 3228, 113, 3, 85, "Input"], Cell[87943, 3233, 113, 3, 85, "Input"], Cell[88059, 3238, 113, 3, 85, "Input"], Cell[88175, 3243, 114, 3, 85, "Input"], Cell[88292, 3248, 114, 3, 85, "Input"], Cell[88409, 3253, 806, 21, 221, "Text"], Cell[89218, 3276, 61, 3, 58, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[89316, 3284, 52, 1, 60, "Subsubsection", CellTags->"c:117"], Cell[89371, 3287, 1034, 30, 146, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[90442, 3322, 52, 1, 60, "Subsubsection", CellTags->"c:118"], Cell[90497, 3325, 618, 21, 71, "Text", Evaluatable->False] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[91176, 3353, 126, 3, 64, "Section", Evaluatable->False, CellTags->{"relation", "c:119"}], Cell[CellGroupData[{ Cell[91327, 3360, 56, 1, 39, "Subsubsection", CellTags->"c:120"], Cell[91386, 3363, 1881, 60, 346, "Text", Evaluatable->False], Cell[93270, 3425, 292, 5, 108, "Input"], Cell[93565, 3432, 56, 1, 39, "Input"], Cell[93624, 3435, 477, 11, 200, "Input"], Cell[94104, 3448, 78, 1, 39, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[94219, 3454, 50, 1, 39, "Subsubsection", CellTags->"c:121"], Cell[94272, 3457, 192, 5, 71, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[94501, 3467, 73, 2, 58, "Subsection", Evaluatable->False, CellTags->"c:122"], Cell[CellGroupData[{ Cell[94599, 3473, 52, 1, 39, "Subsubsection", CellTags->"c:123"], Cell[94654, 3476, 1390, 37, 246, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[96081, 3518, 52, 1, 28, "Subsubsection", CellTags->"c:124"], Cell[96136, 3521, 1093, 35, 196, "Text", Evaluatable->False], Cell[97232, 3558, 92, 2, 62, "Input"], Cell[97327, 3562, 1534, 41, 321, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[98922, 3610, 109, 3, 64, "Section", Evaluatable->False, CellTags->{"relation", "c:125"}], Cell[CellGroupData[{ Cell[99056, 3617, 56, 1, 39, "Subsubsection", CellTags->"c:126"], Cell[99115, 3620, 1030, 35, 196, "Text", Evaluatable->False], Cell[100148, 3657, 383, 9, 154, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[100568, 3671, 50, 1, 39, "Subsubsection", CellTags->"c:127"], Cell[100621, 3674, 452, 15, 96, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[101110, 3694, 73, 2, 44, "Subsection", Evaluatable->False, CellTags->"c:128"], Cell[CellGroupData[{ Cell[101208, 3700, 52, 1, 39, "Subsubsection", CellTags->"c:129"], Cell[101263, 3703, 1800, 57, 296, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[103100, 3765, 52, 1, 39, "Subsubsection", CellTags->"c:130"], Cell[103155, 3768, 498, 12, 171, "Text"], Cell[103656, 3782, 144, 2, 62, "Input"], Cell[103803, 3786, 76, 2, 62, "Input"], Cell[103882, 3790, 76, 2, 62, "Input"], Cell[103961, 3794, 76, 2, 62, "Input"], Cell[104040, 3798, 811, 25, 146, "Text"], Cell[104854, 3825, 90, 1, 39, "Input"], Cell[104947, 3828, 159, 5, 46, "Text"], Cell[105109, 3835, 103, 2, 39, "Input"], Cell[105215, 3839, 91, 1, 39, "Input"], Cell[105309, 3842, 55, 0, 46, "Text"], Cell[105367, 3844, 76, 1, 39, "Input"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[105504, 3852, 102, 3, 64, "Section", Evaluatable->False, CellTags->"c:131"], Cell[CellGroupData[{ Cell[105631, 3859, 56, 1, 60, "Subsubsection", CellTags->"c:132"], Cell[105690, 3862, 1028, 32, 171, "Text"], Cell[106721, 3896, 246, 5, 131, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[107004, 3906, 50, 1, 60, "Subsubsection", CellTags->"c:133"], Cell[107057, 3909, 779, 24, 171, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[107873, 3938, 51, 1, 64, "Subsection", CellTags->"c:134"], Cell[CellGroupData[{ Cell[107949, 3943, 52, 1, 60, "Subsubsection", CellTags->"c:135"], Cell[108004, 3946, 1352, 48, 221, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[109393, 3999, 52, 1, 60, "Subsubsection", CellTags->"c:136"], Cell[109448, 4002, 336, 12, 71, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[109821, 4019, 52, 1, 60, "Subsubsection", CellTags->"c:137"], Cell[109876, 4022, 289, 11, 46, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[110226, 4040, 132, 3, 64, "Section", Evaluatable->False, CellTags->{"lexicographic order", "c:138"}], Cell[CellGroupData[{ Cell[110383, 4047, 56, 1, 60, "Subsubsection", CellTags->"c:139"], Cell[110442, 4050, 171, 4, 71, "Text", Evaluatable->False], Cell[110616, 4056, 175, 3, 62, "Input"], Cell[110794, 4061, 1969, 70, 271, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[112800, 4136, 50, 1, 60, "Subsubsection", CellTags->"c:140"], Cell[112853, 4139, 765, 19, 221, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[113655, 4163, 76, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:141"], Cell[113734, 4167, 661, 20, 121, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[114432, 4192, 73, 2, 64, "Subsection", Evaluatable->False, CellTags->"c:142"], Cell[CellGroupData[{ Cell[114530, 4198, 73, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:143"], Cell[114606, 4202, 2376, 39, 621, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[117019, 4246, 82, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:144"], Cell[117104, 4250, 139, 6, 46, "Text", Evaluatable->False], Cell[117246, 4258, 327, 6, 154, "Input"], Cell[117576, 4266, 83, 1, 39, "Input"], Cell[117662, 4269, 207, 4, 85, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[117906, 4278, 79, 2, 60, "Subsubsection", Evaluatable->False, CellTags->"c:145"], Cell[117988, 4282, 1160, 19, 371, "Text", Evaluatable->False] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[119209, 4308, 114, 3, 64, "Section", Evaluatable->False, CellTags->"c:146"], Cell[CellGroupData[{ Cell[119348, 4315, 78, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:147"], Cell[119429, 4319, 951, 26, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[120417, 4350, 72, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:148"], Cell[120492, 4354, 380, 10, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[120909, 4369, 73, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:149"], Cell[CellGroupData[{ Cell[121007, 4375, 52, 1, 70, "Subsubsection", CellTags->"c:150"], Cell[121062, 4378, 1361, 44, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[122460, 4427, 52, 1, 70, "Subsubsection", CellTags->"c:151"], Cell[122515, 4430, 874, 24, 70, "Text"], Cell[123392, 4456, 283, 6, 70, "Text"], Cell[123678, 4464, 394, 11, 70, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[124133, 4482, 105, 3, 64, "Section", Evaluatable->False, CellTags->"c:152"], Cell[CellGroupData[{ Cell[124263, 4489, 72, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:153"], Cell[124338, 4493, 593, 17, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[124968, 4515, 73, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:154"], Cell[125044, 4519, 473, 12, 70, "Text", Evaluatable->False], Cell[125520, 4533, 656, 24, 70, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[126225, 4563, 99, 3, 64, "Section", Evaluatable->False, CellTags->"c:155"], Cell[CellGroupData[{ Cell[126349, 4570, 78, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:156"], Cell[126430, 4574, 772, 23, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[127239, 4602, 72, 2, 70, "Subsubsection", Evaluatable->False, CellTags->"c:157"], Cell[127314, 4606, 134, 4, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[127485, 4615, 73, 2, 70, "Subsection", Evaluatable->False, CellTags->"c:158"], Cell[CellGroupData[{ Cell[127583, 4621, 52, 1, 70, "Subsubsection", CellTags->"c:159"], Cell[127638, 4624, 184, 8, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[127859, 4637, 52, 1, 70, "Subsubsection", CellTags->"c:160"], Cell[127914, 4640, 317, 7, 70, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[128292, 4654, 130, 4, 64, "Section", Evaluatable->False, PageBreakAbove->True, CellTags->"c:161"], Cell[CellGroupData[{ Cell[128447, 4662, 50, 1, 70, "Subsubsection", CellTags->"c:162"], Cell[128500, 4665, 833, 25, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[129370, 4695, 83, 2, 70, "Subsection", CellTags->"c:163"], Cell[CellGroupData[{ Cell[129478, 4701, 52, 1, 70, "Subsubsection", CellTags->"c:164"], Cell[129533, 4704, 715, 22, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[130285, 4731, 52, 1, 70, "Subsubsection", CellTags->"c:165"], Cell[130340, 4734, 555, 17, 70, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[130956, 4758, 98, 3, 64, "Section", Evaluatable->False, CellTags->"c:166"], Cell[CellGroupData[{ Cell[131079, 4765, 56, 1, 39, "Subsubsection", CellTags->"c:167"], Cell[131138, 4768, 601, 17, 196, "Text"], Cell[131742, 4787, 62, 1, 39, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[131841, 4793, 50, 1, 39, "Subsubsection", CellTags->"c:168"], Cell[131894, 4796, 478, 13, 196, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[132409, 4814, 53, 1, 39, "Subsubsection", CellTags->"c:169"], Cell[132465, 4817, 319, 9, 71, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[132821, 4831, 51, 1, 44, "Subsection", CellTags->"c:170"], Cell[CellGroupData[{ Cell[132897, 4836, 52, 1, 39, "Subsubsection", CellTags->"c:171"], Cell[132952, 4839, 1454, 47, 221, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[134443, 4891, 52, 1, 39, "Subsubsection", CellTags->"c:172"], Cell[134498, 4894, 867, 32, 71, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[135402, 4931, 52, 1, 39, "Subsubsection", CellTags->"c:173"], Cell[135457, 4934, 479, 13, 96, "Text"] }, Closed]] }, Closed]] }, Closed]] }, Open ]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)