. 8
( 107 .)


Which of the following atomic sentences of the functional language can be translated into atomic
sentences of the relational language? Translate those that can be and explain the problem with
those that can™t.

4. father(melanie) = jon
5. father(melanie) = father(claire)
6. Taller(father(claire), father(jon))

When we add connectives and quanti¬ers to the language, we will be able to translate freely
back and forth between the functional and relational languages.

1.16 Let™s suppose that everyone has a favorite movie star. Given this assumption, make up a ¬rst-
 order language for talking about people and their favorite movie stars. Use a function symbol
that allows you to refer to an individual™s favorite actor, plus a relation symbol that allows
you to say that one person is a better actor than another. Explain the interpretation of your
function and relation symbols, and then use your language to express the following claims:
1. Harrison is Nancy™s favorite actor.
2. Nancy™s favorite actor is better than Sean.
3. Nancy™s favorite actor is better than Max™s.
4. Claire™s favorite actor™s favorite actor is Brad.
5. Sean is his own favorite actor.

1.17 Make up a ¬rst-order language for talking about people and their relative heights. Instead of
 using relation symbols like Taller, however, use a function symbol that allows you to refer to
people™s heights, plus the relation symbols = and <. Explain the interpretation of your function
symbol, and then use your language to express the following two claims:
1. George is taller than Sam.
2. Sam and Mary are the same height.

Do you see any problem with this function symbol? If so, explain the problem. [Hint: What
happens if you apply the function symbol twice?]

1.18 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 predicates and function symbols you use.
1. Indiana™s capital is larger than California™s.
2. Hitler™s mistress died in 1945.
3. Max shook Claire™s father™s hand.
4. Max is his father™s son.
5. John and Nancy™s eldest child is younger than Jon and Mary Ellen™s.

Chapter 1
The first-order language of set theory / 37

Section 1.6
The ¬rst-order language of set theory
Fol was initially developed for use in mathematics, and consequently the
most familiar ¬rst-order languages are those associated with various branches
of mathematics. One of the most common of these is the language of set
theory. This language has only two predicates, both binary. The ¬rst is the predicates of set theory
identity symbol, =, which we have already encountered, and the second is the
symbol ∈, for set membership.
It is standard to use in¬x notation for both of these predicates. Thus, in
set theory, atomic sentences are always formed by placing individual constants
on either side of one of the two predicates. This allows us to make identity
claims, of the form a = b, and membership claims, of the form a ∈ b (where
a and b are individual constants).
A sentence of the form a ∈ b is true if and only if the thing named by b is membership (∈)
a set, and the thing named by a is a member of that set. For example, suppose
a names the number 2 and b names the set {2, 4, 6}. Then the following table
tells us which membership claims made up using these names are true and
which are false.2
a ∈ a false
a ∈ b true
b ∈ a false
b ∈ b false
Notice that there is one striking di¬erence between the atomic sentences
of set theory and the atomic sentences of the blocks language. In the blocks
language, you can have a sentence, like LeftOf(a, b), that is true in a world,
but which can be made false simply by moving one of the objects. Moving
an object does not change the way the name works, but it can turn a true
sentence into a false one, just as the sentence Claire is sitting down can go
from true to false in virtue of Claire™s standing up.
In set theory, we won™t ¬nd this sort of thing happening. Here, the analog
of a world is just a domain of objects and sets. For example, our domain
might consist of all natural numbers, sets of natural numbers, sets of sets of
natural numbers, and so forth. The di¬erence between these “worlds” and
those of Tarski™s World is that the truth or falsity of the atomic sentences is
determined entirely once the reference of the names is ¬xed. There is nothing
that corresponds to moving the blocks around. Thus if the universe contains
2 Forthe purposes of this discussion we are assuming that numbers are not sets, and that
sets can contain either numbers or other sets as members.

Section 1.6
38 / Atomic Sentences

the objects 2 and {2, 4, 6}, and if the names a and b are assigned to them,
then the atomic sentences must get the values indicated in the previous table.
The only way those values can change is if the names name di¬erent things.
Identity claims also work this way, both in set theory and in Tarski™s World.


1.19 Which of the following atomic sentences in the ¬rst-order language of set theory are true
‚ and which are false? We use, in addition to a and b as above, the name c for 6 and d for
{2, 7, {2, 4, 6}}.
1. a ∈ c
2. a ∈ d
3. b ∈ c
4. b ∈ d
5. c ∈ d
6. c ∈ b

To answer this exercise, submit a Tarski™s World sentence ¬le with an uppercase T or F in each
sentence slot to indicate your assessment.

Section 1.7
The ¬rst-order language of arithmetic

While neither the blocks language as implemented in Tarski™s World nor the
language of set theory has function symbols, there are languages that use
them extensively. One such ¬rst-order language is the language of arithmetic.
This language allows us to express statements about the natural numbers
0, 1, 2, 3, . . . , and the usual operations of addition and multiplication.
There are several more or less equivalent ways of setting up this language.
The one we will use has two names, 0 and 1, two binary relation symbols, =
predicates (=, <) and
functions (+, —) of and <, and two binary function symbols, + and —. The atomic sentences are
arithmetic those that can be built up out of these symbols. We will use in¬x notation
both for the relation symbols and the function symbols.
Notice that there are in¬nitely many di¬erent terms in this language (for
example, 0, 1, (1 + 1), ((1 + 1) + 1), (((1 + 1) + 1) + 1), . . . ), and so an in¬nite
number of atomic sentences. Our list also shows that every natural number is
named by some term of the language. This raises the question of how we can
specify the set of terms in a precise way. We can™t list them all explicitly, since

Chapter 1
The first-order language of arithmetic / 39

there are too many. The way we get around this is by using what is known as
an inductive de¬nition.
De¬nition The terms of ¬rst-order arithmetic are formed in the following terms of arithmetic
1. The names 0, 1 are terms.

2. If t1 , t2 are terms, then the expressions (t1 + t2 ) and (t1 — t2 ) are also
3. Nothing is a term unless it can be obtained by repeated application of
(1) and (2).

We should point out that this de¬nition does indeed allow the function
symbols to be applied over and over. Thus, (1 + 1) is a term by clause 2 and
the fact that 1 is a term. In which case ((1 + 1) — (1 + 1)) is also a term, again
by clause 2. And so forth.
The third clause in the above de¬nition is not as straightforward as one
might want, since the phrase “can be obtained by repeated application of” is
a bit vague. In Chapter 16, we will see how to give de¬nitions like the above
in a more satisfactory way, one that avoids this vague clause.
The atomic sentences in the language of ¬rst-order arithmetic are those atomic sentences of
that can be formed from the terms and the two binary predicate symbols, =
and <. So, for example, the fol version of 1 times 1 is less than 1 plus 1 is
the following:
(1 — 1) < (1 + 1)


1.20 Show that the following expressions are terms in the ¬rst-order language of arithmetic. Do this
 by explaining which clauses of the de¬nition are applied and in what order. What numbers do
they refer to?
1. (0 + 0)
2. (0 + (1 — 0))
3. ((1 + 1) + ((1 + 1) — (1 + 1)))
4. (((1 — 1) — 1) — 1)

1.21 1.22
Find a way to express the fact that three Show that there are in¬nitely many
is less than four using the ¬rst-order lan- terms in the ¬rst-order language of
guage of arithmetic. arithmetic referring to the number one.

Section 1.7
40 / Atomic Sentences

Section 1.8
Alternative notation
As we said before, fol is like a family of languages. But, as if that were not
enough diversity, even the very same ¬rst-order language comes in a variety
of dialects. Indeed, almost no two logic books use exactly the same notational
conventions in writing ¬rst-order sentences. For this reason, it is important
to have some familiarity with the di¬erent dialects”the di¬erent notational
conventions”and to be able to translate smoothly between them. At the end
of most chapters, we discuss common notational di¬erences that you are likely
to encounter.
Some notational di¬erences, though not many, occur even at the level of
atomic sentences. For example, some authors insist on putting parentheses
around atomic sentences whose binary predicates are in in¬x position. So
(a = b) is used rather than a = b. By contrast, some authors omit parentheses
surrounding the argument positions (and the commas between them) when
the predicate is in pre¬x position. These authors use Rab instead of R(a, b).
We have opted for the latter simply because we use predicates made up of
several letters, and the parentheses make it clear where the predicate ends
and the arguments begin: Cubed is not nearly as perspicuous as Cube(d).
What is important in these choices is that sentences should be unambigu-
ous and easy to read. Typically, the ¬rst aim requires parentheses to be used in
one way or another, while the second suggests using no more than is necessary.

Chapter 1
Chapter 2

The Logic of Atomic Sentences
A major concern in logic is the concept of logical consequence: When does
one sentence, statement, or claim follow logically from others? In fact, one of
the main motivations in the design of fol was to make logical consequence
as perspicuous as possible. It was thought that by avoiding the ambiguities
and complexities of ordinary language, we would be able to recognize the
consequences of our claims more easily. This is, to a certain extent, true; but
it is also true that we should be able to recognize the consequences of our
claims whether or not they are expressed in fol.
In this chapter, we will explain what we mean by “logical consequence,” or
equivalently, what we mean when we say that an argument is “logically valid.”
This is a fairly simple concept to understand, but it can also be devilishly dif-
¬cult to apply in speci¬c cases. Indeed, in mathematics there are many, many
examples where we do not know whether a given claim is a consequence of
other known truths. Mathematicians may work for years or decades trying
to answer such questions. After explaining the notion of consequence, we will
describe the principal techniques for showing that a claim is or is not a con-
sequence of other claims, and begin presenting what is known as a formal
system of deduction, a system that allows us to show that a sentence of fol is
a consequence of others. We will continue developing this system as we learn
more about fol in later chapters.

Section 2.1
Valid and sound arguments
Just what do we mean by logical consequence? Or rather, since this phrase
is sometimes used in quite di¬erent contexts, what does a logician mean by
logical consequence?
A few examples will help. First, let™s say that an argument is any series arguments, premises,
and conclusions
of statements in which one (called the conclusion) is meant to follow from, or
be supported by, the others (called the premises). Don™t think of two people
arguing back and forth, but of one person trying to convince another of some
conclusion on the basis of mutually accepted premises. Arguments in our
sense may appear as part of the more disagreeable sort of “arguments””
the kind parents have with their children”but our arguments also appear

42 / The Logic of Atomic Sentences


. 8
( 107 .)