Understanding soundness/completeness as "validity classification"?
Posted: Thu Mar 09, 2017 5:33 am
I want to test my understanding of soundness and completeness. In particular, I will attempt to describe it in terms of *validity classification* where "positive" relates to "valid", and "negative" relates to "invalid", hence we can judge a classification to be one of (*true positive/false positive/true negative/false negative*). Finally I will consider some example scenarios where the notions of soundness and completeness are applied to draw conclusions (in particular with a specific proof method - proof trees).
#Definitions
Def. An **argument** is a statement of the form "(A and B and C and ... ) implies Z", where (A,B,C,...) is the set of premises and Z is the conclusion.
Def. **Validity** is a property of *arguments*, ie. a given argument is either valid or invalid. Roughly speaking, validity is the property that whenever the premises are true, the conclusion is also true.
Def. A **proof method** is a formal process for *classifying* a given argument as either valid or invalid. Examples of proof methods include proof trees, clausal resolution, an algorithm which examines every line of a truth table, etc.
Def. **Soundness** is a property of *proof methods*, ie. a given proof method is either sound or unsound. If a proof method is "sound", then whenever the method indicates that an argument is valid, we can be sure it is indeed valid. In other words, the proof method **never yields a "false positive"** (ie. incorrectly classifying an argument is valid when in fact it isn't).
Def. **Completeness** is a property of *proof methods*, ie. a given proof method is either complete or incomplete. If a proof method is "complete", then whenever the method indicates that an argument is invalid, we can be sure that it is indeed invalid. In other words, the proof method **never yields a "false negative"** (ie. incorrectly classifying an argument as invalid when it actually is valid).
Observations
- If a proof method is **sound but incomplete**, then I can trust its "valid" classifications but I should mistrust it's "invalid" classifications.
- If a proof method is **complete but unsound**, then I can trust its "invalid" classifications, but I should mistrust its "valid" classifications.
- If a proof method is **both unsound and incomplete**, then I should mistrust all of its classifications!
- However if a proof method is **sound and complete**, then I can always trust its classifications, as it classifies both valid and invalid arguments infallibly.
Example scenarios
Example 1
Suppose a Faulty Logician friend gave me a novel proof method. I use it on an argument which I already know is **actually invalid**, and yet the proof method **classifies it as valid**! This is a **false positive**, which never happens with *sound* proof method. Hence I can conclude that the proof method given to me is **unsound** (but know nothing about its completeness yet).
Example 2
Suppose this Faulty Logician handed me another novel proof method. I use it on an argument which I already know is **actually valid**, and yet the proof method **classifies it as invalid**! This is a **false negative**, which never happens in a *complete* proof method. Hence I can conclude that the proof method given to me is **incomplete** (but know nothing about its soundness yet).
(12-second recap of proof trees as a particular proof method)
Using proof trees as a proof method involves:
- Starting with the list of premises and the *negated* conclusion, ie. the set of statements (A,B,C,...,~Z)
- Using various (sound and complete) branching rules to grow the tree and close branches off (I will not attempt to describe here)
- If all branches of the tree for (A,B,C,...,~Z) close, then the original argument "A and B and C and ... implies Z" is classified as **valid**
- However if one or more branches of the tree for (A,B,C,...,~Z) are completely finished and yet remain open, then the original argument "A and B and C and ... implies Z" is classified as **invalid**
Example 3
Suppose my Faulty Logician friend turned his attention to proof trees, and invented a novel proof tree method with faulty rules such that the trees for (A,B,C...~Z) actually **stayed open more often** than they should (but never closed when they shouldn't)! This leads us to classify arguments as invalid more often than we should, hence the method yields **false negatives** (but never false positives). Of course, this doesn't happen with a *complete* proof method, so I conclude that the proof method is **incomplete** (but still sound).
Example 4
Suppose the Faulty Logician, a bit flustered now, invented yet another proof tree method with faulty rules such that the trees resulting from various roots (A,B,C...~Z) actually **closed more often** than they should (but never remained open when they shouldn't)! This leads us to classify some arguments as valid when we shouldn't, hence the method yields **false positives** (but never false negatives). Of course, this doesn't happen with a *sound* proof method, so I conclude that the proof method is **unsound** (but still complete).
Example 5
Suppose in a final fit of rage the Faulty Logician invented a proof tree method which faulty rules such that the trees resulting from various roots (A,B,C...~Z) sometimes **closed when they should remain open**, and sometimes **remained open when they should close**!
We sometimes incorrectly label arguments as valid, and sometimes incorrectly label arguments as invalid as well, yielding both **false positives** and **false negatives**. Thus the proof method lacks both soundness and completeness, hence I conclude that the proof method is **unsound and incomplete**.
#Definitions
Def. An **argument** is a statement of the form "(A and B and C and ... ) implies Z", where (A,B,C,...) is the set of premises and Z is the conclusion.
Def. **Validity** is a property of *arguments*, ie. a given argument is either valid or invalid. Roughly speaking, validity is the property that whenever the premises are true, the conclusion is also true.
Def. A **proof method** is a formal process for *classifying* a given argument as either valid or invalid. Examples of proof methods include proof trees, clausal resolution, an algorithm which examines every line of a truth table, etc.
Def. **Soundness** is a property of *proof methods*, ie. a given proof method is either sound or unsound. If a proof method is "sound", then whenever the method indicates that an argument is valid, we can be sure it is indeed valid. In other words, the proof method **never yields a "false positive"** (ie. incorrectly classifying an argument is valid when in fact it isn't).
Def. **Completeness** is a property of *proof methods*, ie. a given proof method is either complete or incomplete. If a proof method is "complete", then whenever the method indicates that an argument is invalid, we can be sure that it is indeed invalid. In other words, the proof method **never yields a "false negative"** (ie. incorrectly classifying an argument as invalid when it actually is valid).
Observations
- If a proof method is **sound but incomplete**, then I can trust its "valid" classifications but I should mistrust it's "invalid" classifications.
- If a proof method is **complete but unsound**, then I can trust its "invalid" classifications, but I should mistrust its "valid" classifications.
- If a proof method is **both unsound and incomplete**, then I should mistrust all of its classifications!
- However if a proof method is **sound and complete**, then I can always trust its classifications, as it classifies both valid and invalid arguments infallibly.
Example scenarios
Example 1
Suppose a Faulty Logician friend gave me a novel proof method. I use it on an argument which I already know is **actually invalid**, and yet the proof method **classifies it as valid**! This is a **false positive**, which never happens with *sound* proof method. Hence I can conclude that the proof method given to me is **unsound** (but know nothing about its completeness yet).
Example 2
Suppose this Faulty Logician handed me another novel proof method. I use it on an argument which I already know is **actually valid**, and yet the proof method **classifies it as invalid**! This is a **false negative**, which never happens in a *complete* proof method. Hence I can conclude that the proof method given to me is **incomplete** (but know nothing about its soundness yet).
(12-second recap of proof trees as a particular proof method)
Using proof trees as a proof method involves:
- Starting with the list of premises and the *negated* conclusion, ie. the set of statements (A,B,C,...,~Z)
- Using various (sound and complete) branching rules to grow the tree and close branches off (I will not attempt to describe here)
- If all branches of the tree for (A,B,C,...,~Z) close, then the original argument "A and B and C and ... implies Z" is classified as **valid**
- However if one or more branches of the tree for (A,B,C,...,~Z) are completely finished and yet remain open, then the original argument "A and B and C and ... implies Z" is classified as **invalid**
Example 3
Suppose my Faulty Logician friend turned his attention to proof trees, and invented a novel proof tree method with faulty rules such that the trees for (A,B,C...~Z) actually **stayed open more often** than they should (but never closed when they shouldn't)! This leads us to classify arguments as invalid more often than we should, hence the method yields **false negatives** (but never false positives). Of course, this doesn't happen with a *complete* proof method, so I conclude that the proof method is **incomplete** (but still sound).
Example 4
Suppose the Faulty Logician, a bit flustered now, invented yet another proof tree method with faulty rules such that the trees resulting from various roots (A,B,C...~Z) actually **closed more often** than they should (but never remained open when they shouldn't)! This leads us to classify some arguments as valid when we shouldn't, hence the method yields **false positives** (but never false negatives). Of course, this doesn't happen with a *sound* proof method, so I conclude that the proof method is **unsound** (but still complete).
Example 5
Suppose in a final fit of rage the Faulty Logician invented a proof tree method which faulty rules such that the trees resulting from various roots (A,B,C...~Z) sometimes **closed when they should remain open**, and sometimes **remained open when they should close**!
We sometimes incorrectly label arguments as valid, and sometimes incorrectly label arguments as invalid as well, yielding both **false positives** and **false negatives**. Thus the proof method lacks both soundness and completeness, hence I conclude that the proof method is **unsound and incomplete**.