Union of Two Sets (Inclusion-Exclusion)
#1n(A∪B)=n(A)+n(B)−n(A∩B) 💡 For three sets: n(A union B union C) = n(A) + n(B) + n(C) - n(A cap B) - n(B cap C) - n(A cap C) + n(A cap B cap C). Always subtract the pairwise overlaps and add back the triple overlap.
⚠ Forgetting to subtract n(A cap B) and double-counting elements in the intersection.
De Morgan's Laws
#2(A∪B)′=A′∩B′and(A∩B)′=A′∪B′ 💡 Complement of union is intersection of complements. Complement of intersection is union of complements. These hold for any number of sets.
⚠ Swapping the operations: writing (A union B)' = A' union B' instead of A' cap B'.
Reflexive, Symmetric, Transitive Conditions
#3Reflexive: (a,a)∈R∀a∈A∣Symmetric: (a,b)∈R⇒(b,a)∈R∣Transitive: (a,b),(b,c)∈R⇒(a,c)∈R 💡 Reflexive requires every element to be related to itself. Symmetric requires the relation to work both ways. Transitive requires chains to close. Check each condition independently.
⚠ Assuming that a relation with some (a, a) pairs is reflexive. It must hold for ALL elements of the set.
Equivalence Class
#4[a]={x∈A:(a,x)∈R} 💡 The equivalence class of a is the set of all elements related to a. Equivalence classes partition the set into disjoint, exhaustive subsets. Two elements have the same equivalence class if and only if they are related.
One-One (Injective) and Onto (Surjective) Definitions
#5One-one: f(a)=f(b)⇒a=b∣Onto: ∀y∈B,∃x∈A s.t. f(x)=y 💡 One-one means no two distinct inputs give the same output. Onto means every element of the codomain is hit. A function that is both one-one and onto is called bijective.
⚠ Confusing one-one with onto. One-one is about distinct inputs giving distinct outputs. Onto is about the range equalling the codomain.
Domain of Composite Function
#6dom(g∘f)={x∈dom(f):f(x)∈dom(g)} 💡 For g(f(x)) to exist, x must be in the domain of f AND f(x) must be in the domain of g. Always check both conditions.
⚠ Computing the domain of g(f(x)) by only checking where g is defined, without verifying that f(x) falls in g's domain.
Inverse Function Existence
#7f−1 exists⟺f is bijective (one-one and onto) 💡 Only bijective functions have inverses. If f is one-one but not onto, restrict the codomain to the range to make it bijective. If f is onto but not one-one, no inverse exists.
⚠ Trying to find the inverse of a function that is not one-one. For example, f(x) = x^2 on R has no inverse because f(2) = f(-2).
Number of Relations on a Set
#8Number of relations from A to B=2n(A)⋅n(B) 💡 A relation from A to B is any subset of A x B. Since A x B has n(A)*n(B) elements, the number of subsets is 2^(n(A)*n(B)). For a relation on set A (from A to A), this becomes 2^(n(A)^2).
Number of Onto Functions (Surjections)
#9Onto functions from A to B=k=0∑n(−1)k⋅nCk⋅(n−k)m 💡 Here m = n(A) and n = n(B) with m >= n. This uses inclusion-exclusion. For n(B) = 2: onto functions = 2^m - 2. For n(B) = 3: onto functions = 3^m - 3*2^m + 3.
⚠ Using the formula when m < n. There are no onto functions when the domain is smaller than the codomain.
Floor and Ceiling Functions
#10⌊x⌋=greatest integer≤x∣⌈x⌉=least integer≥x 💡 Also called the greatest integer function [x]. For negative numbers: floor(-2.3) = -3, not -2. The fractional part {x} = x - floor(x) always satisfies 0 <= {x} < 1.
⚠ Computing floor(-2.3) as -2 instead of -3. The floor function rounds towards negative infinity, not towards zero.