Necessary Condition
   HOME

TheInfoList



OR:

In
logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
and
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two
statements Statement or statements may refer to: Common uses *Statement (computer science), the smallest standalone element of an imperative programming language *Statement (logic), declarative sentence that is either true or false *Statement, a declarative ...
. For example, in the conditional statement: "If then ", is necessary for , because the
truth Truth is the property of being in accord with fact or reality.Merriam-Webster's Online Dictionarytruth 2005 In everyday language, truth is typically ascribed to things that aim to represent reality or otherwise correspond to it, such as beliefs ...
of is guaranteed by the truth of (equivalently, it is impossible to have without ). Similarly, is sufficient for , because being true always implies that is true, but not being true does not always imply that 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 In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...
the latter is true. That is, the two statements must be either simultaneously true, or simultaneously false. In
ordinary English Ordinary language philosophy (OLP) is a philosophical methodology that sees traditional philosophical problems as rooted in misunderstandings philosophers develop by distorting or forgetting how words are ordinarily used to convey meaning in ...
(also
natural language In neuropsychology, linguistics, and philosophy of language, a natural language or ordinary language is any language that has evolved naturally in humans through use and repetition without conscious planning or premeditation. Natural languages ...
) "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.


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 A consequent is the second half of a hypothetical proposition. In the standard form of such a proposition, it is the part that follows "then". In an implication, if ''P'' implies ''Q'', then ''P'' is called the antecedent and ''Q'' is called ...
. 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''", , 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 A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
" immediately below). In other words, the antecedent ''S'' cannot be true without ''N'' being true. For example, in order for someone to be called ''S''ocrates, it is necessary for that someone to be ''N''amed. 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 ''S''ocrates is sufficient to know that someone has a ''N''ame. A ''necessary and sufficient'' condition requires that both of the implications S \Rightarrow N and N \Rightarrow S (the latter of which can also be written as S \Leftarrow N) hold. The first implication suggests that ''S'' is a sufficient condition for ''N'', while the second implication suggests that ''S'' is a necessary condition for ''N''. This is expressed as "''S'' is necessary and sufficient for ''N'' ", "''S''
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...
''N'' ", or S \Leftrightarrow 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 In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a stateme ...
, 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. ;Example 1: 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 Predicate or predication may refer to: * Predicate (grammar), in linguistics * Predication (philosophy) * several closely related uses in mathematics and formal logic: **Predicate (mathematical logic) **Propositional function **Finitary relation, ...
. ;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. One says that thunder is necessary for lightning, since lightning never occurs without thunder. Whenever there is lightning, there is 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 must be at least 30 years old. ;Example 5:In
algebra Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics. Elementary a ...
, for some
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
''S'' together with an
operation Operation or Operations may refer to: Arts, entertainment and media * ''Operation'' (game), a battery-operated board game that challenges dexterity * Operation (music), a term used in musical set theory * ''Operations'' (magazine), Multi-Ma ...
\star to form a
group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...
, it is necessary that \star 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'' \star ''x'' and ''x'' \star ''e'' both equal ''x''. It is also necessary that for every ''x'' in ''S'' there exist a corresponding element ''x″'', such that both ''x'' \star ''x″'' and ''x″'' \star ''x'' equal the special element ''e''. None of these three necessary conditions by itself is sufficient, but the
conjunction Conjunction may refer to: * Conjunction (grammar), a part of speech * Logical conjunction, a mathematical operator ** Conjunction introduction, a rule of inference of propositional logic * Conjunction (astronomy), in which two astronomical bodies ...
of the three is.


Sufficiency

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. ;Example 1:"John is a king" implies that John is male. So knowing that John is a king is sufficient to knowing that he is a male. ;Example 2:A number's being divisible by 4 is sufficient (but not necessary) for it to be even, but being divisible by 2 is both sufficient and necessary for it to be even. ;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:If the U.S. Congress passes a bill, the president's signing of the bill is sufficient to make it law. Note that the case whereby the president did not sign the bill, e.g. through exercising a presidential
veto A veto is a legal power to unilaterally stop an official action. In the most typical case, a president or monarch vetoes a bill to stop it from becoming law. In many countries, veto powers are established in the country's constitution. Veto ...
, does not mean that the bill has not become a law (for example, it could still have become a law through a congressional
override Override may refer to: * Dr. Gregory Herd, a Marvel Comics character formerly named Override * Manual override, a function where an automated system is placed under manual control * Method overriding, a subclassing feature in Object Oriented progr ...
). ;Example 5:That the center of a
playing card A playing card is a piece of specially prepared card stock, heavy paper, thin cardboard, plastic-coated paper, cotton-paper blend, or thin plastic that is marked with distinguishing motifs. Often the front (face) and back of each card has a fi ...
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 single diamond (♦), heart (♥), or club (♣). None of these conditions is necessary to the card's being an ace, but their
disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
is, since no card can be an ace without fulfilling at least (in fact, exactly) one of these conditions.


Relationship between necessity and sufficiency

A condition can be either necessary or sufficient without being the other. For instance, ''being a
mammal Mammals () are a group of vertebrate animals constituting the class Mammalia (), characterized by the presence of mammary glands which in females produce milk for feeding (nursing) their young, a neocortex (a region of the brain), fur or ...
'' (''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 In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
'' (''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 Independence Day (colloquially the Fourth of July) is a federal holiday in the United States commemorating the Declaration of Independence, which was ratified by the Second Continental Congress on July 4, 1776, establishing the United States ...
" is a necessary and sufficient condition for "today is Independence Day in the
United States The United States of America (U.S.A. or USA), commonly known as the United States (U.S. or US) or America, is a country primarily located in North America. It consists of 50 states, a federal district, five major unincorporated territorie ...
". Similarly, a necessary and sufficient condition for invertibility of a
matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
''M'' is that ''M'' has a nonzero
determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
. 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 Predicate or predication may refer to: * Predicate (grammar), in linguistics * Predication (philosophy) * several closely related uses in mathematics and formal logic: **Predicate (mathematical logic) **Propositional function **Finitary relation, o ...
''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 In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
of ''T''(''S''), while asserting the sufficiency of ''S'' for ''N'' is equivalent to claiming that ''T''(''S'') is a
subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
of ''T''(''N'').


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'', P \Leftarrow Q, and that ''P'' is sufficient for ''Q'', P \Rightarrow Q. # equivalently, it may be understood to say that ''P'' and ''Q'' is necessary for the other, P \Rightarrow Q \land Q \Rightarrow 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 In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...
''Q''", which is denoted by P \Leftrightarrow Q, whereas cases tell us that P \Leftrightarrow Q is identical to P \Rightarrow Q \land Q \Rightarrow P. For example, in
graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
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 philosopherStanford University primer, 2006
might characterize this state of affairs thus: "Although the concepts of bipartiteness and absence of odd cycles differ in
intension In any of several fields of study that treat the use of signs — for example, in linguistics, logic, mathematics, semantics, semiotics, and philosophy of language — an intension is any property or quality connoted by a word, phrase, or anoth ...
, they have identical
extension Extension, extend or extended may refer to: Mathematics Logic or set theory * Axiom of extensionality * Extensible cardinal * Extension (model theory) * Extension (predicate logic), the set of tuples of values that satisfy the predicate * E ...
."Meanings, in this sense, are often called ''intensions'', and things designated, ''extensions''. Contexts in which extension is all that matters are, naturally, called ''extensional'', while contexts in which extension is not enough are ''intensional''. Mathematics is typically extensional throughout.
Stanford University primer, 2006
In mathematics, theorems are often stated in the form "''P'' is true if and only if ''Q'' is true". 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 \Leftarrow Q is equivalent to Q \Rightarrow P, if ''P'' is necessary and sufficient for ''Q'', then ''Q'' is necessary and sufficient for ''P''. We can write P \Leftrightarrow Q \equiv Q \Leftrightarrow P and say that the statements "''P'' is true
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...
''Q'', is true" and "''Q'' is true if and only if ''P'' is true" are equivalent.


See also


References


External links

*Critical thinking web tutorial
''Necessary and Sufficient Conditions''
*Simon Fraser University

{{Logic Concepts in logic Concepts in metaphysics Dichotomies Mathematical terminology