📘 1.
SETS
Definition:
A set is a collection of distinct, well-defined objects.
We denote a set with capital letters like A,B,CA, B, CA,B,C etc.
Example:
A={1,2,3,4,5}A = \{1, 2, 3, 4, 5\}A={1,2,3,4,5}
means set AAA contains the elements 1 to 5.
Types of Sets:
1. Finite Set → Limited number of elements
Example: A={1,2,3}A = \{1,2,3\}A={1,2,3}
2. Infinite Set → Unlimited number of elements
Example: N={1,2,3,…}N = \{1,2,3,\ldots\}N={1,2,3,…}
Example: ∅={}\emptyset = \{\}∅={}
3. Empty (Null) Set → No element
4. Subset
A⊆BA \subseteq BA⊆B if every element of AAA is also in BBB.
Example: A={1,2},B={1,2,3}⇒A⊆BA = \{1,2\}, B = \{1,2,3\} \Rightarrow A \subseteq
BA={1,2},B={1,2,3}⇒A⊆B
5. Proper Subset
A⊂BA \subset BA⊂B if A⊆BA \subseteq BA⊆B and A≠BA \neq BA=B
6. Universal Set (U)
Contains all possible elements under discussion.
Set Operations:
Symbo
Operation Example Result
l
A∪BA
{1,2}∪{2,3}\{1,2\} \cup \{2,3\}
Union \cup {1,2,3}\{1,2,3\}{1,2,3}
{1,2}∪{2,3}
BA∪B
A∩BA
{1,2}∩{2,3}\{1,2\} \cap \{2,3\}
Intersection \cap {2}\{2\}{2}
{1,2}∩{2,3}
BA∩B
Difference A−BA {1,2,3}−{2,3}\{1,2,3\} - \{2,3\} {1}\{1\}{1}
Symbo
Operation Example Result
l
-
{1,2,3}−{2,3}
BA−B
If U={1,2,3,4,5}U=\
Complemen A′={3,4,5}A'=\{3,4,5\}A
A′A'A′ {1,2,3,4,5\}U={1,2,3,4,5}, A={1,2}A=\
t ′={3,4,5}
{1,2\}A={1,2}
Properties of Set Operations:
1. Commutative:
A∪B=B∪AA \cup B = B \cup AA∪B=B∪A, A∩B=B∩AA \cap B = B \cap
AA∩B=B∩A
2. Associative:
(A∪B)∪C=A∪(B∪C)(A \cup B) \cup C = A \cup (B \cup C)(A∪B)∪C=A∪(B∪C)
3. Distributive:
A∩(B∪C)=(A∩B)∪(A∩C)A \cap (B \cup C) = (A \cap B) \cup (A \cap
C)A∩(B∪C)=(A∩B)∪(A∩C)
4. Identity Laws:
A∪∅=AA \cup \emptyset = AA∪∅=A, A∩U=AA \cap U = AA∩U=A
5. Complement Laws:
A∪A′=UA \cup A' = UA∪A′=U, A∩A′=∅A \cap A' = \emptysetA∩A′=∅
Example Questions:
Q1. If A={1,2,3}A = \{1, 2, 3\}A={1,2,3} and B={3,4,5}B = \{3, 4, 5\}B={3,4,5}, find A∪BA \
cup BA∪B, A∩BA \cap BA∩B, and A−BA - BA−B.
Ans:
A∪B={1,2,3,4,5}A \cup B = \{1,2,3,4,5\}A∪B={1,2,3,4,5}
A∩B={3}A \cap B = \{3\}A∩B={3}
A−B={1,2}A - B = \{1,2\}A−B={1,2}
Q2. Prove that (A∪B)′=A′∩B′(A \cup B)' = A' \cap B'(A∪B)′=A′∩B′.
Proof:
Using De Morgan’s Law:
Let x∈(A∪B)′x \in (A \cup B)'x∈(A∪B)′ → xxx not in A∪BA \cup BA∪B → xxx not in AAA
and not in BBB → x∈A′∩B′x \in A' \cap B'x∈A′∩B′.
Hence, proved.
📘 2. RELATIONS
Definition:
A relation from set AAA to set BBB is a subset of their Cartesian product A×BA \times BA×B.
If A={1,2,3}A = \{1, 2, 3\}A={1,2,3}, B={a,b}B = \{a, b\}B={a,b}, then:
A×B={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)}A \times B = \{(1,a), (1,b), (2,a), (2,b), (3,a),
(3,b)\}A×B={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)}
A relation R={(1,a),(2,b)}R = \{(1,a), (2,b)\}R={(1,a),(2,b)} means 1Ra1Ra1Ra and
2Rb2Rb2Rb.
Types of Relations:
1. Reflexive:
(a,a)∈R ∀a∈A(a,a) \in R \, \forall a \in A(a,a)∈R∀a∈A
Every element is related to itself.
2. Symmetric:
If (a,b)∈R⇒(b,a)∈R(a,b) \in R \Rightarrow (b,a) \in R(a,b)∈R⇒(b,a)∈R
3. Transitive:
If (a,b)∈R(a,b) \in R(a,b)∈R and (b,c)∈R⇒(a,c)∈R(b,c) \in R \Rightarrow (a,c) \in
R(b,c)∈R⇒(a,c)∈R
4. Antisymmetric:
If (a,b)∈R(a,b) \in R(a,b)∈R and (b,a)∈R⇒a=b(b,a) \in R \Rightarrow
a=b(b,a)∈R⇒a=b
5. Equivalence Relation:
A relation that is Reflexive, Symmetric, and Transitive.
Example:
Let A={1,2,3}A = \{1,2,3\}A={1,2,3}
Define R={(1,1),(2,2),(3,3),(1,2),(2,1)}R = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}R={(1,1),(2,2),(3,3),
(1,2),(2,1)}
✅ Reflexive: yes
✅ Symmetric: yes
✅ Transitive: yes
👉 Therefore, RRR is an equivalence relation.
Practice Questions:
Q1. For A={1,2,3}A = \{1,2,3\}A={1,2,3}, define R={(a,b)∣a≤b}R = \{(a,b) | a \leq
b\}R={(a,b)∣a≤b}.
Check if RRR is reflexive, symmetric, or transitive.
Q2. Show that “divisibility” relation on integers is transitive but not symmetric.
📘 3. FUNCTIONS
Definition:
A function from set AAA to set BBB is a relation where each element of A is related to
exactly one element of B.
f:A→Bf: A \rightarrow Bf:A→B
Example:
A={1,2,3},B={a,b,c}A = \{1,2,3\}, B = \{a,b,c\}A={1,2,3},B={a,b,c}
f={(1,a),(2,b),(3,c)}f = \{(1,a),(2,b),(3,c)\}f={(1,a),(2,b),(3,c)}
Types of Functions:
Type Condition Example
One-One Different inputs →
f(x)=x+1f(x)=x+1f(x)=x+1
(Injective) different outputs
Onto Every element of BBB has f(x)=x2f(x)=x^2f(x)=x2 from [−1,1]→[0,1][-
(Surjective) a preimage 1,1]→[0,1][−1,1]→[0,1]
f(x)=x+1f(x)=x+1f(x)=x+1 where domain =
Bijective Both One-One and Onto
codomain
Constant Every element of AAA
f(x)=2f(x)=2f(x)=2
Function maps to same bbb
Composition of Functions:
If f:A→Bf: A \to Bf:A→B and g:B→Cg: B \to Cg:B→C,
then g∘f:A→Cg∘f: A \to Cg∘f:A→C defined by (g∘f)(x)=g(f(x))(g∘f)(x) = g(f(x))(g∘f)
(x)=g(f(x)).
Example:
f(x)=x+1f(x)=x+1f(x)=x+1, g(x)=2xg(x)=2xg(x)=2x
Then (g∘f)(x)=g(f(x))=2(x+1)=2x+2(g∘f)(x) = g(f(x)) = 2(x+1) = 2x+2(g∘f)
(x)=g(f(x))=2(x+1)=2x+2
Inverse Function:
If fff is bijective, inverse f−1f^{-1}f−1 exists such that
f−1(f(x))=xf^{-1}(f(x))=xf−1(f(x))=x.
Example:
If f(x)=2x+3f(x)=2x+3f(x)=2x+3, then f−1(x)=x−32f^{-1}(x)=\frac{x-3}{2}f−1(x)=2x−3
Practice Questions:
Q1. If f(x)=x2f(x)=x^2f(x)=x2, g(x)=x+2g(x)=x+2g(x)=x+2, find (f∘g)(x)(f∘g)(x)(f∘g)(x) and
(g∘f)(x)(g∘f)(x)(g∘f)(x).
Q2. Determine if f(x)=3x+5f(x)=3x+5f(x)=3x+5 is bijective.
Q3. Find inverse of f(x)=x−4f(x)=x−4f(x)=x−4.
PROOF TECHNIQUES in TOC (and
Discrete Math)
🔹 1. Direct Proof
Concept:
We start from what is given (premise) and logically show that the conclusion is true.
Form:
If PPP then QQQ.
We assume PPP is true and show QQQ must be true.
Example 1:
Statement:
If nnn is even, then n2n^2n2 is even.
Proof:
Let n=2kn = 2kn=2k for some integer kkk.
Then n2=(2k)2=4k2=2(2k2)n^2 = (2k)^2 = 4k^2 = 2(2k^2)n2=(2k)2=4k2=2(2k2).
Since 2k22k^22k2 is an integer, n2n^2n2 is even. ✅
Hence, proved.
Example 2:
Prove: If two numbers are odd, their sum is even.
Let a=2m+1a = 2m + 1a=2m+1, b=2n+1b = 2n + 1b=2n+1.
Then a+b=2m+1+2n+1=2(m+n+1)a + b = 2m + 1 + 2n + 1 = 2(m + n +
1)a+b=2m+1+2n+1=2(m+n+1), which is even. ✅
✅ When to Use:
When the hypothesis directly leads to conclusion using definitions or algebra.
🔹 2. Proof by Contrapositive
Concept:
Instead of proving P⇒QP \Rightarrow QP⇒Q, we prove its contrapositive form:
¬Q⇒¬P\neg Q \Rightarrow \neg P¬Q⇒¬P
Both are logically equivalent.
Example 1:
Statement:
If n2n^2n2 is even, then nnn is even.
Proof (by contrapositive):
Contrapositive is:
If nnn is odd, then n2n^2n2 is odd.
Let n=2k+1n = 2k + 1n=2k+1
Then n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) +
1n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1
→ Odd ✅
Hence, original statement true.
✅ When to Use:
When direct proof seems hard but the opposite direction is simpler.
🔹 3. Proof by Contradiction
Concept:
We assume the statement is false, and show that this leads to a contradiction (impossible
situation).
Thus, the statement must be true.
Example 1:
Statement:
√2 is irrational.
Proof:
Assume √2 is rational, i.e.,
2=pq where p,q integers with no common factor.\sqrt{2} = \frac{p}{q} \text{ where } p,q \
text{ integers with no common factor.}2=qp where p,q integers with no common factor.
Then 2=p2q22 = \frac{p^2}{q^2}2=q2p2 → p2=2q2p^2 = 2q^2p2=2q2.
So p2p^2p2 is even → ppp is even → p=2kp=2kp=2k.
Substitute: (2k)2=2q2⇒4k2=2q2⇒q2=2k2.(2k)^2 = 2q^2 \Rightarrow 4k^2 = 2q^2 \Rightarrow
q^2 = 2k^2.(2k)2=2q2⇒4k2=2q2⇒q2=2k2.
Both even ⇒ common factor 2 — contradiction! ❌
So qqq is also even.
Hence, √2 is irrational ✅
✅ When to Use:
When statement denies an impossible case (common for irrationality, infiniteness proofs, etc.).
🔹 4. Proof by Cases
Concept:
Divide the proof into separate cases covering all possibilities.
Example:
Prove: For any integer nnn, n2≥0.n^2 \geq 0.n2≥0.
Proof:
Case 1: n=0n = 0n=0 → n2=0.n^2 = 0.n2=0.
Case 2: n>0n > 0n>0 → n2>0.n^2 > 0.n2>0.
Case 3: n<0n < 0n<0 → n2=(−n)2>0.n^2 = (-n)^2 > 0.n2=(−n)2>0.
In all cases, n2≥0.n^2 \ge 0.n2≥0. ✅
✅ When to Use:
When multiple scenarios exist (e.g., even/odd, positive/negative).
🔹 5. Proof by Mathematical Induction
Concept:
Used for statements involving natural numbers nnn.
We prove the statement P(n)P(n)P(n) is true for all n ≥ k.
Steps:
1. Base Case:
Show P(k)P(k)P(k) is true.
2. Inductive Hypothesis:
Assume P(n)P(n)P(n) is true for some nnn.
3. Inductive Step:
Show P(n+1)P(n+1)P(n+1) is true using hypothesis.
Example 1:
Prove: 1+2+3+…+n=n(n+1)21 + 2 + 3 + … + n = \frac{n(n+1)}{2}1+2+3+…+n=2n(n+1)
Proof:
1️⃣ Base Case:
For n=1n=1n=1:
LHS = 1, RHS = 1(1+1)2=1\frac{1(1+1)}{2} = 121(1+1)=1. ✅
2️⃣ Inductive Hypothesis:
Assume for n=kn=kn=k:
1+2+…+k=k(k+1)21 + 2 + … + k = \frac{k(k+1)}{2}1+2+…+k=2k(k+1)
3️⃣ Inductive Step:
For n=k+1n=k+1n=k+1:
1+2+…+k+(k+1)=k(k+1)2+(k+1)1 + 2 + … + k + (k+1) = \frac{k(k+1)}{2} + (k+1)1+2+…+k+
(k+1)=2k(k+1)+(k+1) =(k+1)(k2+1)=(k+1)(k+22)=(k+1)(k+2)2= (k+1)(\frac{k}{2} + 1) = (k+1)
(\frac{k+2}{2}) = \frac{(k+1)(k+2)}{2}=(k+1)(2k+1)=(k+1)(2k+2)=2(k+1)(k+2)
✅ Hence true for n=k+1n=k+1n=k+1.
By induction, true for all n≥1n \ge 1n≥1.
✅ When to Use:
Whenever the problem involves sequences, recurrence, or patterns over natural numbers.
🔹 6. Proof by Counterexample
Concept:
To disprove a statement, one counterexample is enough.
Example:
Statement: “All prime numbers are odd.”
Counterexample: 2 is prime and even. ❌
Hence, statement is false.
✅ When to Use:
When the claim is universal (like “for all x”), and you just need one example to disprove it.
🔹 7. Constructive & Non-Constructive Proofs
Constructive Proof:
You construct an actual example to show existence.
Example:
“There exists an even prime number.” → Construct example: 2 ✅
Non-Constructive Proof:
You show existence logically without giving a specific example.
Example:
“There exist irrational numbers a and b such that aba^bab is rational.”
Proof exists logically, but example not directly built.
🧩 Practice Questions on Proof Techniques
1. Prove: If nnn is odd, then n2n^2n2 is odd.
2. Prove by contrapositive: If 3n+23n + 23n+2 is even, then nnn is even.
3. Use contradiction to prove that there is no smallest positive rational number.
4. Use induction to prove 2n>n22^n > n^22n>n2 for n≥5n ≥ 5n≥5.
5. Disprove: “Every function from N to N is one-one.”