Home / Courses / Discrete Mathematics / Unit 3

Discrete Mathematics Unit 3: Sets, functions & relations

Sets, functions and relations are the basic objects of discrete math. They describe collections and how elements connect.

Covers: Set operations, functions (injective/surjective), equivalence relations, partial orders

Study guide

A set is an unordered collection of distinct elements. Set operations: the union A ∪ B (in either), the intersection A ∩ B (in both), the difference A − B (in A but not B), and the complement Aᶜ (not in A, relative to a universal set). Venn diagrams visualize them. A is a subset of B if every element of A is in B. The power set of A is the set of all its subsets; an n-element set has 2ⁿ subsets. The Cartesian product A × B is the set of ordered pairs (a, b), and the size of a union is |A ∪ B| = |A| + |B| − |A ∩ B|.

A function f: A → B assigns each element of A exactly one element of B. It's injective (one-to-one) if different inputs give different outputs, surjective (onto) if every element of B is an output, and bijective if both. Bijections have inverses and show that two sets have the same size. Composition and inverses work as in algebra.

A relation on a set is a set of ordered pairs. Its possible properties are reflexive (every element relates to itself), symmetric (a R b implies b R a), antisymmetric (a R b and b R a imply a = b) and transitive (a R b and b R c imply a R c). An equivalence relation is reflexive, symmetric and transitive, and it splits the set into disjoint equivalence classes, like congruence mod n. A partial order is reflexive, antisymmetric and transitive, like ≤ or divisibility, and can be drawn as a Hasse diagram.

To prove X ⊆ Y, take an arbitrary element of X and show it is in Y. To prove X = Y, prove both inclusions. For a function f, the image f(A) is {f(a) : a ∈ A}. Then f(A ∩ B) ⊆ f(A) ∩ f(B) always holds, with equality when f is injective. If g∘f is surjective, then g must be surjective, but f need not be. If g∘f is injective, then f must be injective, but g need not be. Compositions of injections are injective, and compositions of surjections are surjective.

If |A| = |B| is finite, a function f: A → B is injective exactly when it is surjective, so either property makes it a bijection. There are n! bijections between two n-element sets and none if the sizes differ. The reflexive closure of R adds every pair (a, a). The symmetric closure adds (b, a) for each (a, b) in R. The transitive closure keeps adding (a, c) whenever (a, b) and (b, c) are present, until no new pairs appear.

In a poset, an element is minimal if nothing is strictly below it and maximal if nothing is strictly above it. It is least if it is below every element and greatest if it is above every element. On a Hasse diagram, minimal elements have no lines going down from them, and a poset can have several minimal elements but at most one least element.

Key ideas

• Set operations: union, intersection, difference, complement.
• A set with n elements has 2ⁿ subsets.
• A function is injective (one-to-one), surjective (onto), or bijective (both).
• Equivalence relations are reflexive, symmetric and transitive; they split a set into classes.
• Partial orders are reflexive, antisymmetric and transitive.

Formulas and rules

Common mistakes

• Confusing ∈ (element of) with ⊆ (subset of).
• Mixing up symmetric and antisymmetric.

Words to know

Power set

The set of all subsets; an n-element set has 2ⁿ of them.

Injective function

Different inputs always give different outputs.

Surjective function

Every element of the codomain is an output.

Equivalence relation

A relation that is reflexive, symmetric and transitive.

|A ∪ B|

|A| + |B| − |A ∩ B|

Union (A ∪ B)

Elements in A or B.

Intersection (A ∩ B)

Elements in both A and B.

Set difference (A − B)

Elements in A but not B.

Subset

A ⊆ B if every element of A is in B.

Cartesian product (A × B)

All ordered pairs (a, b).

Bijection

A function that is both injective and surjective.

Equivalence class

All elements related to a given element.

Partial order

A relation that is reflexive, antisymmetric and transitive.

Hasse diagram

A drawing of a partial order.

Sample practice questions

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