# Propositional Logic Proof

• Jun 16th 2011, 07:03 AM
hmmmm
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 $\mathcal{F}$ is an inconsistent set of sentences. For each $G\epsilon\mathcal{F}$ let $\mathcal{F}_G$ be the set obtained from removing G from $\mathcal{F}$.

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

Proof

We can split into two cases.

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

2. $\mathcal{F}$ is now consistent in which case G was false in the cases that $\mathcal{F}_G$ was satisfied and so $\lnot G$ is true when $\mathcal{F}_G$ is satisfied and so by definition $\mathcal{F}_G\models\lnot G$ and by completness $\mathcal{F}_G\vdashz\lnot G$
• Jun 16th 2011, 08:02 AM
bryangoodrich
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 $\mathcal{F}_G$ that is satisfied. We say that $\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., $\mathcal{F}_G \vdash G$) Since our assumption is that $\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?
• Jun 16th 2011, 08:06 AM
emakarov
Re: Propositional Logic Proof
Quote:

Originally Posted by hmmmm
2. $\mathcal{F}$ is now consistent in which case G was false in the cases that $\mathcal{F}_G$ was satisfied and so $\lnot G$ is true when $\mathcal{F}_G$ is satisfied and so by definition $\mathcal{F}_G\models\lnot G$ and by completness $\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, $\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.
• Jun 16th 2011, 08:30 AM
hmmmm
Re: Propositional Logic Proof
Yeah sorry it is I will try to clarify:

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

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

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

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

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

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

Is this any better?

thanks for the help
• Jun 16th 2011, 09:23 AM
emakarov
Re: Propositional Logic Proof
Quote:

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

First, I would say, "G is false in any interpretation where the rest of the sentences in $\mathcal{F}$ are true." Note that you use soundness theorem here. Indeed, " $\mathcal{F}$ is inconsistent" means that $\mathcal{F}\vdash\bot$, so $\mathcal{F}\models\bot$ by soundness, i.e., $\mathcal{F}$ is unsatisfiable.

Quote:

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

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

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

By the completness of propositional logic $\mathcal{F}_G\vdash\lnot G$
Yes, this works. In fact, there is no need to consider the case when $\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, $\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.

• Jun 16th 2011, 09:50 AM
hmmmm
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
• Jun 16th 2011, 10:29 AM
bryangoodrich
Re: Propositional Logic Proof
Quote:

Originally Posted by emakarov
" $\mathcal{F}$ is inconsistent" means that $\mathcal{F}\vdash\bot$, so $\mathcal{F}\models\bot$ by soundness, i.e., $\mathcal{F}$ is unsatisfiable.

Just for technical clarification, is it correct to say that $\mathcal{F}$ is unsatisfiable? Don't we say,

(Definition) A theory is satisfiable if it has a model: $\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 $\mathcal{F} \models \bot$, isn't this saying that F models a contradiction or F satisfies a contradiction?
• Jun 16th 2011, 12:25 PM
emakarov
Re: Propositional Logic Proof
Quote:

Originally Posted by bryangoodrich
If we're saying $\mathcal{F} \models \bot$, isn't this saying that F models a contradiction or F satisfies a contradiction?

Yes, but $\mathcal{F} \models \bot$ iff $\mathcal{F}$ has no model.