Hello. You're about to watch the video lectures
for a course called Introduction to University Mathematics. This is something that is covered in the first
two weeks of the mathematics degree at Oxford. The goal of the course is to introduce you
to what is probably a more formal and rigorous way of presenting mathematical arguments
than you'll be used to from school. We're going to cover some basics of set theory
and logic and functions, and we're going to see various different examples
of mathematical proof and problem solving. The course is not trying to be completely
foundational in the sense that we start from some axioms and build everything up from those - that's something that we do in some other
courses - but it will introduce you to the notation
and the mathematical language that you need in order to do that. So I hope that you will enjoy it. Hello, so we're going to start by talking
about the natural numbers and then we're going to talk a bit about induction. So the natural numbers are something you've
probably come across before. These are the non-negative integers. There is a bit of ambiguity about whether
to include zero or not as a natural number. I'm going to decide that we will include zero.
So I'm first of all going to give a definition. That a natural number (I tend to underline
the thing that I'm trying to define) is a member of the sequence, zero, one, two and so on,
formed by starting from zero, and then successively adding one. OK, we're
going to write the set of natural numbers as N is curly brackets,
zero, one, two and so on. So this notation, this N with an extra line
on the front - it looks like that - is common notation
to mean the set of natural numbers. We'll see other related letters soon as well. And then this curly bracket is the notation
that's used to mean a set. So this is... I'm going to talk more about
sets later on as well... but a set is a collection of objects. In this case, the objects are the numbers
zero, one, two and so on. And as I say, we've included zero, but I'll
just make a remark that this is not universally accepted. So I'll say zero is
sometimes included in N and sometimes not. So that's just something to be aware of. We're
going to work with the definition that does include zero, and I think that for all of your courses,
you'll be doing that, at least in this first year. OK, what can we do in natural numbers? Well,
one thing that we know we can do is we can add them and we can multiply them. So I'll say we can add and multiply natural
numbers. And that gives rise to other natural numbers.
So If, for instance, M and N are two natural
numbers, I'm going to write that as M and M are in
the set N. This symbol here, this kind of curly E, is a symbol that means is an element
of. So this says M and N are elements of the set
of natural numbers. You're going to see that notation a lot. If
that's the case, then M plus N And M times N are also natural numbers. I'll just make the comment that M times N
is sometimes written as just M N.
It's often written M N. So typically I don't write the times symbol and just write the numbers next to each other, and by convention
that means that we're just multiplying them. Sometimes you put a dot in between as well. OK, in the context of addition and multiplication,
there are two important natural numbers and those are zero and one. So I'll say two important natural numbers
are zero and one. Why are they important? Well, they are the additive and multiplicative identities. What does that mean? So I'll say i.e. (that stands for Latin id
est - it means that is - I quite often write it if I want to restate something). So what
does it mean to say that you're an additive or a multiplicative identity? That means that
they don't do anything when you add them or multiply them. So this
means that for any N in the natural numbers, N plus zero is just
the same as N. So that means zero is an additive identity,
it leaves N alone. And N times one is N, and so one leaves alone
when it multiplies. So an identity, that's something which leaves
things alone when it operates on them. Addition and multiplication are examples of
what we call a binary operation. So they take two elements of the set of natural
numbers and then they do something to them - they operate on them - and produce another
natural number. We will see more examples of operations later on. So another important fact about natural numbers
is that they have an ordering. That's to say it makes sense to say that one
number is smaller than another one. So they have an ordering. So we can write
things like M is less than or equal to N. OK, hopefully you have some feeling about
what that means. But this is not something that's totally obvious. If we write down a set, some other sorts of
sets, which we'll talk about more later, then it's not obvious that we'll be able to do
this. For instance, if we had a set of matrices,
which is something that you will have to deal with a lot in Linear Algebra, and then we can't say one of the matrices
is less than or equal to another matrix. It doesn't mean anything. At least we don't
know what it would mean. In fact, even if the set is numbers, if this is a set of complex
numbers, you can't say one complex number is less than
or equal to another complex number because we don't know what that would mean. There are ways that you can make sense of
that, but it's certainly not obvious. So what exactly do we mean by less than or
equal to sign in the context of the natural numbers? I'm going to try and write down a more careful
definition. So this is attempting to be a definition of the less than or equal to sign. So here I'm going to let M and N be natural
numbers. I say that we write M is less than or equal
to N to mean that there exists some other natural, which I'll call K, such that M plus K is equal to N. So if you just think about that a second,
that makes sense. If M is less than or equal to N, then M plus K is equal to N for some
K, which is a natural number, an integer that's
greater than or equal to zero. OK, so that, once we're happy with addition,
then that tells me how to define this less than or equal to sign. I should point out that we haven't actually
defined addition and multiplication. I'm assuming that you know how to add and
multiply and natural numbers. But you might want to think about how to go
about defining what exactly you mean by adding and multiplying. In fact, I'm going to talk about that in the
next video. OK, so I want to now move on and talk about induction. And I'm going to quote this as a theorem,
although given the way that I've defined the natural numbers, it follows directly from
the definition, so it's not something I'm going to prove,
which is what I normally would do with a theorem. So I'm going to put it in quotation marks. And this is the principle of mathematical
induction. So let me state this here - and hopefully
this is something that you've seen before - we're going to let P of N be a family of
statements, indexed by the natural numbers. OK, so there's one of these statements for
each different N. So the statements might be something like, something really simple, like 'N is a natural number'. That's a statement
which is true for every N. It might be a statement like, N squared is odd - that's a statement that
is not true for every natural number, so we wouldn't be trying to do that by induction
- we wouldn't be trying to prove it by induction - but in general, P could be any family of statements
that's indexed by the natural numbers. And what we're going to suppose is that we
know two things. First of all, we know that P of zero is true. And second of all, for any N (N is a natural
number), if P N is true, then P N plus one is true. And if all of this is the case, then the principle
of induction says that P N is true for all N. So then P N is true for all N in the set of natural numbers. And as I say, that follows directly from the
way that we've defined the set of natural numbers. This. The two hypotheses of this theorem,
that P of zero is true - that's called the initial step - and secondly,
that for any N of P N is true, then P N plus one
is also true, and that's called the inductive step. So if we want to prove something by induction
- and I'm sure that most of you have done this before - I'll show you an example in a second - then
we just need to show that both of those two things are true. I like to visualise induction as like having
a set of dominoes that we're going to knock over. So there's lots of dominoes lined up on the
table. The line goes on forever. And then saying
P zero is true is like knocking over the first domino, and then the inductive step is like saying that we've placed the dominoes
so close together that when one of them falls over, it will always knock over the next one. So
then obviously when we knock over the first one, we're going to end up with them all falling
over. OK, so here's an example of what we can do
with this, so this is going to be a proposition. So that's something that we're proposing is
true, and we're going to then try and prove it. So the proposition is that for any N that's
a natural number, the sum of all of the integers from zero up to N,
is given by - and you probably know this formula - is given by a half N times N plus one. OK, so we prove that by induction. So in this
case the statement is, the statement P N, is that
this expression works for that N. So we're going to do a proof. So first of all, is P of zero true? Well yes it is, because
in the case N equals zero, there's nothing in this term on the left hand
side, it gives zero. And the right hand side is also zero when N is zero. So I'll say P of zero is true since for N
equals zero, the left hand side is equal to zero and the right hand side is also equal
to zero. OK, that ticks off the initial step, then
we're going to do the inductive step. So we're then going to suppose that P N is
true, and then we're going to think about P N plus one. P N plus one would be the statement that this
thing works with N replaced with N plus one. So we need to think about.... So I'm going
to say, then the sum from K is zero up to N plus one of K... well it's pretty obvious how to do this
so we're just going to pull out the final term
from that. So I'll write it as the sum from zero up to N of K, plus the final term, which
is the N plus one. And the reason that we do that is because
this sum, we know, is given by half N N plus one, because we're supposing that P N is true. So we're supposing we know this formula for
N. So this is equal to a half N N plus one, and then plus that final term N plus one. And I'm just going to point out in my writing
here, that I'm using the inductive step. This is usually using the inductive hypothesis.
So I'll say using the inductive hypothesis. And I like when I'm writing a proof to write
some kind of commentary like this. I tend to put it in brackets, often at the side of my working (although
in this case I'm trying to fit it all on one line) just to explain what I've done. OK, then we're basically there, because we
can just rearrange, we can factorise, that right hand side now You can write this as a half N plus one times
N plus two. And that is what we were trying to show, because
that is exactly this expression here with N replaced by N plus one. So we write the next line of the proof. I'm
going to say so P N plus one is also true. That's what we've just shown. And therefore,
by induction P N is true for all N. So then I conclude by saying by induction...
that doesn't look like induction so let me write that again... by induction P of N is
true for all N in the set of natural numbers. And
so that's the end of the proof. I'm going to draw a little square at the right
hand side, which is a way of indicating we have reached the end of the proof. People used to write QED here, but it's better
just to write a square. OK, so that's a pretty straightforward example.
And I want to mention two variants on induction. One of them is so easy that we're not going
to say anything more about it. And that's if the initial step is somewhere other than
zero. So if we didn't have P of zero being true
but say we had P of three being true, that would be like knocking over... well actually
it would be like knocking over the fourth domino, because I've started counting my dominoes
at zero... this is the confusing thing about having the
natural numbers start at zero... but obviously we could just start the sequence
somewhere else and we would then prove it for every N larger than that. So that follows directly. The second variant
that I want to say a bit more about is if, in the inductive step, sometimes it might be useful to use not just
that P held for the previous one, the previous N, which is what we did in this case - so here, I used that this sum worked for
P N when I was trying to prove it for N plus one - but sometimes it's useful if we can use some
previous cases as well, not just the immediately previous case. And that's called strong induction. So I'm
just going to say a bit about that now. So this is going to be another theorem, and
this is going to be strong induction. And I'm going to state it. A lot of it's going
to look almost exactly the same as in the previous one. So we're going to say let P of N be a family
of statements, again indexed by the natural numbers - let me just write those as N - and we're going
to suppose our two things. The first is that P of zero is true. And the
second - and this is the one that's going to be different - is that for any N, if all of the statements
P of zero, P of one, up to P of N, are true, Then P of N plus one is also true. So it's a slightly different inductive step.
If that's the case, then P of N is true for all
N. This also probably seems quite obvious, but
I'm going to prove it this time. I'm going to prove it by converting this back
to an instance of normal induction. Which is what we just talked about. Because this is quite a common thing that
you try to do in maths - to convert some new result into some previous result that you
already know - and don't do more work than you need to. So the way I'm going to do that in this case
is I'm going to define a new family of statements. So I'm going to define Q of N to be the statement - I'm going to put my
statement in inverted commas - that P of K is true for K equals zero, one, up to N. OK, and then I'm going to re express what
I know in terms of Q. So if you if you look at this Q of zero is actually just the same
thing as P of zero. So, what do we know? So we know, first of all, that Q of zero is true - that's
just this, restated in terms of Q - and then this inductive step now says, well, so this
P of zero up to P N are true, that is just Q N is true. And if that's the
case, then P N plus one is true, but if P N plus one is true as well as all the previous ones, then that
means that Q N plus one is true. So I can restate all of that thing as... well, let me just write it out. This is hopefully
quite obvious, I'm just trying to be very careful about the way I write it. So I write
this as for any N in the natural numbers, if Q
N is true, then Q N plus one is true. So I've just rewritten these - this statement
and this statement - in terms of Q. But now they are exactly of the form in the previous
theorem, in fact I'm going to go back to it, they're
exactly of the form that's written here, and that's why I tried to write them out quite
carefully/. And so then applying this theorem, that means that Q N is true for all N. So then here I'm going to say So, by induction. Q N is true for all N. And then if Q N is true for all N then obviously
that means that P N is true for all N. So I'll say hence P N is true for all N. OK. And so that concludes that proof, which is
maybe a bit more laboured than it really needed to be, but I was trying to spell it out quite
carefully. Let me give you an example of when we might
use strong induction. So let me give you another proposition. So this proposition is that every natural
number greater than one can be expressed as a product of one or more primes. So hopefully this is something that
you already know, but how do we go about proving that? We're going to prove it by induction. So we're going to try and prove that for each
N, it is true that it can be expressed as a product of one or more primes. So I'm
going to quite carefully set up the statement, so I'm going to let P of N be the statement that N can be expressed as a product of primes. Ooh, I seem to have said let twice. That should
have said proof at the start. So, well P of... well we're trying to show
that this works actually for N greater than or equal to two. The statement says it should
be for every N that's greater than one. So I'll say that
P of two... well that obviously holds because two is itself
a prime, which is a product of a prime. So P of two is true, since two is itself prime, and therefore is
a product of primes. Then I'm going to show that this works for the other N. So let's let N be bigger than two and we're
going to suppose that P of M holds for all the previous M, so for M less than N. OK, well, so now, so we're trying to show
the P N holds in this case. If N is itself prime, then it is already a
product of primes, so there's nothing really to do. So if N is prime then P N is true. If N is not prime, then it means that... well
by definition of it not being prime it must be the product of two smaller numbers, So if N is not prime then N is... let's call
them R and S... so we're going to say N is R times S for some
R and S, which are themselves natural numbers, and R and S are both less than N, and bigger
than one, and since they're less than N then the inductive
hypothesis means that P of R and S are true. So that means that R and S can be expressed
as products of primes. So then I write by the inductive hypothesis,
R and S can be expressed as products of primes. And hence so can N, because N was R times
s. And that means that P N holds. Or P N is true. I say holds or is true - they mean the same
thing. And so that proves the inductive step and therefore by strong induction, we have
shown it for every N. So I conclude by saying by strong induction P of N holds for all N. And that concludes
that proof. OK, so that's the end of this first video.
I'm just going to quickly summarise what we've done. So let me take you back. We've talked about what the national numbers
are. We've noticed that they can be added and multiplied,
and we've also noticed that they have an ordering. We've then looked at induction, we looked
at a simple example of an induction, and then we've looked at strong induction
and seen an example of using that, to prove that every natural number greater than one can be expressed
as a product of primes. OK, so in this second part of the lecture,
which should be a bit shorter, I'm going to use induction to do some things
that might be slightly different from how you've seen induction used in the past. So I'm going to prove some properties of the
natural numbers. The first one of those is going to relate to addition. And so the first thing I want to do is to
define addition. This will be a definition of addition on the natural numbers. And so I'm going to suppose that I know how
to add one - I know what that means - and then based on
that, define adding any other number. So we're going to define additions by the
rules that for any natural number M, two things
are going to hold. First of all, if we do M add zero, we get
M - so that's really telling us that zero is the additive identity - and secondly, for any N in the natural numbers,
if I want to do, M add N plus one, then I do it by doing M add N, and then add one. OK, so if you just think through that and
heopefully that will convince you that that actually tells you how to add on any natural
number. So, for instance, if I take N equals four
in that second rule, it tells me that in order to do M plus five, I do M plus four, plus
one. And then in order to do plus four it tells
me that I do that by doing plus three plus one. OK, and I can keep going back down. Eventually I get to the point where in order
to do M plus one I do M plus zero, which is M according to the first rule, add
one. OK, so I had to somehow know what add one means. OK, so what we're going to try and do now
is to use this definition to prove that addition is associative. So this is a proposition, and the proposition
is that addition is associative. Now that might or might not be a word that
you've come across before. What does it mean? So I'll say i.e., it means that if I take three natural numbers,
I'll call them X, Y and Z (usually I call my natural numbers M and N but in this case I've chosen to do X, Y and
Z) - you'll find that there's conventional letters that tend to get used for numbers
in different sets - so if I take three natural numbers, then to
be associative means that X add Y plus Z is the same as X plus Y plus Z. OK, so basically, it's saying that
the order of the brackets doesn't matter. And this is something that presumably you
take for granted in addition of natural numbers, but we want to try and prove it. And we're going to do that by induction. And
we're going to induct on Z, so I'll say we induct on Z. I'm going to say X and Y are completely arbitrary
natural numbers, and then first of all I'm going to try and
show that this is true when Z is zero, and then I'm going to assume that it's true
when Z is N then show that it's true when Z is N plus one. So for Z is zero, the left hand side of this
expression is X plus Y plus zero. And if we follow rule one from the definition
of addition up here, we know that Y plus zero is the same as Y. So that's X plus Y. And I'm going to make
a note at the side here of what I've just used because I'm trying to be quite careful. So using I from the definition. I'll write D E F N, that's shorthand for definition.
And then I'm trying to show that this is the right hand side of this expression here, which is, for the case Z equals zero, X plus
Y plus zero, but that is the same, that's again, just using this rule here, X
plus Y is the same as X plus Y plus zero. And that is the right hand side of this expression.
Actually I'm going to give this expression a name, I'm going to call it star, because I keep
referring back to it. So star holds for Z equals zero. OK, so now, we'll suppose star holds for Z
equals N, and then we'll think about Z equals N plus one. So then for Z equals N plus one, the left
hand side now is going to be X plus Y plus N plus one. I'm using brackets just to clarify which numbers
are which here. And so here I'm going to use the second rule for how to do addition to write this bit here
as Y plus N plus one. So this is the same as X plus Y plus N plus
one. OK, so that was using the second part of the
definition. And then I can use that again, because this
is now - the whole of the right hand side here - is X plus Y plus N, plus one. And so the same rule tells me that's the same
as doing X plus Y plus N, plus one. So this is X plus Y plus N, plus one. And that's using that same rule again. And now I'm in a position where I can use
my inductive hypothesis, because this bit here is now X plus Y plus N. This is exactly the form of this thing for
Z equals N, which we're assuming to be true. So now we can use the inductive hypothesis
and turn that around. So this is X plus Y plus N. And so this time we are using the inductive
hypothesis. And I'm getting a bit squished up here because
I'm trying to fit this onto the slide, which is going to happen quite a lot. We're nearly there now because this is now
of the form X plus Y plus N plus one. So if I now work backwards through this second
part of the definition of addition, then this is the same as X plus Y plus N plus one, and that is exactly the right hand side of
the thing we're trying to show - X plus Y plus Z, since Z is N plus one. So this is the right
hand side. So we've shown that star holds for Z is N
plus one. And therefore, by induction, it holds for
all Z. So by induction star holds for all Z in the national numbers,
and so we've shown that addition is associative. Which is great. This is actually a really important result,
because that means that I can now blindly apply this rule - it means I don't need to
write out my brackets when adding things together, without having to think about it. So we've
been quite careful in doing this. this is the kind of thing that I don't particularly
enjoy. I used to quite enjoy it, but I don't really enjoy doing it anymore. And if you're doing applied maths, you don't
tend to worry about proving every step like this. And even when you're doing pure maths you
don't, once you've decided that you're happy with
this result, you can then use it without needing to prove it again every time - that's kind of the point of doing a rigorous
proof - that we can now use this with confidence. OK. So let me prove and another property,
this time just of the natural numbers themselves. This is a proposition, and this is called
the well-ordering property of the national numbers. And this is a simple
statement. The statement is that every non-empty subset of the natural numbers has a least
element. So a subset I haven't defined yet, but a subset
of the natural numbers is some set of natural numbers, but maybe not all of them. Being non-empty
means that it contains at least one number. And then we're saying it has at least element.
If you remember that we said the national numbers have in ordering, so we know what it means to say that one of
them's smaller than the other ones. So this is saying that every non-empty subset
of the natural numbers has a smallest element - that would mean the same thing. That might seem like a pretty obvious property,
if you think about it, but it's not completely trivial. So if you
think about the set of integers, or the set of real numbers, they don't have this property. So we'd like to prove it. And we're going to do that using induction,
but we're going to combine induction this time with contradiction. So we're going to assume for a contradiction
- you're going to see this method of proof a
lot - so we're going to assume that this statement
is not true and then show that that leads to a contradiction, and that therefore it
must have been true. So if this is not true it means that there
must be some non-empty subset of the natural numbers that does not have at least element. So let's assume that S, which is the name
we'll give to that set, is a non empty subset of the natural numbers that does not have a least element. And then what I'm going to
do is to consider the complement of that, which I'll call S star - that's going to be the set of all natural
numbers that are not in S. So this notation - we'll see a bit more of shortly - this notation
here says this is the set composed of N which are in the natural numbers such that (the colon
means such that) N is not a member of the set S. And what I'm going to try to do is to show
that all natural numbers are in this set S star, because then that means that S is empty, which
contradicts the fact that we've said it's a non-empty subset. So that's what we're going to try and do.
And so we can try and use induction to show that every N is in S star. So first of all, I'm going to note that zero
is in S star because zero can't be in S, because if zero was in S, then it would be
the least element of S, since it's the least natural number. So it can't be in S. So I'll say zero is in
S star, since zero is not in S, else it would be the least element. OK, so that's the initial step - I've proved
that zero is in S star. And then I'm going to suppose - I'm going
to write it as if - zero, one, up to N ,are in S star, then, well then N plus one must also be in
S star because - well actually it's almost the same reason - if
N plus one were in S, then it would be the least element in S because all the other smaller natural numbers are
in S star and therefore not in S. So if zero up to N are in S star - in other
words, if zero up to N are not in S - then N plus one is not in S, else it would be the least element. So N plus one
is therefore in S star. By induction, in fact by strong induction,
every N in the national numbers is in S star. So by strong induction, N is in S star for all N in the natural numbers. Hence S is empty, which is a contradiction, so I'll
write, a contradiction. Some people, when they reach a contradiction,
will write some kind of symbol. A common one is a kind of double cross like this. Another one is a kind of lightning bolt kind
of thing. I tend to just write that it's a contradiction, and if I feel like it's not obvious what the
contradiction was, then I'll spell out what the contradiction is. OK, but that completes the proof. And that
means that the original statement, which we assumed not to be true, must have been true. OK, so that's another example of how we can
use induction, in this case as part of a larger proof by contradiction. In this case, I have not spelled out explicitly what the
family of statements P of N was. So that was on these lines here. The statement would have been N is a member
of S star, and here we were proving P of zero and then here we were proving the inductive
step. So you don't have to be really explicit about
what the P of N is as long as it's clear. This well ordering property of the natural
numbers is actually quite important, and in fact, it almost defines the natural numbers. So here we've used induction to prove it. You can actually work the other way around
and use just this property of the natural numbers to prove the principle of induction. You can look in the typed lecture notes if
you want to see that. So let me just summarise what I've done here. We gave a recursive definition of addition,
and then we saw how we could use induction to prove that addition is associative, which
is great. And then we've seen that we can use induction
to prove this well ordering property of the natural numbers.