Results 1 to 8 of 8

Thread: Propositional Logic Proof

  1. #1
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    Propositional Logic Proof

    I was wondering if this proof was ok or if (as I suspect) I am wrong and if you could help point me in the right direction.

    thanks for any help

    Suppose that $\displaystyle \mathcal{F}$ is an inconsistent set of sentences. For each $\displaystyle G\epsilon\mathcal{F}$ let $\displaystyle \mathcal{F}_G$ be the set obtained from removing G from $\displaystyle \mathcal{F}$.

    Prove that for any $\displaystyle G\epsilon\mathcal{F}$ $\displaystyle \mathcal{F}_G\vdash\lnot G$.


    Proof


    We can split into two cases.

    1. $\displaystyle \mathcal{F}_G$ is still an inconsistent set and so it can prove anything, namely $\displaystyle \lnot G$


    2. $\displaystyle \mathcal{F}$ is now consistent in which case G was false in the cases that $\displaystyle \mathcal{F}_G$ was satisfied and so $\displaystyle \lnot G$ is true when $\displaystyle \mathcal{F}_G$ is satisfied and so by definition $\displaystyle \mathcal{F}_G\models\lnot G$ and by completness $\displaystyle \mathcal{F}_G\vdashz\lnot G$
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165

    Re: Propositional Logic Proof

    Your first case is correct. I think you're on the right path with the second case, but I don't believe it is $\displaystyle \mathcal{F}_G$ that is satisfied. We say that $\displaystyle \mathcal{F}_G$ satisfies or models or is a model of the formula on the RHS of the turnstile. Furthermore, satisfiability is a semantic concept, and your proof, as you've written with the single-turnstile, is a proof about provability. I think you should keep to the syntactical proof theory in your proof.

    I would approach the problem from this perspective. Ask yourself, what happens when our set of sentences proves G? (i.e., $\displaystyle \mathcal{F}_G \vdash G$) Since our assumption is that $\displaystyle \mathcal{F}_G$ is consistent, and it is precisely so because of the removal of G, I think the answer to that question will provide your solution: it eliminates the case of proving G and leaves us with only one other option, i.e., that it proves G. Do you see why?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Propositional Logic Proof

    Quote Originally Posted by hmmmm View Post
    2. $\displaystyle \mathcal{F}$ is now consistent in which case G was false in the cases that $\displaystyle \mathcal{F}_G$ was satisfied and so $\displaystyle \lnot G$ is true when $\displaystyle \mathcal{F}_G$ is satisfied and so by definition $\displaystyle \mathcal{F}_G\models\lnot G$ and by completness $\displaystyle \mathcal{F}_G\vdashz\lnot G$
    It's pretty hard to understand this sentence. It would help if you break it into several sentences and/or insert punctuation.

    In any case, you can't say that G is false. In which interpretation? This problem is not about semantics at all.

    In fact, $\displaystyle \mathcal{F}_G\vdash\neg G$ just by the deduction theorem if you use Hilbert-style system, or by negation introduction or implication introduction if you use natural deduction.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    Re: Propositional Logic Proof

    Yeah sorry it is I will try to clarify:

    $\displaystyle \mathcal{F}_G$ is now a consistent set of sentences.

    It must then have been the case that $\displaystyle \mathcal{F}$ was inconsistent because G was false when the rest of the sentences in $\displaystyle \mathcal{F}$ were true ($\displaystyle \mathcal{F}_G$)

    So when all the sentences in $\displaystyle \mathcal{F}_G$ are true G is false.

    So when all the sentences in $\displaystyle \mathcal{F}_G$ are true $\displaystyle \lnot G$ is true

    By definition $\displaystyle \mathcal{F}_G\models\lnot G$

    By the completness of propositional logic $\displaystyle \mathcal{F}_G\vdash\lnot G$

    Is this any better?

    thanks for the help
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Propositional Logic Proof

    Quote Originally Posted by hmmmm View Post
    It must then have been the case that $\displaystyle \mathcal{F}$ was inconsistent because G was false when the rest of the sentences in $\displaystyle \mathcal{F}$ were true ($\displaystyle \mathcal{F}_G$)
    First, I would say, "G is false in any interpretation where the rest of the sentences in $\displaystyle \mathcal{F}$ are true." Note that you use soundness theorem here. Indeed, "$\displaystyle \mathcal{F}$ is inconsistent" means that $\displaystyle \mathcal{F}\vdash\bot$, so $\displaystyle \mathcal{F}\models\bot$ by soundness, i.e., $\displaystyle \mathcal{F}$ is unsatisfiable.

    So when all the sentences in $\displaystyle \mathcal{F}_G$ are true G is false.

    So when all the sentences in $\displaystyle \mathcal{F}_G$ are true $\displaystyle \lnot G$ is true

    By definition $\displaystyle \mathcal{F}_G\models\lnot G$

    By the completness of propositional logic $\displaystyle \mathcal{F}_G\vdash\lnot G$
    Yes, this works. In fact, there is no need to consider the case when $\displaystyle \mathcal{F}_G$ is inconsistent; the proof above goes through for that case as well.

    However, I am still saying that doing this problem through soundness and completeness is a huge detour.
    Quote Originally Posted by emakarov
    In fact, $\displaystyle \mathcal{F}_G\vdash\neg G$ just by the deduction theorem if you use Hilbert-style system, or by negation introduction or implication introduction if you use natural deduction.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    Re: Propositional Logic Proof

    Thanks very much. Yeah I see that now thanks but having started like this I just wanted to know if this was right.

    thanks for the help
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165

    Re: Propositional Logic Proof

    Quote Originally Posted by emakarov View Post
    "$\displaystyle \mathcal{F}$ is inconsistent" means that $\displaystyle \mathcal{F}\vdash\bot$, so $\displaystyle \mathcal{F}\models\bot$ by soundness, i.e., $\displaystyle \mathcal{F}$ is unsatisfiable.
    Just for technical clarification, is it correct to say that $\displaystyle \mathcal{F}$ is unsatisfiable? Don't we say,

    (Definition) A theory is satisfiable if it has a model: $\displaystyle \mathcal{M} \models \mathcal{T}$

    So a theory is unsatisfiable if it lacks any model (i.e., it is not true under any interpretation). If we're saying $\displaystyle \mathcal{F} \models \bot$, isn't this saying that F models a contradiction or F satisfies a contradiction?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Propositional Logic Proof

    Quote Originally Posted by bryangoodrich View Post
    If we're saying $\displaystyle \mathcal{F} \models \bot$, isn't this saying that F models a contradiction or F satisfies a contradiction?
    Yes, but $\displaystyle \mathcal{F} \models \bot$ iff $\displaystyle \mathcal{F}$ has no model.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. propositional logic
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Aug 30th 2011, 09:52 AM
  2. propositional logic equivalence proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Mar 11th 2010, 12:20 AM
  3. Propositional Logic Proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Sep 8th 2009, 08:34 AM
  4. Replies: 15
    Last Post: Jun 3rd 2008, 03:58 PM
  5. propositional logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Jun 10th 2007, 09:50 AM

Search Tags


/mathhelpforum @mathhelpforum