We will encounter many definitions, theorems, and proofs throughout these notes.

A definition has nothing to do with something being true. It just tells us what a mathematical word means. A definition might define a type of object, or it might define a property. The definition about defines a property about linear equations.

You already know that a definition tells us what a word means because you’ve been using dictionaries for a very long time. But there are two very, very important differences between dictionary definitions and mathematical definitions. If you want to understand the material in these notes, it is vital that you understand these differences.

The first difference is that when mathematicians (in particular, your algebra professor) state a definition, they real ly mean it. They don’t mean that this is a good description of the majority of cases, but that there might be exceptions out there somewhere. This is not how dictionary definitions work. If you took two dictionaries and looked up an everyday concept, either a concrete one (like “table”) or an abstract one (like “justice”), would you expect the definitions to be identical? Probably not. Probably, in fact, you would expect to be able to find things in the world that satisfy one definition but not the other. Or to find something that you would want to call a “table” or “justice” but that didn’t really satisfy either definition^∗. Or to find something for which, even though there is a definition, people would disagree.

Now, compare this with what would happen if you took a mathematics book and looked up a definition of “even number.” Would you expect to be able to find an even number that did not satisfy the definition? Or an non-even number that did, nonetheless, satisfy the definition? Absolutely not. Exceptions simply don’t exist. It’s not like you could find a number so big that it could be even without being divisible by 2. If you took two textbooks, you might not expect the two definitions to be phrased in exactly the same way, but you would expect them to be logically equivalent. That is, you would expect that all and only the things that satisfy the first definition would also satisfy the second. So, that’s one difference: mathematical definitions mean exactly, exactly what they say. There are no exceptions, and different phrasings might exist but these must be logically equivalent.

The other difference, which is partly a consequence of the first, is that mathematical definitions are precise and operable in a way that dictionary definitions are not. This means that they contain some information that we can actually manipulate in an algebraic or logical argument. For instance, consider the following simple definition:

“Well, yes,” you’ll be thinking, “obviously.” In fact, though, this is probably not how your professor will write this definition. You’re more likely to see something like this:

You could be forgiven for thinking that this over-complicates things. But it has some advantages. The first is precision. We can see this by comparing with the kind of thing that students sometimes write when they try to define even. They tend to say things like “Even is when it’s divisible by 2.” Clearly that captures the key idea, but it isn’t very precise. For a start, what is “it”? Clearly “it” is supposed to be a number, but this number isn’t introduced properly. In contrast, the better definition tells us explicitly that we are dealing with a number and gives it a name, n. For another thing, the student definition contains the locution “is when.” This tends to sound clunky, in mathematics but also in other fields. In mathematics, if you find yourself writing “it” or “is when,” you should probably consider rephrasing.

The second advantage is operability. We can operate with the mathematical definition to prove things. The better definition gives us a way of capturing and manipulating even numbers because it states what divisibility means in algebraic terms. We could, for instance, use it to prove that any integer multiple of an even number must also be even, perhaps by writing something like this:

Suppose that n is an even number. Then (by definition) there is an integer k such that n = 2k. Now, let z be any integer and y = zn. Then y = z(2k). But we can rewrite this as y = 2(zk). Now zk is an integer, so y is even because it can be written in the required form.

We could have the same ideas if we were working with the imprecise student definition. But the better version gives us a leg-up for writing arguments like this by providing some notation. Moreover, we expect the precise definition to exclude all the numbers that are not even (for the number 3, there is no appropriate integer k). In this way, the definition of even number captures the notion of evenness in a reasonable way.

A final point here is that we do not “prove” definitions. We can’t, because there’s nothing to prove: definitions just capture conventions in which we all agree to use a word to mean exactly the same thing. A professor might, at some point, explain to you how a definition captures an intuitive idea, but this isn’t the same as proving it.

Whereas a definition states what we mean by a word describing a mathematical object or property, a theorem tells us about a relationship between two or more types of objects and properties; it assumes that we already know what those objects and properties are. Of course, if you don’t know the meanings of all the words and symbols in the statement of a theorem you will probably feel that you don’t understand the theorem. Notice, however, that even if you don’t understand a theorem, you should be able to recognize that it has a theorem-like structure of the form:

The bit that goes with the if is called the premise or the assumption or the hypothesis. The bit that goes with the then is called the conclusion. It’s actually not quite this simple in real life, because there are a few ways of phrasing theorems that don’t make the “if… then… ” structure so obvious.

Theorems tell us true things about relationships between concepts. Nevertheless, we need to go to the trouble of proving them. Sometimes we do this because theorems are far from obvious. Sometimes, though, theorems are pretty obviously true, and we do it for the more subtle reason that proving them allows us to see how they all fit together to form a coherent theory.

Once definitions are settled, theorems follow by logical necessity. For instance, once we have decided to define even numbers as numbers divisible by 2, we must conclude that any integer multiple of an even number is also even. We don’t have any choice about that kind of consequence.

We should say that although we’ve only used the term theorem, there are several words that sometimes get used instead. Some of these are proposition, lemma, claim, corol lary, and the apparently all-encompassing result. Lemma is usually used for a small theorem that will then be used to prove a bigger, more important one. Corol lary is used for a result that follows as a fairly immediate consequence of a big theorem. The other terms are more or less interchangeable (in our opinion).

Thinking about objects can allow us to link new statements to our existing knowledge. However, we can also work towards understanding statements by thinking about their logical structures. To do so, we need to pay attention to mathematical uses of logical language. We will start by looking more carefully at ways in which the word if is used in mathematics.

First, consider a statement “If A then B.” This is sometimes written as “A ⇒ B,” which is read out loud as “A implies B.” The use of an arrow makes it clearer that we can think of this statement as having a direction, which is important because we might have a situation in which A ⇒ B is a true statement but B ⇒ A is not. Sometimes both implications do hold, as in the case:

However, sometimes one is true but the other is not, as in the case:

These statements are actually somewhat imprecise, because we have not specified what type of object x is. You probably assumed that it must be an integer in the squaring case and a real number in the inequalities case, since that would make sense. But, to be clearer, we could write things like:

Doing so makes it easier to see why this particular statement is false: there are some real numbers that are less than 5 but not less than 2. But mathematicians sometimes omit such phrases when writing in note form or when the intended interpretation is obvious.

When they want to discuss both implications at once, mathematicians use a double-headed arrow meaning “is equivalent to,” or write “if and only if” or its abbreviation “iff.” So these are different ways of writing the same (true) statement about integers:

We have seen the phrase “if and only if” before, in our definitions. Here it is again:

Can you see how this definition “catches” the numbers that are even, and excludes those that are not?

One final thing to note about a statement of the form “A if and only if B” is that, if we want to prove it, we can take one of two approaches. We can either construct a proof in which all the lines are equivalent to each other, or prove the two statements A ⇒ B and B ⇒ A separately.

The uses of “if” and “ ⇒ ” sound straightforward when we are considering simple mathematical statements. But we would like to draw your attention to two potential sources of confusion.

First, some thought is necessary to sort out which of the “if” and the “only if” corresponds to which implication. You should think about this, perhaps by thinking about which one could replace the “implies” arrow in these two versions of the same (true) statement:

Second, it turns out that students do not always interpret “if” in a mathematical way in everyday life. In everyday conversation, we tend to speak rather imprecisely, relying on the context to help our listener make the interpretation we intend. For instance, imagine someone says to you,

You could reasonably infer from this that if you don’t clean the car then you can’t go out Friday night. Clearly that is what the speaker intends. And someone else could infer that if you were allowed out on Friday, they you must have cleaned the car. But, in fact, neither of these is logical ly equivalent to the original statement. Perhaps the easiest way to see this is to look at the logic in parallel with our simple statements about inequalities:

The second and third statements in each case are not logically the same as the first. Alternatively, you could think about the everyday situation, and see that the original statement says nothing at all about what happens if you don’t clean the car, so there would be no contradiction if you didn’t clean it but you were still allowed out. Technically, the person bargaining with you should really say:

Of course, no one talks like that. Which means that you might have less practice than you think accurately interpreting logical statements. Using logical language in a mathematically correct sense is not too hard, thought, because there are cases in which the intended natural language interpretation is the same as the mathematical one. Consider the statement:

No one hearing this would dream of inferring either of these:

But these inferences are analogous to those we looked at for the statement about cleaning the car. Make sure you can see how.

In the Sevilla case, the natural interpretation of the statement is the same as the mathematical one. We can also use it to illustrate a general point about logical equivalence of different implications. For any statement of the form A ⇒ B we can consider three related statements called its converse, inverse, and contrapositive. This is what each one means, using the Sevilla example for illustration.

This is what each one means using one of our simple mathematical example instead:

This should help you remember that if A ⇒ B is a true statement, then its contrapositive will also be true (in fact, they are logically equivalent), but its inverse and its converse might not be.

Finally, I should point out that your professor will be careful about uses of “if” and “if and only if” in theorems and proofs, but perhaps not so careful in definitions. In a definition, they might just write “if” instead of “if and only if.” This works for the same reason that everyday communication works: everyone knows that, in a definition, this is what is intended.

Next we want to discuss the phrases “for all” and “there exists.” These are called quantifiers, because they tell us how many of something we’re talking about. They are so common in mathematics that we have symbols for them: we use “∀” (the universal quantifier) to mean “for all” and “∃” (the existential quantifier) to mean “there exists.”

In simple statements, quantifiers are easy to think about. Here is a simple quantifier statement:

In this statement, we write ∀x ∈ ℤ to specify exactly which objects we are talking about. We could just write ∀x, and sometimes people do when it is obvious what kind of numbers (or other objects) a statement is about. But doing so could be ambiguous. In this case, the statement could just as well be about real or complex numbers, which raises issues of the truth or otherwise of the statement: “∀x ∈ ℤ, x² ≥ 0” is true, “∀x ∈ ℂ, x² ≥ 0” is not. So it is good practice to be specific.

More complicated quantified statements can be harder to think about. Here is a definition written in words and in an abbreviated form using the new symbol (which might be more naturally read as “for every” in this case):

Here is a simple quantified statement involving the existential quantifier:

This is a true statement, because when mathematicians say “there exist,” they mean “there exists at least one.” Here, there are two different integers x that satisfy the statement. In other cases, there might be hundreds. Students sometimes find it strange that we say “there exists” without specifying how many because, if we know exactly how many there are, it seems rude not to say so. However, advanced mathematics is at least partly about general relationships between concepts, rather than about finding “answers” as such. We can see other reasons why it makes sense to use “there exists” without extra specification if we look at another definition (again shown both in words and in an abbreviated form):

This definition gives us an agreed way of deciding whether a number is even or not. To make that decision, we do not care what the particular k is, we just care whether or not there is one. It also allows us to make general arguments about all even numbers. We might start by saying “Suppose n is even, so ∃k ∈ ℤ such that n = 2k.” In this case, we don’t want to specify what the k is because we want the ensuing argument to be general in the sense that it applies to any number that satisfies to the condition.

Some mathematical statements have more than one quantifier. The following definition (again with an abbreviated version) might be described as doubly quantified or as having two nested quantifiers:

When a statement has more than one quantifier, the order in which they appear is real ly important. In this case, the definition says, “for every x, there exists a d.” We should imagine taking a particular x value and finding an appropriate d (maybe depending on x). If we take a different x, we might need a different d (perhaps a smaller one, as in the right-had diagram below).

If the definition instead said “there exists a d for every x,” mathematicians would read that as meaning that we could select a single d (independent of x) that works for every x. That is not the same thing at all.

To check your understanding of this, consider the following two statements. One is true, and the other is false. Which is which?

It is normal to find this difficult, because everyday life would probably not distinguish between these two statements. Without even realizing it, we would make the interpretation that seems most realistic, disregarding logical correctness. Most students therefore have to concentrate for a while before they get the hang of reading what is literally there and making the mathematical correct interpretation.

Although we have written the theorems in the form “If… then …,” you might also see different phrasings. Here are some common ones:

These would all be interpreted to mean the same thing: the premise in each case is that the function is even, and the conclusion is that its derivative is odd. It might seem strange that we don’t just pick one form and stick to it but, sometimes, one version or another sounds more natural, so mathematicians like to have this flexibility.

You will also see theorems of different types. There are, for instance, existence theorems like this one:

Theorem: There exists a number x such that x³ = x.

One way to prove a theorem like this is just to produce an object that satisfies it: the number 1 would do, in this case. It’s not always that easy, but it’s important to recognize that it might be, because sometimes students tie themselves in knots doing complicated things when a simple answer would do.

There are also theorems about non-existence, like this one:

Theorem: There does not exist a largest prime number.

In fact, a bit of thought, non-existence theorems can be restated in our standard form. This one, for instance, could be written with a universal quantifier:

Theorem: For every prime number n there exists a prime number p such that p > n.

Then it could be rephrased into our initial form:

Theorem: If n is a prime number then there exists another prime number p such that p > n.

These rephrasing possibilities can be very useful when we want to start proving something: sometimes rewriting in a different way can give us different ideas about sensible things to try. However, the fact that we can often rephrase does not mean that you can be sloppy about your mathematical writing. Sloppy paraphrasing can easily change the logical meaning of a statement. Once you become fluent in using logical language in a mathematical way, you will find that you can switch forms without doing violence to the meaning. Until that point you should think carefully about logical precision.

One great thing about having precise meanings for logical terms is that it buys us a lot of mechanistic reasoning power. For instance, if we know that A ⇒ B and that B ⇒ C, then we can deduce that A ⇒ C. We can do this even if A, B, and C are about really complicated objects that we’ve never met before and we don’t understand. Similarly, if we would like to prove a statement of the form A ⇒ B, be we are not making much progress, we can remember that the contrapositive (not B ⇒ no A) is always equivalent to the original, and try proving that instead.

This is what we mean when we say that we can develop valuable understanding by looking at the logical structure of a statement. If we pay attention to constructions involving “if” or quantifier, we can make use of such regularities in our reasoning. This is (at least partly) what people mean when they talk about formal work: we can concentrate on the logical form of a sentence and temporarily ignore its meaningful content. We don’t have to ignore the meaning, of course, and for most of the above discussion you were probably thinking about meanings as well. But attending to logical form is vital for proper understanding. Some students are lax about this; when reading mathematics, they look mostly at the symbols, ignoring or glossing over the words. This can make their understanding faulty and their writing inacurate, because they mix up important quantifiers or implications. For instance, consider the following theorem:

Rolle’s Theorem: Suppose that f : [a, b] → ℝ is continuous on [a, b] and differentiable on (a, b) and that f(a) = f (b). Then ∃c ∈ (a, b) such that f^′(c) = 0.

It is quite common to see students make errors, writing things like this:

Rolle’s Theorem: Suppose that f : [a, b] → ℝ is continuous on [a, b] and differentiable on (a, b). Then f(a) = f(b) and ∃c ∈ (a, b) such that f^′(c) = 0.

We can see that these are different by looking at their logical forms: one of the premises in the correct version appears instead as part of the conclusion in the second (look carefully to make sure that you can see this). Clearly that must make a very important difference, so the incorrect version cannot possibly be logically equivalent to the correct version. Nonetheless, it might still be a valid theorem. In this case, however, it isn’t, which we can see by thinking in terms of examples. In the incorrect version, the premises introduce a function f that is defined on an interval and is continuous and differentiable on this interval. The conclusion claims that the function values are equal at the endpoints of the interval, but this cannot possibly follow in a valid way from the premises, because there are many functions and intervals that satisfy the premises but do not have this property. For example, f (x) = x² is continuous on [0, 2] and differentiable on (0, 2), but certainly isn’t the case that f(0) = f (2). We can see how a student might write the incorrect version in the first place, but someone who is thinking about the meaning of their writing should recognize such errors when rereading.

This brings us back to the idea that both logical form and example objects can contribute to mathematical understanding, though focusing on each has different advantages and disadvantages. If you look mainly at examples, you might feel that you understand, but you might fail to appreciate the full generality of a statement of find it difficult to see the logical structure of a whole course. If you look mainly at formal arguments, you might be able to see how everything fits together logically, but you might find yourself complaining that it is very abstract and that you don’t really understand what is going on. Your experience of these issues will probably vary from course to course, because some professor give lots of examples and draw lots of diagrams, whereas others give a much more formal presentation. If a professor’s approach does not match you preferred way of developing understanding, you might find it useful to strengthen your understanding of the links between the example objects and the formal work.

You have constructing mathematical proofs for many years. For instance, to do the calculations needed to prove that the solutions to the equation x² − 20x + 10 = 0 are 10+310 and 10−310, you would write something like this:

This calculation uses methods that everyone agrees are valid, so it captures everything we need for a proof that the solutions really are as claimed. To make it look more like and upper-level proof, we could rewrite it like this:

Claim: If x² − 20x + 10 = 0 then x=10+310 or x=10−310.

Proof: Suppose that x² − 20x + 10 = 0. Then, using the quadratic formula,

This version explicitly states the claim, begins with the premise (“Suppose that x² − 20x + 2 = 0”), and contains few words to justify those steps that are more sophisticated or less obvious.

My point is that there is nothing inherently mysterious about proofs. It is certainly true that most high school mathematics is not presented in this way, but it’s also true that most of it could be. We say this because, in upper-level courses, lots of the mathematics you meet will be presented in this form; these lecture notes will be full of theorems and proofs. This might seem rather an abrupt change, and some students get the idea that proof writing is a mysterious dark art to which only the very privileged have access. It isn’t. In cases like the one above, all it really involves is writing in a more mathematically professional way – writing less like a student and more like a textbook, if you like.

This is not to belittle the genuine difficulties that undergraduate students face when handling proofs. Obviously the example above is simple one, and the proofs you are asked to understand and construct in upper-level courses will often (though not always) be much harder. It might take you a while to get used to digesting mathematics presented in this way, and to writing your own mathematics more professionally. But there is no reason to think you won’t manage it, and this section discusses some things you could pay attention to in order to get used to it quickly.

One thing you’ll often asked to do is to prove that a mathematical object satisfies a definition. The question won’t be phrased like that, though. It will just say something like, “Prove that the set (2, 5) is open.” You will have to interpret this to mean “Prove that the set (2, 5) satisfies the definition of open set,” and review the definition of open set to make sure you are clear about what this involves. That sounds simple, but We have often seen students who, faced with an instruction like “Prove that the set (2, 5) is open,” don’t know what to do. If you don’t know how to start on any proof problem, your first thought should often be, what does the definition say?

We have seen the relevant definition, which says:

How should we write a proof that (2, 5) is an open set? Often the best advice is to follow the structure of the definition itself. We want to prove that (2, 5) is open, so we want to show that for every x ∈ (2, 5) there exists d > 0 such that (x − d, x + d) ⊆ (2, 5). When we want to show something is true for every x in some set, we usually start our proof by introducing one, like this:

Here, arbitrary means that we are taking any old x, not some specific one or one with special properties. It is not necessary to write this – lots of people would just write “Let x ∈ (2, 5)” – but it does emphasize that the ensuing argument will work for any x in the set.

Now we need to show the existence of an appropriate d. The simplest way to show the existence of something is to produce one. In this case, we need to produce a d that will work for our x. This d will depend on x, and one way to do it is to pick d to be the minimum of the two distances 5-x and x−2 (think about why). So we might write the rest of our proof like this:

Notice that this proof reflect the order and structure of the definition. We are showing something for all x, so we start with an arbitrary one. We are showing that for this x, an appropriate d exists, so we produce one. Because of this, the structure of the proof will be obvious to a mathematician, so you don’t really need to write the line “So ∀x ∈ (2, 5) …, but you might find it helpful for your own thinking.

Some people tend to include diagrams along with proofs like this, and some don’t. That’s because diagrams can be illuminating, but they are not necessary, and they are not a substitute for writing a proof out properly (diagrams are not proofs); mathematicians (in particular you algebra and calculus professors) want to see a written argument that is clearly linked to the appropriate definition.

Another standard proof type is known as direct proof. In a direct proof we start by assuming that the premise(s) hold and move, via a sequence of valid manipulations or logical deductions, to the desired conclusion. Here are some theorems for which we’ve already studied a direct proof:

Stop and think for a moment here. Can you write out proofs of these statements without looking? If you can’t do it immediately, can you remember the gist of how we proceed in each case and reconstruct the rest? If you give yourself a minute for each one, we bet you can remember more than you would initially have thought. Students often have too little faith in their own ability to recall mathematical ideas and reconstitute arguments around them.

One important thing to note is that direct describes the eventual proof we write, it does not necessarily describe the process of constructing the proof. You might be able to write down the premises and just follow you nose to a proof, but is more likely that you’ll have to try out some of the things like: write everything in terms of definitions, think about some examples, maybe draw a diagram, and so on. You should then, however, work out how to write your final proof in a way that makes its logical structure clear for a reader. It is probably a good idea to treat this writing as a separate task, one that is worthy of your attention over and above simply getting to an answer or a proof.

A second thing to note is that direct proofs can have somewhat more complicated structures within them. The most obvious such structure occurs in a proof by cases, which means what it sounds like it means: we divide up the cases we’re dealing with into sensible groups and work with each one separately within the main proof. Consider the following theorem:

Of course, we need to define the symbols that appear in the statement.

The first definition gives the meaning to max{x, y} as “choose the largest number between x and y”, and the second definition is just the usual absolute value function. The theorem states that max can be expressed in terms of the absolute value function. In order to prove the theorem, you need to reinterpret it as follows:

Theorem: For every x, y ∈ ℝ, the expression x+y+|x−y|2 satisfies the definition of max{x, y}.

Notice that the definition of max{x, y} is given in a piece-wise format, where two cases are obvious: x ≥ y and y > x. The absolute value function is defined in a piece-wise format as well (and probably it is the first time you see it written formally in this way). This should hint you into considering a proof by cases. Before reading the proof below, you should try to come up with one by yourself.

Proof: Case 1: Suppose that x ≥ y. Then x - y ≥ 0 and, thus, by the definition of the absolute value function, |x - y | = x - y. So,

Case 2: Suppose that x < y. Then x - y < 0 and, thus, by the definition of the absolute value function, |x - y| = -(x - y) = y - x. So,

Putting both cases together, we have that for all x, y ∈ ℝ,

Therefore, x+y+|x−y|2 satisfies the definition of max{x, y}.

So when should you consider a proof by cases? Sometimes you will find that you have to. In this illustration, for instance, we don’t have much choice; the max{x, y} values are different depending on whether x ≥ y or x < y, so we have to handle theses cases separately. In other situations, it might not be necessary to use a proof by cases, but it might be convenient anyway because there is some sort of natural split, perhaps between positive and negative numbers (like in the definition of the absolute value function), or between odd and even ones. Finally, it might be worth starting a proof by cases if you think that you can construct an argument for some of the objects to which the theorem applies but not for others. A start is better than nothing and, once you’ve got an argument written down for one case, you might find that reflecting on it gives you ideas about how to continue.

One final tip is that, if you have produced a proof by cases, or if you’re looking at one produced by someone else, it might be a good idea to ask whether the number of cases could be reduced. You don’t have to do this, of course – if your proof is valid as it is, that’s fine. But remember that mathematicians also value elegance, and brevity contributes to elegance so it’s a worthwhile aim.

The next type of proof we want to talk about is proof by contradiction. This is a type of indirect proof, so called because we do not proceed directly from the premises to the conclusion. Instead, we make a temporary assumption that our desired conclusion (or some part of it) is false, and we show that this leads us to a contradiction. From this we can deduce that the temporary assumption must have been wrong, and thus that the desired conclusion is true. This sounds rather convoluted, but you’re accustomed to making this kind of argument informally in everyday life. Here’s a simple case:

Here you are implicitly using a proof by contradiction. The temporary assumption is that Daniel was in Vicálvaro. Your argument says that if we make that assumption, then we can deduce that he wasn’t in Alcorcón (if you like, this uses the “theorem” that people can’t be in two places at the same time). But this is contradicted by the fact that you saw him in Alcorcón. So the assumption that he was in Vicálvaro must have been wrong.

Next, we will look at a mathematical example, which involves the definition of rational number. The notation ℚ denotes the set of all rational numbers and ℤ denotes the set of integers. We introduce this definition here:

The theorem and proof below use the symbol ̸∈ to mean “is not an element of,” and in this case y ̸∈ ℚ means that y is an irrational number. The theorem and proof both implicitly assumes that all the numbers we are working with are real (this is common in early work with rational and irrational numbers). As with any theorem and proof, you should read everything carefully, checking that you understand what is going on in each step.

Then

So ∀k ∈ ℕ, P (k) ⇒ P (k + 1). Hence, by mathematical induction, P (n) is true ∀n ∈ ℕ.

There are a couple of things to notice about this. First, the proof contains only a few words, but these help to make the structure clear. Second, all the algebra is in a single chain of equalities that starts with the left-hand side of the statement of P (k + 1) and ends with the right-hand side. You might like to think about why it makes sense to do the manipulations in this order, given that we know what we’re going for. You might also like to think about why the last expression in the chain is not necessary but might be useful for a reader who wants to link the proof back to the theorem.

Confusion does tend to arise with proof by induction because there are lots of things to think about. We find that students are confused most often by the point which we write, “Assume that P (k) is true.” Students often read this and think, “But that’s what we want to prove, how come we’re allowed to assume it?” In fact, at that stage of the proof, we are not proving that P (k) is true, we are proving that P (k) ⇒ P (k + 1). Make sure you can see the difference. Also, students sometimes confuse themselves, usually because they have allowed ambiguities to creep into their writing by using the word “it” in phrases like “so it is true for n.” There are many possible candidates for the meaning of “it” in a typical proof by induction, so you should be more specific. Writing “So P (n) is true” is one way to do that. (Notice that the proof above does not include the word “it” – we are very specific about what we have deduced at each stage.)

So when should you use proof by induction? In some cases this will be obvious, because you are likely to have a section about it in at least one course. Also you will come across cases in which you want to prove that something is true for all n ∈ ℕ, which is a giveaway that induction is worth a try. Be aware, however, that problems for which induction is useful can vary quite a bit. First, there is no particular reason for a proof by induction to start at n = 1. You might be asked to prove that something is true for every n ∈ ℕ such that n > 4, for instance. In that case, you can just make P (5) your base case and proceed as before, except that at some point, perhaps in the induction step (the point in the proof when you apply the assumption that P (k) is true, referred to as the induction hypothesis), you will find that you need n > 4 to justify some manipulation you want to make. Second, while some of the first problems you meet will involve working with a sum, proof by induction is useful for many other types of problem. All we really need is a situation in which we have infinitely many statements that can be listed in the order of the natural numbers, which can happen in all sorts of ways. For instance, consider these tasks:

For the first task, we would write

Then we would prove directly that P (11) is true, that is, that 2¹¹ > 11³. Then we would work out how to prove that if k > 10 and 2^k > k³, then 2^k+1 > (k + 1)³.

For the second task, we would write

Then we would prove directly that P (1) is true, that is, that 5³ + 2² is divisible by 3. Then we would work out how to prove that if 5^3k + 2^k+1 is divisible by 3, then 5^3(k+1) + 2^(k+1)+1 is divisible by 3. Notice, in this case, that the statement P (k) is not just “5^3k + 2^k+1.” In fact, 5^3k + 2^k+1 isn’t a statement at all – we couldn’t prove it because it’s just an expression (for any particular k it is a number; you can’t “prove” a number, and it makes no sense to say that one number implies another). The statement is “5^3k + 2^k+1 is divisible by 3.”

In our experience, starting out with a clear statement of P (n) often makes the difference between success and failure in constructing a proof by induction, especially when dealing with a new type of problem. This isn’t that surprising, of course – before you start any problem, you should always make sure that you are clear about what you are trying to do. In any case, you won’t always be told what method to use, so you should be on the lookout for less familiar cases like these, and you should train yourself to notice when proof by induction might be useful.

Earlier we said that a student should never sit in from of a problem and think “I don’t know what to do.” There are always things to try and, to be a good student, you must be willing to try them. In fact, you must be willing to try things that turn out not to work. In our experience, students are sometimes unwilling to do this, for three main reasons.

First, some students dislike the insecurity of not knowing exactly what to do. It makes them nervous. They want to know in advance what is going to work, and sometimes they ask for a teacher’s assurance about this (“Is this the right way to do it”). The problem with seeking such assurance all the time is that you never find out what you could have done if you’d had a go, which means that you never get any more confident, which means that you end up in a vicious circle, having to ask for support all the time.

Second, some students do not want to waste time. We understand this – obviously no one wants to spend ages on one thing, especially when there are so many interesting things to do at university. But it is a big mistake to think that trying something that turns out not to work is a waste of time. Time spent learning is never wasted. If you try a method that doesn’t work then, provided you are thoughtful about it, you learn why it doesn’t work, which means you know something new about the applicability of the method. And you might gain some insight about the problem so that you have a better idea about what to try next. Of course, it is a mistake to keep plugging away at a method that clearly isn’t working – research shows that good problem solvers stop frequently to re-evaluate whether their current approach seems to be getting them anywhere. But it’s an even bigger mistake not to start.

Third, some students do not want to mess up their paper. They want to know that once they begin writing, they will be able to carry on writing and arrive at a nice, neat, correct solution. If this applies to you, then we’re afraid you’ll have to get over it. Real mathematical thinking is not tidy. It is full of false starts and partial attempts and realizations that what does not seem to be working just here would, in fact, form a useful part of a solution if put together with something that failed then minutes ago, or yesterday, or last week. It is very important to embrace this if you want to keep improving as a mathematical problem solver. You need to get partial solution attempts on paper for the simple, practical reason that your brain cannot handle many things at once. You have an enormous amount of knowledge stored in what is known as you long-term memory, but your working memory, where you actually do the new thinking, has a seriously limited capacity. It will not be big enough to hold all the information about a complicated mathematical problem while simultaneously working out how to solve it. When you write down definitions or theorems or calculations that might help you solve a problem or construct a proof, you are using the paper to supplement your cognitive powers by, in effect, extending the capacity of your working memory. So don’t be worried about writing things that are wrong or that turn out not to be useful. You can always write up a neat version of your solution or proof later.

Your professors will explain proofs that are long and logically complicated. They will also explain proofs that rely on some really clever insight. Sometimes they will explain proofs that are long and logically complicated and that rely on some really clever insight. This tends to worry students. They think, “Well, okay, I can see how that works, but I would never have thought of it.” This makes them wonder whether they’re good enough at mathematics. But you shouldn’t worry, because you’re not supposed to be able to reinvent the whole of modern mathematics by having all the original ideas yourself. Even a mathematics PhD student wouldn’t be expected to have many totally original insights. As an undergraduate, when faced with a poof like this, your job is to appreciate the clever insight, to understand why it works, to think about how modifications of it might work in slightly different circumstances, and to relate it to ideas used elsewhere in the course or in your major. Te reassure you further, here is a list of things the you will be expected to do.

First, you will be expected to do routine mathematical calculations much like those you have seen in lower-level mathematics. As we said at the beginning of this introduction, you should be prepared for these calculations to be longer and more involved that those you have experienced before, and you should be prepared to have to adapt the calculation procedure if a step in it not valid for a new case.

Second, you will be expected to adapt proofs that you have seen to closely related cases. For instance:

In such cases, you will often be able to treat the proof you have seen like a template, and change some numbers appropriately. However, to reiterate one of the main points of this introduction, you shouldn’t do this thoughtlessly – you should make sure that each step in the proof really does work for the new cases, and be ready to make minor adjustments if it doesn’t. It is important to be careful in cases where some number might be zero, for instance, or when dividing both sides of an inequality by a number that might be negative.

Third, you will be expected to adapt proofs you have seen to cases that are related, but not so closely. For instance:

In cases like these, the proof you have seen will certainly be helpful, but you will not be able to treat like a template. You might be able to construct a proof that is very similar in its basic structure, but you will have to think fuqrther to work out exactly what needs changing.

Fourth, you will be expected to show that definitions are satisfied. You will sometimes be expected to do this with definitions you have not seen before, if your professor thinks that they are sufficiently straightforward.

Fifth, you will be expected to construct proofs of theorems for which you haven’t seen a closely related model, or to solve problems for which you haven’t seen your professor solve in class. As we’ve said, the biggest mistake you could make here would be to sit around thinking “We haven’t been shown how to do this.” No one will ask you to do things that are completely beyond you.

Sixth and finally, on an exam you might be asked to solve some challenging problems. Sometimes a question might lead you through a solution in steps, or might offer a fairly big hit to help you with a key idea or useful trick. Sometimes it might just ask outright, which means you’ll have to be able to remember the key ideas or useful tricks yourself and come up with the rest. To do so you will need to have effectively read and understood the material in your lecture notes.

By linear equations in the unknowns or variables x1, x2, …, x_n we mean an equation that can be written in the following standard form:

where a₁, a₂, …, a_n, b are scalars. The scalar a_k is called the coefficient of x_k and b is called the independent term of the equation.

A solution of the linear equation (1.1) is a list of scalars (s₁, s₂, …, s_n) with the property that the following statement (obtained by substituting each si for xi in the equation) is true:

This set of values is then said to satisfy the equation.

The set of all such solutions is called solution set or general solution, or, simply, the solution of the equation.

The above notions implicitly assume that there is an ordering of the variables. If the number of variables is small, then, in order to avoid subscripts, we will usually use the variables x, y, as ordered to denote two unknowns, x, y, z, as ordered, to denote three unknowns, x, y, z, t, as ordered, to denote four unknowns, and x, y, z, s, t, as ordered, to denote five unknowns.

At this point, your algebra professor expects you to have carefully and thoroughly read the introduction section of these notes.

The solutions of degenerate equations are described in the following theorem.

Proof. We begin by proving the first statement. Let (s₁, s₂, …, s_n) be any list of scalars.

Suppose that b ≠ 0. Substituting x_i = s_i in the equation we obtain:

This is not a true statement since b ≠ 0. Hence no list of scalars is a solution.

Now we prove the second statement. Suppose b = 0. Substituting (s₁, s₂, …, s_n) in the equation we obtain:

which is a true statement. Thus every list of scalars is a solution, as claimed.

We now consider a system of m linear equations, say, L₁, L₂, …, L_m, in the n unknowns x₁, x₂, …, x_n which can be put in the standard form:

where the a_ij, b_i are constants.

A solution (or particular solution) of the above system is a list of scalars (s₁, s₂, …, s_n) which is simultaneously a solution of all the equations of the system. The set of all such solutions is called the solution set or the general solution of the system.

Systems of linear equations in the same unknowns are said to be equivalent if the systems have the same solution set. One way of producing a system which is equivalent to a given system, with linear equations L₁, L₂, …, L_m, is by applying a sequence of the following three basic operations called elementary operations:

Roughly speaking, the simplest equivalent version of a system is obtained using the elementary operations as follows. Use the x₁ term in the first equation of a system to eliminate the x₁ terms in the other equations. Then use the x₂ term in the second equation to eliminate the x₂ terms in the other equations, and so on, until you finally obtain the least amount of variables in common among the equations. The following example illustrates this strategy. Make sure to understand that we replace x₁, x₂, x₃ with x, y, z.

Suppose that you start with the system of equation (1.2) and use elementary operations to obtain a simpler equivalent version such that the equations have the least amount of variables in common. Then the first variable with non zero coefficient in each equation is called leading variable and the variables that are not leading variables are called free variables.

Recall from the beginning of this chapter that we have implicitly assumed that there is an ordering of the variables. Moreover, there may be more than one simpler system equivalent to (1.2). For this reason, we impose some additional requirements for writing a simpler equivalent version of (1.2). First, we will require that the equations should be rearranged so that the leading variables are order not only horizontally from left to right but also vertically from top to bottom. This can be accomplished by interchanging the necessary equations (recall that interchanging equations is an elementary operation). Second, we will require that the coefficient of each leading variable is 1^†. This is possible by rescaling the necessary equations. These two additional conditions ensure that the resulting simpler equivalent system is the simplest one, independently of the sequence of elementary operations that you use to arrive at it.

This notion of simplest equivalent system will be, in our opinion, the most useful tool at your disposal to develop and understand the material in this course. We will illustrate how to obtain such simplest equivalent system in the following examples.

Before continuing on to the next example, we need to discuss free variables further. Suppose that after reducing (1.2) to its simplest equivalent version, you find that all of its degenerate equations (if any) are of the form 0 x₁ + 0 x₂ + … + 0x_n = 0, and that at least one of its variables is a free variable. Then the system has infinite number of solutions since each of the free variables may be assigned any real number. The general solution of the system is obtained as follows. Once the system has been reduced to its simplest form, arbitrary values, called parameters, are assigned to the free variables, and the non free variables can be solved in terms of these parameters.

We finish this section by answering two fundamental questions about systems of linear equations:

The answer to these questions are stated as a theorem.

Proof. Given any system of linear equations, we apply elementary operations to reduce it to its simplest equivalent form. After this is done, we may get one of the following cases:

No other cases are possible, which proves the theorem.

In light of Theorem 1.2, systems of linear equations can be classified according to the existence of solutions. A system is said to be consistent if it has at least one solution, and is said to be inconsistent if it has no solution.

A matrix is a rectangular array of numbers:

Such matrix may be denoted by A = (a_ij). Note that the element a_ij, called the (i, j)-entry, appears in the i-th row and the j-th column. A matrix with m rows and n columns is called and m × n matrix.

The first non zero entry of a row is called its leading entry. A row whose all of its entries consists of zeros has no leading entries.

Just like with systems of equations, we can operate with the rows of a matrix by applying the following three basic operations.

A matrix A is said to be row equivalent to a matrix B, written A ∼ B, if B can be obtained from A by applying a finite sequence of elementary row operations.

Any non zero matrix is row equivalent to more than one matrix in echelon form that can be obtained by using different sequences of row operations. However, the reduced echelon form one obtains from a matrix is unique, independently of the row operations used to obtain it. We state this as a theorem without proof.

When row operations on a matrix produce an echelon form, further row operations to obtain the reduced echelon form do not change the positions of the leading entries. Since the reduced echelon form is unique, the leading entries are always in the same positions in any echelon form obtained from a given matrix. These leading entries correspond to leading 1’s in the reduced echelon form.

Heuristically, pivot positions are non zero entries of a matrix that are used to create zeros as needed via elementary row operations to obtain a row reduced echelon form.

Matrices will usually be denoted by capital letters A, B, … Two matrices A and B are equal, written A = B, if they have the same size, that is, the same number of rows and columns, and if the corresponding elements are equal. Thus the equality of two m × n matrices is equivalent to a system of mn equalities, one for each pair of elements. For instance, the statement

is equivalent to the following system of equations:

The solution of the system is x = 2, y = 1, z = 3, w = -1. (Do not just accept that these are the answers. Try to solve the system by yourself.)

A matrix with one row is also referred to as a row matrix, and with one column as a column vector. In particular, a scalar can be viewed as a 1 × 1 matrix.

Let A = (a_ij) and B = (bij) be two matrices with the same size, say, m × n matrices. The sum of A and B, written A + B, is obtained by adding the corresponding entries:

or, more compactly, A + B = (a_ij + bij).

The product of a matrix A = (a_ij ) by a scalar k, written kA, is the matrix obtained by multiplying each entry of A by k: kA = (k aij). We also define -A = (−1) A and A − B = A + (−B).

The m × n matrix whose entries are all zeros is called the zero matrix. We usually write the zero matrix as 0 and its size is usually understood from context. The zero matrix is similar to the scalar 0. For any matrix A, A + 0 = 0 + A = A.

Basic properties of matrices under the operations of matrix addition and scalar multiplication follow.

Proof. We only prove the first property here. The rest are left as an exercise for the reader. Let A = (a_ij), B = (bij), and C = (cij) be matrices of the same size. Then

There are several ways to define matrix-vector multiplication. You have probably seen one way in high school. Nevertheless, we choose the following definition because it is the most convenient for developing the theoretical ideas throughout the course. It should not be difficult for you verify that the definition you learned in high school is equivalent to the one we present here.

In words, the product of a matrix A and a column vector x is the column vector that is equal to the weighted sum of the columns of A using the entries x as weights. Note that Ax is defined only if the number of columns of A equals the number of entries in x.

We take this opportunity to give this type of weighted sum a special name. Given vectors v₁, v₂, …, v_p in ℝⁿ and given scalars c₁, c₂, …, c_p, the vector y ∈ ℝⁿ defined by

is called a linear combination of v₁, v₂, …, v_p with weights c₁, c₂, …, c_p.

The properties of the matrix-vector multiplication in the next theorem are important and will be used throughout the course.

Proof. Let ui and vi be the i-th entries of u and v, respectively. To prove the first statement, use the definition of matrix-vector multiplication to compute A(u + v):

The proof of the second statement is left as an exercise for the reader.

You have certainly seen how to multiply matrices in high school. Nevertheless, such a definition is not very useful for theoretical purposes. We now give an equivalent abstract definition of matrix multiplication.

It is possible to find a (less abstract) representation of AB in terms of matrix-vector multiplication. We provide this representation in the following theorem.

Proof. Following the definition of AB, let x be an arbitrary vector in ℝⁿ. Let

Then,

This is true for every choice of x and each product A b_i is uniquely determined. This proves the theorem.

The following theorem lists the standard properties of matrix multiplication. We note that I_m denotes the unique m × m, called the identity matrix, such that I_m x = x for all x in ℝⁿ. The identity matrix has the following representation:

Proof. Let C = [c₁ … c_p]. By Theorem 1.6,

By the definition of matrix multiplication, A (B x) = (A B) x for all x, so

The rest of the properties are left for the reader to prove.

The left-to-right order in matrix products is critical because AB and BA are usually not the same. On one hand, the sizes of A and B are such that AB is well defined but BA may not be even possible to compute. For instance, if A is a 3 × 5 matrix and B is a 5 × 1 matrix, then we can compute AB because the number of columns of A is equal to the number of rows of B, but it is not possible to compute BA because the number of columns of B is not equal to the number of rows of A. on the other hand, the columns of AB are linear combinations of the columns of A, whereas the columns of BA are constructed from the columns of B. If AB = BA, we say that A and B commute with one another.

Every now and then we need to compute a particular entry of the product AB without computing the whole matrix product. In this case, we do so by recalling the matrix multiplication rule you learned in high school (which can be deduced from Theorem 1.6).

Given an m × n matrix A = (a_ij), the transpose of A, denoted by A^⊤, is the n × m matrix A⊤=(aij⊤), where aij⊤=aji. That is, A^⊤ is obtained by changing the columns of A into columns, or, equivalently, by changing the rows of A into columns. So, if we write A = [a₁ … a_n], then

Proof. We only prove the last statement. The rest are left for the reader as exercises. First, observe that

On the other hand,

which shows that the (i, j)-entry of (AB)^⊤ is equal to the corresponding entry of B^⊤A^⊤. Therefore, (AB)^⊤ = B^⊤A^⊤.

Consider again a system of m linear equations and n unknowns:

We can interpret (1.3) the equations resulting from considering two equal column vectors:

Then, L_i is obtained by setting the i-th entry of the vector on the left side equal to the i-th entry of the vector on the right side. We can also operate on the left-hand side vector as follows: