Hello everyone, and welcome to this week's Carmen's Core Concepts.
This is week 2, my name is Carmen Bruni,
and this week we're gonna talk about some
of the key concepts that we did in Math 135 in week 2.
Again, I want to remind you that this isn't a substitute for lectures
in any way, shape, or form. I'll be going way too quickly
for this to be a substitute for lectures,
but what this is supposed to do is it's supposed to reinforce the key ideas of the week
to give you an idea of what we did
and to be used in conjunction with other tools,
like going to lectures, like practicing the problems, etc etc.
So let's start with divisibility theorems.
So last week we finished off with Bounds By Divisibility,
this week we'll start with it and talk about a couple of others.
So let a, b, c be integers,
recall that Bounds By Divisibility states that
"if a divides b and b is non-zero,
then the magnitude of a is less than or equal to the magnitude of b."
So it gives us a bound on the size of a and b.
So if a and b are always positive, then
a must be less than or equal to b, if it divides...
if a divides b, for example.
Transitivity of Divisibility, so we call this TD.
Transitivity itself is a very important mathematical concept. It's
one of the conditions to be an equivalence relation, for example.
So we'll see it again later.
What do we have here? We have
a divides b and b divides c and that implies that a divides c,
so the transitivity part is if the middle thing is the same,
so in this case the b on either side,
and a divides b and b divides c, then a must divide c.
This can be…you can change divisibility with, let's say "equals",
or other operators that you know.
So many things are transitive.
Divisibility of Integer Combinations, one of the
most used theorems of this course.
If a divides b and a divide c,
then for all x and y inside the integers,
a divides b x plus c [y].
So we'll talk about “for all” a little bit more in depth later, but
I just want to use this symbol here just to show that you can write
DIC using just symbols.
The proof of DIC it’s, again, one of these “follow your nose” type of proofs I like to say.
Assume the hypothesis, and then it kind of just
gradually leads you towards the conclusion.
At this point in the course, we really don't have any tools so
if all you get is a divides b and a divides c,
you probably want to use the definition.
Using the definition gives you integers m and n such that a m equals b and a n equals c,
and then for any integers x and y, we have that
b x plus c y is equal to a times some integer,
and hence, a divides b x plus c y.
So the proof, again, is a “follow your nose” kind of proof.
It's very short, very sweet,
but this property here, this theorem, has a lot of applications.
Let's see an example of them.
Here's just one example of applying it,
so if 5 divides a plus 2b and 5 divides 2a plus b,
then 5 divides… well if I take
2 times the first term,
and and add negative 1 times the second term,
then it divides that. Well what is that?
Well it's 2a plus 4b minus 2a minus b,
the two a’s are gonna cancel and you’re gonna be left with 3b.
So this shows you a way that you can use Divisibility of Integer Combinations
to find integer combinations to get things like…
so to get rid of a variable, for example, so here we got rid of a,
you can use them prove all sorts of things.
Proving that big numbers are divisible if you know that smaller numbers are,
so you can combine them to make bigger numbers
that are divisible by certain numbers.
Lots of interesting applications of DIC.
Again, we're gonna see this throughout the course,
so it is worth its own slide to give an example.
Very short, but it is a core concept
and you really should try to understand DIC in its fullness.
Converses, so next week especially
we're going to see a lot of words that begin with the letter C,
and it's very easy to get them confused, so
now is a good time that we just have this one
to put it in your memory banks and make sure that you have it down solid.
Let A and B be statements.
the converse of A implies B is B implies A.
So hypothesis implies conclusion,
the converse is conclusion implies hypothesis.
A very simple definition.
Converses are useful in mathematics.
If you prove an implication and you prove its converse,
that's much stronger than just proving an implication itself.
It somehow gives you a classification-type theorem,
which is a lot stronger than just an implication.
So as an example, the converse of Bounds By Divisibility
is given by,
“if the absolute value of a is less than or equal to the absolute value of b,
then a divides b and b does not equal 0."
Notice that this is false.
There's many counter examples of this,
so I mean, just take a equals 6 and b equals 7, for example.
6 is less than 7 but clearly 6 does not divide 7.
There are plenty of examples where this can go awry.
Okay, that's all I really want to say about converses.
But we can use converses in the next topic which is “if and only if”
statements.
So again, let A and B be statements.
we defined “if and only if”… so A if and only if B
we defined it by a truth table.
Here we said A if and only if B is true
if and only if both A and B are true or false, so they share the same value.
So if A and B share the same truth or false value,
then we say that A if and only if B is true, and otherwise it's false.
So how do we prove 'if and only if' questions in practice?
This exercise is what actually shows it.
I'm not going to prove it, I didn’t prove it in class either,
“Show that A if and only if B is logically equivalent to
A implies B ‘and’ B implies A.”
That's something I'll leave as an exercise.
But this gives you an idea of how to prove it.
Well you prove the normal thing, you prove
the implication A implies B,
and then you prove its converse.
So if an implication and its converse are true, then
the statement is an ‘if and only if’ statement.
We'll see a practical example of ‘if and only if’s
when we deal with sets afterwards. I wanted to say that to
accumulate everything; to give a nice
bridge between the two topics.
But that basically covers the end of the first lecture of the week.