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.

Exercises

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

way:

1. The names 0, 1 are terms.

2. If t1 , t2 are terms, then the expressions (t1 + t2 ) and (t1 — t2 ) are also

terms.

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

arithmetic

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)

Exercises

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

41

42 / The Logic of Atomic Sentences