Editing Necessity and sufficiency (section)

==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'', <math>P \Leftarrow Q</math>, and that ''P'' is sufficient for ''Q'', <math>P \Rightarrow Q</math>.
# equivalently, it may be understood to say that ''P'' and ''Q'' is necessary for the other, <math>P \Rightarrow Q \land Q \Rightarrow P</math>, 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]] ''Q''", which is denoted by <math>P \Leftrightarrow Q</math>, whereas cases tell us that <math>P \Leftrightarrow Q</math> is identical to <math>P \Rightarrow Q \land Q \Rightarrow P</math>.

For example, in [[graph theory]] a graph ''G'' is called [[Bipartite graph|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 [[cycle (graph theory)|cycles]]. Thus, discovering whether a graph has any odd cycles tells one whether it is bipartite and conversely. A philosopher<ref name="stan">[http://plato.stanford.edu/entries/logic-intensional/ Stanford University primer, 2006].</ref> might characterize this state of affairs thus: "Although the concepts of bipartiteness and absence of odd cycles differ in [[intension]], they have identical [[extension (semantics)|extension]].<ref>"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." [http://plato.stanford.edu/entries/logic-intensional/ Stanford University primer, 2006].</ref>

In mathematics, theorems are often stated in the form "''P'' is true if and only if ''Q'' is true". <!--(The following is irrelevant and not true.)  Their proofs normally first prove sufficiency, e.g. <math>P \Rightarrow Q</math>. Secondly, the opposite is proven, <math>Q \Rightarrow P</math>
# either directly, assuming ''Q'' is true and demonstrating that the Q circle is located within P, or 
# [[Proof by contrapositive|contrapositively]], that is demonstrating that stepping outside circle of P, we fall out the ''Q'': ''assuming not P, not Q results''.

This proves that the circles for Q and P match on the Venn diagrams above.-->

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. <math>P \Leftarrow Q</math> is [[Logical equivalence|equivalent to]] <math>Q \Rightarrow P</math>, if ''P'' is necessary and sufficient for ''Q'', then ''Q'' is necessary and sufficient for ''P''. We can write <math>P \Leftrightarrow Q \equiv Q \Leftrightarrow P</math> and say that the statements "''P'' is true [[if and only if]] ''Q'', is true" and "''Q'' is true if and only if ''P'' is true" are equivalent.