(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.
-------------------------------------------------------------------