- [Instructor] Okay, so we're gonna work our way
toward the dynamic equivalence problem.
And before we can do that
we have to understand what are relations
and equivalence relations.
And you'll recall that when we first presented sorting
we discussed order relations and we used the
less than or equal to operator as an example.
And we saw that if we apply that operator to the integers
then we see that it's reflexive.
That is A is less than or equal to A
for all A and the integers that makes sense.
It's anti symmetric.
That is if A is less than or equal to B
and B is less than or equal to A, then A's got an equal B.
And it's transitive, if A is less than or equal to B
and B is less than equal to C
then A is less than or equal to C so far so good.
But what we wanna do is we wanna take a step back
and look at relations in general.
And then we're going to move on to the idea
of an equivalence relation
which is different from an order relation.
Now, what is a relation?
Let's say we have two sets A and B
and we have an element from each set.
We'll call those lower case a and lowercase b.
And we say that these a and b are related
if the pair that's an ordered pair, a b is an element
of the set S where S is a subset
of the Cartesian product of sets a and b.
That's a mouthful.
So let's unpack this.
First we need to understand what is a Cartesian product.
A really good example
of a Cartesian product is playing cards.
We've all seen playing cards.
It's 52 of them, and we have a set of ranks.
Every suit has each one of these ranks.
And then we have a set of suits.
They're are four of those.
So we have the ACE of clubs, the ACE of diamonds, the ACE
of spades, the ACE of hearts, the two of clubs, and so on.
You see what I'm doing?
I'm taking every item in this set
and pairing it with one item in this set
but I'm doing it for all possible pairs.
Now we've got 13 elements
in this set and four elements in this set.
So the Cartesian product, when we take all
of those possible pairs is gonna be 52.
That's gonna get us our deck of cards.
So the set of all playing cards is the set of all ranks.
And I'm gonna say, cross the set of all suits.
Now this x, I say cross, because that's what we're doing
when we're generating these pairs from these sets
it's meant to have a connotation similar to multiplication.
And that's of course implied
in the term Cartesian product, but we're not multiplying.
You can think of it as a overloaded operator
which it is we're taking all of the possible pairs.
So we do that.
We get this set, we get this set
and we can generate from that all possible pairs.
And we have our complete deck of playing cards here, right?
That's a Cartesian product.
So let's go back to the relations here for a second.
And let's read it again.
Let's say we have two sets A and B and we have an element
from each set, little a and little b,
and we say that little a and little b related
if the pair little a b is an element
of the set S with S being a subset
of the Cartesian product of the sets, a and b.
So in the case of playing cards, that might be
we have two cards are related.
Maybe if their suit is the same
or if their rank is the same
or if their rank is even for example
and that would be a subset of the Cartesian product of sets.
Okay?
So that's our example of playing cards.
But it needn't be playing cards,
we could take any two sets, set a and set b
and we could take all of the possible pairs
of elements taking the first element
from the set a and the second element from the set b
and we can generate the Cartesian product
on two arbitrary sets.
It's not unusual that a and b are the same set.
Here A and B are both a set of natural numbers.
Those are the counting numbers.
And this set, the Cartesian product
of N cross N is
one one, one two,
one three, one four
off to infinity there, two one, two two, two three, two four
off to infinity three one, and so on.
That's the Cartesian product
of the natural numbers and the natural numbers.
But remember, let's go back to this one again.
I'm gonna go back to it again.
We're gonna look at S being a subset
of the Cartesian product.
So here's a subset, we've got one one,
two four, three nine, four 16, five 25.
That's clearly a subset of the cross of N by N,
what generates this?
What function gives us this subset of the Cartesian product
of N cross N?
Well, it's the function F of X equals X squared.
One squared is one, two squared is four
three squared is nine, four squared to 16 and so on.
Here's another one, we have this subset
one two, two three, three four, four five, five six,
and so on.
That's clearly a subset of the Cartesian product
of N cross N.
And it's generated by this function
F of X equals X plus one.
We often call that the successor function.
So one plus one is two
two plus one is three, three, plus one is four.
And so on.
Here's another one.
Take a look at this and tell me if you can figure out
what the function is that generates this subset
one one, two two, three three, four four,
five zero, six one, seven two, eight three, nine four,
10 zero, 11 one.
Yup, F of X equals X mod five.
So one mod five is one, two mod five is two,
three mod five is three, four mod five is four
five mod five is zero, six mod five is one.
And so on.
Guess what?
We're gonna see this example again.
So I hope we've unpacked this paragraph a little bit.
Again, we have two sets A and B,
we take an element from each set, A and B,
and we say that A and B are related
if the pair is an element of the set S
with S being a subset of the Cartesian product of the sets
A and B, and put another way, quote, this is
from a book by Mark Alan Weiss called data structures
and algorithms in Java.
A relation R is defined on a set S
if for every pair of the elements, A and B
with a and B elements of S a R b is either true or false.
So here, this a R b is a way of writing a is related to b.
Okay. And it's either true or false.
There's a predicate involved here.
And if a R b is true, then we say that a is related to b.
So those are relations.
Now what's an equivalence relation.
Well, if you'll remember again,
we looked at some properties of order relations,
for example, they're anti symmetric.
Well, an equivalence relation is a relation
which is reflexive, symmetric, and transitive.
We have all three of those apply.
Then our relation is an equivalence relation.
What does that mean?
Well, a is related to itself that seems almost obvious.
That is a is related to a, for all a and S, okay.
What does it mean to be symmetric?
Well, if a is related to b, then b is related to a
that seems pretty straight forward too.
And transitivity should come as no surprise.
If a is related to b, and b is related to c,
then a is related to c.
Now we're using this R notation, but sometimes
you'll see this written with a Tilde same thing.
Don't be surprised to see that notation.
Now let's talk about equivalence classes.
Now, given some relation R we can speak
of equivalence classes with respect to r.
And we just saw the example of congruence mod five
we'll have five equivalence classes.
Let's say we have some number a with a mod five equal one.
We write the equivalence class represented by a
as a in square brackets.
So this means all of the things that are equivalent to a
with regard to some relation.
All right, in this case, mod five equals one.
A number is in this same class as a, if it is congruent
to a mod five what's in this class, well, one, six, 11.
Okay. And generally we can write the equivalence class
that's represented by a equals all the X
in S such that X is related to a let's look at an example.
We're gonna stick with congruence modulo five.
So here we have some numbers.
We have zero mod five zero, one mod five is one,
two mod five is two and so on.
And you can see that some
of these are equivalent they're congruent
modulo five, zero and five for example,
one in six are congruent modulo five,
two and seven are congruent modulo five,
three and eight are congruent modulo five,
four and nine are congruent modulo five.
And so on.
Now, an interesting property of equivalence classes
is they completely partition the set in question,
for example, we here we have the set A Z
is the set of all integers
and we have five nice tidy slices.
And each slice has its own representative.
This is all the X element of Z
where X is congruent to zero modulo five.
That's these orange guys here fall
in this orange slice here.
These are all the ones that are congruent to one mod five
all the elements of Z that are congruent
to two mod five, to three mod five, to four by five.
There's nothing else.
If you take any number mod five
you're only gonna get one of these five answers,
zero, one, two, three, or four.
So any number any integer is gonna be congruent
either to zero, to one, to two, to three or to four,
with respect to mod five.
Notice also that these sets are disjoint.
What does it mean to be disjoint?
Well, remember what we saw in our introduction to sets
it means that their intersection is empty.
That means that there can't be any element
in the integers that's in this set.
And also in this set or any other set.
If it's congruent to zero,
it's only congruent to zero mod five.
It also can't be congruent to two mod five
every number is in its own bin.
And those sets are disjoint and they form a partition.
All of Z is in one of these five sets.
And each element in Z is in exactly one of these sets.
And that's an equivalence class.
Here's some examples.
Obviously we've just been looking at Congress modulo N
that's going to generate equivalence classes for us.
Are hash values are equivalence classes.
Similar triangles or congruent triangles
represent equivalence classes, cities within countries,
all the cities in France are within France.
They're not within Spain.
And all cities are within some country.
Yes, there are some city States
but then the city is the country like Monaco for example.
The countries are the equivalents classes that partition
the set of all cities.
Birthdays another good example, we all have a birthday.
Some of us have the same birthday.
None of us have two birthdays.
You can imagine the population of earth
all partitioned into sets based on their birthday.
Everybody that was born on January 1st
everybody that was born on January 2nd and so on.
What are some non-examples order relations?
Why aren't order relations equivalence classes?
Well, because they're not symmetric.
If A is less than B than B is not less than A.
Students and course registration at UVM.
Well, those aren't equivalent classes
because students can register for more than one class.
And the classes that they've registered don't partition
the students.
Dog breeds. Well, we have mixed breeds.
We have cockapoos that are a mix of cocker, spaniels
and poodles are labradoodles, which are mixes
of labrador, retrievers, and poodles and so on.
And finally friendship.
Friendship. What's the problem with friendship?
It's not transitive.
Abby can be a friend of Joe.
Joe can be a friend of Lisa
but that doesn't mean that Lisa and Abby are friends.
It's not transitive and therefore it's not an equivalent.
So this should give you an overview
of what are equivalence classes.
And from here, we're gonna move on to
the dynamic equivalence problem.
We'll see that in a later video, that's all for now.