Necessary and sufficient conditions

From Wikipedia, the free encyclopedia

This article or section needs copy editing for grammar, style, cohesion, tone and/or spelling.
You can assist by editing it now. A how-to guide is available, as is general documentation.
This article has been tagged since January 2007.

This article discusses only the formal meanings of necessary and sufficient. For the causal meanings see causation.

In logic, the words necessary and sufficient describe the conditions of a statement. A necessary and sufficient condition of a statement is one that is true if and only if the statement is true.

A necessary condition is one that 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 stay alive; if you did not have the ability to breathe, you would not stay alive. Breathing is not sufficient to stay alive, however, because even if you breathe, you can still die. It is necessary that a prime number p greater than two be odd; it is not sufficient for p to be odd for it to be prime. (There are composite odd numbers.)

A sufficient condition is one that, if satisfied, guarantees the statement will be true. Formally, a statement P is a sufficient condition of a statement Q if P implies Q. Jumping is sufficient to leave the ground, since the act of jumping causes one to leave the ground. Jumping is not necessary to leave the ground however, since one can leave the ground in other ways. A number's being divisible by six is sufficient for it to be even, but not necessary (there exist even numbers not divisible by six).

Some conditions 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 United States Independence Day". It is a necessary and sufficient condition for a matrix to be invertible that its determinant be non-zero. Tautologically, it is necessary and sufficient for a matrix to be an element of the General Linear Group that it be invertible (non-singular).

1 Necessary conditions
2 Sufficient conditions
3 Relationship between "necessary" and "sufficient"
4 Necessary and sufficient conditions
5 See also
6 External links

[edit] Necessary conditions

Lightning is both necessary and sufficient for thunder, and vice versa. This is because the two events are part of the same phenomenon.

To say that P is necessary for Q is to say "if P is not true, then Q is not 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" or "Q $\Rightarrow$ P" (Q implies P), and may also be seen as "P, if Q", "P whenever Q" or "P when Q". In many cases, a necessary condition is part of a set of conditions, as shown in Example 3.

Example 1: Consider the statement "Being a dictator is necessary for being the Twiz." Here if you are not a dictator then it is impossible for you to be the Twiz. That is, if you are the Twiz, then you are automatically a dictator.

Example 2: Suppose that any lightning bolt causes thunder (however quiet the thunder may be) and suppose that by "thunder" we mean the sound caused by lightning (and not any other loud rumbling). Then it might be said "thunder is necessary for lightning", for if there is absolutely no thunder, then there cannot be any lightning. That is, if lightning does occur, then it must create some thunder.

Example 3: As an example of something not being a necessary condition, consider the rectangle/square example. Notice that being a square is not a necessary condition for being a rectangle, since there are rectangles that are not squares. On the other hand, being a rectangle is necessary for a square albeit with another condition of equal sides.

Example 4: An operational power supply is necessary for a computer to function, as is an operational monitor, etc.

[edit] Sufficient conditions

To say that P is sufficient for Q is to say that P being true forces Q to be true, or whenever P occurs, Q occurs. The logical relation is expressed as "If P then Q" or "P $\Rightarrow$ Q", and may also be seen as "P implies Q." A true sufficient statement can imply a lot as shown in the case of the square/rectangle relationship, Example 5.

Example 1: For simplicity, let us suppose everyone is biologically male or female, and that a "father" is a biological male who has fathered a child. Then "being a father is sufficient for being male".

Example 2: As in the previous section, let us define "thunder" as the sound that lightning creates. Then "thunder is sufficient for lightning." For if one hears thunder, then some lightning must have occurred in order to create the thunder.

Example 3: As an example of a condition being NOT sufficient, consider the "male/father" example. Being male is NOT sufficient for being a father, since there are males that are not fathers.

Example 4: A "functioning computer" is a sufficient condition to assume an operational power supply, operational monitor, etc.

Example 5: Being a square is a sufficient condition for being a rectangle. Too, being a square is sufficient to having equal-length sides. This sufficient dual is the converse of that shown in Necessary Conditions, Example 3.

[edit] Relationship between "necessary" and "sufficient"

The statement that "P is sufficient for Q" is the same as "Q is necessary for P", for both statements are the same as "P implies Q".

Example: Recall "Being a rectangle is necessary for being a square". Also, "being a square is sufficient for being a rectangle."

[edit] Necessary and sufficient conditions

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

P is necessary for Q (P $\Leftarrow$ Q)
P is sufficient for Q (P $\Rightarrow$ Q)

For example, if Alice always eats steak on Monday, but never on any other day, it can be said "being Monday is a necessary condition for Alice eating steak." This is so since Alice does not eat steak on days that are not Monday. Also, "being Monday is a sufficient condition for Alice eating steak." This is true since Alice always eats steak on Monday.

Consider the thunder/lightning example as outlined in previous sections. "Thunder is necessary for lightning", since absolutely no thunder means there isn't any lightning to create any noise. "Thunder is sufficient for lightning" since thunder (as we have narrowly defined it) must have originated from some lightning.

The relationship between being a square and being a rectangle is one which is NOT "necessary and sufficient" despite the ordering of the conditions "square" and "rectangle". "Being a rectangle is necessary for being a square", yet "being a rectangle is NOT sufficient for being a square". "Being a square is sufficient for being a rectangle", yet "being a square is NOT necessary for being a rectangle." As seen in Necessary conditions (Example 3) and Sufficient conditions (Example 5), there are multiple conditions involved in the rectangle/square relationship.

In the Gregorian calendar, there is an example of this concept. February is noted as the only month that has less than 30 days. So, this relationship works both ways; whether the statement starts from February and concludes 'less than 30 days' or the statement starts with 'less than 30 days' and concludes February, it works as it ought as a tautology. If only things were always so simple, as the relationship falls apart when one considers the specifics of 28 or 29 days. Given either of these numbers of days which is less than 30, it is necessary or sufficient to conclude February. However given that February is the starting point, more information is needed to determine whether it has 28 or 29 days, namely whether or not it's a leap year.

"P is necessary and sufficient for Q" expresses the same thing as "P if and only if Q" (P $\Leftrightarrow$ Q).