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$

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?

Re: Propositional Logic Proof

Quote:

Originally Posted by

**hmmmm** 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.

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

Re: Propositional Logic Proof

Quote:

Originally Posted by

**hmmmm** 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.

Quote:

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.

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

Re: Propositional Logic Proof

Quote:

Originally Posted by

**emakarov** "$\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?

Re: Propositional Logic Proof

Quote:

Originally Posted by

**bryangoodrich** 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.