Trace it. Derive it. Know it.
Every cluster below maps one schematic path — from first principles to the final equation. Expand a node to follow the full derivation trace.
Types of Relations: Reflexive, Symmetric, Transitive & Equivalence Relations
3 concepts · 1.1What formal criteria classify a relation on a set as reflexive, symmetric, or transitive, and how do their combinations yield equivalence relations and combinatorial counting formulas?
A relation R on a set A is a subset of the Cartesian product A x A. The empty set (null relation) and A x A (universal relation) represent the extreme trivial relations. Non-trivial relations are classified by three fundamental structural axioms: Reflexivity mandates that every element is related to itself ((a, a) in R for all a in A), meaning the diagonal identity relation I_A is a subset of R; Symmetry dictates that for every ordered pair in R, its transposed reverse pair must also belong to R ((a, b) in R implies (b, a) in R for all a, b in A), equivalently R = R^(-1); and Transitivity requires that an intermediate link guarantees a direct link ((a, b) in R and (b, c) in R implies (a, c) in R for all a, b, c in A). A relation satisfying all three conditions simultaneously is termed an Equivalence Relation. For a finite set of cardinality n, there are 2^(n^2) total relations, 2^(n(n-1)) reflexive relations, 2^(n(n+1)/2) symmetric relations, and 2^(n(n-1)/2) relations that are simultaneously reflexive and symmetric.
Empty, Universal, and Identity Relations on a Set
A relation R on set A is a subset of A x A. The empty relation R = Phi and universal relation R = A x A are the trivial extreme relations. The identity relation I_A = {(a, a) : a in A} contains ONLY diagonal pairs.
Reflexive, Symmetric, and Transitive Relations: Definitions and Counterexamples
R on A is: (1) Reflexive if (a, a) in R for all a in A; (2) Symmetric if (a, b) in R implies (b, a) in R; (3) Transitive if (a, b) in R and (b, c) in R implies (a, c) in R.
Equivalence Relations and Integer Difference Proofs
A relation R on A is an Equivalence Relation if and only if it is simultaneously Reflexive, Symmetric, and Transitive.
Equivalence Classes, Set Partitions & Congruence Modulo m
3 concepts · 1.2How does an equivalence relation decompose a set into mutually disjoint equivalence classes, and why does congruence modulo m provide the archetype for modular arithmetic and quotient sets?
Let R be an equivalence relation on a non-empty set A. For any element a in A, the Equivalence Class of a, denoted by [a] or cl(a), is the set of all elements in A that are related to a: [a] = { x in A : (x, a) in R }. By the Fundamental Theorem of Equivalence Relations, the collection of all equivalence classes forms a Partition of A, satisfying three ironclad criteria: (1) Every class is non-empty ([a] != empty since a in [a]), (2) Any two equivalence classes are either strictly identical or completely disjoint (either [a] = [b] or [a] cap [b] = empty), and (3) The union of all equivalence classes reconstructs the original set A (cup [a] = A). The most celebrated arithmetic equivalence relation is Congruence Modulo m on the set of integers Z: a = b (mod m) if and only if m divides (a - b). For any positive integer m, this relation partitions Z into exactly m pairwise disjoint equivalence classes [0], [1], ..., [m - 1], forming the quotient set Z_m = Z/mZ. Geometrically, equivalence classes correspond to parallel line families (same slope), concentric circles (equal distance from origin), or congruence classes of polygons.
Equivalence Class Definition: [a] = {x in A : (x, a) in R}
Given an equivalence relation R on A, the equivalence class of an element a in A, denoted [a], is the set of all elements in A related to a: [a] = {x in A : (x, a) in R}.
The Fundamental Theorem of Equivalence Relations (Partitions)
The Fundamental Theorem states that any equivalence relation on a set A partitions A into mutually disjoint equivalence classes whose union is the entire set A. Two equivalence classes [a] and [b] are either identical or disjoint: [a] = [b] iff (a, b) in R, else [a] cap [b] = Phi.
Congruence Modulo m and Residue Classes Z_m
For integers a, b and positive integer m, a is congruent to b modulo m, written a = b (mod m), if m divides (a - b). This equivalence relation partitions Z into m residue classes: [0], [1], ..., [m - 1].
Types of Functions: Injective (One-One), Surjective (Onto) & Bijective Mappings
3 concepts · 1.3How do one-one and onto conditions govern functional mappings, how is injectivity determined graphically and analytically, and how are injections, surjections, and bijections enumerated combinatorially?
A function f: X -> Y maps every element x in X to a unique element y = f(x) in Y. A function is Injective (One-to-One) if distinct elements in the domain map to distinct images in the codomain: x1 != x2 implies f(x1) != f(x2), or contrapositively, f(x1) = f(x2) implies x1 = x2. Graphically, a function is injective if and only if every horizontal line intersects its graph at most once (Horizontal Line Test); analytically, a differentiable function on an interval is injective if its derivative f'(x) is strictly positive or strictly negative throughout (strictly monotonic). A function is Surjective (Onto) if every element in the codomain Y possesses at least one pre-image in domain X: for every y in Y, there exists x in X such that f(x) = y, which holds if and only if Range(f) = Codomain(Y). A function that is both Injective and Surjective is called Bijective (One-to-One Correspondence). For finite sets with |X| = m and |Y| = n: Total functions = n^m; Injections = nPm if m <= n (0 if m > n by the Pigeonhole Principle); Bijections = n! if m = n (0 if m != n); and Surjections = sum_{r=0}^n (-1)^(n-r) * nCr * r^m for m >= n.
Injective (One-to-One) Functions: f(x1) = f(x2) => x1 = x2
A function f: X -> Y is Injective (one-one) if distinct elements in X have distinct images in Y: f(x1) = f(x2) implies x1 = x2. Graphically, every horizontal line intersects the curve at most once.
Surjective (Onto) Functions: Range(f) = Codomain(Y)
A function f: X -> Y is Surjective (onto) if every element y in codomain Y has at least one pre-image x in domain X such that f(x) = y. Equivalently, Range(f) = Codomain(Y).
Bijective Functions and Cardinality Requirements
A function f: X -> Y is Bijective if it is both Injective (one-one) and Surjective (onto). For finite sets, a bijection exists if and only if |X| = |Y|.
Composition of Functions: Pipeline Construction & Preservation Theorems
3 concepts · 1.4Under what exact domain-range conditions does composite function g o f exist, why is composition generally non-commutative, and what do preservation theorems dictate about injectivity and surjectivity?
Let f: A -> B and g: B -> C be two functions. The Composite Function g o f (read as 'g circle f' or 'g composed with f') is a function from A to C defined by (g o f)(x) = g(f(x)) for all x in A. For g o f to be well-defined, the output of f must be an admissible input for g; that is, the Range of f must be a subset of the Domain of g: Range(f) subseteq Domain(g). Composition of functions satisfies associativity: h o (g o f) = (h o g) o f for all compatible functions f, g, h. However, composition is in general NOT commutative: g o f != f o g (in fact, f o g often cannot even be formed because the domains and codomains may be entirely incompatible). Composition preserves mapping properties in the forward direction: (1) If f and g are both injective, then g o f is injective; (2) If f and g are both surjective, then g o f is surjective; (3) If f and g are both bijective, then g o f is bijective. In the reverse direction (crucial competitive trap): If g o f is injective, it guarantees that f MUST be injective (g need not be injective); if g o f is surjective, it guarantees that g MUST be surjective (f need not be surjective).
Function Composition Definition: (g o f)(x) = g(f(x))
Let f: A -> B and g: B -> C. The composite function g o f: A -> C is defined by (g o f)(x) = g(f(x)) for all x in A. Crucially, Range(f) must be a subset of Domain(g).
Non-Commutativity (g o f != f o g) and Associativity of Composition
In general, function composition is NOT commutative: g o f != f o g. However, function composition is ALWAYS associative: h o (g o f) = (h o g) o f whenever the compositions are defined.
Preservation Theorems: Injectivity and Surjectivity of Composite Maps
Theorem 1: If f: A -> B and g: B -> C are both injective, then g o f is injective. Theorem 2: If f and g are both surjective, then g o f is surjective. Conversely, if g o f is injective, f MUST be injective (g may not be); if g o f is surjective, g MUST be surjective (f may not be).
Invertible Functions, Inverse Mapping & Reflection Symmetry across y = x
3 concepts · 1.5What is the rigorous definition of an invertible function, why is bijectivity both necessary and sufficient for invertibility, and how does the line y = x govern inverse graphs?
A function f: X -> Y is defined to be Invertible if there exists a function g: Y -> X such that g o f = I_X (the identity function on X) and f o g = I_Y (the identity function on Y). When such a function g exists, it is unique and is denoted as f^(-1) (the inverse of f). The Fundamental Theorem of Invertibility establishes that a function f: X -> Y is invertible if and only if f is Bijective (both one-one and onto). If f is not one-one, its inverse would map a single input to multiple outputs, violating the definition of a function; if f is not onto, its inverse would be undefined for unmapped codomain elements. Key algebraic properties of inverses include: (1) Involution: (f^(-1))^(-1) = f; (2) Reversal Law: (g o f)^(-1) = f^(-1) o g^(-1); and (3) Domain-Range Inversion: Dom(f^(-1)) = Range(f) and Range(f^(-1)) = Dom(f). Geometrically, if (a, b) lies on the graph of y = f(x), then (b, a) must lie on the graph of y = f^(-1)(x). Therefore, the graph of y = f^(-1)(x) is the exact bilateral mirror reflection of the graph of y = f(x) across the diagonal line y = x.
Invertibility Criteria: Bijectivity and the Identity Composition
A function f: X -> Y is invertible if and only if there exists a function g: Y -> X such that g o f = I_X and f o g = I_Y. This function g is unique and called the inverse of f, denoted f^(-1). A function is invertible if and only if it is a Bijection.
Algebraic Protocol for Finding the Inverse Function f^(-1)(x)
To find f^(-1)(x): (1) Set y = f(x); (2) Solve the equation algebraically for x in terms of y, giving x = g(y); (3) Replace y with x to write f^(-1)(x) = g(x).
Geometric Reflection Symmetry Across the Line y = x
The graph of y = f^(-1)(x) is the exact geometric reflection of the graph of y = f(x) across the diagonal line y = x. If point (a, b) lies on y = f(x), then point (b, a) lies on y = f^(-1)(x).
Binary Operations, Identity Elements, Inverses & Cayley Tables
3 concepts · 1.6What formal axioms define a binary operation on a set, how are commutativity, associativity, identity, and inverse verified, and how are Cayley tables analyzed visually?
A Binary Operation * on a set A is a function *: A x A -> A. The output *(a, b) is written as a * b, and the requirement that a * b in A for all a, b in A is known as the Closure Property. A binary operation * on A is Commutative if a * b = b * a for all a, b in A; it is Associative if (a * b) * c = a * (b * c) for all a, b, c in A. An element e in A is called an Identity Element for * if a * e = e * a = a for all a in A (e.g., 0 for addition on R, 1 for multiplication on R). If an identity element exists, an element a in A is said to be Invertible with respect to * if there exists an element b in A such that a * b = b * a = e; the element b is the unique inverse of a, denoted as a^(-1). For a finite set A = {a1, a2, ..., an}, a binary operation is completely displayed via an n x n Operation Table (Cayley Table). In a Cayley table: (1) Commutativity is confirmed if and only if the table is symmetric about its main diagonal; (2) The identity element e is identified by locating the row and column that exactly duplicate the top and left header labels; and (3) The inverse of any element x is found by locating the cell containing e in the row of x and reading the corresponding column header. On a finite set of n elements, there are n^(n^2) total binary operations and n^(n(n+1)/2) commutative binary operations.
Binary Operation Definition and Closure Property
A binary operation * on a non-empty set A is a function * : A x A -> A. We denote *(a, b) by a * b. Closure requires that for all a, b in A, the result a * b must belong to A.
Commutativity and Associativity of Binary Operations
An operation * on A is: (1) Commutative if a * b = b * a for all a, b in A; (2) Associative if (a * b) * c = a * (b * c) for all a, b, c in A.
Identity Element, Invertible Elements, and Cayley Tables
An element e in A is the Identity for * if a * e = e * a = a for all a in A. An element a in A is Invertible if there exists b in A such that a * b = b * a = e; b is called the inverse of a (a^(-1)). On a finite set, * is visualized via a Cayley table.