Necessity and sufficiency
In logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. For example, in the conditional statement: "If P then Q", Q is necessary for P, because the truth of Q is guaranteed by the truth of P (equivalently, it is impossible to have P without Q). Similarly, P is sufficient for Q, because P being true always implies that Q is true, but P not being true does not always imply that Q is not true.
In general, a necessary condition is one that must be present in order for another condition to occur, while a sufficient condition is one that produces the said condition. The assertion that a statement is a "necessary and sufficient" condition of another means that the former statement is true if and only if the latter is true. That is, the two statements must be either simultaneously true, or simultaneously false.
In ordinary English (also natural language) "necessary" and "sufficient" indicate relations between conditions or states of affairs, not statements. For example, being a male is a necessary condition for being a brother, but it is not sufficient—while being a male sibling is a necessary and sufficient condition for being a brother. Any conditional statement consists of at least one sufficient condition and at least one necessary condition.
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 several equivalent ways, such as "N if S", "S only if N", "S implies N", "N is implied by S", S → N , S ⇒ N and "N whenever S".
In the above situation, N is said to be a necessary condition for S. In common language, this is equivalent to saying that if the conditional statement is a true statement, then the consequent N must be true—if S is to be true (see third column of "truth table" immediately below). In other words, the antecedent S cannot 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. Similarly, in order for human beings to live, it is necessary that they have air.
In the above situation, one can also say S is a sufficient condition for N (refer again to the third column of the truth table immediately below). If the conditional statement is true, then if S is true, N must be true; whereas if the conditional statement is true and N is true, then S may be true or be false. In common terms, "the truth of S guarantees the truth of N". For example, carrying on from the previous example, one can say that knowing that someone is called Socrates is sufficient to know that someone has a Name.
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 P and Q 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 (i.e., individually necessary and jointly sufficient), as shown in Example 5.
If P is sufficient for Q, then knowing P to be true is adequate grounds to conclude that Q is true; however, knowing P to be false does not meet a minimal need to conclude that Q is false.
The logical relation is, as before, expressed as "if P, then Q" or "P ⇒ Q". This can also be expressed as "P only if Q", "P implies Q" or several other variants. It may be the case that several sufficient conditions, when taken together, constitute a single necessary condition (i.e., individually sufficient and jointly necessary), as illustrated in example 5.
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).
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.
This proves that the circles for Q and P match on the Venn diagrams above.