Set Theory & Fundamentals
Definition of sets, well-defined collections, roster vs set-builder notation, membership operations, and elementary set types.
Why this topic exists
Sets are the foundational building block of discrete mathematics and computer science. Core concepts in databases (relational algebra), query optimization, search algorithms, formal languages, and programming data structures (hash sets, dictionaries) borrow directly from set theory. Before defining relations, functions, or formal logic, a precise framework is required to define "a collection of objects." That framework is set theory.
What is a Set?
[!definition] Formal Set Definition A set is a well-defined collection of distinct objects, considered as an entity in itself.
Two fundamental principles govern every set:
- Well-defined: There must be an objective criteria determining whether any given object belongs to the set.
- Invalid: "The set of good programmers" (vague/subjective).
- Valid: "The set of students with a GPA above 3.5" (objective).
- Distinct: Elements within a set are unique. Duplicate elements are ignored.
Examples:
- $A = {1, 2, 3, 4}$
- $V = {a, e, i, o, u}$ (Set of English vowels)
- $F = {\text{Apple, Mango, Banana}}$
In computational terms: A set represents a collection of unique data points with zero duplicate entries and explicit membership rules.
Set Representation
The standard method to represent a set is the Roster (or Listing) Method, where every element is listed explicitly inside curly braces ${ }$, separated by commas.
Examples:
- $A = {2, 4, 6, 8}$
- $N = {1, 2, 3, 4, 5}$ (First five natural numbers)
[!invalid] Syntax Trap: Brackets vs Parentheses Curly braces ${ }$ strictly denote a set. Square brackets $[ ]$ and parentheses $( )$ denote sequences, vectors, ranges, or ordered tuples in discrete mathematics and computer science.
(Note: Sets can also be expressed using Set-Builder Notation, which describes elements via a condition rather than an explicit list, e.g., $S = {x \mid x \in \mathbb{N} \text{ and } x < 6}$).
Element / Membership
An object contained within a set is called an element or member of that set.
- The symbol $\in$ denotes membership ("is an element of").
- The symbol $\notin$ denotes non-membership ("is not an element of").
Example: Given $A = {10, 20, 30}$:
- $20 \in A$ (True: $20$ belongs to $A$)
- $50 \notin A$ (True: $50$ does not belong to $A$)
Basic Types of Sets
1. Empty Set (Null Set)
A set containing no elements. Denoted by ${}$ or $\emptyset$.
- Example: $A = {x \mid x \text{ is an even prime number greater than } 2} = \emptyset$
2. Singleton Set
A set containing exactly one element.
- Example: $A = {5}$
3. Finite Set
A set whose cardinality (count of elements) is a fixed natural number. The process of counting its elements terminates.
- Example: $A = {1, 2, 3, 4}$ ($|A| = 4$)
4. Infinite Set
A set whose elements cannot be completely listed or counted, as the collection continues indefinitely.
- Example: $\mathbb{N} = {1, 2, 3, 4, 5, \dots}$ (Set of all natural numbers)