PROOF 113

Prove.

Necessary and sufficient conditions are containment

In propositional logic.

A way to read this proof

First separate what is assumed from what is to be proved. At each step, ask which definition or earlier result permits the move. If it is unclear, return to that premise rather than skipping to the conclusion.

Definition D1

For propositions p, q, when p → q holds, p is called a sufficient condition for q and q a necessary condition for p. When both directions hold, they are necessary and sufficient for each other.

Proof.

This definition merely attaches names; it does not yet say why the names are justified.convention

∎

Definition D2

For a condition p on a universal set U, P = {x ∈ U : p(x) is true} is called the truth set of p.

Proof.

A condition is a sentence whose truth is determined by inserting x, and the truth set collects the elements that make the condition true.convention

∎

Definition D3

P ⊆ Q means every element of P is an element of Q.

Proof.

Containment is a claim about each individual element, not a comparison of the sizes of two sets.convention

∎

Theorem T1

When p → q, the truth of p alone settles q.

Proof.

(1)Suppose p → q.assumption

(2)Suppose p is true.assumption

(3)By modus ponens, q is true.(1), (2), A1

(4)Since p → q, p is a sufficient condition for q.(1), (3), D1

∎

Theorem T2

When p → q, if q is false, then p is false as well.

Proof.

(1)Suppose p → q.assumption

(2)p → q ⟺ ¬q → ¬pA2

(3)Hence ¬q → ¬p.(1), (2), E

(4)Suppose q is false; that is, ¬q is true.assumption, A3

(5)By modus ponens, ¬p is true.(3), (4), A1

(6)That is, p is false.(5), A3

(7)If q fails, p cannot hold either. This is the ground for calling q a necessary condition.(6), D1

∎

Theorem T3

For conditions p, q, write p ⟹ q when p(x) → q(x) holds for every x. Then p ⟹ q if and only if P ⊆ Q.

Proof.

(1)Suppose p(x) → q(x) for every x.assumption

(2)Suppose a ∈ P; that is, p(a) is true.assumption, D2

(3)Putting x = a in (1) gives p(a) → q(a)(1), A4

(4)By modus ponens, q(a) is true, so a ∈ Q(2), (3), A1, D2

(5)a was an arbitrary element of P, so P ⊆ Q(4), D3

(6)Conversely, suppose P ⊆ Q.assumption

(7)For any a, if a ∈ P, then a ∈ Q.(6), D3

(8)That is, if p(a) is true, then q(a) is true.(7), D2

(9)Hence for every x, p(x) → q(x)(8)

(10)Both directions hold, so the two are equivalent.(5), (9)

∎

Corollary C

Conditions p, q are necessary and sufficient for each other if and only if P = Q.

Proof.

(1)Being necessary and sufficient means p ⟹ q and q ⟹ p hold together.D1

(2)p ⟹ q is equivalent to P ⊆ Q.T3

(3)q ⟹ p is equivalent to Q ⊆ P.T3

(4)Hence being necessary and sufficient is equivalent to P ⊆ Q and Q ⊆ P.(1), (2), (3)

(5)P ⊆ Q and Q ⊆ P is equivalent to P = Q.A5

(6)Hence being necessary and sufficient is equivalent to P = Q.(4), (5)

∎

Remark

Can A2 be removed from this proof?

Look at the two names separately. One reads the arrow from the front, the other from the back.