∀x Rxx

(1)

∀x ∀y (Rxy ” Ryx)

(2)

∀x ∀y ∀z ((Rxy & Ryz) ’ Rxz)

(3)

In this situation, the equivalence classes [a]R = {b ∈ U : a, b ∈ R}, a ∈ U ,

form a partition of U , i.e., a decomposition of the set U into pairwise disjoint

nonempty subsets.

Let A be the following sentence of the predicate calculus with identity:

(1) & (2) & (3) & ∀x ∃y ((¬ Ixy) & ∀z (Rxz ” (Ixz ∨ Iyz)))

1 Jones/Selman [1] show that X is a spectrum if and only if there exists a nondeterministic

Turing machine which accepts X in time 2ck , where k is the length of the input. Since the

input is a positive integer n, we have k = [log2 n], as usual in computational number theory.

2 A set of positive integers is said to be co¬nite if its complement is ¬nite.

55

Intuitively, A says that R is an equivalence relation with the property that each

equivalence class consists of exactly two elements. Obviously, a ¬nite set U

admits an equivalence relation with this property if and only if the cardinality

of U is even. Thus the spectrum of A is the set of even numbers.

Example 4.1.17. We show that the set of composite numbers3 is a spectrum.

Let L be a language consisting of two binary predicates, R and S, as well as

the identity predicate, I. Let A be an L-sentence saying that R and S are equiv-

alence relations, each with more than one equivalence class, and ∀x ∀y (∃ exactly

one z)(Rxz & Syz). Thus, for any normal L-structure M = (UM , RM , SM , IM )

satisfying A, we have that RM and SM partition UM into “rows” and “columns”,

respectively, in such a way that the intersection of any “row” with any “column”

consists of exactly one element of UM . Thus, if UM is ¬nite, the elements of

UM are arranged in an m — n “matrix”, where m, n ≥ 2. Therefore, the number

of elements in UM is mn, a composite number. Conversely, for any m, n ≥ 2,

there is an L-structure M as above, which satis¬es A. Thus spectrum(A) is the

set of composite numbers.

Exercise 4.1.18. Let L be a ¬nite language with identity, and let M be a

¬nite normal L-structure. Construct an L-sentence A such that, for all normal

L-structures M , M satis¬es A if and only if M is isomorphic to M .

Exercise 4.1.19. Let L be the following language:

Ox: x = 1

P xyz: x + y = z

Qxyz: x — y = z

Rxy: x < y

Sxy: x + 1 = y

Ixy: x = y (identity predicate)

For each positive integer n, let Mn be the normal L-structure

Mn = (Un , On , Pn , Qn , Rn , Sn , In )

where

Un = {1, . . . , n}

On = {1}

Pn = { i, j, k ∈ (Un )3 : i + j = k}

Qn = { i, j, k ∈ (Un )3 : i — j = k}

3A composite number is an integer greater than 1 which is not prime.

56

Rn = { i, j ∈ (Un )2 : i < j}

Sn = { i, j ∈ (Un )2 : i + 1 = j}

In = { i, j ∈ (Un )2 : i = j}

Exhibit an L-sentence A such that, for all ¬nite normal L-structures M , M

satis¬es A if and only if M is isomorphic to Mn for some n.

Exercise 4.1.20. Let L and Mn be as in Exercise 4.1.19. Show that there

exists an in¬nite normal L-structure M = M∞ with the following property: for

all L-sentences A, if Mp satis¬es A for all su¬ciently large primes p, then M∞

satis¬es A. (Hint: Use the Compactness Theorem.)

Exercise 4.1.21. Use the result of Exercise 4.1.19 to prove the following:

1. The set of prime numbers and its complement are spectra.

2. The set of squares {1, 4, 9, . . .} and its complement are spectra.

3. The set of powers of 2, {2n : n = 1, 2, 3, . . .}, and its complement, are

spectra.

4. The set of prime powers {pn : p prime, n = 1, 2, . . .} and its complement

are spectra.

Exercise 4.1.22.

1. The Fibonacci numbers are de¬ned recursively by F1 = 1, F2 = 2, Fn =

Fn’1 + Fn’2 for n ≥ 3. Show that the set of Fibonacci numbers

{Fn : n = 1, 2, . . .} = {1, 2, 3, 5, 8, 13, 21, 34, 55, . . .}

and its complement are spectra.

2. Show that {xy : x, y ≥ 2} and its complement are spectra.

4.2 Predicate Calculus With Operations

In this section we extend the syntax and semantics of the predicate calculus,

to encompass operations. As examples of operations, we may cite the familiar

mathematical operations of addition (+) and multiplication (—). Such opera-

tions are considered binary, because they take two arguments. More generally,

we consider n-ary operations.

De¬nition 4.2.1 (languages). A language is a set of predicates P, Q, R, . . .

and operations f, g, h, . . .. Each predicate and each operation is designated as

n-ary for some nonnegative4 integer n.

4A 0-ary operation is sometimes known as a constant. Syntactically, constants behave as

parameters.

57

De¬nition 4.2.2 (terms, formulas, sentences). Let L be a language, and

let U be a nonempty set. The set of L-U -terms is generated as follows.

1. Each variable is an L-U -term.

2. Each element of U is an L-U -term.

3. If f is an n-ary operation of L, and if t1 , . . . , tn are L-U -terms, then

f t1 · · · tn is an L-U -term.

An L-U -term is said to be variable-free if no variables occur in it. An atomic

L-U -formula is an expression of the form

P t1 · · · tn

where P is an n-ary predicate of L, and t1 , . . . , tn are L-U -terms. The set

of L-U -formulas is generated as in clauses 2, 3, 4 and 5 of De¬nition 2.1.3.

The notions of substitution, free variables, and L-U -sentences are de¬ned as in

Section 2.1. Note that P t1 · · · tn is a sentence if and only if it is variable-free.

De¬nition 4.2.3 (structures). An L-structure M consists of a nonempty set

UM , an n-ary relation PM ⊆ (UM )n for each n-ary predicate P of L, and an

n-ary function fM : (UM )n ’ UM for each n-ary operation f of L.

De¬nition 4.2.4 (isomorphism). Two L-structures M and M are said to

be isomorphic if there exists an isomorphism of M onto M , i.e., a one-to-one

correspondence φ : UM ∼ UM such that:

=

1. for all n-ary predicates P of L and all n-tuples a1 , . . . , an ∈ (UM )n ,

a1 , . . . , an ∈ PM if and only if φ(a1 ), . . . , φ(an ) ∈ PM .

2. for all n-ary operations f of L and all n-tuples a1 , . . . , an ∈ (UM )n ,

φ(fM (a1 , . . . , an ) = fM (φ(a1 ), . . . , φ(an )).

Lemma 4.2.5 (valuations). Let M be an L-structure.

1. There is a unique valuation

vM : {t : t is a variable-free L-UM -term} ’ UM

de¬ned as follows:

(a) vM (a) = a for all a ∈ UM .

(b) vM (f t1 · · · tn ) = fM (vM (t1 ), . . . , vM (tn )) for all n-ary operations f

of L and all variable-free L-UM -terms t1 , . . . , tn .

2. There is a unique valuation

vM : {A : A is an L-UM -sentence} ’ {T, F}

58

de¬ned as follows. For atomic L-U -sentences, we have

if vM (t1 ), . . . , vM (tn ) ∈ PM ,

T

vM (P t1 · · · tn ) =

if vM (t1 ), . . . , vM (tn ) ∈ PM .

F /