Now with this definition - so,
in a vacuum, you kind of look at this and you're like,
“Okay, this kind of makes sense. I mean this is how I
think we should add these two sets. We just add the arguments together,
and that’s how I think we should multiply the two sets.
We just multiply the arguments together.
So at the surface, it seems really obvious,
but there's something that you have to actually do here
and that's not maybe so obvious on your first time around,
and that's this issue of this notion of being well-defined.
So that's we're going to talk about in the next slide, okay?
So this operation depends a little bit
on the representation of your congruence class.
What do I mean by this? Let's take a look at this abstractly,
and then let's take a look at this concretely,
and then I think it's a little bit easier to understand.
So suppose that over Z mod m, the integers modulo m
we have that the congruence class a is the same as the
the congruence class of c, and the congruence class of
b is the same as the congruence class for d,
for some integers a, b, c, d.
Is it true - therefore then,
so is it true that
the congruence class of a plus b
is the same as the congruence class of c plus d?
So in other words, if I add a and I add b,
right, that gives me a plus b, is that the same as if I add c and if I add d?
Similarly, if I multiply a and b,
the congruence class of a and the congruence class of b,
is it the same as when I multiply the congruence class of c and the congruence class of d?
This would be a very weird world if this wasn't true.
If we had two different representations for something,
did an operation to them, and got two different results,
that seems to be a problem, right?
The results that we should get should be the same.
This is the notion - this is what we mean by when we call something well-defined, okay?
An object - this is well-defined if I take two different representations,
do the same operation to them, I get the same result. Okay?
Let's take a look at a concrete example which might make this a little bit clearer.
So concretely, let's do an example with the multiplication operation.
So as an example in Z mod 6,
is it true that 2 times 5 is equal to 14 times 13,
so the congruence class of 2 times the congruence class of 5,
is it true that that equals the congruence class of 14,
times the congruence class of negative 13.
We should expect that this is true, right? Why?
Because 2 is the same as 14, and
5 is the same as negative 13 in Z mod 6.
So modulo 6, 2 is congruent to 14 and 5 is congruent to negative 13.
Right. So this should be true. If
this operation is well-defined, these two things should work out okay.
So again, this is something - take a minute, pause the video,
try to work this out by hand.
What is 2 times 5? What does that really mean?
What is 14 times negative 13? What does that really mean?
Are those two congruence classes the same?
Let's take a look at a brief solution, or a solution sketch, of this problem now.
Hopefully you've paused it and solved it and come back.
So what are we doing? Well in Z mod 6, we're looking at this left hand side which is
the congruence class of 2 times the congruence class of 5.
By definition that's just the congruence class of 2 times 5,
and that is congruent to 10.
This is a typo, not 1. This is congruent to 10,
and 10 is congruent to 4 in Z mod 6. So the congruence class consisting of 10,
consists of all elements like 10, 16, 22,
and all the elements the other way so 10, 4, negative 2, and so on and so forth,
and 4 consist of the same elements, right? That's true because 10 is congruent to 4.
And also, on the other side, the right hand side is 14 times negative 13,
so we multiply those together.
Right? That's what this is defined as. When doing congruence class
multiplication, you multiply the arguments together,
and that's going to give me the congruence class of negative 182.
And if we think about it, well negative 180, that's congruent to 0 mod 6,
so I mean negative of 182 is congruent to minus 2
modulo 6.
And the congruence class consisting of the elements of…
the congruence class of elements congruent to minus 2 mod 6
is the same as the congruence class of the elements consisting of 4 mod 6,
and that's the key idea here, okay? So here's what it means to be well-defined.
A very, very subtle notion.
This is something that took me a very long time
when I first learned it to really understand and appreciate,
but now hopefully I've given you at least a starting point
to try to understand what it really means to be well-defined.
If you have two different representations of an object and you do the same operation
to those two different representations, you should end up with the same answer.
In this case we do.
Now to prove this formally and abstractly, you'd have to do this for all cases.
Not going to do that. It's a big symbol…
it's a big symbol manipulation and hopefully
this gives you at least the idea down of this.