# 4.1

# Identity in Logic

In module 3, we learned $PL$, a relatively rich language that allows us to talk about objects and their properties. Here we will further enrich it by introducing the identity symbol $=$.

#### § 1 Limitation of PL

Consider this sentence:

- Pavel owes money to everyone else.

Let the UD be people; this will allow us to translate ``everyone'' as a universal quantifier. Let \(Oxy\) mean ``\(x\) owes money to \(y\),'' and let \(p\) mean Pavel. Now we can symbolize sentence ef{else1} as \(\forall x Opx\). Unfortunately, this translation has some odd consequences. It says that Pavel owes money to every member of the UD, including Pavel; it entails that Pavel owes money to himself. However, sentence ef{else1} does not say that Pavel owes money to himself; he owes money to everyone else. This is a problem, because \(\forall x Opx\) is the best translation we can give of this sentence into QL.

The solution is to add another symbol to QL. The symbol \(=\) is a two-place predicate. Since it has a special logical meaning, we write it a bit differently: For two terms \(t_1\) and \(t_2\), \(t_1=t_2\) is an atomic formula.

The predicate \(x=y\) means ``\(x\) is identical to \(y\).'' This does not mean merely that \(x\) and \(y\) are indistinguishable or that all of the same predicates are true of them. Rather, it means that \(x\) and \(y\) are the very same thing.

When we write \(x \neq y\), we mean that \(x\) and \(y\) are not identical. There is no reason to introduce this as an additional predicate. Instead, \(x \neq y\) is an abbreviation of \(\neg x = y\). $\neg x = y$ might look a bit funny, and you might be tempted to write $\neg (x = y)$, but that's technically incorrect. Keep in mind that '=' is really just a special symbol for a predicate - other syntactical rules governing predicates apply to it as well. Just as we don't write $\neg (Ixy)$, we also don't add parentheses to $\neg x = y$. Also don't forget that the negation is not attached to the the variables - neither the variables ('x' and 'y') nor the identity symbol '=' is a by itself a statement in QL.

Now suppose we want to symbolize this sentence:

- Pavel is Mister Checkov.

Let the constant \(c\) mean Mister Checkov. The sentence above can be symbolized as \(p=c\). This means that the constants \(p\) and \(c\) both refer to the same guy.

This is all well and good, but how does it help with sentence ' Pavel owes money to everyone else.'? That sentence can be paraphrased as, ``Everyone who is not Pavel is owed money by Pavel.'' This is a sentence structure we already know how to symbolize: ``For all \(x\), if \(x\) is not Pavel, then \(x\) is owed money by Pavel.'' In QL with identity, this becomes \(\forall x (x\neq p \to Opx)\).

In addition to sentences that use the word ``else,'' identity will be helpful when symbolizing some sentences that contain the words ``besides'' and ``only.'' Consider these examples:

- No one besides Pavel owes money to Hikaru
- Only Pavel owes Hikaru money.

We add the constant \(h\), which means Hikaru.

'No one besides Pavel owes money to Hikaru.' can be paraphrased as, ``No one who is not Pavel owes money to Hikaru.'' This can be translated as \(\neg\exists x(x\neq p \wedge Oxh)\).

'Only Pavel owes Hikaru money.' can be paraphrased as, ``Pavel owes Hikaru and no one besides Pavel owes Hikaru money.'' We have already translated one of the conjuncts, and the other is straightforward. The sentence becomes \(Oph \wedge \neg\exists x(x\neq p \wedge Oxh)\).

#### § 2 Expressing Specific Quantities in Logic

We can also use identity to say how many things there are of a particular kind. For example, consider these sentences:

$$\text{1. There is at least one apple on the table.}$$

$$\text{2. There are at least two apples on the table.}$$

$$\text{3. There are at least three apples on the table.}$$

Let UD: {x| x is on the table}, which reads the domain of discourse is the set that includes 'all x is such that x is on the table', and let \(Ax\) mean ``\(x\) is an apple.''

Sentence 1 does not require identity. It can be translated adequately as \(\exists x Ax\): There is some apple on the table---perhaps many, but at least one.

It might be tempting to also translate sentence 2 without identity. Yet consider the sentence \(\exists x \exists y(Ax \wedge Ay)\). It means that there is some apple \(x\) in the UD and some apple \(y\) in the UD. Since nothing precludes \(x\) and \(y\) from picking out the same member of the UD, this would be true even if there were only one apple. In order to make sure that there are two different apples, we need an identity predicate. Sentence 2 needs to say that the two apples that exist are not identical, so it can be translated as \(\exists x \exists y(Ax \wedge Ay \wedge x\neq y)\).

Sentence 3 requires talking about three different apples. It can be translated as \(\exists x \exists y\exists z(Ax \wedge Ay \wedge Az \wedge x\neq y \wedge y\neq z \wedge x \neq z)\).

Continuing in this way, we could translate ``There are at least n apples on the table.'' for any n.

Now consider these sentences

$$\text{A. There is at most one apple on the table.}$$

$$\text{B. There are at most two apples on the table.}$$

Sentence A can be paraphrased as, ``It is not the case that there are at least two apples on the table.'' This is just the negation of sentence B: $$\neg \exists x \exists y(Ax \wedge Ay \wedge x \neq y)$$

Sentence A can also be approached in another way. It means that any apples that there are on the table must be the selfsame apple, so it can be translated as $\forall x\forall y[(Ax \wedge Ay) \to x=y]$. The two translations are logically equivalent, so both are correct.

In a similar way, sentence B can be translated in two equivalent ways. It can be paraphrased as, ``It is not the case that there are three or more distinct apples'', so it can be translated as the negation of sentence 3. Using universal quantifiers, it can also be translated as $$\forall x\forall y\forall z[(Ax \wedge Ay \wedge Az) \to (x=y \vee x=z \vee y=z)].$$

The examples above are sentences about apples, but the logical structure of the sentences translates mathematical inequalities like $a\geq 3$, $a \leq 2$, and so on. We also want to be able to translate statements of equality which say exactly how many things there are. For example:

$$\text{C. There is exactly one apple on the table.}$$

$$\text{D. There are exactly two apples on the table.}$$

Sentence C can be paraphrased as, ``There is at least one apple on the table, and there is at most one apple on the table.'' This is just the conjunction of sentence 1 and sentence A $\exists x Ax \wedge \forall x\forall y [(Ax \wedge Ay) \to x=y]$. This is a somewhat complicated way of going about it. It is perhaps more straightforward to paraphrase sentence A as ``There is a thing which is the only apple on the table.'' Thought of in this way, the sentence can be translated $\exists x[Ax \wedge \neg\exists y(Ay \wedge x\neq y)]$.

Similarly, sentence B may be paraphrased as, ``There are two different apples on the table, and these are the only apples on the table.'' This can be translated as $\exists x\exists y[Ax \wedge Ay \wedge x\neq y \wedge \neg\exists z(Az \wedge x\neq z \wedge y\neq z)]$.

Finally, consider this sentence:

$$\text{E. There are at most two things on the table.}$$

It might be tempting to add a predicate so that $Tx$ would mean ``$x$ is a thing on the table.'' However, this is unnecessary. Since the UD is the set of things on the table, all members of the UD are on the table. If we want to talk about a thing on the table, we need only use a quantifier. Sentence E can be symbolized like sentence D (which said that there were at most two apples), but leaving out the predicate entirely. That is, sentence E can be translated as $\forall x \forall y \forall z(x=y \vee x=z \vee y=z)$.

#### § 3 Complex Statements Involving Identity

There are occasions (for instance, in quizzes and tests) where we have to talk about not only the quantity of some objects, but also their relations to something else. Consider the following statement:

$$\text{At least two apples are next to some oranges.}$$

How should we proceed? It might help to first change the English sentence to a more logic-friendly form before tackling the QL. To begin we note that we are essentially talking about three objects: unique orange A, unique orange B, and at least one orange. Thus, we can say. Since we are committing into their existence, we can say:

$$\text{There exist at least two apples and at least one orange such that these apples are next to these oranges.}$$

From here, we can begin our translation by writing out the quantifiers and assigning variables to things we want to talk about:

$$\exists x \exists y \exists z \text{ x is an apple y is an apple, x and y are not the same, and they are next to some orange z}$$

From this 'pseudo-QL' statement, it is a small step to complete the translation, by adding the predicates:

$$\exists x \exists y \exists z (Ax \wedge By \wedge x \neq y \wedge Oz \wedge Nxz \wedge Nyz)$$

Note that there is some ambiguity in the English: our QL statement says that there is some orange that is next to both of these apples. But the original statement does not necessarily say that - it could mean that for each of these apples, it is next to some orange, but these are not necessarily the same one. Apple A can be next to orange B but not orange C, and apple D can be next to C but not B. To accommodate this possibility, we can add another existential quantifier to allow the interpretation that there are two different oranges

$$\exists x \exists y \exists z \exists w (Ax \wedge By \wedge x \neq y \wedge Oz \wedge Nxz \wedge Nyw \wedge Ow)$$

Here we don't say that $z \neq w$ because we don't know for sure if they are not the same; we allow the possibility. Note that we can also translate the same sentence conditionally:

$$\exists x \exists y [Ax \wedge By \wedge x \neq y \wedge \forall z ((z = x \vee z =y) \to \exists w (Ow \wedge Nzw) )]$$

This one says: there are at least two distinct oranges such that if we have anything that is identical to one of them, then it will be next to some orange. Clearly, no one talks this way in real life ( except for pretentious logicians) but it expresses the same idea.