Home / Courses / Intro to Proofs / Unit 5

Intro to Proofs Unit 5: Sets and Set Proofs

Sets are the basic objects of modern mathematics. This unit covers the set operations and the element-chasing technique used to prove that one set is contained in, or equal to, another.

Covers: Set notation and set-builder form, Subsets and set equality, Union, intersection, difference and complement, Power sets and Cartesian products, Element-chasing proofs, Double-inclusion proofs and De Morgan's laws, Indexed families of sets

Study guide

A set is a collection of distinct objects, its elements, and x ∈ A means x is an element of A. Sets are written by listing, {1, 2, 3}, or in set-builder form, {x ∈ ℤ : x² < 10}. Order and repetition do not matter, so {1, 2} = {2, 1, 1}. The empty set ∅ has no elements, and {∅} is a different set with one element. A ⊆ B means every element of A is in B; it is a quantified conditional, ∀x (x ∈ A → x ∈ B). Since ∅ has no elements, ∅ ⊆ A holds vacuously for every set A, including ∅ itself.

The basic operations correspond to logical connectives. The union A ∪ B = {x : x ∈ A or x ∈ B}; the intersection A ∩ B = {x : x ∈ A and x ∈ B}; the difference A − B = {x : x ∈ A and x ∉ B}; and the complement Aᶜ = U − A relative to a universal set U. Because of this correspondence, De Morgan's laws carry over: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ and (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ. For finite sets, inclusion-exclusion gives |A ∪ B| = |A| + |B| − |A ∩ B|. The symmetric difference A Δ B contains elements in exactly one of the two sets.

The power set P(A) is the set of all subsets of A; if |A| = n then |P(A)| = 2ⁿ. The Cartesian product A × B is the set of ordered pairs (a, b) with a ∈ A and b ∈ B, and |A × B| = |A| · |B|. Keep ∈ and ⊆ separate: {1} ∈ P({1, 2}) because {1} is a subset of {1, 2}, while 1 ∈ {1, 2} but 1 ∉ P({1, 2}). Indexed families such as Aₙ = [0, 1/n] for n ≥ 1 have unions and intersections defined by 'for some n' and 'for every n'; here the intersection is {0}.

To prove S ⊆ T, use element chasing: 'Let x ∈ S. ... Therefore x ∈ T.' Translate each set membership into its logical meaning and reason with the connectives; an 'or' in the hypothesis usually calls for cases. To prove S = T, prove S ⊆ T and T ⊆ S (double inclusion), or chain known identities. To disprove a set identity, give a specific small counterexample, often with sets of one or two elements. Never 'prove' an identity with a Venn diagram or a single example; a diagram can suggest a proof but is not one.

Key ideas

• A ⊆ B means every element of A is in B; A ∈ B means A itself is an element of B.
• Union, intersection and complement mirror ∨, ∧ and ¬.
• To prove S ⊆ T, take an arbitrary x ∈ S and show x ∈ T.
• To prove S = T, prove both inclusions.
• An 'or' in a membership condition leads to a proof by cases.
• A single small counterexample disproves a set identity.
• |P(A)| = 2ⁿ and |A × B| = |A| · |B| for finite sets.

Formulas and rules

Common mistakes

• Confusing ∈ with ⊆, for example writing 2 ∈ {{2}}.
• Treating ∅ and {∅} as the same set.
• Proving a set identity with a Venn diagram or one example.
• Forgetting the second inclusion in a set-equality proof.
• Writing |A ∪ B| = |A| + |B| without subtracting the overlap.

Before the test, make sure you can

• Read and write sets in roster and set-builder notation.
• Compute unions, intersections, differences, complements and symmetric differences.
• List power sets and Cartesian products and count their elements.
• Distinguish ∈ from ⊆ in sets whose elements are themselves sets.
• Write element-chasing proofs of subset statements.
• Prove set identities by double inclusion, using cases for 'or'.
• Disprove false identities with small counterexamples.
• Compute unions and intersections of simple indexed families.

Words to know

Set

A collection of distinct objects called elements.

Element (∈)

x ∈ A means x is one of the objects in A.

Subset (⊆)

A ⊆ B means every element of A is an element of B.

Proper subset

A ⊊ B means A ⊆ B and A ≠ B.

Empty set

The set ∅ with no elements; a subset of every set.

Union

A ∪ B: elements in A or B (or both).

Intersection

A ∩ B: elements in both A and B.

Set difference

A − B: elements in A but not in B.

Complement

Aᶜ = U − A: elements of the universal set not in A.

Disjoint sets

Sets with no elements in common, so A ∩ B = ∅.

Power set

P(A): the set of all subsets of A.

Cartesian product

A × B: the set of ordered pairs (a, b) with a ∈ A, b ∈ B.

Symmetric difference

A Δ B = (A − B) ∪ (B − A).

Double inclusion

Proving S = T by proving S ⊆ T and T ⊆ S.

Element chasing

Proving S ⊆ T by following an arbitrary element of S into T.

Indexed family

A collection of sets Aᵢ labeled by an index set, with unions and intersections over all i.

Sample practice questions

30 more questions like these, from level 1 to 5, are in the practice set.