. 7
( 107 .)


t is earlier than t t<t Earlier-than for times.
x was hungry at time t Hungry(x, t)
x was angry at time t Angry(x, t)
x owned y at time t Owned(x, y, t)
x gave y to z at t Gave(x, y, z, t)
x fed y at time t Fed(x, y, t)

1.9 We will be giving a number of problems that use the symbols explained in Table 1.2. Start a
‚ new sentence ¬le in Tarski™s World and translate the following into fol, using the names and
predicates listed in the table. (You will have to type the names and predicates in by hand.
Make sure you type them exactly as they appear in the table; for example, use 2:00, not 2:00
pm or 2 pm.) All references to times are assumed to be to times on January 2, 2001.
1. Claire owned Folly at 2 pm.
2. Claire gave Pris to Max at 2:05 pm.
3. Max is a student.
4. Claire fed Carl at 2 pm.
5. Folly belonged to Max at 3:05 pm.
6. 2:00 pm is earlier than 2:05 pm.

Name and submit your ¬le in the usual way.

Chapter 1
Function symbols / 31

1.10 Translate the following into natural sounding, colloquial English, consulting Table 1.2.
 1. Owned(max, scru¬y, 2:00)
2. Fed(max, scru¬y, 2:30)
3. Gave(max, scru¬y, claire, 3:00)
4. 2:00 < 2:00
1.11 For each sentence in the following list, suggest a translation into an atomic sentence of fol. In
 addition to giving the translation, explain what kinds of objects your names refer to and the
intended meaning of the predicate you use.
1. Max shook hands with Claire.
2. Max shook hands with Claire yesterday.
3. AIDS is less contagious than in¬‚uenza.
4. Spain is between France and Portugal in size.
5. Misery loves company.

Section 1.5
Function symbols
Some ¬rst-order languages have, in addition to names and predicates, other
expressions that can appear in atomic sentences. These expressions are called
function symbols. Function symbols allow us to form name-like terms from function symbols
names and other name-like terms. They allow us to express, using atomic
sentences, complex claims that could not be perspicuously expressed using
just names and predicates. Some English examples will help clarify this.
English has many sorts of noun phrases, expressions that can be combined
with a verb phrase to get a sentence. Besides names like Max and Claire,
other noun phrases include expressions like Max™s father, Claire™s mother,
Every girl who knows Max, No boy who knows Claire, Someone and so forth.
Each of these combines with a singular verb phrase such as likes unbuttered
popcorn to make a sentence. But notice that the sentences that result have
very di¬erent logical properties. For example,
Claire™s mother likes unbuttered popcorn
implies that someone likes unbuttered popcorn, while
No boy who knows Claire likes unbuttered popcorn
does not.
Since these noun phrases have such di¬erent logical properties, they are terms
treated di¬erently in fol. Those that intuitively refer to an individual are

Section 1.5
32 / Atomic Sentences

called “terms,” and behave like the individual constants we have already dis-
cussed. In fact, individual constants are the simplest terms, and more complex
terms are built from them using function symbols. Noun phrases like No boy
who knows Claire are handled with very di¬erent devices, known as quanti-
¬ers, which we will discuss later.
The fol analog of the noun phrase Max™s father is the term father(max).
It is formed by putting a function symbol, father, in front of the individual
constant max. The result is a complex term that we use to refer to the father
complex terms
of the person referred to by the name max. Similarly, we can put the function
symbol mother together with the name claire and get the term mother(claire),
which functions pretty much like the English term Claire™s mother.
We can repeat this construction as many times as we like, forming more
and more complex terms:
The ¬rst of these refers to Max™s paternal grandfather, the second to Claire™s
paternal grandmother, and so forth.
These function symbols are called unary function symbols, because, like
unary predicates, they take one argument. The resulting terms function just
like names, and can be used in forming atomic sentences. For instance, the
fol sentence
Taller(father(max), max)
says that Max™s father is taller than Max. Thus, in a language containing
function symbols, the de¬nition of atomic sentence needs to be modi¬ed to
allow complex terms to appear in the argument positions in addition to names.
Students often confuse function symbols with predicates, because both
function symbols vs.
predicates take terms as arguments. But there is a big di¬erence. When you combine a
unary function symbol with a term you do not get a sentence, but another
term: something that refers (or should refer) to an object of some sort. This is
why function symbols can be reapplied over and over again. As we have seen,
the following makes perfectly good sense:
This, on the other hand, is total nonsense:
To help prevent this confusion, we will always capitalize predicates of fol and
leave function symbols and names in lower case.

Chapter 1
Function symbols / 33

Besides unary function symbols, fol allows function symbols of any ar-
ity. Thus, for example, we can have binary function symbols. Simple English arity of function
counterparts of binary function symbols are hard to come up with, but they
are quite common in mathematics. For instance, we might have a function
symbol sum that combines with two terms, t1 and t2 , to give a new term,
sum(t1 , t2 ), which refers to the sum of the numbers referred to by t1 and t2 .
Then the complex term sum(3, 5) would give us another way of referring to
8. In a later section, we will introduce a function symbol to denote addition,
but we will use in¬x notation, rather than pre¬x notation. Thus 3 + 5 will be
used instead of sum(3, 5).
In fol, just as we assume that every name refers to an actual object,
we also assume that every complex term refers to exactly one object. This
is a somewhat arti¬cial assumption, since many function-like expressions in
English don™t always work this way. Though we may assume that


refers to an actual (deceased) individual”one of Max™s great-grandmothers”
there may be other uses of these function symbols that don™t seem to give
us genuinely referring expressions. For example, perhaps the complex terms
mother(adam) and mother(eve) fail to refer to any individuals, if Adam and Eve
were in fact the ¬rst people. And certainly the complex term mother(3) doesn™t
refer to anything, since the number three has no mother. When designing a
¬rst-order language with function symbols, you should try to ensure that your
complex terms always refer to unique, existing individuals.
The blocks world language as it is implemented in Tarski™s World does not functions symbols for
blocks language
contain function symbols, but we could easily extend the language to include
some. Suppose for example we introduced the function expressions fm, bm, lm
and rm, that allowed us to form complex terms like:


We could interpret these function symbols so that, for example, fm(a)
refers to the frontmost block in the same column as a. Thus, if there are
several blocks in the column with a, then fm(a) refers to the one closest to
you. If a is the only block in the column, or is the frontmost in its column,
then fm(a) would refer to a. Analogously, bm, lm and rm could be interpreted
to mean backmost, leftmost and rightmost, respectively.
With this interpretation, the term lm(bm(c)) would refer to the leftmost
block in the same row as the backmost block in the same column as c. The

Section 1.5
34 / Atomic Sentences

atomic sentence Larger(lm(bm(c)), c) would then be true if and only if this
block is larger than c.
Notice that in this expanded language, the sentence lm(bm(c)) = bm(lm(c))
is not always true. (Can you think of an example where it is false?) On the
other hand, fm(fm(a)) = fm(a) is always true. Can you think of any other
atomic sentences using these function symbols that are always true? How
about sentences that are always false?


In a language with function symbols,

—¦ Complex terms are typically formed by putting a function symbol of
arity n in front of n terms (simple or complex).

—¦ Complex terms are used just like names (simple terms) in forming
atomic sentences.

—¦ In fol, complex terms are assumed to refer to one and only one object.


1.12 Express in English the claims made by the following sentences of fol as clearly as you can.
 You should try to make your English sentences as natural as possible. All the sentences are,
by the way, true.
1. Taller(father(claire), father(max))
2. john = father(max)
3. Taller(claire, mother(mother(claire)))
4. Taller(mother(mother(max)), mother(father(max)))
5. mother(melanie) = mother(claire)
1.13 Assume that we have expanded the blocks language to include the function symbols fm, bm, lm
 and rm described earlier. Then the following formulas would all be sentences of the language:
1. Tet(lm(e))
2. fm(c) = c
3. bm(b) = bm(e)
4. FrontOf(fm(e), e)
5. LeftOf(fm(b), b)

Chapter 1
Function symbols / 35

6. SameRow(rm(c), c)
7. bm(lm(c)) = lm(bm(c))
8. SameShape(lm(b), bm(rm(e)))
9. d = lm(fm(rm(bm(d))))
10. Between(b, lm(b), rm(b))

Fill in the following table with true™s and false™s according to whether the indicated sentence
is true or false in the indicated world. Since Tarski™s World does not understand the function
symbols, you will not be able to check your answers. We have ¬lled in a few of the entries for
you. Turn in the completed table to your instructor.

Leibniz™s Bolzano™s Boole™s Wittgenstein™s
1. true
5. false
6. true
8. false

1.14 As you probably noticed in doing Exercise 1.13, three of the sentences came out true in all
‚ four worlds. It turns out that one of these three cannot be falsi¬ed in any world, because of
the meanings of the predicates and function symbols it contains. Your goal in this problem is
to build a world in which all of the other sentences in Exercise 1.13 come out false. When you
have found such a world, submit it as World 1.14.

1.15 Suppose we have two ¬rst-order languages for talking about fathers. The ¬rst, which we™ll
 call the functional language, contains the names claire, melanie, and jon, the function symbol
father, and the predicates = and Taller. The second language, which we will call the relational
language, has the same names, no function symbols, and the binary predicates =, Taller, and
FatherOf, where FatherOf(c, b) means that c is the father of b. Translate the following atomic
sentences from the relational language into the functional language. Be careful. Some atomic
sentences, such as claire = claire, are in both languages! Such a sentence counts as a translation
of itself.
1. FatherOf(jon, claire)
2. FatherOf(jon, melanie)

Section 1.5
36 / Atomic Sentences

3. Taller(claire, melanie)


. 7
( 107 .)