Necessity and sufficiency

This article is about the formal terminology in logic. For causal meanings of the terms, see Causality.

In logic, 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.

1 Definitions
2 Necessity
3 Sufficiency
4 Relationship between necessity and sufficiency
5 Simultaneous necessity and sufficiency
6 See also
- 6.1 Argument forms involving necessary and sufficient conditions
  - 6.1.1 Valid forms of argument
  - 6.1.2 Invalid forms of argument (i.e. fallacies)
7 References
8 External links

Definitions [edit]

A true necessary condition in a conditional statement makes the statement true. In formal terms, a consequent N is a necessary condition for an antecedent S, in the conditional statement, "N if S", "N is implied by S", or N $\Leftarrow$ S. In common words, we would also say "N is weaker than S" or "S cannot occur without N". For example, it is necessary to be Named, to be called "Socrates".

A true sufficient condition in a conditional statement ties the statement's truth to its consequent. In formal terms, an antecedent S is a sufficient condition for a consequent N, in the conditional statement, "if S, then N", "S implies N", or S $\Rightarrow$ N. In common words, we would also say "S is stronger than N" or "S guarantees N". For example, "Socrates" suffices for a Name.

**S implies N**
S	N	S $\Rightarrow$ N
T	T	T
T	F	F
F	T	T
F	F	T

Necessity [edit]

The sun being above the horizon is a necessary condition for direct sunlight; but it is not a sufficient condition as something else may be casting a shadow, e.g. in the case of an eclipse.

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, this is the same thing as "whenever P is true, so is Q". The logical relation between them is expressed as "If P then Q" and denoted "P $\Rightarrow$ Q" (P implies Q), and may also be expressed as any of "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, 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 algebra, in order for some set S together with an operation $\star$ to form a group, 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 of the three is.

Sufficiency [edit]

That a train runs on schedule is often a sufficient condition for arriving on time (if the train arrives on time and one boards it, one will presumably arrive on time); but it is not always a necessary condition, since there are other ways to travel (if the train does not arrive on time, one might still arrive on time to one's destination through other means of transport).

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 $\Rightarrow$ 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 override).

Example 5: 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 [edit]

To satisfy S, you must be in N. When we are in S, we know that we are in N.

A condition can be either necessary or sufficient without being the other. For instance, being a mammal (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's being a real number (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" 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 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 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 of T(S), while asserting the sufficiency of S for N is equivalent to claiming that T(S) is a subset of T(N).

Simultaneous necessity and sufficiency [edit]

References [edit]

^ Stanford University primer, 2006
^ "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

External links [edit]

Critical thinking web tutorial: Necessary and Sufficient Conditions
Simon Fraser University: Concepts with examples

Logic

Overview

Academic areas	Argumentation theory Axiology Critical thinking Computability theory Formal semantics History of logic Informal logic Logic in computer science Mathematical logic Mathematics Metalogic Metamathematics Model theory Philosophical logic Philosophy Philosophy of logic Philosophy of mathematics Proof theory Set theory

Foundations	Abduction Analytic truth Antinomy A priori Deduction Definition Description Induction Inference Logical form Logical consequence Logical truth Name Necessity Meaning Paradox Possible world Presupposition Probability Reason Reasoning Reference Semantics Statement Strict implication Substitution Syntax Truth Truth value Validity

Philosophical logic

Critical thinking Informal logic	Analysis Ambiguity Argument Belief Bias Credibility Evidence Explanation Explanatory power Fact Fallacy Inquiry Opinion Parsimony Premise Propaganda Prudence Reasoning Relevance Rhetoric Rigor Vagueness

Theories of deduction	Constructivism Dialetheism Fictionalism Finitism Formalism Intuitionism Logical atomism Logicism Nominalism Platonic realism Pragmatism Realism

Metalogic Metamathematics

Cantor's theorem Church's theorem Church's thesis Consistency Effective method Foundations of mathematics Gödel's completeness theorem Gödel's incompleteness theorems Soundness Completeness Decidability Interpretation Löwenheim–Skolem theorem Metatheorem Satisfiability Independence Type–token distinction Use–mention distinction

Mathematical logic

General	Formal language Formation rule Formal system Deductive system Formal proof Formal semantics Well-formed formula Set Element Class Classical logic Axiom Natural deduction Rule of inference Relation Theorem Logical consequence Axiomatic system Type theory Symbol Syntax Theory

Traditional logic	Proposition Inference Argument Validity Cogency Syllogism Square of opposition Venn diagram

Propositional calculus Boolean logic	Boolean functions Propositional calculus Propositional formula Logical connectives Truth tables

Predicate logic	First-order Quantifiers Predicate Second-order Monadic predicate calculus

Set theory	Set Empty set Enumeration Extensionality Finite set Function Subset Power set Countable set Recursive set Domain Range Ordered pair Uncountable set

Model theory	Model Interpretation Non-standard model Finite model theory Truth value Validity

Proof theory	Formal proof Deductive system Formal system Theorem Logical consequence Rule of inference Syntax

Computability theory	Recursion Recursive set Recursively enumerable set Decision problem Church–Turing thesis Computable function Primitive recursive function

Non-classical logic

Modal logic	Alethic Axiologic Deontic Doxastic Epistemic Temporal

Intuitionism	Intuitionistic logic Constructive analysis Heyting arithmetic Intuitionistic type theory Constructive set theory

Fuzzy logic	Degree of truth Fuzzy rule Fuzzy set Fuzzy finite element Fuzzy set operations

Substructural logic	Structural rule Relevance logic Linear logic

Paraconsistent logic	Dialetheism

Description logic	Ontology Ontology language

Logicians

Anderson Aristotle Averroes Avicenna Bain Barwise Bernays Boole Boolos Cantor Carnap Church Chrysippus Curry De Morgan Frege Geach Gentzen Gödel Hilbert Kleene Kripke Leibniz Löwenheim Peano Peirce Putnam Quine Russell Schröder Scotus Skolem Smullyan Tarski Turing Whitehead William of Ockham Wittgenstein Zermelo