On this page & study actions
Assessed progress
Sign in and complete the verified MCQs to track mastery.
Unit 2: Set theory5 min read
Set theory serves as the fundamental language of modern mathematics and computer science. It provides the essential framework for defining mathematical structures, establishing relations, and constructing functions.
A set is an unordered collection of distinct objects, referred to as elements or members. When an element belongs to a set , we write ; otherwise, we write .
Set operations allow us to combine and manipulate sets to form new ones.
Set operations mirror logical operators, which leads to identical structural laws:
| Law | Union Identity | Intersection Identity | | :--- | :--- | :--- | | Identity Laws | | | | Domination Laws | | | | | | | | | | | | | | | | | | |
Let us prove the identity using basic set identities:
B - (B - A) &= B \cap \overline{(B \cap \overline{A})} && \text{(Definition of Difference)} \\ &= B \cap (\overline{B} \cup \overline{\overline{A}}) && \text{(De Morgan's Law)} \\ &= B \cap (\overline{B} \cup A) && \text{(Complementation Law)} \\ &= (B \cap \overline{B}) \cup (B \cap A) && \text{(Distributive Law)} \\ &= \emptyset \cup (B \cap A) && \text{(Complement Law)} \\ &= B \cap A && \text{(Identity Law)} \\ &= A \cap B && \text{(Commutative Law)} \end{aligned}$$ Alternatively, this can be proven using a **membership table** (where $1$ indicates membership and $0$ indicates non-membership): | $A$ | $B$ | $A \cap B$ | $B - A$ | $B - (B - A)$ | | :---: | :---: | :---: | :---: | :---: | | 1 | 1 | **1** | 0 | **1** | | 1 | 0 | **0** | 0 | **0** | | 0 | 1 | **0** | 1 | **0** | | 0 | 0 | **0** | 0 | **0** | Since the columns for $A \cap B$ and $B - (B - A)$ are identical, the sets are equal. --- ## 3. Cartesian Products and Relations An **ordered pair** $\langle a, b \rangle$ (or $(a, b)$) represents a ordered sequence of two objects, where order matters: $\langle a, b \rangle = \langle c, d \rangle$ if and only if $a = c$ and $b = d$. This can be generalized to an **ordered $n$-tuple**. ### Cartesian Product The Cartesian product of sets $A$ and $B$, denoted $A \times B$, is the set of all ordered pairs where the first element is from $A$ and the second is from $B$: $$A \times B = \{\langle a, b \rangle \mid a \in A \land b \in B\}$$ ### Binary Relations A **binary relation** $R$ from set $A$ to set $B$ is a subset of their Cartesian product: $$R \subseteq A \times B$$ If $\langle a, b \rangle \in R$, we say $a$ is related to $b$, often denoted as $aRb$. Unlike functions, a single element $a \in A$ can relate to multiple elements (or no elements) in $B$. --- ## 4. Theory of Functions A **function** $f$ from set $X$ to set $Y$ (denoted $f: X \rightarrow Y$) is a specific type of relation that assigns **exactly one** element $f(x) \in Y$ to each element $x \in X$. ```text Domain (X) Codomain (Y) +------------+ +------------+ | x1 *-----+------------+---> * y1 | | | f | | | x2 *-----+------------+---> * y2 | <- Range (R) | | | | | x3 *-----+------------+---> * y3 | +------------+ | | | * y4 | +------------+ ``` ### Terminology * **Domain:** The source set $X$. * **Codomain:** The target set $Y$. * **Image:** For $f(x) = y$, $y$ is the image of $x$ under $f$. * **Pre-image:** $x$ is the pre-image of $y$. An element in the codomain can have zero, one, or multiple pre-images. * **Range ($R_f$):** The subset of $Y$ consisting of all actual images: $$R_f = \{y \in Y \mid \exists x \in X \, (f(x) = y)\}$$ ### Special Mathematical Functions * **Peano's Successor Function:** Let $P$ be the set of positive integers. The successor function $\sigma: P \rightarrow P$ is defined as: $$\sigma(n) = n + 1$$ * **Floor Function ($\lfloor x \rfloor$):** Assigns the largest integer less than or equal to the real number $x$. * **Ceiling Function ($\lceil x \rceil$):** Assigns the smallest integer greater than or equal to the real number $x$. For any non-integer real number $x \notin \mathbb{Z}$: $$\lfloor -x \rfloor \neq -\lfloor x \rfloor \quad \text{and} \quad \lceil -x \rceil \neq -\lceil x \rceil$$ ### Injection, Surjection, and Bijection * **One-to-One (Injective):** A function $f$ is injective if distinct domain elements map to distinct codomain elements. $$\forall x, y \in X \, (f(x) = f(y) \rightarrow x = y)$$ * **Onto (Surjective):** A function $f$ is surjective if its range equals its codomain. $$\forall y \in Y, \exists x \in X \, (f(x) = y)$$ * **One-to-One Correspondence (Bijective):** A function that is both injective and surjective. Only bijective functions are **invertible**, meaning there exists a unique inverse function $f^{-1}: Y \rightarrow X$ such that: $$f^{-1}(y) = x \iff f(x) = y$$ --- ## 5. Equivalence Relations, Congruence, and Partitions A relation $R$ on a single set $A$ (meaning $R \subseteq A \times A$) can possess properties that characterize its structure. ### Key Properties of Relations * **Reflexivity:** Every element is related to itself. $$\forall a \in A, \, \langle a, a \rangle \in R$$ * **Symmetry:** If $a$ is related to $b$, then $b$ is related to $a$. $$\forall a, b \in A, \, \langle a, b \rangle \in R \rightarrow \langle b, a \rangle \in R$$ * **Transitivity:** If $a$ is related to $b$, and $b$ is related to $c$, then $a$ is related to $c$. $$\forall a, b, c \in A, \, (\langle a, b \rangle \in R \land \langle b, c \rangle \in R) \rightarrow \langle a, c \rangle \in R$$ ### Equivalence Relations An **equivalence relation** is a relation that is reflexive, symmetric, and transitive. #### Classical Example: Congruence Modulo $n$ For a positive integer $n \geq 2$, we define $a \equiv b \pmod n$ if and only if $a - b$ is divisible by $n$. 1. **Reflexivity:** $a - a = 0 = 0 \cdot n$. Thus, $a \equiv a \pmod n$. 2. **Symmetry:** If $a \equiv b \pmod n$, then $a - b = k \cdot n$. Thus, $b - a = (-k) \cdot n$, which means $b \equiv a \pmod n$. 3. **Transitivity:** If $a \equiv b \pmod n$ and $b \equiv c \pmod n$, then $a - b = k \cdot n$ and $b - c = m \cdot n$. Adding these equations yields: $$(a - b) + (b - c) = a - c = (k + m) \cdot n$$ Thus, $a \equiv c \pmod n$. ### Equivalence Classes and Partitions * **Equivalence Class ($[a]_R$):** The set of all elements related to $a$ under $R$. $$[a]_R = \{x \in A \mid \langle a, x \rangle \in R\}$$ * **Quotient Set ($A/R$):** The set of all equivalence classes under $R$: $$A/R = \{[a]_R \mid a \in A\}$$ * **Partition:** A collection of non-empty, pairwise disjoint subsets of $A$ whose union is $A$. The quotient set $A/R$ always forms a partition of $A$. --- ## 6. Partially Ordered Sets (Posets) and Hasse Diagrams A relation $R$ on a set $S$ is a **partial ordering** if it is reflexive, **antisymmetric**, and transitive. * **Antisymmetry:** If $aRb$ and $bRa$, then $a = b$. $$\forall a, b \in S \, ((\langle a, b \rangle \in R \land \langle b, a \rangle \in R) \rightarrow a = b)$$ A set $S$ combined with a partial ordering $\le$ is called a **partially ordered set**, or **poset**, and is denoted as $\langle S, \le \rangle$. ### Comparability and Chains * **Comparable:** Two elements $a, b \in S$ are comparable if $a \le b$ or $b \le a$. * **Total Order (Chain):** A poset in which every pair of elements is comparable. ### Hasse Diagrams A **Hasse diagram** is a visual representation of a finite poset. It is constructed by drawing a vertex for each element and an upward edge from $x$ to $y$ if $y$ **covers** $x$. We say $y$ covers $x$ if $x < y$ and there is no element $z$ such that $x < z < y$. ```text Hasse Diagram for the Power Set P({a, b, c}) under the subset relation: {a, b, c} / | \ {a, b} {a, c} {b, c} / \ / \ / \ {a} {b} {c} \ | / { } ``` ### Extremal Elements in Posets Let $\langle P, \le \rangle$ be a poset and $A \subseteq P$: * **Maximal Element:** An element $m \in P$ such that no $x \in P$ exists with $m < x$. * **Minimal Element:** An element $m \in P$ such that no $x \in P$ exists with $x < m$. * **Greatest Element (Maximum):** A unique element $g \in P$ such that $x \le g$ for all $x \in P$. * **Least Element (Minimum):** A unique element $l \in P$ such that $l \le x$ for all $x \in P$. * **Upper Bound of $A$:** An element $u \in P$ such that $a \le u$ for all $a \in A$. * **Lower Bound of $A$:** An element $l \in P$ such that $l \le a$ for all $a \in A$. * **Least Upper Bound (LUB / Supremum):** An upper bound of $A$ that is less than or equal to every other upper bound of $A$. * **Greatest Lower Bound (GLB / Infimum):** A lower bound of $A$ that is greater than or equal to every other lower bound of $A$. --- ## 7. Computer Representation of Sets When working with a finite universal set $U$, we can represent any subset $A \subseteq U$ in computer memory using a **bit vector** (bit array). ### Bit Vector Mapping Let $U = \{a, b, c, d, e, f, \dots, z\}$ with $|U| = 26$. We can establish a direct mapping between each element of the alphabet and a bit index (from $0$ to $25$): * The set of vowels $V = \{a, e, i, o, u\}$ corresponds to $1$s at indices $0, 4, 8, 14, 20$: $$\text{Bit Vector}(V) = \texttt{10001000100000100000100000}$$ * The set of consonants $C$ corresponds to the logical negation of $V$: $$\text{Bit Vector}(C) = \texttt{01110111011111011111011111}$$ ### Logical Bitwise Operations Set operations translate directly to fast hardware-level bitwise operations: * **Union ($V \cup C$)** is computed using bitwise **OR** ($\lor$): ```text 10001000100000100000100000 (Vowels) OR 01110111011111011111011111 (Consonants) ----------------------------- 11111111111111111111111111 (Universal Set U) ``` * **Intersection ($V \cap C$)** is computed using bitwise **AND** ($\land$): ```text 10001000100000100000100000 (Vowels) AND 01110111011111011111011111 (Consonants) ----------------------------- 00000000000000000000000000 (Empty Set Ø) ``` --- ## Summary * **Sets** are collections of distinct elements where order is irrelevant. Their size is represented by cardinality $|S|$, and the set of all their subsets is the power set $P(S)$ of size $2^{|S|}$. * **Set operations** such as union, intersection, difference, and complementation mirror logical operators ($\lor, \land, \neg$), and follow identical laws (like De Morgan's). * **Functions** map each element of a domain to exactly one element of a codomain. They can be classified as injective (one-to-one), surjective (onto), or bijective (both), with only bijections being invertible. * **Equivalence relations** partition a set into disjoint equivalence classes by satisfying reflexivity, symmetry, and transitivity. * **Posets** are structured around a reflexive, antisymmetric, and transitive relation. They can be visualized using Hasse diagrams, which show the covering relations between elements.The set of all subsets of a given set S, denoted P(S), with a cardinality of 2^|S|.
A function that is simultaneously injective (one-to-one) and surjective (onto), ensuring it has a well-defined inverse.
A binary relation that is reflexive, symmetric, and transitive, which effectively partitions a set into disjoint equivalence classes.
A partially ordered set defined by a relation that is reflexive, antisymmetric, and transitive.
A simplified visual representation of a poset where transitivity and reflexivity are implicitly understood, reducing visual clutter.
Test your understanding with 5 questions
If the cardinality of a set A is 4 (i.e., |A| = 4), what is the cardinality of its power set's power set, |P(P(A))|?
Let f: R -> R be a function defined by f(x) = floor(x/3). What is the value of f(-1.4)?
Which of the following relations on the set of integers Z is an equivalence relation?
In a poset, the greatest lower bound (GLB) of a subset is also uniquely called what?
Let A = {1, 2, 3} and B = {3, 4, 5}. What is the symmetric difference of A and B?
6 Modules
6 Modules