let delta be a set of wffs such that (1) every finite subset of delta is satisfi

Question

let delta be a set of wffs such that

(1) every finite subset of delta is satisfiable, and

(2) for every wff a, either a belongs to delta or (¬ a) belongs to delta.

Define the truth assignment v: v(A) = T iff A belongs to delta. v(A) = F iff A doesnt belong to delta. for each sentence symbol A.

Show that for every wff phi, v bar of phi = T iff phi belongs to delta.

(This is the part of the proof of the compactness theorem)

Suggestion: use induction on phi.

Please prove by induction. Thank you so much.

Explanation / Answer

There are many proofs, for example via Boolean algebras or compact Hausdorff topological spaces or binary trees and probably more.

For example, consider the sequence S0, S1, S2, ..., of sets of truth assignments, such that:

a) S0 is the set of all truth assignments
b) S1 is a subset of S0, S2 is a subset of S1, S3 is a subset of S2, etc.
c) For every finite subset E of A, every Sn contains at least one truth assignment that satisfies E

Note that by assumption, S0 satisfies condition (c).

Enumerate the propositional letters as p0, p1, p2, ...

Given that Sn satisfies (c), construct S{n+1} as follows:

let Fn = { truth assignments in Sn such that the value assigned to letter pn is FALSE }
let Tn = { truth assignments in Sn such that the value assigned to letter pn is TRUE }

Claim: at least one of Fn and Tn must satisfy clause (c).

Why? Suppose that both E1 is a finite subset of A with no satisfying assignment in Fn and E2 is a finite subset of A with no satisfying assignment in Tn. Then E1 union E2 is also a finite subset of A which can be seen to have no satifying assignment in Sn, contrary to our assumption about Sn.

So now we define

S{n+1} = Fn if every finite subset of A has a satisfying assignment in Fn, otherwise S{n+1} = Tn

This way we define S0, S1, S2, ..., Sn, ... so that all Sn have property (c) and each S{n+1} is a proper subset of Sn.

There is one truth assignment in the intersection of all of the S0, S1, S2, ..., Sn, .... Why? It is the assignment that assigns FALSE to pn if S{n+1} was Fn and TRUE to pn if S{n+1} was Tn. It can be seen that both this truth assignment is in the common intersection of the Sn and that no other truth assignment can be.

Finally, the one truth assignment in the common intersection of the Sn is a satifying truth assignment for all of the formulas in A. I guess the easiest way to see this is that for any finite subset E of A (including the one-element subsets), all of the letters of the formulas in E are pi for 0 <= i < n. Then since Sn already decides the FALSE or TRUE value of each pi, 0 <= i < n, we see that every truth assignment in Sn decides E the same way: all elements of Sn satify E or all elements of Sn do not satifsy E. But at least one element of Sn must satisfy E -- so they all do, including the unique truth assignment in the common intersection of all of the Sn.

So A has at least one satisfying truth assignment.

(You can find others by varying whether you pick Fn or Tn as the next S{n+1} whenever both have property (c)).


Update: A few hours later I realized the above was essentially the same as saying:

Claim: If A is a finitely satisfiable set of formulas and s is a formula, then at least one of A union { s }, A union { not s } is also finitely satisfiable.

Otherwise there are finite subsets E1 and E2 of A such that neither E1 union { s ] nor E2 union { not s } can be satisfied, when clearly the finite subset E1 union E2 of A cannot be satisfied.

So in the above construction the sequence S0, S1, S2, ... corresponded to a sequence like for example

A0 = A
A1 = A0 union { not p0 } if that is finitely satisfiable, otherwise A0 union { p0 } (which then is, by the claim)
A2 = A1 union { not p1 } if that is finitely satisfiable, otherwise A1 union { p1 } (which then is, by the claim)

...where as before the propositional letters are p0, p1, p2, ....

Then the union of all of the An is finitely satisfiable (because a finite subset would be contained in some finitely satisfiable An along the way) and in fact you can read off a satisfying truth assignment of the union of all of the An because for each letter the union contains either the letter (so assign it TRUE) or its negation (so assign it FALSE).

Same proof, just a different way of looking at it.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.