{VERSION 3 0 "IBM INTEL NT" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{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 "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{CSTYLE " word" -1 256 "" 0 0 128 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "code" -1 257 "Courier" 1 12 255 0 0 1 0 1 0 0 0 0 0 0 0 }{CSTYLE "index" -1 258 "" 0 0 0 128 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "TXT CMD" -1 259 "MS S ans Serif" 0 0 128 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "Bookmark" -1 260 "" 0 0 0 128 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "bookmark" -1 261 "Arial N arrow" 0 0 0 128 0 1 0 1 0 0 0 0 0 0 0 }{CSTYLE "paragraph" -1 262 "" 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 } {CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 } {CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 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 0 1 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 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 } {CSTYLE "" -1 284 "" 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 0 1 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 0 1 0 0 0 0 0 0 } {CSTYLE "" -1 288 "" 0 1 0 0 0 0 0 0 1 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 292 "" 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 0 1 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 } {CSTYLE "" -1 296 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 297 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 298 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 300 "" 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 "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "Title" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 }{PSTYLE "newpage" -1 256 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 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 0 0 -1 0 }{PSTYLE "Definit ion" -1 258 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 259 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 260 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 261 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 262 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 263 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 "subprobl em" 0 264 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 265 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 266 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 267 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 268 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 269 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 18 "" 0 "" {TEXT -1 42 "The semigroup of selfmaps on a finite set." }}{PARA 258 "" 0 "" {TEXT 263 12 "Definitions." } {TEXT -1 40 " Let A and B be nonempty sets. The " }{TEXT 265 17 " Cartesian product" }{TEXT -1 66 " of A with B is the set A x B of all ordered pairs [a,b] where a " }{XPPEDIT 18 0 "epsilon;" "6#%(epsilonG " }{TEXT -1 9 " A and b " }{XPPEDIT 18 0 "epsilon;" "6#%(epsilonG" } {TEXT -1 8 " B. A " }{TEXT 266 20 "function from A to B" }{TEXT -1 49 " is a subset f of A x B such that for each a " }{XPPEDIT 18 0 "epsilon;" "6#%(epsilonG" }{TEXT -1 83 " A, there exactly one ordered pair in f with a as the first term. The symbol " }{TEXT 269 9 "f : A -> B" }{TEXT -1 61 " is written to mean f is a function from A to B. If [a,b] " }{XPPEDIT 18 0 "epsilon" "6#%(epsilonG" }{TEXT -1 29 " f, one says that b is the " }{TEXT 268 5 "value" }{TEXT -1 35 " of the function f at a and writes " }{XPPEDIT 18 0 "f(a) = b;" "6#/-%\"f G6#%\"aG%\"bG" }{TEXT -1 45 ". If f: A -> B, then A is called \+ the " }{TEXT 271 6 "domain" }{TEXT -1 19 " of f and B is the " }{TEXT 272 5 "range" }{TEXT -1 47 " of f. The set \{f(a) | a in A\} is call ed the " }{TEXT 282 5 "image" }{TEXT -1 56 " of A under f and is writt en f(A). The function f is " }{TEXT 283 10 "one-to-one" }{TEXT -1 172 " if it satisfies the condition f(x)=f(y) implies x = y. If f \+ : A -> B and g: B -> C, then gf: A -> C is the function defined by gf (x) = g (f (x)). gf is called the " }{TEXT 270 11 "composition" } {TEXT -1 55 " of g with f. If A = B, then f: A -> B is called a " }{TEXT 279 7 "selfmap" }{TEXT -1 5 " of A" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 278 9 "Examples." }{TEXT -1 60 " Let A = B = \{1,2,3\}. Two functions from A to A are " }{XPPEDIT 18 0 " f = \{[1,1],[2,1],[3,1]\}" "6#/%\"fG<%7$\"\"\"\"\"\"7$\"\"#\"\"\"7$ \"\"$\"\"\"" }{TEXT -1 5 " and " }{XPPEDIT 18 0 " g =\{[1,2],[2,3],[3, 1]\}" "6#/%\"gG<%7$\"\"\"\"\"#7$\"\"#\"\"$7$\"\"$\"\"\"" }{TEXT -1 143 ". The composition of fg and gf are different: They have differe nt values at 1, fg(1) = f(g(1)) = f(2) = 1, and gf(1) = g(f(1)) = g(1 ) = 2. " }}{PARA 259 "" 0 "" {TEXT 276 8 "Lemma. " }{TEXT -1 94 " If f and g are functions with the same domain A and for each x in A, f(x ) = g(x), then f = g." }}{PARA 0 "" 0 "" {TEXT 277 7 "Proof. " }{TEXT -1 21 " f = \{ (x,f(x)) | x " }{XPPEDIT 18 0 "epsilon;" "6#%(epsilonG " }{TEXT -1 20 " A\} = \{(x,g(x)) | x " }{XPPEDIT 18 0 "epsilon;" "6#% (epsilonG" }{TEXT -1 14 " A\} = g. qed." }}{PARA 259 "" 0 "" {TEXT 273 9 "Theorem. " }{TEXT -1 9 " The set " }{XPPEDIT 18 0 "F[A];" "6#&% \"FG6#%\"AG" }{TEXT -1 87 " of all functions from a set A to A is a s emigroup under the operation of composition." }}{PARA 0 "" 0 "" {TEXT 275 6 "Proof:" }{TEXT -1 182 " We need to show that the operation of composition is associative. So let f, g, and h be functions A->A. Then f(gh)(x) = f(gh(x)) = f(g(h(x)) = fg(h(x) = (fg)h (x) for each \+ x " }{XPPEDIT 18 0 "epsilon" "6#%(epsilonG" }{TEXT -1 43 " X. So by t he lemma, (fg)h = f(gh). qed." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 260 "" 0 "" {TEXT 280 8 "Problem." }{TEXT -1 23 " How many elem ents in " }{XPPEDIT 18 0 "F[A]" "6#&%\"FG6#%\"AG" }{TEXT -1 3 "? " }} {PARA 0 "" 0 "" {TEXT 281 18 "Start on Solution." }{TEXT -1 106 " We worked this out in class for A = \{1,2,3\} and got 27. Work it out in general, A = \{1, 2, ..., n\}." }}{PARA 258 "" 0 "" {TEXT 284 11 "Definition." }{TEXT -1 66 " If A is a finite set and f: A -> A is \+ 1-1, then f is called a " }{TEXT 285 11 "permutation" }{TEXT -1 47 " o f A. At the other extreme, f is called a " }{TEXT 287 8 "constant " }{TEXT -1 1 " " }{TEXT 288 8 "function" }{TEXT -1 38 " if f(A) has o nly one element. Let " }{XPPEDIT 18 0 "G[A]" "6#&%\"GG6#%\"AG" } {TEXT -1 5 " and " }{XPPEDIT 18 0 "C[A]" "6#&%\"CG6#%\"AG" }{TEXT -1 65 " denote the permutations and constant selfmaps of A respectively. " }}{PARA 260 "" 0 "" {TEXT 286 8 "Problem." }{TEXT -1 47 " If A = \+ \{1,2, ..., n\}, how many elements in " }{XPPEDIT 18 0 "G[A]" "6#&%\" GG6#%\"AG" }{TEXT -1 3 "? " }{XPPEDIT 18 0 "C[A]" "6#&%\"CG6#%\"AG" } {TEXT -1 10 "? Justify." }}{PARA 260 "" 0 "" {TEXT 289 9 "Problem. " } {TEXT -1 4 " Is " }{XPPEDIT 18 0 "G[A]" "6#&%\"GG6#%\"AG" }{TEXT -1 44 " a semigroup under composition? What about " }{XPPEDIT 18 0 "C[A] " "6#&%\"CG6#%\"AG" }{TEXT -1 12 "? Justify." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 4 "" 0 "" {TEXT -1 51 "Using Maple to work with \+ functions on a finite set." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 290 10 "Notation. " }{TEXT -1 187 " It is very convenien t use an abbreviated notation for a function f: A -> A by by just li sting its sequence of values. So if f = \{(1,3), (2,1), (3,1)\} a nd g= \{(1,2), (2,2), (3,1)\}" }{TEXT 291 1 "," }{TEXT -1 89 "then as lists of values f = [3,1,1] and g = [2,2,1]. . Maple can handle th ese as lists" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "f := [3,1,1 ]; g:= [2,2,1]; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG7%\"\"$\"\" \"F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG7%\"\"#F&\"\"\"" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 155 "Lets generate the set of all self maps on \{1,2,3\}. (We will make a list, rather than a set because Ma ple orders the elements of a differently than I like.)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 109 "F := NULL:\nfor i from 1 to 3 do f or j from 1 to 3 do for k from 1 to 3 do\nF := F,[i,j,k] od od od:\nF := [F];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"FG7=7%\"\"\"F'F'7%F'F' \"\"#7%F'F'\"\"$7%F'F)F'7%F'F)F)7%F'F)F+7%F'F+F'7%F'F+F)7%F'F+F+7%F)F' F'7%F)F'F)7%F)F'F+7%F)F)F'7%F)F)F)7%F)F)F+7%F)F+F'7%F)F+F)7%F)F+F+7%F+ F'F'7%F+F'F)7%F+F'F+7%F+F)F'7%F+F)F)7%F+F)F+7%F+F+F'7%F+F+F)7%F+F+F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 131 "Note all the functions which s atisfy f(1)=1 come first, then all functions such that f(1)=2, and la st all functions with f(1) = 3." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 260 "" 0 "" {TEXT 295 8 "Problem." }{TEXT -1 76 " List all the functions in F with exactly two values. How many are there?" }} {PARA 260 "" 0 "" {TEXT 296 9 "Problem. " }{TEXT -1 72 " If A = \{1,2 , ..., n\}, describe a method of listing all functions in " } {XPPEDIT 18 0 "F[A] " "6#&%\"FG6#%\"AG" }{TEXT -1 63 " with exactly tw o values. How many such functions are there?" }}{PARA 0 "" 0 "" {TEXT 297 24 "Hint on getting started." }{TEXT -1 348 " Depending on \+ how much experience you have had counting things, you might be able to just figure this out without experiment. Otherwise, work it for n = 3 first. Then n = 4. etc. until you see the pattern. Then use mat hematical induction to prove that the formula always works. Use mapl e profusely to generate data to look for the pattern." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 4 "" 0 "" {TEXT -1 25 "The composition operation" }}{PARA 0 "" 0 "" {TEXT -1 131 "The composition operation can be conveniently defined in Maple by an 'ampersand' operation (see neutral operators in Maple help). " }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "`&c` := proc(f,g) \n local i;\n [seq(f[g[i]],i=1..nops(f))] end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#&cGR6$%\"fG%\"gG6#%\"iG6\"F+7#-%$seqG6$&9$6#&9%6#8$/F6;\"\"\" -%%nopsG6#F1F+F+F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "[1,2, 2] &c [1,2,2];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"\"\"\"#F%" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 258 "" 0 "" {TEXT -1 0 "" }{TEXT 294 11 "Definition." }{TEXT -1 34 " A function \+ f: A -> A is called " }{TEXT 293 10 "idempotent" }{TEXT -1 59 " if f (f) = f. That is, f(f(x)) = f(x) for each x in A." }}{PARA 260 "" 0 "" {TEXT 292 9 "Problem. " }{TEXT -1 39 " List all the idempotent f unctions in " }{XPPEDIT 18 0 "F[A]" "6#&%\"FG6#%\"AG" }{TEXT -1 41 ", \+ where A = \{1,2,3\}. How many are there?" }}{PARA 0 "" 0 "" {TEXT 300 10 "Solution: " }{TEXT -1 93 " One solution is to just go though t he list F and list all the ones for which f &c f = f." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "for f in F do if f &c f = f then pr int(f) fi od ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"\"F$F$" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"\"F$\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"\"\"\"#F$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\" \"\"\"\"#F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"\"\"\"#\"\"$" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"\"\"\"$F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"#F$F$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"#F $\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"$\"\"#F$" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#7%\"\"$F$F$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 138 "So we see that there are 10 idempotent selfmaps on a 3 element se t: 1 permutation, 3 constants, and 6 idempotents with exactly 2 valu es." }}}{EXCHG {PARA 260 "" 0 "" {TEXT 298 9 "Problem. " }{TEXT -1 83 " If A = \{1,2, ..., n\}, describe a method of listing all idempoten t functions in " }{XPPEDIT 18 0 "F[A] " "6#&%\"FG6#%\"AG" }{TEXT -1 39 ". How many such functions are there?" }}}{EXCHG {PARA 4 "" 0 " " {TEXT -1 0 "" }}}}{MARK "10 0 0" 67 }{VIEWOPTS 1 1 0 1 1 1803 }