{VERSION 3 0 "IBM INTEL NT" "3.0" } {USTYLETAB {CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 256 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "word" -1 262 "" 0 0 128 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "code" -1 263 "Courier" 1 12 255 0 0 1 0 1 0 0 0 0 0 0 0 }{CSTYLE "index" -1 264 "" 0 0 0 128 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "TXT CMD" -1 265 "MS Sans Serif" 0 0 128 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "Bookmark" -1 266 "" 0 0 0 128 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "bookmark" -1 267 "Arial Narrow" 0 0 0 128 0 1 0 1 0 0 0 0 0 0 0 }{CSTYLE "paragraph" -1 268 "" 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 269 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 278 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 282 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 285 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 286 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 287 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 288 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 289 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 290 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 291 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 293 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 294 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 295 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 255 255 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 6 6 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 4 4 0 0 0 0 0 0 -1 0 }{PSTYLE "" 4 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "newpage" -1 257 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 1 0 -1 0 }{PSTYLE "vfill" -1 258 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Definition" -1 259 1 {CSTYLE " " -1 -1 "" 0 0 0 64 128 1 0 0 0 0 0 0 0 0 0 }0 0 0 -1 4 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Theorem" -1 260 1 {CSTYLE "" -1 -1 "" 0 0 219 36 36 1 0 0 0 0 0 0 0 0 0 }0 0 0 -1 4 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Problem" -1 261 1 {CSTYLE "" -1 -1 "" 0 0 0 0 255 1 0 0 0 0 0 0 0 0 0 }0 0 0 -1 4 4 3 4 0 0 0 0 -1 0 }{PSTYLE "dblnorm" -1 262 1 {CSTYLE "" -1 -1 " " 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 2 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "code" 2 263 1 {CSTYLE "" -1 -1 "Comic Sans MS" 0 0 128 0 128 1 0 1 0 0 0 0 3 0 0 }0 0 0 -1 -1 -1 3 12 0 0 0 0 -1 0 }{PSTYLE "asis" 0 264 1 {CSTYLE "" -1 -1 "Arial Narrow" 1 12 128 64 0 1 0 0 0 0 0 1 3 0 0 }0 0 0 -1 -1 -1 3 6 0 0 0 0 0 0 }{PSTYLE "subproblem" 0 265 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "diagram" -1 266 1 {CSTYLE "" -1 -1 "" 0 0 239 239 239 1 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "dblnorm.mws" -1 267 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 2 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Item" 0 268 1 {CSTYLE " " -1 -1 "Lucida Sans" 1 12 0 0 0 1 0 0 0 0 0 0 0 0 0 }0 0 0 -1 6 -1 3 0 0 0 0 0 -1 0 }{PSTYLE "rdiagram" -1 269 1 {CSTYLE "" -1 -1 "" 0 0 239 239 239 1 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "texcomment" -1 270 1 {CSTYLE "" -1 -1 "" 0 0 128 128 128 1 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT -1 48 "Green's Relation on the \+ set of selfmaps of a set" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 259 "" 0 "" {TEXT 261 12 "Definitions:" }{TEXT -1 51 " Let X be a set. \+ A subset of X x X is called a " }{TEXT 256 8 "relation" }{TEXT -1 57 " on X. Let R be a relation on X. The statement [x,y] " }{XPPEDIT 18 0 "epsilon;" "6#%(epsilonG" }{TEXT -1 40 " R can also be written \+ x R y. R is " }{TEXT 257 9 "symmetric" }{TEXT -1 51 " if x R y i mplies y R x. The relation R is " }{TEXT 258 10 "transitive" } {TEXT -1 57 " if x R y and y R z implies x R z. The relation R is \+ " }{TEXT 259 9 "reflexive" }{TEXT -1 21 " if x R x for all x " } {XPPEDIT 18 0 "epsilon;" "6#%(epsilonG" }{TEXT -1 73 " X. If R is \+ symmetric, transitive, and reflexive then R is called an " }{TEXT 260 20 "equivalence relation" }{TEXT -1 57 " on R. Let R be an equivalen ce relation on X. The set " }{XPPEDIT 18 0 "R[x]" "6#&%\"RG6#%\"xG" } {TEXT -1 30 " = \{y | x R y\} is called the " }{TEXT 269 7 "R-class" }{TEXT -1 57 " of x. A collection P of nonempty subsets of X is a " }{TEXT 271 9 "partition" }{TEXT -1 74 " of X if every point of X l ies in exactly one member of the collection P." }}{PARA 261 "" 0 "" {TEXT 279 10 "Problem. " }{TEXT -1 96 " Show that the collection of R -classes of an equivalence relation R on X is a partition of X. " }} {PARA 261 "" 0 "" {TEXT 280 8 "Problem." }{TEXT -1 179 " Let P be a \+ partition of X and define a relation R on X by x R y if and only if \+ x and y lie in the same member of the partition. Show that R is an e quivalence relation on X." }}{PARA 259 "" 0 "" {TEXT 276 39 "Definitio n of Green's R and D relations" }{TEXT -1 63 ". Let X be the set of \+ selfmaps of the set A = \{1,2, ... n\}. " }{TEXT 277 18 "Green's R-re lation" }{TEXT -1 123 " is the relation R on X defined by f R g if and only if f(A) = g(A), that is, f and g have the same set of value s. " }{TEXT 278 18 "Green's D-relation" }{TEXT -1 61 " is the relat ion D on X defined by f D g if and only if " }{XPPEDIT 18 0 "abs( f(A)) =abs( g(A))" "6#/-%$absG6#-%\"fG6#%\"AG-F%6#-%\"gG6#F*" }{TEXT -1 51 ", that is, f and g have the same number of values." }}}{EXCHG {PARA 261 "" 0 "" {TEXT 281 9 "Problem. " }{TEXT -1 63 " Show that bot h of Green's relations are equivalence relations." }}{PARA 261 "" 0 " " {TEXT 285 9 "Problem. " }{TEXT -1 48 " Show that each D-class is a u nion of R-classes." }}{PARA 260 "" 0 "" {TEXT 286 8 "Example." }{TEXT -1 50 " If we take A = \{1,2\}, there are 2 D-classes, " } {XPPEDIT 18 0 "D[2,2];" "6#&%\"DG6$\"\"#\"\"#" }{TEXT -1 22 " = \{[1,2 ], [2,1]\} and " }{XPPEDIT 18 0 "D[2,1];" "6#&%\"DG6$\"\"#\"\"\"" } {TEXT -1 102 " = \{[1,1],[2,2]\}. The first D-class is also an R-clas s, but the second is the union of 2 R-classes, " }{XPPEDIT 18 0 "R[\{ 1\}]" "6#&%\"RG6#<#\"\"\"" }{TEXT -1 15 " = \{[1,1]\} and " }{XPPEDIT 18 0 "R[\{2\}]" "6#&%\"RG6#<#\"\"#" }{TEXT -1 11 " = \{[2,2]\}." }} {PARA 261 "" 0 "" {TEXT 282 8 "Problem." }{TEXT -1 42 " Let A = \{1,2 ,3\}. List each D-class in " }{XPPEDIT 18 0 "F[A]" "6#&%\"FG6#%\"AG " }{TEXT -1 58 " and count its members. Do the same for the R-classes in " }{XPPEDIT 18 0 "F[A]" "6#&%\"FG6#%\"AG" }{TEXT -1 2 ". " }} {PARA 261 "" 0 "" {TEXT 283 8 "Problem." }{TEXT -1 46 " Let A = \{1, 2,3,4\}. List each D-class in " }{XPPEDIT 18 0 "F[A]" "6#&%\"FG6#% \"AG" }{TEXT -1 58 " and count its members. Do the same for the R-cla sses in " }{XPPEDIT 18 0 "F[A]" "6#&%\"FG6#%\"AG" }{TEXT -1 2 ". " }} {PARA 0 "" 0 "" {TEXT 290 6 "Hint: " }{TEXT -1 12 " Use Maple." }} {PARA 261 "" 0 "" {TEXT -1 0 "" }{TEXT 289 8 "Problem." }{TEXT -1 48 " Let A = \{1,2,3,4,5\}. List each D-class in " }{XPPEDIT 18 0 "F[ A]" "6#&%\"FG6#%\"AG" }{TEXT -1 58 " and count its members. Do the sa me for the R-classes in " }{XPPEDIT 18 0 "F[A]" "6#&%\"FG6#%\"AG" } {TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT 291 5 "Hint:" }{TEXT -1 33 " N ow you really could use Maple." }}{PARA 259 "" 0 "" {TEXT 287 12 "Defi nition. " }{TEXT -1 76 " For each pair of positive integers [n,r] wit h r between n and 1, define " }{XPPEDIT 18 0 "D[n,r]" "6#&%\"DG6$%\" nG%\"rG" }{TEXT -1 23 " to be the D-class of " }{XPPEDIT 18 0 "F[A]" "6#&%\"FG6#%\"AG" }{TEXT -1 6 " and " }{XPPEDIT 18 0 "d[n,r]" "6#&%\" dG6$%\"nG%\"rG" }{TEXT -1 34 " to be the number of functions in " } {XPPEDIT 18 0 "D[n,r]" "6#&%\"DG6$%\"nG%\"rG" }{TEXT -1 4 ". " }} {PARA 261 "" 0 "" {TEXT 288 8 "Problem." }{TEXT -1 15 " Fill in the \+ " }{XPPEDIT 18 0 "d[n,r]" "6#&%\"dG6$%\"nG%\"rG" }{TEXT -1 49 " triang le. I will get you started: 1st row: " }{XPPEDIT 18 0 "d[1,1] = 1 " "6#/&%\"dG6$\"\"\"\"\"\"\"\"\"" }{TEXT -1 14 ", 2nd row: " } {XPPEDIT 18 0 "d[2,1] = 2, d[2,2] = 2" "6$/&%\"dG6$\"\"#\"\"\"\"\"#/&F %6$\"\"#\"\"#\"\"#" }{TEXT -1 3 ". " }}{PARA 261 "" 0 "" {TEXT 293 9 "Problem. " }{TEXT -1 78 " Show that two R-classes in the same D-class have the same number of elements." }}{PARA 259 "" 0 "" {TEXT 294 14 " Definition. " }{XPPEDIT 18 0 "r[n,r]" "6#&%\"rG6$%\"nGF$" }{TEXT -1 62 " is defined to be the number of elements in any R-class in " } {XPPEDIT 18 0 "D[n,r]" "6#&%\"DG6$%\"nG%\"rG" }{TEXT -1 3 ". " }} {PARA 261 "" 0 "" {TEXT 295 9 "Problem. " }{TEXT -1 13 " Fill in the \+ " }{XPPEDIT 18 0 "r[n,r]" "6#&%\"rG6$%\"nGF$" }{TEXT -1 47 " triangle. I will get you started. 1st row: " }{XPPEDIT 18 0 "r[1,1] = 1" "6# /&%\"rG6$\"\"\"\"\"\"\"\"\"" }{TEXT -1 12 ", 2nd row: " }{XPPEDIT 18 0 "r[2,1] = 1" "6#/&%\"rG6$\"\"#\"\"\"\"\"\"" }{TEXT -1 3 ", " } {XPPEDIT 18 0 "r[2,2] = 2;" "6#/&%\"rG6$\"\"#\"\"#\"\"#" }{TEXT -1 1 " ." }}}}{MARK "2" 0 }{VIEWOPTS 1 1 0 1 1 1803 }