Goldrei’s book is only recommended if you want to learn logic in much more depth than is necessary for 0005. You can also take MATH0037 Logic in your third year to learn more.
This part of 0005 is about logic - the study of how we can reason and make deductions, of methods of argument, and methods of proof.
We begin with the simplest bit of mathematical logic, propositional calculus. This deals with propositions which are statements that can be either true or false, and logical connectives which combine simpler logical statements into more more complex ones.
Example propositions:
Outside of 0005, propositions don’t have to be mathematical statements. Logic helps us reason about all kinds of things. But in 0005 we mainly stick to math where determining truth or falsity is usually easier.
Logical connectives are what we use to build complex propositions out of simpler ones. The ones we mainly use are and, or, not, implies, if and only if (iff, for short).
“Implies” is often expressed as “if…then”: “if 34043 is odd then 34043 is divisible by 3.”
You might wonder if there are any more interesting “exotic connectives” that would allow us to create new statements not expressible using the connectives above. There are other connectives - common examples are exclusive or (xor) , NAND (Sheffer stroke), nor - but it’s a theorem that any connective you invent can be expressed in an equivalent way using just the connectives above (in fact, you don’t even need all of them).
In the next video we are going to develop a formal language for representing complex logical statements.
We’re going to develop a formal language for expressing logical propositions.
Because we want to talk abstractly about how to reason, we don’t want to confine ourselves to particular propositions but to explore what can be said about all propositions. For that reason we introduce propositional variables: symbols that represent a proposition. Traditionally lower case English letters p, q, r, … are used for propositional variables, or letters with subscripts \(p_1, p_2, ...\)
In additional to propositional variables, our language will have symbols for some of the logical connectives we discussed before.
Sometimes we’ll be interested in other logical connectives, but for now we will stick to the above 4.
Lastly we will also use brackets: ( and ).
We’ve now got the “letters” of our language. Just like the letters abc..z can be used to make English sentences, we can now build what we will call formulas, like \(p \vee q\), or \(p \implies (q \wedge (\neg r))\). But just like eifaefeaioj is a legitimate string of letters that isn’t a meaningful word, \(\wedge \implies p q )\neg\) doesn’t seem like something we can give a useful logical interpretation to.
We need rules to say which strings of connectives, brackets, and variables are “well-formed formulas”, WFFs for short.
To do this we are going to describe a procedure for making formulas. A well-formed formula, by definition, is one that can be made using this procedure.
Suppose \(p\) and \(q\) are propositional variables. Then the following are WFFs:
ONLY things that can be built like this are WFFs. You can’t build
\[\wedge \implies p q ) \neg\]
using the rules above (why?), so it’s not a WFF. You can’t even build \(p \vee q\) or \((p\wedge q \wedge r)\), so these aren’t WFFs either with our strict definition.
We’ve seen what a WFF is. It’s important to remember that a wff like \((p \wedge q)\) isn’t true or false on its own: that will depend on the truth or falsity of the statements represented by the propositional variables \(p\) and \(q\) of course. The aim of the next couple of videos is to see how, once we decide whether the propositional variables in a WFF are true or false, how to give a truth value to the WFF as a whole.
Let’s start with giving truth values to propositional variables.
Definition a truth assignment for a set \(V\) of propositional variables is a function \(\nu : V \to \{\text{true}, \text{false}\}\).
That’s easy enough. Our problem has become, given a truth assignment for some prop vars, how can we extend it to get a truth value for all the WFFs using those vars? For ex, if you know p and q and r are true, what should the truth value of \[((p \implies (q \vee r)) \implies (\neg p \vee q)),\] or some other complex WFF, be?
In order to do this, we work from simpler WFFs to more complex ones. Our truth assignment already tells us how to give truth values to the simplest WFFs of all, propositional variables. The next simplest WFFs are ones with a single connective, like \((p \wedge q)\) or \(\neg r\). There’s no way to “work out” these truth values: it is a matter of definition - we have to decide what these truth values should be so that they mimic how we think “and”, “or”, “not”, and “implies” should behave.
We define truth values for WFFs with a single connective using truth tables. Here’s the truth table for \(\wedge\):
| \(p\) | \(q\) | \((p \wedge q)\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
(T and F are short for true and false)
The first row of table is telling you that if the truth assignment makes \(p\) and \(q\) true, then \((p \wedge q)\) is true. The second row tells you that if the truth assignment makes \(p\) true and \(q\) false, then \((p \wedge q)\) will be false, and so on.
Here are the truth tables for the other connectives in our language.
| \(p\) | \(q\) | \((p \vee q)\) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
| \(p\) | \(q\) | \((p \implies q)\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
People often find the truth table for implies confusing, especially the final two rows where \(p\) is false which say that \((p \implies q)\) is true whenever \(p\) is false, regardless of the truth value given to \(q\). If you’d like to read more about why this truth table is a sensible way to define truth values for statementes containing “implies”, this short piece of writing by (Fields medallist!) Tim Gowers, or this longer version is good.
| \(p\) | \(\neg p\) |
|---|---|
| T | F |
| F | T |
In the next video we’ll discuss how to extend a truth assignment to all WFFs.
Given a truth assignment \(\nu\) for some propositional variables, we want to assign a truth value \(\nu(\phi)\) to each WFF \(\phi\) using those variables. We have made a definition of how to do this when the WFF has only one connective, using our truth tables. How to do it for general WFFs?
The idea is to try to do this in a way which is compatible with the truth tables, in the sense that for any two WFFs \(\phi\) and \(\psi\), the truth value \(\nu (\phi \wedge \psi)\), say, is the same as the value in the final column of the row of the truth table for \(\wedge\) corresponding to \(\nu(\phi)\) and \(\nu(\psi)\).
Since each WFF was built up from propositional variables using logical connectives, this enables us to give a truth value to any WFF. For example, let
\[\phi = ((p \wedge q) \vee (\neg p \wedge \neg q)).\]
Let \(\nu(p)=T, \nu(q)=F\). Then if our truth assignment is to be compatible with the truth table for \(\neg\), it has to be that \(\nu(\neg p) = F\) and \(\nu(\neg q) = T\).
Now the \(T, F\) row of the truth table for \(\wedge\) tells us that \(\nu(p \wedge q) = F\), and \(\nu( \neg p \wedge \neg q ) = F\).
Finally, looking at the \(F, F\) row of the truth table for \(\vee\), \(\nu(\phi)\) is \(F\).
In summary, we know how to give truth values to the simplest bits of these WFFs - those with only one connective. So we can build up the truth value of a complex WFF by starting from its simplest parts and working upwards.
(It’s not completely obvious this gives the same result no matter which way you build up the formula: see Goldrei, Theorem 2.2.)
Let’s do another example. Consider the WFF \(\phi = (p \implies (p \implies p))\) and the truth assignment \(\nu(p) =\) true. What is the truth value for \(\phi\)?
The method is to start with the simplest pieces of \(\phi\) and work up. Looking at the true true row of the truth table for implies, \((p\implies p)\) is true.
| \(p\) | \((p \implies p)\) | \((p\implies(p\implies p))\) |
|---|---|---|
| T | T |
Since we know p is true and \(p\implies p\) is true, looking again at the t t row of the truth table for implies, \(\phi = (p \implies (p\implies p))\) is true. So we can fill in a T in the last column of the table.
Pause the video and work out the truth value of \(\phi\) when \(p\) is false.
You should get
| \(p\) | \((p \implies p)\) | \((p\implies(p\implies p))\) |
|---|---|---|
| T | T | T |
| F | T | T |
\(\phi\) is true for every truth assignment of its variables. A WFF with this property is called a tautology, and a WFF which is false under every truth assignment, e.g. \(p \wedge \neg p\), is a contradiction.
Let’s do another. \(\phi = ((p \vee q) \wedge (p \vee \neg q))\). Given a truth assignment \(\nu\) for \(p\) and \(q\), say \(\nu(p)=\text{true}, \nu(q) = \text{false}\), let’s work out the truth value of \(\phi\).
Again, we start with simplest pieces of \(\phi\) and use the truth tables for those pieces. Inside \(\phi\) you can see \(p \vee q\), \(\neg q\), and the truth values of those follow from the truth tables:
| \(p\) | \(q\) | \((p \vee q)\) | \(\neg q\) | \(( p \vee \neg q )\) | \(\phi\) |
|---|---|---|---|---|---|
| T | F | T | T | T | T |
This is just one row in a truth table for \(\phi\), describing its truth value under every possible truth assignment for \(p\) and \(q\).
| \(p\) | \(q\) | \((p \vee q)\) | \(\neg q\) | \(( p \vee \neg q )\) | \(\phi\) |
|---|---|---|---|---|---|
| T | F | T | T | T | T |
| T | T | T | F | T | T |
| F | T | T | T | T | T |
| F | F | F | T | T | F |
To motivate the idea of logical equivalence, consider the two WFFs
\[\begin{align*} \phi &= (p \wedge q) \\ \psi &= (q \wedge p) \end{align*}\]
These are different WFFs - a WFF is purely a string of symbols, and these are two different strings of symbols. But no matter what truth assignment you choose, \(\phi\) and \(\psi\) get the same truth value: if you look at the truth table for \(\wedge\) it is symmetrical in \(p\) and \(q\), that is, \(p \wedge q\) is true if and only if \(q \wedge p\) is true.
Definition. Two WFFs \(\phi\) and \(\psi\) are logically equivalent, and we write \(\phi \equiv \psi\), if they have the same truth value under any truth assignment.
Equivalently you could say that two WFFs are logically equivalent if and only if they have the same truth table. Of course, our definition only makes sense when \(\phi\) and \(\psi\) use the same propositional variables.
When two WFFs are logically equivalent they may be different but they always have the same truth value, no matter what the truth values of their variables. This concept is tremendously useful in practise: if you want to prove something is true, you can prove some logically equivalent formula instead.
Let’s begin with some simple but useful examples of logical equivalence. In the next video we’ll do some more in depth ones.
Proposition. Let \(\phi\), \(\psi\), and \(\theta\) be WFFs.
1 and 2 are very easy to check - they follow straight from the truth tables for \(\wedge\) and \(\vee\). 3 and 4 are tedious to check, but very easy - just compute the truth tables, and you’ll see they have the same value for any truth value \(\psi\), \(\psi\), and \(\theta\) could have.
What the associativity laws 3 and 4 do is allow us to drop some brackets. Something like \(p \wedge q \wedge r\) isn’t a WFF - because it has \(\wedge\) symbols but no brackets - but part 3 guarantees us that any two ways we choose to bracket it give logically equivalent WFFs. Similarly
\[\begin{gather*}p_1 \wedge p_2 \wedge \cdots p_n \\ p_1 \vee p_2 \vee \cdots p_n\end{gather*}\]
may not be WFFs, but any bracketings turning that do turn them into WFFs give logically equivalent formulas.
On the other hand, sometimes we do need brackets. The WFFs
\[\begin{align*} \phi &= (p \wedge (q \vee r)) \\ \psi &= ((p \wedge q) \vee r) \end{align*}\]
are not logically equivalent. Pause the video and find a truth assignment witnessing this - a truth assignment where the two WFFs get different values.
Here are the truth tables for these two formulas:
| \(p\) | \(q\) | \(r\) | \((p \wedge (q \vee r))\) | \(((p \wedge q) \vee r)\) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | T | F | T | T |
| T | F | T | T | T |
| T | F | F | F | F |
| F | T | T | F | T |
| F | T | F | F | F |
| F | F | T | F | T |
| F | F | F | F | F |
so the only places they differ are when
\[p=F, q=T, r=T\]
or when
\[p=F, q=F, r=T.\]
Now we’re going to look at some more complex and useful logical equivalences.
Proposition. Let \(\phi\) be a WFF. Then \(\neg \neg \phi \equiv \phi\)
Proof Under any truth assignment, \(\phi\) is either t or f. If it is t then \(\neg \phi\) is f, so \(\neg \neg \phi\) is t. Similarly if it is f so is \(\neg \neg \phi\). Therefore they have the same value under any truth assignment.
Proposition. Let \(\phi\) and \(\psi\) be WFFs. Then
(There are some extra brackets here which aren’t strictly needed).
Proof. Again, proving this is simply a matter of checking the possibilities for the truth values of \(\phi\) and \(\psi\) under any assignment. In a table:
| \(\phi\) | \(\psi\) | \(\neg(\phi\vee\psi)\) | \((\neg \phi) \wedge (\neg \psi)\) |
|---|---|---|---|
| T | T | F | F |
| T | F | F | F |
| F | T | F | F |
| F | F | T | T |
The final columns are the same, so the two formulas have the same truth value no matter what truth assignment is used, so they are logically equivalent.
The next logical equivalence shows us that every formula that uses \(\implies\) can be written with \(\neg\) and \(\vee\) instead.
Proposition. Let \(\phi\) and \(\psi\) be WFFs. Then \[(\phi \implies \psi) \equiv (\neg \phi) \vee \psi.\]
(again I’ve been slightly sloppy with the brackets to make this more readable).
Here is the relevant truth table.
| \(\phi\) | \(\psi\) | \((\phi \implies \psi)\) | \((\neg \phi) \vee \psi\) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | T | T |
| F | F | T | T |
This one is commonly used when proving a statement like “A implies B.” If you read a proof of a statement like that, what you will often see is that it is carried out by assuming that A is true and then deducing that B is also true. That works because if A is false then not A is true, so \(\neg A \vee B\) is true no matter what the statements A and B were. On the other hand if A is true you’ve shown B is true so \(\neg A \vee B\) is true in that case too. Because this is logically equivalent to \(A \implies B\), you’ve proved A implies B.
For any \(n\) and any WFFs \(\phi_1,\ldots,\phi_n\),
Strictly speaking something like \(\phi_1 \wedge \phi_2 \wedge \phi_3\) isn’t a WFF, but we know - from the associativity laws - that any two ways of adding brackets to make it into a WFF give logically equivalent WFFs.
The contrapositive of an implication \(A \implies B\) is by definition \(\neg B \implies \neg A\). For example, the contrapositive of “if it’s Monday, then it’s raining” is “if it’s not raining, then it’s not Monday.” The next result is that an implication and its contrapositive are logically equivalent.
Proposition. Let \(\phi\) and \(\psi\) be WFFs. Then
\[(\phi \implies \psi) \equiv (\neg \psi) \implies (\neg \phi).\]
Proof you can check the truth tables for these two statments, or you can do this:
\[\begin{align*} \phi \implies \psi & \equiv (\neg \phi) \vee \psi & \text{rewriting implies}\\ & \equiv \psi \vee (\neg \phi) & \text{commutativity} \\ &\equiv \neg (\neg \psi) \vee (\neg \phi) & \text{double negation} \\ &\equiv (\neg \psi) \implies (\neg \phi) & \text{rewriting implies} \end{align*}\]
Again this is very useful as a proof technique. If you want to prove \(A \implies B\), it is logically equivalent to prove the contrapositive \((\neg B) \implies (\neg A)\), and this is sometimes easier. An example is a statement like “\(x^2\) is an irrational number implies \(x\) is an irrational number”: the contrapositive, “\(x\) is rational implies \(x^2\) is rational”, is very easy to prove. There are further examples given in this blog post by Timothy Gowers.
Don’t confuse the contrapositive with the converse. The converse of \(\phi \implies \psi\) is \(\psi \implies \phi\), the two are not logically equivalent. (You should think of a truth assignment to show that \(p \implies q\) and \(q \implies p\) are not logically equivalent.)
Proposition: Let \(\phi\), \(\psi\), and \(\theta\) be WFFs. Then
Proof:
| \(\phi\) | \(\psi\) | \(\theta\) | \(\phi \wedge (\psi \vee \theta)\) | \((\phi \wedge \psi )\vee (\phi \wedge \theta)\) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | T | F | T | T |
| T | F | T | T | T |
| T | F | F | F | F |
| F | T | T | F | F |
| F | T | F | F | F |
| F | F | T | F | F |
| F | F | F | F | F |
| \(\phi\) | \(\psi\) | \(\theta\) | \(\phi \vee (\psi \wedge \theta)\) | \((\phi \vee \psi )\wedge (\phi \vee \theta)\) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | T | F | T | T |
| T | F | T | T | T |
| T | F | F | T | T |
| F | T | T | T | T |
| F | T | F | F | F |
| F | F | T | F | F |
| F | F | F | F | F |
The last two columns are the same in both cases, so the formulas are logically equivalent.
The negation of a statement asserts that the statement is false, and the negation of a WFF \(\phi\) is \(\neg \phi\). We are often interested in the negations of statements - for example, when we do proof by contradiction.
Logical equivalences can help to understand what it means for a statement to be false. We already know some useful ones, namely De Morgan’s laws:
and double negation:
\[\neg \neg \phi \equiv \phi.\]
The only connective we don’t know how to negate is implies.
Proposition. Let \(\phi\) and \(\psi\) be WFFs. Then
\[\neg (\phi \implies \psi) \equiv \phi \wedge \neg \psi\]
Proof. We’ve already seen that
\[(\phi \implies \psi) \equiv (\neg \phi) \vee \psi\]
Now just negate both sides, and use De Morgan’s laws and double negation: \[\begin{align*} \neg (\phi \implies \psi) &\equiv\neg ( (\neg \phi) \vee \psi) \\ & \equiv (\neg \neg \phi) \wedge (\neg \psi) & \text{De Morgan's laws} \\ & \equiv \phi \wedge \neg \psi & \text{Double negation} \end{align*}\]
One of the logical equivalences we proved was
\[(p \implies q) \equiv (\neg p) \vee q\]
which you could interpret as saying that we don’t really need the \(\implies\) connective: if you give me any WFF using \(\vee\), \(\wedge\), \(\implies\), and \(\neg\) I can convert it into a logically equivalent one that does not use \(\implies\) by replacing every occurrence of \(\phi \implies \psi\) with \(\neg \phi \vee \psi\).
This property is called adequacy, and we say a set of connectives is adequate if every WFF is logically equivalent to one using only the connectives from that set. For example, the argument above shows that \(\{\neg, \wedge, \vee\}\) is adequate.
In fact \(\{\wedge, \neg\}\) is adequate. We already know that every WFF is logically equivalent to one only using \(\neg\), \(\wedge\), and \(\vee\). By De Morgan’s laws,
\[\neg (\phi \vee \psi) \equiv (\neg \phi) \wedge (\neg \psi)\]
and so using double negation,
\[\phi \vee\psi\equiv\neg((\neg\phi) \wedge (\neg\psi)) \;\;\; (\dagger)\]
which means we can replace every occurrence of \(\phi\vee\psi\) in a WFF with the right hand side of this last equivalence, which only involves \(\neg\) and \(\wedge\).
Similarly we can use the other De Morgan law
\[\neg (\phi \wedge\psi) \equiv (\neg \phi) \vee (\neg\psi)\]
and double negation to get
\[\phi\wedge\psi \equiv \neg((\neg\phi)\vee(\neg\psi))\]
and so every WFF is equivalent to one only using \(\vee\) and \(\neg\).
Example. Consider
\[\phi = (p \implies (q \wedge r))\]
Let’s find a logically equivalent formula using only \(\neg\) and \(\vee\). First we get rid of the implies:
\[\begin{align*} p \implies (q \wedge r) & \equiv (\neg p) \vee (q \wedge r) \\ &\equiv (\neg p)\vee \neg ((\neg q) \vee (\neg r)) \end{align*}\]
using the \(\wedge\)-removal result \((\dagger)\) above.
Similarly we can show any WFF is logically equivalent to one using only \(\neg, \implies\): the required identities are
\[\begin{align*} \phi \vee\psi & \equiv (\neg \phi) \implies \psi \\ \phi \wedge \psi & \equiv \neg (\neg a \vee \neg b) \\ & \equiv \neg (a \implies \neg b) \end{align*}\]
It’s clear that we can’t go any further: it isn’t true that every WFF is equivalent to one using \(\vee\) only (any such formula is true when all its variables are true, so we can’t find one equivalent to \(\neg p\)) or using \(\wedge\) only (same argument) or \(\implies\) only (same argument).
There are other single connectives with the property that any WFF is logically equivalent to one using only that connective. For example, if we define \(p \uparrow q\) to have the same truth table as \(\neg (p \wedge q)\) (the “Sheffer stroke”, or NAND), and \(p \text{ NOR } q\) to have the truth table of \(\neg (p \vee q)\), it can be shown that both \(\{\uparrow \}\) and \(\{ \text{NOR}\}\) are adequate.
Why do we care about getting rid of connectives? Firstly it can be useful to be able to find logical equivalents to a WFF in simple standard forms, e.g. disjunctive normal form. Second, “logic gates” (electronic devices implementing logical connectives) are a fundamental part of digital circuit design. A computer chip is largely made up of many logic gates connected together. In the early days of digital electronics using only one type of logic gate helped make the design much easier. The Apollo guidance computer, used on the first ever moon landing, was built out of 6000 separate NOR gates - and no other kind of gate.
The WFFs we have studied so far only capture logical statements of a very simple form. For example, we can’t express statements like the following with a WFF:
These kind of statement are especially common in analysis, but they arise everywhere. Propositional calculus doesn’t have a way of talking about statements that depend on a parameter, and might be true for some values, or all values, or no values of that parameter. It also has no way to talk about functions or relations. The logical theory we’re going to learn about that can deal with statements like this is called first order logic or predicate calculus.
In propositional calculus we had WFFs. The corresponding thing in first order calculus is called a first order formula.
When we studied propositional calculus, we were able to give a precise definition of a WFF. Doing something similar in first order logic is much more complicated, so we won’t do that (if you want to see how, read Goldrei chapter 4 or take MATH0037 in year 3). Instead we are going to list the ingredients used to write first order formulas and give some examples.
Here is a simple example of a first order formula:
\[\forall x \exists y \; R(x,y)\]
The intended meaning of this is “for all \(x\), there exists a \(y\), such that \(x\) and \(y\) are related by the relation \(R\).” At the moment, this is like a WFF in that it isn’t true or false - we need more information (what sort of thing are the xs and ys? What is the relation R?) to decide that. This information is called an interpretation, and it will be discussed in the next video.
First order formulas are made up of:
The quantifiers \(\forall\) and \(\exists\) are known as the universal quantifier and the existential quantifier). Formulas that contain \(\forall x \; \ldots\) are interpreted to mean “for all x, …” and formulas that contain \(\exists x \; \ldots\) are interpreted to mean “there exists an x such that ….”
We write \(R(x,y)\) to indicate that \(x\) and \(y\) are related by some relation \(R\) instead of \(x \sim y\) because it is easier to generalize the former notation to relations involving different numbers of variables. For example, a one-variable relation \(R(x)\) is just a true or false property of a single thing \(x\) (e.g. “x is even”), and a three-variable relation \(R(x, y, z)\) is a true or false property of three things (e.g. “x+y equals z”).
The three statements at the start of this lecture correspond to first order formulas
Turning the first order formula into the statement in brackets is called giving an interpretation for the formula. That’s the subject of the next video.
A WFF isn’t true or false until you specify a truth assignment for its variables. Similarly, a first order formula isn’t true or false on its own. Before we can get a truth value we have to give an interpretation. First we have to give a set \(A\) (the domain of the interpretation) where the variables of the formula will come from, then we have to give a relation on \(A\) for each relation symbol in the formula.
Once we’ve done that, we can decide if the formula is true or false in that interpretation.
Here are some example interpretations of the first order formula \(\forall x \; \exists y \;\; R(x,y)\)
Here’s a slight variation on the formula we write before:
\[\exists y \forall x \; R(x,y)\]
Again, to give an interpretation we have to give a domain - a set \(A\) for the elements \(y\) and \(x\) to come from - and a relation \(R\) on \(A\). The interpreted statement will be true if and only if for every \(y \in A\) there exists an \(x \in A\) such that \(x\) is related to \(y\) by the relation \(R\).
Is this formula true in the following interpretations?
We already know how to determine the truth value in a particular interpretation of a formula just involving the logical connectives. The rules for deciding whether a formula containing a quantifier is true in an interpretation with domain \(A\) are:
Here are two first order formulas:
Let’s try and determine whether F1 and F2 are true in some interpretations.
Interpretation 1. \(A = \{0, 1, 2\}\), \(P(x, y)\) is interpreted as \(x < y\).
Interpretation 2. \(A = \{0, 1, 2\}\), \(P(x, y)\) is interpreted as \(x \leq y\).
Interpretation 3. \(A = \mathbb{N}\), \(P(x, y)\) is interpreted as \(x < y\).
It was quite awkward to determine truth or falsity of these formulas. One thing that would be helpful would be to transform them into equivalent, simpler formulas. We know about logically equivalent WFFs for propositional calculus, but right now we don’t know how to define logical equivalence in first order logic. That’s the subject of the next video.
Just as when we studied propositional calculus, there are distinct formulas of first order logic which are true in exactly the same interpretations, which is the idea the definition above captures. Logical equivalence has the same use as before: if you want to prove some statement is true, you can instead prove some logically equivalent statement, and this may be easier if the logically equivalent statement is somehow simpler or clearer.
Here’s a simple example and a non-example of logically equivalent statements.
Lemma:
Proof: \(\forall x \forall y P(x,y)\) is true in an interpretation \(\mathcal{A}\) iff all the interpreted statements \(P(a,b)\) for \(a, b \in A\) are true. This is the same collection of statements required to be true for \(\forall y \forall x P(x,y)\) to be true in that interpretation. So the two statements are logically equivalent.
For the second pair of formulas consider the interpretation where the variables range over the real numbers and \(P(x,y)\) is interpreted as \(x \leq y\). The interpretation \(\forall x \exists y : x \leq y\) is true, since whatever real number \(x\) is, \(y=x\) is another real number and \(x \leq y\). On the other hand the interpretation \(\exists y \forall x : x \leq y\) is false, because there is no real number \(y\) which is greater than or equal to every real number \(x\).
Let’s look at two more interesting equivalences. It’s often useful to ask, about a mathematical statements, “what would it mean for this statement not to be true?” e.g.
Continuity and limits are expressed using quantifiers, so to analyse this logically we need to be able to negate formulas of first order logic. Obviously you can just put a \(\neg\) in front of them to negate them, but a helpful solution will provide a logical equivalence that might actually be useful in understanding the negation of these statements.
Lemma: 1. \(\neg \forall x P(x) \equiv \exists x \neg P(x)\) 2. \(\neg \exists x P(x) \equiv \forall x \neg P(x)\)
Proof:
1. Fix an interpretation \(\mathcal{A}\). Then \(\forall x P(x)\) is true in this interpretation iff every statement \(P(a)\) for a in A is true. So this is false iff for at least one \(a\) in \(A\), \(P(a)\) is false. That’s precisely what is required for \(\exists x \neg P(x)\) to be true in the interpretation.
2. Fix an interpretation \(\mathcal{A}\). Then \(\exists x P(x)\) is true in this interpretation iff there is some \(a \in A\) such that \(P(a)\) is true. So \(\neg \exists x P(x)\) is true in this interpretation iff there is no \(a \in A\) such that \(P(a)\) is true, that is, for all \(a \in A\), \(\neg P(a)\) is true. This is exactly the requirement for \(\forall x \neg P(x)\) to be true in this interpretation. Therefore in any interpretation \(\neg \exists x P(x)\) is true iff \(\forall x \neg P(x)\) is true, and the two statements are logically equivalent.
Informally, what this lemma says is
You can use the lemma together with what we already know about negating logical expressions to negate any quantified statement.
This video is about some examples of producing useful logical equivalents for negations of quantified formulas. We’re going to use real-life examples from bits of mathematics you may not have met yet, but this won’t be a problem: our negation procedure doesn’t require understanding anything about the meaning of the formulas!
The statement “every value the function \(f: \mathbb{R}\to \mathbb{R}\) takes is less than 10.” can be written
\[\forall x : f(x) < 10.\]
This is an interpretation of a formula
\[\forall x : P(x).\]
Let’s negate it, using the negation of quantifiers lemma:
\[\neg \forall x P(x) \equiv \exists x \neg P(x)\]
Passing back to our interpretation, this says \(\exists x : \neg (f(x) < 10)\) which is the same as \(\exists x : f(x) \geq 10\).
Consider the statement “the function \(f: \mathbb{R}\to \mathbb{R}\) is bounded”, which we could write as
\[\exists M \forall x : |f(x)| \leq M.\]
This is an interpretation of a formula
\[\exists M \forall x : P(x, M).\]
Let’s negate it.
\[\begin{align*} \neg \exists M \forall x \; P(x, M) & \equiv \forall M \neg \forall x \; P(x,M) \\ &\equiv \forall M \exists x \; \neg P(x,M) \end{align*}\]
so “\(f\) is not bounded” is \(\forall M \exists x \; \neg ( |f(x)| \leq M )\), or equivalently, \(\forall M \exists x \; |f(x)| > M\).
Goldbach’s conjecture is that “every integer larger than 2 is either odd, or it is a sum of two primes”. We could write this as
\[\forall n : \operatorname{Odd}(n) \vee \exists p \exists q \operatorname{Prime}(p) \wedge \operatorname{Prime}(q) \wedge (p+q=n)\]
This is an interpretation of a formula
\[\forall n O(n) \vee \exists p \exists q \; P(p) \wedge P(q) \wedge R(p,q,n).\]
Let’s negate it.
\[\begin{gather*} \neg \forall n O(n) \vee \exists p \exists q \; P(p) \wedge P(q) \wedge R(p,q,n) \\ \equiv \exists n \neg ( O(n) \vee \exists p \exists q \; P(p) \wedge P(q) \wedge R(p,q,n) ) \\ \equiv \exists n\; (\neg O(n)) \wedge (\neg \exists p \exists q \; P(p) \wedge P(q) \wedge R(p,q,n)) \\ \equiv \exists n\; (\neg O(n)) \wedge (\forall p \neg \exists q \; P(p) \wedge P(q) \wedge R(p,q,n)) \\ \equiv \exists n\; (\neg O(n)) \wedge (\forall p \forall q \; \neg (P(p) \wedge P(q) \wedge R(p,q,n))) \\ \equiv \exists n\; (\neg O(n)) \wedge (\forall p \forall q \; (\neg P(p)) \vee (\neg Q(p)) \vee (\neg R(p,q,n))) \end{gather*}\]