Necessary and sufficient conditions
Encyclopedia
In logic
, the words necessity and sufficiency refer to the implicational relationships between statements
. The assertion that one statement is a necessary and sufficient condition of another means that the former statement is true if and only if
the latter is true.
P).
A sufficient condition is one that, if satisfied, assures the statement's truth. In formal terms, a statement P is a sufficient condition of a statement Q if P implies Q (P
Q).
, this is the same thing as "whenever Q is true, so is P". The logical relation between them is expressed as "If Q then P" and denoted "Q
P" (Q implies P), and may also be expressed as any of "P, if Q"; "P whenever Q"; and "P when Q." One often finds, in mathematical prose for instance, several necessary conditions that, taken together, constitute a sufficient condition, as shown in Example 5.
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. (It is to say, at the same time, that knowing P not to be true does not, in and of itself, provide adequate grounds to conclude that Q is not true, either.) The logical relation is expressed as "If P then Q" or "P 
Q," and may also be expressed as "P implies Q." Several sufficient conditions may, taken together, constitute a single necessary condition, as illustrated in example 5.
(Q) (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 P and Q, the assertion that “P is necessary for Q” is equivalent to the assertion that “Q is sufficient for P.” Another facet of this duality is that, as illustrated above, conjunctions of necessary conditions may achieve sufficiency, while disjunctions of sufficient conditions may achieve necessity. For a third facet, identify every mathematical predicate P with the set S(P) of objects for which P holds true; then asserting the necessity of P for Q is equivalent to claiming that S(P) is a superset
of S(Q), while asserting the sufficiency of P for Q is equivalent to claiming that S(P) is a subset
of S(Q).
Q.
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 vice versa. 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
.
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
, the words necessity and sufficiency refer to the implicational relationships between statements
Statement (logic)
In logic a statement is either a meaningful declarative sentence that is either true or false, or what is asserted or made by the use of a declarative sentence...
. The assertion that one statement is a necessary and sufficient condition of another means that the former statement is true if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
the latter is true.
Definitions
A necessary condition of a statement must be satisfied for the statement to be true. In formal terms, a statement P is a necessary condition of a statement Q if Q implies P (Q P).A sufficient condition is one that, if satisfied, assures the statement's truth. In formal terms, a statement P is a sufficient condition of a statement Q if P implies Q (P
Q).Necessary conditions
The assertion that P is necessary for Q is colloquially equivalent to "Q cannot be true unless P is true," or "if P is false then Q is false." By contrapositionContraposition
In traditional logic, contraposition is a form of immediate inference in which from a given proposition another is inferred having for its subject the contradictory of the original predicate, and in some cases involving a change of quality . For its symbolic expression in modern logic see the rule...
, this is the same thing as "whenever Q is true, so is P". The logical relation between them is expressed as "If Q then P" and denoted "Q
P" (Q implies P), and may also be expressed as any of "P, if Q"; "P whenever Q"; and "P when Q." 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: In order for it to be true that "John is a bachelor," it is necessary that it be also true that he is
- unmarried
- male
- 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, in the technical sense, the acoustic quality demonstrated by the shock wave that inevitably results from any lightning bolt in the atmosphere. It may fairly be said that thunder is necessary for lightning, since lightning cannot occur without thunder, too, occurring. That is, if lightning does occur, then there is thunder.
- Example 4: Being at least 30 years old is necessary of 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 algebraAlgebraAlgebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
, in order for some set S together with an operationBinary operationIn mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
to form a groupGroup (mathematics)In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
, 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.
Sufficient conditions
Q," and may also be expressed as "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 overrideVeto overrideA veto override is an action by legislators and decision-makers to override an act of veto by someone with such powers - thus forcing through a new decision. The power to override a veto varies greatly in tandem with the veto power itself. The U.S constitution gives a 2/3 majority Congress the...
).
- Example 5: That the center of a playing cardPlaying cardA playing card is a piece of specially prepared heavy paper, thin cardboard, plastic-coated paper, cotton-paper blend, or thin plastic, marked with distinguishing motifs and used as one of a set for playing card games...
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 (P) is necessary but not sufficient to being human (Q), and that a number q is rational (P) is sufficient but not necessary to q‘s being a real numberReal number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
(Q) (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
Independence Day
An Independence Day is an annual event commemorating the anniversary of a nation's assumption of independent statehood, usually after ceasing to be a colony or part of another nation or state, and more rarely after the end of a military occupation...
in the United States
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
." Similarly, a necessary and sufficient condition for invertibility of a matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
M is that M has a nonzero determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
.
Mathematically speaking, necessity and sufficiency are dual
Duality (mathematics)
In mathematics, a duality, generally speaking, translates concepts, theorems or mathematical structures into other concepts, theorems or structures, in a one-to-one fashion, often by means of an involution operation: if the dual of A is B, then the dual of B is A. As involutions sometimes have...
to one another. For any statements P and Q, the assertion that “P is necessary for Q” is equivalent to the assertion that “Q is sufficient for P.” Another facet of this duality is that, as illustrated above, conjunctions of necessary conditions may achieve sufficiency, while disjunctions of sufficient conditions may achieve necessity. For a third facet, identify every mathematical predicate P with the set S(P) of objects for which P holds true; then asserting the necessity of P for Q is equivalent to claiming that S(P) is a superset
SuperSet
SuperSet Software was a group founded by friends and former Eyring Research Institute co-workers Drew Major, Dale Neibaur, Kyle Powell and later joined by Mark Hurst...
of S(Q), while asserting the sufficiency of P for Q is equivalent to claiming that S(P) is a subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of S(Q).
Simultaneous necessity and sufficiency
To say that P is necessary and sufficient for Q is to say two things, that P is necessary for Q and that P is sufficient for Q. Of course, it may instead be understood to say a different two things, namely that each of P and Q is necessary for the other. And it may be understood in a third equivalent way: as saying that each is sufficient for 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.For example, in graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
a graph G is called bipartite
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
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
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
. Thus, discovering whether a graph has any odd cycles tells one whether it is bipartite and vice versa. A philosopher
might characterize this state of affairs thus: "Although the concepts of bipartiteness and absence of odd cycles differ in intension
Intension
In linguistics, logic, philosophy, and other fields, an intension is any property or quality connoted by a word, phrase or other symbol. In the case of a word, it is often implied by the word's definition...
, they have identical extension
Extension (semantics)
In any of several studies that treat the use of signs - for example, in linguistics, logic, mathematics, semantics, and semiotics - the extension of a concept, idea, or sign consists of the things to which it applies, in contrast with its comprehension or intension, which consists very roughly of...
.
See also
- CausationCausalityCausality is the relationship between an event and a second event , where the second event is understood as a consequence of the first....
- Material implication
- Wason selection taskWason selection taskDevised in 1966 by Peter Cathcart Wason, the Wason selection task, one of the most famous tasks in the psychology of reasoning, is a logic puzzle which is formally equivalent to the following question:...
- Closed conceptClosed conceptA closed concept is a concept where all the necessary and sufficient conditions required to include something within the concept can be listed. For example, the concept of a triangle is closed because a three-sided polygon, and only a three-sided polygon, is a triangle...
Invalid forms of argument (i.e. fallacies)
- Affirming the consequentAffirming the consequentAffirming the consequent, sometimes called converse error, is a formal fallacy, committed by reasoning in the form:#If P, then Q.#Q.#Therefore, P....
- Denying the antecedentDenying the antecedentDenying the antecedent, sometimes also called inverse error, is a formal fallacy, committed by reasoning in the form:The name denying the antecedent derives from the premise "not P", which denies the "if" clause of the conditional premise....
External links
- Critical thinking web tutorial: Necessary and Sufficient Conditions
- Simon Fraser University: Concepts with examples