ńņš. 4 |

Languages

As noted in the Introduction, propositional logic has obvious deļ¬-

ciencies as a tool for mathematical reasoning. First-order logic remedies

enough of these to be adequate for formalizing most ordinary mathe-

matics. It does have enough in common with propositional logic to let

us recycle some of the material in Chapters 1ā“4.

A few informal words about how ļ¬rst-order languages work are in

order. In mathematics one often deals with structures consisting of

a set of elements plus various operations on them or relations among

them. To cite three common examples, a group is a set of elements

plus a binary operation on these elements satisfying certain conditions,

a ļ¬eld is a set of elements plus two binary operations on these elements

satisfying certain conditions, and a graph is a set of elements plus a

binary relation with certain properties. In most such cases, one fre-

quently uses symbols naming the operations or relations in question,

symbols for variables which range over the set of elements, symbols

for logical connectives such as not and for all, plus auxiliary symbols

such as parentheses, to write formulas which express some fact about

the structure in question. For example, if (G, Ā·) is a group, one might

express the associative law by writing something like

āx āy āz x Ā· (y Ā· z) = (x Ā· y) Ā· z ,

it being understood that the variables range over the set G of group

elements. A formal language to do as much will require some or all of

these: symbols for various logical notions and for variables, some for

functions or relations, plus auxiliary symbols. It will also be necessary

to specify rules for putting the symbols together to make formulas, for

interpreting the meaning and determining the truth of these formulas,

and for making inferences in deductions.

For a concrete example, consider elementary number theory. The

set of elements under discussion is the set of natural numbers N =

{ 0, 1, 2, 3, 4, . . . }. One might need symbols or names for certain inter-

esting numbers, say 0 and 1; for variables over N such as n and x; for

functions on N, say Ā· and +; and for relations, say =, <, and |. In

addition, one is likely to need symbols for punctuation, such as ( and

23

24 5. LANGUAGES

); for logical connectives, such as Ā¬ and ā’; and for quantiļ¬ers, such

as ā (āfor allā) and ā (āthere existsā). A statement of mathematical

English such as āFor all n and m, if n divides m, then n is less than or

equal to mā can then be written as a cool formula like

ānām (n | m ā’ (n < m ā§ n = m)) .

The extra power of ļ¬rst-order logic comes at a price: greater com-

plexity. First, there are many ļ¬rst-order languages one might wish to

use, practically one for each subject, or even problem, in mathematics.1

We will set up our deļ¬nitions and general results, however, to apply to

a wide range of them.2

As with LP , our formal language for propositional logic, ļ¬rst-order

languages are deļ¬ned by specifying their symbols and how these may

be assembled into formulas.

Definition 5.1. The symbols of a ļ¬rst-order language L include:

1. Parentheses: ( and ).

Connectives: Ā¬ and ā’.

2.

Quantiļ¬er: ā.

3.

4. Variables: v0, v1, v2, . . . , vn , . . .

5. Equality: =.

6. A (possibly empty) set of constant symbols.

For each k ā„ 1, a (possibly empty) set of k-place function sym-

7.

bols.

8. For each k ā„ 1, a (possibly empty) set of k-place relation (or

predicate) symbols.

The symbols described in parts 1ā“5 are the logical symbols of L, shared

by every ļ¬rst-order language, and the rest are the non-logical symbols

of L, which usually depend on what the languageā™s intended use.

Note. It is possible to deļ¬ne ļ¬rst-order languages without =, so

= is considered a non-logical symbol by many authors. While such lan-

guages have some uses, they are uncommon in ordinary mathematics.

Observe that any ļ¬rst-order language L has countably many logical

symbols. It may have uncountably many symbols if it has uncountably

many non-logical symbols. Unless explicitly stated otherwise, we will

1

It is possible to formalize almost all of mathematics in a single ļ¬rst-order

language, like that of set theory or category theory. However, trying to actually do

most mathematics in such a language is so hard as to be pointless.

2

Speciļ¬cally, to countable one-sorted ļ¬rst-order languages with equality.

5. LANGUAGES 25

assume that every ļ¬rst-order language we encounter has only count-

ably many non-logical symbols. Most of the results we will prove actu-

ally hold for countable and uncountable ļ¬rst-order languages alike, but

some require heavier machinery to prove for uncountable languages.

Just as in LP , the parentheses are just punctuation while the con-

nectives, Ā¬ and ā’, are intended to express not and if . . . then. How-

ever, the rest of the symbols are new and are intended to express ideas

that cannot be handled by LP . The quantiļ¬er symbol, ā, is meant to

represent for all, and is intended to be used with the variable symbols,

e.g. āv4. The constant symbols are meant to be names for particular

elements of the structure under discussion. k-place function symbols

are meant to name particular functions which map k-tuples of elements

of the structure to elements of the structure. k-place relation symbols

are intended to name particular k-place relations among elements of

the structure.3 Finally, = is a special binary relation symbol intended

to represent equality.

Example 5.1. Since the logical symbols are always the same, ļ¬rst-

order languages are usually deļ¬ned by specifying the non-logical sym-

bols. A formal language for elementary number theory like that unof-

ļ¬cially described above, call it LN T , can be deļ¬ned as follows.

ā¢ Constant symbols: 0 and 1

ā¢ Two 2-place function symbols: + and Ā·

ā¢ Two binary relation symbols: < and |

Each of these symbols is intended to represent the same thing it does

in informal mathematical usage: 0 and 1 are intended to be names

for the numbers zero and one, + and Ā· names for the operations of

addition and multiplications, and < and | names for the relations āless

thanā and ādividesā. (Note that we could, in principle, interpret things

completely diļ¬erently ā“ let 0 represent the number forty-one, + the

operation of exponentiation, and so on ā“ or even use the language to

talk about a diļ¬erent structure ā“ say the real numbers, R, with 0,

1, +, Ā·, and < representing what they usually do and, just for fun,

| interpreted as āis not equal toā. More on this in Chapter 6.) We

will usually use the same symbols in our formal languages that we use

informally for various common mathematical objects. This convention

3

Intuitively, a relation or predicate expresses some (possibly arbitrary) relation-

ship among one or more objects. For example, ān is primeā is a 1-place relation

on the natural numbers, < is a 2-place or binary relation on the rationals, and

a Ć— (b Ć— c) = 0 is a 3-place relation on R3 . Formally, a k-place relation on a set X

is just a subset of X k , i.e. the collection of sequences of length k of elements of X

for which the relation is true.

26 5. LANGUAGES

can occasionally cause confusion if it is not clear whether an expression

involving these symbols is supposed to be an expression in a formal

language or not.

Example 5.2. Here are some other ļ¬rst-order languages. Recall

that we need only specify the non-logical symbols in each case and

note that some parts of Deļ¬nitions 5.2 and 5.3 may be irrelevant for

a given language if it is missing the appropriate sorts of non-logical

symbols.

1. The language of pure equality, L= :

ā¢ No non-logical symbols at all.

2. A language for ļ¬elds, LF :

ā¢ Constant symbols: 0, 1

ā¢ 2-place function symbols: +, Ā·

3. A language for set theory, LS :

ā¢ 2-place relation symbol: ā

4. A language for linear orders, LO :

ā¢ 2-place relation symbol: <

5. Another language for elementary number theory, LN :

ā¢ Constant symbol: 0

ā¢ 1-place function symbol: S

ā¢ 2-place function symbols: +, Ā·, E

Here 0 is intended to represent zero, S the successor function, i.e.

S(n) = n+1, and E the exponential function, i.e. E(n, m) = nm .

6. A āworst-caseā countable language, L1 :

ā¢ Constant symbols: c1, c2 , c3, . . .

ā¢ For each k ā„ 1, k-place function symbols: f1 , f2 , f3 , . . .

k k k

ā¢ For each k ā„ 1, k-place relation symbols: P1 , P2 , P3 , . . .

k k k

This language has no use except as an abstract example.

It remains to specify how to form valid formulas from the symbols

of a ļ¬rst-order language L. This will be more complicated than it was

for LP . In fact, we ļ¬rst need to deļ¬ne a type of expression in L which

has no counterpart in propositional logic.

Definition 5.2. The terms of a ļ¬rst-order language L are those

ļ¬nite sequences of symbols of L which satisfy the following rules:

1. Every variable symbol vn is a term.

2. Every constant symbol c is a term.

3. If f is a k-place function symbol and t1, . . . , tk are terms, then

ft1 . . . tk is also a term.

4. Nothing else is a term.

5. LANGUAGES 27

That is, a term is an expression which represents some (possibly

indeterminate) element of the structure under discussion. For example,

in LN T or LN , +v0 v1 (informally, v0 + v1 ) is a term, though precisely

which natural number it represents depends on what values are assigned

to the variables v0 and v1.

Problem 5.1. Which of the following are terms of one of the lan-

guages deļ¬ned in Examples 5.1 and 5.2? If so, which of these lan-

guage(s) are they terms of; if not, why not?

1. Ā·v2

2. +0 Ā· +v611

3. |1 + v30

4. (< E101 ā’ +11)

5. + + Ā· + 00000

32

6. f4 f7 c4 v9c1 v4

7. Ā·v5(+1v8 )

8. < v6v2

9. 1 + 0

Note that in languages with no function symbols all terms have

length one.

Problem 5.2. Choose one of the languages deļ¬ned in Examples

5.1 and 5.2 which has terms of length greater than one and determine

the possible lengths of terms of this language.

Proposition 5.3. The set of terms of a countable ļ¬rst-order lan-

guage L is countable.

Having deļ¬ned terms, we can ļ¬nally deļ¬ne ļ¬rst-order formulas.

Definition 5.3. The formulas of a ļ¬rst-order language L are the

ļ¬nite sequences of the symbols of L satisfying the following rules:

1. If P is a k-place relation symbol and t1 , . . . , tk are terms, then

P t1 . . . tk is a formula.

2. If t1 and t2 are terms, then = t1 t2 is a formula.

3. If Ī± is a formula, then (Ā¬Ī±) is a formula.

4. If Ī± and Ī² are formulas, then (Ī± ā’ Ī²) is a formula.

5. If Ļ• is a formula and vn is a variable, then āvn Ļ• is a formula.

6. Nothing else is a formula.

Formulas of form 1 or 2 will often be referred to as the atomic formulas

of L.

Note that three of the conditions in Deļ¬nition 5.3 are borrowed

directy from propositional logic. As before, we will exploit the way

28 5. LANGUAGES

formulas are built up in making deļ¬nitions and in proving results by

induction on the length of a formula. We will also recycle the use

of lower-case Greek characters to refer to formulas and of upper-case

Greek characters to refer to sets of formulas.

Problem 5.4. Which of the following are formulas of one of the

languages deļ¬ned in Examples 5.1 and 5.2? If so, which of these lan-

guage(s) are they formulas of; if not, why not?

1. = 0 + v7 Ā· 1v3

2. (Ā¬ = v1v1 )

3. (|v20 ā’ Ā·01)

4. (Ā¬āv5(= v5v5 ))

5. < +01|v1 v3

6. (v3 = v3 ā’ āv5 v3 = v5)

7. āv6(= v60 ā’ āv9(Ā¬|v9v6 ))

8. āv8 < +11v4

Problem 5.5. Show that every formula of a ļ¬rst-order language

has the same number of left parentheses as of right parentheses.

Problem 5.6. Choose one of the languages deļ¬ned in Examples

5.1 and 5.2 and determine the possible lengths of formulas of this lan-

guage.

Proposition 5.7. A countable ļ¬rst-order language L has count-

ably many formulas.

In practice, devising a formal language intended to deal with a par-

ticular (kind of) structure isnā™t the end of the job: one must also specify

axioms in the language that the structure(s) one wishes to study should

satisfy. Deļ¬ning satisfaction is oļ¬cially done in the next chapter, but

it is usually straightforward to unoļ¬cially ļ¬gure out what a formula

in the language is supposed to mean.

Problem 5.8. In each case, write down a formula of the given

language expressing the given informal statement.

1. āAddition is associativeā in LF .

2. āThere is an empty setā in LS .

3. āBetween any two distinct elements there is a third elementā in

LO .

4. ān0 = 1 for every n diļ¬erent from 0ā in LN .

5. āThere is only one thingā in L= .

Problem 5.9. Deļ¬ne ļ¬rst-order languages to deal with the follow-

ing structures and, in each case, an appropriate set of axioms in your

language:

5. LANGUAGES 29

1. Groups.

2. Graphs.

3. Vector spaces.

We will need a few additional concepts and facts about formulas of

ļ¬rst-order logic later on. First, what are the subformulas of a formula?

Problem 5.10. Deļ¬ne the set of subformulas of a formula Ļ• of a

ļ¬rst-order language L.

For example, if Ļ• is

ńņš. 4 |