Hello everyone. So I'd like to explain this new video series, that I'm going to do. I’m going to call it Carmen’s Core Concepts, for alliteration reasons. The idea behind these videos is, not to be a replacement of lectures, but rather to be a quick summary of what we did this week; what I felt were the highlights, what were the most important things and how you can maybe use these techniques to help you in Math 135. So I've started with week 1. Again I would love your feedback, please either send me an email cbruni@uwaterloo.ca or post on Piazza if I'm teaching this term. Either way, this is great, I'd love to hear feedback, if these are helpful or not. Anyways I'm going to begin with week 1
The way these are going to work is I'm going to have a table of contents here. Roughly every bullet will be approximately one minute. So clearly this is going to be very very quick. It's not, you know, you're meant to pause it, and go back, and review it, and it's not meant to replace lectures. It's meant to be a complement to the lectures to say, “Oh okay, these are the important things we did this week and these are what I should be focusing on in order to to develop mastery of mathematics.”
So we're going to start off with, “What is Math 135?”, what we cover in it, what's the importance of it. We’ll talk about truth tables as a definition. So we talked about truth tables this week and we’d like to talk about how we can use them to define things. We'll talk about DeMorgan’s Law and how truth tables can also be used to prove things. We're going to talk about…we talked about chains of equivalences, so using logical equivalences to show that statements are equivalent to each other. Then we talked about direct proofs, so we just talked about a normal direct proof, we talked about direct proofs from true statements, we talked about direct proofs when you break into cases, and then we finished off the week with the divisibilities and bounds by divisibility.
I should mention that at this point, before we continue, don't be alarmed if you didn't cover all of these things. You'll eventually cover all of these topics, that's perfectly fine. Some instructors might go in different orders, some instructors might not have gotten to everything this week, not a big deal. It's definitely not a big deal; don't take this as like the gospel to teaching Math 135, or what you should have done this week, or what you didn't do this week. Again, these are the topics that I've covered this week, and so that's what I based this lecture series on.
So let's start Math 135. So Math 135, that's your first proofs course, right? Remember that proofs differentiate mathematics from science. Science proof is kind of like, “Well I took a ball and dropped it a hundred times so if I drop it the next time it's going to fall.” That's kind of like proof in science, right, whereas mathematics that's not enough. Mathematics starts with a set of axioms and develops a huge network of theorems, lemmas, propositions, all kinds of things. You derive new truths from given truths.
We spoke a little bit this week about reading, writing, and discovering proofs. So there's a difference between these three acts, right? Reading a proof is very different than reading a normal book, right? Reading a math textbook should take you a lot longer than reading a novel. A novel is written in English, they're easy to understand. Reading a math textbook’s going to require a little bit of thought, a little bit of writing on the side. You have to kind of digest what's going on, things like that. Writing a proof…writing a proof is usually not the hardest part of this process. If I'm discovering - for me anyways - discovering is a lot harder than writing. But even writing is tricky, right? You need to make sure that you have the audience level aimed correctly, and that you're not missing any steps or important key facts in the proof Discovering from a proof, like I said, is always the difficult part. I always love analogies with napkins. I used to go to the C&D or to Mel's Diner, two of my favorite spots to do mathematics, and you know I used to take their napkins and placemats and doodle on them, right? That's what I would call the discovering proof stage, and these napkin computations. We’ll see an example of that in a minute.
And sort of the analogy to go through all this is the “Goldilocks analogy”. You want to write just the right amount in your proof. You don't want to write too much where people aren't going to read, it's too long it's too verbose, you don't want to write too little where you're missing details and missing important facts. You want to write just the right amount with good and proper explanation. You want to make sure that you're using all the correct information here.
Okay so, truth tables as a definition. So, truth tables are the building blocks of mathematics, right, I mean this is how we start off with some axioms and we develop from here. So here, we're going to define truth and… well true and false which we know, right? Like a toggle. So throughout these explanations of truth tables let \(A\) and \(B\) be statements. What did we see this week? We saw $$\neg A, A \wedge B, A \lor B, A \Rightarrow B$$ These are the four major ones. For \(\neg A\): Remember if \(A\) is true, \(\neg A\) is false, if \(A\) is false, \(\neg A\) is true.
For the other ones, we have this truth table here.
| \(A\) | \(B\) | \(A \land B\) | \(A \lor B\) | \(A \Rightarrow B\) |
|---|---|---|---|---|
| \(T\) | \(T\) | \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) | \(T\) | \(F\) |
| \(F\) | \(T\) | \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(F\) | \(F\) | \(T\) |
So here, we're using it as a definition. So here, we've talked about all four possibilities for \(A\) and \(B\):
| \(A\) | \(B\) |
|---|---|
| \(T\) | \(T\) |
| \(T\) | \(F\) |
| \(F\) | \(T\) |
| \(F\) | \(F\) |
Again, you don't need to put them in this order, but it's usually easy to read when they're in a nice order. Here we have \(A \land B\) which is true only when both \(A\) and \(B\) are true. We have \(A \lor B\) which is false only when both are false and true otherwise, and you have \(A \Rightarrow B\). Now remember this was the little tricky.. this one was the trickier one. True and true so if \(A\) is true and \(B\) is true, then the implication is true. If \(A\) is true and \(B\) is false, then the implication is false, and if \(A\) is false then the implication is true, doesn't matter what \(B\) is. Okay? So keep that in mind, that implication - remember the only way it's false is if \(A\) is true \(B\) is false. \(A\) is false the implication is true. “If \(5\) is even then \(5\) is odd”, right, that's a true statement, because \(5\) is not even, therefore the hypothesis is false and the implication is true.
Keep in mind… I guess since I said hypothesis, \(A\) is the hypothesis and \(B\) is the conclusion. That's what we talked about with truth tables as a definition.
We saw DeMorgan's Law, so the other part of truth tables is that we can actually use them as a method of proof. So what are DeMorgan's Laws? Well it's basically a distributive property with \(A \land B\) or \(A \lor B\). De Morgan's Laws are: $$\neg (A \land\ B) \equiv \neg A \lor \neg B \;and\; \neg (A \lor B) \equiv \neg A \land \neg B$$
So if you have \(\neg (A \land B)\) the way I kinda remember it is you bring the little \(\neg\) inside to the \(A\), you change the \(\land\) to \(\lor\), or \(\lor\) to \(\land\), and you bring the \(\neg\) inside \(B\). Again, that's sort of the way I remember it it's like a distributive law over all of the symbols.
I could prove this by a truth table, right, so here I’m proving \(\neg (A \lor B)\) \(\equiv\) \(\neg A \land \neg B\).
| \(A\) | \(B\) | \(A \land B\) | \(\neg (A \land B)\) | \(\neg A\) | \(\neg B\) | \(\neg A \land \neg B\) |
|---|---|---|---|---|---|---|
| \(T\) | \(T\) | \(T\) | \(F\) | \(F\) | \(F\) | \(F\) |
| \(T\) | \(F\) | \(T\) | \(F\) | \(F\) | \(T\) | \(F\) |
| \(F\) | \(T\) | \(T\) | \(F\) | \(T\) | \(F\) | \(F\) |
| \(F\) | \(F\) | \(F\) | \(T\) | \(T\) | \(T\) | \(T\) |
So here we have \(A\), B, and then we write \(A \lor B\) and then we write \(\neg (A \lor B)\), then we have \(\neg A\) and \(\neg B\), and then you have \(\neg A \land \neg B\). Remember you should always include a concluding sentence, or you should always write a concluding sentence, right?
Since the fourth column and the seventh column have all the truth values for all possibilities of \(A\) and \(B\), it means that these two statements are logically equivalent.
So you should include that final sentence. You want to make sure that the reader knows that you understand why this table actually means you proved something. This is a little something subtle there.
De Morgan's Laws, they help to form chains of equivalence, which we'll see in a minute, we're going to negate implication next, and we'll see how we use DeMorgan's Laws and other chains of equivalences to derive new truths. So one way to derive new truth is using the truth table and the other way, with these statements, is to use a chain of equivalence.
So using chains of equivalences.
Recall: \(A \Rightarrow B \equiv \neg A \lor B\)
Either the hypothesis is false, or the conclusion is true. If one of those two things are true then the implication is true, that’s one way to remember it.
Prove that \(A \Rightarrow B \equiv \neg A \lor B\)
So how do we do that? Well here we can use the "Recall" proposition that we proved in class by a truth table. So by the "Recall" proposition we have: $$\neg(A \Rightarrow B) \equiv \neg (\neg A \lor B)$$ Then we have \(\neg (\neg A \lor B)\), well that's DeMorgan's Law, right, we bring the \(\neg\) into everything. So \(\neg (\neg A)\), \(\neg\) of \(\lor\) I like to think of as \(\land\), and \(\neg B\) is \(\neg B\). Now we have: \begin{align*} \neg(A \Rightarrow B) &\equiv \neg (\neg A \lor B) \\\\ &\equiv \neg(\neg A) \land \neg B \end{align*} Then \(\neg (\neg A)\) that’s just \(A\) from a proposition from class that double negation should cancel:
$$\begin{align*} \neg(A \Rightarrow B) &\equiv \neg (\neg A \lor B) &&\\\\ &\equiv \neg(\neg A) \land \neg B &&\\\\ &\equiv A \land \neg B \end{align*}$$And that's it. So here's an example where we can use equivalent statements to prove new truths in mathematics. That was sort of our brief look at logic for Math 135.
Direct proof, so this is the next thing that we talk about this week. So we can prove equalities or inequalities by direct proofs. Here's one example that I did in class:
$$\text{Prove that}\, \sin(3\theta) = 3\sin\theta - 4\sin^3(\theta)$$Now, how do we go about proving this? Well we start with the left hand side, which is \(\sin(3\theta)\), and split it up and then use our trig rules.
$$\begin{align*} \text{LHS} &=\sin(3\theta)\\\\ &= \sin(2\theta + \theta)\\\\ &=\sin(2\theta)\cos(\theta) + \sin(\theta)\cos(2\theta) &&\text{Trig Identity} \end{align*}$$Now whenever you use a trig rule, something like this, you should cite what you're doing, okay? For the purposes of this video I've just called it a “trig identity”, for the purposes of Math 135, this is probably okay. I think people understand what happened here. Even beyond Math 135, this is definitely okay.
$$\begin{align*} \text{LHS} &=\sin(3\theta)\\\\ &= \sin(2\theta + \theta)\\\\ &=\sin(2\theta)\cos(\theta) + \sin(\theta)\cos(2\theta) &&\text{Trig Identity}\\\\ &=(2\sin(\theta)\cos(\theta))\cos(\theta) + \sin(\theta)(cos^(\theta) - sin^2(\theta)) &&\text{Trig Identity} \end{align*}$$I used a trig identity here, and then from the second line to the third line, you actually use two trig identities. You use a trig identity on \(\sin(2\theta)\) and a trig identity on \(\cos(2\theta)\), which is perfectly fine. You do a little bit of simplifying and distributing, so collect like terms, etc etc. Then on the second last line of the following sequences of equalities, we use the Pythagorean identity Since \(\cos^2(\theta)\) is equal \(1 - \sin^2(\theta)\).
$$\begin{align*} \text{LHS} &=\sin(3\theta)\\\\ &= \sin(2\theta + \theta)\\\\ &=\sin(2\theta)\cos(\theta) + \sin(\theta)\cos(2\theta) &&\text{Trig Identity}\\\\ &=(2\sin(\theta)\cos(\theta))\cos(\theta) + \sin(\theta)(\cos^2(\theta) - \sin^2(\theta)) &&\text{Trig Identity}\\\\ &=3\sin(\theta)(\cos^2(\theta) - \sin^3(\theta))\\\\ &=3\sin(\theta)(1 - \sin^2(\theta) - \sin^3(\theta)) &&\text{Pythagorean Identity}\\\\ &=3\sin(\theta) - 4\sin^3(\theta)\\\\ &=\text{RHS} \end{align*}$$We expand it out, we get the result that we want. Well the correct result that we want. So here's the direct proof. Start with half of it, and derive using things that you already know are true, axioms, to get new truths. Okay? For the purposes of this course, we can take trig identities for granted. If you ever need them on an exam, we will give them to you, in all likelihood, with the exception of the Pythagorean identity. This should be ingrained into your head. You might want to tattoo this on your arm, it's a possibility… okay don't tattoo things on your arm… but, you know , you should know this one. That's sort of the summary of what I needed to say.
Direct proof from a true statement. So here's another example of we saw.
$$\text{Prove that}\, 5x^2y - 3y^2 \leq x^4 + x^2y + y^2\, , \, x,y \in \mathbb{R}$$Now the way we proved this in class, I kind of just ripped it like a band-aid, right? So here we have this statement: Since \(0 \leq (x^2-2y)^2\)... remember this is the square of a real number, it's always greater than or equal to 0…we have the following.
So I wrote that down expand it out, add \(5x^2y-3y^2\) to both sides, and then simplify. We get the results. Now on the one hand, you can read the proof and you can follow it and it's reasonably clear what's happening, right? We haven't done too too much that was tricky. The only thing that was maybe clever was adding \(5x^2y-3y^2\) to both sides, but in hindsight, if you think about it, right, if you're trying to prove \(5x^2y - 3y^2 \leq x^4 + x^2y + y^2\), then you probably want \(5x^2y - 3y^2\) to appear on the left hand side. So you probably want to add that to both sides.
Well it's actually a very “follow your nose” kind of proof, once you have the first line. Now the question is, where does this first line come from? That's where the discovery happens. These are what I call the “napkin computations” and things you do at Mel's Diner, the things you do at the C & D, something like that, right? Where does it come from? Well you take the conclusion, which is not something you can normally do take the conclusion and mess around with it, but for the purposes of discovery you can do whatever you want, right? I mean if I'm just going to play around, I'm going to play around with a way that will hopefully help me. So, the discovery of this:
We know that \(5x^2y-3y^2 \leq x^4+x^2y+y^2\) . Now what I'm going to is I'm going to bring the terms over, which is what I do in the second line, I'm going to simplify and then I'm going to notice that, oh well I can factor \(x^4-4x^2y+4y^2\), and I get \((x^2-2y)^2\) And I know that this last statement is true. So as long as I can go backwards with all these steps, then I'm perfectly okay with writing the proof, and it turns out that I can go backwards in all these steps. We'll see in a bit that you can do "if and only if" proofs like this, which we'll get to next week. Something to look forward - something to look towards… well maybe you look forward to Math 135 that's okay if you don’t. That's something to look towards, that you can write these proofs like this as long as all the implications are both directions.
Direct proof breaking into cases. “If \(2^{2n}\) is an odd integer, then \(2^{-2n}\) is also an odd integer if \(n \in \mathbb{Z}\).” Now this is an implication, an “if… then”, right? So remember, implications are true if the hypothesis is true and the conclusion is true, or the hypothesis is false. If the hypothesis is false then the implication is always true.
So the question now becomes… well let's think about this. \(2^{2n}\) that looks like it should be even almost all the time. But if you think about it, \(2^{2n}\) is an odd integer, what does that mean for \(n\)? Well \(n\) must…well I mean, in theory, \(n\) must be an integer but in particular, if \(n\) is a negative integer, then \(2^{2n}\) isn't even an integer. It's going to be \(\frac{1}{2^{2n}}\), and that's not an integer.
If \(n\) is positive, then \(2^{2n}\) that's going to be an even integer because 2 will divide \(2^{2n}\) right? I can write:
$$2^{2n}=2(2^{2n-1})$$We see that \(2n-1\) is positive when \(n\) is positive, so we see that \(2^{2n}\) is even.
Thus, what's left? Well \(n\) must be 0, and hence \(2^{2n}=1=2^{-2n}\) thus, \(2^{-2n}\) is an odd integer.
So here's an example where we broke into cases. There are other ways to do this so, one way to do it. So again, we saw positive versus negative versus 0, even versus odd is another common way to break things down. Sometimes if you have integers \(a\) and \(b\), you could write \(a \leq b\) and \(b \leq a\), that's possible too. Lots of ways to break in the cases. I just want to give you a couple of examples of ways to do that. Just make sure that your cases cover everything, okay? When we head into sets next week, we'll see a couple more ways to break into cases.
Last topics of the week were divisibility. I know that some people didn't get to divisibility this week, that's okay. Here's an interlude to next week. We say that \(m~divides~n\) and write \(m \mid n\), and we read this as \(m~divides~n\), if and only if there exists an integer k such that \(mk=n\). So I told my class this “and only if” part, we'll get to that next week, okay? Usually, mathematicians don't write this, they're generally sloppy with their definitions in this sense, but it should be “if and only if”. I'll try to do that throughout the course for myself, but note that other books might not do this. Otherwise, we write \(m~does~not~divide~n\) so \(m \nmid n\). The \(\nmid\) symbol is \nmid inside LaTeX if you're interested. That is when there's no integer k satisfying \(mk=n\).
That's just the definition of divisibility. Divisibility is a very core concept in this course. We kind of understand divisibility from an intuitive standpoint, right, like \(3 \mid 9, \,-6 \mid 36\), the only ones that are weird are things like \(0 \mid 0\). Remember \(0 \times 3 =0\), right? So it satisfies the definition of divides, right? Same with things like \(3 \mid 0\) because \(3 \times 0 =0\) right? So just keep that in mind that \(0's\) can be in here, just remember which way they go. So if \(m=0\) and this is true, then \(n=0\). I'll let you think about that for a minute.
Finally Bounds By Divisibility, this was the last major thing we did. This is the first look at an acronym in the textbook. I also like to use DeMorgan's law, DML, as an acronym but BBD is the first one in the book, Bounds by Divisibility. So we have:
$$a \mid b \land b \neq 0 \Rightarrow |a| \leq |b|$$So one thing I did here intentionally before, and one thing we do here intentionally, is if we don't specify the domains of these symbols, then take them to be as big as they can possibly be. So because we defined the vertical bar, \(\mid\) for integers, we're going to take \(a\) and \(b\) as integers. That's really what I want here anyways, but I want to make this note because it is possible that I will forget during class, or I will forget during…something. During an exam, hopefully the questions are written crystal clear, but you know mistakes do happen. But the exam should be clear otherwise, take that to me. Same with other textbooks as well. This is usually a golden rule.
What's the proof of this? Well okay, if I take two integers a and b satisfying the two requirements, then the definition of \(a \mid b\), remember that's all we really have, right? So when all you have are hammers and nails, then you should probably hammer nails, right? All you have is a hammer, use the hammer. So all we have is the definition, so let's use the definition. So we know \(\exists k \in \mathbb{Z}\) such that \(ak = b\). Since \(b\ \neq 0\), what do we know? We know that \(k \neq 0\) and so we have the following sequence of statements:
$$|a| \leq |a||k| = |ak| = |b|,\,\text{as required}$$That’s true because \(k \neq 0\) and \(k \in \mathbb{Z}\) so \(|k| \geq 1\) so therefore this holds. Remember absolute values, you can take them in, so now I have \(|ak|\). That's just equal to \(b\), as required.
Last thing I want to mention, a lot of you probably already know this but, I do have symbol and theorem cheat sheets on the Math 135 resources page so, for example, I didn't mention here but \(\mathbb{Z}\) being the set of all integers, Z being the first letter of the word integers in German, \(\exists\) is "there exists", we’ll see that a lot this upcoming week, but I want to introduce it now just so that it's a little bit easier to cope with these symbols. You're going to see a lot of symbols over the next couple of days, the beginning of this course does have a lot of symbols, but once you get them down it's a lot easier to write things mathematically. There are theorem cheat sheets. So the first couple of weeks the theorems aren't too too bad, but I did include them. After week five or six, the theorems start to pick up very heavily, and there's where the cheat sheets will probably be more useful to you. But, you know, for the moment, the symbol cheat sheet might be more useful. Again though, there are theorem cheat sheets to help you out.
Okay, so again thank you very much for listening. Hopefully this gave you a little bit of an insight as to what we did, where we're going, why these things are important. Again if you have any feedback, email me at cbruni@uwaterloo.ca, post on Piazza, and that's it. Thank you very much.