Propositional Logic Proof

**hmmmm** · June 16th 2011, 06:03 AM

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$

**bryangoodrich** · June 16th 2011, 07:02 AM

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?

**emakarov** · June 16th 2011, 07:06 AM

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.

**hmmmm** · June 16th 2011, 07:30 AM

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

**emakarov** · June 16th 2011, 08:23 AM

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.

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.

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.

**hmmmm** · June 16th 2011, 08:50 AM

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

**bryangoodrich** · June 16th 2011, 09:29 AM

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?

**emakarov** · June 16th 2011, 11:25 AM

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.

Thread: Propositional Logic Proof

LinkBack

Thread Tools

Display

Propositional Logic Proof

Re: Propositional Logic Proof

Re: Propositional Logic Proof

Re: Propositional Logic Proof

Re: Propositional Logic Proof

Re: Propositional Logic Proof

Re: Propositional Logic Proof

Re: Propositional Logic Proof

Similar Math Help Forum Discussions

propositional logic

propositional logic equivalence proof

Propositional Logic Proof

[SOLVED] Stuck in Proof of Laws of Syllogism and Absorption in Propositional Logic!

propositional logic

Search Tags