Search code examples
logicproofproof-of-correctness

Necessary and Sufficient vs Soundness and Completeness

I am trying to learn proof. I came across these 4 terms. I am trying to relate all. 

A: X>Y B: Y<X

Necessary Condition 
             B implies A
Sufficient Condition 
             A implies B

And

A = { set of statements}  Q= a statement

Soundness 
        if A derives Q then A is a logical consequence of Q
Completeness
         if A is a logical consequence of Q then A derives Q.

What is relation between all? Help is appreciated.

Solution

  • Necessary / sufficient doesn't have much to do with soundness and completeness so I'll explain the two concepts separately.

    Necessary / sufficient:

    In your example, the two statements are equivalent: X>Y if and only if Y<X. So it is indeed the case that B implies A and A implies B. A better example would perhaps be:

    A: X>Y+1
B: X>Y

    Here A would imply B, i.e. A would be sufficient for B to hold. The other way would not hold: B does not imply A (since you could have X=10 and Y=9 in which case only B would hold). This means that A is not necessary for B.

    Completeness/soundness:

    This took a while for me to wrap my head around when I first encountered it. But it's really simple!

    Suppose you have the following:

    A = { X>Y, Y>Z }
Q = X>Z

    Now, soundsess says that we can't reach crazyness by sticking to the statements of A. More formally, if Q does not hold, it can't be derived from A. Or, only valid things can be derived from A.

    It's easy to create an unsound set of statements. Take for instance

    A = { x<Y, X>Y }

    They contradict each other, so we can for instance derive X>X (which is false) by using proof by contradiction.

    Completeness says the dual: All valid things can be derived from A. Suppose that X, Y and Z are the only variables in the world, and > is the only relation in the world. Then a set of statements such as

    A = { X>Y, Y>Z }

    is complete, since for any two given variables, a and b, we can derive a>b if and only if a>b in fact holds.

    If we would only have

    A = { X>Y }  (and no knowledge about Z)

    then the set of statements would not be complete since there would be true statements about Z which we could say nothing about.

    In a nutshell: Soundness says that you can't come to crazy conclusions, and completeness says that you can reach all sensible conclusions.