(Math 547) Discrete Math. Appl. June 12 - July 28 2006 Instructor: Irvin Hentzel 7:30 - 9:20 a.m. Department of Mathematics Monday - Friday. 432 Carver Hall Ames, Iowa, 50011 Phone: 515-294-8141 E-mail: hentzel@iastate.edu Fax: 515-294-5454 (Math. Dept.) http://orion.math.iastate.edu/hentzel/class.547.06 June 12 1.1 and 1.2 P8: 9,11 p16: 26, 28, 29 June 13 1.3 and 1.4 June 14 2.1 and 2.2 p46:3,38 p52:3 p53:17,31 June 15 2.3 June 16 2.4 -------------------------------------------------------------- June 19 2.5 June 20 2.6 June 21 3.1 and 3.2 June 22 3.3 and 3.4 June 23 3.5 and 3.6 -------------------------------------------------------------- June 26 TEST I Wednesday, June 14 sections 2.1 and 2.2 sets and equivalence relations Homework p46:3,38 p52:3 p53:17,31 ------------------------------------------------------------------ Main Idea: Sort objects into piles. Goal: Recognize that Equivalence relations and partitions are the exact same thing. Key words: Equivalence Relation, Partition. mod, sixteen-puzzle ---------------------------------------------------------------- We first review set terminology using Venn Diagrams. _____________________________________ | | | | | | | ___________ | | | | c | | | A | A | | | | | | |_________| | | | | | | | |___________________________________| The Universe. Given a set A, everything not in A is in the complement of A. This naive concept of "everything not in A" leads to a logical contradiction. So the problem was fixed by always fixing a Universe under discussion first. Then the complement is taken with respect to this universe. ------------------------------------------------------------- This illustrates the union of A and B or A U B. _____________________________________ | | | | | | | ___________ | | |/////////| | | |// A/|---|----------| | | |/////|///|//////////| | | |-----|---|//////////| | | |////// B /////| | | |//////////////| | | |--------------| | | | | | ------------------------------------- The Universe ------------------------------------------------------------- This illustrates the intersection of A and B or A n B. _____________________________________ | | | | | | | |---------| | | | | | | | A ----|----------| | | | |///| | | | | |///| | | | |-----|---| B | | | | | | | |--------------| | | | ------------------------------------- The Universe. ------------------------------------------------------------- c c c Prove (A U B) = A n B If indeed this is true, it might be a good idea to visualize the statement. Maybe then we can see an application of the idea in our daily lives. "I don't like hobbles and I can't stand fences" means I don't like either hobbles or fences. -------------------------------------------------------------- Traditionally, one expects the proof of the expression to be written in the following format. Two sets are equal if they contain the same elements. So we show that: (a) each element of the left set is in the right set. (b) each element in the right set is also in the left set. Sometimes one writes part (a) and then claims that part (b) follows by reading the proof backwards. People do this, but short cuts in proofs do not convince me very much. It is so easy to miss something in proofs that I like the clear direct method. This is just a word of advice for those times when it is important to know you have a proof. Can you beat four aces with a royal flush? ------------------------------------------------------------------ Proof: c c c We first show that (AUB) c A n B. c Suppose that x e (A U B) . Then x is not in A U B . x is not in A and x is not in B. c c x e A and x e B. c c x e A n B. c c c We next show that A n B c (AUB). c c Suppose that x e A n B . c c Then x is in A and x is in B . Then x is not in A and x is not in B. Then x is not in A U B. c Then x is in (A U B) . -------------------------------------------------------------- We have shown that both sets contain the same elements so the sets are equal. An interesting note is the operation A+B defined by the Venn Diagram below: _____________________________________ | | | | | | | |---------| | | |/////////| | | |// A ----|----------| | | |/////| |//////////| | | |/////| | /////////| | | |-----|---|// B /////| | | |//////////////| | | |--------------| | ------------------------------------- The Universe. A+B = the elements in A or in B but not in Both. c A+B = (A n B) n (A U B) ---------------------------------------------------------------- Notice that we have A + B = B + A Commutative. (A + B) + C = A + (B + C) Associative (A + {} ) = A The empty set {} is the identity for the sum + (A + A ) = {} Each element is its own additive inverse. Furthermore An(B+C) = (AnB)+(AnC) distributive laws An(BnC) = (AnB)nC associativity of multiplication A n U = A U is the multiplicative identity. ------------------------------------------------------------------ Supposedly, this sum and product occurred to George Boole as a student. It seemed that sets have an addition and multiplication just like the integers. His teacher is supposed to have observed that c AnA = {} and said that if {} was supposed to be zero, how could you have the product of two nonzero things being zero. These things are now called Boolean rings and are important in logic. The proof of the associative law for addition is rather lengthy. ------------------------------------------------------------------- Problem: Look at this ring in the subset notation where the string a b c d e f 1 0 0 1 0 0 means the subset {a,d}. -------------------------------------------------------------- CARTESIAN PRODUCT: If A and B are sets, then AxB = {(a,b) | a e A and b e B}. This is called the Cartesian product of the two sets. It is not commutative and is just a way to talk about ordered pairs of elements. A relation on a set S is any subset of SxS. Just any few ordered pairs is enough to make a relation. Not much can be said about a relation. But an EQUIVALENCE RELATION is another matter. ---------------------------------------------------------------- An Equivalence relation R has enough of the ordered pairs of SxS so that the following three properties hold. (s,s) is in R for all s in S. Thus R involves every element of S To some extent. This is called the diagonal. When a relation has the diagonal, the relation is called reflexive. if (s,t) is in R, then (t,s) is in R. This is called symmetric. if (s,t) is in R and (t,u) is in R, then This is called transitive. (s,u) is in R. ----------------------------------------------------------------- It is convenient to write sRt when we mean (s,t) is in R. _ It is also convenient to write x~t or x = t . We write the three properties of an equivalence relation as xRx for all x in S (Reflexive) xRy => yRx (Symmetric) xRy and yRz => xRz. (Transitive) ------------------------------------------------------------------ Example: Show that the relation on the real numbers given by xRy if x-y is rational. We show reflexive, symmetric, transitive. x-x = 0 which is rational so xRx for all x. if xRy then x-y is rational, so -(x-y) is rational, so yRx. if xRy and yRz then x-y and y-z are rational so (x-y)+(y-z) = x-z is rational and xRz. ------------------------------------------------------------------- This particular equivalence relation strikes at the very heart of mathematics. We will mention the problem when we get to the partition. ------------------------------------------------------------------ Fix an integer n. Show that the relation on the integers given by xRy if x-y is divisible by n is an equivalence relation. (reflexive) x-x = 0*n so xRx for all integers x. (symmetric) xRy => x-y = kn => y-x = (-k)n so yRx (transitive) xRy and yRz => x-y = kn and y-z = k'n (x-z) = (x-y)+(y-z) = (k+k')n xRz. --------------------------------------------------------------- BREAK BREAK BREAK BREAK BREAK BREAK BREAK BREAK BREAK BREAK BREAK BREAK BREAK BREAK BREAK ---------------------------------------------------------- PARTITION: Everybody knows what a partition is. What is a partition anyway? The interesting thing is that an equivalence relation is simply an internal way to describe a partition. -------------------------------------------------------------------- This is an example of a partition. The subsets are called cells of the partition. ---------------------------------- | | | | | | | | | | | | |------------| |------| | | | | | |------------| | | | | | |------| | | | | | | | | ---------------------------------- We demand that the cells be non-empty, non-intersecting, and that the cells exhaust the original set. In set notation {Ai | i e I} is said to be a partition of a set S if. (1) Ai =/= {}. (non-empty) (2) U Ai = S (union is all of S) i e I (3) Ai n Aj =/= {} ==> Ai = Aj (disjoint). ------------------------------------------------------------ If one has a partition, we simply say two elements are related if the are in the same cell. Clearly this is reflexive and symmetric. The transitive follows because the cells are disjoint. ------------------------------------------------------------ If one has an equivalence relation, the partition is formed by slicing up the set into blocks where all the elements in the block are related to one another. In this instance, we refer to the block containing an element s as Class(s). Of course Class(s) = Class(s') whenever s and s' are in the same block. The name of the block need not be unique. We live with this imperfection daily. ----------------------------------------------------------------- If Johnny is a Boy Scout, we talk about Johnny's scout troop. Yet Freddy's troop may be the same troop. If you wish to separate the scouts into individual troops, it is easier to tell the scouts to seek out their own troop. The other way would require knowing all the troop numbers and telling repeatedly where each troop should gather. ------------------------------------------------------------ Rationals as a partition; A more mathematical example. In rational numbers we say the rational 1/2 is the same as 2/4 is the same as 3/6. So by the rational number 1/2 we mean not just the example 1/2 but all other fractions with the same value. When one gives the formula for addition of fractions, it does not matter if the fractions added are in reduced form or not. One gets the same answer. But it is not obvious that the answer does not depend on the particular form. Sometimes good students can be just a bit hesitant about accepting the adding of fractions because they sense something is missing. The teacher just assumes that they can't learn the obvious. -------------------------------------------------------------- We may point out the relation involved is a/b R c/d <======> ad = bc is an equivalence relation that partitions all the fractions a/b into classes with the same value as rationals. In fact is is more reasonable to think of the rational 1/2 as the common property of all the elements in the class of 1/2, rather than as the expression with numerator 1 and denominator 2. --------------------------------------------------------------- _ _ Problem: Show that if a/b = a'/b' and c/d = c'/d', then _ (ad+bc)/(bd) = (a'd'+b'c')/(b'd'). ---------------------------------------------------------------- The sgn of a permutation: Given a string of distinct numbers a1 a2 a3 ... an we say in inversion occurs when a larger number precedes a smaller number. For example: 3 2 1 has 3 inversions. 4 3 1 2 has 5 inversions. 3 4 1 3 we do not talk about inversions here because the numbers are not distinct. ---------------------------------------------------------------- We are going to partition the permutations of 1 2 3 ... n into two classes putting those with an even number of inversions into one class, the those with an odd number of inversions into the other. The permutations in with the even number of inversions are called even permutations. Those with an odd number of inversions are called odd permutations. This even or odd is called the "parity" of the permutation. ------------------------------------------------------------------- Problem: If one interchanges two adjacent numbers in a permutation then one changes the parity of the permutation. -------------------------------------------------------------------- Problem: If one changes any two numbers in permutation, then one changes the parity of the permutation. --------------------------------------------------------------------- Count the number of inversions: Is this permutation even or odd? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Count the number of inversions: 15 14 13 12 Is this permutation even or odd? 11 10 9 8 7 6 5 4 3 2 1 16 --------------------------------------------------------------- Assuming that 16 is the "blank", notice that each move interchanges the position of two elements and thus changes the parity of the permutation. Also notice that whenever the 16 is on one of the # squares the parity must be the same. What is that parity. # 0 # 0 0 # 0 # # 0 # 0 0 # 0 # ----------------------- --------------------- | Even permutations | | odd permutations | | | <--------->| | | Blank on [#] | Each move | Blank on [0] | | | | | ----------------------- --------------------- Doing legal moves prevents the 16 from getting back to its starting position with a different parity. Thus the second is impossible to get from the first. He put down his crack brain puzzle He has climbed the asylum stair Numbers 13 15 14 turned his brain and sent him there. -------------------------------------------------------------------