Unit 1: Set theory and relations

A set is a well-defined collection of distinct objects. "Well-defined" means that for any object we can say clearly whether it belongs to the set or not. "The vowels of English" is a set; "the good students of a class" is not, because "good" is a matter of opinion. The objects in a set are called its elements or members. We write sets with capital letters (A, B, C) and elements with small letters. If a is an element of A, we write a ∈ A; if not, a ∉ A.

• Order does not matter: {1, 2, 3} and {3, 1, 2} are the same set.
• Repetition does not matter: {1, 1, 2} is the same as {1, 2}.
• The number of elements in a finite set A is its cardinality, written n(A).

There are two standard ways to write a set.

Roster form is best for small sets. Set-builder form is best for large or infinite sets, where listing is impossible.

• Null (empty) set: contains no element, written φ or { }. Example: {x : x is a natural number less than 1}.
• Singleton set: has exactly one element, such as {0}. Note that {0} is not empty — it contains 0.
• Finite and infinite sets: a finite set can be counted to an end ({1, 2, 3}); an infinite set cannot (the set of all natural numbers).
• Equal sets: A = B when they have exactly the same elements, e.g. {1, 2, 3} = {3, 2, 1}.
• Equivalent sets: have the same number of elements, n(A) = n(B), even if the elements differ: {a, b, c} and {1, 2, 3}.
• Disjoint sets: have no element in common, so A ∩ B = φ.
• Universal set (U): the set containing all elements under discussion in a problem.

Take U = {1, 2, 3, 4, 5, 6, 7, 8}, A = {1, 2, 3, 4} and B = {3, 4, 5, 6}.

Useful laws to remember:

• Commutative: A ∪ B = B ∪ A and A ∩ B = B ∩ A
• De Morgan's laws: (A ∪ B)' = A' ∩ B' and (A ∩ B)' = A' ∪ B'
• Counting formula: n(A ∪ B) = n(A) + n(B) − n(A ∩ B)

• Principle of duality: any law remains true if ∪ and ∩ are interchanged and U and ∅ are interchanged.

• A partition of A is a collection of non-empty, pairwise disjoint subsets whose union is A.
• Example: {1, 2, 3, 4, 5, 6} partitioned into {1, 3, 5} and {2, 4, 6}. Every equivalence relation creates a partition into equivalence classes.

• Cartesian product: A × B = {(a, b) : a ∈ A, b ∈ B}. A relation from A to B is a subset of A × B.

• Domain: set of first elements; range: set of second elements.
• Inverse: R⁻¹ = {(b, a) : (a, b) ∈ R}.
• Composite: if R ⊆ A × B and S ⊆ B × C, then S ∘ R = {(a, c) : (a, b) ∈ R and (b, c) ∈ S for some b}.

• Digraph: each element is a vertex; draw an arrow a → b for each (a, b) in R; a loop for (a, a).
• Relation matrix: M[i][j] = 1 if (ai, bj) ∈ R, else 0.
• Reading properties from the matrix: reflexive — all diagonal entries 1; symmetric — matrix equals its transpose; composition — Boolean product of matrices.