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.
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments