ńņš. 6 |

Theorem that M is compact. For each L-formula A, put MA = {M ā M :

vM (A) = T}. It is easy to check that each MA is a topologically closed set

in M. If S is ļ¬nitely satisļ¬able, then the family of sets MA , A ā S has the

ļ¬nite intersection property, i.e., AāS0 MA = ā… for each ļ¬nite S0 ā S. By

compactness of M it follows that AāS MA = ā…. Thus S is satisļ¬able.

1.8 Combinatorial Applications

In this section we present some combinatorial applications of the Compactness

Theorem for propositional calculus.

Deļ¬nition 1.8.1.

1. A graph consists of a set of vertices together with a speciļ¬cation of certain

pairs of vertices as being adjacent. We require that a vertex may not be

adjacent to itself, and that u is adjacent to v if and only if v is adjacent

to u.

2. Let G be a graph and let k be a positive integer. A k-coloring of G is a

function f : {vertices of G} ā’ {c1 , . . . , ck } such that f (u) = f (v) for all

adjacent pairs of vertices u, v.

3. G is said to be k-colorable if there exists a k-coloring of G. This notion is

much studied in graph theory.

Exercise 1.8.2. Let G be a graph and let k be a positive integer. For each

vertex v and each i = 1, . . . , k, let pvi be a propositional atom expressing that

vertex v receives color ci . Deļ¬ne Ck (G) to be the following set of propositional

formulas: pv1 āØ Ā· Ā· Ā· āØ pvk for each vertex v; Ā¬ (pvi & pvj ) for each vertex v and

1 ā¤ i < j ā¤ k; Ā¬ (pui & pvi ) for each adjacent pair of vertices u, v and 1 ā¤ i ā¤ k.

1. Show that there is a one-to-one correspondence between k-colorings of G

and assignments satisfying Ck (G).

2. Show that G is k-colorable if and only if Ck (G) is satisļ¬able.

3. Show that G is k-colorable if and only if each ļ¬nite subgraph of G is

k-colorable.

Deļ¬nition 1.8.3. A partial ordering consists of a set P together with a binary

relation ā¤P such that

1. a ā¤P a for all a ā P (reļ¬‚exivity);

17

2. a ā¤P b, b ā¤P c imply a ā¤P c (transitivity);

3. a ā¤P b, b ā¤P a imply a = b (antisymmetry).

Example 1.8.4. Let P = N+ = {1, 2, 3, . . . , n, . . .} = the set of positive inte-

gers.

1. Let ā¤P be the usual order relation on P , i.e., m ā¤P n if and only if m ā¤ n.

2. Let ā¤P be the divisibility ordering of P , i.e., m ā¤P n if and only if m is

a divisor of n.

Deļ¬nition 1.8.5. Let P, ā¤P be a partial ordering.

1. Two elements a, b ā P are comparable if either a ā¤P b or b ā¤P a. Other-

wise they are incomparable.

2. A chain is a set X ā P such that any two elements of X are comparable.

3. An antichain is a set X ā P such that any two distinct elements of X are

incomparable.

Exercise 1.8.6. Let P, ā¤P be a partial ordering, and let k be a positive integer.

1. Use the Compactness Theorem to show that P is the union of k chains if

and only if each ļ¬nite subset of P is the union of k chains.

2. Dilworthā™s Theorem says that P is the union of k chains if and only if

every antichain is of size ā¤ k. Show that Dilworthā™s Theorem for arbi-

trary partial orderings follows from Dilworthā™s Theorem for ļ¬nite partial

orderings.

18

Chapter 2

Predicate Calculus

2.1 Formulas and Sentences

Deļ¬nition 2.1.1 (languages). A language L is a set of predicates, each pred-

icate P of L being designated as n-ary for some nonnegative1 integer n.

Deļ¬nition 2.1.2 (variables and quantiļ¬ers). We assume the existence of

a ļ¬xed, countably inļ¬nite set of symbols x, y, z, . . . known as variables. We

introduce two new symbols: the universal quantiļ¬er (ā) and the existential

quantiļ¬er (ā). They are read as āfor allā and āthere existsā, respectively.

Deļ¬nition 2.1.3 (formulas). Let L be a language, and let U be a set. The

set of L-U -formulas is generated as follows.

1. An atomic L-U -formula is an expression of the form P e1 Ā· Ā· Ā· en where P

is an n-ary predicate of L and each of e1 , . . . , en is either a variable or an

element of U .

2. Each atomic L-U -formula is an L-U -formula.

3. If A is an L-U -formula, then Ā¬ A is an L-U -formula.

4. If A and B are L-U -formulas, then A & B, A āØ B, A ā’ B, A ā” B are L-

U -formulas.

5. If x is a variable and A is an L-U -formula, then āx A and āx A are L-U -

formulas.

Deļ¬nition 2.1.4 (degree). The degree of a formula is the number of occur-

rences of propositional connectives Ā¬ , & , āØ , ā’ , ā” and quantiļ¬ers ā, ā in it.

Deļ¬nition 2.1.5. An L-formula is an L-ā…-formula, i.e., an L-U -formula where

U = ā…, the empty set.

1 It will be seen that 0-ary predicates behave as propositional atoms. Thus predicate

calculus is an extension of propositional calculus.

19

Remark 2.1.6. If U is a subset of U , then every L-U -formula is automati-

cally an L-U -formula. In particular, every L-formula is automatically an L-U -

formula, for any set U .

Deļ¬nition 2.1.7. In situations where the language L is understood from con-

text, an L-U -formula may be called a U -formula, and an L-formula a formula.

Deļ¬nition 2.1.8 (substitution). If A is an L-U -formula and x is a variable

and a ā U , we deļ¬ne an L-U -formula A[x/a] as follows.

1. If A is atomic, then A[x/a] = the result of replacing each occurrence of x

in A by a.

2. (Ā¬ A)[x/a] = Ā¬ A[x/a].

3. (A & B)[x/a] = A[x/a] & B[x/a].

4. (A āØ B)[x/a] = A[x/a] āØ B[x/a].

5. (A ā’ B)[x/a] = A[x/a] ā’ B[x/a].

6. (A ā” B)[x/a] = A[x/a] ā” B[x/a].

7. (āx A)[x/a] = āx A.

8. (āx A)[x/a] = āx A.

9. If y is a variable other than x, then (āy A)[x/a] = āy A[x/a].

10. If y is a variable other than x, then (āy A)[x/a] = āy A[x/a].

Deļ¬nition 2.1.9 (free variables). An occurrence of a variable x in an L-U -

formula A is said to be bound in A if it is within the scope of a quantiļ¬er āx or

āx in A. An occurrence of a variable x in an L-U -formula A is said to be free

in A if it is not bound in A. A variable x is said to occur freely in A if there is

at least one occurrence of x in A which is free in A.

Exercise 2.1.10.

1. Show that A[x/a] is the result of substituting a for all free occurrences of

x in A.

2. Show that x occurs freely in A if and only if A[x/a] = A.

Deļ¬nition 2.1.11 (sentences). An L-U -sentence is an L-U -formula in which

no variables occur freely. An L-sentence is an L-ā…-sentence, i.e., an L-U -sentence

where U = ā…, the empty set.

Remark 2.1.12. If U is a subset of U , then every L-U -sentence is automat-

ically an L-U -sentence. In particular, every L-sentence is automatically an

L-U -sentence, for any set U .

Deļ¬nition 2.1.13. In situations where the language L is understood from con-

text, an L-U -sentence may be called a U -sentence, and an L-sentence a sentence.

20

2.2 Structures and Satisļ¬ability

Deļ¬nition 2.2.1. Let U be a nonempty set, and let n be a nonnegative2 inte-

ger. U n is the set of all n-tuples of elements of U , i.e.,

U n = { a1 , . . . , an : a1 , . . . , an ā U } .

An n-ary relation on U is a subset of U n .

Deļ¬nition 2.2.2. Let L be a language. An L-structure M consists of a non-

empty set UM , called the domain or universe of M , together with an n-ary

relation PM on UM for each n-ary predicate P of L. An L-structure may be

called a structure, in situations where the language L is understood from context.

Deļ¬nition 2.2.3. 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 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 .

As usual in abstract mathematics, we are mainly interested in properties of

structures that are invariant under isomorphism.

Lemma 2.2.4. Given an L-structure M , there is a unique valuation or assign-

ńņš. 6 |