## Basic logic — summary

Here is the promised post that I hope will be easier to refer back to than the much longer posts I’ve written on individual aspects of basic logic. What I imagine people doing is reading the longer posts and using this one to jog their memories later. If you can think of any important points that I made in earlier posts and have forgotten to mention here, I’d be grateful to know of them.

Once again, the main topics dealt with were these.

Logical connectives. AND, OR, NOT, IMPLIES (or in symbols, $\wedge,\vee,\neg,\implies$).

Quantifiers. “for every” and “there exists” (or in symbols, $\forall$ and $\exists$).

Relationships between statements. Negation, converse, contrapositive.

I think I’ll just write down a numbered list of points.

1. AND has a similar meaning in mathematics to its meaning in ordinary English, but some care is needed if you use it to connect anything other than statements. If you do do that, then make sure you know how to translate what you have written into more formal mathematical language where AND connects statements only.
2. OR is slightly more different from its ordinary English meaning than AND, since in mathematics it is always the inclusive OR. One should think of $P\vee Q$ as saying “P is true or Q is true or both” or “At least one of P and Q is true” (or both).
3. AND and OR are associative. That means that $(P\wedge Q)\wedge R\iff P\wedge(Q\wedge R)$ and $(P\vee Q)\vee R\iff P\vee(Q\vee R).$ In practice what this tells us is that we don’t need brackets. If we connect a bunch of statements with ANDs it means that all those statements are true, and if we connect them with ORs it means that at least one of them is true.
4. However, brackets matter very much indeed when you mix ANDs and ORs. You are not allowed to write $P\wedge Q\vee R$ or $P\vee Q\wedge R$ (or more wordy statements of the same kind). You have to put the brackets in to make clear in which order you are doing things.
5. AND is distributive over OR and vice versa. That means that $P\wedge(Q\vee R)\iff(P\wedge Q)\vee(P\wedge R)$ and $P\vee(Q\wedge R)\iff(P\vee Q)\wedge(P\vee R).$
6. NOT is again similar but not identical to the ordinary English word. If $P$ is a statement, then the statement $\neg P$ should be thought of as saying “It is not the case that $P.$” The main thing to remember is that $\neg P$ is not the opposite of $P.$ For example, if $P$ is the statement “$x$ is the largest element of $A,$” then $\neg P$ has nothing to do with the smallest element of $A.$ It is simply the statement that $x$ is not the largest element of $A.$
7. A good rule for checking whether your use of NOTs is correct is this: NOT turns weak statements into strong statements and vice versa.
8. de Morgan’s laws are that $\neg(P\vee Q)\iff \neg P\wedge\neg Q$ and that $\neg(P\wedge Q)\iff\neg P\vee\neg Q$.
9. IMPLIES is, of all the connectives, the one that least resembles its ordinary English counterpart.
10. If P and Q are specific statements, such as “23 is a prime number” or “there are infinitely many primes” then $P\implies Q$ does not mean that there is any interesting relationship between the two statements. It merely means that it is not the case that P is true and Q is false. (An alternative definition is that if P is true then Q must be true. Though perfectly valid, this definition doesn’t convey quite as vividly just how unnecessary it is for the truth of P to “cause” the truth of Q.)
11. However, most of the time, we do not use IMPLIES to relate specific statements. Rather, we use them to relate general statements — that is, statements that involve unknown variables. And once we do that, the picture becomes more complicated.
12. The reason for the complication is that general statements often look like specific cases. For example, if I say that “$n$ is a prime greater than 2″ implies “$n$ is odd”, then it looks as though I’m talking about one particular case, that of $n$. However, if you ask me which $n$ I’m talking about, I have to admit that I’m not talking about a specific number like 103. Rather, I am making the general statement that would normally be written using a quantifier: for every natural number $n,$ if $n$ is a prime greater than 2 then $n$ is odd.
13. This means that there are two notions of implication that it is important to be aware of and not to confuse. One, which I have called the truth-value notion, is the one mentioned above. The other, which I have called the “causal” notion, is best thought of as relating properties rather than statements. For instance, “is a prime greater than 2″ implies (in the property sense) “is odd”.
14. The two notions of implication are related as follows. Let P and Q be two properties and write $P(n)$ and $Q(n)$ for the statements “$n$ has property P” and “$n$ has property Q”. Then the property P implies the property Q (in the more “causal”, property sense) if and only if for every $n$ the statement $P(n)$ implies the statement $Q(n)$ (in the truth-value sense). If you don’t feel you understand this point properly, I recommend not worrying about it for now, but coming back and rereading what I’ve written if at some stage you find yourself confused about “implies”.
15. Many English words and expressions contain inside them, sometimes not very explicitly, notions of “all” or “some”. For example, “There are always golf balls in the undergrowth over there,” could be translated into more formal language as follows: “For every time $t$ there exists a golf ball $g$ such that $g$ is in the undergrowth over there at time $t.$
16. Note that the quantifiers go at the beginning of the sentence and the variables we are talking about are specifically mentioned. That is to avoid ambiguities such as the following: “Every element of the set $A$ is less than some number.” Does that mean that for each element $x$ of $A$ you can find a $y$ that’s bigger than $x$? If so, then it’s not a very interesting thing to say. It’s more likely that the intended meaning is that there is some number $y$ that is bigger than every element of the set $A.$ This can be made crystal clear if you follow the rule about putting quantifiers first and specifying the variables. Then you get the statement, “There exists a number $y$ such that for every element $x\in A,$ $x” (Perhaps this particular sentence is even clearer in its symbolic form: $\exists y\in\mathbb{R}\ \forall x\in A\ \ x)
17. The negation of $\exists x\in A\ \ P(x)$ is $\forall x\in A\ \ \neg P(x),$ and the negation of $\forall x\in A\ P(x)$ is $\exists x\in A\ \ \neg P(x).$ These two rules are similar to de Morgan’s laws, and the similarity is not a coincidence.
18. That isn’t surprising, as there are almost no coincidences in mathematics.
19. Using the rules for negating single quantifiers, we can negate complicated sentences with lots of quantifiers in a purely mechanical way. We start with $\neg$ right outside the entire sentence, and we then drag it past the quantifiers, changing each $\forall$ into $\exists$ and each $\exists$ into $\forall.$
20. That doesn’t finish the job, because we still have to negate the inner quantifier-free statement. To do that we have to use things like de Morgan’s laws. A particularly important case is when the inner statement takes the form $P\implies Q.$ (Here, and this is very important, I am thinking of $P$ and $Q$ as statements that involve several variables that have also been involved in the quantifiers.) The negation of $P\implies Q$ is $P\wedge\neg Q.$ Why? Because once we get inside all the quantifiers, we’re talking about the truth-value meaning of implication, and the condition for $P\implies Q$ to be false is precisely that $P$ should be true and $Q$ false.
21. A quick example. Suppose that $A$ is some special set of integers and consider the statement “$\forall x\in A\ \ x$ is odd $\implies x$ is prime.” The negation of this is “$\exists x\in A\ \ x$ is odd and $x$ is not prime.”
22. It’s worth thinking about the meaning of “$\implies$” in that previous example. A number’s being odd doesn’t cause it to be prime. However, the statement is saying that for every number $x$ that belongs to the set $A,$ it so happens that if $x$ is odd then it is also prime. This is very much the truth-value meaning of “$\implies$” and not the “causal” meaning.
23. The converse of a statement $P\implies Q$ is the statement $Q\implies P$. Also, we often say that the converse of a statement of the form $\forall x\in X\ \ P(x)\implies Q(x)$ is the statement $\forall x\in X\ \ Q(x)\implies P(x)$.
24. If a statement is true, that does not make its converse automatically true: it is very easy to think of true statements with false converses. Therefore, you should be careful not to confuse a statement with its converse.
25. However, there are many interesting examples of true statements that do have true converses. When this happens, it is very often easier to prove the implication in one direction than it is to prove it in the other.
26. The contrapositive of the statement $P\implies Q$ is the statement $\neg Q\implies\neg P$. The contrapositive is equivalent to the original statement (in the sense that it is true if and only if the original statement is true), but it often turns out to be easier to prove.
27. The contrapositive of the converse of $P\implies Q$ is $\neg P\implies\neg Q$. It is sometimes easier to prove $\neg P\implies\neg Q$ than it is to prove $Q\implies P$.
28. If you need to prove the converse of $P\implies Q$, don’t accidentally prove that $\neg Q\implies\neg P$ instead …
29. A free variable is one that is not quantified over. A bound variable is one that is quantified over. For example, in the statement $\exists M\in\mathbb{R}\ \forall x\in\mathbb{R}\ \ |f(x)|\leq M$, $M$ and $x$ are bound variables and $f$ is free. (An intuitive test you can apply is this: of which variables does it make sense to say that the statement is telling us something about those variables? The above statement is telling us about $f$ and it doesn’t make sense to say that it is telling us about $M$ or $x$.)
30. Bound variables are a bit like the dummy variables that appear in expressions such as $\sum_{m=1}^nm^2$ and $\{x\in\mathbb{R}:x^2\leq a\}$. (In the first expression $m$ is a dummy variable and in the second one $x$ is a dummy variable.)
31. When you are writing a proof, always be clear in your mind — and in your write-up, which variables are free and which bound.
34. An important way of introducing a variable is to use the “let” trick and the “suppose” trick. For instance, if you want to prove a statement of the form $\forall x\in X\ \ P(x)\implies Q(x)$, then without thinking you can begin your proof, “Let $x\in X$ and suppose that $P(x)$.” Another way of putting it is, “Let $x$ be an element of $X$ such that $P(x)$.
35. If you have just proved a statement of the form $\exists x\ \ P(x)$ then it is considered OK to go on and talk about $x$ as though you had just chosen it — even if you haven’t. For example, it’s OK to write, “There exists $x$ such that $f(x)\in B$. It follows that $f(x)\in B\cup C$.” which is a kind of shorthand for, “There exists $y$ such that $f(y)\in B$. Let $x$ be such that $f(x)\in B$. Then $f(x)\in B\cup C$.”