Predicates and quantifiers

The most famous valid argument in the subject comes out invalid in the system built so far, and that is not a small defect.

"All men are mortal. Socrates is a man. Therefore Socrates is mortal." Propositional logic sees three sentences with no connective in any of them, so it assigns three unrelated letters and finds a valuation making the first two true and the third false. The verdict is invalid, and it is wrong. The failure is not in the rules of the previous lessons but in the language: the form that makes the argument work lies inside the sentences, where atoms have no parts to look at. This lesson opens them up, and the price is a much richer notation that will take the next four lessons to pay off.

Inside an atomic sentence

Split a simple sentence into what it is about and what it says. "Socrates is a man" mentions one individual and applies one property. Write individuals with lower-case letters near the start of the alphabet, called names or constants: $s$ for Socrates, $a$ for the alloy. Write properties with capital letters, called predicates: $M$ for being a man, $F$ for being mortal.

An atomic formula is a predicate followed by the right number of names, so "Socrates is a man" is $M s$ and "Socrates is mortal" is $F s$ . The number a predicate takes is fixed, and the choice of letter is arbitrary, though a mnemonic saves effort later.

Predicates of more than one place are what make the notation powerful, and they arrive in the next lesson: $L a b$ for " $a$ loves $b$ ", $G a b$ for " $a$ is greater than $b$ ". For now everything is one-place, which is enough for the syllogism and for most of the traps.

Note what has already changed. Propositional logic could see that "Socrates is a man" and "Plato is a man" were different sentences and nothing else; the notation now shows they share a predicate, and that shared structure is what an argument about all men can grab hold of.

Variables and the domain

To say something about every individual rather than a named one, a placeholder is needed. Variables are lower-case letters from the end of the alphabet, $x$ , $y$ , $z$ , and $F x$ on its own is not a statement: it has no truth value until something fills $x$ .

Filling it is what the quantifiers do. The universal quantifier $\forall x$ says the formula after it holds for every individual, and the existential quantifier $\exists x$ says it holds for at least one. So $\forall x F x$ says everything is mortal and $\exists x F x$ says something is.

Every quantified statement is implicitly about some collection, the domain of discourse, and the same formula changes truth value as the domain changes. $\forall x F x$ is false if the domain is all things and true if the domain is all people. Fixing the domain is part of stating the problem, and forgetting to fix it is a standard source of fake disagreements. When the domain is everything, restrictions must be written into the formula itself, which is what the next section is about.

"At least one" is the exact reading of $\exists$ . It does not mean exactly one, and it does not suggest that not all. $\exists x F x$ is true when everything is $F$ , in the same way that $P \lor Q$ is true when both hold, and for the same reason: logic takes the weaker reading and makes you write the stronger one out.

The two translations

Nearly everything in this lesson rests on two patterns, and getting them the wrong way round is the single most common error in the subject.

All $F$ are $G$ is $\forall x (F x \to G x)$ : take anything at all, and if it is $F$ then it is $G$ . Some $F$ are $G$ is $\exists x (F x \land G x)$ : there is something that is both.

The connectives cannot be swapped, and it pays to see exactly what goes wrong. Writing $\forall x (F x \land G x)$ for "all ravens are black" claims that everything in the domain is a raven and black, which makes a claim about ravens into a claim about the universe. Writing $\exists x (F x \to G x)$ for "some ravens are black" is worse in a subtler way: a conditional is true whenever its antecedent is false, so if the domain contains a single non-raven the formula is true, whatever colour ravens are. Neither error changes the sentence slightly; both destroy it.

The reason for the asymmetry is that $\forall$ needs to let irrelevant things through, and the conditional does that by being vacuously true of them, while $\exists$ needs to pin down one thing that satisfies both conditions, and only a conjunction does that.

Example. Translate, with the domain being everything: "Every alloy containing nickel is magnetic" and "some alloys containing nickel are not magnetic".

With $A x$ for being an alloy containing nickel and $M x$ for being magnetic, the first is $\forall x (A x \to M x)$ and the second is $\exists x (A x \land \neg M x)$ . Note that the second is the exact denial of the first: it says there is a counterexample, which is precisely what refuting a universal claim requires, and austenitic stainless steels are that counterexample in the real world.

Now you. Translate "no reptile is warm-blooded" and "some reptiles are venomous".

Answer

With $R x$ for reptile, $W x$ for warm-blooded, $V x$ for venomous: the first is $\forall x (R x \to \neg W x)$ , which can equally be written $\neg \exists x (R x \land W x)$ , and the second is $\exists x (R x \land V x)$ . The two forms of the first say the same thing, and the next lesson gives the law that converts one into the other.

The four categorical forms

Aristotle worked with four sentence forms, and they are still the best drill for translation. They are labelled with vowels from the Latin affirmo and nego.

Form	English	Translation
A	All $F$ are $G$	$\forall x (F x \to G x)$
E	No $F$ is $G$	$\forall x (F x \to \neg G x)$
I	Some $F$ is $G$	$\exists x (F x \land G x)$
O	Some $F$ is not $G$	$\exists x (F x \land \neg G x)$

A and O are exact denials of each other, and so are E and I. That is the whole content of the traditional square of opposition, minus the parts that depend on the assumption discussed below. Recognising which of the four an English sentence is saying is most of the work of translating it, and the misleading English is worth watching: "all that glitters is not gold" is an E claim in intent and an A claim with a negation in form, and only context resolves it.

Now the syllogism. "All men are mortal. Socrates is a man. So Socrates is mortal" becomes $\forall x (M x \to F x)$ , $M s$ , therefore $F s$ , and the validity is visible: the universal premise applies to Socrates in particular, giving $M s \to F s$ , and modus ponens finishes it. The eleventh lesson makes that instantiation an official rule.

Existential import, and a count

Aristotle's system assumes that the terms in a syllogism are not empty: talk of ravens presupposes that ravens exist. Modern logic drops that assumption, so $\forall x (F x \to G x)$ comes out true when nothing is $F$ at all. "Every unicorn in this room is on fire" is true, vacuously, in a room with no unicorns.

This is not a quibble, and the difference can be counted. A categorical syllogism has three terms and two premises, each premise and the conclusion being one of the four forms, arranged in one of four figures, which gives $4 \times 4 \times 4 \times 4 = 256$ possible forms. Under modern semantics, exactly 15 are valid. Under Aristotle's assumption that every term is non-empty, 24 are, the extra 9 being exactly those that draw a "some" conclusion from two universal premises.

The most useful of the nine is easy to see: from "all $F$ are $G$ " and "all $G$ are $H$ " it concludes "some $F$ is $H$ ". If there are no $F$ s, both premises hold vacuously and the conclusion is false, so the inference needs the extra assumption. Modern logic makes you state it, writing $\exists x F x$ as an extra premise when the argument depends on it, which is the honest arrangement: the assumption is often true and it should be visible.

Example. Is "all trespassers will be prosecuted, and nobody has trespassed, therefore somebody will be prosecuted" valid?

No. The first premise is $\forall x (T x \to P x)$ and the second is $\neg \exists x T x$ . In a domain where nothing is a trespasser, the first premise is vacuously true, the second is true, and $\exists x P x$ can be false. The premises are consistent and the conclusion fails, which is exactly the situation Aristotle's assumption rules out by fiat and modern logic allows.

Now you. Under modern semantics, is "all $F$ are $G$ , all $G$ are $H$ , therefore some $F$ is $H$ " valid, and what single premise would make it so?

Answer

It is invalid: an empty $F$ makes both premises vacuously true and the conclusion false. Adding $\exists x F x$ repairs it, since then some individual is $F$ , and the two conditionals carry it through $G$ to $H$ .

Scope, free and bound

A quantifier governs a stretch of formula, its scope, marked by brackets exactly as in propositional logic. In $\forall x (F x \to G x)$ the scope is the whole conditional. In $\forall x F x \to G x$ it is $F x$ alone, and the $x$ in $G x$ is left dangling.

An occurrence of a variable inside the scope of a quantifier using that variable is bound; one that is not is free. A formula with a free variable is not a statement and has no truth value, the way $x > 3$ has none until $x$ is fixed. A formula with no free variables is a sentence, and only sentences are true or false. Checking that a translation has no free variables is the fastest error check there is, and it catches the misplaced bracket above immediately.

Placing the negation is the other half of scope. $\neg \forall x F x$ says not everything is $F$ ; $\forall x \neg F x$ says everything fails to be $F$ . The first is far weaker, and mixing them up turns "not all snakes are venomous" into "no snake is venomous". The rule that relates them is the subject of the next lesson.

Example. Translate "not every alloy containing nickel is magnetic" and say how it relates to the earlier translation.

It is $\neg \forall x (A x \to M x)$ , the denial of the earlier A form. It is equivalent to $\exists x (A x \land \neg M x)$ , the O form, which is the useful shape because it says what to go and look for: one alloy, containing nickel, not magnetic.

Now you. Which of $\neg \exists x (R x \land V x)$ and $\exists x (R x \land \neg V x)$ says "no reptile is venomous"?

Answer

The first. The second says some reptile is not venomous, which is far weaker and is compatible with many venomous ones. The pair is the E and O forms, and confusing them is the same error as confusing "none" with "not all".

What this buys and what it costs

The language now has names, predicates, variables, two quantifiers and the whole propositional apparatus on top. The syllogism is valid in it, the four categorical forms are expressible, and the empty-term assumption that Aristotle left implicit is now something you write down or leave out deliberately.

The cost arrives with the next lesson. As soon as predicates take two places, a formula can carry two quantifiers, and their order changes what is said: everyone loving someone is a different claim from someone being loved by everyone. English handles that ambiguity badly, mathematics depends on it completely, and the notation is about to make it exact.