1
00:00:00,000 --> 00:00:02,700
Now with this definition - so,

2
00:00:02,700 --> 00:00:04,266
in a vacuum, you kind of 
look at this and you're like,

3
00:00:04,266 --> 00:00:07,000
“Okay, this kind of makes
sense. I mean this is how I

4
00:00:07,000 --> 00:00:09,600
think we should add these two sets. 
We just add the arguments together, 

5
00:00:09,600 --> 00:00:12,000
and that’s how I think we
should multiply the two sets.

6
00:00:12,000 --> 00:00:13,800
We just multiply the 
arguments together.

7
00:00:13,800 --> 00:00:15,766
So at the surface, it 
seems really obvious,

8
00:00:15,766 --> 00:00:17,933
but there's something that 
you have to actually do here

9
00:00:17,933 --> 00:00:20,533
and that's not maybe so obvious 
on your first time around,

10
00:00:20,533 --> 00:00:23,800
and that's this issue of this 
notion of being well-defined. 

11
00:00:23,800 --> 00:00:25,166


12
00:00:25,166 --> 00:00:27,666
So that's we're going to talk 
about in the next slide, okay?

13
00:00:27,666 --> 00:00:30,400
So this operation
depends a little bit

14
00:00:30,400 --> 00:00:34,533
on the representation of 
your congruence class.

15
00:00:34,533 --> 00:00:36,933
What do I mean by this? Let's 
take a look at this abstractly,

16
00:00:36,933 --> 00:00:38,633
and then let's take a 
look at this concretely,

17
00:00:38,633 --> 00:00:40,933
and then I think it's a little 
bit easier to understand.

18
00:00:40,933 --> 00:00:41,966


19
00:00:41,966 --> 00:00:45,033
So suppose that over Z mod
m, the integers modulo m

20
00:00:45,033 --> 00:00:48,133
we have that the congruence 
class a is the same as the

21
00:00:48,133 --> 00:00:50,733
the congruence class of c,
and the congruence class of

22
00:00:50,733 --> 00:00:53,100
b is the same as the 
congruence class for d,

23
00:00:53,100 --> 00:00:55,200
for some integers a, b, c, d.

24
00:00:55,200 --> 00:00:57,566
Is it true - therefore then,

25
00:00:57,566 --> 00:00:59,300
so is it true that

26
00:00:59,300 --> 00:01:01,433
the congruence class of a plus b

27
00:01:01,433 --> 00:01:04,466
is the same as the congruence 
class of c plus d?

28
00:01:04,466 --> 00:01:05,366


29
00:01:05,366 --> 00:01:08,566
So in other words, if 
I add a and I add b,

30
00:01:08,566 --> 00:01:13,133
right, that gives me a plus b, is that
the same as if I add c and if I add d?

31
00:01:13,133 --> 00:01:14,600


32
00:01:14,600 --> 00:01:16,400
Similarly, if I multiply a and b,

33
00:01:16,400 --> 00:01:19,000
the congruence class of a and 
the congruence class of b,

34
00:01:19,000 --> 00:01:23,566
is it the same as when I multiply the congruence 
class of c and the congruence class of d?

35
00:01:23,566 --> 00:01:26,400
This would be a very weird 
world if this wasn't true.

36
00:01:26,400 --> 00:01:27,200


37
00:01:27,200 --> 00:01:30,000
If we had two different
representations for something,

38
00:01:30,000 --> 00:01:32,400
did an operation to them, 
and got two different results, 

39
00:01:32,400 --> 00:01:35,166
that seems to be a problem, right?

40
00:01:35,166 --> 00:01:37,700
The results that we should 
get should be the same.

41
00:01:37,700 --> 00:01:38,466


42
00:01:38,466 --> 00:01:41,900
This is the notion - this is what we mean by 
when we call something well-defined, okay?

43
00:01:41,900 --> 00:01:45,366
An object - this is well-defined if I 
take two different representations,

44
00:01:45,366 --> 00:01:48,600
do the same operation to them, 
I get the same result. Okay?

45
00:01:48,600 --> 00:01:52,000
Let's take a look at a concrete example 
which might make this a little bit clearer.

46
00:01:52,000 --> 00:01:53,633


47
00:01:53,633 --> 00:01:56,400
So concretely, let's do an example 
with the multiplication operation.

48
00:01:56,400 --> 00:01:59,133
So as an example in Z mod 6,

49
00:01:59,133 --> 00:02:02,533
is it true that 2 times 5 
is equal to 14 times 13,

50
00:02:02,533 --> 00:02:06,000
so the congruence class of 2
times the congruence class of 5,

51
00:02:06,000 --> 00:02:08,300
is it true that that equals 
the congruence class of 14,

52
00:02:08,300 --> 00:02:11,233
times the congruence 
class of negative 13.

53
00:02:11,233 --> 00:02:13,600
We should expect that 
this is true, right? Why?

54
00:02:13,600 --> 00:02:15,700
Because 2 is the 
same as 14, and

55
00:02:15,700 --> 00:02:18,733
5 is the same as 
negative 13 in Z mod 6.

56
00:02:18,733 --> 00:02:22,933
So modulo 6, 2 is congruent to 14 
and 5 is congruent to negative 13.

57
00:02:22,933 --> 00:02:25,333


58
00:02:25,333 --> 00:02:27,466
Right. So this should be true. If

59
00:02:27,466 --> 00:02:30,266
this operation is well-defined, these 
two things should work out okay.

60
00:02:30,266 --> 00:02:33,366
So again, this is something - take 
a minute, pause the video,

61
00:02:33,366 --> 00:02:34,900
try to work this out by hand.

62
00:02:34,900 --> 00:02:36,833
What is 2 times 5? What 
does that really mean?

63
00:02:36,833 --> 00:02:39,333
What is 14 times negative 13? 
What does that really mean?

64
00:02:39,333 --> 00:02:41,733
Are those two congruence 
classes the same?

65
00:02:41,733 --> 00:02:42,933


66
00:02:42,933 --> 00:02:46,066
Let's take a look at a brief solution, or
a solution sketch, of this problem now.

67
00:02:46,066 --> 00:02:48,800
Hopefully you've paused it 
and solved it and come back.

68
00:02:48,800 --> 00:02:52,766
So what are we doing? Well in Z mod 6, 
we're looking at this left hand side which is

69
00:02:52,766 --> 00:02:55,566
the congruence class of 2 times 
the congruence class of 5.

70
00:02:55,566 --> 00:02:59,666
By definition that's just the
congruence class of 2 times 5,

71
00:02:59,666 --> 00:03:01,866


72
00:03:01,866 --> 00:03:04,933
and that is congruent to 10.

73
00:03:04,933 --> 00:03:08,033
This is a typo, not 1. 
This is congruent to 10,

74
00:03:08,033 --> 00:03:12,200
and 10 is congruent to 4 in Z mod 6. So
the congruence class consisting of 10,

75
00:03:12,200 --> 00:03:15,300
consists of all elements like 10, 16, 22,

76
00:03:15,300 --> 00:03:19,366
and all the elements the other way so
10, 4, negative 2, and so on and so forth,

77
00:03:19,366 --> 00:03:23,633
and 4 consist of the same elements, right? 
That's true because 10 is congruent to 4.

78
00:03:23,633 --> 00:03:24,333


79
00:03:24,333 --> 00:03:27,733
And also, on the other side, the right 
hand side is 14 times negative 13, 

80
00:03:27,733 --> 00:03:29,766
so we multiply those together.

81
00:03:29,766 --> 00:03:32,866
Right? That's what this is defined 
as. When doing congruence class

82
00:03:32,866 --> 00:03:35,133
multiplication, you multiply 
the arguments together,

83
00:03:35,133 --> 00:03:39,400
and that's going to give me the 
congruence class of negative 182.

84
00:03:39,400 --> 00:03:44,433
And if we think about it, well negative 
180, that's congruent to 0 mod 6,

85
00:03:44,433 --> 00:03:48,800
so I mean negative of 182 
is congruent to minus 2

86
00:03:48,800 --> 00:03:50,866
modulo 6.

87
00:03:50,866 --> 00:03:53,733
And the congruence class
consisting of the elements of…

88
00:03:53,733 --> 00:03:54,866


89
00:03:54,866 --> 00:03:58,933
the congruence class of elements 
congruent to minus 2 mod 6

90
00:03:58,933 --> 00:04:03,033
is the same as the congruence class 
of the elements consisting of 4 mod 6,

91
00:04:03,033 --> 00:04:06,866
and that's the key idea here, okay? So
here's what it means to be well-defined.

92
00:04:06,866 --> 00:04:07,500


93
00:04:07,500 --> 00:04:09,700
A very, very subtle notion.

94
00:04:09,700 --> 00:04:12,000
This is something that took 
me a very long time

95
00:04:12,000 --> 00:04:14,933
when I first learned it to really
understand and appreciate,

96
00:04:14,933 --> 00:04:18,433
but now hopefully I've given 
you at least a starting point

97
00:04:18,433 --> 00:04:20,966
to try to understand what it 
really means to be well-defined.

98
00:04:20,966 --> 00:04:24,000
If you have two different representations 
of an object and you do the same operation

99
00:04:24,000 --> 00:04:27,133
to those two different representations, you 
should end up with the same answer.

100
00:04:27,133 --> 00:04:28,733
In this case we do.

101
00:04:28,733 --> 00:04:32,366
Now to prove this formally and abstractly,
you'd have to do this for all cases.

102
00:04:32,366 --> 00:04:35,066
Not going to do 
that. It's a big symbol…

103
00:04:35,066 --> 00:04:37,266
it's a big symbol manipulation and hopefully

104
00:04:37,266 --> 00:04:40,000
this gives you at least 
the idea down of this.

105
00:04:40,000 --> 00:04:40,066