1 Logic 1.10 Interpretations 1.12 Negation

1.11 First order equivalences

Definition 1.11.1.

Two first order formulas $F_{1}$ and $F_{2}$ are called logically equivalent if and only if, in every interpretation, $F_{1}$ and $F_{2}$ have the same truth value. We write $F_{1}\equiv F_{2}$ if $F_{1}$ and $F_{2}$ are logically equivalent.

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.

1.11.1 Example of logically equivalent statements

Here’s a simple example and a non-example of logically equivalent statements.

Lemma 1.11.1.

1.

$\forall x\forall y\;P(x,y)\equiv\forall y\forall x\;P(x,y)$
2.

$\forall x\exists y\;P(x,y)\not\equiv\exists y\forall x\;P(x,y)$

Proof.

1.

$\forall x\forall y\;P(x,y)$ is true in an interpretation if and only if all of the interpreted statements $P(a,b)$ for $a, b$ in the domain are true. This is exactly 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.
2.

Consider the interpretation with domain the real numbers and with $P(x,y)$ interpreted as $x\leqslant y$ . The interpretation $\forall x\exists y\;x\leqslant y$ is true, since whatever real number $x$ is, $y=x$ is another real number and $x\leqslant y$ . On the other hand the interpretation $\exists y\forall x\;x\leqslant y$ is false, because there is no real number $y$ which is greater than or equal to every real number $x$ . ∎

1.11.2 Logical equivalents for negated quantifiers

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.

•

what does it mean for a function not to be continuous?
•

what does it mean for a function not to have a limit as $x\to 0$ ?

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.11.2.

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.

$\forall x\;P(x)$ is true in an interpretation if and only if every statement $P(a)$ for $a$ in the domain of the interpretation is true. So the formula is false in the interpretation if not all of the statements $P(a)$ is true, that is, for at least one $a$ in the domain $P(a)$ is false. That’s precisely what is required for $\exists x\;\neg P(x)$ to be true in the interpretation.
2.

$\exists x\;P(x)$ is true in an interpretation if and only if there is some $a$ in the domain of the interpretation such that $P(a)$ is true. So $\neg\exists x\;P(x)$ is true in this interpretation if and only if 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 if and only if $\forall x\;\neg P(x)$ is true, and the two statements are logically equivalent. ∎

You can use the lemma in this section together with what we already know about negating logical expressions to negate any quantified statement.