Sets, Relations, Functions (JEE)

Cheatsheet Content

Sets, Relations, Functions Essential concepts for JEE Mains & Advanced covering mathematical structures and mappings. Concept Map Sets: Definition, operations ($\cup, \cap, -, \Delta, ^c$), Venn diagrams, cardinality, power set, De Morgan's Laws. Relations: Definition, types (reflexive, symmetric, transitive, antisymmetric), equivalence relations & partitions. Functions: Definition, domain/codomain/range, injective/surjective/bijective, composition, inverse, counting functions. 1. Sets A collection of well-defined, distinct objects. 1.1 Basic Definitions & Notation Set: $A = \{1, 2, 3\}$ Element: $x \in A$ (x is an element of A), $y \notin A$ (y is not an element of A) Subset: $A \subseteq B$ (A is a subset of B). $A \subset B$ (proper subset). Equality: $A = B \iff A \subseteq B \text{ and } B \subseteq A$. Empty Set: $\emptyset$ or $\{\}$ (set with no elements). Universal Set: $U$ (the set of all possible elements under consideration). Cardinality: $|A|$ (number of elements in set A). 1.2 Set Operations Union: $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$ Intersection: $A \cap B = \{x \mid x \in A \text{ and } x \in B\}$ Difference: $A - B = \{x \mid x \in A \text{ and } x \notin B\}$ (also $A \setminus B$) Symmetric Difference: $A \Delta B = (A - B) \cup (B - A) = (A \cup B) - (A \cap B)$ Complement: $A^c = U - A = \{x \mid x \in U \text{ and } x \notin A\}$ 1.3 Properties & Laws Commutative Laws: $A \cup B = B \cup A$, $A \cap B = B \cap A$ Associative Laws: $(A \cup B) \cup C = A \cup (B \cup C)$, $(A \cap B) \cap C = A \cap (B \cap C)$ Distributive Laws: $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$, $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ De Morgan's Laws: $(A \cup B)^c = A^c \cap B^c$, $(A \cap B)^c = A^c \cup B^c$ Idempotent Laws: $A \cup A = A$, $A \cap A = A$ Identity Laws: $A \cup \emptyset = A$, $A \cap U = A$, $A \cup U = U$, $A \cap \emptyset = \emptyset$ Complement Laws: $A \cup A^c = U$, $A \cap A^c = \emptyset$, $(A^c)^c = A$ 1.4 Power Set & Cardinality Power Set: $\mathcal{P}(A)$ is the set of all subsets of $A$. Cardinality of Power Set: If $|A|=n$, then $|\mathcal{P}(A)|=2^n$. (M) Counting Formula for Union: $|A \cup B| = |A| + |B| - |A \cap B|$ (A) Counting Formula for 3 Sets: $|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$ 1.5 Venn Diagrams Visual representation of sets and their relationships. A B A ∪ B A ∩ B A B C U 2. Relations A relation $R$ from set $A$ to set $B$ is a subset of the Cartesian product $A \times B$. If $A=B$, it's a relation on $A$. 2.1 Types of Relations on a Set $A$ Reflexive: $(a, a) \in R$ for all $a \in A$. Symmetric: If $(a, b) \in R$, then $(b, a) \in R$. Transitive: If $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$. Antisymmetric: If $(a, b) \in R$ and $(b, a) \in R$, then $a = b$. 2.2 Equivalence Relations A relation is an equivalence relation if it is reflexive, symmetric, and transitive. Equivalence Class: For an equivalence relation $R$ on $A$, the equivalence class of $a \in A$ is $[a] = \{x \in A \mid (x, a) \in R\}$. Partition: An equivalence relation on $A$ partitions $A$ into disjoint equivalence classes whose union is $A$. Conversely, any partition of $A$ defines an equivalence relation. (A) Number of Equivalence Relations: Given by Bell numbers $B_n$ for a set of size $n$. 2.3 Partial Order Relation A relation is a partial order if it is reflexive, antisymmetric, and transitive. (e.g., $\le$ on numbers, $\subseteq$ on sets) 3. Functions A function (or mapping) $f: A \to B$ assigns to each element $x \in A$ exactly one element $y \in B$. 3.1 Basic Definitions Domain: Set $A$. Codomain: Set $B$. Range (Image): $f(A) = \{f(x) \mid x \in A\} \subseteq B$. Image of an element: $f(x) = y$. Preimage of an element: $f^{-1}(y) = \{x \in A \mid f(x) = y\}$. (A) Preimage of a set: $f^{-1}(S) = \{x \in A \mid f(x) \in S\}$ for $S \subseteq B$. 3.2 Types of Functions Injective (One-to-one): If $f(x_1) = f(x_2) \implies x_1 = x_2$. (No two elements in domain map to the same element in codomain). Surjective (Onto): For every $y \in B$, there exists an $x \in A$ such that $f(x) = y$. (Range = Codomain). Bijective (One-to-one and Onto): Both injective and surjective. 3.3 Composition of Functions If $f: A \to B$ and $g: B \to C$, then $g \circ f: A \to C$ is defined by $(g \circ f)(x) = g(f(x))$. Properties: Composition is associative: $h \circ (g \circ f) = (h \circ g) \circ f$. If $g \circ f$ is injective, then $f$ is injective. If $g \circ f$ is surjective, then $g$ is surjective. If $f, g$ are bijections, then $g \circ f$ is a bijection. 3.4 Inverse Function If $f: A \to B$ is a bijection, then its inverse $f^{-1}: B \to A$ exists such that $f^{-1}(f(x)) = x$ and $f(f^{-1}(y)) = y$. 3.5 Counting Functions Let $|A|=m$ and $|B|=n$. Total number of functions $f: A \to B$: $n^m$. Number of injective functions $f: A \to B$: $P(n, m) = \frac{n!}{(n-m)!}$ if $m \le n$, else $0$. ($P(n,m) = n(n-1)\dots(n-m+1)$) Number of bijective functions $f: A \to B$: $n!$ if $m=n$, else $0$. (A) Number of surjective functions $f: A \to B$: $n^m - \binom{n}{1}(n-1)^m + \binom{n}{2}(n-2)^m - \dots + (-1)^{n-1}\binom{n}{n-1}(1)^m$. This is $n! \times S(m,n)$, where $S(m,n)$ are Stirling numbers of the second kind. 3.6 Characteristic Function For a set $A \subseteq U$, its characteristic function $\chi_A: U \to \{0, 1\}$ is defined by $\chi_A(x) = 1$ if $x \in A$ and $0$ if $x \notin A$. Useful for converting set operations to arithmetic. Worked Examples Example 1 (Mains — set ops, Venn counting) Problem: Let universal set $U=\{1,2,\dots,10\}$. Let $A=\{1,2,3,4,5\},\; B=\{4,5,6,7\}$. Find: $A \cup B, A \cap B, A \setminus B, A^c$. Solution: $A \cup B=\{1,2,3,4,5,6,7\}$. $A \cap B=\{4,5\}$. $A \setminus B=\{1,2,3\}$. $A^c=U \setminus A=\{6,7,8,9,10\}$. Exam tip: List elements quickly; use complement to count large sets. Example 2 (Mains — relation classification) Problem: On $S=\{1,2,3\}$, define $R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$. Is R an equivalence relation? If yes, write classes. Solution: Reflexive? Yes — $(1,1),(2,2),(3,3)$ present. Symmetric? Yes — when $(1,2)$ is present, $(2,1)$ also is; others trivial. Transitive? Check pairs: the only nontrivial are $(1,2)$ and $(2,1) \to (1,1)$ exists; combos produce no missing pairs. So transitive holds. Therefore R is an equivalence relation. Equivalence classes: $[1]=[2]=\{1,2\},\;[3]=\{3\}$. Exam tip: For small finite sets, check properties by brute force. Example 3 (Mains — injective/surjective) Problem: $f:\mathbb{R}\to\mathbb{R},\; f(x)=2x+1$. Is f injective? surjective? Find inverse. Solution: Injective: Suppose $2x_1+1=2x_2+1 \Rightarrow x_1=x_2 \Rightarrow$ injective. Surjective: For any $y \in \mathbb{R}$, choose $x=(y-1)/2$. Then $f(x) = 2((y-1)/2)+1 = y-1+1 = y$. So surjective. Hence bijection. Inverse: Set $y=2x+1 \Rightarrow x=(y-1)/2$. So $f^{-1}(y)=(y-1)/2$. Exam tip: Linear nonzero slope $\Rightarrow$ bijection. Example 4 (Advanced — count onto functions via inclusion–exclusion) Problem: Number of surjections from a 4-element domain onto a 2-element codomain. Solution: Total functions = $2^4=16$. Exclude functions hitting only one codomain element: there are 2 constant maps (all map to $y_1$ or all map to $y_2$). So onto = $2^4 - 2 = 16 - 2 = 14$. General formula for onto count from $m$ (domain) $\to k$ (codomain): $k^m - \binom{k}{1}(k-1)^m + \binom{k}{2}(k-2)^m - \dots + (-1)^{k-1}\binom{k}{k-1}(1)^m$. Exam tip: For small $k$, simpler to subtract constant maps. Example 5 (Advanced — composition property proof & counterexample) Problem: Show: if $g \circ f$ is injective then f is injective. Give example where $g \circ f$ injective but g not injective. Solution: Proof: Suppose $f(x_1)=f(x_2)$. Apply g: $g(f(x_1))=g(f(x_2))$. This means $(g \circ f)(x_1) = (g \circ f)(x_2)$. But $g \circ f$ is injective $\Rightarrow x_1=x_2$. Hence f is injective. Counterexample: Let $f:\{1\}\to\{1,2\}$ with $f(1)=1$. Let $g:\{1,2\}\to\{a\}$ be constant map, i.e., $g(1)=a, g(2)=a$. Then $(g \circ f)(1) = g(f(1)) = g(1) = a$. $g \circ f: \{1\} \to \{a\}$ maps $1 \to a$. This function is trivially injective (domain size 1). However, $g$ is not injective because $g(1)=g(2)=a$ but $1 \ne 2$. Exam tip: Remember: injectivity of composition forces left factor injective; surjectivity forces right factor surjective. Example 6 (Advanced — equivalence relation from parity) Problem: On $\mathbb{Z}$ define $a \sim b$ iff $a-b$ is even. Show it's an equivalence relation and find classes. Solution: Reflexive: For any $a \in \mathbb{Z}$, $a-a=0$, which is even. So $a \sim a$. Symmetric: If $a \sim b$, then $a-b$ is even. This means $a-b = 2k$ for some integer $k$. Then $b-a = -(a-b) = -2k$, which is also even. So $b \sim a$. Transitive: If $a \sim b$ and $b \sim c$, then $a-b = 2k_1$ and $b-c = 2k_2$ for integers $k_1, k_2$. Adding these equations: $(a-b) + (b-c) = 2k_1 + 2k_2 \Rightarrow a-c = 2(k_1+k_2)$, which is even. So $a \sim c$. Since it's reflexive, symmetric, and transitive, it is an equivalence relation. Classes: $[0] = \{x \in \mathbb{Z} \mid x-0 \text{ is even}\} = \{\dots, -4, -2, 0, 2, 4, \dots\}$ (Set of even integers). $[1] = \{x \in \mathbb{Z} \mid x-1 \text{ is even}\} = \{\dots, -3, -1, 1, 3, 5, \dots\}$ (Set of odd integers). These are the two equivalence classes: the set of even integers and the set of odd integers. They form a partition of $\mathbb{Z}$. Exam tip: "difference even" often yields parity partition. Practice Problems Mains Problems Let $A = \{x \in \mathbb{N} \mid x \le 10\}$ and $B = \{x \in \mathbb{N} \mid x \text{ is prime and } x \le 10\}$. Find $|A \cup B|$ and $|A \cap B|$. If $U = \{1, 2, \dots, 20\}$ and $A = \{x \mid x \text{ is a multiple of 3}\}$, $B = \{x \mid x \text{ is a multiple of 5}\}$. Find $|A \cup B|$. Which of the following relations on $\mathbb{Z}$ is an equivalence relation? (a) $aRb \iff a \le b$ (b) $aRb \iff a-b (c) $aRb \iff a^2 = b^2$ Let $f: \mathbb{R} \to \mathbb{R}$ be defined by $f(x) = x^2$. Is $f$ injective? surjective? Mains Solutions $A=\{1,2,3,4,5,6,7,8,9,10\}$, $|A|=10$. $B=\{2,3,5,7\}$, $|B|=4$. $A \cap B = \{2,3,5,7\}$, $|A \cap B|=4$. $|A \cup B| = |A| + |B| - |A \cap B| = 10 + 4 - 4 = 10$. $A=\{3,6,9,12,15,18\}$, $|A|=6$. $B=\{5,10,15,20\}$, $|B|=4$. $A \cap B = \{15\}$, $|A \cap B|=1$. $|A \cup B| = 6 + 4 - 1 = 9$. (a) Reflexive (true), Antisymmetric (true), Transitive (true). Not symmetric. So not equivalence. (b) Reflexive ($0 (c) Reflexive ($a^2=a^2$, true). Symmetric (if $a^2=b^2$, then $b^2=a^2$, true). Transitive (if $a^2=b^2$ and $b^2=c^2$, then $a^2=c^2$, true). Hence, (c) is an equivalence relation. Injective? No. $f(-2)=4$ and $f(2)=4$, but $-2 \ne 2$. Surjective? No. The range is $[0, \infty)$, which is a subset of the codomain $\mathbb{R}$ but not equal to it. For example, there is no $x$ such that $f(x)=-1$. Advanced Problems Let $A=\{1,2,3\}$ and $B=\{a,b\}$. How many surjective functions are there from $A$ to $B$? Prove that if $f:A \to B$ and $g:B \to C$ are both surjective, then $g \circ f: A \to C$ is surjective. Let $f: X \to Y$. Prove: $f^{-1}(Y \setminus B) = X \setminus f^{-1}(B)$ for any $B \subseteq Y$. How many distinct equivalence relations can be defined on a set with 3 elements? Advanced Solutions Using inclusion-exclusion formula: $k=2, m=3$. $2^3 - \binom{2}{1}(2-1)^3 + \binom{2}{2}(2-2)^3 = 8 - 2(1)^3 + 1(0)^3 = 8 - 2 + 0 = 6$. Alternatively: Total functions $2^3=8$. Functions that miss 'a' (map only to 'b') is 1. Functions that miss 'b' (map only to 'a') is 1. Surjective = $8 - 1 - 1 = 6$. Proof: Let $z \in C$. Since $g$ is surjective, there exists $y \in B$ such that $g(y)=z$. Since $f$ is surjective, there exists $x \in A$ such that $f(x)=y$. Combining these, $(g \circ f)(x) = g(f(x)) = g(y) = z$. Thus, for any $z \in C$, there exists an $x \in A$ such that $(g \circ f)(x)=z$. Therefore, $g \circ f$ is surjective. Proof: Let $x \in f^{-1}(Y \setminus B) \iff f(x) \in Y \setminus B \iff f(x) \in Y \text{ and } f(x) \notin B$. Since $f(x) \in Y$ is always true, this simplifies to $f(x) \notin B$. $f(x) \notin B \iff x \notin f^{-1}(B)$. $x \notin f^{-1}(B) \iff x \in X \setminus f^{-1}(B)$. Hence, $f^{-1}(Y \setminus B) = X \setminus f^{-1}(B)$. This is the Bell number $B_3$. Partitions of a 3-element set $\{1,2,3\}$: 1. $\{\{1,2,3\}\}$ (1 partition) 2. $\{\{1,2\}, \{3\}\}$, $\{\{1,3\}, \{2\}\}$, $\{\{2,3\}, \{1\}\}$ (3 partitions) 3. $\{\{1\}, \{2\}, \{3\}\}$ (1 partition) Total = $1+3+1 = 5$ distinct equivalence relations. Common Pitfalls & Exam Tips Codomain vs. Range: The range is a subset of the codomain. For a function to be surjective, they must be equal. Transitivity Check: Always check transitivity for all possible triples $(a,b), (b,c)$ in the relation. Don't assume. De Morgan's Laws: $(A \cup B)^c = A^c \cap B^c$, NOT $A^c \cup B^c$. Counting Onto Maps: The inclusion-exclusion principle is crucial for general cases. For small cases, total-minus-not-onto works. Function Composition: Remember $g \circ f$ is read right-to-left: $f$ applies first, then $g$. Fast Formulas & Shortcuts (1-Page Revision) Set Algebra Identities $A \cup B = (A \setminus B) \cup (B \setminus A) \cup (A \cap B)$ $|A \cup B| = |A| + |B| - |A \cap B|$ $|A \cup B \cup C| = \sum |A| - \sum |A \cap B| + |A \cap B \cap C|$ $(A \cup B)^c = A^c \cap B^c$ -- De Morgan's $(A \cap B)^c = A^c \cup B^c$ -- De Morgan's $A \setminus B = A \cap B^c$ $A \Delta B = (A \cup B) \setminus (A \cap B)$ Relation Properties Summary (on set A) Property Definition Consequence/Use Reflexive $\forall a \in A, (a,a) \in R$ Each element relates to itself Symmetric $(a,b) \in R \implies (b,a) \in R$ Relation is two-way Transitive $(a,b) \in R, (b,c) \in R \implies (a,c) \in R$ Chain-like property Antisymmetric $(a,b) \in R, (b,a) \in R \implies a=b$ No two distinct elements are related both ways Equivalence Relation: Reflexive + Symmetric + Transitive. Partitions a set. Partial Order: Reflexive + Antisymmetric + Transitive. Counting Functions (Domain $|A|=m$, Codomain $|B|=n$) Total Functions $f: A \to B$: $n^m$ Injective Functions $f: A \to B$: $P(n,m) = n(n-1)\dots(n-m+1)$ (if $m \le n$, else 0) Bijective Functions $f: A \to B$: $n!$ (if $m=n$, else 0) Surjective Functions $f: A \to B$: $\sum_{i=0}^{n} (-1)^i \binom{n}{i} (n-i)^m$ (Inclusion-Exclusion) (A) Number of Partitions of a set of size $n$: Bell Number $B_n$. Each partition corresponds to an equivalence relation. Function Composition & Inverse Properties If $g \circ f$ is injective $\implies f$ is injective. If $g \circ f$ is surjective $\implies g$ is surjective. $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ $f^{-1}(B \cup C) = f^{-1}(B) \cup f^{-1}(C)$ $f^{-1}(B \cap C) = f^{-1}(B) \cap f^{-1}(C)$ $f^{-1}(Y \setminus B) = X \setminus f^{-1}(B)$