Logic¶
We will start with a short discussion of logic, in particular we will briefly cover some notation and a few proof techniques. We will need these later on to be able to make sense of statements concerning things like rings and fields, and also to prove or disprove these statements.
You will probably be happy with the idea that statements such as “the sky is blue” and “pigs can fly” can have truth-values (i.e. “true” or “false”). There are also ways of combining statements to make new statements, which again you are most likely familiar with already:
- If you have two statements \(P\) and \(Q\), you can make a new statement “\(P \text{ and } Q\)”, which is true if both \(P\) and \(Q\) are true. This is often written as \(P \land Q\).
- Similarly, you can also make a new statement “\(P \text{ or } Q\)”, which is true if at least one of \(P\) and \(Q\) are true. This is often written as \(P \lor Q\).
So for example, if we let the symbol \(P\) represent the statement “the sky is blue”, and let the symbol \(Q\) represent the statement “pigs can fly”, the statement \(P \lor Q\) is true, because at least one of them, in this case \(P\), is true.
Exercise 1.1. Using the same assignment of the symbols \(P\) and \(Q\), what is the truth-value of the statement \(P \land Q\)?
Truth tables¶
We can describe the behaviour of logical operators like \(\land\) and \(\lor\) using things called truth tables. For example, here is the truth table for logical and (\(\land\)):
| \(P\) | \(Q\) | \(P \land Q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
The table lists the four possible combinations of truth-values of \(P\) and \(Q\), as well as the truth-value of \(P \land Q\) in each case. If this isn’t clear, it might help to compare it to an implementation of \(\land\) in PureScript:
logicalAnd :: Boolean -> Boolean -> Boolean
logicalAnd true true = true
logicalAnd true false = false
logicalAnd false true = false
logicalAnd false false = false
Exercise 1.2. Write out the truth table for logical or, \(\lor\).
Logical equivalence¶
We say that two statements are logically equivalent if they always have the same truth value as each other, that is, if they are always either both true or both false. Here is a truth table for logical equivalence with some entries missing:
| \(P\) | \(Q\) | \(P \Leftrightarrow Q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | ? |
| F | F | ? |
Exercise 1.3. Complete the missing entries of this truth table.
So for example, \(P \land P\) is always logically equivalent to \(P\), regardless of the truth-value of \(P\). We can express this in symbols by using a double-ended arrow like this: \(P \land P \Leftrightarrow P\).
Logical negation¶
Another thing we can do with statements is negate them: make a new statement which is true if the original statement is false, and false if the original statement is true. If \(P\) is a statement, then the logical negation of \(P\) is written as \(\neg P\).
The following two equivalences hold regardless of the truth-values of \(P\) and \(Q\):
These two equivalences are called De Morgan’s laws.
Exercise 1.4. Persuade yourself that De Morgan’s laws hold. One way to do this is to write out a truth table.
Logical implication¶
We now consider statements of the form “if \(P\), then \(Q\)”, for example:
- if it is raining, then we will get wet,
- if \(x\) is even, then it can be divided by \(2\) exactly,
- if \(y\) is even and \(z\) is even, then \(y + z\) is even.
We represent this kind of statement by defining a new logical operator called logical implication, which we write as a rightwards-pointing arrow: \(\text{it is raining} \Rightarrow \text{we will get wet}\).
The logical implication operator is defined as follows:
| \(P\) | \(Q\) | \(P \Rightarrow Q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
That is, \(P \Rightarrow Q\) is a logical statement just like all of the others we have seen, and it has a truth-value which depends on the truth-values of \(P\) and \(Q\).
Exercise 1.5. Persuade yourself, by using a truth table (or any other method that works for you), that \(P \Rightarrow Q\) is always logically equivalent to \(\neg P \lor Q\) regardless of the truth-values of \(P\) and \(Q\).
The standard way of proving a statement of the form \(P \Rightarrow Q\) is to first assume that \(P\) is true, and then show that \(Q\) follows, i.e. show that \(Q\) must also be true.
For example, suppose we wanted to prove the statement
We would start by letting \(x\) be some arbitrary integer and assuming that it is even. Since \(x\) is even, we can write \(x = 2m\) for some integer \(m\). Then, \(x^2 = 4m^2\) and therefore we have shown \(x^2\) has \(4\) as a factor, so it must also have \(2\) as a factor, which means it must be even.
Converses¶
If we have a statement which is a logical implication, for example \(x \text{ is even} \Rightarrow x \text{ can be divided by 2 exactly}\), there is another closely related statement called its converse. To find the converse of an implication statement, we simply swap the two operands. For example, the converse of the statement
is this:
Notice that both of the above statements are true. However, this is often not the case! If a statement is true, it is not safe to assume that its converse is also true. For example, consider the statement
The converse of this statement is
Notice that, while the first is true, the second is not. For instance, if we take \(y = z = 1\), then \(y + z\) is even, but neither \(y\) nor \(z\) is.
Contrapositives¶
If we have a statement which is a logical implication, for example \(\text{my pet is a cat} \Rightarrow \text{my pet is a mammal}\), there is another closely related statement called its contrapositive. To find the contrapositive of a logical implication statement, we swap the operands and negate them both. So, for example, the contrapositive of the statement \(\text{my pet is a cat} \Rightarrow \text{my pet is a mammal}\) is the statement \(\text{my pet is not a mammal} \Rightarrow \text{my pet is not a cat}\).
The first thing to notice is that any implication statement is always logically equivalent to its contrapositive.
Exercise 1.6. Check this! Persuade yourself that \(P \Rightarrow Q\) is always logically equivalent to \(\neg Q \Rightarrow \neg P\), perhaps with a truth table.
This exercise suggests another way of proving statements of the form \(P \Rightarrow Q\), which is to instead assume that \(\neg Q\) is true, and show that \(\neg P\) follows. This technique is called contraposition; the new statement is called the contrapositive of the original one.
Exercise 1.7. Use contraposition to prove the statement
Another way of thinking of logical equivalence is in terms of logical implication. Specifically, an alternative way of defining \(\Leftrightarrow\) is by saying that \(P \Leftrightarrow Q\) is the same as this bad boy:
In fact, the standard way of proving a statement of the form \(P \Leftrightarrow Q\) is to first prove \(P \Rightarrow Q\) and then to prove \(Q \Rightarrow P\).
Sets¶
For our purposes, it will be sufficient to say a set is a collection of any kind of mathematical object: sets may contain numbers, functions, sets of numbers, and so on.
We can write a set by listing the elements in between curly braces, like this:
Note that sets have no concept of ordering, so the set \(\{1, 3, 2\}\) is the same as the set \(\{1, 2, 3\}\).
The only thing we can really do with a set is to ask whether it contains some particular thing. The notation for the statement “\(a\) exists within the set \(A\)” looks like this:
We also have a notation for the negation of this statement, i.e. “\(a\) does not exist within the set \(A\)”:
Often (but not always), uppercase letters denote sets, and lowercase letters denote elements of sets.
Here are a few sets you may have come across already:
- The set of natural numbers, \(\{0, 1, 2, 3, 4, ...\}\). That is, the set of all the integers which are not negative. This set comes up fairly often so we have a special notation for it: \(\mathbb{N}\). (Note: depending on context, \(0\) is sometimes not considered to be an element of \(\mathbb{N}\); in this guide we will say that it is.)
- The set of integers, \(\{0, 1, -1, 2, -2, 3, -3, ...\}\). Like \(\mathbb{N}\) but it also includes negative numbers. We have a special notation for this set too: \(\mathbb{Z}\), from the German Zahlen, which just means “numbers”.
- The set of real numbers, which is the kind of number you’re probably most used to. \(0, 1, 37, \frac{1}{2}\), and \(\pi\) are all examples of real numbers. This set also has a special notation: \(\mathbb{R}\).
So for example, the following are all true:
Quantifiers¶
Up to now, the symbols \(P\) and \(Q\) have always represented statements. However we can also use symbols to represent predicates, which are like functions which return statements. For example, we might have a predicate “\(x\) is even”, “\(x\) is divisible by 6”, or “\(x\) is prime”.
If we let \(P(x)\) represent the predicate “\(x\) is even”, then we can write the statement “2 is even” as \(P(2)\). Similarly we can write the statement “3 is even” as \(P(3)\). In each case we get a statement whose truth-value can depend on the specific value of \(x\) which was chosen — in this case, \(P(2)\) would be true, and \(P(3)\) would be false.
If we have a predicate, we can make statements about the truth-values of a predicate over all the possible values it can take as arguments by using things called quantifiers.
The first quantifier we will introduce is called “for all”, written as an upside-down capital letter A like this: \(\forall\). Here is how we write the statement “the square of any real number is greater than or equal to 0” using the \(\forall\) quantifier:
This can be read as: “For all \(x\) in \(\mathbb{R}\), \(x\) squared is greater than or equal to \(0\).”
The standard way of proving a statement like this is more or less what you might expect: we have to show that every element of the set satisfies the predicate. If the set is finite, we can do this by checking each element individually. However, individual checking quickly gets very tedious for even fairly small sets. Additionally, we often deal with infinite sets, where exhaustively checking each element individually is not possible. Therefore, we will usually prove statements of this kind by constructing an argument which deals with every single element of the set at the same time. In fact, we have already seen an example of such a proof: the proof that \(x\) being even implies that \(x^2\) is also even, from a moment ago.
The other quantifier we will use is written as a back-to-front capital letter E, like this: \(\exists\), and can be read as “there exists”. Here is how we would write the statement “there exists a real number whose square is 4” in mathematical notation:
There are two possible values of \(x\) which you can use as examples to show that this statement is true: \(2\) and \(-2\). In fact, the standard way of proving a statement of the form \(\exists x. P(x)\) is to pick a specific value of \(x\) and demonstrate that \(P(x)\) is true for that \(x\) (again, as you might expect).
Exercise 1.8. Prove the statement \(\exists x \in \mathbb{R}.\; 3x + 4 = 13\) by finding a suitable value for \(x\).
The last thing we need to know in this section is how to negate statements that contain quantifiers. Here goes:
- The negation of the statement \(\forall x. P(x)\) is \(\exists x. \neg P(x)\).
- The negation of the statement \(\exists x. P(x)\) is \(\forall x. \neg P(x)\).
This is all rather pleasingly symmetric, isn’t it? Try to make sense of these two rules if you can; they will be useful later. Hopefully if you think about them for a bit you’ll be able to persuade yourself intuitively why they are true.
Exercise 1.9. Show that the statement \(\forall x \in \mathbb{R}.\; x < x^2\) is false by finding a counterexample — that is, a value of \(x\) such that \(x < x^2\) does not hold. Do you see how we are using the first of the above two rules for negating statements with quantifiers here?