iPedia Free Information Center

Information about Necessary And Sufficient Conditions

This article discusses only the formal meanings of necessary and sufficient. For the causal'' meanings see causation.
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.
  • A necessary condition of a statement must be satisfied for the statement to be true. Formally, a statement P is a necessary condition of a statement Q if Q implies P. For example, the ability to breathe is necessary to a human's survival. Likewise, 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.
  • A sufficient condition is one that, if satisfied, assures the statement's truth. Formally, a statement P is a sufficient condition of a statement Q if P implies Q. Thus, jumping is sufficient to leave the ground, since an intrinsic element of the concept jumping is leaving the ground. A number's being divisible by six is sufficient for its being even.
  • That a condition is one of necessary and sufficient does not imply the other. For instance, being a mammal is necessary but not sufficient to being human, and that a number q is rational is sufficient but not necessary to q‘s being a real number. 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 have a nonzero determinant.

Necessary conditions

The assertion that P is necessary for Q is colloquially equivalent to "Q cannot be true unless P is true." By contraposition, 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 which, taken together, constitute a sufficient condition, as shown in Example 3.

Example 1: Consider thunder, technically 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 2: 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 3: In algebra, in order 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.

Sufficient conditions

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. 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 3.

Example 1: 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 2: A U.S. president's signing a bill that Congress passed is sufficient to make the bill law, regardless of the fact that even in the event of a presidential veto it still could have become law through a congressional override.

Example 3: 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

Mathematically speaking, necessity and sufficiency are dual to one another. First, for any statements P and Q, the assertion that "P is sufficient for Q" is the same as "Q is necessary for P", for both statements mean that P implies Q. 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).

Simultaneous necessity and sufficiency

See also: Material equivalence
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 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."

See also

External links

Causality or causation denotes the relationship between one event (called cause) and another event (called effect) which is the consequence (result) of the first. [1]
..... Click the link for more information.
Logic (from Classical Greek λόγος logos; meaning word, thought, idea, argument, account, reason, or principle) is the study of the principles and criteria of valid inference and demonstration.
..... Click the link for more information.
“Iff” redirects here. For other uses, see IFF.
If and only if, in logic and fields that rely on it such as mathematics and philosophy, is a logical connective between statements which means that the truth of either one of the statements
..... Click the link for more information.
In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2.4871773339…. The real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as π and
..... Click the link for more information.
Independence Day (commonly known as the Fourth of July) is a federal holiday commemorating the adoption of the Declaration of Independence on July 4, 1776, declaring independence from the Kingdom of Great Britain.
..... Click the link for more information.
An Independence Day is an annual celebration commemorating the anniversary of a nation's assumption of independent statehood, usually after ceasing to be a colony or part of another state.
..... Click the link for more information.
Motto
"In God We Trust"   (since 1956)
"E Pluribus Unum"   ("From Many, One"; Latin, traditional)
Anthem
..... Click the link for more information.
matrix (plural matrices) is a rectangular table of elements (or entries), which may be numbers or, more generally, any abstract quantities that can be added and multiplied.
..... Click the link for more information.
In algebra, a determinant is a function depending on n that associates a scalar, det(A), to every n×n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A
..... Click the link for more information.
Contraposition is the concept of how two qualities or statements relate to each other. In mathematics, for the statement "if P, then Q" for any two propositions P and Q, the converse is "if Q, then P", the inverse
..... Click the link for more information.
Implication can refer to:
  • Logic:
  • Logical implication as regarded in mathematical logic.
  • Material conditional as regarded in philosophical logic.

..... Click the link for more information.
Algebra is a branch of mathematics concerning the study of structure, relation and quantity. The name is derived from the treatise written by the Arabic[1] mathematician, astronomer, astrologer and geographer,
..... Click the link for more information.
group is a set with a binary operation that satisfies certain axioms, detailed below. For example, the set of integers with addition is a group. The branch of mathematics which studies groups is called group theory.
..... Click the link for more information.
associativity is a property that a binary operation can have. It means that, within an expression containing two or more of the same associative operators in a row, the order of operations does not matter as long as the sequence of the operands is not changed.
..... Click the link for more information.
In logic and/or mathematics, logical conjunction or and is a two-place logical operation that results in a value of true if both of its operands are true, otherwise a value of false!

Definition

Logical conjunction
..... Click the link for more information.
or, also known as logical disjunction or inclusive disjunction is a logical operator that results in true whenever one or more of its operands are true. In grammar, or is a coordinating conjunction.
..... Click the link for more information.
In mathematics, duality has numerous meanings. Generally speaking, dualities translate concepts, theorems or mathematical structures into other concepts, theorems or structures, in a one-to-one fashion.
..... Click the link for more information.
predicate is either a relation or the boolean-valued function that amounts to the characteristic function or the indicator function of such a relation.

A function P: X→ is called a predicate on X. When P is a predicate on X, we sometimes say P is a property of X.
..... Click the link for more information.
(See also Subset for the uncapitalized use of the word "superset" in mathematics.)

SuperSet Software was a group founded by friends and former Eyring Research Institute (ERI) co-workers Drew Major, Dale Neibaur, Kyle Powell and later joined by Mark Hurst.
..... Click the link for more information.
subset of a set B if A is "contained" inside B. Notice that A and B may coincide. The relationship of one set being a subset of another is called inclusion or containment.
..... Click the link for more information.
“Iff” redirects here. For other uses, see IFF.
If and only if, in logic and fields that rely on it such as mathematics and philosophy, is a logical connective between statements which means that the truth of either one of the statements
..... Click the link for more information.
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
..... Click the link for more information.
Bipartite means having two parts, or an agreement between two parties. More specifically, it may refer to any of the following:
  • 2 (number)
In mathematics:
  • Bipartite graph
  • Bipartite Cubic, a type of Cubic function

..... Click the link for more information.
Cycle in graph theory and computer science has several meanings:
  • A closed walk, with repeated vertices allowed. See path (graph theory). (This usage is common in computer science. In graph theory it is more often called a closed walk.

..... Click the link for more information.
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 its definition. The term may also refer to the complete set of meanings or properties that are implied by a concept, although the term
..... Click the link for more information.
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 the ideas, properties, or corresponding signs that are implied or suggested by the concept in question.
..... Click the link for more information.
Causality or causation denotes the relationship between one event (called cause) and another event (called effect) which is the consequence (result) of the first. [1]
..... Click the link for more information.
The material conditional, also known as the material implication or truth functional conditional, expresses a property of certain conditionals in logic. In propositional logic, it expresses a binary truth function ⊃ from truth-values to truth-values.
..... Click the link for more information.


This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus


page counter