Thread: Satisfying Truth Assignment

So I have to show: is complete has a unique satisfying truth assignment. So my proof has to go in both directions...

To show the " ", we can try proving its contrapositive:

"If is not complete then it has no unique truth assignment."

If there is a truth assignment then for an arbitrary A the following is one of the options that must be true:

then .

And in order for that to be true we need to be complete (because if we have , then so so ).

Suppose is not complete, then if then . So there's no truth assignment. Is this right?


To show the " ", similarly I'll try proving its contrapositive:

"If doesn't have a unique satisfying truth assignment, then it is not complete."

Suppose doesn't have a unique satisfying truth assignment. Then how could we prove that is therefore not complete? Here's where I'm stuck...

P.S: By the truth assignment I meant:

Originally Posted by demode

So there's no truth assignment.

No, the link in your post stipulates that sigma is consistent. Moreover, the assumption of incompleteness does NOT imply unsatisfiability. If you use the contrapositive approach, then what you have to show is that there is more than one assignment that satisfies sigma.

Question: May we use the completeness theorem?

Originally Posted by MoeBlee

No, the link in your post stipulates that sigma is consistent. Moreover, the assumption of incompleteness does NOT imply unsatisfiability. If you use the contrapositive approach, then what you have to show is that there is more than one assignment that satisfies sigma.

That's exactly what I wanted to show, that the truth assignment is not unique and there are more than one that satisfy sigma. But HOW can I prove that? I think this is the most diificult part...

Question: May we use the completeness theorem?

Yes, we can use any other method to prove this.

I think using contrapositive is unnecessarily roundabout.

First, though, just for exactness, do you mean that S (sigma) is complete in the sense that for every formula P, either P or ~P is in S, or do you mean that S is complete in the sense that for every formula P, either S |- P or S |- ~P ?

Originally Posted by MoeBlee

I think using contrapositive is unnecessarily roundabout.

So how else would you prove that?

First, though, just for exactness, do you mean that S (sigma) is complete in the sense that for every formula P, either P or ~P is in S, or do you mean that S is complete in the sense that for every formula P, either S |- P or S |- ~P ?

We say that is compelete if for every we have either or .

That definition of 'S is complete' is correct.

However, if I'm not mistaken, in this problem, S should not be just a set of formulas, but rather S should be a set of formulas closed under deduction (S is closed under deduction iff for any formula P, if S proves P then P is in S).

We can NOT prove:

If S is consistent and there is a unique assigment that satisfies S, then S is complete

since we have this counterexample:

Let S be the set of all atomic formulas. Then there is a unique assigment that satisfies S (viz., the assignment f such that f(P) = 1 for all atomic P) but S is not complete since, for example, for any formula P, neither ~P nor ~~P are in S.

But we CAN prove

If S is closed under deduction and there is a unique assigment that satisfies S, then S is complete.

Proof:

Let f be the unique assigment. Let f' be the truth evaluation for all the formulas determined by the truth assignment f of the atomic formulas.

Suppose f'(K) = 1. Then, since f is the only assignment that satisfies S, we have S |= K, so, by the completeness theorem, S |- K, so, since S is closed under deduction, K is in S.

Suppose f'(K) = 0. So f'(~K) = 1. Then, since f is the only assignment that satisfies S, we have S |= ~K, so, by the completeness theorem, S |- ~K, so, since S is closed under deduction, ~K is in S.

Note: The proof is even simpler, in an obvious way, and does not require the completeness thereom if we change to:

If S is closed under entailment and there is a unique assigment that satisfies S, then S is complete.


/

Next we want to prove:

If S is consistent and S is complete, then there is a unique assigment that satisfies S

There might be more elegant proofs, but the following is straightforward and routine:

Proof:

Let f be the assignment to the atomic formulas by f(P) = 1 iff P is in S. Let f' be the extension of f.

By induction on formulas K, we show K is in S iff f'(K) = 1.

The induction is straightforward and routine, even if tedious. (Note that, at least for me, it only works out by proving it as an 'iff').

And it's trivial to show that f is unique:

If g, different from f, also satisfies S, then let P be an atomic formula on which f and g disagree. Let g' be the extension of g.

Suppose f(P) = 0 and g(P) = 1. So P is not in S. Since S is complete, ~P is in S. But g'(~P) = 0. So g does not satisfy S.

Suppose f(P) = 1 and g(P) = 0. So P is in S. So g does not satisfy S.