4.2: Translating to First-Order Logic

We now have all of the pieces of . Translating assertions (no matter how complicated) from English to mathematical notation will only be a matter of knowing the right way to combine predicates, constants, quantifiers, connectives, and sets. Consider these assertions:

5. Every coin in my pocket is a dime.
6. Some coin on the table is a dime.
7. Not all the coins in my pocket are dimes.
8. None of the coins on the table are dimes.

In providing a symbolization key, we need to specify \(\mathcal{U}\). Since we are not talking about anything besides coins, we may let \(\mathcal{U}\) be the set of all coins. (It is not necessary to include all coins in \(\mathcal{U}\), but, since we are talking about the coins in my pocket and the coins on the table, \(\mathcal{U}\) must at least contain all of those coins.) Since we are not talking about any specific coins, we do not need to define any constants. Since we will be explicitly talking about the coins in my pocket and the coins on the table, it will be helpful to have these defined as sets. The symbolization key also needs to say something about dimes; let’s do this with a predicate. So we define this key:

\(\mathcal{U}\): The set of all coins.

\(P\): The set of all coins in my pocket.

\(T\): The set of all coins on the table.

\(D(x)\) is a dime.

Assertion 5. is most naturally translated with a universal quantifier. It talks about all of the coins in my pocket (that is, the elements of the set \(P\)). It means that, for any coin in my pocket, that coin is a dime. So we can translate it as \(\forall p\in P, D(p)\).

Assertion 6. says there is some coin on the table, such that the coin is a dime. So we translate it as \(\exists t \in T, D(t)\).

Assertion 7. can be paraphrased as, “It is not the case that every coin in my pocket is a dime.” So we can translate it as \(\neg(\forall p \in P, D(p))\). This is simply the negation of .

Assertion 8. can be paraphrased as, “It is not the case that some coin on the table is a dime.” This can be translated as \(\neg\bigl(\exists t\in T, D(t) \bigr)\). It is the negation of Assertion 6.

Remark \(4.2.1\).

Alternatively, we could have defined a set \(D\), the set of all dimes, instead of the predicate \(D(x)\). In this case:

• Assertion 5. would be translated as \(\forall p \in P, \ p \in D\).
• Assertion 6. would be translated as \(\exists t \in T, \ t \in D\).
• Assertion 7. would be translated as \(\neg (\forall p \in P, \ p \in D)\).
• Assertion 8. would be translated as \(\neg (\exists t \in T, \ t \in D)\).

Either approach is perfectly legitimate.

However, if we need to quantify over dimes, then it is much better to use a set than a predicate. For example, let’s symbolize the assertion “Every dime is in my pocket.”

• If \(D\) is the set of all dimes, we can write: \(\forall d \in D, \ d \in P\).
• It is less straightforward if we use the predicate \(D(x)\), because we cannot directly say "for all dimes” (since the set of all dimes is not available). The translation must consider all coins, and then say that the ones that are dimes are in my pocket: \(\forall x, \bigl( D(x) \Rightarrow d \in P \bigr)\).

For this reason (and others), mathematicians tend to use sets, rather than predicates, and we will do the same.

Remark \(4.2.2\).

If we had defined the predicate \(P(x)\) (for “\(x\) is in my pocket”) instead of the corresponding set \(P\), we would have needed to translate as \(\forall x, \bigl( P(x) \implies D(x) \bigr)\): that is, “for any coin, if it is in my pocket, then it is a dime.” Since the assertion is about coins that are both in my pocket and that are dimes, it might be tempting to translate it using \(\eand\). However, the assertion \(\forall x, \bigl(P(x) \eand D(x) \bigr)\) would mean that everything in is both in my pocket and a dime: All the coins that exist are dimes in my pocket. This is would be a crazy thing to say, and it means something very different than . However, this issue is completely avoided when we use sets. Thus, defining \(P\) to be a set, rather than a predicate, is the best approach in this problem (and similarly for \(T\)).

Example \(4.2.3\).

We can now translate the deduction from page , the one that motivated the need for quantifiers:

Merlin is a wizard. All wizards wear funny hats.
\(\therefore\) Merlin wears a funny hat.

\(\mathcal{U}\): The set of all people.
\(W\): The set of all wizards.
\(H\): The set of all people who wear a funny hat.
\(m\): Merlin

Translating, we get:

Hypotheses: \[\begin{aligned}
&m \in W \\
&\forall w \in W,(w \in H)
\end{aligned}\]

Conclusion: \(m \in H\)

This captures the structure that was left out when we translated the deduction into , and this is a valid deduction in . We will be able to prove it rigorously after we have discussed the introduction and elimination rules for \(\forall\) (and \(\exists\)) in Section \(4.4\).

Exercise \(4.2.4\).

Using the given symbolization key, translate each English-language assertion into First-Order Logic.

\(\mathcal{U}\): The set of all animals.
\(A\): The set of all alligators.
\(R\): The set of all reptiles.
\(Z\): The set of all animals who live at the zoo.
\(M\): The set of all monkeys.
\(x\) ♥ \(y\): \(x\) loves \(y\).
\(a\): Amos
\(b\): Bouncer
\(c\): Cleo

1. Amos, Bouncer, and Cleo all live at the zoo.
2. Bouncer is a reptile, but not an alligator.
3. If Cleo loves Bouncer, then Bouncer is a monkey.
4. If both Bouncer and Cleo are alligators, then Amos loves them both.
5. Some reptile lives at the zoo.
6. Every alligator is a reptile.
7. Every animal that lives at the zoo is either a monkey or an alligator.
8. There are reptiles which are not alligators.
9. Cleo loves a reptile.
10. Bouncer loves all the monkeys that live at the zoo.
11. All the monkeys that Amos loves love him back.
12. If any animal is an alligator, then it is a reptile.
13. Every monkey that Cleo loves is also loved by Amos.
14. There is a monkey that loves Bouncer, but Bouncer does not reciprocate this love.

Exercise \(4.2.5\).

Using the given symbolization key, translate each English-language assertion into First-Order Logic.

\(\mathcal{U}\): The set of all animals.
\(D\): The set of all dogs.
\(S\): The set of all reptiles.
\(Z\): The set of all animals who like to swim.
\(x\) \(L\) \(y\): \(x\) is larger than \(y\).
\(b\): Bertie
\(e\): Emerson
\(f\): Fergis

1. Bertie is a dog who likes to swim.
2. Bertie, Emerson, and Fergis are all dogs.
3. Emerson is larger than Bertie, and Fergis is larger than Emerson.
4. All dogs like to swim.
5. Every animal that likes to swim is a dog.
6. There is a dog that is larger than Emerson.
7. No animal that likes to swim is larger than Emerson.
8. Any animal that does not like to swim is larger than Bertie.
9. There is no animal that is larger than Bertie, but smaller than Emerson.
10. There is no dog that is larger than Bertie, but smaller than Emerson.
11. No dog is larger than itself.

Exercise \(4.2.6\).

For each deduction, write a symbolization key and translate the deduction into First-Oder Logic.

1. Nothing on my desk escapes my attention. There is a computer on my desk. Therefore, there is a computer that does not escape my attention.
2. All my dreams are black and white. Old TV shows are in black and white. Therefore, some of my dreams are old TV shows.
3. Neither Holmes nor Watson has been to Australia. A person could see a kangaroo only if they had been to Australia or to a zoo. Although Watson has not seen a kangaroo, Holmes has. Therefore, Holmes has been to a zoo.
4. No one expects the Spanish Inquisition. No one knows the troubles I’ve seen. Therefore, anyone who expects the Spanish Inquisition knows the troubles I’ve seen.
5. Every antelope is bigger than a bread box. The thing I am thinking of is no bigger than a bread box, and it is either an antelope or a cantaloupe. Therefore, I am thinking of a cantaloupe.

4.2A. Multiple Quantifiers

Example \(4.2.7\).

Consider the following symbolization key and the assertions that follow it:

\(\mathcal{U}\): The set of all people.
\(D\): The set of all of Karl's friends.
\(S\): The set of all Imre's neighbours.
\(x\) \(L\) \(y\): \(x\) likes \(y\).
\(i\): Imre.
\(k\): Karl.

9. All of Imre’s neighbours like all of Karl’s friends.
10. At least one of Karl’s friends likes at least one of Imre’s neighbours.
11. All of Karl’s friends like at least one of Imre’s neighbours.
12. There is one of Imre’s neighbours, who is a friend of Karl and who likes all of Imre’s neighbours.

Solution

Beginning to translate Assertion 9., we start with all of Imre’s neighbours: \(\forall n \in N.\) Now we would like to say \(n \mathrel{L}f\), where \(f\) represents every one of Karl’s friends. Before we can do this, we need to introduce the variable \(f\), and give it the desired meaning and the appropriate quantifier: \(\forall f \in F\). Thus, Assertion 9. can be translated as \(\forall n \in N, \bigl(\forall f \in F, (n \mathrel{L}f)\bigr)\).

For Assertion 10., we start with at least one of Karl’s friends. Another way to say this is that there is some friend of Karl’s: \(\exists f \in F\). Similarly, we now need to introduce at least one of Imre’s neighbours: \(\exists n \in N\). The completed translation is \(\exists f \in F, \bigl(\exists n \in N, (f \mathrel{L}n)\bigr)\bigr)\).

For Assertion 11., we start with all of Karl’s friends: \(\forall f \in F\). Now we need at least one of Imre’s neighbours: \(\exists n \in N\). The completed translation is \(\forall f\in F, \bigl(\exists n\in N, (f \mathrel{L} n)\bigr)\).

Finally, for Assertion 12., we start with one of Imre’s neighbours: \(\exists n \in N\). Now we need this person to be a friend of Karl: \(n \in F\). For the next part of the sentence, we need all of Imre’s neighbours. It is tempting to write \(\forall n \in N\), but we have already used the variable \(n\) for a particular one of Imre’s neighbours, so we cannot use it again here to mean something else. Let’s use \(n'\) instead: \(\forall n' \in N\). We are now ready to translate Assertion 12: \[\exists n \in N,\left(n \in F \&\left[\forall n^{\prime} \in N,\left(n L n^{\prime}\right)\right]\right) .\]
(Alternatively, we could have used \(n_{1}\) and \(n_{2}\) instead of \(n\) and \(n^{\prime}\).)

When symbolizing assertions with multiple quantifiers, it is best to proceed by small steps. Figure out who is being discussed in the sentence, and what quantifiers are required to introduce these variables. Paraphrase the English assertion so that the logical structure is readily symbolized in . Then translate bit by bit, replacing the daunting task of translating a long assertion with the simpler task of translating shorter formulas.

Remark \(4.2.8\).

The equals sign “\(=\)” is a part of every symbolization key (even though we do not bother to include it explicitly). It is a binary predicate, and, as you would expect, “\(x = y\)” means “\(x\) is equal to \(y\).” This does not mean merely that \(x\) and \(y\) look very much alike, or that they are indistinguishable, or that they have all of the same properties. Rather, it means that \(x\) and \(y\) are (different) names for the same object.

Warning.

It is important to put quantifiers in the correct order. For example, consider the following assertions (with \(\mathcal{U}\)) being the set of all objects):

13. \(\forall x,\bigl( \exists y, (x=y)\bigr)\)
14. \(\exists y, \bigl(\forall x, (x=y)\bigr)\)

They are exactly the same, except for which of \(\forall x\) and \(\exists y\) is first, and which is second. is obviously true: “For every thing, there is something that it is equal to.” (Namely, every thing is equal to itself.) But says: “There is some thing (let us call it \(y\)), such that everything is equal to \(y\).” There is no such \(y\), so this is obviously false.

Exercise \(4.2.9\).

Using the symbolization key from Exercise \(4.2.5\), translate each English-language assertion into First-Order Logic.

1. If there is a dog larger than Fergis, then there is a dog larger than Emerson.
2. Every dog is larger than some dog.
3. There is an animal that is smaller than every dog.
4. If there is an animal that is larger than every dog, then Emerson does not like to swim.
5. For every dog that likes to swim, there is a smaller dog that does not like them.
6. Every dog that likes to swim is larger than every dog that does not like them.
7. Some animal is larger than all of the dogs that like to swim.
8. If there is a dog that does not like to swim, than there is a dog that is larger than every animal that likes to swim.

Exercise \(4.2.10\) (harder).

Using the given symbolization key, translate each English-language assertion into First-Order Logic.

\(\mathcal{U}\): The set of all people.
\(D\): The set of all ballet dancers.
\(F\): The set of all females.
\(M\): The set of all males.
\(x\) \(C\) \(y\): \(x\) is a child of \(y\).
\(x\) \(S\) \(y\): \(x\) is a sibling of \(y\).
\(e\): Elmer
\(j\): Jane
\(p\): Patrick

1. Everyone who dances ballet is the child of someone who dances ballet.
2. Every man who dances ballet is the child of someone who dances ballet.
3. Everyone who dances ballet has a sister who also dances ballet.
4. Jane is an aunt.
5. Patrick’s brothers have no children.

4.2B. Uniqueness

Saying “there is a unique so-and-so” means not only that there is a so-and-so, but also that there is only one of them—there are not two different so-and-so’s. For example, to say that “there is a unique person who owes Hikaru money” means

some person owes Hikaru and no other person owes Hikaru.

This translates to \[\exists h\in H, \bigl( \forall y, (y \neq h \Rightarrow y \notin H) \bigr);\]
or, equivalently, \[\exists h\in H, \bigl( \forall y, ( y \in H \Rightarrow y =h ) \bigr).\]
Unfortunately, both of these are quite complicated expressions (and are examples of “multiple quantifiers,” because they use both \(\exists\) and \(\forall\)). To simplify the situation, mathematicians introduce a special notation: \[\text { " } \exists ! x \text { " means "there is a unique } x \text {, such that..." }\]

If \(X\) is any set, then "\(\exists ! x \in X\)" means
"there is a unique \(x\) in \(X\), such that . . ."

For example, \(\exists!\, h, h \in H\) means exactly the same thing as the complicated expression above.

If we add

\(R\): The set of people who are rich.

to our symbolization key, we can translate “There is a unique rich person who owes Hikaru money.” Namely, it translates as: \[\exists!\, r \in R, (r \in H).\]

Exercise \(4.2.11\).

Using the given symbolization key, translate each English-language assertion into First-Order Logic.

\(\mathcal{U}\): The set of all creatures.
\(H\): The set of all horses.
\(W\): The set of all creatures with wings.
\(B\): The set of all creatures in Farmer Brown's field.

1. There is a unique winged creature that is in Farmer Brown’s field.
2. If some horse has wings, then there is a unique horse that is in Farmer Brown’s field.
3. If there is a horse that is in Farmer Brown’s field, then there is a unique horse that is in Farmer Brown’s and has wings.

Answer

Add texts here. Do not delete this text first.

4.2C. Bound Variables

Recall that an assertion is a statement that is either true or false. For example, consider the following symbolization key:

\(\mathcal{U}\): The set of all students.
\(M(x)\): \(x\) is taking a math class.
\(a\): Anna

Then:

• \(M(a)\) is an assertion. Either Anna is taking a math class, or she is not.
• \(M(x)\) is not an assertion. The letter \(x\) is a variable, not any particular object. (We call \(x\) a free variable.) If we plug in a particular value for \(x\) (such as \(a\)), then we will have an assertion. However, until some value is plugged in for \(x\), we cannot say whether the expression is true or false. So the expression is not an assertion if the variable remains free.
• \(\exists x, M(x)\) and \(\forall x, M(x)\) are assertions. The letter \(x\) is a variable in both of these expressions, but it is no longer free, because it is acted on by the quantifier. (We call \(x\) a bound variable.)

An important principle of is that, in an assertion, each variable must be bound by some quantifier: \[\text { Assertions cannot have free variables. }\]

Exercise \(4.2.12\).

Suppose that \(p\) is a constant, but all other lower-case letters represent variables. For each of the following, a. does it have a free variable? b. is it an assertion?

1. \(\forall x\in X, (x \mathrel{L} y)\)
2. \((p \in S) \eand \exists y \in Y, (y \mathrel{T} p)\)
3. \(\forall v \in V, \bigl( (\exists!\, y \in Y, v \mathrel{R} y) \Rightarrow (v=z) \bigr)\)
4. \(y \in Y \eand \bigl(\forall x \in X, (x \in T) \bigr)\)
5. \((p \mathrel{L} p) \Rightarrow \exists x, (x \mathrel{L} p)\)
6. \(\forall x \in X, (x \mathrel{L} x)\)

Answer

Add texts here. Do not delete this text first.