<<

. 4
( 11 .)



>>


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
( 11 .)



>>