Completeness and Consistency

http://img89.imageshack.us/img89/8743/qs1q.jpg


Here's my attempt:

Suppose we have a set which is a subset of set of all wffs of the system-L, such that for all even n, and for all odd n. Then I guess we have to show it is consistent and complete.

is consistent if there is no wff A such that and .

is complete if for every we have either or .

I appreciate any help to get me started on this. I'm not sure how to start proving the two conditions...

I assume that L is a propositional language and p1, p2, ... are all propositional variables. This information should be in the problem statement.

There is a general theorem that every consistent set of formulas has a maximal extension (i.e., superset). Let's call it Π. This fact is often used as a key lemma in proving model completeness of propositional (and first-order) logic. Since Π is maximal (i.e., no proper superset of it is consistent), it is complete. Indeed, suppose Π derives neither A nor ~A for some formula A. Then Π ∪ {A} is a proper superset of Π and it is consistent, for if Π and A derive a contradiction, then Π derives ~A contrary to our assumption.

You are left to show that {p2, p4, ...} ∪ {~p1, ~p3, ...} is consistent. But every derivation uses only a finite number of assumption, so if a contradiction is derived from this set, then a finite subset is also inconsistent. This would contradict the soundness theorem.

The theorem about maximal consistent extension is pretty simple. You just enumerate all formulas in the language and for each formula you add either it or its negation so that the set stays consistent. One has to prove that this is always possible. After that, the union of the increasing chain of sets is taken; it is easy to see that it is also consistent. In fact, this construction implies that the resulting set has either A or ~A for each formula A, i.e., it is complete.

Quote:

---

Originally Posted by emakarov

But every derivation uses only a finite number of assumption, so if a contradiction is derived from this set, then a finite subset is also inconsistent. This would contradict the soundness theorem.

---

Thanks, I hadn't thought about the Extension Theorem. But could you please this two lines to me in a simpler way? I'm not sure if I understodd this part very well...

Every derivation uses a finite number of formulas and, therefore, a finite number of assumptions. So if {p2, p4, ...} ∪ {~p1, ~p3, ...} ⊢ ⊥ (where ⊥ is a contradiction, say, ~(A -> A) for some formula A), then S ⊢ ⊥ for a finite subset S of {p2, p4, ...} ∪ {~p1, ~p3, ...}. But every formula in S is true in the interpretation that assigns True to variables that occur in S without negation and False to variables that occur in S with negation. By Soundness theorem, ⊥ has to be true, which contradicts the assumption that {p2, p4, ...} ∪ {~p1, ~p3, ...} ⊢ ⊥. Therefore, {p2, p4, ...} ∪ {~p1, ~p3, ...} is consistent.