# Proving a theorem, what is meant by sufficiency and necessity?

I am looking at the proof of a theorem and the proof begins by saying

...is the proof of the sufficiency part of this theorem so we just need to establish the necessity of the condition.

What is the sufficiency part and the necessity part of the theorem?

• We want to prove B. Can knowing if A is true help? If $A \implies B$ then, yes, all we have to do is prove A and then B is automatic. It is "sufficient" to prove A. Now there might be other ways and A might not need to be true for B to happen, but if we can prove A it will be "sufficient"... but on the other hand ... If $A \implies B$ (or $- A \implies - B$) then we absolutely must have A be true. It is "nescessary" that A be true for B to be true. Jul 11, 2016 at 17:51
• @fleablood: Do you mean "but on the other hand ... If $B \Longrightarrow A$ (or $A \Longleftarrow B$, or $\lnot A \Longrightarrow \lnot B$) then we absolutely must have A be true."? Jul 12, 2016 at 6:22
• Hmm, I guess I did. If b => a (or -a => b)... is what I meant. Jul 12, 2016 at 6:29

## 7 Answers

It is essentially a biconditional, also known as an if and only if.

An "if and only if" statement goes both ways. That is, $p\iff q$ means "if $p$ is true then $q$ is true" and "if $q$ is true then $p$ is true."

The statement "$p$ is sufficient for $q$" means "if $p$ is true, then $q$ is true."

The statement "$p$ is necessary for $q$" means that if we don't have $p$, then we don't have $q$. Therefore, if we have $q$, we certainly have $p$. In other words, "$q$ implies $p$."

When we put the two together, a necessary and sufficient condition is the same as an if and only if.

A condition A is called sufficient for a statement B to hold if A implies B.

A condition A is called necessary for a statement B to hold if B implies A.

"Necessary and sufficient" is the same as equivalent

Consider two statements $A$ and $B$; and we want to know conditions on $A$ for $B$ to be true

Sufficient condition: $A$ is true implies $B$ is true

Necessary conditions: For $B$ to be true, $A$ must be true. It can happen that $A$ is true but $B$ might not be true ( so condition on $A$ is not sufficient).

Sometimes relating math to "everyday" simple English is helpful. Sufficiency and necessary theorems (or proofs) means a two-way mutual affair between some two things: $$A$$ and $$B$$ ie. if $$A$$ happens implies $$B$$ has also happens. The reverse is the same (or vice-versa).

So, to prove this kind of theorems, a prior knowledge on either one of the two things is very paramount. You can decide to prove it from the forward direction $$(\Rightarrow)$$ also known as the $$\textbf{sufficiency}$$ or from the backward direction $$(\Leftarrow)$$ also know as the $$\textbf{necessity}.$$ Thus, combining the two directions we have: $$A\Leftrightarrow B.$$

The proof goes like this:

$$\textbf{sufficiency}$$ $$(\Rightarrow)$$ if $$A$$ is true implies that $$B$$ is also true. Now, what do you know about $$A$$ that will help you realize that $$B$$ is also true? If you are able to figure it out, then this forward direction is done.

$$\textbf{necessity}$$ $$(\Leftarrow)$$ if $$B$$ is true implies that $$A$$ is also true. Now, what do you know about $$B$$ that will help you realize that $$A$$ is also true? If you are able to figure it out, then this backward direction is done. End of proof.

Every car has wheels, but not every wheeled vehicle is a car.

So, having wheels is a necessary condition on a car, but not a sufficient one.

Conversely, a car is a type of wheeled vehicle, so it is sufficient that if a vehicle is a car, it is a wheeled vehicle; but it is not necessary that a vehicle be a car in order for it to have wheels.

Suppose a theorem says that

An edge is a cut-edge if and only if it belongs to no cycle.

We need to prove it.

Sufficiency

An edge is a cut-edge if it belongs to no cycle.

Edge belongs to no cycle => Edge is a cut-edge.

Necessity

An edge is a cut-edge only if it belongs to no cycle.

Edge is a cut-edge => Edge belongs to no cycle.

• I think this is the opposite. Oct 7, 2022 at 5:31

The terms "necessity" and "sufficiency" in the context of a proof are really somewhat ambiguous, and they are sometimes used by different authors in different ways.

Consider the claim "$$A$$ if and only if $$B$$".

Then we have:

• $$A$$ if $$B$$, which means $$(B \implies A)$$. So $$B$$ is sufficient for $$A$$.
• $$A$$ only if $$B$$, which menas $$(A \implies B)$$. So $$B$$ is necessary for $$A$$.

But also:

• $$B$$ if $$A$$, which means $$(A \implies B)$$. So $$A$$ is sufficient for $$B$$.
• $$B$$ only if $$A$$, which means $$(B \implies A)$$. So $$A$$ is necessary for $$B$$.