Set Theory and Relations

Set Theory and Relations

Set theory is the mathematical study of collections of objects. It provides the foundation for nearly all of mathematics and is essential to computer science — in databases, type systems, formal languages, and algorithm design.

Sets and Notation

A set is an unordered collection of distinct elements. Notation: roster method {1, 2, 3} or set-builder {x | x > 0}. The empty set is ∅. Membership is denoted by ∈. Sets can be finite or infinite, countable or uncountable.

Set Operations

Union (A ∪ B): elements in A or B or both. Intersection (A ∩ B): elements in both. Difference (A − B): elements in A but not B. Complement (A'): elements not in A. Symmetric difference (A Δ B): elements in exactly one set. Power set P(A): set of all subsets of A (|P(A)| = 2^|A|).

Laws of Set Operations

Set operations obey commutative, associative, distributive, identity, complement, idempotent, absorption, and De Morgan's laws. De Morgan's laws: (A ∪ B)' = A' ∩ B' and (A ∩ B)' = A' ∪ B'. These parallel logic laws.

Cartesian Product

The Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B. |A × B| = |A| · |B|. The Cartesian product underlies the definition of relations and functions.

Relations

A relation R from A to B is a subset of A × B. A relation on A is a subset of A × A. Relations can be represented as sets of ordered pairs, matrices, or directed graphs. Key properties include reflexive, symmetric, antisymmetric, and transitive.

Equivalence Relations

A relation that is reflexive, symmetric, and transitive is an equivalence relation. It partitions the set into disjoint equivalence classes. Example: congruence modulo n. The quotient set A/R is the set of all equivalence classes.

Partial Orders

A relation that is reflexive, antisymmetric, and transitive is a partial order. A set with a partial order is a poset. Hasse diagrams visualise posets. Concepts include greatest/least elements, upper/lower bounds, lattices, and total (linear) orders.

Summary

Set theory and relations provide the mathematical language for expressing relationships between objects. These concepts underpin databases (relational algebra), programming (type systems), and formal methods in computer science.