Chapter 1: Sets
Introduction to Set Theory
Set theory is the mathematical foundation for dealing with collections of objects. A set is a well-defined collection of distinct objects, called elements or members. Set theory appears throughout mathematics and computer science—databases organize data as sets, algorithms operate on sets of inputs, and probability theory is built on set foundations.
1. Basic Set Concepts
Definition of a Set
A set is characterized by its elements. The notation {a, b, c} represents a set with elements a, b, and c. We write a ∈ S to mean "a is an element of set S" and a ∉ S to mean "a is not an element of S." Sets are unordered (so {1,2,3} = {3,2,1}) and elements are distinct (repetitions don't matter: {1,1,2} = {1,2}).
Describing Sets
We can describe sets explicitly by listing elements: {1, 2, 3, 4, 5}. Or implicitly using set-builder notation: {x | x is a positive integer less than 6}. The vertical bar means "such that." The second notation is useful when listing all elements is impractical (like {x | x is a real number between 0 and 1}).
Empty Set
The empty set (or null set), denoted ∅ or {}, contains no elements. It's a valid set and appears frequently in mathematics and logic.
2. Types of Sets
Finite and Infinite Sets
A finite set has a countable number of elements, like {1, 2, 3} or {all students in this class}. An infinite set has infinitely many elements, like the set of all positive integers or the set of all real numbers.
Universal Set
The universal set (denoted U) is the set of all objects under consideration in a particular context. In a problem about students, U might be all students in the university. In probability, U might be all possible outcomes of an experiment.
Subsets
Set A is a subset of set B (written A ⊆ B) if every element of A is also in B. For example, {1,2} ⊆ {1,2,3}. Note: A ⊆ A (every set is a subset of itself) and ∅ ⊆ A (the empty set is a subset of every set).
Proper Subsets
A is a proper subset of B (written A ⊂ B) if A ⊆ B and A ≠ B. So {1,2} ⊂ {1,2,3}, but {1,2,3} is not a proper subset of {1,2,3}.
Power Set
The power set of A, denoted P(A), is the set of all subsets of A. For A = {1,2}, the power set is P(A) = {∅, {1}, {2}, {1,2}}. If A has n elements, P(A) has 2^n elements.
3. Set Operations
Union
The union of sets A and B, denoted A ∪ B, is the set of all elements in A or B (or both). Example: {1,2,3} ∪ {3,4,5} = {1,2,3,4,5}. The union includes all elements without repetition.
Intersection
The intersection of A and B, denoted A ∩ B, is the set of elements in both A and B. Example: {1,2,3} ∩ {3,4,5} = {3}. If A ∩ B = ∅, the sets are disjoint (have no elements in common).
Complement
The complement of A (relative to universal set U), denoted A' or A^c, is the set of all elements in U that are not in A. If U = {1,2,3,4,5} and A = {1,3}, then A' = {2,4,5}.
Difference
The difference A - B is the set of elements in A but not in B. Example: {1,2,3} - {2,3,4} = {1}. Note: A - B is not the same as B - A.
4. Venn Diagrams
Visual Representation
Venn diagrams use rectangles and circles to visualize sets and their relationships. The rectangle represents the universal set U. Circles represent sets. Overlapping circles show elements in multiple sets. Regions outside circles show complements.
Using Venn Diagrams
Venn diagrams help visualize set operations. To show A ∪ B, shade all regions in A or B (or both). For A ∩ B, shade only the overlapping region. For A', shade everything outside A (within U). Diagrams make relationships between sets intuitive.
5. Properties of Set Operations
Commutative Properties
A ∪ B = B ∪ A and A ∩ B = B ∩ A. The order of sets doesn't matter for union or intersection.
Associative Properties
(A ∪ B) ∪ C = A ∪ (B ∪ C) and (A ∩ B) ∩ C = A ∩ (B ∩ C). Grouping doesn't matter.
Distributive Properties
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). These mirror algebraic distribution.
De Morgan's Laws
(A ∪ B)' = A' ∩ B' and (A ∩ B)' = A' ∪ B'. Complement distributes over union and intersection but flips the operation.
Idempotent Laws
A ∪ A = A and A ∩ A = A. Operating a set with itself gives the set unchanged.
6. Counting Elements in Sets
Cardinality
The cardinality of set A, denoted |A|, is the number of elements in A. For finite sets, this is straightforward: |{1,2,3}| = 3. For infinite sets, cardinality is more subtle (infinite cardinalities can differ in size—an advanced topic).
Inclusion-Exclusion Principle
To count elements in A ∪ B without double-counting: |A ∪ B| = |A| + |B| - |A ∩ B|. For three sets: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|. This principle accounts for overlaps correctly.
Practical Example
In a class of 100 students, 60 study math, 40 study physics, and 20 study both. How many study at least one subject? |Math ∪ Physics| = 60 + 40 - 20 = 80. How many study neither? 100 - 80 = 20.
7. Applications of Set Theory
In Computer Science
Databases use sets to organize data. Algorithms operate on sets (sorting sets of numbers, searching sets of records). Programming languages provide set data structures. Set theory is foundational to formal language theory and automata.
In Probability and Statistics
Sample spaces (all possible outcomes) are sets. Events are subsets of sample space. Probability calculations use set operations.
Conclusion
Set theory provides a language and framework for discussing collections of objects mathematically. Understanding sets, operations on sets, and their properties is essential for advanced mathematics and computer science. From simple finite sets to infinite sets, from concrete applications to abstract theory, set theory is a unifying mathematical framework.