(************** 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[ 187584, 5989]*) (*NotebookOutlinePosition[ 195656, 6277]*) (* CellTagsIndexPosition[ 194288, 6221]*) (*WindowFrame->Normal*) Notebook[{ Cell["\[Copyright] 2003 K.Sutner", "MR"], Cell[CellGroupData[{ Cell["Relations", "Title", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:1"], Cell[CellGroupData[{ Cell["Relations", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:2"], Cell[CellGroupData[{ Cell[" Motivation", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:3"], Cell["\<\ Sets are the mathematical formalization of collections of objects. \ In order to get interesting models of some aspects of the real world, one \ also needs to express relationships between the objects. Typical examples of such relationships are: \t- less-than relation on integers, \t- divisibility relation on natural numbers, \t- primality of natural numbers, \t- greater-than relation on rational numbers, \t- the \"attends course\" relation for students and courses, \t- the \"is prerequisite\" relation for courses, \t- the \"is a parent of\" relation for humans. As the last few examples already indicate, in CS, database theory deals with \ questions relating to the representation of large classes of objects and \ their mutual relationships. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" The Definition", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:4"], Cell[TextData[{ "Let ", Cell[BoxData[ \(TraditionalForm\`A\)]], " and ", Cell[BoxData[ \(TraditionalForm\`B\)]], " be two sets. A ", StyleBox["relation \[Rho] from ", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`A\)]], " ", StyleBox[" to ", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`B\)]], " is a subset of the Cartesian product ", Cell[BoxData[ \(TraditionalForm\`A\ \[Cross]\ B\)]], ". The idea is that elements ", Cell[BoxData[ \(TraditionalForm\`a\ \[Element] \ A\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\ \[Element] \ B\)]], " are related via ", Cell[BoxData[ \(TraditionalForm\`\(\(\[Rho]\)\(\ \)\)\)]], " iff the pair ", Cell[BoxData[ \(TraditionalForm\`\[LeftAngleBracket]a, b\[RightAngleBracket]\)]], " belongs to \[Rho]. \n\nHere is a typical example: let ", Cell[BoxData[ \(TraditionalForm\`A\ = \ \(B\ = \ \[DoubleStruckCapitalZ]\)\)]], " and let ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ = \ {\ \[LeftAngleBracket]a, b\[RightAngleBracket]\ | \ a\ \ is\ less\ than\ b\ }\)]], ". Then \[Rho] is the standard less-than relation on the integers, ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ = \ {\ \[LeftAngleBracket]0, 1\[RightAngleBracket], \ \[LeftAngleBracket]0, 2\[RightAngleBracket], \ \[Ellipsis], \ \[LeftAngleBracket]1, 2\[RightAngleBracket], \ \[LeftAngleBracket]1, 3\[RightAngleBracket], \ \[Ellipsis], \ \[LeftAngleBracket]i, i + 1\[RightAngleBracket], \ \[Ellipsis]\ }\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "More precisely, these relations are binary relations. In particular for ", Cell[BoxData[ \(TraditionalForm\`A\ = \ B\)]], " we speak of a ", StyleBox["binary relation on ", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`A\)]], ", and ", Cell[BoxData[ \(TraditionalForm\`A\)]], " is called the ", StyleBox["carrier set", FontColor->RGBColor[0, 0, 1]], " or ground set or underlying set of the relation. To express that \ elements ", Cell[BoxData[ \(TraditionalForm\`a\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\)]], " are related by a binary relation \[Rho], one often writes ", Cell[BoxData[ \(TraditionalForm\`\[Rho](a, b)\)]], " rather than the clumsy ", Cell[BoxData[ \(TraditionalForm\`\[LeftAngleBracket]a, b\[RightAngleBracket]\ \ \[Element] \ \[Rho]\)]], ". In fact, for many standard relations one uses infix notation: \n\t", Cell[BoxData[ \(TraditionalForm\`a\ \[Rho]\ b\)]], " or ", Cell[BoxData[ \(TraditionalForm\`\[Rho](a, b)\)]], " or ", Cell[BoxData[ \(TraditionalForm\`\((a, b)\)\ \[Element] \ \ \[Rho]\)]], ". \nFor example, everybody is used to seeing the less-than relation on \ numbers expressed as ", Cell[BoxData[ \(TraditionalForm\`a\ < \ b\)]], " ( but not as ", Cell[BoxData[ \(TraditionalForm\`\(\(<\)\((a, b)\)\)\)]], " or even worse as ", Cell[BoxData[ \(TraditionalForm\`\[LeftAngleBracket]a, b\[RightAngleBracket]\ \[Element] \ < \)]], " ). \n\nAccording to this definition, the collection of all relations from \ ", Cell[BoxData[ \(TraditionalForm\`A\)]], " to ", Cell[BoxData[ \(TraditionalForm\`B\)]], " is simply the power set of ", Cell[BoxData[ \(TraditionalForm\`A\ \[Cross]\ B\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[CellGroupData[{ Cell[TextData[{ Cell[BoxData[ \(TraditionalForm\`n\)]], "-ary Relations" }], "Subsubsection", CellTags->"c:5"], Cell[TextData[{ "On occasion one also has to consider relations between more than two sets. \ This is captured by defining a general ", Cell[BoxData[ \(TraditionalForm\`n\)]], "-ary relation to be as set of the form \n\t", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \ \[SubsetEqual] \ \ \ A\_1\[Cross]\ A\_2\[Cross]\ \[Ellipsis]\ \[Cross]\ A\_n\)]], ".\nThese ", Cell[BoxData[ \(TraditionalForm\`n\)]], "-are relations tend to be less interesting than unary and binary \ relations, but are still important. An example is the relation \n\t", Cell[BoxData[ \(TraditionalForm\`\[Rho](x, y, z)\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\)]], " are the parents of ", Cell[BoxData[ \(TraditionalForm\`z\)]], ".\nThe carrier set here is the set of, say, all mammals." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Very important is the special case ", Cell[BoxData[ \(TraditionalForm\`n = 1\)]], ". In this case we are dealing with a relation on a single set, ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[SubsetEqual] \ A\)]], ". This is called a ", StyleBox["unary relation on ", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`A\)]], ". For example, primality is a unary relation on the natural numbers. Thus, \ by definition, a unary relation on ", Cell[BoxData[ \(TraditionalForm\`A\)]], " is just a subset of ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". Nonetheless, one often thinks about unary relations in terms of a \ predicate, some assertion about elements in ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Implementing relations is actually a rather delicate task, if one \ is serious about being able to handle large relations, and perform \ complicated operations on them. But we will not get involved with database \ theory here, and just suggest of few obvious, and rather brute force \ approaches (brute force from the data structure point of view, the \ mathematics actually works out very nicely). \ \>", "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Implementing Relations", "Subsection", CellTags->"c:6"], Cell[TextData[{ "Since relations are by definition sets of pairs (or, more generally, ", Cell[BoxData[ \(TraditionalForm\`k\)]], "-tuples), we can implement finite relations simply by a list of all these \ pairs. However, this is not necessarily a particular interesting nor useful \ implementation. We will have more to say about implementation questions at \ the end of this notebook, for the time being we just want to have enough \ machinery in place to give some computational examples. " }], "Text"], Cell[CellGroupData[{ Cell["Brute Force List Implementation", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:7"], Cell["\<\ Since by definition a relation is just a subset of a Cartesian \ product we can implement relations directly once we have an implementation of \ sets. More precisely, using lists, we can represent a relation simply by a \ list of pairs. In Mathematica, this might look as follows:\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(A = \(B = {1, 2, 3, 4}\);\)\), "\n", \(\[Rho] = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}\)}], "Input", AspectRatioFixed->True], Cell["\<\ To test whether the relation holds on a given pair of elements can \ then be handled by a membership query.\ \>", "Text"], Cell[BoxData[{ \(MemberQ[\ \[Rho], \ {2, 4}\ ]\), "\n", \(MemberQ[\ \[Rho], \ {2, 5}\ ]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Boolean Functions versus Sets", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:8"], Cell[TextData[{ "In computer scienes, it is very natural to think of a relation not as a \ subset (which is some kind of static object that performs no actions), but as \ a ", StyleBox["Boolean", FontColor->RGBColor[0, 0, 1]], " ", StyleBox["function", FontColor->RGBColor[0, 0, 1]], ": a program which takes as input elements from the sets in question, and \ returns as output True or False, depending on whether the relation holds. A \ relation ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[SubsetEqual] \ A\ \[Cross]\ B\)]], " would be represented by a function ", Cell[BoxData[ \(TraditionalForm\`bool\_\[Rho]\)]], Cell[BoxData[ \(TraditionalForm\`\(\(:\)\(\ \)\(A\ \[Cross]\ B\ \[LongRightArrow]\ \[DoubleStruckCapitalB]\)\)\)]], ".\nThis point of view is taken in programming languages such as \ Mathematica and C." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \({\ 3 < 5, \ 3 < 3\ }\)], "Input", AspectRatioFixed->True], Cell["\<\ One advantage of this approach is that one can easily cope with \ infinite relations as the last example shows: Less works for arbitrary \ integers. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ For large relations, the explicit table approach from the last \ section becomes very cumbersome, and a Boolean function is much preferable. \ Note, however, that it is often impossible to come up with a simple Boolean \ function that represents the relation in question: otherwise database \ programs would be quite superfluous. Instead of storing megabytes of data, \ one could simply store a little piece of code for the function. Also, a drawback of having an implicit representation in the form of a \ Boolean function can make it harder to manipulate relations. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "One strong reason to consider the representation of a relation as a list \ of pairs is visualization. We can draw a picture of the relation by drawing \ two rows of points, representing the elements of ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", and a line indicating that the two elements are related by \[Rho]. This \ will be particularly useful in the next chapter on functions. We start with \ a relation such as ", StyleBox["Less", "MR"], " given by a Boolean function, and convert into the appropriate picture.\n \ Here is the basic instance: " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[\ Less, 5, 1];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "It is helpful to label the points, in particular when ", Cell[BoxData[ \(TraditionalForm\`A\)]], " is a set of integers. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[\ Less, \ 5, 1, LabelGrid \[Rule] Automatic];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Here the relation is \"", Cell[BoxData[ \(TraditionalForm\`\(\(x\)\(\ \)\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(\(y\)\(\ \)\)\)]], " have no common factors\" on ", Cell[BoxData[ \(TraditionalForm\`A\ = \ \([8]\)\)]], ". We use the built-in function ", StyleBox["GCD[x,y]", "MR"], " to determine whether there are common factors. " }], "Text"], Cell[BoxData[ \(\(PlotRelation[\ GCD[#1, #2] == 1 &, 8, 1, LabelGrid \[Rule] Automatic];\)\)], "Input", AspectRatioFixed->True], Cell["Too many elements are related. Here is the complement.", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[\ GCD[#1, #2] =!= 1 &, 8, 1, LabelGrid \[Rule] Automatic];\)\)], "Input", AspectRatioFixed->True], Cell["And the complement after removal of the identity relation. ", "Text"], Cell[BoxData[ \(\(PlotRelation[\ \((GCD[#1, #2] =!= 1\ && \ #1 != #2)\) &, 8, 1, LabelGrid \[Rule] Automatic];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "The original relation on domain ", Cell[BoxData[ \(TraditionalForm\`A\ = \ \([25]\)\)]], ". " }], "Text"], Cell[BoxData[ \(\(Block[{Automata`automata`$deffatline = 0.000}, \n PlotRelation[\ GCD[#1, #2] > 1 &, 25\ ]];\)\)], "Input", AspectRatioFixed->True], Cell["Well, at least it's a pretty picture. ", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Boolean Matrices", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:9"], Cell[TextData[{ "Lastly, a representation that is really custom designed to provide visual \ information to a human being, though it actually will turn out to have some \ nice mathematical properties, too. Suppose we have a binary relation \[Rho] \ on some finite set ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", and fix an enumeration ", Cell[BoxData[ \(TraditionalForm\`A\ = \ {a\_1, a\_2, ... , a\_n}\)]], " of this set. Then we can represent a binary relation \[Rho] on ", Cell[BoxData[ \(TraditionalForm\`A\)]], " by an ", Cell[BoxData[ \(TraditionalForm\`n\ \[Cross]\ n\)]], " Boolean valued matrix ", Cell[BoxData[ \(TraditionalForm\`M\_\[Rho]\)]], " defined by ", Cell[BoxData[ FormBox[ RowBox[{ FormBox[\(\(\(M\_\[Rho]\)(i, j)\)\(\ \)\(=\)\(\ \)\(True\)\(\ \ \)\), "TraditionalForm"], "iff", " ", \(a\_i\), " ", "\[Rho]", " ", \(a\_j\)}], TraditionalForm]]], ", and ", Cell[BoxData[ FormBox[ RowBox[{ FormBox[\(\(\(M\_\[Rho]\)(i, j)\)\(\ \)\(=\)\(\ \)\(False\)\(\ \ \)\), "TraditionalForm"], "iff", " ", \(\[Not] \ a\_i\ \[Rho]\ a\_j\)}], TraditionalForm]]], ".\n\nWe can compute this matrix with the following function ", StyleBox["RelationToMatrix[\[Rho],A]", "MR"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ RelationToMatrix[A_List,\[Rho]_]:= \tWith[{n=Length[A]},Table[\[Rho][A\[LeftDoubleBracket]i\[RightDoubleBracket],\ A\[LeftDoubleBracket]j\[RightDoubleBracket]],{i,n},{j,n}]];\ \>", "Program", AspectRatioFixed->True], Cell[TextData[{ "Here, we assume that the relation is originally given as a Boolean \ function ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\)]], " (this is very convenient for doing calculations in Mathematica). Think \ about how to convert a relation given by a list of pairs. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(MatrixForm[RelationToMatrix[5, Less]]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "To get a better readable table, we take the liberty to identify the \ Boolean values ", StyleBox["True", "MR"], " and ", StyleBox["False", "MR"], " with the integers 1 and 0. As pointed out previously, that confuses the \ type information, but it is often very helpful in programming. In C, for \ example, there is no extra type for Booleans in the first place, one has to \ use integers to represent true and false. The corresponding function ", StyleBox["RelationToMatrix[A,\[Rho]]", "MR"], " is already defined in the ", StyleBox["Automata", "MR"], " package." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(MatrixForm[RelationToMatrix[5, Less]]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "And now, we can pipe this 0/1-matrix through a plotting function ", StyleBox["PlotMatrix", "MR"], " to get a picture. Some first examples, we will see more in a while. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotMatrix[RelationToMatrix[5, Less], GridLines \[Rule] True];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotMatrix[RelationToMatrix[5, LessEqual], GridLines \[Rule] True];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotMatrix[RelationToMatrix[5, Greater], GridLines \[Rule] True];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Here is the relation \"x is divisible by y\", on domain ", Cell[BoxData[ \(TraditionalForm\`\([50]\)\)]], ". " }], "Text"], Cell[BoxData[ \(\(\(\ \)\(PlotMatrix[RelationToMatrix[50, Mod[#1, #2] == 0 &], GridLines \[Rule] True];\)\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "An again the no-common-factor relation, on domain ", Cell[BoxData[ \(TraditionalForm\`\([50]\)\)]], ". " }], "Text"], Cell[BoxData[ \(\(PlotMatrix[RelationToMatrix[\ 50, \ GCD[#1, #2] == 1 &\ ], GridLines \[Rule] True];\)\)], "Input", AspectRatioFixed->True], Cell["\<\ In a moment, when we discuss operations on relations, and \ properties of relations, it will be a good exercise to determine how, say, \ the properties translate into pictures. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Operations on Relations", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:10"], Cell[TextData[{ "Relations are a description of relationships that hold between objects, \ and so have a fairly complicated type. However, we can think of relations as \ basic objects (sets of a certain type), and try to develop some useful \ operations on them. \nIn the following, we will mostly deal with binary \ operations of a fixed set ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[CellGroupData[{ Cell["Empty, Identity and Universal Relation", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:11"], Cell[TextData[{ "OK, it's trivial, but there are always three special binary relations for \ every ground set ", Cell[BoxData[ \(TraditionalForm\`A\)]], ": \n\[Bullet] the ", StyleBox["empty relation", FontColor->RGBColor[0, 0, 1]], ", that relates no one to no one, \n\[Bullet] the ", StyleBox["identity relation", FontColor->RGBColor[0, 0, 1]], ", that relates a only to a, and no one else, and \n\[Bullet] the ", StyleBox["universal relation", FontColor->RGBColor[0, 0, 1]], ", that relates everyone to everyone. \nWe will write ", Cell[BoxData[ \(TraditionalForm\`E\_A\)]], ", ", Cell[BoxData[ \(TraditionalForm\`Id\_A\)]], ", and ", Cell[BoxData[ \(TraditionalForm\`U\_A\)]], " for these relations. Thus,\n\n\t", Cell[BoxData[ \(TraditionalForm\`E\_A = \ \[EmptySet]\)]], ", ", Cell[BoxData[ \(TraditionalForm\`Id\_A = \ {\ \[LeftAngleBracket]a, a\[RightAngleBracket]\ | \ a\ \[Element] \ A\ }\)]], ", and ", Cell[BoxData[ \(TraditionalForm\`U\_A = \ {\ \[LeftAngleBracket]a, b\[RightAngleBracket]\ | \ a, \ b\ \[Element] \ A\ }\)]], ". \n" }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Boolean Operations", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:12"], Cell[TextData[{ "Since binary relations are special sets (subsets of the Cartesian product \ ", Cell[BoxData[ \(TraditionalForm\`A\ \[Cross]\ A\)]], "), we can apply all the standard operations knows on sets to them: ", StyleBox["union", FontColor->RGBColor[0, 0, 1]], ", ", StyleBox["intersection", FontColor->RGBColor[0, 0, 1]], ", ", StyleBox["complement", FontColor->RGBColor[0, 0, 1]], ". More precisely, given two relations \[Rho] and \[Sigma] we can form new \ relations \n\t", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \ \[Union] \ \[Sigma]\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[Intersection] \ \[Sigma]\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ - \ \[Sigma]\)]], ". \nThis corresponds to the logical operations Or, And, and Not. For \ example, letting ", Cell[BoxData[ \(TraditionalForm\`\[Tau]\ = \ \(\(\[Rho]\)\(\ \)\(\[Union]\)\(\ \)\(\ \[Sigma]\)\(\ \)\)\)]], " we have: ", Cell[BoxData[ \(TraditionalForm\`\[Tau](x, y)\)]], " holds iff ", Cell[BoxData[ \(TraditionalForm\`\[Rho](x, y)\)]], " holds or ", Cell[BoxData[ \(TraditionalForm\`\[Sigma](x, y)\)]], " holds. \nAn important special case is ", Cell[BoxData[ \(TraditionalForm\`\[Tau]\ = \ U\_A - \ \[Rho]\)]], ", the negation (or complement) of \[Rho], i.e., ", Cell[BoxData[ \(TraditionalForm\`\[Tau](x, y)\)]], " holds iff ", Cell[BoxData[ \(TraditionalForm\`\[Rho](x, y)\)]], " fails to hold. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "We write ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^-\)\)]], " for ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(U\_A - \ \[Rho]\)\)\)]], ".\n\n", StyleBox["Examples:", FontWeight->"Bold"], " \nThe complement of Less is GreaterEqual. \nThe complement of the empty \ relation is the universal relation.\nThe complement of the identity relations \ is the \"not-equal\" relation. \nThe complement of \"is parent of\" is \"is \ not parent of\". Duh.\nThe complement of ", Cell[BoxData[ \(TraditionalForm\`U\_A\)]], " is ", Cell[BoxData[ \(TraditionalForm\`\[EmptySet]\_A\)]], ".\n\n", StyleBox["Lemma:", FontWeight->"Bold"], "\n\[Bullet] ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^--\) = \ \[Rho]\)]], "\n\[Bullet] ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^-\)\ \[Union] \ \[Sigma]\^\(\(-\)\(\ \)\) \ = \ \(\((\[Rho]\ \[Intersection] \ \[Sigma])\)\^-\)\)]], "\n\[Bullet] ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[Intersection] \ \((\ \[Sigma]\ \[Union] \ \ \[Tau]\ )\)\ = \ \((\ \[Rho]\ \[Intersection] \ \[Sigma]\ )\)\ \[Union] \ \ \((\ \[Rho]\ \[Intersection] \ \[Tau]\ )\)\)]], "\n" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Again the relation \"", Cell[BoxData[ \(TraditionalForm\`\(\(x\)\(\ \)\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(\(y\)\(\ \)\)\)]], " have no common factors\" on ", Cell[BoxData[ \(TraditionalForm\`A\ = \ \([8]\)\)]], ". " }], "Text"], Cell[BoxData[{ \(Clear[\[Rho]]\), "\n", \(\(\[Rho][x_, y_]\ := \ GCD[x, y] == 1;\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[\ \[Rho], 8, 1, LabelGrid \[Rule] Automatic];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Too many elements are related. Here is the complement ", Cell[BoxData[ \(TraditionalForm\`U\_A\ - \ \[Rho]\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[\ Not[\[Rho][#1, #2]] &, 8, 1, LabelGrid \[Rule] Automatic];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "And the complement after removal of the identity relation, ", Cell[BoxData[ \(TraditionalForm\`\((U\_A\ - \ \[Rho])\)\ \ - \ Id\_A\)]], "." }], "Text"], Cell[BoxData[ \(\(PlotRelation[\ \((Not[\[Rho][#1, #2]] \[And] \ #1 \[NotEqual] #2)\) \ &, 8, 1, LabelGrid \[Rule] Automatic];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "The complement intersected with the less-than relation ", Cell[BoxData[ FormBox[ RowBox[{" ", FormBox[\(\(\((U\_A\ - \ \[Rho])\)\(\ \ \)\(\[Intersection]\)\)\(\ \ \)\(<\)\), "TraditionalForm"]}], TraditionalForm]]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[\ \((Not[\[Rho][#1, #2]] \[And] \ #1 < #2)\) &, 8, 1, LabelGrid \[Rule] Automatic];\)\)], "Input", AspectRatioFixed->True], Cell["The complement on a somewhat larger carrier set.", "Text"], Cell[BoxData[ \(\(Block[{Automata`automata`$deffatline = 0.001}, \n\t PlotRelation[Not[\[Rho][#1, #2]] &, 25\ ]];\)\)], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Converse Relation", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:13"], Cell[TextData[{ "More interesting than Boolean operations are operations that apply \ specifically to relations. Here is the first example. \nFor any relation \ \[Rho], define its ", StyleBox["converse", FontColor->RGBColor[0, 0, 1]], " relation ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^c\)]], " by ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^c\)(x, y)\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\[Rho](y, x)\)]], ". \n\n", StyleBox["Examples", FontWeight->"Bold"], ": \nThe converse of Less is Greater. \nThe converse of \"is parent of\" is \ \"is child of\". \nThe converse of ", Cell[BoxData[ \(TraditionalForm\`U\_A\)]], " is ", Cell[BoxData[ \(TraditionalForm\`U\_A\)]], ", and likewise for ", Cell[BoxData[ \(TraditionalForm\`Id\_A\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\[EmptySet]\_A\)]], ".\n\n", StyleBox["Lemma: ", FontWeight->"Bold"], " ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^\(c\[VeryThinSpace]c\)\ = \ \[Rho]\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["The pictures of a relation and its converse are symmetric.", "Text"], Cell[BoxData[{ \(\(gr1\ = PlotRelation[\ Less, 8, 1, DisplayFunction \[Rule] Identity];\)\), "\n", \(\(gr2\ = PlotRelation[Greater, 8, 1, DisplayFunction \[Rule] Identity];\)\), "\n", \(\(ShowArray[{gr1, gr2}];\)\)}], "Input", AspectRatioFixed->True], Cell["\<\ This is even easier to see in the matrix representation. On the \ left is Less, on the right Greater.\ \>", "Text"], Cell[BoxData[{ \(\(gr1\ = \ PlotMatrix[RelationToMatrix[\ 8, Less], \[IndentingNewLine]\t GridLines \[Rule] True, DisplayFunction \[Rule] Identity];\)\), "\n", \(\(gr2\ = \ \ PlotMatrix[ RelationToMatrix[\ 8, Greater], \[IndentingNewLine]\t GridLines \[Rule] True, DisplayFunction \[Rule] Identity];\)\), "\n", \(\(ShowArray[{gr1, gr2}];\)\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Composition of Relations", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:14"], Cell[TextData[{ "Suppose we have two binary relations \[Rho] and \[Sigma] on ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". We can combine these relations into a new relation ", Cell[BoxData[ \(TraditionalForm\`\[Tau]\ = \ \[Rho]\ \[SmallCircle]\ \[Sigma]\)]], ", the ", StyleBox["composition", FontColor->RGBColor[0, 0, 1]], " of \[Rho] and \[Sigma], defined as follows.\n\n\t", Cell[BoxData[ \(TraditionalForm\`\(\[Tau](x, y)\)\ \ \ iff\ \ \(\[Exists] \ z\ \[Element] \ A\ \((\ \ \[Rho](x, z)\ \ \[And] \ \ \[Sigma](z, \ y)\ )\)\)\)]], "\n\nThe intermediate element ", Cell[BoxData[ \(TraditionalForm\`z\)]], " in the last definition is sometimes called a ", StyleBox["witness", FontColor->RGBColor[0, 0, 1]], " for ", Cell[BoxData[ \(TraditionalForm\`x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\)]], ". \nNote that this definition is a bit more complicated than the previous \ ones, since there is an existential quantifier: \"there is some ", Cell[BoxData[ \(TraditionalForm\`z\)]], " \[Ellipsis]\". Computationally this is a warning signal, in order to \ compute compositions we will have to find the witness, or determine that \ there isn't one. \nTo us, this notion of composition is of use mostly when \ \[Rho] and \[Sigma] are the same. In this case one writes ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^2\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^3\)]], ", and so forth. These relations are called the ", StyleBox["powers of ", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`\[Rho]\)]], ", since one can think of composition as some kind of multiplication. More \ precisely, we can define\n\n\t", Cell[BoxData[ FormBox[GridBox[{ {\(\[Rho]\^0\), "=", \(Id\_A\)}, {\(\[Rho]\^\(n + 1\)\), "=", \(\[Rho]\ \[SmallCircle]\ \[Rho]\^n\)} }], TraditionalForm]]] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Examples", FontWeight->"Bold"], ":\nThe composition of Less with itself on the integers is the relation \ \"smaller by at least two\". In fact, one can see that \n\n\t", Cell[BoxData[ \(TraditionalForm\`\(\(Less\^k\)(x, y)\)\ \ \ iff\ \ \ x\ \[LessEqual] \ y\ - \ k\)]], ". \n\nNote, though, that on the rationals the composition of Less with \ itself is simply Less: the rationals are dense, for any ", Cell[BoxData[ \(TraditionalForm\`x\ < \ y\)]], " there is a ", Cell[BoxData[ \(TraditionalForm\`z\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`x\ < \ z\ < \ y\)]], ". So, for ", Cell[BoxData[ \(TraditionalForm\`\(\(A\)\(\ \)\(=\)\(\ \ \)\(\[DoubleStruckCapitalQ]\)\(\ \)\)\)]], " we have ", Cell[BoxData[ \(TraditionalForm\`Less\^2\ = \ Less\)]], ". \nThe composition of \"divides\" on the integers with itself is again \ \"divides\". \nThe composition of \"is parent of\" with itself is \"is \ grandparent of\". \n" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Lemma", FontWeight->"Bold"], ": For any relation ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\)]], " on ", Cell[BoxData[ \(TraditionalForm\`A\)]], ": ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[SmallCircle]\ Id\_A = \ \(Id\_A\ \[SmallCircle]\ \[Rho]\ = \ \[Rho]\)\)]], ". \nFurthermore, ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[SmallCircle]\ \[EmptySet]\_A = \ \(\ \[EmptySet]\_A\ \[SmallCircle]\ \[Rho]\ = \ \[EmptySet]\)\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Lemma", FontWeight->"Bold"], ": Composition of relations is associative: \n", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[SmallCircle]\ \((\ \[Sigma]\ \ \[SmallCircle]\ \[Tau]\ )\)\ = \ \((\ \[Rho]\ \[SmallCircle]\ \[Sigma]\ )\)\ \ \[SmallCircle]\ \[Tau]\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Lemma", FontWeight->"Bold"], ": \n", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^n\[SmallCircle]\ \[Rho]\^m = \ \[Rho]\^\(n + \ m\)\)]], "\n", Cell[BoxData[ \(TraditionalForm\`\((\[Rho]\^n)\)\^m = \ \ \[Rho]\^\(n\[CenterDot]m\)\)]] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ The first claim simply says that the identity relation behaves like \ a 1 if we think of composition as some kind of multiplication. The second \ claim says that the empty relation behaves like 0, the third says that it \ does not matter which order we choose for a sequence of relational \ compositions, and the last two look just like the laws for exponentiation of \ numbers.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Lemma", FontWeight->"Bold"], ": ", Cell[BoxData[ FormBox[ RowBox[{" ", RowBox[{"(", " ", RowBox[{\(\[Sigma]\ \[SmallCircle]\ \[Tau]\), " ", FormBox[\(\()\^\(\(c\)\(\ \)\)\)\(=\)\(\ \)\(\(\(\[Tau]\)\(\ \)\ \)\^c\ \[SmallCircle]\ \[Sigma]\^\(\(\ \)\(c\)\)\)\), "TraditionalForm"]}]}]}], TraditionalForm]]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "How can we use pictures to visualize relational composition? For example, \ for ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^2\)]], " we could draw two of our old dot-and-line pictures right next to each \ other, and merge the two columns of dots in the middle. The following picture \ shows for example that 1 and 3 are related in ", Cell[BoxData[ \(TraditionalForm\`\( < \^2\)\)]], " on ", Cell[BoxData[ \(TraditionalForm\`A\ = \ {1, 2, 3, 4, 5}\)]], ", but 1 and 2 are not: there is no path from node 1 on the left to node 2 \ on the right. \n(The light gray lines indicate the relation in each block, \ the black lines from the left colum to the right column connect pairs of \ elements related in ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^2\)]], "). " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[\ Less, 5, 2, LabelGrid \[Rule] Automatic, Full \[Rule] True];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[\ Less, 5, 3, LabelGrid \[Rule] Automatic, Full \[Rule] True];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "In ", Cell[BoxData[ \(TraditionalForm\`Less\^4\)]], " only one pair remains related on ", Cell[BoxData[ \(TraditionalForm\`\([5]\)\)]], "." }], "Text"], Cell[BoxData[ \(\(PlotRelation[\ Less, 5, 4, LabelGrid \[Rule] Automatic, Full \[Rule] True];\)\)], "Input", AspectRatioFixed->True], Cell["If we start with the weak order, nothing new happens. ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[\ LessEqual, 5, 2, LabelGrid \[Rule] Automatic, Full \[Rule] True];\)\)], "Input", AspectRatioFixed->True], Cell["Here is a relation based on modular counting. ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[\[Rho]]\), "\n", \(\(\[Rho][x_, y_] := y == Mod[x + 1, 5];\)\), "\n", \(\(\[Rho][0, 0] = True;\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[\ \[Rho], \ Range[0, 4], 1, LabelGrid \[Rule] Range[0, 4], Full \[Rule] True];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[\ \[Rho], \ Range[0, 4], 5, LabelGrid \[Rule] Range[0, 4], DoTrace -> {1}, Full \[Rule] True];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[\ \[Rho], \ Range[0, 4], 5, LabelGrid \[Rule] Range[0, 4], DoTrace -> {2}, Full \[Rule] True];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "The pictures show that ", Cell[BoxData[ \(TraditionalForm\`0\ \[Rho]\^5\ y\)]], " for all ", Cell[BoxData[ \(TraditionalForm\`y\ \[Element] \ A\)]], ". However, ", Cell[BoxData[ \(TraditionalForm\`1\ \[Rho]\^5\ y\)]], " holds only for ", Cell[BoxData[ \(TraditionalForm\`y = 0, 1\)]], ". \nHow about the matrix pictures here? First, ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\)]], " and then ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^5\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(Mr\ = \ RelationToMatrix[Range[0, 4], \[Rho]];\)\), "\n", \(\(PlotMatrix[Mr, GridLines \[Rule] True];\)\)}], "Input"], Cell[BoxData[ \(\(PlotMatrix[Sign@MatrixPower[Mr, 5], GridLines -> True];\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Projections, Permutations", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:15"], Cell[TextData[{ "The last two operations are really somewhat technical, and become really \ important in a strict formal treatment of relations. We include them here \ mostly to point to yet another problem one has to face when implementing \ relations. \nFor any ", Cell[BoxData[ \(TraditionalForm\`\((n + 1)\)\)]], "-relation \[Rho] on ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", define its ", StyleBox["projection", FontColor->RGBColor[0, 0, 1]], " \[Sigma] with respect to ", Cell[BoxData[ \(TraditionalForm\`p\ \[Element] \ A\)]], ", an ", Cell[BoxData[ \(TraditionalForm\`n\)]], "-ary relation, by ", Cell[BoxData[ \(TraditionalForm\`\(\[Sigma](x\_1, \[Ellipsis], \ x\_n)\)\ \ \ iff\ \ \(\[Rho](p, x\_1, \[Ellipsis], \ x\_n)\)\)]], ".\nSee the example on a registrar database below. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Suppose we have an ", Cell[BoxData[ \(TraditionalForm\`n\)]], "-relation ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\[Rho](p, x\_1, \[Ellipsis], \ x\_n)\)\)\)]], " on ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", and let ", Cell[BoxData[ \(TraditionalForm\`y\_1, y\_2, \[Ellipsis], y\_n\)]], " be a rearrangement of ", Cell[BoxData[ \(TraditionalForm\`x\_1, \[Ellipsis], \ x\_n\)]], ". Then we can define a ", StyleBox["permutation", FontColor->RGBColor[0, 0, 1]], " of \[Rho] by \n ", Cell[BoxData[ \(TraditionalForm\`\(\[Sigma](y\_1, \[Ellipsis], \ y\_n)\)\ \ \ iff\ \ \(\[Rho](x\_1, \[Ellipsis], \ x\_n)\)\)]], ".\t\nFor example, for ", Cell[BoxData[ \(TraditionalForm\`n = 2\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\_1 = \ x\_2\)]], ", ", Cell[BoxData[ \(TraditionalForm\`y\_2 = \ x\_1\)]], " this is just the converse. In general, this operation addresses the \ issue of listing the arguments in different orders. Clearly, moving the \ arguments does not affect the relation per se, but it produces a different \ data structure for each rearrangement of the arguments. \n\nWith the example \ from above, ", Cell[BoxData[ \(TraditionalForm\`\[Rho](x, y, z)\)]], " : \"", Cell[BoxData[ \(TraditionalForm\`x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\)]], " are the parents of ", Cell[BoxData[ \(TraditionalForm\`z\)]], "\" we could produce a new relation ", Cell[BoxData[ \(TraditionalForm\`\(\[Sigma](x, y, z)\)\ \ iff\ \ \(\[Rho](x, z, y)\)\)]], ", meaning that \"", Cell[BoxData[ \(TraditionalForm\`x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`z\)]], " are the parents of ", Cell[BoxData[ \(TraditionalForm\`y\)]], "\". Clearly, this is essentially the same relation, but there is a subtle \ difference. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Properties of Relations", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:16"], Cell["\<\ The relations one encounters typically in mathematics and computer \ science have a number of special properties. We now list the most important \ ones of these properties.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[CellGroupData[{ Cell["Reflexivity", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:17"], Cell[TextData[{ "A relation \[Rho] is ", StyleBox["reflexive", FontColor->RGBColor[0, 0, 1]], " iff ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ x\ \[Element] \ A\ \((\ \ x\ \[Rho]\ x\ )\)\)]], ". \nA relation \[Rho] is ", StyleBox["irreflexive", FontColor->RGBColor[0, 0, 1]], " iff ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ x\ \[Element] \ A\ \((\ \ \[Not] \ x\ \[Rho]\ x\ )\)\)]], ". \nIn other words, \[Rho] is reflexive iff the identity relation ", Cell[BoxData[ \(TraditionalForm\`Id\_A\)]], " is contained in \[Rho], ", Cell[BoxData[ \(TraditionalForm\`Id\_\(\(A\)\(\ \)\) \[SubsetEqual] \ \[Rho]\)]], ". Likewise, \[Rho] is irreflexive iff ", Cell[BoxData[ \(TraditionalForm\`Id\_A\ \[Intersection] \ \[Rho]\ = \ \ \[EmptySet]\)]], ". Note that \"not reflexive\" and \"irreflexive\" is not the same. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Examples", FontWeight->"Bold"], ": \nThe identity relation is the smallest reflexive relation. \nThe \ LessEqual relation is reflexive, but Less is not. \nThe \"is parent of\" \ relations is irreflexive. \nThe empty relation ", Cell[BoxData[ \(TraditionalForm\`E\_A\)]], " is irreflexive, but both ", Cell[BoxData[ \(TraditionalForm\`Id\_A\)]], " and ", Cell[BoxData[ \(TraditionalForm\`U\_A\)]], " are reflexive. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["The Reflexive Closure", FontWeight->"Bold"], "\nSometimes it is more convenient to work with a reflexive version of a \ relation. The ", StyleBox["reflexive closure of \[Rho]", FontColor->RGBColor[0, 0, 1]], " is the least relation that contains \[Rho] and is reflexive. If we think \ of relations as sets (subsets fo the Cartesian product ", Cell[BoxData[ \(TraditionalForm\`A\ \[Cross]\ A\)]], "), this simply means the reflexive closure of \[Rho] is ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[Union] \ Id\_A\)]], ". \nLikewise, if one prefers a irreflexive version, one can consider ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ - \ Id\_A\)]], ". The standard example for this phenomenon is ", Cell[BoxData[ \(TraditionalForm\` < \)]], ", the ordinary less-than relation versus ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], ", the usual less-than-or-equal relation. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Closures in general are an extremely important concept. You have a \ relation that fails to have certain property, and you want to add to it as \ little as possible in order to get the desired property. In other words, the \ symmetric closure of a relation \[Rho] is the smallest relation \[Sigma] \ that contains \[Rho] and is already reflexive. Smallest here means that it \ is a subset of any other relation with these properties. More about this \ topic later. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ In the plot of a relation, reflixivity is indicated by horizontal \ lines starting from each dot. In the matrix picture, reflexivity is indicated \ by the diagonal.\ \>", "Text"], Cell[BoxData[ \(\(PlotRelation[\ \ LessEqual, \ 8, \ 4\ ];\)\)], "Input"], Cell[BoxData[ \(\(PlotMatrix[\ RelationToMatrix[\ 8, LessEqual\ ], \ GridLines \[Rule] \ True];\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Symmetry and Anti-Symmetry", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:18"], Cell[TextData[{ "A relation \[Rho] is ", StyleBox["symmetric ", FontColor->RGBColor[0, 0, 1]], " iff ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ x, y\ \[Element] \ A\ \((\ \ x\ \[Rho]\ y\ \[DoubleLongRightArrow]\ y\ \[Rho]\ x\ )\)\)]], ". \nA relation \[Rho] is ", StyleBox["asymmetric ", FontColor->RGBColor[0, 0, 1]], " iff ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ x, y\ \[Element] \ A\ \((\ \ x\ \[Rho]\ y\ \[DoubleLongRightArrow]\ \(\[Not] y\ \[Rho]\ \ x\)\ )\)\)]], ". \nA relation \[Rho] is ", StyleBox["antisymmetric ", FontColor->RGBColor[0, 0, 1]], " iff ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ x, y\ \[Element] \ A\ \((\ \ x\ \[Rho]\ y\ \[And] y\ \[Rho]\ x\ \ \[DoubleLongRightArrow]\ x\ = \ y\ )\)\)]], ". \n\nIn other words, in a symmetric relation the converse relation ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^c\)]], " is contained in \[Rho]. Equivalently, ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \ \)\(\[Rho]\ = \ \[Rho]\^c\)\)\)]], ". In a asymmtric relation we have ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[Intersection] \ \[Rho]\^c = \ \[EmptySet]\ \)]], " and in an antisymmetric relation we have ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[Intersection] \ \[Rho]\^c \[SubsetEqual] \ \ Id\_A\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Examples", FontWeight->"Bold"], ": \nThe identity relation ", Cell[BoxData[ \(TraditionalForm\`Id\_A\)]], " is symmetric, as is ", Cell[BoxData[ \(TraditionalForm\`U\_A\)]], ". \nThe LessEqual relation is not symmetric but antisymmetric. \nThe \"is \ parent of\" relation is asymmetric. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "The ", StyleBox["symmetric closure of \[Rho]", FontColor->RGBColor[0, 0, 1]], " is the least relation that contains \[Rho] and is symmetric. As sets, \ this simply means the reflexive closure of \[Rho] is ", StyleBox[" ", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[Union] \ \[Rho]\^c\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ In the matrix picture, symmetry translates into symmetry of the \ matrix (with respect to the main diagonal).\ \>", "Text"], Cell[BoxData[ \(\(PlotMatrix[\ RelationToMatrix[\ 100, GCD[#1, #2] \[Equal] 3 &]];\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Transitivity", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:19"], Cell[TextData[{ "A relation \[Rho] is ", StyleBox["transitive ", FontColor->RGBColor[0, 0, 1]], " iff ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ x, \ y, \ z\ \[Element] \ A\ \((\ \ x\ \[Rho]\ y\ \[And] \ y\ \[Rho]\ z\ \[DoubleLongRightArrow]\ x\ \[Rho]\ z\ )\)\)]], ". \nNote that this is equivalent to saying that ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^2 \[SubsetEqual] \ \[Rho]\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Examples", FontWeight->"Bold"], ": \n", Cell[BoxData[ \(TraditionalForm\`E\_A\)]], ", ", Cell[BoxData[ FormBox[ SubscriptBox[ StyleBox["Id", FontSlant->"Italic"], "A"], TraditionalForm]]], ", and ", Cell[BoxData[ \(TraditionalForm\`U\_A\)]], " are all transitive. \nDivisibility is transitive. \nBoth the Less and \ LessEqual relations are transitive. \nThe \"is parent of\" relation is not \ transitive. \nThe \"co-author\" relation is not transitive. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Transitivity is notoriously hard to discern in a picture. Here is \ an example of a relation that fails to be transitive.\ \>", "Text"], Cell[BoxData[{ \(\(\[Rho][x_, y_]\ := \ GCD[x, y] == 2;\)\), "\n", \(\(PlotMatrix[\ RelationToMatrix[\ 8, \[Rho]], \ GridLines \[Rule] \ True];\)\)}], "Input"], Cell[TextData[{ "Rearranging the carrier set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " makes things much more obvious. Can you see why the relation is not \ transitive?" }], "Text"], Cell[BoxData[ \(\(PlotMatrix[\ RelationToMatrix[\ {2, 6, 4, 8, 1, 3, 5, 7}, \[Rho]], \ GridLines \[Rule] \ True];\)\)], "Input"], Cell["By comparison, here is a transitive relation.", "Text"], Cell[BoxData[{ \(\(\[Rho][x_, y_]\ := \ Mod[x, 3] == Mod[y, 3];\)\), "\n", \(\(PlotMatrix[\ RelationToMatrix[\ 8, \[Rho]\ ], \ GridLines -> True];\)\)}], "Input"], Cell["\<\ This time we can rearrange the carrier set in a way that makes it \ completely obvious (yes?) that the relation is transitive. \ \>", "Text"], Cell[BoxData[ \(\(PlotMatrix[\ RelationToMatrix[\ {1, 4, 7, 2, 5, 8, 3, 6}, \[Rho]], \ GridLines \[Rule] True];\)\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Orders", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:20"], Cell[TextData[{ "A relation \[Rho] is a", StyleBox[" pre-order", FontColor->RGBColor[0, 0, 1]], " iff it is both reflexive and transitive. \nA relation \[Rho] is a ", StyleBox["partial order", FontColor->RGBColor[0, 0, 1]], " iff it is a pre-order and anti-symmetric. \nA relation \[Rho] is an ", StyleBox["order", FontColor->RGBColor[0, 0, 1]], " or ", StyleBox["total order", FontColor->RGBColor[0, 0, 1]], " iff it is a partial order and any two elements of ", Cell[BoxData[ \(TraditionalForm\`A\)]], " are ", StyleBox["comparable", FontColor->RGBColor[0, 0, 1]], " with respect to \[Rho]: ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ x, \ y\ \[Element] \ A\ \((\ \ x\ \[Rho]\ y\ \[Or] \ y\ \[Rho]\ x\ )\)\)]], ". \n\nIn other words, in a total order we have ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[Union] \ \[Rho]\^c\ = \ U\_A\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Examples", FontWeight->"Bold"], ":\nLessEqual is a total order (on the natural numbers, the integers, the \ rationals, the reals). \nThe lexicographic order is a total order on strings.\ \nThe relation \"is no longer than\" is a pre-order on lists, as is the \ relation \"is no deeper than\". \nThe \"is subset of\" relation is an order \ on the power set ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalP](A)\)]], " of any set ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", but is not total unless ", Cell[BoxData[ \(TraditionalForm\`A\)]], " is empty or a singleton. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Strict Orders", FontWeight->"Bold"], "\nAccording to our definition, a pre-order is always reflexive. This is \ the appropriate way to model the less-than-or-equal relation. However, on \ occasion it is more convenient to deal with the less-than relation. \ Correspondingly, one defines the notions of ", StyleBox["strict pre-order", FontColor->RGBColor[0, 0, 1]], ", ", StyleBox["strict order", FontColor->RGBColor[0, 0, 1]], ", and ", StyleBox["strict total order", FontColor->RGBColor[0, 0, 1]], ". \nAs a matter of fact, for any ordering relation (in the non-technical \ sense) there is always a ", StyleBox["weak", FontColor->RGBColor[0, 0, 1]], " and a ", StyleBox["strict", FontColor->RGBColor[0, 0, 1]], " version, which are reflexive and irreflexive, respectively, but agree \ otherwise.\nSome authors prefer to work with the strict version. So don't be \ confused if you open a book and you find a definition of order as a relation \ that is irreflexive, transitive, and anti-symmetric. It is just the strict \ version of our notion of order. Also note that some author refer to partial \ orders as orders, and distinguish total order by always mentioning totality. \ " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Equivalence Relations", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:21"], Cell[TextData[{ "A relation \[Rho] is an", StyleBox[" equivalence relation", FontColor->RGBColor[0, 0, 1]], " iff it is reflexive, symmetric and transitive. \nEquivalence relations \ are important since they allow us to identify objects that are similar from \ some point of view. For an equivalence relation \[Rho] and an element ", Cell[BoxData[ \(TraditionalForm\`a\)]], " of ", Cell[BoxData[ \(TraditionalForm\`A\)]], " we write ", Cell[BoxData[ \(TraditionalForm\`\([a]\)\_\[Rho]\)]], " or simply ", Cell[BoxData[ \(TraditionalForm\`\([a]\)\)]], " for the ", StyleBox["equivalence class of ", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`a\)]], ": \n\t", Cell[BoxData[ \(TraditionalForm\`\([a]\)\_\[Rho]\ = \ {\ x\ \[Element] \ A\ | \ x\ \[Rho]\ a\ }\)]], ". \nWe can factor ", Cell[BoxData[ \(TraditionalForm\`A\)]], " by \[Rho] and consider the quotient set ", Cell[BoxData[ \(TraditionalForm\`A/\[Rho]\ = \ {\ \([a]\)\ | \ a\ \[Element] \ A\ }\)]], ". The number of equivalence classes is the index of \[Rho]. More \ precisely, the index of \[Rho] is the cardinality of the quotient set ", Cell[BoxData[ \(TraditionalForm\`A/\[Rho]\)]], ". \n \n", StyleBox["Examples", FontWeight->"Bold"], ":\nThe identity relation is an equivalence relation. Its index is finite \ iff the carrier set is finite.\nThe relation \"has the same length\" is an \ equivalence relation on lists (also on strings). It has infinite index.\nThe \ relation \"contains the same elements\" is an equivalence relation on lists. \ If we limit the list elements to be choses from a finite set, this relation \ also has finite index.\nThe relation ", Cell[BoxData[ \(TraditionalForm\`\(\(x\)\(\ \)\(\[Rho]\)\(\ \)\(y\)\(\ \)\)\)]], " on the integers defined by \"", Cell[BoxData[ \(TraditionalForm\`x\ - \ y\)]], " is divisble by 17\" is an equivalence relation with index 17.\n" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Lemma:", FontWeight->"Bold"], " Let \[Rho] be an equivalence relation on ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", and ", Cell[BoxData[ \(TraditionalForm\`a, b\ \[Element] \ A\)]], ". Then either ", Cell[BoxData[ \(TraditionalForm\`\([a]\)\ = \ \([b]\)\)]], " or ", Cell[BoxData[ \(TraditionalForm\`\([a]\)\ \[Intersection] \ \([b]\)\ = \ \ \[EmptySet]\)]], ". \nProof.\nSuppose the two equivalence classes are not disjoint. Then \ there is some element ", Cell[BoxData[ \(TraditionalForm\`c\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\(\(a\)\(\ \)\(\[Rho]\)\(\ \)\(c\)\(\ \)\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\ \[Rho]\ c\)]], ". But then by symmetry ", Cell[BoxData[ \(TraditionalForm\`c\ \[Rho]\ b\)]], ", and by transitivity ", Cell[BoxData[ \(TraditionalForm\`a\ \[Rho]\ b\)]], ". Now consider ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ \([a]\)\)]], ". Then ", Cell[BoxData[ \(TraditionalForm\`a\ \[Rho]\ x\)]], ", and by symmetry and transitivity, ", Cell[BoxData[ \(TraditionalForm\`b\ \[Rho]\ x\)]], ". Hence ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\([a]\)\ \[SubsetEqual] \ \ \([b]\)\)\)\)]], ". A similar argument shows the converse, and so both classes must be \ equal. \n\[EmptySquare]" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "In other words, an equivalence relation partitions the underlying set into \ disjoint ", StyleBox["blocks", FontColor->RGBColor[0, 0, 1]], " of similar elements. So, we can actually think of an equivalence relation \ as a ", StyleBox["partition", FontColor->RGBColor[0, 0, 1]], ". And, conversely, any partition can be viewed as an equivalence \ relation. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Definition", FontWeight->"Bold"], ": Let ", Cell[BoxData[ \(TraditionalForm\`\(\(A\)\(\ \)\)\)]], "be a set. A partition on ", Cell[BoxData[ \(TraditionalForm\`A\)]], " is a collection of subsets of ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", ", Cell[BoxData[ \(TraditionalForm\`P\ \[SubsetEqual] \ \[ScriptCapitalP](A)\)]], ", with the following properties: ", Cell[BoxData[ \(TraditionalForm\`\(\[Union]\_\(B\ \[Element] \ P\)\ B\)\ \ = \ A\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ \ B\ \[NotEqual] B\^\[Prime]\ \[Element] \ P\ \((\ B\ \[Intersection] \ B\^\[Prime] = \ \[EmptySet]\ )\)\)]], ". \n\nGiven an equivalence relation \[Rho] we obtain a partition ", Cell[BoxData[ \(TraditionalForm\`P\ = \ {\ \([a]\)\ | \ a\ \[Element] \ A\ }\)]], ". On the other hand, given a partition ", Cell[BoxData[ \(TraditionalForm\`P\)]], " we obtain an equivalence relation \[Rho] by setting \n\t", Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\ y\ \ iff\ \ \(\[Exists] \ B\ \[Element] \ P\ \((\ x, y\ \[Element] \ B\ )\)\)\)]], ". \nMake sure you understand why all the properties of a partition are \ needed to obtain an equivalence relation in this way." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Needless to say, there is a computational problem here: we are given a \ finite carrier set ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", and some equivalence relation \[Rho] on ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", and we have to determine the equivalence classes. For example, we could \ try to compute a list of lists \n\t", Cell[BoxData[ \(TraditionalForm\`P\ = \ {\ L\_1, \ L\_2, \ \[Ellipsis], \ L\_\(\(m\)\(\ \)\)}\)]], "\nwhere the ", Cell[BoxData[ \(TraditionalForm\`L\_i\)]], " are precisely the equivalence classes of \[Rho]. \n\nHere is a very \ inefficient way of doing this. Suppose rel is given as a binary matrix. We \ think of each row of A as a bit-vector, and pick out the corresponding \ elements of A. For the i-th row, this produces the equivalence class of A\ \[LeftDoubleBracket]i\[RightDoubleBracket]. Since there will repetitions in \ general, we have to take a Union in the end. \n" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(classifyMatrix[rel_?MatrixQ, A_List] := Union[\((A\[LeftDoubleBracket] Flatten[Position[#1, 1]]\[RightDoubleBracket] &)\) /@ \ rel];\)\), "\n", \(\(classifyMatrix[rel_?MatrixQ, n_Integer] := \n\t classifyMatrix[rel, Range[n]];\)\)}], "InputOnly"], Cell["\<\ Here is an example. We get the matrix by converting a Boolean function that \ tests whether two numbers have the same greatest common factor with 3. \ \>", \ "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(R = RelationToMatrix[\ 30, \ GCD[#1, 3] == GCD[#2, 3] &];\)\), "\n", \(\(PlotMatrix[R];\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(TableForm[\ classifyMatrix[R, 30], TableSpacing \[Rule] {1, 1}]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "So, in this case, there are only two classes, ", Cell[BoxData[ \(TraditionalForm\`\([3]\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\([1]\)\)]], ". \nCan you find the classes in the picture? What will happen if we \ replace 3 by 4, by 6? " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Kernel Relations", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:22"], Cell[TextData[{ "There is a standard method to produce an equivalence relation on a set ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". Suppose we have a function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ A\ \[LongRightArrow]\ B\)]], ". Then we can concoct a relation ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\_f\)]], " defined by \n\n\t", Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\_f\ y\ \ \ iff\ \ \ \(f(x)\)\ = \ f(y)\)]], ". \n\t\nThis is sometimes called the ", StyleBox["kernel relation of ", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`f\)]], ". Note that ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\_f\)]], " is always an equivalence relation, no matter what the function ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is: \n- reflexivity:\t", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ f(x)\)]], ",\n- symmetry:\t", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ f(y)\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`f(y)\ = \ f(x)\)]], ",\n- transitivity:\t", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ f(y)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`f(y)\ = \ f(z)\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ f(z)\)]], ".\n\nOne can think of ", Cell[BoxData[ \(TraditionalForm\`f\)]], " as describing a particular feature of the elements of ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". Two elements are equivalent w.r.t. ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\_f\)]], " iff they have the same feature. Computing the equivalence classes of ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\_f\)]], " then comes down to producing a classification of the elements of ", Cell[BoxData[ \(TraditionalForm\`A\)]], " (w.r.t. the feature described by ", Cell[BoxData[ \(TraditionalForm\`f\)]], "). " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Examples", FontWeight->"Bold"], ": \n- ", Cell[BoxData[ \(TraditionalForm\`A\ = \ humans\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x) := \ height\ in\ centimeters\)]], "\n- ", Cell[BoxData[ \(TraditionalForm\`A\ = \ humans\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x) := eye\ color\)]], "\n- ", Cell[BoxData[ \(TraditionalForm\`A\ = \ polynomials\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x) := degree\)]], "\n- ", Cell[BoxData[ \(TraditionalForm\`A\ = \ triangles\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x) := area\)]], "\n- ", Cell[BoxData[ \(TraditionalForm\`A\ = \ lists\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x) := length\)]], "\nand so on, and so forth.\n" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "A moment's thought reveals that in fact all equivalence relations are \ kernel relations for some suitably chosen function. \n", StyleBox["Lemma", FontWeight->"Bold"], ": A relation ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\ \[SubsetEqual] \ A\ \[Cross]\ A\)]], " is an equivalence relation iff ", Cell[BoxData[ \(TraditionalForm\`\[Exists] \ \(\(f\)\(\ \)\(function\)\(\ \)\((\ dom(f)\ = \ \(A\ \[And] \ \[Sigma]\ = \ \[Rho]\_f\))\)\(\ \ \)\ \)\)]], ".\nProof. \nThe direction from right to left is obvious, so assume that ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], " is an equivalence relation. Consider the function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ A\ \[LongRightArrow]\ A/\[Sigma]\)]], ", defined by ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ \([x]\)\_\[Sigma]\)]], ". It is clear that ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\ = \ \[Rho]\_f\)]], ". \n\[EmptySquare]" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "It is not hard to come up with an algorithm that computes the equivalence \ classes just like ", StyleBox["classifyMatrix", "MR"], " above, but starts not with a matrix for ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\_f\)]], ", but with the function ", Cell[BoxData[ \(TraditionalForm\`f\)]], " directly. In fact, it's one of the many functions in dimath.m. Of \ course, the brute force answer" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ classifyFunction[ A_, f_ ] := \tclassifyMatrix[ RelationToMatrix[ f[#1]==f[#2]&, A ], A ] \ \>", "Program", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "is a really bad idea. One should try to avoid having to build the big, \ cumbersome matrix. At any rate, look at ", StyleBox["Automata", "Program"], " to see how ", ButtonBox["ToClasses", ButtonStyle->"AddOnsLink"], " is implemented. Better, figure it out yourself. \n\nNote that the \ example from above is really a kernel relation, so we can get the classes \ directly without converting to a matrix first. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(ToClasses[Range[30], GCD[#1, 3] &, Type \[Rule] Function]\)], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Congruences ", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:23"], Cell[TextData[{ "Equivalence relations are very, very important. For example, public key \ encryption systems can be based on performing arithmetic with respect to a \ simple equivalence relation on the integers. More precisely, two integers ", Cell[BoxData[ \(TraditionalForm\`x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\)]], " are ", StyleBox["congruent mod m", FontColor->RGBColor[0, 0, 1]], " iff ", Cell[BoxData[ \(TraditionalForm\`m\ | \ x - y\)]], ". Equivalently, ", Cell[BoxData[ \(TraditionalForm\`x\ mod\ m\ = \ y\ mod\ m\)]], ". Here ", Cell[BoxData[ \(TraditionalForm\`m\)]], " is some fixed, positive integer, the so-called ", StyleBox["modulus", FontColor->RGBColor[0, 0, 1]], ". It is customary to write this in the style of an equation (thanks to \ Gauss): \n\t\t", Cell[BoxData[ \(TraditionalForm\`x\ \[Congruent] \ \(\(y\)\(\ \)\((mod\ m)\)\(\ \)\)\ \)]], "\nConguence modulo ", Cell[BoxData[ \(TraditionalForm\`m\)]], " is an equivalence relation: it is the kernel relation of the function \n\ \t ", Cell[BoxData[ \(TraditionalForm\`mod\_m\)]], " ", Cell[BoxData[ \(TraditionalForm\`\(\(:\)\(\ \)\(\[DoubleStruckCapitalZ]\ \ \[LongRightArrow]\ \ {0, 1, \[Ellipsis], m - 1}\)\)\)]], ". \nThe equivalence classes of this relation are called ", StyleBox["modular numbers", FontColor->RGBColor[0, 0, 1]], ". As it turns out, one can perform arithmetic on modular numbers in \ exactly the same way as on integers. But, there are only finitely many of \ them, ", Cell[BoxData[ \(TraditionalForm\`m\)]], " to be more precise, so one can get a better overview of what's going on. \ Moreover, there are very interesting connections between ordinary arithmetic, \ and modular arithmetic. We will exploit this in the next chapter to build a \ public key encryption system. \n\nHere are the classes (or rather, a small \ segment of them) for modulus 5. Ponder deeply. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(ToClasses[Range[\(-30\), 29], Mod[#1, 5] &, Type \[Rule] Function]\ // \ TableForm[#, TableSpacing \[Rule] {1, 2}] &\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Note that here ", Cell[BoxData[ \(TraditionalForm\`\([0]\)\)]], " consists of all multiples of 5 (in the proper range), ", Cell[BoxData[ \(TraditionalForm\`\([1]\)\ = \ \([0]\)\ + \ 1\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\([2]\)\ = \ \([0]\)\ + \ 2\)]], ", and so forth. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Well-Orderings and Induction", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:24"], Cell[TextData[{ "The following notion of well-foundedness originated in set theory, but \ turns out be useful in the theory of computation as well. Suppose we have a \ relation \[Rho] on some set ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". \[Rho] is ", StyleBox["well-founded", FontColor->RGBColor[0, 0, 1]], " iff there is no infinite chain of the form ", Cell[BoxData[ \(TraditionalForm\`x\_1\ \[Rho]\ x\_0\)]], ", ", Cell[BoxData[ \(TraditionalForm\`x\_2\ \[Rho]\ x\_1\)]], ", ", Cell[BoxData[ \(TraditionalForm\`x\_3\ \[Rho]\ x\_2\)]], ", \[Ellipsis]\nIn other words, there must be no function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ A\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ i\ \((\ \ \(f(i + 1)\)\ \[Rho]\ \(f(i)\)\ )\)\)]], ". \n\nThe perhaps most important example is the element relation on sets: \ we cannont have an element inside an element inside an element and so on ad \ infinitum. Strictly speaking, this requires an axiom that proclaims that \ \[Element] is well-founded. Note that this rules out the existence of sets \ ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ x\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Well-foundedness is of interest in particular in conjunction with a strict \ order. A ", StyleBox["well-order", FontColor->RGBColor[0, 0, 1]], " iff is a strict order that is also well-founded. Thus, in a well-order we \ cannot have an infinite descending sequence\n\t", Cell[BoxData[ \(TraditionalForm\`\(\(x\_0\)\(\ \)\(>\)\(\ \)\(x\_1\)\(>\)\(\ \ \)\(x\_\(\(2\)\(\ \)\)\)\(>\)\(\ \)\(\[Ellipsis]\)\(\ \)\(>\)\(\ \)\(x\_i\)\(\ \ \)\(>\)\(\ \)\(x\_\(i + 1\)\)\(>\)\(\ \)\(\[Ellipsis]\)\(\ \ \)\)\)]], "\nNote that the converse of the order is used here. \n\n", StyleBox["Examples", FontWeight->"Bold"], ":\nThe crucial example for a well-order is the natural numbers together \ with the usual order ", Cell[BoxData[ \(TraditionalForm\` < \)]], ". Note that the integers, rationals and reals with the standard order fail \ to be well-ordered (not even if we consider only the open interval ", Cell[BoxData[ \(TraditionalForm\`\((0, 1)\)\ \[Subset] \ \[DoubleStruckCapitalR]\)]], "). \nThe ", StyleBox["lexicographic order", FontColor->RGBColor[0, 0, 1]], " ", Cell[BoxData[ \(TraditionalForm\`\(\(x\)\(\ \)\(\[Precedes]\)\(\ \ \)\(y\)\(\ \ \ \)\)\)]], "is on strings is not a well-order: ", Cell[BoxData[ \(TraditionalForm\`b\ > \ ab\ > \ aab\ > \ aaab\ > \ \[Ellipsis]\)]], "\nBut the so-called ", StyleBox["length-lex", FontColor->RGBColor[0, 0, 1]], " order is well-founded: \n\t", Cell[BoxData[ \(TraditionalForm\`x\ < \ y\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(x\)\(|\)\(\(<\)\(|\)\)\) y | \ \ \ \ \(\(\[Or]\)\(\ \ \)\((\ \ \(\(|\)\(x\)\(|\)\)\ = \ \ \(\(|\)\(y\)\(|\)\(\ \ \)\(\(\[And]\)\(\ \ \)\(x\ \[Precedes] \ y\)\)\)\ )\)\)\)]], ".\nThe relation \"is shorter than\" is a well-order on lists, as is the \ relation \"is more shallow than\". \nThe \"is a proper subset of\" relation \ on the power set of a set ", Cell[BoxData[ \(TraditionalForm\`B\)]], " is a well-order only if ", Cell[BoxData[ \(TraditionalForm\`B\)]], " is finite. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "To see why this might be of interest in computer science, suppose we have \ a well-ordering ", Cell[BoxData[ \(TraditionalForm\` < \)]], " on some data type ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". Then the following loop always terminates: " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "\n\tpick an element ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ A\)]], " at random\n\t\n\twhile( there is a ", Cell[BoxData[ \(TraditionalForm\`y\ < \ x\)]], " )\n\t{\n\t\tpick some ", Cell[BoxData[ \(TraditionalForm\`y\ < \ x\)]], " at random;\n\t\t", Cell[BoxData[ \(TraditionalForm\`x\ = \ y\)]], ";\n\t}\n\t" }], "Program", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Thus, well-orders can guarantee the termination of algorithms, even \ of wildly non-deterministic ones like the one just stated. Of more interest \ in practice are recursive algorithms. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ \ttype f( type x ) \t{ \t\t... f(g(x)) ... \t} \t\ \>", "Program", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "A recursive algorithm of this type are guaranteed to terminate as long as \ ", Cell[BoxData[ \(TraditionalForm\`g(x)\ < \ x\)]], " in some well-order on the data type. The standard example for this ", Cell[BoxData[ \(TraditionalForm\`g(n)\ = \ n - 1\)]], " on the natural numbers, but the principle applies to many other \ situations as well. " }], "Text"], Cell[CellGroupData[{ Cell["\<\ Induction on a Well-Ordering\ \>", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:25"], Cell[TextData[{ "The importance of well-ordering in CS comes from recursion and induction. \ If we have a set ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", usually some kind of data type like numbers, strings, lists or trees, \ and we have a well-ordering \[Rho] on ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", than we can perform induction. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["\[Rho]-Induction Principle", FontColor->RGBColor[0, 0, 1]], "\nLet ", Cell[BoxData[ \(TraditionalForm\`P(x)\)]], " be an assertion about elements of ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". Then it suffices to show the following in order to prove that ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ x\ \[Element] \ A\ \ \ \(P(x)\)\)]], ":\nInduction Property: ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] z\ \((\ z\ \[Rho]\ x\ \ \[Implies] P(z)\ )\)\ \[DoubleLongRightArrow]\ \(P(x)\)\)]], ". \n\t\nI.e., it suffices to show that ", Cell[BoxData[ \(TraditionalForm\`P(x)\)]], " holds for any ", Cell[BoxData[ \(TraditionalForm\`x\)]], ", assuming that ", Cell[BoxData[ \(TraditionalForm\`P(z)\)]], " already holds for all lesser ", Cell[BoxData[ \(TraditionalForm\`z\)]], ", lesser in the sense of \[Rho]. The induction hypothesis usually written \ a bit more sloppily as ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ \(\(z\)\(\ \)\(\[Rho]\)\(\ \)\(x\)\(\ \ \ \)\(P(z)\)\(\ \)\)\)]], ". \n\nOne might wonder where the base case is. After all, this is supposed \ to be more general that ordinary induction, so if we let ", Cell[BoxData[ \(TraditionalForm\`A\ = \ \[DoubleStruckCapitalN]\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ = \ < \)]], ", we should get back to our old method. The answer is, the base case is \ hidden: if ", Cell[BoxData[ \(TraditionalForm\`{\ z\ | \ z\ \[Rho]\ x\ }\ = \ \[EmptySet]\)]], ", then the premise on the left is automatically true: try to find a ", Cell[BoxData[ \(TraditionalForm\`z\ \[Rho]\ x\)]], " for which ", Cell[BoxData[ \(TraditionalForm\`P(z)\)]], " fails. There aren't any. Hence, in order for the implication to be \ true, we have to show ", Cell[BoxData[ \(TraditionalForm\`P(x)\)]], ", without the benefit of any induction hypothesis. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "To see that this is really a sound induction principle, let us establish a \ little theorem that is none other than the ", StyleBox["least element principle for ", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`A\)]], StyleBox[" and \[Rho]", FontColor->RGBColor[0, 0, 1]], ", rather than just the natural numbers and Less. \n\n", StyleBox["Theorem:", FontWeight->"Bold"], " (Least Element Principle for Well-Orderings) \nLet \[Rho] be a \ well-ordering on ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". Then every non-empty subset of ", Cell[BoxData[ \(TraditionalForm\`A\)]], " has an \[Rho]-least element. \nProof: \nSuppose there is some bad subset \ ", Cell[BoxData[ \(TraditionalForm\`B\ \[SubsetEqual] \ A\)]], " that fails to have an \[Rho]-least element. Pick some element ", Cell[BoxData[ \(TraditionalForm\`b\_0\ \[Element] \ B\)]], " at random. Since ", Cell[BoxData[ \(TraditionalForm\`b\_0\)]], " is not \[Rho]-minimal in ", Cell[BoxData[ \(TraditionalForm\`B\)]], ", there must be an element ", Cell[BoxData[ \(TraditionalForm\`b\_1 \[Element] \ B\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\(b\_1\) \[Rho]\ b\_0\)]], ". But ", Cell[BoxData[ \(TraditionalForm\`b\_1\)]], " is not \[Rho]-minimal either, and so we can recursively define a sequence \ ", Cell[BoxData[ \(TraditionalForm\`\(\(b\_0\)\(,\)\(\ \)\(b\_1\)\(,\)\(\ \ \)\(b\_2\)\(,\)\(\ \)\(\[Ellipsis]\)\(\ \ \)\)\)]], "of strictly smaller and smaller elements of ", Cell[BoxData[ \(TraditionalForm\`B\)]], ", contradicting the fact that \[Rho] is a well-ordering. \n\[EmptySquare]" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "The LEP for well-orderings shows that our \[Rho]-Induction principle is \ perfectly sound. For suppose that it fails, that there is some set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " with a well-order \[Rho] such that the induction property \n\t ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] z\ \((\ z\ \[Rho]\ x\ \ \[Implies] P(z)\ )\)\ \[DoubleLongRightArrow]\ \(P(x)\)\)]], "\nholds for all ", Cell[BoxData[ \(TraditionalForm\`x\)]], ", but nonetheless ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ x\ \[Element] \ A\ \(P(x)\)\)]], " is false. Let ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\[EmptySet]\ \[NotEqual] B\ \ = \ {\ \ x\ \[Element] \ A\ | \ \ \[Not] P(x)\ \ }\ \[SubsetEqual] \ A\)\)\)]], ". By the LEP, there is an ", Cell[BoxData[ \(TraditionalForm\`x\_0\)]], " in ", Cell[BoxData[ \(TraditionalForm\`B\)]], " that is minimal w.r.t. \[Rho]. That means that for all ", Cell[BoxData[ \(TraditionalForm\`z\ \[Rho]\ x\_0\)]], ", ", Cell[BoxData[ \(TraditionalForm\`z\)]], " is not in ", Cell[BoxData[ \(TraditionalForm\`B\)]], ". In other words, ", Cell[BoxData[ \(TraditionalForm\`P(z)\)]], " holds. But then, by the induction property, we have ", Cell[BoxData[ \(TraditionalForm\`P(x\_0)\)]], ", contradicting the definition of ", Cell[BoxData[ \(TraditionalForm\`B\)]], ". \n\nThe reason this type of general induction principle is useful is \ that we can custom design the well-ordering \[Rho]. For some set such as the \ natural numbers we already have a perfectly good well-ordering, namely the \ natural one, Less, but for more complicated data types we have to invent a \ suitable well-ordering. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["\<\ Termination of Ackerman\ \>", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:26"], Cell["\<\ Here is a typical example: a function that can easily be computed \ by recursion, but cannot be computed at all with for-loops (with the \ constraint that the bound in the loop cannot be modified during the \ executation of the loop body). The first example of such a function was given \ by Ackermann, a logician, in the 30's. As it turns out, the Ackermann \ function actually plays a role in the running time analysis of the so-called \ Union-Find algorithm, see 15-211. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Here is a recursive definition of the Ackerman function. The \ Ackermann function grows extremely rapidly and produdes huge call-trees in \ the process. It is very easy to crash the system running Ackermann, be \ careful. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(ClearAll[A]\), "\n", \(\(A[0, y_Integer] := \(A[0, y] = y + 1\);\)\), "\n", \(\(A[x_Integer, 0] := \(A[x, 0] = A[x - 1, 1]\);\)\), "\n", \(\(A[x_Integer, y_Integer] := \(A[x, y] = A[x - 1, A[x, y - 1]]\);\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\($RecursionLimit = 100000;\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(\((A[0, #1] &)\) /@ Range[10]\), "\n", \(\((A[1, #1] &)\) /@ Range[10]\), "\n", \(\((A[2, #1] &)\) /@ Range[10]\), "\n", \(\((A[3, #1] &)\) /@ Range[8]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "It is helpful to think of ", Cell[BoxData[ \(TraditionalForm\`A\)]], " as a family of functions defined by ", Cell[BoxData[ \(TraditionalForm\`\(A\_x\)(y)\ = \ A(x, y)\)]], ". Then \n\t\n\t", Cell[BoxData[ FormBox[GridBox[{ {\(\(A\_0\)(y)\), "=", \(y + 1\)}, {\(\(A\_1\)(y)\), "=", \(y + 2\)}, {\(\(A\_2\)(y)\), "=", \(2 y + 3\)}, {\(\(A\_3\)(y)\), "=", \(2\^\(y + 3\) - \ 3\)}, {\(\(A\_4\)(x)\), "=", \(2\^\(2\^\(\[AscendingEllipsis]\^2\)\) - 3\)} }], TraditionalForm]]], "\n\t\nwhich indicates that ", Cell[BoxData[ \(TraditionalForm\`A\_x\)]], " grows more and more rapidly as ", Cell[BoxData[ \(TraditionalForm\`x\)]], " increases. ", Cell[BoxData[ \(TraditionalForm\`A\_4\)]], " already corresponds to some form of super-exponentiation, there are ", Cell[BoxData[ \(TraditionalForm\`y - 3\)]], " 2's in the stack of exponents, and ", Cell[BoxData[ \(TraditionalForm\`A\_5\)]], " grows much too fast to be of any practical importance. The following \ input already crashes the system." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\tA[4,1]", "Program", AspectRatioFixed->True], Cell[TextData[{ "Don't even dream about computing A[10,10] or some such. How do we know \ that the recursion always terminates, at least on a machine with unbounded \ resources? The trick is to impose the right well-ordering on pairs of natural \ numbers, the input type for Ackermann: \n ", Cell[BoxData[ \(TraditionalForm\`\((a, b)\)\ < \ \((a\^\[Prime], b\^\[Prime])\)\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`a\ < \ a\^\(\(\[Prime]\)\(\ \)\)\ \[Or] \ \ \((\ a\ = \ a\^\[Prime]\ \[And] \ b\ < \ b\^\[Prime])\)\)]], ". \nNote that this construction is perfectly general and allows one to \ extend any strict order from a set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " to the set of pairs over ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". The new order is called a ", StyleBox["product order", FontColor->RGBColor[0, 0, 1]], ". \n\n", StyleBox["Lemma:", FontWeight->"Bold"], " The product order of ", Cell[BoxData[ \(TraditionalForm\` < \)]], " on ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalN]\ \[Cross]\ \ \[DoubleStruckCapitalN]\)]], " is a well-ordering. \nProof: Suppose for the sake of a contradiction \ that we have an infinite descending chain ", Cell[BoxData[ \(TraditionalForm\`\[LeftAngleBracket]a\_i, b\_i\[RightAngleBracket]\)]], ". Consider any segment where ", Cell[BoxData[ \(TraditionalForm\`a\_m = \ \(a\_\(m + 1\) = \ \(\[Ellipsis]\ = \ a\_\(m + n\)\)\)\)]], ", for some ", Cell[BoxData[ \(TraditionalForm\`m, n\ \[GreaterEqual] \ 0\)]], ". But then ", Cell[BoxData[ \(TraditionalForm\`b\_m\ > \ b\_\(m + 1\)\ > \ \[Ellipsis]\ > \ b\_\(m + n\)\)]], ". Since the natural numbers are well-ordered, that descending chain \ cannot extend indefinitely. Hence, for some sufficiently large ", Cell[BoxData[ \(TraditionalForm\`n\)]], ", we must have ", Cell[BoxData[ \(TraditionalForm\`b\_\(m + n\)\ \[LessEqual] \ b\_\(m + n + 1\)\)]], " and therefore ", Cell[BoxData[ \(TraditionalForm\`a\_\(m + n\)\ > \ a\_\(m + n + 1\)\)]], ". So, after finitely many steps the ", Cell[BoxData[ \(TraditionalForm\`a\)]], "-part of the sequence must decrease. Then, it may again be constant for a \ while, but ultimately it has to strictly decrease again. In fact, it must \ decrease infinitely often, there must be a subsequence \n\t", Cell[BoxData[ \(TraditionalForm\`a\_0 > \ a\_\(n\_1\) > \ a\_\(n\_2\) > \ \[Ellipsis]\)]], "\nBut that contradicts the natural numbers being well-ordered. \n\ \[EmptySquare]" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "\nHow do we use the fact that ", Cell[BoxData[ \(TraditionalForm\`\[LeftAngleBracket]\ \[DoubleStruckCapitalN]\ \ \[Cross]\ \[DoubleStruckCapitalN], \ < \ \[RightAngleBracket]\)]], " is well-ordered? \nIt is very easy to check that all recursive calls ", Cell[BoxData[ \(TraditionalForm\`A[c, d]\)]], " that are made within the call ", Cell[BoxData[ \(TraditionalForm\`A[a, b]\)]], " have the property that ", Cell[BoxData[ \(TraditionalForm\`\((c, d)\)\ < \ \((a, b)\)\)]], ": there is a call ", Cell[BoxData[ \(TraditionalForm\`A[a, b - 1]\)]], " and another ", Cell[BoxData[ \(TraditionalForm\`A[\ a - 1, \ z\ ]\)]], " where ", Cell[BoxData[ \(TraditionalForm\`z\ = \ A[a, b - 1]\)]], ". Hence, by <-induction, we may assume that these calls already \ terminate. But then the main call also terminates. Done. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Comment: For those of you who find well-orderings suspicious, you can \ also show that Ackermann always terminates by using an ordinary induction \ inside another. To show that ", Cell[BoxData[ \(TraditionalForm\`A[x, y]\)]], " is well-defined, use \n- induction on ", Cell[BoxData[ \(TraditionalForm\`x\)]], ", and \n- subinduction on ", Cell[BoxData[ \(TraditionalForm\`y\)]], ". \n\nBases case: ", Cell[BoxData[ \(TraditionalForm\`x = 0\)]], ". Then ", Cell[BoxData[ \(TraditionalForm\`A[0, y]\ = \ y + 1\)]], ", and we are done. \n\nInuction step: Assume ", Cell[BoxData[ \(TraditionalForm\`A[x, y]\)]], " is defined for all ", Cell[BoxData[ \(TraditionalForm\`y\)]], ". \nShow by subinduction on y that: ", Cell[BoxData[ \(TraditionalForm\`A[x + 1, y]\)]], " is defined for all ", Cell[BoxData[ \(TraditionalForm\`y\)]], ". \n\tSubbase case: ", Cell[BoxData[ \(TraditionalForm\`y = 0\)]], ". Then ", Cell[BoxData[ \(TraditionalForm\`A[x + 1, 0]\ = \ A[x, 1]\)]], ", which is well-defined by IH \n\tSubinduction step: assume ", Cell[BoxData[ \(TraditionalForm\`A[x + 1, y]\)]], " is well-defined. \n\tThen ", Cell[BoxData[ \(TraditionalForm\`A[x + 1, y + 1]\ = \ \ A[\ x, \ A[x + 1, y]\ ]\)]], ", which is well-defined \n\tsince ", Cell[BoxData[ \(TraditionalForm\`A[x + 1, y]\)]], " is by sub-IH, so ", Cell[BoxData[ \(TraditionalForm\`A[x + 1, y]\ = \ z\)]], " for some ", Cell[BoxData[ \(TraditionalForm\`z\)]], "; \n\tand therefore ", Cell[BoxData[ \(TraditionalForm\`A[x + 1, y + 1]\ = \ \ A[\ x, \ z\ ]\)]], " which is well-defined by IH. \n\tEnd of subinduction. \nEnd of \ induction. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Needless to say, if you have a recursion on three variables, then \ there would be a subsubinduction inside the subinduction. Too horrible to \ consider, well-orderings make life quite a bit easier here. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Universal Genealogy", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:29"], Cell["\<\ There is actually a whole calculus of relations, which was of \ interest only to mathematicians and logicians, until databases arrived. Many \ of the problems of storing and manipulating large amounts of relational \ information can be expressed very nicely in terms of the classical calculus \ of relations. The first two examples give a slight indication how ideas about relations can \ be useful in the design of a database. Actually, in real life one has to \ modify things quite a bit to get a useful implementation, but the principles \ are all the same. The third example shows a few relations on binary \ lists.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "For example, some people find the idea of tracing back one's own ancestry \ absolutely fascinating. In terms of relations, what these people are trying \ to do is to build a database for a binary relation on the set of all humans, \ and the relation is simply parenthood:\n\t", Cell[BoxData[ \(TraditionalForm\`\[Pi](x, y)\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(x\)\)\)]], " is a parent of ", Cell[BoxData[ \(TraditionalForm\`y\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Everything else can be computed from there. For example, \n\t", Cell[BoxData[ \(TraditionalForm\`x\)]], " is a child of ", Cell[BoxData[ \(TraditionalForm\`y\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\(\[Pi]\^c\)(x, y)\)]], ".\n\t", Cell[BoxData[ \(TraditionalForm\`x\)]], " is a grand-parent of ", Cell[BoxData[ \(TraditionalForm\`y\)]], " iff \[Exists] z ( \[Pi](x,z) \[And] \[Pi](z,y) ) iff ", Cell[BoxData[ \(TraditionalForm\`\(\[Pi]\^2\)(x, y)\)]], ". \t \n\t", Cell[BoxData[ \(TraditionalForm\`x\)]], " is a great-grand-parent of ", Cell[BoxData[ \(TraditionalForm\`y\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\(\[Pi]\^3\)(x, y)\)]], ". \n\t", Cell[BoxData[ \(TraditionalForm\`x\)]], " is an ancestor of ", Cell[BoxData[ \(TraditionalForm\`y\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\[Exists] \ n > 0\ \ \ \(\(\[Pi]\^\(\(\ \)\(n\)\)\)(x, \ y)\)\)]], ". \t\n\t", Cell[BoxData[ \(TraditionalForm\`x\)]], " is a sibling of ", Cell[BoxData[ \(TraditionalForm\`y\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\[Exists] \ \(\(z\)\(\ \ \)\((\ \[Pi](z, x)\ \[And] \ \[Pi](z, y)\ )\)\(\ \)\)\)\)\)]], " \n\t\t\tiff ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\[Exists] \ \(\(z\)\(\ \ \)\((\ \(\[Pi]\^c\ \)(x, z)\ \[And] \ \[Pi](z, y)\ )\)\(\ \)\)\)\)\)]], "\n\t\t\tiff ", Cell[BoxData[ \(TraditionalForm\`\((\[Pi]\^\(\(\ \)\(c\)\)\[SmallCircle]\ \[Pi])\) \ \((x, y)\)\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "By the way, what does ", Cell[BoxData[ \(TraditionalForm\`\((\[Pi]\ \[SmallCircle]\ \[Pi]\^\(\(\ \)\(c\)\))\) \ \((x, y)\)\)]], " mean?" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Suppose we want to express the fact that ", Cell[BoxData[ \(TraditionalForm\`x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\)]], " are not related to each other. This can be translated as having no common \ ancestor:\n\n\t", Cell[BoxData[ FormBox[ RowBox[{"\[NotExists]", " ", RowBox[{"z", " ", RowBox[{"(", " ", RowBox[{ RowBox[{ FormBox[\(\[Pi]\^+\), "TraditionalForm"], \((z, x)\)}], "\[And]", " ", \(\(\[Pi]\^+\)(z, y)\)}], " ", ")"}]}]}], TraditionalForm]]], " iff \n\t", Cell[BoxData[ FormBox[ RowBox[{"\[NotExists]", " ", RowBox[{"z", " ", RowBox[{"(", " ", RowBox[{ RowBox[{ FormBox[\(\[Pi]\^\(+c\)\), "TraditionalForm"], \((x, z)\)}], "\[And]", " ", \(\(\[Pi]\^+\)(z, y)\)}], " ", ")"}]}]}], TraditionalForm]]], " iff \n\t", Cell[BoxData[ FormBox[ RowBox[{"\[Not]", RowBox[{ RowBox[{"(", " ", RowBox[{ FormBox[\(\[Pi]\^\(+c\)\), "TraditionalForm"], "\[SmallCircle]", " ", \(\[Pi]\^+\)}], ")"}], \((x, y\ )\)}]}], TraditionalForm]]], " iff \n\t", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ RowBox[{"(", " ", RowBox[{ FormBox[\(\[Pi]\^\(+c\)\), "TraditionalForm"], "\[SmallCircle]", " ", \(\[Pi]\^+\)}], ")"}], "-"], \((x, y\ )\)}], TraditionalForm]]], ".\n\t\nBy contrast, Genesis is correct iff there are humans ", Cell[BoxData[ \(TraditionalForm\`A\)]], " and ", Cell[BoxData[ \(TraditionalForm\`E\)]], " such that:\n\t", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ x\ \ \((\ \ \(\[Pi]\^+\)(\ A, \ x\ )\ \ \[And] \ \ \(\[Pi]\^+\)(\ E, \ x\ )\ )\)\ \ \[And] \ \ \ \[NotExists] \ z\ \((\ \[Pi](z, A)\ )\)\ \ \[And] \ \[NotExists] \ z\ \((\ \[Pi](z, E)\ )\)\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Relations on Binary Lists", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:31"], Cell[TextData[{ "As a final example we will consider a number of relations on binary lists \ of fixed length. For convenience, we only consider binary lists of length 6, \ but you should think carefully about what would happen if we were to use \ lists of different lengths. Note that there are ", Cell[BoxData[ \(TraditionalForm\`2\^\(\(\ \)\(n\)\)\)]], " binary lists of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], ", so you can only experiment with small values of ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". \nFirst, we use a Cartesian product to produce all binary lists of \ length 6." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(L6 = Tuples[{0, 1}, 6];\)\), "\n", \(Short[L6, 4]\), "\n", \(L6\ // \ Length\)}], "Input", AspectRatioFixed->True], Cell["\<\ A pretty picture of somewhat dubious use. Note that there are lots \ of symmetries.\ \>", "Text"], Cell["\<\ PlotMatrix[ Transpose[L6],AspectRatio\[Rule].5];\ \>", "Input"], Cell[CellGroupData[{ Cell["Sorting", "Subsubsection", CellTags->"c:32"], Cell[TextData[{ "Here is a very simple relation based on sorting: two lists are related if \ their sorted versions are the same. Note that this is an example of a kernel \ relation: the function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ L6\ \[LongRightArrow]\ L6\)]], " is the sorting operation. Hence, we should get an equivalence relation. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(\[Rho][x_, y_] := Sort[x] == Sort[y];\)\), "\n", \(\(R = RelationToMatrix[L6, \[Rho]];\)\), "\n", \(\(PlotMatrix[R];\)\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Certainly reflexive and symmetric. Actually, the picture is doubly \ symmetric (symmetric with respect to both diagonals). The main diagonal is \ clear, but how about the other diagonal? Reflection along the main diagonal \ corresponds to exchanging the element in position ", Cell[BoxData[ \(TraditionalForm\`\((i, j)\)\)]], " with the element in position ", Cell[BoxData[ \(TraditionalForm\`\((j, i)\)\)]], ". What position corresponds to position ", Cell[BoxData[ \(TraditionalForm\`\((i, j)\)\)]], " when we reflect with respect to the second diagonal? A moments thought \ reveals that the corresponding position is ", Cell[BoxData[ \(TraditionalForm\`\((n - j + 1, n - i + 1)\)\)]], " for a ", Cell[BoxData[ \(TraditionalForm\`n\)]], " by ", Cell[BoxData[ \(TraditionalForm\`n\)]], " matrix, ", Cell[BoxData[ \(TraditionalForm\`1\ \[LessEqual] i, j \[LessEqual] n\)]], ". Using the ", StyleBox["Mathematica", FontSlant->"Italic"], " indexing convention, this can be written more understandably as ", Cell[BoxData[ \(TraditionalForm\`\((\(-j\), \(-i\))\)\)]], ". \nLet's check:" }], "Text"], Cell[BoxData[{ \(\(n = 64;\)\), "\n", \(i = Random[Integer, {1, n}]\), "\n", \(j = Random[Integer, {1, n}]\), "\n", \(R\[LeftDoubleBracket]i, j\[RightDoubleBracket] \[Equal] R\[LeftDoubleBracket]\(-j\), \(-i\)\[RightDoubleBracket]\)}], "Input"], Cell[BoxData[ \(TableForm[{{L6\[LeftDoubleBracket]i\[RightDoubleBracket], L6\[LeftDoubleBracket]\(-i\)\[RightDoubleBracket]}, {L6\ \[LeftDoubleBracket]j\[RightDoubleBracket], L6\[LeftDoubleBracket]\(-j\)\[RightDoubleBracket]}}]\)], "Input"], Cell[TextData[{ "Can you see what is going on? Remember the dubious picture from above?\n\n\ As usual, transitivity is not immediately obvious. We can check that ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^2\)]], " is really a subset of \[Rho]. Since subset testing is not directly \ implmented, we use the trick to check ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^\(\(\ \)\(2\)\)\ - \ \[Rho]\ = \ \ \[EmptySet]\)]], " instead. " }], "Text"], Cell[BoxData[{ \(\(RR = BooleanComposition[R, R];\)\), "\n", \(Union[Flatten[BooleanComplement[RR, R]]]\)}], "Input"], Cell["\<\ What are the equivalence classes? We generate the partition of L6 \ corresponding to \[Rho], and check the number of blocks, as well as their \ sizes.\ \>", "Text"], Cell[BoxData[{ \(\(part = ToClasses[L6, R, Type \[Rule] Matrix];\)\), "\n", \(Length[part]\), "\n", \(Map[\ Length, part]\)}], "Input"], Cell["It is fairly easy to figure out what the blocks are.", "Text"], Cell["part[[3]]", "Input"], Cell["part[[4]]", "Input"], Cell[TextData[{ "Right, two lists are equivalent iff they have the same number of 1's in \ them. If we think of them as bitvectors over the universe ", Cell[BoxData[ \(TraditionalForm\`\([6]\)\)]], ", that just means that the corresponding subsets have the same \ cardinality. Which tempts the question how many ", Cell[BoxData[ \(TraditionalForm\`k\)]], "-element subsets a set of cardinality ", Cell[BoxData[ \(TraditionalForm\`n\)]], " has as ", Cell[BoxData[ \(TraditionalForm\`k\)]], " ranges from 0 to ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". For ", Cell[BoxData[ \(TraditionalForm\`n = 6\)]], " we can read off the answer from the partition above, but the real \ question is what happens for arbitrary ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". " }], "Text"], Cell["\<\ On a different topic, let us use the partition to reorder L6: we \ put all elements in the first block of the partition first, then the elements \ of the second block, and so forth. Within each block, the order really does \ not matter.\ \>", "Text"], Cell[BoxData[{ \(\(AA\ = \ Flatten[part, 1];\)\), "\n", \(Short[AA, 6]\)}], "Input"], Cell["\<\ The output is rather large, so we have truncated it with Short. \ Alternatively, we could think of the binary lists as being binary expansions \ of numbers, and print the numbers instead.\ \>", "Text"], Cell["Map[ FromDigits[#,2]&, AA ]", "Input"], Cell["\<\ No particular pattern visible here. The original arrangement is the \ trivial one:\ \>", "Text"], Cell["Map[ FromDigits[#,2]&, L6 ]", "Input"], Cell["\<\ Reordering the universe in this way does not change the relation \ itself, but the picture changes drastically. It is clear now that the \ relation is reflexive, symmetric, and transitive.\ \>", "Text"], Cell[BoxData[{ \(\(R = RelationToMatrix[AA, \[Rho]];\)\), "\[IndentingNewLine]", \(\(PlotMatrix[R];\)\)}], "Input"], Cell[TextData[{ "What are the ", Cell[BoxData[ \(TraditionalForm\`k\)]], " values associated with the squares along the diagonal?\nOf course, the \ question remains how large the blocks are in general, i.e., how many ", Cell[BoxData[ \(TraditionalForm\`k\)]], "-element subsets a set of cardinality ", Cell[BoxData[ \(TraditionalForm\`n\)]], " has. We will postpone this problem for a while." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Rotations", "Subsubsection", CellTags->{"Rotations", "c:33"}], Cell["\<\ Here is a relation based on cyclic rotation: two lists are related \ if the first is a left-shift of the second.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(shift[x_, y_] := x === RotateLeft[y];\)\), "\n", \(\(R = RelationToMatrix[L6, shift];\)\), "\n", \(\(g1 = PlotMatrix[R];\)\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Note that for every ", Cell[BoxData[ \(TraditionalForm\`x\)]], " there is exactly one", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(y\)\)\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\ y\)]], ". There are precisely two ", Cell[BoxData[ \(TraditionalForm\`x\)]], "'s such that ", Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\ x\)]], ". Namely ??? \nAny ideas what the next picture will look like? We are \ using the command ", StyleBox["TransitiveClosure", "MR"], " that computes ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^+\)\)]], ". It will be explained in detail in the next chapter. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(RR = TransitiveClosure[R];\)\), "\n", \(\(g2\ = \ PlotMatrix[RR];\)\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Why is the diagonal in there? In other words, why is the transitive \ closure already reflexive? In general, what do we need to know about \[Rho] \ to conclude that ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^*\)\ = \ \(\[Rho]\^+\)\)]], " ?\nThe picture also looks symmetric, so the transitive closure here \ appears to be an equivalence relation. Let's check symmetry (yes, in fact we \ have another doubly symmetric picture)." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(BooleanConverse[RR] === RR\)], "Input"], Cell[TextData[{ "What are the equivalence classes? We compute the partition on L6 induced \ by ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^+\)\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(part = ToClasses[L6, RR, Type \[Rule] Matrix];\)\), "\n", \(Length[part]\), "\n", \(Length /@ part\)}], "Input", AspectRatioFixed->True], Cell["\<\ Again, we can use this partition to reorder L6: we put all \ elements in the first block of the partition first, then the elements of the \ second block, and so forth. \ \>", "Text"], Cell[BoxData[{ \(\(AA\ = \ Flatten[part, 1];\)\), "\n", \(Short[AA, 5]\)}], "Input"], Cell["\<\ With this reordering of the universe, the relation itself looks a \ bit less appealing.\ \>", "Text"], Cell[BoxData[{ \(\(R = RelationToMatrix[AA, shift\ ];\)\), "\n", \(\(PlotMatrix[R];\)\)}], "Input", AspectRatioFixed->True], Cell["\<\ A bit strange. But the closure now really takes on a very simple \ form. From the next picture it is easy to see that the transitive closure of \ \[Rho] really is an equivalence relation. \ \>", "Text"], Cell[BoxData[{ \(\(RR = TransitiveClosure[R];\)\), "\[IndentingNewLine]", \(\(PlotMatrix[RR];\)\)}], "Input", AspectRatioFixed->True], Cell["\<\ It is important to realize that the last two pairs of pictures are \ very closely related (no pun intended). Both pairs provide visualizations of \ the same relation. You have to be careful with pictures, there are many ways \ the same object can be translated into a graphical object.\ \>", "Text"], Cell[TextData[{ "At any rate, what would happen if we were to consider lists of length 7 \ instead? Lists of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], " in general?" }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Reversal", "Subsubsection", CellTags->"c:34"], Cell["\<\ The last example was based on rotation of lists. Clearly, this \ opens up endless opportunity to produce more relations by using different \ operations. For example, here is reversal.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(R = RelationToMatrix[L6, Reverse[#1] === #2 &\ ];\)\), "\n", \(\(PlotMatrix[R];\)\), "\n", \(\(RR = TransitiveClosure[R];\)\), "\n", \(\(PlotMatrix[RR];\)\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "This time, the transitive closure only adds the diagonal. In other \ words, ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^+\)\ = \ \[Rho]\ \[Union] \ Id\)]], ", and the transitive closure is none other than the reflexive closure. \ Why? Again, symmetry is apparent from the picture, so ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^+\)\)]], " is an equivalence relation. Here is the partition." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(part = ToClasses[L6, RR, Type \[Rule] Matrix];\)\), "\n", \(Length[part]\), "\n", \(Length /@ part\), "\n", \(\(%\ // \ Frequencies\)\ // \ TableForm\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "There are only two types of equivalence classes: those consisting of a \ single element, and those containing exactly two elements. Can you see which \ lists form the 8 singletons? Why are there exactly 8? Don't look at ", StyleBox["part", "MR"], " right away, think first." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Bitwise Order", "Subsubsection", CellTags->"c:35"], Cell[TextData[{ "As a last example, let's define a partial order on L6: ", StyleBox["less1[x,y]", "MR"], " means that ", Cell[BoxData[ \(TraditionalForm\`y\)]], " can be obtained from ", Cell[BoxData[ \(TraditionalForm\`x\)]], " by turning on one more bit. First, an auxiliary function that checks if \ every bit in ", Cell[BoxData[ \(TraditionalForm\`x\)]], " is less than or equal to the corresponding bit in ", Cell[BoxData[ \(TraditionalForm\`y\)]], ". A nice Mathematica hack, too." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(listless[x_, y_] := And @@ Thread[\ x\ \[LessEqual] \ y];\)\)], "Input", AspectRatioFixed->True], Cell["\<\ listless[ {0,1,1,0,0,0}, {0,1,1,0,0,1}] listless[ {0,1,1,0,1,1}, {0,1,1,0,0,1}]\ \>", "Input"], Cell[BoxData[ \(\(less1[x_, y_] := Count[y, 1] - Count[x, 1] == 1 && listless[x, y];\)\)], "Input", AspectRatioFixed->True], Cell["\<\ less1[ {0,1,1,0,0,0}, {0,1,1,0,0,1}] less1[ {0,1,1,0,0,0}, {0,1,1,0,1,1}]\ \>", "Input"], Cell[BoxData[{ \(\(R = RelationToMatrix[L6, less1];\)\), "\n", \(\(PlotMatrix[R];\)\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "An irreflexive, asymmetric, and non-transitive relation. Note that for any \ ", Cell[BoxData[ \(TraditionalForm\`x\)]], " there are at most 6 lists ", Cell[BoxData[ \(TraditionalForm\`y\)]], " such ", Cell[BoxData[ \(TraditionalForm\`x\ \[Rho]\ y\)]], ". There is exactly one ", Cell[BoxData[ \(TraditionalForm\`x\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ y\ \ \(\[Not] \ x\ \[Rho]\ y\)\)]], " (look at the last row in the picture). Here are the number of \ relationships for all elements, and the frequencies. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Map[\ Count[#, 1] &, \ R\ ]\), "\n", \(TableForm[Frequencies[%]]\)}], "Input", AspectRatioFixed->True], Cell["\<\ Symmetry. Do these numbers look vaguely familiar? What do they \ mean? The transitive closure also looks somewhat unexpected.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(RR = TransitiveClosure[R];\)\), "\n", \(\(PlotMatrix[RR, GridLines \[Rule] False];\)\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Voila, fractals hiding in binary lists. \nHow about ", StyleBox["listless", "MR"], "? It turns out that ", StyleBox["listless", "MR"], " is the reflexive transitive closure of ", StyleBox["less1.", "MR"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(S = RelationToMatrix[L6, listless];\)\), "\n", \(\(PlotMatrix[S];\)\)}], "Input", AspectRatioFixed->True] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Implementation and Representation", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:36"], Cell[CellGroupData[{ Cell[" Standard Implementations", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:37"], Cell[TextData[{ "Now that we have a whole long list of properties of relations, and \ operations on them, we can seriously return to the issue of implementation. \ The question arises, how does one perform the various operations on relations \ computationally? And how can one test the various properties? How does one \ compute the closures? \nAs always, when one tries to implement a mathematical \ model as a data type, additional complications arise. For example, one has to \ worry about initialization, destruction, memory management in general, \ performance, and so on. For example, the most important operation often is \ the basic query: given elements ", Cell[BoxData[ \(TraditionalForm\`a, \ b\ \[Element] \ A\)]], ", and an implementation of a binary relation \[Rho] on ", Cell[BoxData[ \(TraditionalForm\`A\)]], ":\n\ttest if ", Cell[BoxData[ \(TraditionalForm\`a\ \[Rho]\ b\)]], " holds. \nIn a static situation, where \[Rho] is built once and then \ never changed, the primary concern is usually to make queries fast. \ Different problems arise when the relation itself is dynamic and has to be \ changed. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "We have seen three very basic ways of representing relations. \n\t(1) \ sets of pairs,\n\t(2) Boolean matrices,\n\t(3) Boolean functions.\nOf \ course, approaches (1) and (2) only work for relations on a fixed finite \ set ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", and if fact only for rather small sets. Also, for the matrices we have \ to fix an enumeration of ", Cell[BoxData[ \(TraditionalForm\`A\)]], ": \n\t", Cell[BoxData[ \(TraditionalForm\`A\ = \ {a\_1, a\_2, ... , a\_n}\)]], ".\nOften, it may be a good idea to keep a table of the enumeration and \ then deal exclusively with relations on ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\([n]\)\ = \ {1, 2, ... , n}\)\)\)]], " rather than the set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " itself. \nApproach (3) is more flexible, but causes headaches when it \ comes to actually implementing operations. Union, intersection, complement, \ and converse are simple, but composition becomes very hard. For example, we \ know that ", Cell[BoxData[ \(TraditionalForm\`\(\(<\)\(\ \)\(\(\[SmallCircle]\)\(\ \ \)\(<\)\)\)\)]], " on the rational numbers is just ", Cell[BoxData[ \(TraditionalForm\` < \)]], " itself, but how is an algorithm implementing relational composition \ supposed to figure this out? And the algorithm would also have to know that \ things change when Less is considered to be a relation over the integers. \n\ We will use Boolean functions mostly as a convenient way of generating \ example relations. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "For our purposes, Boolean matrices are the best solution. Note, though, \ that the size of such a matrix is ", Cell[BoxData[ \(TraditionalForm\`\[CapitalTheta](n\^2)\)]], ", which translates into a rather large data structure even for moderate \ values of ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". Also, algorithms will tend to take ", Cell[BoxData[ \(TraditionalForm\`\[CapitalOmega](n\^2)\)]], " steps, since usually we have to read every bit in the data structure. One \ notable, and important exception is the basic query \"does ", Cell[BoxData[ \(TraditionalForm\`a\ \[Rho]\ b\)]], " hold?\"This boils down to a look-up in the matrix, and can be done in ", Cell[BoxData[ \(TraditionalForm\`O(1)\)]], " steps. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Sets and Lists", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:38"], Cell[CellGroupData[{ Cell[" Basics", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:39"], Cell[TextData[{ "Just for the sake of completeness, let us take a quick look at the \ set-of-pairs representation. In the most primitive implementation, the set is \ given by a list (a linked list, or an array), and the list contains precisely \ those pairs ", Cell[BoxData[ \(TraditionalForm\`\[LeftAngleBracket]a, b\[RightAngleBracket]\)]], " for which ", Cell[BoxData[ \(TraditionalForm\`a\ \[Rho]\ b\)]], " holds. \nGiven a Boolean function for \[Rho], it is easy to convert the \ function into a list of pairs over the carrier set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " (use ", StyleBox["Select", FontFamily->"Courier"], " on the Cartesian product ", Cell[BoxData[ \(TraditionalForm\`A\ \[Cross]\ A\)]], ", see the definitions above). " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "For example, here is the list that represents the divisibility relation on \ the set ", Cell[BoxData[ \(TraditionalForm\`\([n]\)\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(PairList[rel_, A_List] := Select[CartesianProduct[A, A], rel[#1\[LeftDoubleBracket]1\[RightDoubleBracket], #1\ \[LeftDoubleBracket]2\[RightDoubleBracket]] &];\)\), "\n", \(\(PairList[rel_, n_Integer] := PairList[rel, Range[n]];\)\)}], "InputOnly", AspectRatioFixed->True], Cell[BoxData[ \(div = PairList[Mod[#2, #1] == 0 &, Range[10]]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "To test whether the relation holds, we have to search for the \ corresponding pair in the list. Note that this might take ", Cell[BoxData[ \(TraditionalForm\`\(\(O(n\^2)\)\(\ \)\)\)]], " steps, depending on how large \[Rho] is, and how bad our searching \ method. This is much worse than the ", Cell[BoxData[ \(TraditionalForm\`O(1)\)]], " for Boolean matrices. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(MemberQ[div, {3, 9}]\), "\n", \(MemberQ[div, {3, 5}]\)}], "Input", AspectRatioFixed->True], Cell["\<\ How easy is it to implement all the operations on relations, given \ a list-of-pairs data structure? Some are easy. For example, the converse \ can be obtained as follows.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(converse[LL_List] := Map[Reverse, LL];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(converse[div]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "How about composition? This is more interesting, since we have to search \ for a witness. Here is a nice hack in ", StyleBox["Mathematica", FontSlant->"Italic"], ". Note that \"nice hack\" really translates into: there is no graceful \ method. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(composition[L1_List, L2_List] := \n\t Union[Cases[ CartesianProduct[L1, L2], {{_, x_}, {x_, _}}] /. {{x_, _}, {_, y_}} \[Rule] {x, y}]\)], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(composition[div, div]\), "\n", \(% === div\)}], "Input", AspectRatioFixed->True], Cell["\<\ Make sure to figure out how to deal with the other operations in \ this setting. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Pictures", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:40"], Cell[TextData[{ "One reason to consider the representation of a relation as a list of pairs \ is visualization. We can draw a picture of the relation by drawing two rows \ of points, representing the elements of ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", and a line indicating that the two elements are related by \[Rho]. This \ will be particularly useful in the next chapter on functions. Here is the \ basic picture: " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[\ Less, 5, 1];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "It is helpful to label the points, in particular when ", Cell[BoxData[ \(TraditionalForm\`A\)]], " is a set of integers. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[\ Less, \ 5, 1, LabelGrid \[Rule] Automatic];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[\ GCD[#1, #2] == 1 &, 8, 1, LabelGrid \[Rule] Automatic];\)\)], "Input", AspectRatioFixed->True] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Boolean Matrices and Networks", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:41"], Cell[CellGroupData[{ Cell[" The Basics", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:42"], Cell[TextData[{ "From now on, we will only consider Boolean matrix representations. \ Actually, to make life a little easier in Mathematica, we will use binary \ matrices (i.e., entries are of type Integer and restricted to 0 and 1) rather \ than Boolean ones. The reason for this is that a we can use arithmetic on \ those matrices, and since arithmetic in Mathematica behaves properly with \ respect to lists and matrices, that makes the implementation much easier. \ Yes, efficiency be damned. \n\nThe basic correspondence is very simple: the \ relation ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[SubsetEqual] \ A\ \[Cross]\ A\)]], " where ", Cell[BoxData[ \(TraditionalForm\`A\ = \ {a\_1, a\_2, ... , a\_n}\)]], " is represented by the ", Cell[BoxData[ \(TraditionalForm\`n\)]], " by ", Cell[BoxData[ \(TraditionalForm\`n\)]], " Boolean (or binary) matrix ", Cell[BoxData[ \(TraditionalForm\`M\_\[Rho]\)]], " defined by\n\t", Cell[BoxData[ \(TraditionalForm\`M\_\[Rho]\[LeftDoubleBracket]i, j\[RightDoubleBracket]\ = \ 1\ \ \ \ \ iff\ \ \ \ a\_i\ \[Rho]\ a\_j\ \ holds\)]], ".\nRecall that we can plot pretty pictures of Boolean matrices, so we can \ visualize our operations. First, converse and complement. Always remember, \ we are dealing with binary matrices. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(BooleanConverse[R_?MatrixQ] := Transpose[R];\)\), "\n", \(\(BooleanComplement[R_?MatrixQ] := 1 - R;\)\)}], "InputOnly", AspectRatioFixed->True], Cell[TextData[{ "You might wish to recall at this point how Mathematica deals with \ instructions like ", Cell[BoxData[ \(TraditionalForm\`1\ - \ L\)]], " when ", Cell[BoxData[ \(TraditionalForm\`L\)]], " is a list: pointwise. Since a matrix is a list of lists, we are \ actually producing the matrix that has entry ", Cell[BoxData[ \(TraditionalForm\`1\ - \ L\[LeftDoubleBracket]i, j\[RightDoubleBracket]\)]], " in position ", Cell[BoxData[ \(TraditionalForm\`\((i, j)\)\)]], ". Here is a trace of addition between a matrix and a number in general:" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[a, b, c, d]; \ Unprotect[X];\), "\n", \(TableForm[Trace[{{a, b}, {c, d}} + X]]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Some examples. Let's consider the ordinary ", StyleBox["Less", "MR"], " relation on ", Cell[BoxData[ \(TraditionalForm\`A\ = \ {1, 2, ... , 10}\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(R = RelationToMatrix[10, Less]\), "\n", \(\(g1\ = \ PlotMatrix[R, GridLines \[Rule] True];\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(BooleanConverse[R]\), "\n", \(\(g2 = \ PlotMatrix[BooleanConverse[R], GridLines \[Rule] True];\)\)}], "Input",\ AspectRatioFixed->True], Cell["\<\ So, the converse is just a reflection along the diagonal, as \ predicted. How about complement? \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(BooleanComplement[R]\), "\n", \(\(g3 = PlotMatrix[BooleanComplement[R], GridLines \[Rule] True];\)\)}], "Input", AspectRatioFixed->True], Cell["\<\ Bit-wise complement, as one might suspect. Here are all three. \ \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(ShowArray[{g1, g2, g3}, 3];\)\)], "Input", AspectRatioFixed->True], Cell["\<\ The other Boolean operations are also straightforward, we just have \ to perform the operations pointwise, for each element in the matrix. \ \>", \ "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(R1 = RelationToMatrix[8, Less];\)\), "\n", \(\(R2 = RelationToMatrix[8, 9 - #1 \[LessEqual] #2 &];\)\), "\n", \(\(g1 = PlotMatrix[R1, GridLines \[Rule] True, DisplayFunction \[Rule] Identity];\)\), "\n", \(\(g2 = PlotMatrix[R2, GridLines \[Rule] True, DisplayFunction \[Rule] Identity];\)\), "\n", \(\(g3 = PlotMatrix[BooleanIntersection[R1, R2], GridLines \[Rule] True, DisplayFunction \[Rule] Identity];\)\), "\n", \(\(g4 = PlotMatrix[BooleanUnion[R1, R2], GridLines \[Rule] True, DisplayFunction \[Rule] Identity];\)\)}], "Input", AspectRatioFixed->True], Cell["ShowArray[{g1,g2,g3,g4}];", "Input"] }, Closed]], Cell[CellGroupData[{ Cell[" Composition and Transitive Closure", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:43"], Cell["\<\ Now for relational composition, a real beauty that bears some \ detailed explanation.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(BooleanComposition[RR__?MatrixQ] := Sign[Dot[RR]];\)\)], "InputOnly", AspectRatioFixed->True], Cell[TextData[{ "The ", StyleBox["Dot[]", FontFamily->"Courier"], " here stand for matrix multiplication. Note that we have to apply the ", StyleBox["Sign", FontFamily->"Courier"], " function in the last definition: Mathematica does not know that we are \ interested only in binary matrices, it performs the matrix multiplication \ using ordinary integers. As a result, some of the entries may be larger than \ 1, and we have to replace them by 1 in the end to get back a binary matrix. \ In fact, we really should be using Boolean matrices, but Mathematica does not \ know how to multiply Boolean matrices. We could add the necessary \ definitions, but it's easier to use the trick with integers and ", StyleBox["Sign", FontFamily->"Courier"], ". Of course, this is somewhat of a hack. \n\nAlso note that the \ definition allows for composition of not just two but any number of \ relations, since ", Cell[BoxData[ FormBox[ StyleBox["RR", "MR"], TraditionalForm]]], " is a sequence of 1 or more matrices, which is simply handed over to ", StyleBox["Dot", FontFamily->"Courier"], ". Clever, huh? " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Since ", Cell[BoxData[ \(TraditionalForm\` < \)]], " is certainly transitive but not reflexive, we should expect ", Cell[BoxData[ \(TraditionalForm\`\( < \^2\)\)]], " to come out smaller than < when we apply ", StyleBox["BooleanComposition", FontFamily->"Courier"], ". Recall that we are dealing with a universe of integers here, not with \ rationals or reals. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(R = RelationToMatrix[\ 10, Less\ ];\)\)], "Input"], Cell[BoxData[ \(\(PlotMatrix[BooleanComposition[R, R], GridLines \[Rule] True];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "And ", Cell[BoxData[ \(TraditionalForm\`\( < \^3\)\)]], " is smaller still." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotMatrix[BooleanComposition[R, R, R], GridLines \[Rule] True];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Here is a picture of ", Cell[BoxData[ \(TraditionalForm\`\( < \^\(\(\ \)\(2\)\)\)\)]], " through ", Cell[BoxData[ \(TraditionalForm\`\( < \^\(\(\ \)\(10\)\)\)\)]], "." }], "Text"], Cell[BoxData[ \(\(ShowArray[ Table[\ PlotMatrix[ BooleanComposition @@ Table[R, {i}], \[IndentingNewLine]\t GridLines \[Rule] True, DisplayFunction \[Rule] Identity], {i, 2, 10}]];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "So, ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^10\)]], " is the empty relation. That's fine, since we already know that ", Cell[BoxData[ \(TraditionalForm\`a\ \[Rho]\^k\ b\ \ \ iff\ \ \ a\ \[LessEqual] \ b\ - \ k\)]], ", and we are only considering the carrier set ", Cell[BoxData[ \(TraditionalForm\`A\ = \ {1, 2, ... , 10}\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "One last example before we explain how composition is implemented: \ lexicographic order on strings. Since you already have `automata' loaded, it \ is easy to generate all words up to length 4 over the two-element alphabet ", Cell[BoxData[ \(TraditionalForm\`{a, b}\)]], ". Note that we have to use ", StyleBox["OrderedQ", FontFamily->"Courier"], " here, the \[LessEqual] symbol in Mathematica is not overloaded with \ lexigraphic order for strings. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(W = Rest[Words[\(-4\), 2]]\)], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(\(R = RelationToMatrix[W, OrderedQ[\ {#1, #2}] &];\)\), "\n", \(\(PlotMatrix[R];\)\)}], "Input", AspectRatioFixed->True], Cell["\<\ Since this relation is supposedly a total order, its square should \ be just R:\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(BooleanComposition[R, R] === R\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Here is the picture for alphabet ", Cell[BoxData[ \(TraditionalForm\`{a, b, c}\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(W = Rest[Words[\(-4\), 3]]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotMatrix[RelationToMatrix[W, OrderedQ[{#1, #2}] &]];\)\)], "Input", AspectRatioFixed->True], Cell["\<\ Can you see the antisymmetry of the relation in this picture?\ \>", \ "Text"] }, Closed]], Cell[CellGroupData[{ Cell[" Matrix Multiplication", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:44"], Cell[TextData[{ "The implementation for ", StyleBox["BooleanComposition", FontFamily->"Courier"], " from the last section is somewhat less than obvious. It helps to go back \ a step and to first try to determine the meaning of the matrix multiplication \ used in the definition of ", StyleBox["RComposition", FontFamily->"Courier"], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(Information["\", LongForm \[Rule] False]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Thanks.\nLet's try a small example. We multiply a ", Cell[BoxData[ \(TraditionalForm\`4\[Cross]3\)]], " matrix ", Cell[BoxData[ \(TraditionalForm\`A\)]], " with a ", Cell[BoxData[ \(TraditionalForm\`3\[Cross]2\)]], " matrix ", Cell[BoxData[ \(TraditionalForm\`B\)]], ". The result will be a ", Cell[BoxData[ \(TraditionalForm\`4\ \[Cross]\ 2\)]], " product matrix. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[a, b, A, B]\), "\n", \(A = Array[a\_\(#1, #2\) &, {4, 3}]\), "\n", \(B = Array[b\_\(#1, #2\) &, {3, 2}]\), "\n", \(MatrixForm[A]\), "\n", \(MatrixForm[B]\), "\n", \(MatrixForm[A . B]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Note carefully how the indices work. \nIn general, we have a matrix ", Cell[BoxData[ \(TraditionalForm\`A\)]], " that is ", Cell[BoxData[ \(TraditionalForm\`n\ \[Cross]\ p\)]], ", a matrix ", Cell[BoxData[ \(TraditionalForm\`B\)]], " that is ", Cell[BoxData[ \(TraditionalForm\`p\ \[Cross]\ m\)]], ", and obtain a product matrix ", Cell[BoxData[ \(TraditionalForm\`C\)]], " that is ", Cell[BoxData[ \(TraditionalForm\`n\ \[Cross]\ m\)]], ". To get the entry in position ", Cell[BoxData[ \(TraditionalForm\`\((i, j)\)\)]], " of the product matrix ", StyleBox["C = Dot[A,B]", FontFamily->"Courier"], ", one has to compute the product of the i-th row in ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", and the j-th column in ", Cell[BoxData[ \(TraditionalForm\`B\)]], ": \n\t", Cell[BoxData[ \(TraditionalForm\`C\_\(i, j\) = \ \[Sum]\_l\ A\_\(i, l\)\ \[CenterDot]\ \ B\_\(l, j\)\)]], " \nwhere the summation is over ", Cell[BoxData[ \(TraditionalForm\`l\ \[Element] \ \([p]\)\)]], ". Actually, we are only interested in the special case ", Cell[BoxData[ \(TraditionalForm\`n\ = \ \(p\ = \ m\)\)]], ", so all the matrices are ", Cell[BoxData[ \(TraditionalForm\`n\ \[Cross]\ n\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Let us calculate the product of a binary matrix by itself. First, \ the matrix for Less. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(R = RelationToMatrix[5, Less];\)\), "\n", \(MatrixForm[R]\), "\n", \(MatrixForm[R . R]\)}], "Input", AspectRatioFixed->True], Cell["Here is the matrix for LessEqual. ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(R = RelationToMatrix[5, LessEqual];\)\), "\n", \(MatrixForm[R]\), "\n", \(MatrixForm[R . R]\)}], "Input", AspectRatioFixed->True], Cell["\<\ A relation built from GCD and LessEqual (just an example, it has no \ particular significance). \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(R = RelationToMatrix[\ 10, GCD[#1, 3] \[LessEqual] GCD[#2, 3] &\ ];\)\), "\n", \(MatrixForm[R]\), "\n", \(MatrixForm[R . R]\)}], "Input", AspectRatioFixed->True], Cell["\<\ A frivolous exercise: we plot pictures of these matrices. We have \ to make sure we don't run out of colors (the standard plotting command only \ deals with matrices whose entries are 0 through 9). \ \>", "Text"], Cell[BoxData[{ \(\(cols\ = \ HueRasterColors[Max[R . R] + 1];\)\), "\n", \(\(PlotMatrix[R . R, RasterStyle \[Rule] cols];\)\)}], "Input"], Cell["\<\ Very Scottish. And lastly, inspired by the previous relation, a \ random relation. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(R = Table[Random[Integer], {10}, {10}];\)\), "\n", \(MatrixForm[R]\), "\n", \(MatrixForm[R . R]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(cols\ = \ HueRasterColors[Max[R . R] + 1]; gr1\ = \ PlotMatrix[R, RasterStyle \[Rule] cols, DisplayFunction \[Rule] Identity];\), "\n", \(\(gr2\ = \ PlotMatrix[R . R, RasterStyle \[Rule] cols, DisplayFunction \[Rule] Identity];\)\), "\n", \(\(ShowArray[{gr1, gr2}];\)\)}], "Input", AspectRatioFixed->True], Cell["Absolutely gorgeous. But what does it all mean? ", "Text"] }, Closed]], Cell[CellGroupData[{ Cell[" Networks and Paths", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:45"], Cell[TextData[{ "There is yet another way to visualize binary relations on a set that has \ many advantages, and makes it much easier to understand some of the \ operations, and in particular transitive closure. As always, consider a \ relation ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[SubsetEqual] \ A\ \[Cross]\ A\)]], " where ", Cell[BoxData[ \(TraditionalForm\`A\ = \ {a\_1, a\_2, ... , a\_n}\)]], ". We can think of the elements ", Cell[BoxData[ \(TraditionalForm\`a\_i\)]], " as nodes in a network. The relation \[Rho] can be represented by \ directed edges. More precisely, we draw an arrow from node ", Cell[BoxData[ \(TraditionalForm\`a\)]], " to node ", Cell[BoxData[ \(TraditionalForm\`b\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`a\ \[Rho]\ b\)]], ". The idea is that we can send a message from node ", Cell[BoxData[ \(TraditionalForm\`a\)]], " to node ", Cell[BoxData[ \(TraditionalForm\`b\)]], " directly, in one hop. To send a message to a node that is not directly \ adjacent we have to chain together several such steps. \nHere is an example: \ \n\t ", Cell[BoxData[ \(TraditionalForm\`A\ = \ {1, 2, 3, 4, 5}\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ = \ {\ \((1, 2)\), \((2, 3)\), \((3, 4)\), \((4, 5)\), \((5, 1)\)}\)]], ". \nThus, the network is a simple cycle of length 5. \nHere is the \ matrix:" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ R = NestList[ RotateRight, {0,1,0,0,0}, 4 ]; R // MatrixForm\ \>", "Input"], Cell[TextData[{ "The matrix ", Cell[BoxData[ \(TraditionalForm\`R\^\(\(\ \)\(2\)\)\)]], " shows which nodes are connected by a path of length 2:" }], "Text"], Cell["R.R // MatrixForm", "Input"], Cell["R.R.R // MatrixForm", "Input"], Cell[TextData[{ "Note that we are only getting paths of length exactly equal to 2. If we \ want all paths of length at most 2 we have to add up ", Cell[BoxData[ \(TraditionalForm\`R\)]], ", ", Cell[BoxData[ \(TraditionalForm\`R\^2\)]], " and also the identity matrix (1's along the diagonal, 0's everywhere \ else). The last matrix accounts for paths of lengths 0. " }], "Text"], Cell["IdentityMatrix[5] + R + R.R // MatrixForm", "Input"], Cell[TextData[{ "Note that we are only getting paths of length exactly equal to 2. If we \ want all paths of length at most 2 we have to add up ", Cell[BoxData[ \(TraditionalForm\`R\)]], ", ", Cell[BoxData[ \(TraditionalForm\`R\^2\)]], " and also the identity matrix (1's along the diagonal, 0's everywhere \ else). The last matrix accounts for paths of lengths 0. " }], "Text"], Cell["IdentityMatrix[5] + R + R.R // MatrixForm", "Input"], Cell["\<\ It is intuitively clear that it will take at most 4 steps to get to \ any node in our network.\ \>", "Text"], Cell["IdentityMatrix[5] + R + R.R + R.R.R + R.R.R.R // MatrixForm", "Input"], Cell[TextData[{ "The last example is a bit misleading in that for any two nodes there is at \ most one path of a given length that connects them. In general, there may be \ several such paths. We can add a link to our cycle. \n\t ", Cell[BoxData[ \(TraditionalForm\`A\ = \ {1, 2, 3, 4, 5}\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ = \ {\ \((1, 2)\), \((1, 3)\), \((2, 3)\), \((3, 4)\), \((4, 5)\), \((5, 1)\)}\)]], ". " }], "Text"], Cell["\<\ R[[1,3]] = 1; R // MatrixForm\ \>", "Input"], Cell["If we go far enough, there will now be multiple paths.", "Text"], Cell["MatrixPower[R,12] // MatrixForm", "Input"], Cell[TextData[{ "The last matrix ", Cell[BoxData[ \(TraditionalForm\`R\^12\)]], " provides more information than we actually want: for example, there are \ 3 paths from node 1 to node 4 and node 5. " }], "Text"], Cell[TextData[{ "At any rate, we now have a good explanation for the product matrices ", Cell[BoxData[ \(TraditionalForm\`R\^\(\(\ \)\(k\)\)\)]], " in terms of networks. There are ", Cell[BoxData[ \(TraditionalForm\`n\ = \ \(\(|\)\(\(A\)\(|\)\)\)\)]], " nodes in the network, and a 1 in position ", Cell[BoxData[ \(TraditionalForm\`\((i, j)\)\)]], " indicates that there is a link from node ", Cell[BoxData[ \(TraditionalForm\`i\)]], " to node ", Cell[BoxData[ \(TraditionalForm\`j\)]], ". Now consider the ", Cell[BoxData[ \(TraditionalForm\`\((i, j)\)\)]], "-th entry in the product matrix \n\n\t", Cell[BoxData[ \(TraditionalForm\`C\_\(i, j\) = \ \[Sum]\_l\ R\_\(i, l\)\ \[CenterDot]\ \ R\_\(l, j\)\)]], " \n \nwhere the summation is over ", Cell[BoxData[ \(TraditionalForm\`l\ = \ 1, 2, ... , n\)]], ". In order for a term ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(R\_\(i, l\)\ \[CenterDot]\ \ R\_\(l, j\)\)\ \)\)]], " to make a contribution, both components have to 1. Hence, we are really \ counting the number of paths of length 2 from node ", Cell[BoxData[ \(TraditionalForm\`i\)]], " to node ", Cell[BoxData[ \(TraditionalForm\`j\)]], ": every such path has to go through some intermediate node ", Cell[BoxData[ \(TraditionalForm\`l\)]], ", and we sum up over all these nodes. Yes, ", Cell[BoxData[ \(TraditionalForm\`l\)]], " is the witness that demonstrates that ", Cell[BoxData[ \(TraditionalForm\`\((i, j)\)\ \[Element] \ \[Rho]\^2\)]], " if we think of the matrix ", Cell[BoxData[ \(TraditionalForm\`R\)]], " representing a relation \[Rho]. Thus, ", Cell[BoxData[ \(TraditionalForm\`R\^2\)]], " tells us how many paths of length 2 there are in our network. In \ hindsight, the matrix ", Cell[BoxData[ \(TraditionalForm\`R\)]], " itslef tells us how many paths of length 1 there are: those are just the \ ordinary links. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Now it's time for a wild conjecture: \n\n", StyleBox["Theorem:", FontWeight->"Bold"], " ", Cell[BoxData[ \(TraditionalForm\`\(R\^\(\(\ \)\(k\)\)\)\[LeftDoubleBracket]i, j\[RightDoubleBracket]\)]], " is the number of paths of length ", Cell[BoxData[ \(TraditionalForm\`k\)]], " from node ", Cell[BoxData[ \(TraditionalForm\`i\)]], " to node ", Cell[BoxData[ \(TraditionalForm\`j\)]], ", for all ", Cell[BoxData[ \(TraditionalForm\`k\ \[GreaterEqual] \ 0\)]], ". \n\nProof: By induction on ", Cell[BoxData[ \(TraditionalForm\`k\)]], ". \nBase step: we can start at ", Cell[BoxData[ \(TraditionalForm\`k = 0\)]], " or ", Cell[BoxData[ \(TraditionalForm\`k = 1\)]], ". In either case, the claim is immediate \n(needless to say, it is \ immediate only if we know what ", Cell[BoxData[ \(TraditionalForm\`R\^\(\(\ \)\(0\)\)\)]], " is for a matrix; by convention, it's the diagonal matrix with 1's on the \ diagonal, and 0's everywhere else). \nInduction step: suppose the claim \ correct for ", Cell[BoxData[ \(TraditionalForm\`k\)]], ", so ", Cell[BoxData[ \(TraditionalForm\`\(R\^k\)\[LeftDoubleBracket]i, j\[RightDoubleBracket]\)]], " is the number of paths of length ", Cell[BoxData[ \(TraditionalForm\`k\)]], " from node ", Cell[BoxData[ \(TraditionalForm\`i\)]], " to node ", Cell[BoxData[ \(TraditionalForm\`j\)]], ". Now consider an arbitrary path of length ", Cell[BoxData[ \(TraditionalForm\`k + 1\)]], " from ", Cell[BoxData[ \(TraditionalForm\`i\)]], " to ", Cell[BoxData[ \(TraditionalForm\`j\)]], ". We can decompose this path into an initial segment of length ", Cell[BoxData[ \(TraditionalForm\`k\)]], ", and a final link (a path of length 1). But then the number of all such \ paths is by IH: \n\t", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\[Sum]\_l\ R\_\(i, l\)\%k\ \[CenterDot]\ \ R\_\(l, j\)\ = \ \(R\^\(k + 1\)\)\[LeftDoubleBracket]i, j\[RightDoubleBracket]\)\)\)]], " \nby the definition of matrix multiplication. \n\[EmptySquare]" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Now, what does that have to do with composition of relations? If we think \ of the relation \[Rho] as a network, where the nodes are the elements in the \ carrier set, and there is a link from ", Cell[BoxData[ \(TraditionalForm\`i\)]], " to", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(j\)\)\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`i\ \[Rho]\ j\)]], " holds iff ", Cell[BoxData[ \(TraditionalForm\`R\[LeftDoubleBracket]i, j\[RightDoubleBracket]\ = \ 1\)]], ", then ", Cell[BoxData[ \(TraditionalForm\`\(R\^\(\(\ \)\(2\)\)\)\[LeftDoubleBracket]i, j\[RightDoubleBracket]\ > \ 0\)]], " means exactly that there is a path of length 2 in the network from ", Cell[BoxData[ \(TraditionalForm\`i\)]], " to ", Cell[BoxData[ \(TraditionalForm\`j\)]], ". The intermediate node is none other than the witness for ", Cell[BoxData[ \(TraditionalForm\`i\)]], " and ", Cell[BoxData[ \(TraditionalForm\`j\)]], ". In general,\n\t", Cell[BoxData[ \(TraditionalForm\`\(\(i\ \[Rho]\^k\ j\ \ \ \ iff\ \ \ \(R\^\(\(\ \)\(k\ \)\)\)\[LeftDoubleBracket]i, j\[RightDoubleBracket]\)\(\ \)\(>\)\(\ \)\(0\)\(\ \)\)\)]], " iff there is a path of length ", Cell[BoxData[ \(TraditionalForm\`k\)]], " in the network from ", Cell[BoxData[ \(TraditionalForm\`i\)]], " to ", Cell[BoxData[ \(TraditionalForm\`j\)]], ". \n\nFor our purposes, we actually don't need to know how many paths \ there are, we only distinguish between 0 or more. This is accomplished by \ applying the ", StyleBox["Sign", "MR"], " function to the integer matrix: 0 remains 0, but all positive entries are \ scaled back to 1. \n\nThat's how ", StyleBox["BooleanComposition", "MR"], " works. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Representing Relations", "Subsubsection", CellTags->"c:46"], Cell[TextData[{ "We can now summarize the crucial properties of the represenation of \ binary relations by Boolean matrices. The basic operations on relations such \ as union, intersection, converse and so on, can all be readily translated \ into operations on the matrices. For example, \n- the relational union ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[Union] \ \[Sigma]\)]], " is given by ", Cell[BoxData[ \(TraditionalForm\`Sign[\ R\ + \ S\ ]\)]], ", \n- the relational intersection ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[Intersection] \ \[Sigma]\)]], " is given by ", Cell[BoxData[ \(TraditionalForm\`R\ *\ S\)]], " (Mathematica performs multiplication pointwise!), \n- the relational \ complement of \[Rho] is given by ", Cell[BoxData[ \(TraditionalForm\`1\ - \ R\)]], " (Mathematica performs subtraction pointwise!). \n\nThe connection \ between matrix multiplication and relational composition is as follows. \n\n\ ", StyleBox["Theorem", FontWeight->"Bold"], ": Let ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\)]], " be a relation from ", Cell[BoxData[ \(TraditionalForm\`A\)]], " to ", Cell[BoxData[ \(TraditionalForm\`B\)]], ", and ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], " a relation from ", Cell[BoxData[ \(TraditionalForm\`B\)]], " to ", Cell[BoxData[ \(TraditionalForm\`C\)]], ", and let ", Cell[BoxData[ \(TraditionalForm\`R\)]], " and ", Cell[BoxData[ \(TraditionalForm\`S\)]], " be the corresponding binary matrices. Then ", Cell[BoxData[ \(TraditionalForm\`\(\(Sign[\ R\ \[CenterDot]\ S\ ]\)\(\ \)\)\)]], " is the matrix representing the relational composition ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[SmallCircle]\ \[Sigma]\)]], ". \n", "\n", "So, it is quite easy to implement standard operations on relations in the \ binary matrix model. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "As mentioned previously, using binary matrices is really a hack, we should \ be using Boolean matrices. In order to multiply Boolean matrices we then \ have to replace ", StyleBox["Plus", "MR"], " by ", StyleBox["Or", "MR"], ", and ", StyleBox["Times", "MR"], " by ", StyleBox["And", "MR"], ". So, the product ", Cell[BoxData[ \(TraditionalForm\`Z\)]], " of two Boolean matrices ", Cell[BoxData[ \(TraditionalForm\`X\)]], " and ", Cell[BoxData[ \(TraditionalForm\`Y\)]], " is given by \n\n\t", Cell[BoxData[ \(TraditionalForm\`Z\_\(i, j\) = \ \(\(\[Or]\)\(\[VeryThinSpace]\ \ \)\((X\_\(i, l\)\ \[And] \ \ Y\_\(l, j\))\)\)\)]], " \n\nwhere the index in the Or ranges from ", Cell[BoxData[ \(TraditionalForm\`1\)]], " to ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". So, matrix multiplication makes sense not just for integers or real, \ but also for Booleans. The logical structure of the algorithm is the same, \ but the underlying data type changes, and the operations have to be \ interpreted differently. \nNote that this can be done very nicely in C++ by \ using a template function and overloading + and *. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "We can summarize the situation nicely in terms of a diagram:\n\n\t", Cell[BoxData[ FormBox[GridBox[{ {\(Rel\ \[Cross]Rel\), \(\[LongRightArrow]\&\[SmallCircle]\), "Rel"}, { RowBox[{" ", GridBox[{ {GridBox[{ {" ", "\[DownArrow]", GridBox[{ {" "}, {"M"}, {" "} }]} }], ""} }]}], StyleBox[\(1 a11111\), ShowContents->False], GridBox[{ {GridBox[{ {GridBox[{ {" "}, {\(M\^\(-1\)\)}, {" "} }], "\[UpArrow]"} }], " "} }]}, {\(BM\ \[Cross]\ BM\), \(\[LongRightArrow]\&Dot\), "BM"} }], TraditionalForm]]], "\n\t\nHere ", Cell[BoxData[ \(TraditionalForm\`Rel\)]], " stands for the set of all relations on some finite carrier set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " of size ", Cell[BoxData[ \(TraditionalForm\`n\)]], " and ", Cell[BoxData[ \(TraditionalForm\`BM\)]], " stands for the Boolean ", Cell[BoxData[ \(TraditionalForm\`n\ \[Cross]\ n\)]], " matrices. Instead of performing relational composition, we can \ translate the relations \[Rho] and \[Sigma] into the corresponding matrices \ ", Cell[BoxData[ \(TraditionalForm\`M\_\[Rho]\)]], " and ", Cell[BoxData[ \(TraditionalForm\`M\_\[Sigma]\)]], ", multiply the matrices, and translate the result back into a relation. \ The translation process is indicated by the function ", Cell[BoxData[ \(TraditionalForm\`M\ : \ Rel\ \[LongRightArrow]\ BM\)]], ". \nAlternatively, we can think of ", Cell[BoxData[ \(TraditionalForm\`BM\)]], " as binary matrices. Then we still use multiplication, but we have to \ apply the Sign function afterwards to make sure the product matrix is a again \ binary. The translation function is essentially the same as before." }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Transitive Closure", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:47"], Cell["\<\ We still have to deal with an extremely important operation on \ relations: the transitive closure. It is not surprsing that this is the \ hardest task. Fortunately, we already have all the necessary tools in \ place.\ \>", "Text"], Cell[CellGroupData[{ Cell[" A Fixed Point Algorithm", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:48"], Cell[TextData[{ "Specifically, we can get more mileage out of the networks idea from the \ last section. Again assume that \[Rho] is a binary relation on some fixed \ finite set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " of size ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". Recall that the transitive closure of a relation \[Rho] is the least \ relation containing \[Rho] that is also transitive. To compute the \ transitive closure we have to compute the potentially infinite union \n\t", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^+\)\ = \ \ \[Rho]\ \[Union] \ \ \ \[Rho]\^2\ \[Union] \ \ \ \[Rho]\^3\ \[Union] \[Ellipsis]\)]], "\nWe know how to calculate the powers ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^\(\(\ \)\(t\)\)\)]], ", and we can compute unions. Now note that ", Cell[BoxData[ \(TraditionalForm\`a\ \(\[Rho]\^\(\(\ \)\(t\)\(\ \)\)\) b\)]], " holds iff there are elements ", Cell[BoxData[ \(TraditionalForm\`x\_0, x\_1, ... , x\_t\ \[Element] \ A\)]], " such that \n\t", Cell[BoxData[ \(TraditionalForm\`x\_0\ = \ \(a\ \ \ \[And] \ \ x\_t\ = \ b\ \ \[And] \ \ \ \[ForAll] \ \ i\ < \ t\ \((\ \ \ \(x\_\(\(i\)\(\ \ \)\)\) \[Rho]\ \ \ x\_\(i + 1\)\ \ )\)\)\)]], ". \nIn other words, in the ordinary composition ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[SmallCircle]\ \[Rho]\)]], " there is only one witness between ", Cell[BoxData[ \(TraditionalForm\`a\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\)]], ", but for arbitrary powers ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^\(\(\[VeryThinSpace]\ \)\(k\)\)\)]], " there are ", Cell[BoxData[ \(TraditionalForm\`k - 1\)]], " witnesses, a whole chain of them. If we think of \[Rho] as describing \ links in a network, ", Cell[BoxData[ \(TraditionalForm\`a\ \[Rho]\^\(\(\ \)\(t\)\)\ b\)]], " simply means that we have a path from ", Cell[BoxData[ \(TraditionalForm\`a\)]], " to ", Cell[BoxData[ \(TraditionalForm\`b\)]], " of length ", Cell[BoxData[ \(TraditionalForm\`t\)]], ". But since our whole network has only ", Cell[BoxData[ \(TraditionalForm\`n\)]], " nodes, we have:\n\n", StyleBox["Lemma", FontWeight->"Bold"], ": Truncation Lemma\nThere is a path from ", Cell[BoxData[ \(TraditionalForm\`a\)]], " to ", Cell[BoxData[ \(TraditionalForm\`b\)]], " iff there is a path of length at most ", Cell[BoxData[ \(TraditionalForm\`n - 1\)]], ".\nProof.\nSuppose there is a path from ", Cell[BoxData[ \(TraditionalForm\`a\)]], " to ", Cell[BoxData[ \(TraditionalForm\`b\)]], " of length at least ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". Since there are only ", Cell[BoxData[ \(TraditionalForm\`n\)]], " nodes in the network, some node ", Cell[BoxData[ \(TraditionalForm\`c\)]], " must occur twice. But then we can shorten the path by omitting the loop \ that begins and ends at ", Cell[BoxData[ \(TraditionalForm\`c\)]], ". Repeating this process we ultimately obtain a path of length less than \ ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(n\)\)\)]], ". \nThe opposite direction is trivial.\n\[EmptySquare]\nNote that the last \ argument is based on the so-called ", StyleBox["Pigeon Hole Principle", FontColor->RGBColor[0, 0, 1]], ": if you have ", Cell[BoxData[ \(TraditionalForm\`n\)]], " pigeons, and less than ", Cell[BoxData[ \(TraditionalForm\`n\)]], " pigeon holes, than at least one hole is occupied by at least 2 pigeons." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Now we have an algorithm to compute the transitive closure.\n\n", StyleBox["Theorem: ", FontWeight->"Bold"], " Let \[Rho] be a binary relation on a finite set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " of size ", Cell[BoxData[ \(TraditionalForm\`n\)]], " and define \n\t", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\ = \[Rho]\ \[Union] \ \ \[Rho]\^2\ \ \[Union] \ \ \[Ellipsis]\ \[Union] \ \ \[Rho]\^\(n - 1\)\)]], ".\nThen ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], " is the transitive closure of \[Rho].\nProof.\nThe fact that \[Sigma] is \ transitive follows easily from the truncation lemma. \nIt remains to show \ that ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], " is the smallest transitive relation containg \[Rho]. One way of tackling \ this problem is to consider an arbitrary transitive relation ", Cell[BoxData[ \(TraditionalForm\`\[Tau]\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ \[SubsetEqual] \ \[Tau]\)]], ", and to show that ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\ \[SubsetEqual] \ \[Tau]\)]], ". That turns out to be easy: we show by induction on ", Cell[BoxData[ \(TraditionalForm\`k\)]], " that ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^k\ \[SubsetEqual] \ \[Tau]\)]], ". \nThe base case is ", Cell[BoxData[ \(TraditionalForm\`k = 1\)]], ", and there is nothing to show since we assume that ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^1 = \ \[Rho]\ \[SubsetEqual] \ \[Tau]\)]], ". For the induction step, suppose we already have ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^k\ \[SubsetEqual] \ \[Tau]\)]], " and assume ", Cell[BoxData[ \(TraditionalForm\`a\ \(\[Rho]\^\(k + 1\)\) b\)]], ". By defintion of composition, this means ", Cell[BoxData[ \(TraditionalForm\`a\ \(\[Rho]\^k\) x\ \ \[And] \ x\ \[Rho]\ b\)]], " for some witness ", Cell[BoxData[ \(TraditionalForm\`x\)]], ". But both ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^k\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\)]], " are contained in \[Tau], so we have ", Cell[BoxData[ \(TraditionalForm\`a\ \[Tau]\ x\ \ \[And] \ x\ \[Tau]\ b\)]], ". Since ", Cell[BoxData[ \(TraditionalForm\`\[Tau]\)]], " is transitive it follows that ", Cell[BoxData[ \(TraditionalForm\`a\ \[Tau]\ b\)]], ", so that ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^\(k + 1\)\ \[SubsetEqual] \ \[Tau]\)]], ".\n\[EmptySquare]\n\nHence, we have an algorithm to compute the transitive \ closure ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^+\)\)]], " of a binary relation \[Rho] on a carrier set of size ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". ", Cell[BoxData[ \(TraditionalForm\`R\)]], ", ", Cell[BoxData[ \(TraditionalForm\`S\)]], ", and ", Cell[BoxData[ \(TraditionalForm\`T\)]], " below are all ", Cell[BoxData[ \(TraditionalForm\`n\ \[Cross]\ n\)]], " Boolean matrices, and ", Cell[BoxData[ \(TraditionalForm\`R\)]], " is the Boolean matrix representing relation \[Rho]." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Algorithm Transitive Closure \tT = S = R; \tfor i = 1,..,n-2 do \t\tT = T.R; \t\tS = S + T; \treturn S;\ \>", "Program"], Cell[TextData[{ "How about computing the reflexive transitive closure? We could simply \ compute ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^+\)\)]], " and then add the identity relation in the end to obtain ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\^*\)\)]], ". Alternatively, we can replace \[Rho] by ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\ = \ Id\_A\ \[Union] \ \[Rho]\)]], " and compute ", Cell[BoxData[ \(TraditionalForm\`\(\[Sigma]\^+\) = \ \(\[Rho]\^*\)\)]], ".\n\nHere is our standard example, the successor relation." }], "Text"], Cell[BoxData[{ \(\(R = RelationToMatrix[5, #2 == #1 + 1 &];\)\), "\n", \(MatrixForm[R]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(\(Unprotect[T];\)\), "\n", \(\(S = \(T = R\);\)\), "\n", \(\(Do[T = BooleanComposition[T, R]; S = BooleanUnion[S, T], {3}];\)\), "\n", \(MatrixForm[S]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "The less-than relation, as expected. \nWhat kind of efficiency can we \ expect from this method? It is not hard to see that a single matrix \ multiplication can be handled in ", Cell[BoxData[ \(TraditionalForm\`O(n\^3)\)]], " steps, and since we have to perform ", Cell[BoxData[ \(TraditionalForm\`n - 2\)]], " such multiplications, the whole computation will take no more than ", Cell[BoxData[ \(TraditionalForm\`O(n\^4)\)]], " steps. This is fine for small carrier sets but hopeless for large ones. \ In the next section we will show how to reduce the running time to ", Cell[BoxData[ \(TraditionalForm\`O(n\^3)\)]], " steps using a slightly different approach.\n" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "There is a slight improvement we can make to this algorithm: it is not \ always necessary to compute all the powers up to ", Cell[BoxData[ \(TraditionalForm\`R\^\(\(\ \)\(n - 1\)\)\)]], ". For example, if the relation is already transitive after ", Cell[BoxData[ \(TraditionalForm\`i\)]], " steps we have ", Cell[BoxData[ \(TraditionalForm\`R\^\(\(\ \)\(i\)\)\ = \ \(R\^\(\(\ \)\(i + 1\)\) = \ \ \(R\^\(\(\ \)\(i + 2\)\) = \[Ellipsis]\)\)\)]], " , so we should stop immediately after computing ", Cell[BoxData[ \(TraditionalForm\`R\^\(\(\ \)\(i + 1\)\)\)]], " and finding out that it has not changed from ", Cell[BoxData[ \(TraditionalForm\`\(\(R\)\(\ \)\)\^i\)]], ". \nIn terms of the network, it may well happen that if there is a path \ from ", Cell[BoxData[ \(TraditionalForm\`a\)]], " to ", Cell[BoxData[ \(TraditionalForm\`b\)]], " at all, there is one of length much less than ", Cell[BoxData[ \(TraditionalForm\`n - 1\)]], ". In fact, for communication networks it is extremely important to design \ them in such a way that the longest path from one node to another (the \ so-called ", StyleBox["diameter", FontColor->RGBColor[0, 0, 1]], " of the network) is much smaller than ", Cell[BoxData[ \(TraditionalForm\`n\)]], ", say, something like ", Cell[BoxData[ \(TraditionalForm\`O(log\ n)\)]], ". \nActually, we can do slightly better than this. Since we have to add up \ all the powers of ", Cell[BoxData[ \(TraditionalForm\`R\)]], " in the end, we can repeatedly apply the function ", Cell[BoxData[ \(TraditionalForm\`f(X)\ = \ X\ + \ X\^\(\(\ \)\(2\)\)\)]], " until nothing changes any more. The ", Cell[BoxData[ \(TraditionalForm\`X\)]], " here really is a matrix, initially ", Cell[BoxData[ \(TraditionalForm\`R\)]], ", but we can see the intermediate results just as well if we look at \ ordinary numbers instead. Note that we have to use ", StyleBox["Expand", "MR"], ", otherwise ", StyleBox["Mathematica", FontSlant->"Italic"], " will leave the terms unevaluated." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(Clear[f];\)\), "\n", \(\(f[x_] := Expand[x + x\^2];\)\), "\n", \(TableForm[NestList[f, x, 4]]\)}], "Input"], Cell[TextData[{ "The integer coefficients tell us exactly how many times a term ", Cell[BoxData[ \(TraditionalForm\`x\^\(\(\ \)\(i\)\)\)]], " appeared, for our Boolean matrices they would disappear and we simply \ get the desired sum of powers of ", Cell[BoxData[ \(TraditionalForm\`X\)]], ". Note that we are getting large powers very quickly, we only have to \ apply ", Cell[BoxData[ \(TraditionalForm\`f\)]], " about ", Cell[BoxData[ \(TraditionalForm\`log\ n\)]], " times to get all the needed powers." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "We can implement this easily in Mathematica by using the ", ButtonBox["FixedPoint", ButtonStyle->"RefGuideLink"], " operator. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["TransitiveClosure[R_?MatrixQ]:= FixedPoint[Sign[#+#.#]&,R];", "Program", AspectRatioFixed->True], Cell[TextData[{ "This function is actully defined in dimath.m. It accepts the option ", StyleBox["Reflexive->True", "MR"], ". Here is the machinery applied to the successor relation from above. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(R = RelationToMatrix[5, #2 \[Equal] #1 + 1 &];\)\), "\n", \(\(gr1 = PlotMatrix[R, GridLines \[Rule] True, DisplayFunction \[Rule] Identity];\)\), "\n", \(\(gr2 = PlotMatrix[TransitiveClosure[R], GridLines \[Rule] True, DisplayFunction \[Rule] Identity];\)\), "\n", \(\(gr3 = PlotMatrix[TransitiveClosure[R, Reflexive \[Rule] True], GridLines \[Rule] True, DisplayFunction \[Rule] Identity];\)\), "\n", \(\(ShowArray[{gr1, gr2, gr3}, 3];\)\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "More interesting is the following relation on positive integers: ", StyleBox["close[a,b]", "MR", FontWeight->"Bold"], " holds iff the prime factorization of ", Cell[BoxData[ \(TraditionalForm\`a\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\)]], " agree, except in one factor, where the exponent for ", Cell[BoxData[ \(TraditionalForm\`b\)]], " is one higher than the exponent for ", Cell[BoxData[ \(TraditionalForm\`a\)]], ". \nFor God's sake, don't compute factorizations to test this relation!" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(close[a_Integer, b_Integer] := Mod[b, a] \[Equal] 0 && PrimeQ[b/a];\)\)], "Input", AspectRatioFixed->True], Cell["\<\ We only plot the upper half of the matrix, since the lower half is \ boring (why?).\ \>", "Text"], Cell[BoxData[{ \(\(R = RelationToMatrix[100, close];\)\), "\n", \(\(PlotMatrix[\ Take[R, 50]\ ];\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotMatrix[\ Take[TransitiveClosure[R], 50]];\)\)], "Input", AspectRatioFixed->True], Cell["Here is the old gcd-equal-one picture again. ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(R = RelationToMatrix[100, GCD[#1, #2] == 1 &];\)\), "\n", \(\(PlotMatrix[R, GridLines \[Rule] False];\)\)}], "Input", AspectRatioFixed->True], Cell["Quick, what will the next picture look like? ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotMatrix[TransitiveClosure[R], GridLines \[Rule] False];\)\)], "Input", AspectRatioFixed->True], Cell["In fact, we don't need to go very far in this case:", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotMatrix[Sign[MatrixPower[R, 2]]\ ];\)\)], "Input", AspectRatioFixed->True], Cell["Why?", "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" A Dynamic Programming Algorithm", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:49"], Cell[TextData[{ "Yet another, rather efficient algorithm for the calculation of the \ transitive closure can be obtained from the network interpretation. As we \ have seen, we need to determine whether there is a path in the network from \ node ", Cell[BoxData[ \(TraditionalForm\`a\)]], " to node ", Cell[BoxData[ \(TraditionalForm\`b\)]], ", for all pairs of nodes ", Cell[BoxData[ \(TraditionalForm\`a, \ b\)]], ". The fixed point algorithm in the last section was based on building \ paths of increasing length. \nHere is a different way to construct the paths \ in a systematic way. To simplify notation, we use ", Cell[BoxData[ \(TraditionalForm\`\([n]\)\)]], " as node set. Define sets of paths as follows:\n\n\t", Cell[BoxData[ \(TraditionalForm\`\(P\_k\)(a, b)\ := \ {\ \ p\ \ | \ \ p\ \ path\ from\ a\ to\ b, \ all\ intermediate\ nodes\ \[LessEqual] \ k, \ no\ repetitions\ }\)]], "\n\t\nwhere ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ k\ \[LessEqual] \ n\)]], " and ", Cell[BoxData[ \(TraditionalForm\`1\ \[LessEqual] \ a, b \[LessEqual] \ n\)]], ". Thus, there is no restriction on the first and last node, and no direct \ restriction on the length, but all the nodes in between are bounded by ", Cell[BoxData[ \(TraditionalForm\`k\)]], " and we are not allowed to come back to the same intermediate node (note \ that this restriction is not a problem if we are only interested in path \ existence: if there is a path from ", Cell[BoxData[ \(TraditionalForm\`a\)]], " to ", Cell[BoxData[ \(TraditionalForm\`b\)]], " at all, then there already is a path without repetions). The constraint \ ", Cell[BoxData[ \(TraditionalForm\`k = 0\)]], " really means that there are no intermediate nodes at all. Hence we have\n\ \n\t\[Bullet] ", Cell[BoxData[ \(TraditionalForm\`\(P\_0\)(a, b)\ = \ {\ \((a, b)\)\ }\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\[Rho](a, b)\)]], ", where ", Cell[BoxData[ \(TraditionalForm\`a \[NotEqual] \ b\)]], ",\n\t ", Cell[BoxData[ \(TraditionalForm\`\(P\_0\)(a, a)\ = \ {\ \((a)\)\ }\)]], " iff ", Cell[BoxData[ FormBox[ RowBox[{" ", FormBox[\(\[Rho](a, a)\), "TraditionalForm"]}], TraditionalForm]]], ", \n\t ", Cell[BoxData[ \(TraditionalForm\`\(P\_0\)(a, b)\ = \ \[EmptySet]\)]], " otherwise.\n\t\[Bullet] ", Cell[BoxData[ \(TraditionalForm\`\(\(\(\(P\_n\)(a, b)\)\(\ \)\(=\)\)\(\ \)\)\)]], " all repetition-free paths from ", Cell[BoxData[ \(TraditionalForm\`a\)]], " to ", Cell[BoxData[ \(TraditionalForm\`b\)]], ".\n\nSo, ", Cell[BoxData[ \(TraditionalForm\`P\_0\)]], " is just a translation of \[Rho], and ", Cell[BoxData[ \(TraditionalForm\`P\_n\)]], " is what we really want to compute. All that is missing is a way to get \ from ", Cell[BoxData[ \(TraditionalForm\`P\_k\)]], " to ", Cell[BoxData[ \(TraditionalForm\`P\_\(k + 1\)\)]], ". To this end, let us write ", Cell[BoxData[ \(TraditionalForm\`p\ \[CircleTimes]\ q\)]], " for the composition of two paths ", Cell[BoxData[ \(TraditionalForm\`p\)]], " and ", Cell[BoxData[ \(TraditionalForm\`q\)]], ". Of course, this is only allowed if the last node on ", Cell[BoxData[ \(TraditionalForm\`p\)]], " is the first node on ", Cell[BoxData[ \(TraditionalForm\`q\)]], ", and if the combined path still contains no repetitions. So, we have a \ partial operation here. We are only interested in sets of paths, and for \ those the operation is total:\n\n\t", Cell[BoxData[ \(TraditionalForm\`P\ \[CircleTimes]\ Q\ = \ {\ p\ \[CircleTimes]\ q\ | \ p\ \[Element] \ P, \ q\ \[Element] \ Q, \ last(p)\ = \ first(q), \ no\ repetitions\ }\)]], ".\n\nUsing this composition operation on paths we can describe ", Cell[BoxData[ \(TraditionalForm\`P\_\(k + 1\)\)]], " in terms of ", Cell[BoxData[ \(TraditionalForm\`P\_k\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Lemma", FontWeight->"Bold"], ": ", Cell[BoxData[ \(TraditionalForm\`\(P\_\(k + 1\)\)(a, b)\ = \ \(P\_k\)(a, b)\ \[Union] \ \(\(P\_k\)(a, k + 1)\)\ \ \[CircleTimes]\ \(\(P\_k\)(k + 1, b)\)\)]], ". \n\nProof. \nConsider a path ", Cell[BoxData[ \(TraditionalForm\`p\)]], " from ", Cell[BoxData[ \(TraditionalForm\`a\)]], " to ", Cell[BoxData[ \(TraditionalForm\`b\)]], " that uses only intermediate nodes ", Cell[BoxData[ \(TraditionalForm\`\(\(\[LessEqual]\)\(\ \)\(k + 1\)\)\)]], ". \nCase 1: All intermediate nodes are ", Cell[BoxData[ \(TraditionalForm\`\(\(\[LessEqual]\)\(\ \)\(k\)\)\)]], ". \nIn this case we have ", Cell[BoxData[ \(TraditionalForm\`p\ \[Element] \ \(P\_k\)(a, b)\)]], ", so ", Cell[BoxData[ \(TraditionalForm\`p\)]], " is on the right hand side. \nCase 2: ", Cell[BoxData[ \(TraditionalForm\`p\)]], " actually uses node ", Cell[BoxData[ \(TraditionalForm\`k + 1\)]], ". \nThen we can split ", Cell[BoxData[ \(TraditionalForm\`p\)]], " into 2 pieces: a path ", Cell[BoxData[ \(TraditionalForm\`p\_1\)]], " from ", Cell[BoxData[ \(TraditionalForm\`a\)]], " to ", Cell[BoxData[ \(TraditionalForm\`k + 1\)]], ", and a path ", Cell[BoxData[ \(TraditionalForm\`p\_2\)]], " from ", Cell[BoxData[ \(TraditionalForm\`k + 1\)]], " to ", Cell[BoxData[ \(TraditionalForm\`b\)]], ". Since ", Cell[BoxData[ \(TraditionalForm\`p\)]], " has no repetitions, ", Cell[BoxData[ \(TraditionalForm\`p\_1\)]], " and ", Cell[BoxData[ \(TraditionalForm\`p\_2\)]], " also have no repetitions. But then ", Cell[BoxData[ \(TraditionalForm\`p\ = \ p\_1\ \[CircleTimes]\ p\_2\)]], " also occurs on the right hand side.\nThe opposite direction is obvious.\n\ \[EmptySquare]" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "\nThe lemma together with the preceding observation yields an ", Cell[BoxData[ \(TraditionalForm\`\[CapitalTheta](n\^3)\)]], " algorithm to compute transitive closures: we can represent ", Cell[BoxData[ \(TraditionalForm\`P\_k\)]], " by an ", Cell[BoxData[ \(TraditionalForm\`n\ \[Cross]\ n\)]], " Boolean matrix where\n\t", Cell[BoxData[ \(TraditionalForm\`\(P\_k\)(a, b)\ = 1\)]], " iff there is a suitable path from ", Cell[BoxData[ \(TraditionalForm\`a\)]], " to ", Cell[BoxData[ \(TraditionalForm\`b\)]], ". \nThe first matrix ", Cell[BoxData[ \(TraditionalForm\`P\_0\)]], " is just the Boolean matrix for \[Rho]. This algorithm is usually \ referred to as ", StyleBox["Warshall's algorithm", FontColor->RGBColor[0, 0, 1]], ".\nHere is the successor example from the last section again. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(R = RelationToMatrix[5, #2 == #1 + 1 &];\)\), "\n", \(MatrixForm[R]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(Warshall[R]\ // MatrixForm\)], "Input"], Cell["\<\ It is a good exercise to write out a program for Warshall's \ algorithm. We will refrain from doing this here since Mathematica is not a \ good environment for low-level loop programming. In C/C++ the implementation \ is quite straightforward.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Comment", FontWeight->"Bold"], ":\nThe condition of having no repetitions on the paths can be deleted, and \ one obtains a similar result:\n \t", Cell[BoxData[ \(TraditionalForm\`\(P\_\(k + 1\)\)(a, b)\ = \ \(P\_k\)(a, b)\ \[Union] \ \(\(P\_k\)(a, k + 1)\)\ \ \ \[CircleTimes]\ \(\(\(P\_k\)(k + 1, k + 1)\)\^*\)\ \[CircleTimes]\ \(\(P\_k\)(k + 1, b)\)\)]], ". \nThe star here indicates that we can take any number of paths from ", Cell[BoxData[ \(TraditionalForm\`k + 1\)]], " back to ", Cell[BoxData[ \(TraditionalForm\`k + 1\)]], ", and combine them with an initial segment from ", Cell[BoxData[ \(TraditionalForm\`a\)]], " to ", Cell[BoxData[ \(TraditionalForm\`k + 1\)]], ", and a final segment from ", Cell[BoxData[ \(TraditionalForm\`k + 1\)]], " to ", Cell[BoxData[ \(TraditionalForm\`b\)]], ". The big difference is that we now are dealing with possibly infinitely \ many paths: whenever there is a loop in our network there are infinitely many \ paths from any point on the loop back to itself, even if the network itself \ is finite. To deal with infinitely many paths one needs more complicated \ machinery, so we will not pursue the issue here. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[" A Scheduling Example", "Subsubsection", CellTags->"c:50"], Cell[TextData[{ "Let us return to the problem of scheduling a sequence of tasks. Below is a \ dependency list for task ", Cell[BoxData[ FormBox[ RowBox[{ FormBox[\(T\_1\), "TraditionalForm"], ",", "...", \(\(,\)\(T\_30\)\)}], TraditionalForm]]], ". Is there a way we can schedule these task without any deadlocks? \nAll \ we need to do is think of the table as describing a binary relation \[Rho] \ on ", Cell[BoxData[ \(TraditionalForm\`\([30]\)\)]], ", and test whether the transitive closure is irreflexive. " }], "Text"], Cell[BoxData[ \(\(dep\ = \ {{18, 7}, {18, 3}, {18, 1}, {18, 30}, {25, 7}, {25, 11}, {25, 22}, {25, 27}, {7, 8}, {7, 20}, {7, 9}, {29, 3}, {29, 11}, {29, 14}, {29, 4}, {3, 8}, {3, 23}, {3, 21}, {11, 8}, {11, 28}, {11, 15}, {8, 26}, {8, 16}, {17, 1}, {17, 22}, {17, 14}, {17, 12}, {1, 20}, {1, 23}, {1, 24}, {22, 20}, {22, 28}, {22, 13}, {20, 26}, {20, 10}, {14, 23}, {14, 28}, {14, 5}, {23, 26}, {23, 2}, {28, 26}, {28, 6}, {19, 30}, {19, 27}, {19, 4}, {19, 12}, {30, 9}, {30, 21}, {30, 24}, {27, 9}, {27, 15}, {27, 13}, {9, 16}, {9, 10}, {4, 21}, {4, 15}, {4, 5}, {21, 16}, {21, 2}, {15, 16}, {15, 6}, {12, 24}, {12, 13}, {12, 5}, {24, 10}, {24, 2}, {13, 10}, {13, 6}, {5, 2}, {5, 6}};\)\)], "Input"], Cell[TextData[{ "To this end we first convert the list into a ", Cell[BoxData[ \(TraditionalForm\`30\ \[Cross]\ 30\)]], " Boolean matrix. We will use a little helper function to make the process \ more obvious." }], "Text"], Cell[BoxData[{ \(\(turnonbit[{x_, y_}] := \(R\[LeftDoubleBracket]x, y\[RightDoubleBracket] = 1\);\)\), "\n", \(\(R = Table[0, {30}, {30}];\)\), "\n", \(Scan[turnonbit, dep]\)}], "Input"], Cell[TextData[{ "Note that we are using ", StyleBox["Scan", "MR"], " rather than ", StyleBox["Map", "MR"], ", since the output is irrelevant (we are only interested in a side effect: \ some bits in R are turned on)." }], "Text"], Cell[BoxData[ \(\(PlotMatrix[R];\)\)], "Input"], Cell["\<\ Let's compute the closure twice, once with the fixed point method, \ and once with Warshall's algorithm.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(R1 = TransitiveClosure[R];\)\), "\n", \(\(R2 = Warshall[R];\)\), "\n", \(R1 \[Equal] R2\)}], "Input"], Cell[TextData[{ "For this example, the direct implementation of Warshall's algorithm is \ inferior because of the explicit loops. This is true in general, ", StyleBox["TransitiveClosure", "MR"], " is faster than ", StyleBox["Warshall", "MR"], ". For larger matrices or less sparse matrices (more 1's) the difference \ can be quite enormous. Moral: in a high level environment like ", StyleBox["Mathematica", FontSlant->"Italic"], " ordinary complexity results have to be taken with a grain of salt. \nIs \ the closure irreflexive?" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotMatrix[R1];\)\)], "Input"], Cell["\<\ Hard to say, we better extract the diagonal. Here is a bizarre way \ of extracting the diagonal from a matrix. Don't ask, it's one of these \ mysteries.\ \>", "Text"], Cell[BoxData[ \(Transpose[R1, {1, 1}]\)], "Input"], Cell["\<\ Thus, we can schedule all the tasks. However, this method does not \ tell us how to do that.\ \>", "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Equivalential Closure", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:51"], Cell[TextData[{ "Suppose you have a relation \[Rho] (which is not required to have any \ special properties), and we would like compute the least equivalence relation \ that contains \[Rho], the so-called equivalential closure of \[Rho], often \ written ", Cell[BoxData[ \(TraditionalForm\`eqc(\[Rho])\)]], ". We could do this by using the tools we already have in place:\n\t", Cell[BoxData[ \(TraditionalForm\`eqc(\[Rho])\ = \ \(trc(sc(\[Rho]))\ = \ tc(\ \[Rho]\ \[Union] \ \[Rho]\^\(\(\ \)\(r\)\) \[Union] \ I)\)\)]], ". \nHowever, there is a much more efficient way to compute equivalential \ closures based on fixed points. " }], "Text"], Cell[CellGroupData[{ Cell[" Union Find", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:52"], Cell[TextData[{ "We can think of the equivalence relation ", Cell[BoxData[ \(TraditionalForm\`eqc(\[Rho])\)]], " as a partition: the carrier set is chopped up into blocks, where each \ block is one equivalence class. To construct the partition representing ", Cell[BoxData[ \(TraditionalForm\`eqc(\[Rho])\)]], ", we begin all blocks being trivial (of size one). We then read the pairs \ ", Cell[BoxData[ \(TraditionalForm\`\((x, y)\)\)]], " in \[Rho] one after the other, and whenever ", Cell[BoxData[ \(TraditionalForm\`x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\)]], " fail to be in the same block, we merge the two blocks. \n\nTo make this \ approach computationally interesting, we need to be able to perform the \ following two operations quickly:\n\[SmallCircle] determine which block ", Cell[BoxData[ \(TraditionalForm\`x\)]], " belongs to, and \n\[SmallCircle] merge two blocks. \nUsing standard data \ structures such as lists is problematic here. But, we can think of each \ block as a tree (directed towards the root). Starting anywhere at node ", Cell[BoxData[ \(TraditionalForm\`x\)]], " in the tree we can traverse to the root ", Cell[BoxData[ \(TraditionalForm\`root(x)\)]], ", and thus have a test for block membership: ", Cell[BoxData[ \(TraditionalForm\`x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\)]], " are in the same block if, and only if, ", Cell[BoxData[ \(TraditionalForm\`root(x) = root(y)\)]], ". If we wish to merge the two blocks, we can simply attach one root as a \ child to the other. \n\nThe efficiency of this schema depends on the depth of \ the trees, but as it turns out one can use simple tricks (weighted union and \ path-compression) to keep them so shallow that the whole algorithm is \ essentially linear. We won't get involved with these speed-up operations \ here, and focus on basic idea. \n\nThe trees can be represented by a function \ ", Cell[BoxData[ \(TraditionalForm\`f\ : \ A\ \[Rule] \ A\)]], " which indicates parents. The root is its own parent, and thus a fixed \ point of ", Cell[BoxData[ \(TraditionalForm\`f\)]], ". Here is the whole code:" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[root, equiv, merge]\), "\[IndentingNewLine]", \(\(A\ = \ Range[20];\)\), "\[IndentingNewLine]", \(\(AssignFunction[\ ff, \ A, \ A\ ];\)\), "\[IndentingNewLine]", \(\(root[x_]\ := \ FixedPoint[ff, x];\)\), "\[IndentingNewLine]", \(\(equiv[x_, y_]\ := \ root[x]\ \[Equal] \ root[y];\)\), "\[IndentingNewLine]", \(\(merge[r1_, r2_]\ := \ \(ff[r1]\ = \ r2\);\)\)}], "Input", AspectRatioFixed->True], Cell["\<\ Now we identify some elements as equivalent and refine the \ partitions accordingly. \ \>", "Text"], Cell["\<\ refine[{x_,y_}] := \tWith[ {rx = root[x],ry = root[y]}, \t\t\tIf[ rx =!= ry, merge[rx, ry] ] ];\ \>", "Input"], Cell["\<\ We do this in two stages, just so that the intermidiate result \ becomes visible. \ \>", "Text"], Cell["\<\ R1 = Table[{i,i+2},{i,1,9,2}] R2 = Table[{i,i+2},{i,10,18,2}]\ \>", "Input", AspectRatioFixed->True], Cell["Scan[ refine, R1 ]", "Input"], Cell["\<\ Iterating the predecessor function makes the trees fairly visible. \ \ \>", "Text"], Cell["PlotFunction[ ff, A ];", "Input"], Cell["Here is the classical Boolean matrix plot. ", "Text"], Cell["RelationToMatrix[ A, equiv ] // PlotMatrix;", "Input"], Cell["And now for the second half. ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["Scan[ refine, R2 ]", "Input"], Cell["PlotFunction[ ff, A ];", "Input"], Cell["RelationToMatrix[ A, equiv ] // PlotMatrix;", "Input"], Cell[BoxData[{ \(ToClasses[A, equiv]\), "\n", \(\(AA = Flatten[%];\)\), "\n", \(\(PlotMatrix[RelationToMatrix[AA, equiv]];\)\)}], "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Summary", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:27"], Cell["Here is all the new terminology summarized. ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Empty, identity, universal relation. Union, intersection, complement. Converse. Composition, powers. Reflexivity, irreflexivity. Symmetry, anti-symmetry. Transitivity. Closures. Orders, partial, total. Well-orders, induction on well-orders. Equivalence relations. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "We can think of a binary relation \[Rho] on a finite set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " as a ", StyleBox["Boolean ", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`n\ \[Cross]\ n\)]], StyleBox[" matrix", FontColor->RGBColor[0, 0, 1]], ", where ", Cell[BoxData[ \(TraditionalForm\`n\)]], " is the size of ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". The Boolean matrix can also be interpreted as a ", StyleBox["binary matrix", FontColor->RGBColor[0, 0, 1]], " (just as one uses 0 for False and 1 for True in C++). \nOne can think of \ the binary (or Boolean) matrix as describing a ", StyleBox["network", FontColor->RGBColor[0, 0, 1]], " (in graph theory, this matrix is called the adjcaceny matrix of the \ network). \nUsing ", StyleBox["matrix multiplication", FontColor->RGBColor[0, 0, 1]], ", one can calculate the number of paths between nodes in the network. \n\ Scaling things back to 0/1, matrix multiplication solves the problem of \ computing ", StyleBox["relational composition", FontColor->RGBColor[0, 0, 1]], ". \nUsing repeated matrix multiplication, we can determine the ", StyleBox["transitive closure", FontColor->RGBColor[0, 0, 1]], " of a relation. \n", StyleBox["Equivalential closure", FontColor->RGBColor[0, 0, 1]], " can be computed via transitive closure, or via Union/Find. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]] }, Closed]] }, Closed]] }, FrontEndVersion->"5.0 for X", ScreenRectangle->{{0, 1280}, {0, 1024}}, AutoGeneratedPackage->None, WindowToolbars->{}, CellGrouping->Automatic, WindowSize->{1016, 998}, WindowMargins->{{0, Automatic}, {Automatic, 0}}, PrintingStartingPageNumber->438, PrintingPageRange->{Automatic, Automatic}, PrintingOptions->{"PaperSize"->{612, 792}, "PaperOrientation"->"Portrait", "Magnification"->1}, PrivateNotebookOptions->{"ColorPalette"->{RGBColor, 128}}, ShowSelection->True, ShowCellLabel->True, ShowCellTags->False, ImageSize->{200, 200}, RenderingOptions->{"ObjectDithering"->True, "RasterDithering"->False}, CharacterEncoding->Automatic, Magnification->1.5, StyleDefinitions -> "Classic.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[1819, 55, 93, 3, 110, "Title", Evaluatable->False, CellTags->"c:1"]}, "c:2"->{ Cell[1937, 62, 95, 3, 88, "Section", Evaluatable->False, CellTags->"c:2"]}, "c:3"->{ Cell[2057, 69, 100, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:3"]}, "c:4"->{ Cell[3027, 98, 104, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:4"]}, "c:5"->{ Cell[6860, 221, 122, 5, 42, "Subsubsection", CellTags->"c:5"]}, "c:6"->{ Cell[9344, 301, 64, 1, 42, "Subsection", CellTags->"c:6"]}, "c:7"->{ Cell[9953, 317, 123, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:7"]}, "c:8"->{ Cell[10883, 348, 121, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:8"]}, "c:9"->{ Cell[15460, 491, 108, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:9"]}, "c:10"->{ Cell[20081, 642, 114, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:10"]}, "c:11"->{ Cell[20686, 662, 131, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:11"]}, "c:12"->{ Cell[22099, 709, 111, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:12"]}, "c:13"->{ Cell[27177, 883, 110, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:13"]}, "c:14"->{ Cell[29404, 961, 117, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:14"]}, "c:15"->{ Cell[38506, 1254, 118, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:15"]}, "c:16"->{ Cell[41646, 1359, 114, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:16"]}, "c:17"->{ Cell[42033, 1374, 104, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:17"]}, "c:18"->{ Cell[45675, 1484, 119, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:18"]}, "c:19"->{ Cell[48418, 1578, 105, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:19"]}, "c:20"->{ Cell[50917, 1664, 99, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:20"]}, "c:21"->{ Cell[54079, 1758, 114, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:21"]}, "c:22"->{ Cell[61955, 1995, 109, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:22"]}, "c:23"->{ Cell[67400, 2180, 105, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:23"]}, "c:24"->{ Cell[70239, 2267, 119, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:24"]}, "c:25"->{ Cell[75563, 2433, 132, 6, 63, "Subsubsection", Evaluatable->False, CellTags->"c:25"]}, "c:26"->{ Cell[81996, 2626, 125, 6, 63, "Subsubsection", Evaluatable->False, CellTags->"c:26"]}, "c:29"->{ Cell[90838, 2888, 110, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:29"]}, "c:31"->{ Cell[96501, 3070, 117, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:31"]}, "c:32"->{ Cell[97677, 3111, 52, 1, 28, "Subsubsection", CellTags->"c:32"]}, "Rotations"->{ Cell[103599, 3294, 69, 1, 42, "Subsubsection", CellTags->{"Rotations", "c:33"}]}, "c:33"->{ Cell[103599, 3294, 69, 1, 42, "Subsubsection", CellTags->{"Rotations", "c:33"}]}, "c:34"->{ Cell[107444, 3425, 53, 1, 42, "Subsubsection", CellTags->"c:34"]}, "c:35"->{ Cell[109072, 3475, 58, 1, 42, "Subsubsection", CellTags->"c:35"]}, "c:36"->{ Cell[112001, 3586, 120, 3, 47, "Section", Evaluatable->False, CellTags->"c:36"]}, "c:37"->{ Cell[112146, 3593, 115, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:37"]}, "c:38"->{ Cell[116031, 3691, 105, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:38"]}, "c:39"->{ Cell[116161, 3698, 101, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:39"]}, "c:40"->{ Cell[119696, 3820, 103, 3, 28, "Subsubsection", Evaluatable->False, CellTags->"c:40"]}, "c:41"->{ Cell[120934, 3865, 120, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:41"]}, "c:42"->{ Cell[121079, 3872, 104, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:42"]}, "c:43"->{ Cell[125793, 4022, 128, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:43"]}, "c:44"->{ Cell[130935, 4201, 115, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:44"]}, "c:45"->{ Cell[135947, 4379, 112, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:45"]}, "c:46"->{ Cell[146303, 4706, 68, 1, 42, "Subsubsection", CellTags->"c:46"]}, "c:47"->{ Cell[152031, 4878, 109, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:47"]}, "c:48"->{ Cell[152409, 4892, 118, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:48"]}, "c:49"->{ Cell[167655, 5366, 126, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:49"]}, "c:50"->{ Cell[176903, 5657, 67, 1, 42, "Subsubsection", CellTags->"c:50"]}, "c:51"->{ Cell[180548, 5766, 112, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:51"]}, "c:52"->{ Cell[181381, 5789, 105, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:52"]}, "c:27"->{ Cell[185478, 5916, 98, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:27"]} } *) (*CellTagsIndex CellTagsIndex->{ {"c:1", 188702, 6022}, {"c:2", 188804, 6026}, {"c:3", 188907, 6030}, {"c:4", 189014, 6034}, {"c:5", 189121, 6038}, {"c:6", 189206, 6041}, {"c:7", 189287, 6044}, {"c:8", 189398, 6048}, {"c:9", 189510, 6052}, {"c:10", 189623, 6056}, {"c:11", 189734, 6060}, {"c:12", 189848, 6064}, {"c:13", 189962, 6068}, {"c:14", 190076, 6072}, {"c:15", 190190, 6076}, {"c:16", 190305, 6080}, {"c:17", 190417, 6084}, {"c:18", 190532, 6088}, {"c:19", 190647, 6092}, {"c:20", 190762, 6096}, {"c:21", 190876, 6100}, {"c:22", 190991, 6104}, {"c:23", 191106, 6108}, {"c:24", 191221, 6112}, {"c:25", 191333, 6116}, {"c:26", 191448, 6120}, {"c:29", 191563, 6124}, {"c:31", 191675, 6128}, {"c:32", 191787, 6132}, {"Rotations", 191880, 6135}, {"c:33", 191984, 6138}, {"c:34", 192088, 6141}, {"c:35", 192177, 6144}, {"c:36", 192266, 6147}, {"c:37", 192376, 6151}, {"c:38", 192489, 6155}, {"c:39", 192602, 6159}, {"c:40", 192718, 6163}, {"c:41", 192834, 6167}, {"c:42", 192947, 6171}, {"c:43", 193063, 6175}, {"c:44", 193179, 6179}, {"c:45", 193295, 6183}, {"c:46", 193411, 6187}, {"c:47", 193500, 6190}, {"c:48", 193613, 6194}, {"c:49", 193729, 6198}, {"c:50", 193845, 6202}, {"c:51", 193934, 6205}, {"c:52", 194047, 6209}, {"c:27", 194163, 6213} } *) (*NotebookFileOutline Notebook[{ Cell[1754, 51, 40, 0, 32, "MR"], Cell[CellGroupData[{ Cell[1819, 55, 93, 3, 110, "Title", Evaluatable->False, CellTags->"c:1"], Cell[CellGroupData[{ Cell[1937, 62, 95, 3, 88, "Section", Evaluatable->False, CellTags->"c:2"], Cell[CellGroupData[{ Cell[2057, 69, 100, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:3"], Cell[2160, 74, 830, 19, 368, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[3027, 98, 104, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:4"], Cell[3134, 103, 1752, 50, 143, "Text", Evaluatable->False], Cell[4889, 155, 1946, 62, 243, "Text", Evaluatable->False], Cell[CellGroupData[{ Cell[6860, 221, 122, 5, 42, "Subsubsection", CellTags->"c:5"], Cell[6985, 228, 960, 28, 193, "Text", Evaluatable->False], Cell[7948, 258, 873, 26, 118, "Text", Evaluatable->False], Cell[8824, 286, 471, 9, 118, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[9344, 301, 64, 1, 42, "Subsection", CellTags->"c:6"], Cell[9411, 304, 517, 9, 118, "Text"], Cell[CellGroupData[{ Cell[9953, 317, 123, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:7"], Cell[10079, 322, 353, 7, 93, "Text", Evaluatable->False], Cell[10435, 331, 164, 3, 74, "Input"], Cell[10602, 336, 131, 3, 43, "Text"], Cell[10736, 341, 110, 2, 74, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[10883, 348, 121, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:8"], Cell[11007, 353, 944, 24, 143, "Text", Evaluatable->False], Cell[11954, 379, 79, 2, 51, "Input"], Cell[12036, 383, 222, 6, 68, "Text", Evaluatable->False], Cell[12261, 391, 641, 11, 168, "Text", Evaluatable->False], Cell[12905, 404, 647, 14, 143, "Text", Evaluatable->False], Cell[13555, 420, 90, 2, 51, "Input"], Cell[13648, 424, 211, 7, 43, "Text", Evaluatable->False], Cell[13862, 433, 130, 3, 51, "Input"], Cell[13995, 438, 409, 13, 68, "Text"], Cell[14407, 453, 142, 3, 51, "Input"], Cell[14552, 458, 118, 2, 43, "Text", Evaluatable->False], Cell[14673, 462, 143, 3, 51, "Input"], Cell[14819, 467, 75, 0, 43, "Text"], Cell[14897, 469, 165, 3, 51, "Input"], Cell[15065, 474, 136, 5, 43, "Text"], Cell[15204, 481, 162, 3, 74, "Input"], Cell[15369, 486, 54, 0, 43, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[15460, 491, 108, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:9"], Cell[15571, 496, 1468, 41, 193, "Text", Evaluatable->False], Cell[17042, 539, 227, 5, 55, "Program"], Cell[17272, 546, 351, 9, 68, "Text", Evaluatable->False], Cell[17626, 557, 96, 2, 51, "Input"], Cell[17725, 561, 659, 16, 143, "Text", Evaluatable->False], Cell[18387, 579, 96, 2, 51, "Input"], Cell[18486, 583, 253, 6, 68, "Text", Evaluatable->False], Cell[18742, 591, 134, 3, 51, "Input"], Cell[18879, 596, 139, 3, 51, "Input"], Cell[19021, 601, 137, 3, 51, "Input"], Cell[19161, 606, 151, 5, 43, "Text"], Cell[19315, 613, 159, 3, 51, "Input"], Cell[19477, 618, 145, 5, 43, "Text"], Cell[19625, 625, 155, 3, 51, "Input"], Cell[19783, 630, 249, 6, 68, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[20081, 642, 114, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:10"], Cell[20198, 647, 463, 11, 118, "Text", Evaluatable->False], Cell[CellGroupData[{ Cell[20686, 662, 131, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:11"], Cell[20820, 667, 1242, 37, 218, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[22099, 709, 111, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:12"], Cell[22213, 714, 1610, 50, 218, "Text", Evaluatable->False], Cell[23826, 766, 1274, 37, 368, "Text", Evaluatable->False], Cell[25103, 805, 293, 11, 43, "Text"], Cell[25399, 818, 132, 3, 74, "Input"], Cell[25534, 823, 130, 3, 51, "Input"], Cell[25667, 828, 205, 7, 43, "Text", Evaluatable->False], Cell[25875, 837, 145, 3, 51, "Input"], Cell[26023, 842, 182, 5, 43, "Text"], Cell[26208, 849, 171, 3, 51, "Input"], Cell[26382, 854, 351, 12, 43, "Text", Evaluatable->False], Cell[26736, 868, 168, 3, 51, "Input"], Cell[26907, 873, 64, 0, 43, "Text"], Cell[26974, 875, 166, 3, 74, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[27177, 883, 110, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:13"], Cell[27290, 888, 1128, 40, 268, "Text", Evaluatable->False], Cell[28421, 930, 74, 0, 43, "Text"], Cell[28498, 932, 308, 8, 97, "Input"], Cell[28809, 942, 125, 3, 43, "Text"], Cell[28937, 947, 430, 9, 143, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[29404, 961, 117, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:14"], Cell[29524, 966, 2095, 56, 396, "Text", Evaluatable->False], Cell[31622, 1024, 1107, 30, 293, "Text", Evaluatable->False], Cell[32732, 1056, 591, 20, 68, "Text", Evaluatable->False], Cell[33326, 1078, 368, 11, 68, "Text", Evaluatable->False], Cell[33697, 1091, 341, 13, 81, "Text", Evaluatable->False], Cell[34041, 1106, 451, 9, 118, "Text", Evaluatable->False], Cell[34495, 1117, 493, 16, 43, "Text", Evaluatable->False], Cell[34991, 1135, 881, 22, 168, "Text", Evaluatable->False], Cell[35875, 1159, 147, 3, 51, "Input"], Cell[36025, 1164, 147, 3, 51, "Input"], Cell[36175, 1169, 190, 8, 43, "Text"], Cell[36368, 1179, 147, 3, 51, "Input"], Cell[36518, 1184, 118, 2, 43, "Text", Evaluatable->False], Cell[36639, 1188, 152, 3, 51, "Input"], Cell[36794, 1193, 110, 2, 43, "Text", Evaluatable->False], Cell[36907, 1197, 173, 4, 97, "Input"], Cell[37083, 1203, 163, 3, 51, "Input"], Cell[37249, 1208, 188, 4, 74, "Input"], Cell[37440, 1214, 188, 4, 74, "Input"], Cell[37631, 1220, 594, 22, 68, "Text", Evaluatable->False], Cell[38228, 1244, 146, 2, 74, "Input"], Cell[38377, 1248, 92, 1, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[38506, 1254, 118, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:15"], Cell[38627, 1259, 926, 26, 168, "Text", Evaluatable->False], Cell[39556, 1287, 2041, 66, 268, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[41646, 1359, 114, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:16"], Cell[41763, 1364, 245, 6, 68, "Text", Evaluatable->False], Cell[CellGroupData[{ Cell[42033, 1374, 104, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:17"], Cell[42140, 1379, 976, 28, 118, "Text", Evaluatable->False], Cell[43119, 1409, 539, 17, 143, "Text", Evaluatable->False], Cell[43661, 1428, 1036, 26, 168, "Text", Evaluatable->False], Cell[44700, 1456, 541, 10, 118, "Text", Evaluatable->False], Cell[45244, 1468, 188, 4, 68, "Text"], Cell[45435, 1474, 77, 1, 51, "Input"], Cell[45515, 1477, 123, 2, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[45675, 1484, 119, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:18"], Cell[45797, 1489, 1509, 45, 168, "Text", Evaluatable->False], Cell[47309, 1536, 402, 13, 118, "Text", Evaluatable->False], Cell[47714, 1551, 418, 13, 68, "Text", Evaluatable->False], Cell[48135, 1566, 133, 3, 43, "Text"], Cell[48271, 1571, 110, 2, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[48418, 1578, 105, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:19"], Cell[48526, 1583, 526, 16, 68, "Text", Evaluatable->False], Cell[49055, 1601, 609, 20, 168, "Text", Evaluatable->False], Cell[49667, 1623, 145, 3, 43, "Text"], Cell[49815, 1628, 178, 3, 74, "Input"], Cell[49996, 1633, 196, 6, 38, "Text"], Cell[50195, 1641, 141, 2, 51, "Input"], Cell[50339, 1645, 61, 0, 38, "Text"], Cell[50403, 1647, 181, 3, 74, "Input"], Cell[50587, 1652, 151, 3, 63, "Text"], Cell[50741, 1657, 139, 2, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[50917, 1664, 99, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:20"], Cell[51019, 1669, 1004, 30, 168, "Text", Evaluatable->False], Cell[52026, 1701, 696, 19, 168, "Text", Evaluatable->False], Cell[52725, 1722, 1317, 31, 268, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[54079, 1758, 114, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:21"], Cell[54196, 1763, 2110, 55, 395, "Text", Evaluatable->False], Cell[56309, 1820, 1484, 49, 168, "Text", Evaluatable->False], Cell[57796, 1871, 453, 13, 93, "Text", Evaluatable->False], Cell[58252, 1886, 1418, 38, 218, "Text", Evaluatable->False], Cell[59673, 1926, 1054, 24, 268, "Text", Evaluatable->False], Cell[60730, 1952, 322, 6, 111, "InputOnly"], Cell[61055, 1960, 224, 7, 93, "Text", Evaluatable->False], Cell[61282, 1969, 157, 3, 74, "Input"], Cell[61442, 1974, 129, 3, 37, "Input"], Cell[61574, 1979, 344, 11, 63, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[61955, 1995, 109, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:22"], Cell[62067, 2000, 2026, 64, 368, "Text", Evaluatable->False], Cell[64096, 2066, 896, 36, 218, "Text", Evaluatable->False], Cell[64995, 2104, 1069, 28, 193, "Text", Evaluatable->False], Cell[66067, 2134, 498, 14, 93, "Text", Evaluatable->False], Cell[66568, 2150, 168, 7, 95, "Program", Evaluatable->False], Cell[66739, 2159, 505, 12, 143, "Text", Evaluatable->False], Cell[67247, 2173, 116, 2, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[67400, 2180, 105, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:23"], Cell[67508, 2185, 2087, 55, 368, "Text", Evaluatable->False], Cell[69598, 2242, 192, 4, 74, "Input"], Cell[69793, 2248, 397, 13, 63, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[70239, 2267, 119, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:24"], Cell[70361, 2272, 1349, 36, 218, "Text", Evaluatable->False], Cell[71713, 2310, 2230, 57, 368, "Text", Evaluatable->False], Cell[73946, 2369, 348, 11, 68, "Text", Evaluatable->False], Cell[74297, 2382, 447, 16, 195, "Program", Evaluatable->False], Cell[74747, 2400, 259, 6, 68, "Text", Evaluatable->False], Cell[75009, 2408, 127, 9, 135, "Program", Evaluatable->False], Cell[75139, 2419, 399, 10, 93, "Text"], Cell[CellGroupData[{ Cell[75563, 2433, 132, 6, 63, "Subsubsection", Evaluatable->False, CellTags->"c:25"], Cell[75698, 2441, 426, 12, 93, "Text", Evaluatable->False], Cell[76127, 2455, 2105, 58, 343, "Text", Evaluatable->False], Cell[78235, 2515, 1805, 52, 293, "Text", Evaluatable->False], Cell[80043, 2569, 1916, 52, 268, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[81996, 2626, 125, 6, 63, "Subsubsection", Evaluatable->False, CellTags->"c:26"], Cell[82124, 2634, 547, 10, 143, "Text", Evaluatable->False], Cell[82674, 2646, 296, 7, 68, "Text", Evaluatable->False], Cell[82973, 2655, 293, 6, 120, "Input"], Cell[83269, 2663, 88, 2, 51, "Input"], Cell[83360, 2667, 227, 5, 120, "Input"], Cell[83590, 2674, 1241, 36, 306, "Text", Evaluatable->False], Cell[84834, 2712, 53, 1, 35, "Program"], Cell[84890, 2715, 2757, 70, 444, "Text", Evaluatable->False], Cell[87650, 2787, 978, 27, 143, "Text", Evaluatable->False], Cell[88631, 2816, 1878, 58, 418, "Text", Evaluatable->False], Cell[90512, 2876, 277, 6, 68, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[90838, 2888, 110, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:29"], Cell[90951, 2893, 693, 13, 168, "Text", Evaluatable->False], Cell[91647, 2908, 568, 16, 118, "Text", Evaluatable->False], Cell[92218, 2926, 1745, 59, 218, "Text", Evaluatable->False], Cell[93966, 2987, 230, 8, 43, "Text", Evaluatable->False], Cell[94199, 2997, 2265, 68, 268, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[96501, 3070, 117, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:31"], Cell[96621, 3075, 691, 17, 143, "Text", Evaluatable->False], Cell[97315, 3094, 150, 4, 97, "Input"], Cell[97468, 3100, 108, 3, 38, "Text"], Cell[97579, 3105, 73, 2, 50, "Input"], Cell[CellGroupData[{ Cell[97677, 3111, 52, 1, 28, "Subsubsection", CellTags->"c:32"], Cell[97732, 3114, 417, 9, 93, "Text", Evaluatable->False], Cell[98152, 3125, 191, 4, 97, "Input"], Cell[98346, 3131, 1207, 33, 188, "Text"], Cell[99556, 3166, 270, 5, 120, "Input"], Cell[99829, 3173, 266, 4, 37, "Input"], Cell[100098, 3179, 469, 11, 113, "Text"], Cell[100570, 3192, 126, 2, 74, "Input"], Cell[100699, 3196, 175, 4, 63, "Text"], Cell[100877, 3202, 149, 3, 97, "Input"], Cell[101029, 3207, 68, 0, 38, "Text"], Cell[101100, 3209, 26, 0, 50, "Input"], Cell[101129, 3211, 26, 0, 36, "Input"], Cell[101158, 3213, 845, 26, 113, "Text"], Cell[102006, 3241, 261, 5, 68, "Text"], Cell[102270, 3248, 94, 2, 74, "Input"], Cell[102367, 3252, 211, 4, 63, "Text"], Cell[102581, 3258, 44, 0, 50, "Input"], Cell[102628, 3260, 106, 3, 38, "Text"], Cell[102737, 3265, 44, 0, 50, "Input"], Cell[102784, 3267, 212, 4, 63, "Text"], Cell[102999, 3273, 124, 2, 74, "Input"], Cell[103126, 3277, 436, 12, 88, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[103599, 3294, 69, 1, 42, "Subsubsection", CellTags->{"Rotations", "c:33"}], Cell[103671, 3297, 184, 5, 43, "Text", Evaluatable->False], Cell[103858, 3304, 195, 4, 97, "Input"], Cell[104056, 3310, 752, 25, 113, "Text", Evaluatable->False], Cell[104811, 3337, 136, 3, 74, "Input"], Cell[104950, 3342, 525, 11, 113, "Text", Evaluatable->False], Cell[105478, 3355, 59, 1, 51, "Input"], Cell[105540, 3358, 225, 8, 38, "Text", Evaluatable->False], Cell[105768, 3368, 171, 4, 97, "Input"], Cell[105942, 3374, 193, 4, 63, "Text"], Cell[106138, 3380, 94, 2, 74, "Input"], Cell[106235, 3384, 111, 3, 38, "Text"], Cell[106349, 3389, 134, 3, 74, "Input"], Cell[106486, 3394, 212, 4, 63, "Text"], Cell[106701, 3400, 144, 3, 74, "Input"], Cell[106848, 3405, 310, 5, 88, "Text"], Cell[107161, 3412, 246, 8, 43, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[107444, 3425, 53, 1, 42, "Subsubsection", CellTags->"c:34"], Cell[107500, 3428, 255, 6, 68, "Text", Evaluatable->False], Cell[107758, 3436, 232, 5, 120, "Input"], Cell[107993, 3443, 498, 12, 88, "Text", Evaluatable->False], Cell[108494, 3457, 229, 5, 120, "Input"], Cell[108726, 3464, 309, 6, 88, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[109072, 3475, 58, 1, 42, "Subsubsection", CellTags->"c:35"], Cell[109133, 3478, 595, 19, 93, "Text", Evaluatable->False], Cell[109731, 3499, 130, 3, 51, "Input"], Cell[109864, 3504, 104, 3, 70, "Input"], Cell[109971, 3509, 138, 3, 37, "Input"], Cell[110112, 3514, 98, 3, 70, "Input"], Cell[110213, 3519, 132, 3, 60, "Input"], Cell[110348, 3524, 667, 21, 88, "Text", Evaluatable->False], Cell[111018, 3547, 130, 3, 74, "Input"], Cell[111151, 3552, 200, 6, 63, "Text", Evaluatable->False], Cell[111354, 3560, 152, 3, 74, "Input"], Cell[111509, 3565, 293, 9, 63, "Text", Evaluatable->False], Cell[111805, 3576, 135, 3, 74, "Input"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[112001, 3586, 120, 3, 47, "Section", Evaluatable->False, CellTags->"c:36"], Cell[CellGroupData[{ Cell[112146, 3593, 115, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:37"], Cell[112264, 3598, 1223, 24, 268, "Text", Evaluatable->False], Cell[113490, 3624, 1650, 38, 393, "Text", Evaluatable->False], Cell[115143, 3664, 851, 22, 143, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[116031, 3691, 105, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:38"], Cell[CellGroupData[{ Cell[116161, 3698, 101, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:39"], Cell[116265, 3703, 859, 23, 143, "Text", Evaluatable->False], Cell[117127, 3728, 228, 8, 43, "Text", Evaluatable->False], Cell[117358, 3738, 330, 7, 65, "InputOnly"], Cell[117691, 3747, 104, 2, 51, "Input"], Cell[117798, 3751, 466, 12, 93, "Text", Evaluatable->False], Cell[118267, 3765, 118, 3, 74, "Input"], Cell[118388, 3770, 245, 6, 68, "Text", Evaluatable->False], Cell[118636, 3778, 101, 2, 51, "Input"], Cell[118740, 3782, 72, 2, 51, "Input"], Cell[118815, 3786, 333, 9, 68, "Text", Evaluatable->False], Cell[119151, 3797, 241, 6, 97, "Input"], Cell[119395, 3805, 108, 3, 74, "Input"], Cell[119506, 3810, 153, 5, 43, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[119696, 3820, 103, 3, 28, "Subsubsection", Evaluatable->False, CellTags->"c:40"], Cell[119802, 3825, 498, 11, 118, "Text", Evaluatable->False], Cell[120303, 3838, 90, 2, 51, "Input"], Cell[120396, 3842, 211, 7, 43, "Text", Evaluatable->False], Cell[120610, 3851, 130, 3, 51, "Input"], Cell[120743, 3856, 142, 3, 51, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[120934, 3865, 120, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:41"], Cell[CellGroupData[{ Cell[121079, 3872, 104, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:42"], Cell[121186, 3877, 1432, 33, 293, "Text", Evaluatable->False], Cell[122621, 3912, 173, 3, 65, "InputOnly"], Cell[122797, 3917, 671, 19, 93, "Text", Evaluatable->False], Cell[123471, 3938, 150, 3, 74, "Input"], Cell[123624, 3943, 250, 9, 43, "Text", Evaluatable->False], Cell[123877, 3954, 159, 3, 74, "Input"], Cell[124039, 3959, 173, 5, 60, "Input"], Cell[124215, 3966, 169, 6, 63, "Text", Evaluatable->False], Cell[124387, 3974, 184, 5, 74, "Input"], Cell[124574, 3981, 138, 5, 38, "Text", Evaluatable->False], Cell[124715, 3988, 90, 2, 51, "Input"], Cell[124808, 3992, 213, 6, 63, "Text", Evaluatable->False], Cell[125024, 4000, 687, 15, 212, "Input"], Cell[125714, 4017, 42, 0, 50, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[125793, 4022, 128, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:43"], Cell[125924, 4027, 157, 5, 43, "Text", Evaluatable->False], Cell[126084, 4034, 117, 2, 42, "InputOnly"], Cell[126204, 4038, 1228, 29, 243, "Text", Evaluatable->False], Cell[127435, 4069, 470, 14, 68, "Text", Evaluatable->False], Cell[127908, 4085, 72, 1, 51, "Input"], Cell[127983, 4088, 133, 3, 51, "Input"], Cell[128119, 4093, 165, 7, 38, "Text", Evaluatable->False], Cell[128287, 4102, 136, 3, 51, "Input"], Cell[128426, 4107, 218, 8, 38, "Text"], Cell[128647, 4117, 270, 6, 97, "Input"], Cell[128920, 4125, 461, 14, 63, "Text", Evaluatable->False], Cell[129384, 4141, 551, 13, 118, "Text", Evaluatable->False], Cell[129938, 4156, 85, 2, 51, "Input"], Cell[130026, 4160, 148, 3, 60, "Input"], Cell[130177, 4165, 151, 5, 38, "Text", Evaluatable->False], Cell[130331, 4172, 89, 2, 51, "Input"], Cell[130423, 4176, 177, 7, 38, "Text", Evaluatable->False], Cell[130603, 4185, 85, 2, 51, "Input"], Cell[130691, 4189, 117, 2, 37, "Input"], Cell[130811, 4193, 87, 3, 38, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[130935, 4201, 115, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:44"], Cell[131053, 4206, 415, 12, 93, "Text", Evaluatable->False], Cell[131471, 4220, 105, 2, 51, "Input"], Cell[131579, 4224, 499, 19, 93, "Text", Evaluatable->False], Cell[132081, 4245, 274, 7, 168, "Input"], Cell[132358, 4254, 1417, 47, 193, "Text", Evaluatable->False], Cell[133778, 4303, 161, 5, 43, "Text", Evaluatable->False], Cell[133942, 4310, 159, 4, 97, "Input"], Cell[134104, 4316, 98, 2, 38, "Text", Evaluatable->False], Cell[134205, 4320, 164, 4, 97, "Input"], Cell[134372, 4326, 168, 5, 38, "Text", Evaluatable->False], Cell[134543, 4333, 216, 6, 97, "Input"], Cell[134762, 4341, 222, 4, 63, "Text"], Cell[134987, 4347, 147, 2, 74, "Input"], Cell[135137, 4351, 155, 5, 38, "Text", Evaluatable->False], Cell[135295, 4358, 168, 4, 97, "Input"], Cell[135466, 4364, 375, 8, 106, "Input"], Cell[135844, 4374, 66, 0, 38, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[135947, 4379, 112, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:45"], Cell[136062, 4384, 1535, 42, 268, "Text", Evaluatable->False], Cell[137600, 4428, 85, 3, 70, "Input"], Cell[137688, 4433, 169, 5, 38, "Text"], Cell[137860, 4440, 34, 0, 50, "Input"], Cell[137897, 4442, 36, 0, 36, "Input"], Cell[137936, 4444, 402, 10, 88, "Text"], Cell[138341, 4456, 58, 0, 50, "Input"], Cell[138402, 4458, 402, 10, 88, "Text"], Cell[138807, 4470, 58, 0, 50, "Input"], Cell[138868, 4472, 118, 3, 38, "Text"], Cell[138989, 4477, 76, 0, 50, "Input"], Cell[139068, 4479, 484, 11, 88, "Text"], Cell[139555, 4492, 54, 3, 70, "Input"], Cell[139612, 4497, 70, 0, 38, "Text"], Cell[139685, 4499, 48, 0, 50, "Input"], Cell[139736, 4501, 225, 6, 63, "Text"], Cell[139964, 4509, 2109, 60, 318, "Text", Evaluatable->False], Cell[142076, 4571, 2287, 72, 373, "Text", Evaluatable->False], Cell[144366, 4645, 1900, 56, 293, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[146303, 4706, 68, 1, 42, "Subsubsection", CellTags->"c:46"], Cell[146374, 4709, 2044, 61, 343, "Text", Evaluatable->False], Cell[148421, 4772, 1281, 37, 268, "Text", Evaluatable->False], Cell[149705, 4811, 2277, 61, 413, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[152031, 4878, 109, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:47"], Cell[152143, 4883, 241, 5, 68, "Text"], Cell[CellGroupData[{ Cell[152409, 4892, 118, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:48"], Cell[152530, 4897, 3742, 109, 593, "Text", Evaluatable->False], Cell[156275, 5008, 3298, 99, 70, "Text", Evaluatable->False], Cell[159576, 5109, 132, 8, 70, "Program"], Cell[159711, 5119, 596, 15, 70, "Text"], Cell[160310, 5136, 135, 3, 70, "Input"], Cell[160448, 5141, 235, 6, 70, "Input"], Cell[160686, 5149, 787, 19, 70, "Text", Evaluatable->False], Cell[161476, 5170, 2230, 61, 70, "Text", Evaluatable->False], Cell[163709, 5233, 140, 3, 70, "Input"], Cell[163852, 5238, 611, 18, 70, "Text", Evaluatable->False], Cell[164466, 5258, 214, 7, 70, "Text", Evaluatable->False], Cell[164683, 5267, 104, 1, 70, "Program"], Cell[164790, 5270, 262, 6, 70, "Text", Evaluatable->False], Cell[165055, 5278, 592, 13, 70, "Input"], Cell[165650, 5293, 631, 19, 70, "Text", Evaluatable->False], Cell[166284, 5314, 139, 3, 70, "Input"], Cell[166426, 5319, 107, 3, 43, "Text"], Cell[166536, 5324, 147, 3, 74, "Input"], Cell[166686, 5329, 108, 2, 37, "Input"], Cell[166797, 5333, 109, 2, 38, "Text", Evaluatable->False], Cell[166909, 5337, 171, 3, 74, "Input"], Cell[167083, 5342, 109, 2, 38, "Text", Evaluatable->False], Cell[167195, 5346, 130, 3, 51, "Input"], Cell[167328, 5351, 115, 2, 38, "Text", Evaluatable->False], Cell[167446, 5355, 101, 2, 51, "Input"], Cell[167550, 5359, 68, 2, 38, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[167655, 5366, 126, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:49"], Cell[167784, 5371, 4240, 122, 718, "Text", Evaluatable->False], Cell[172027, 5495, 2023, 73, 70, "Text", Evaluatable->False], Cell[174053, 5570, 956, 29, 70, "Text", Evaluatable->False], Cell[175012, 5601, 135, 3, 70, "Input"], Cell[175150, 5606, 60, 1, 70, "Input"], Cell[175213, 5609, 315, 7, 70, "Text", Evaluatable->False], Cell[175531, 5618, 1335, 34, 218, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[176903, 5657, 67, 1, 42, "Subsubsection", CellTags->"c:50"], Cell[176973, 5660, 586, 15, 118, "Text"], Cell[177562, 5677, 848, 12, 258, "Input"], Cell[178413, 5691, 236, 6, 68, "Text"], Cell[178652, 5699, 213, 4, 97, "Input"], Cell[178868, 5705, 238, 7, 68, "Text"], Cell[179109, 5714, 51, 1, 51, "Input"], Cell[179163, 5717, 176, 5, 38, "Text", Evaluatable->False], Cell[179342, 5724, 134, 3, 97, "Input"], Cell[179479, 5729, 610, 14, 138, "Text", Evaluatable->False], Cell[180092, 5745, 52, 1, 51, "Input"], Cell[180147, 5748, 176, 4, 63, "Text"], Cell[180326, 5754, 54, 1, 51, "Input"], Cell[180383, 5757, 116, 3, 38, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[180548, 5766, 112, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:51"], Cell[180663, 5771, 693, 14, 143, "Text"], Cell[CellGroupData[{ Cell[181381, 5789, 105, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:52"], Cell[181489, 5794, 2318, 56, 518, "Text", Evaluatable->False], Cell[183810, 5852, 463, 8, 166, "Input"], Cell[184276, 5862, 109, 3, 43, "Text"], Cell[184388, 5867, 122, 4, 90, "Input"], Cell[184513, 5873, 106, 3, 43, "Text"], Cell[184622, 5878, 112, 4, 70, "Input"], Cell[184737, 5884, 35, 0, 36, "Input"], Cell[184775, 5886, 93, 3, 43, "Text"], Cell[184871, 5891, 39, 0, 50, "Input"], Cell[184913, 5893, 59, 0, 38, "Text"], Cell[184975, 5895, 60, 0, 50, "Input"], Cell[185038, 5897, 93, 2, 38, "Text", Evaluatable->False], Cell[185134, 5901, 35, 0, 50, "Input"], Cell[185172, 5903, 39, 0, 50, "Input"], Cell[185214, 5905, 60, 0, 36, "Input"], Cell[185277, 5907, 152, 3, 83, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[185478, 5916, 98, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:27"], Cell[185579, 5921, 108, 2, 43, "Text", Evaluatable->False], Cell[185690, 5925, 339, 15, 318, "Text", Evaluatable->False], Cell[186032, 5942, 1512, 42, 218, "Text", Evaluatable->False] }, Closed]] }, Closed]] }, Closed]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)