Identity, number and descriptions

Nothing in the language so far can say that there are two of something, and the reason is a detail about variables that is easy to miss.

$\exists x F x \land \exists y F y$ looks as though it asserts two $F$ s and does not. Two variables may take the same value, so a domain containing a single object satisfies it. Counting, superlatives, "only", and the word "the" all turn out to need one further predicate, and adding it completes the language that mathematics and most careful writing actually use.

The identity predicate

Add a two-place predicate written $x = y$ , with $x \neq y$ as shorthand for $\neg x = y$ . Unlike every other predicate, its extension is not free to vary: in every interpretation, $a = b$ is true exactly when $a$ and $b$ name the same object in the domain. That is what makes it a logical symbol rather than a piece of vocabulary.

Two rules govern it in derivations. Identity introduction: $a = a$ may be written on any line, with no premises, since every object is itself. Identity elimination, also called Leibniz's law: from $a = b$ and any formula containing $a$ , write the formula with $b$ substituted for some or all occurrences of $a$ . If Hesperus is Phosphorus, whatever is true of one is true of the other.

The word "same" is doing exact work here and is worth separating from ordinary use. Two cars off the same production line are "the same" colloquially and are two objects, so $a \neq b$ . Identity in logic means one object with two names, which is why identity statements can be informative: "Hesperus is Phosphorus" told astronomers that the morning star and the evening star are one planet, Venus, and Frege built his 1892 theory of sense and reference on exactly that puzzle.

Counting

With identity, number becomes expressible, one quantity at a time.

At least two $F$ s: $\exists x \exists y (F x \land F y \land x \neq y)$ . The final clause is the entire content, since without it the formula says only that something is $F$ .

At most one $F$ : $\forall x \forall y ((F x \land F y) \to x = y)$ . Any two $F$ s turn out to be the same one. Note this is true when there are no $F$ s at all, which is correct: at most one includes none.

Exactly one $F$ : the conjunction of "at least one" and "at most one", or more compactly

\exists x (F x \land \forall y (F y \to y = x))

which says something is $F$ and everything that is $F$ is that thing. This is used often enough to have its own abbreviation, $\exists! x F x$ .

Exactly two $F$ s: $\exists x \exists y (F x \land F y \land x \neq y \land \forall z (F z \to (z = x \lor z = y)))$ . The pattern is clear and so is its cost: each further number needs a longer formula, and "exactly ten" is unpleasant to write. The language can express every particular finite number and has no way to talk about number in general, which is what arithmetic is for.

Example. Translate "Mars has exactly two moons".

With the domain everything and $M x$ for being a moon of Mars,

\exists x \exists y (M x \land M y \land x \neq y \land \forall z (M z \to (z = x \lor z = y)))

The claim is true: Phobos and Deimos, both found by Asaph Hall in August 1877, are the only two. Notice how the last clause does all the closing off. Without it the formula would say at least two, which Jupiter and its dozens of moons would satisfy just as well.

Now you. Translate "there is at most one solution", using $S x$ for being a solution.

Answer

\forall x \forall y ((S x \land S y) \to x = y)

It is true when there is no solution, which is what "at most" should mean. To rule that out as well you would conjoin $\exists x S x$ , giving exactly one.

Only, and superlatives

Identity is also what turns exclusivity into a formula. "Only Socrates is wise" says Socrates is wise and nothing else is: $W s \land \forall x (W x \to x = s)$ . The second conjunct is the same closing-off move as in "exactly one", with a name in place of the variable.

"Everyone except Ann passed" needs both directions: $\forall x (x \neq a \to P x) \land \neg P a$ . Leaving off the second conjunct is the usual error, and it loses the part of the English that people actually care about.

Superlatives are comparisons closed off with identity. "Socrates is the wisest" is $\forall x (x \neq s \to W s x)$ , taking $W x y$ as " $x$ is wiser than $y$ ": wiser than everything other than himself. The exception clause is needed because nothing is wiser than itself, and a formula reading $\forall x W s x$ would be false for that reason alone.

Russell on "the"

Definite descriptions are the classic application, and the analysis is due to Bertrand Russell, in "On Denoting", published in Mind in 1905.

The puzzle: "the present King of France is bald" appears to be about somebody, and France has had no king since 1848. If the phrase names nothing, the sentence should be neither true nor false, which breaks the assumption that every sentence has a truth value. If it is false, then its negation, "the present King of France is not bald", should be true, and that seems just as bad.

Russell's move was to deny that "the King of France" is a name at all. The sentence is a quantified claim with three parts: something is King of France, at most one thing is, and that thing is bald.

\exists x (K x \land \forall y (K y \to y = x) \land B x)

Now the sentence is simply false, because its first conjunct is, and no gap in the truth values opens. Nothing has gone missing: the existence claim that the English quietly carries has been written out where it can be inspected.

The negation puzzle dissolves into a scope distinction the notation makes visible. Putting the negation inside gives $\exists x (K x \land \forall y (K y \to y = x) \land \neg B x)$ , which says there is such a king and he is not bald, and is false. Putting it outside gives $\neg \exists x (K x \land \dots \land B x)$ , which says it is not the case that there is a unique bald king, and is true. English writes both as "the present King of France is not bald" and the formulas cannot be confused, which is the clearest example in the subject of formalisation resolving an ambiguity rather than merely recording one.

Example. Translate "the author of Waverley was Scottish", and say what makes it true or false.

With $A x$ for being an author of Waverley and $S x$ for Scottish,

\exists x (A x \land \forall y (A y \to y = x) \land S x)

It is true, since exactly one person wrote Waverley, Walter Scott, who published it anonymously in 1814, and he was Scottish. Had the novel been written by two people in collaboration, the second conjunct would fail and the sentence would come out false rather than half true, which is Russell's analysis behaving as designed.

Now you. Translate "only Ann and Ben passed", using $P x$ and the names $a$ and $b$ .

Answer

P a \land P b \land \forall x (P x \to (x = a \lor x = b))

The first two conjuncts say they passed and the third closes off the list. Whether $a \neq b$ needs stating depends on the reading; the English clearly implies it, so a careful translation adds it.

What identity does not fix

First-order logic with identity is the standard language of mathematics, and it has a definite ceiling that is worth knowing rather than discovering later.

It can say "there are exactly seven $F$ s" for any particular number, with a formula that grows with the number. It cannot say "there are finitely many $F$ s". That is not a failure of ingenuity: it follows from the compactness theorem, which says that if every finite subset of a set of sentences has a model then the whole set does. Suppose some sentence were true in exactly the finite domains. Add to it the sentences "there are at least two things", "there are at least three things", and so on. Every finite subset of that collection is satisfiable, by a domain big enough for the largest one mentioned, so compactness says the whole infinite collection has a model, and that model is infinite while satisfying a sentence supposed to be true only in finite domains. The assumption fails, so no such sentence exists.

The same argument shows that first-order logic cannot pin down the natural numbers uniquely: any first-order theory of arithmetic with an infinite model has models of every infinite size, by the Löwenheim-Skolem theorems. These are limits on the language rather than on the proof rules, and they are the reason mathematicians reach for second-order formulations when they want to characterise a structure exactly, at the cost of losing completeness.

Example. Why can "there are exactly three $F$ s" be written but not "there are finitely many $F$ s"?

Because the first is a single claim about a fixed number and can be written out in full with three existentials and a closing clause, while the second is an infinite disjunction, "exactly none or exactly one or exactly two, and so on", and a formula must be finite. The compactness argument above shows that no finite formula can do the same work by a cleverer route.

Now you. A theory says the domain has at least $n$ members, for every $n$ . Can it have a finite model?

Answer

No. A domain of $k$ members falsifies the sentence demanding at least $k + 1$ , so no finite domain satisfies them all. Every finite subset of the theory does have a model, which is exactly the situation compactness is about: it guarantees an infinite model exists, and it is the step used in the argument above.

Where the machinery ends

The language is now complete for the purposes of this course: connectives, quantifiers, relations, identity, and a proof system that is sound and complete for all of it.

What has not yet been shown is the machinery doing the job it was built for. Mathematicians do not write derivations in this notation; they write proofs in English, using a handful of recurring strategies. Every one of those strategies is an instance of a rule established in the last six lessons, and seeing that correspondence is what makes the formal work pay. That is the next lesson.