Necessary and Sufficient vs Soundness and Completeness

Question

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.

Answer 1

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.