Chapter 12. Sets, Logic and Proof

Sets. A set is a collection of distinct objects. Operations: union (A ∪ B), intersection (A ∩ B), complement (Aᶜ) and difference (A  B). The empty set ∅ has no elements [16].

Logic. A statement is true or false. Connectives: and (∧), or (∨), not (¬), implies (→). The statement “if P then Q” is false only when P is true and Q is false. Its contrapositive (if not Q then not P) is logically equivalent to it; its converse is not [16].

Quantifiers. “For all” (∀) and “there exists” (∃). To negate “all A are B,” say “some A is not B.”

Methods of proof

Direct proof: assume the hypothesis and deduce the conclusion.

Contrapositive: prove “if not Q then not P.”

Contradiction: assume the statement false and derive an impossibility. Example: the classical proof that √2 is irrational [8][16].

Induction: prove a base case, then show that truth for n implies truth for n + 1.

Review: What is the contrapositive of “If a number is divisible by 6, then it is even”? (Answer: “If a number is not even, then it is not divisible by 6.”)