Necessity and sufficiency

Definitions

In the conditional statement, "if S then N", the expression represented by S is called the antecedent and the expression represented by N is called the consequent. This conditional statement may be written in many equivalent ways, for instance, "N if S", "S implies N", "S only if N", "N is implied by S", S ⇒ N or "N whenever S".

In the above situation, we also say that N is a necessary condition for S. In common language this is saying that if the conditional statement is a true statement, then the consequent N must be true if S has any chance of being true (see "truth table" immediately below). Phrased differently, the antecedent S can not be true without N being true. For example, in order for someone to be called Socrates, it is necessary for that someone to be Named.

We also say that S is a sufficient condition for N. Consider the truth table again. If the conditional statement is true, then if S is true, N must be true. In common terms, "S" guarantees N". Continuing the example, knowing that someone is called Socrates is sufficient to know that that someone has a Name.

A necessary and sufficient condition requires that both of the implications S ⇒ N and N ⇒ S (which can also be written as S ⇐ N) hold. From the first of these we see that S is a sufficient condition for N, and from the second that S is a necessary condition for N. This is expressed as "S is necessary and sufficient for N ", "S if and only if N ", or S ⇔ N.

Necessity

The assertion that Q is necessary for P is colloquially equivalent to "P cannot be true unless Q is true" or "if Q is false, then P is false". By contraposition, this is the same thing as "whenever P is true, so is Q". The logical relation between them is expressed as "if P, then Q" and denoted "P ⇒ Q" (P implies Q). It may also be expressed as any of "P only if Q", "Q, if P", "Q whenever P", and "Q when P". One often finds, in mathematical prose for instance, several necessary conditions that, taken together, constitute a sufficient condition, as shown in Example 5.

Example 1

For it to be true that "John is a bachelor", it is necessary that it be also true that he is

1. unmarried,
2. male,
3. adult,

since to state "John is a bachelor" implies John has each of those three additional predicates.

Example 2

For the whole numbers greater than two, being odd is necessary to being prime, since two is the only whole number that is both even and prime.

Example 3

Consider thunder, the sound caused by lightning. We say that thunder is necessary for lightning, since lightning never occurs without thunder. Whenever there's lightning, there's thunder. The thunder does not cause the lightning (since lightning causes thunder), but because lightning always comes with thunder, we say that thunder is necessary for lightning. (That is, in its formal sense, necessity doesn't imply causality.)

Example 4

Being at least 30 years old is necessary for serving in the U.S. Senate. If you are under 30 years old, then it is impossible for you to be a senator. That is, if you are a senator, it follows that you are at least 30 years old.

Example 5

In algebra, for some set S together with an operation ⋆ to form a group, it is necessary that ⋆ be associative. It is also necessary that S include a special element e such that for every x in S it is the case that e ⋆ x and x ⋆ e both equal x. It is also necessary that for every x in S there exist a corresponding element x "such that both x ⋆ x " and x" ⋆ x equal the special element e. None of these three necessary conditions by itself is sufficient, but the conjunction of the three is.

Sufficiency

To say that P is sufficient for Q is to say that, in and of itself, knowing P to be true is adequate grounds to conclude that Q is true. (However, knowing P not to be true does not, in and of itself, provide adequate grounds to conclude that Q is not true.) The logical relation is expressed as "if P, then Q" or "P ⇒ Q" and may also be expressed as "P only if Q" or "P implies Q". Several sufficient conditions may, taken together, constitute a single necessary condition, as illustrated in example 5.

Example 1

Stating that "John is a bachelor" implies that John is male. So knowing that it is true that John is a bachelor is sufficient to know that he is a male.

Example 2

A number's being divisible by 4 is sufficient (but not necessary) for its being even, but being divisible by 2 is both sufficient and necessary.

Example 3

An occurrence of thunder is a sufficient condition for the occurrence of lightning in the sense that hearing thunder, and unambiguously recognizing it as such, justifies concluding that there has been a lightning bolt.

Example 4

A U.S. president's signing a bill that Congress passed is sufficient to make the bill law. Note that the case whereby the president did not sign the bill, e.g. through exercising a presidential veto, does not mean that the bill has not become law (it could still have become law through a congressional override).

Example 5

That the center of a playing card should be marked with a single large spade (♠) is sufficient for the card to be an ace. Three other sufficient conditions are that the center of the card be marked with a diamond (♦), heart (♥), or club (♣), respectively. None of these conditions is necessary to the card's being an ace, but their disjunction is, since no card can be an ace without fulfilling at least (in fact, exactly) one of the conditions.

Relationship between necessity and sufficiency

A condition can be either necessary or sufficient without being the other. For instance, being a mammal (N) is necessary but not sufficient to being human (S), and that a number x is rational (S) is sufficient but not necessary to x being a real number (N) (since there are real numbers that are not rational).

A condition can be both necessary and sufficient. For example, at present, "today is the Fourth of July" is a necessary and sufficient condition for "today is Independence Day in the United States". Similarly, a necessary and sufficient condition for invertibility of a matrix M is that M has a nonzero determinant.

Mathematically speaking, necessity and sufficiency are dual to one another. For any statements S and N, the assertion that "N is necessary for S" is equivalent to the assertion that "S is sufficient for N". Another facet of this duality is that, as illustrated above, conjunctions (using "and") of necessary conditions may achieve sufficiency, while disjunctions (using "or") of sufficient conditions may achieve necessity. For a third facet, identify every mathematical predicate N with the set T(N) of objects, events, or statements for which N holds true; then asserting the necessity of N for S is equivalent to claiming that T(N) is a superset of T(S), while asserting the sufficiency of S for N is equivalent to claiming that T(S) is a subset of T(N).

Simultaneous necessity and sufficiency

To say that P is necessary and sufficient for Q is to say two things:

1. that P is necessary for Q, P ⇐ Q , and that P is sufficient for Q, P ⇒ Q .
2. equivalently, it may be understood to say that P and Q is necessary for the other, P ⇒ Q ∧ Q ⇒ P , which can also be stated as each is sufficient for or implies the other.

One may summarize any, and thus all, of these cases by the statement "P if and only if Q", which is denoted by P ⇔ Q , whereas cases tell us that P ⇔ Q is identical to P ⇒ Q ∧ Q ⇒ P .

For example, in graph theory a graph G is called bipartite if it is possible to assign to each of its vertices the color black or white in such a way that every edge of G has one endpoint of each color. And for any graph to be bipartite, it is a necessary and sufficient condition that it contain no odd-length cycles. Thus, discovering whether a graph has any odd cycles tells one whether it is bipartite and conversely. A philosopher might characterize this state of affairs thus: "Although the concepts of bipartiteness and absence of odd cycles differ in intension, they have identical extension.

In mathematics, theorems are often stated in the form "P is true if and only if Q is true". Their proofs normally first prove sufficiency, e.g. P ⇒ Q . Secondly, the opposite is proven, Q ⇒ P

1. either directly, assuming Q is true and demonstrating that the Q circle is located within P, or
2. contrapositively, that is demonstrating that stepping outside circle of P, we fall out the Q: assuming not P, not Q results.

This proves that the circles for Q and P match on the Venn diagrams above.

Because, as explained in previous section, necessity of one for the other is equivalent to sufficiency of the other for the first one, e.g. P ⇐ Q is equivalent to Q ⇒ P , if P is necessary and sufficient for Q, then Q is necessary and sufficient for P. We can write P ⇔ Q ≡ Q ⇔ P and say that the statements "P is true if and only if Q, is true" and "Q is true if and only if P is true" are equivalent.