Results 1 to 4 of 4

Math Help - Completeness and Consistency

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    224

    Completeness and Consistency




    Here's my attempt:

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

    \Pi is consistent if there is no wff A such that \Pi \vdash_L A and \Pi \vdash_L \neg A.

    \Pi is complete if for every A \in form(L) we have either A \in \Pi or \neg A \in \Pi.

    I appreciate any help to get me started on this. I'm not sure how to start proving the two conditions...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Completeness and Consistency

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2009
    Posts
    224

    Re: Completeness and Consistency

    Quote Originally Posted by emakarov View Post
    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...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Completeness and Consistency

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Span and consistency.
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 18th 2011, 05:01 PM
  2. Consistency of a matrix
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 18th 2011, 11:52 PM
  3. Consistency formula
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: May 7th 2010, 02:58 AM
  4. proof consistency
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: October 18th 2009, 01:09 AM
  5. Matrix Consistency
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: March 16th 2009, 09:34 PM

/mathhelpforum @mathhelpforum