# Math Help - Satisfying Truth Assignment

1. ## Satisfying Truth Assignment

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

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

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

If there is a truth assignment $f_{\Sigma}$ then for an arbitrary A the following is one of the options that must be true:

$f_{\Sigma}(A)=0$ then $f_{\Sigma}(\neg A) = 1$.

And in order for that to be true we need $\Sigma$ to be complete (because if we have $f_{\Sigma}(A)=0$, then $A \notin \Sigma$ so $\neg A \in \Sigma$ so $f_{\Sigma}(\neg A) = 1$).

Suppose $\Sigma$ is not complete, then if $f_{\Sigma}(A)=0$ then $f_{\Sigma}(\neg A) \neq 1$. So there's no truth assignment. Is this right?

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

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

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

P.S: By the truth assignment $f_{\Sigma}(A): form(L) \to \{ 0,1 \}$ I meant:

$f_{\Sigma}(A)= \left\{\begin{matrix}1 \ if A \in \Sigma \\ 0 \ if \ A \notin \Sigma\end{matrix}\right.$

2. ## Re: Satisfying Truth Assignment

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?

3. ## Re: Satisfying Truth Assignment

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.

4. ## Re: Satisfying Truth Assignment

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 ?

5. ## Re: Satisfying Truth Assignment

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 $\Sigma$ is compelete if for every $P \in \ form(L)$ we have either $P \in \Sigma$ or $\neg P \in \Sigma$.

6. ## Re: Satisfying Truth Assignment

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.