Sets and mathematical logic

Sets and logic are the "grammar" of mathematics. The language of sets is used to write the solutions of equations and inequalities, the domain and range of functions, and events in probability. Logic teaches you to understand words such as "necessary", "sufficient", "at least one", "every" and "there exists" precisely and to draw correct conclusions. The topic also underpins counting problems and methods of proof.

§1. Sets and notation

A set is a collection of objects grouped by some property; the objects are its elements. A set is described in two ways: by listing its elements (A = {1, 2, 3}) or by a defining property (B = {x | x² < 9}).

• a ∈ A — a belongs to A; a ∉ A — it does not.
• ∅ — the empty set (it has no elements).
• A ⊂ B — every element of A is also in B (A is a subset of B).
• A = B — both A ⊂ B and B ⊂ A.

Order and repetition do not matter in a set: {1, 2, 2, 3} = {3, 1, 2}.
The main number sets: N — natural, Z — integers, Q — rational, R — real numbers; N ⊂ Z ⊂ Q ⊂ R. Intervals are sets too: [2; 5) = {x | 2 ≤ x < 5}.

Why 2ⁿ? Each element has two options: it is in the subset or it is not. n independent choices give 2 · 2 · … · 2 = 2ⁿ possibilities.

§2. Operations on sets

If the intersection is empty (A ∩ B = ∅), the sets are called disjoint. The operations behave like those on numbers: A ∪ B = B ∪ A, A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
De Morgan’s laws: (A ∪ B)‾ = Ā ∩ B̄, (A ∩ B)‾ = Ā ∪ B̄ — "the complement of a union is the intersection of the complements".
Operations on intervals are done on the number line: [1; 5) ∩ (3; 7] = (3; 5), [1; 5) ∪ (3; 7] = [1; 7]. These are exactly the operations used to write the answer to a system of inequalities (intersection) and to a collection (union).

Worked example

A = {1, 2, 3, 4}, B = {3, 4, 5}. Find the union, the intersection and the difference.

1. A ∪ B = {1, 2, 3, 4, 5} — all elements of both sets, without repeats.
2. A ∩ B = {3, 4} — the common elements.
3. A \ B = {1, 2}, B \ A = {5}.

§3. Venn diagrams and counting elements

In a Venn diagram the sets are drawn as circles and the universal set as a rectangle. Counting problems use the inclusion–exclusion principle:

The intersection is subtracted because it was counted in both n(A) and n(B), i.e. twice. With three sets the common part is first added three times and subtracted three times, so it is added back once.
It is convenient to fill in a diagram from the centre outwards (from the region where most sets overlap).

Worked example

A class has 30 pupils: 18 learn English, 15 learn German and 5 learn neither. How many learn both?

1. At least one language: 30 − 5 = 25.
2. The formula: 25 = 18 + 15 − x.
3. x = 33 − 25 = 8.

Worked example

Of 120 students, 60 attend a maths club, 50 physics and 40 chemistry. 25 attend maths and physics, 20 maths and chemistry, 15 physics and chemistry, and 10 all three. How many attend no club?

1. n(M ∪ P ∪ C) = 60 + 50 + 40 − 25 − 20 − 15 + 10.
2. = 150 − 60 + 10 = 100.
3. No club: 120 − 100 = 20.

§4. Statements and logical operations

A statement (proposition) is a declarative sentence that is either true (T) or false (F). "7 is prime" is a true statement; "x > 2" is not a statement, because x is unknown (it is a predicate).

• Negation ¬A: reverses the truth value.
• Conjunction A ∧ B ("and") — true only if both are true.
• Disjunction A ∨ B ("or") — true if at least one is true.
• Equivalence A ⇔ B — true if both have the same value.

Think of an implication as a promise: "If it rains, I will take an umbrella". The promise is broken only if it rains and no umbrella is taken. If it does not rain, the promise is not broken whatever you do — that is why F ⇒ T and F ⇒ F are true.
De Morgan: ¬(A ∧ B) = ¬A ∨ ¬B, ¬(A ∨ B) = ¬A ∧ ¬B.
The statement equivalent to A ⇒ B is its contrapositive ¬B ⇒ ¬A. The converse B ⇒ A is not equivalent to it.

§5. Quantifiers, necessary and sufficient conditions

• ∀ — "for every", ∃ — "there exists".
• Negation swaps the quantifier: ¬(∀x: P(x)) = ∃x: ¬P(x), ¬(∃x: P(x)) = ∀x: ¬P(x).
• If A ⇒ B is true: A is a sufficient condition for B, and B is a necessary condition for A.
• If A ⇔ B, each is a necessary and sufficient condition for the other.

In terms of sets: A ⇒ B means the set satisfying A is a subset of the set satisfying B. The smaller set is the sufficient condition, the larger one the necessary condition.

Worked example

What kind of condition is "x > 3" for "x > 1"?

1. If x > 3 then certainly x > 1, so x > 3 ⇒ x > 1 is true and the condition is sufficient.
2. The converse fails: for x = 2 we have x > 1 but not x > 3, so it is not necessary.
3. Answer: sufficient but not necessary.

§6. Methods of proof

• Direct proof: start from the hypothesis and reach the conclusion through known facts.
• Contrapositive: prove ¬B ⇒ ¬A instead of A ⇒ B. For example, "if n² is even, then n is even" is easy in the form "if n is odd, then n² is odd": (2k + 1)² = 2(2k² + 2k) + 1.
• Contradiction: assume the conclusion is false and reach a contradiction. The classic example is the proof that √2 is irrational.
• Counterexample: to disprove a statement about "every" case, one example is enough: "all primes are odd" — counterexample 2.

Check yourself

1. A = {2, 4, 6, 8}, B = {4, 8, 12}. Find A ∩ B.

2. How many subsets does a 5-element set have?

3. Of 40 people, 25 drink tea, 20 drink coffee and 8 drink both. How many drink neither?

4. Write the negation of "some numbers are even".

5. What is the value of the implication F ⇒ T?

6. What kind of condition is "a is divisible by 4" for "a is even"?

7. Find [1; 5) ∩ (3; 7].

8. How many numbers from 1 to 100 are divisible by 2 or by 3?

Common mistakes

• Counting the intersection twice in a union.
• Thinking a false premise always gives a false conclusion (F ⇒ … is always true).
• Negating a quantified statement by negating only the predicate and not swapping the quantifier.
• Mixing up necessary and sufficient conditions.
• Assuming that A ⇒ B also makes the converse B ⇒ A true.
• Forgetting the empty set or the set itself when counting subsets.