A GUIDE TO PROOFS IN LINEAR ALGEBRA

1 A GUIDE TO PROOFS IN LINEAR ALGEBRAby Curtis Paul WHAT IS A proof ? What is a proof and why do we care? Previously in your mathematical life you have mostly focused on computation. You were not concerned with whether or not things were true but with whether you got the right answer. It is not uncommon for students to say, I know the answer. Why do I need to understand the steps? There are a number of responses to this. How do you know your answer is correct? How can you convince someone else your answer is correct? If you are given a harder problem to which you don t know the answer, how are you going to approach it? proof addresses these concerns. A proof is a sequence of statements justified by axioms, theorems, definitions, and logical deductions, which lead to a conclusion. Your first introduction to proof was probably in geometry, where PROOFS were done in two column form. This forced you to make a series of statements, justifying each as it was made.

2 This is a bit clunky. We want to have the same content, but without noting every trivial detail. A proof should read naturally. How much detail should we give? it depends on the mathematical background of the writer and the reader. A professional mathematician will need fewer details to understand the argument than will a beginning student. in both cases, though, the proof should be as clear and concise as possible. The process of writing a proof forces us to clearly understand the ideas involved. In formulating our thoughts in such a way as to explain the ideas to others, we clarify the ideas to ourselves. This is akin to what happens when we teach someone else. This process shows us where we have gaps in our understanding. This helps us to see the structure behind what we re trying to show. Mathematics is very much about structure. When we see a new statement, when we re given a new problem, when we try to write a new proof , we try to see how everything fits into this structure.

3 What do the words mean? What kinds of objects are we talking about? What do we know about such kinds of objects? How do they relate? Developing the ability to write good PROOFS takes time and practice. Here s an example from an actual assignment of how wrong it can go. Exercise: If u, v, and w are vectors such that u + v + w = 0, prove that span{u,v} = span{v,w} Here was the student s argument: The only way this would not be true is if (u,v) and (v,w) spanned different things. Since u + v = -w, there can be no dimension Wn in W that does not have a corresponding component in either -Un or -Vn or some combination of the two that can span the same dimension the same way. There are a number of things wrong with this. The use of the word dimension is nonsensical. What does n refer to? What does Wn mean? What is a corresponding component? What is -Un or -Vn or some combination of the two? What does the phrase span the same dimension the same way mean?

4 Virtually nothing in this statement is understandable. Does the student at least have the right idea behind the argument? I don t know, but this is a long way from clearly showing the reader why the statement is true. This GUIDE is not a textbook. It will contain some definitions and some theorems, but it focuses on how to think about LINEAR ALGEBRA and how to put these thoughts into clear statements. No book, no teacher, no class can magically give you abilities. Skills are earned through practice and hard work. The assisted PROOFS in this GUIDE will help you develop your skills, but it is imperative that you write many PROOFS and rewrite those PROOFS and rewrite those PROOFS . Read PROOFS . Share PROOFS . Discuss them. Argue them. Don t be afraid to be wrong. Be open to criticism. Critique yourself. If your peers don t understand your arguments, figure out why. If you don t understand your peers arguments, figure out why. The theme, which I will restate time and again, is that writing a strong proof is a matter of clear thought and hard work.

5 From the beginning, invest time and energy in understanding the ideas and learning to express them well. There is no substitute for hard work. Above, we noted that a proof is a sequence of statements justified by axioms, theorems, definitions, and logical deductions, which lead to a conclusion. Let s look at these. AXIOMS, DEFINITIONS, and THEOREMS Axioms are the statements in mathematics which we accept without proof . Every proof ultimately falls back to these beginning statements. There are very interesting questions about which statements we should start with in mathematics and what the consequences of so doing are. Mathematicians in the late 19th and early 20th centuries expended a great deal of thought and effort into this. Looking back to these statements, deciding how to choose them, and studying the consequences of doing so is beyond the scope of the LINEAR ALGEBRA course, but you are encouraged to look into the subject. Mathematics is the structure which results from the consequences of our axioms.

6 Our job is to understand parts of this structure. To grapple with mathematics, we have to be able to refer to pieces of it and ask how it all fits together. Definitions focus our questions on certain objects or sets or relationships in mathematics. In general, the broader a definition, the more parts of mathematics it applies to, and the less sharp the theorems about it can be. The more restrictive a definition, the fewer parts of mathematics it applies to, and the sharper the theorems can be. Possibly the most important aspect of writing PROOFS is to understand the definitions of the words we are using. Often in beginning LINEAR ALGEBRA , writing out the definitions involved in our statement is half the battle. When we talk about vector spaces, dimensions, bases, and so on, we have to be absolutely clear about what we are referring to. Theorems are the statements in mathematics which we know to be true. Typically, we reserve the word for statements which are not immediately obvious, but there s no hard and fast rule for this.

7 In proving theorems we often try to break our arguments up into digestible pieces so that the organization of the proof is clear. A lemma is a subtheorem that we prove separately so that it can be used in our proof without breaking the flow of the argument. This is akin to developing a subroutine in programming. SOME BASIC LOGIC Logical deduction was the fourth element in our list of ingredients for writing PROOFS . Much of our logical structure is buried in the development of axiomatic structure and set theory. From this we get the theorems we ve previously developed in mathematics such as Euclidean geometry, ALGEBRA , trigonometry, and calculus. We are fortunate to have this structure to work from, so that we already have a solid box of tools when we start studying LINEAR ALGEBRA . We do need some more discussion of the basics of logic, though. We ll look at some symbolic logic now. Let s start with the following symbols: P Q. Here P stands for a given statement, means implies , and Q stands for a conclusion statement.

8 For example, if P is the statement, It is raining , and Q is the statement, Water is falling on the ground , then P Q says, It is raining implies water is falling on the ground . Another way that we say this is, If it is raining, then water is falling on the ground. This is called the if-then form of the statement. This is a logical statement that we would deem to be true, in general. Another example, if P is the statement, You didn t answer your phone , and Q is the statement, You are cheating on me , then P Q says, You didn t answer your phone, so you are cheating on me . This is a logical statement that may or may not be true. Another example, if P is the statement, The sky is blue , and Q is the statement, Pigs can fly , then P Q says, If the sky is blue, then pigs can fly . This is a logical statement which is not true. It is clear from the preceding examples that if we want to know if Q is true, then we need to know that P is true and that the implication is valid.

9 When writing PROOFS , we must check these two things. We must start with statements we know to be true and show the implication is forced, so that Q must be true. If P Q, we say that P is SUFFICIENT for Q to be true and we say that Q is NECESSARY for P to be true. THE CONVERSE The converse of P Q is P Q (equivalently, Q P). In general, we don t expect the converse to be true. For example, If it is raining, then water is falling on the ground seems reasonable, but If water is falling on the ground, then it is raining seems less reasonable to those who own sprinklers. As for a math example, x = 3, so x2 = 9 cannot be reversed to x2 = 9, so x = 3 . THE DOUBLE IMPLICATION Sometimes the implication does work both ways. If P Q and Q P, then we write P Q and we say that P is true if and only if Q is true. An example from mathematics is x = 3 if and only if x + 2 = 5 . To prove a double implication, we often have to show each of the implications separately.

10 THE NEGATION The negation of the statement P, not P, is written ~P and it means the opposite of P. For example, if P is x = 3 , then ~P is x 3 . THE CONTRAPOSITIVE If P Q, then the contrapositive is ~Q ~P. These are considered logically equivalent. For example, x = 3 implies x2 = 9 has as the contrapositive x2 9 implies x 3 . In PROOFS this shows up as the technique proof by Contradiction. If one needs to show P Q, then it suffices to show ~Q ~P. This technique will be examined in its own section. EXAMPLE This example is from Lewis Carroll: Babies are illogical. Nobody is despised who can manage a crocodile. Illogical persons are despised. We can write this symbolically by doing the following: Define P = { a person is a baby }, Q = { a person is illogical }, S = { a person is despised }, and T = { a person can manage a crocodile }. The statements then become P Q, T ~S, and Q S. The contrapositive of the second statement is S ~T.