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 is an inconsistent set of sentences. For each let be the set obtained from removing G from .

Prove that for any .

Proof

We can split into two cases.

1. is still an inconsistent set and so it can prove anything, namely

2. is now consistent in which case G was false in the cases that was satisfied and so is true when is satisfied and so by definition and by completness

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 that is *satisfied*. We say that *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., ) Since our assumption is that 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.

is now consistent in which case G was false in the cases that

was satisfied and so

is true when

is satisfied and so by definition

and by completness

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, 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:

is now a consistent set of sentences.

It must then have been the case that was inconsistent because G was false when the rest of the sentences in were true ( )

So when all the sentences in are true G is false.

So when all the sentences in are true is true

By definition

By the completness of propositional logic

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

was inconsistent because G was false when the rest of the sentences in

were true (

)

First, I would say, "G is false *in any interpretation* where the rest of the sentences in are true." Note that you use soundness theorem here. Indeed, " is inconsistent" means that , so by soundness, i.e., is unsatisfiable.

Quote:

So when all the sentences in

are true G is false.

So when all the sentences in

are true

is true

By definition

By the completness of propositional logic

Yes, this works. In fact, there is no need to consider the case when 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,

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** "

is inconsistent" means that

, so

by soundness, i.e.,

is unsatisfiable.

Just for technical clarification, is it correct to say that is unsatisfiable? Don't we say,

(Definition) A theory is **satisfiable **if it has a model:

So a theory is unsatisfiable if it lacks any model (i.e., it is not true under any interpretation). If we're saying , 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

, isn't this saying that F models a contradiction or F satisfies a contradiction?

Yes, but iff has no model.