Sets and Logic
What the exam tests
Sets and Logic tests precise language: set operations, De Morgan's laws, quantifiers, converse and contrapositive, and direct or contradiction proofs. Kyoto entrance questions use short statements about integers or real numbers and ask whether a condition is necessary, sufficient, or both.
Core rules
- A ∪ B consists of elements in A or B; A ∩ B consists of elements in both. Complements are taken relative to a stated universal set.
- De Morgan: (A ∪ B)^c = A^c ∩ B^c and (A ∩ B)^c = A^c ∪ B^c.
- The contrapositive of P ⇒ Q is ¬Q ⇒ ¬P; they are logically equivalent. The converse Q ⇒ P is not equivalent.
- The negation of 'for all x, P(x)' is 'there exists x such that ¬P(x)'; the negation of 'there exists x such that P(x)' is 'for all x, ¬P(x)'.
- 'P is sufficient for Q' means P ⇒ Q; 'P is necessary for Q' means Q ⇒ P.
Worked example
Prove that if n^2 is even for an integer n, then n is even. Use the contrapositive: assume n is odd, so n = 2k + 1 for some integer k. Then n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1, which is odd. Thus 'n odd implies n^2 odd.' By contraposition, 'n^2 even implies n even.'
Traps
Do not prove the converse when the contrapositive is needed. Treat 'or' as inclusive unless the problem says exclusive. Remember that the empty set is a subset of every set, and check whether a universal set is specified before taking complements.