36

The next proof makes explicit reference to notions in topology. As indicated in the preceding

alternative proof, a truth assignment can be denoted by a path in the full binary tree Tall, now

viewed as an w-sequence in the product space (T,F). (We write for the first infinite ordinal,

which is the set of natural numbers listed in their standard order.)

We view {T,F) as the underlying space of a product topology ({T,F)", O), thus making every

truth assignment a "point" in that topology. O is a family of open sets that define the topology,

which are in this case subsets of points in {T, F)~ and satisfy the usual requirements of a topology:

• The empty set and the full space {T,F) are in O.

• O is closed under arbitrary unions,

• O is closed under finite intersections.

We can define a subset UC {T,F}" to be open iff there is a finite set of indices IC such that:

U = II { Ai | i €w and A; C {T,F}} where A. = {T,F) for every i Ew-I.

In words, in the infinite product U = Ao × A₁ × --- × A; x--, for all but finitely many indices i

it is the case that A; = {T,F). A set U C {T,F)" is closed iff it is the complement of an open

APPENDIX F. ALTERNATIVE COMPACTNESS PROOFS

set. In the case of the product topology, every open subset UC (T,F) is also closed, and thus

called clopen.

Let A be a subset of (T,F). An open covering of A is a family of open sets {U; | i I} CO

such that A CU{U; i 1}. And A is said compact if every open covering of A has a finite

subcovering; i.e., there exists a finite subfamily U₁₁, UU₁ of (U; | i I} such that A

(U₁, UU, U...UU.). By Tychonoff's Theorem in topology, the product topology ({T,F), O)

is compact, which means that every open covering of a subset of points AC {T,F) has a finite

subcovering.

Alternative Proof II of Theorem 2 (Compactness for Propositional Logic). Again here,

we only need to consider the non-trivial implication "+": If I is finitely satisfiable, then I is

satisfiable.

For every propositional wffy, let A, C {T,F}" be the collection of all points/truth assignments

that satisfy p. The set A, is a closed (and open) subset of {T,F}" in the topology ({T,F)",0),

which follows from the fact that only mentions finitely many propositional variables. It is easy

to check that, for every finite subset A of I, if A is satisfiable, then {A | A} is not empty.

Hence, the family of closed sets {Apyr} satisfies the finite intersection property. Moreover,

the product topology ({T.F),O) is compact, as noted above. Hence, {A, ET) is not

empty, which is the desired conclusion.

0/nExercise 147. This exercise is couched in a language which is a little more familiar to computer

scientists. Given a set IWFF₁(P), the binary tree T(I) induced by I' is defined in the

35

proof above. In T(I), every finite path is a finite sequence, and every infinite path is an infinite

sequence, where all the entries are in {T,F). The set of all such finite sequences is denoted

{T,F)", and the set of all such infinite sequences is denoted {T,F). The root node of T(I) is

represented by the empty sequence e, every leaf node is connected to the root node by a finite

path, and every infinite path is one that can be traversed without ever reaching a leaf node.

An arbitrary binary tree can therefore be represented by a subset of {T, F}*U{T,F}", satisfying

two conditions:

• U is prefix-closed, i.e., for every (possibly infinite) path ₁ € {T,F)* U{T,F) and every

finite path #₂ € {T,F)", if ₁ EU and ₂ is a prefix of ₁, then #₂ EU.

• For every finite path = {T,F)", it holds that T U iff F EU, i.e., every non-leaf node

has two immediate successors.

Given an arbitrary IWFF (P), let T(T) be the subset of infinite paths in T(I):

T(T) = T(r)n(T.F)".

By the preceding proof, T. (T) ‡ Ø iff the set I is satisfiable. Let To, F₁, and I2, be defined as

follows:

To = {-P₁ ^P₂},

T₁ = {P₁ → (P₂A---A-PE) | A>2},

del

1₂ = {~-P₁ → (P²2 A---A-¬-Pk) |>2}.

There are two parts in this exercise:

1. Define the sets of infinite paths T. (To), T.(₁UF₂), and T(Tour₁ UF₂) as subsets of

{T,F). In your answers, use the notational conventions of regular languages and regular

w-languages that we have used earlier in the presentation of this exercise.

2. For each of the three sets defined in part 1, explain how they indicate whether the corre-

sponding set of wff's is satisfiable or not.

You will find it useful to consult Figure F.1.

0