← Back to Mathematical Logic, Set Theory and Combinatorics
Course: MAT1MN104 — Mathematical Logic, Set Theory and Combinatorics Hours: 12 | Textbook Sections: 2.1, 2.2, 2.4 (Thomas Koshy, Discrete Mathematics with Applications, 1/e)
Notation (Koshy’s convention): complement $A’$ (prime, not $A^c$), cardinality $|A|$, power set $P(A)$, empty set $\emptyset$ or $\{\}$.
1. The Concept of a Set
A set is a well-defined collection of distinct objects (elements/members). $x \in A$ means x is an element of A; $x \notin A$ otherwise.
- Roster method: list elements, e.g. $B = \{VT, RI, MA, CT, NH, ME\}$. Order doesn’t matter; repeats aren’t counted twice: $\{x,x,y,x,y,z\} = \{x,y,z\}$.
- Set-builder notation: $\{x \mid P(x)\}$ — “the set of all x such that P(x)”. The $\mid$ means “such that”.
Example. B = set of months with exactly 30 days = $\{x \mid x \text{ is a month with 30 days}\} = \{Sept, April, June, Nov\}$.
1.1 Subsets, Equal Sets, Power Sets
- Subset: $A \subseteq B$ iff every element of A is in B: $(A \subseteq B) \leftrightarrow (\forall x)(x \in A \to x \in B)$. Also written $B \supseteq A$.
- Not a subset: $A \not\subseteq B \leftrightarrow (\exists x)(x \in A \land x \notin B)$.
- Equal sets: $A = B \leftrightarrow (A \subseteq B) \land (B \subseteq A)$.
- Proper subset: $A \subset B$ if $A \subseteq B$ and $A \neq B$.
To prove $X \subseteq Y$: take an arbitrary $x \in X$, show $x \in Y$. To prove $X \not\subseteq Y$: exhibit one element of X not in Y.
Example. A = US states, B = New England states, C = Canadian provinces. $B \subseteq A$, but $B \not\subseteq C$ and $A \not\subseteq C$.
- Empty/null set: $\emptyset$ or $\{\}$ — no elements. $\emptyset \subseteq A$ for every A; there is exactly one empty set.
- Universal set U: chosen so every set under discussion is a subset of U.
- Power set $P(A)$: the set of all subsets of A (including $\emptyset$ and A itself).
⚠️ $\{\emptyset\} \neq \emptyset$ — the left side has one element ($\emptyset$ itself); the right has none.
Worked example. $P(A)$ for $A = \{a, b\}$: $P(A) = \{\emptyset, \{a\}, \{b\}, \{a,b\}\}$. Note $|P(A)| = 4 = 2^{|A|}$.
Venn diagrams: rectangle = U, circles = sets. $A \subseteq B$ drawn as circle A entirely inside circle B.
1.2 Finite and Infinite Sets
A set A is finite if it has exactly n elements for some non-negative integer n (n = $|A|$, its cardinality); otherwise infinite. Example: $\{1,3,5,\ldots,99\}$ is finite ($|A|=50$); $\mathbb{N}$, $\mathbb{Z}$ are infinite.
Optional / Not Examined — Hilbert’s Hotel. A hotel with infinitely many rooms (1, 2, 3, …), all occupied, can still fit one more guest: shift everyone from room $n$ to room $n+1$, freeing room 1. It can even fit infinitely many new guests: shift room $n$ to room $2n$, freeing all odd rooms. This paradox (David Hilbert) shows infinite sets behave very differently from finite ones — a preview of countable/uncountable infinity, beyond this course’s scope.
(Exam scope: Section 2.1 examinable through Example 2.7 / power sets; Example 2.6 and everything from Hilbert’s Hotel onward is optional/non-examined.)
2. Operations with Sets
Set operations mirror logical connectives exactly: intersection ↔ “and”, union ↔ “or”.
| Operation | Definition |
|---|---|
| Union | $A \cup B = \{x \mid x \in A \lor x \in B\}$ |
| Intersection | $A \cap B = \{x \mid x \in A \land x \in B\}$. Disjoint if $A \cap B = \emptyset$. |
| Difference | $A - B = \{x \in A \mid x \notin B\}$ |
| Complement | $A’ = U - A = \{x \in U \mid x \notin A\}$ |
| Symmetric difference | $A \oplus B = (A \cup B) - (A \cap B)$ |
Example. $A=\{Nov,Dec,Jan,Feb\}$, $B=\{Feb,Mar,Apr,May\}$, $C=\{Sept,Oct,Nov,Dec\}$. $A\cap B=\{Feb\}$. $B\cap C=\emptyset=C\cap B$ → B, C disjoint.
Worked example. $A=\{a..z,0..9\}$, $B=\{0..9\}$. $A-B=\{a..z\}$, $B-A=\emptyset$. Note $A-B \neq B-A$ in general.
Worked example (distributive law check). $A=\{a,b,c,d,g\}$, $B=\{b,c,d,e,f\}$, $C=\{b,c,e,g,h\}$.
\[\begin{aligned} B\cap C &= \{b,c,e\} \\ A\cup(B\cap C) &= \{a,b,c,d,e,g\} \\ A\cup B &= \{a,b,c,d,e,f,g\}, \quad A\cup C = \{a,b,c,d,e,g,h\} \\ (A\cup B)\cap(A\cup C) &= \{a,b,c,d,e,g\} = A\cup(B\cap C) \quad \checkmark \end{aligned}\]2.1 The 24 Laws of Sets (Koshy’s Table 2.2)
| Law | Statement |
|---|---|
| Idempotent | $A\cup A=A$ $A\cap A=A$ |
| Identity | $A\cup\emptyset=A$ $A\cap U=A$ |
| Inverse | $A\cup A’=U$ $A\cap A’=\emptyset$ |
| Domination | $A\cup U=U$ $A\cap\emptyset=\emptyset$ |
| Commutative | $A\cup B=B\cup A$ $A\cap B=B\cap A$ |
| Double complementation | $(A’)’=A$ |
| Associative | $A\cup(B\cup C)=(A\cup B)\cup C$ $A\cap(B\cap C)=(A\cap B)\cap C$ |
| Distributive | $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 | $(A\cup B)’=A’\cap B’$ $(A\cap B)’=A’\cup B’$ |
| Absorption | $A\cup(A\cap B)=A$ $A\cap(A\cup B)=A$ |
| (unnamed, if A⊆B) | $A\cap B=A$ $A\cup B=B$ $B’\subseteq A’$ |
| Difference identity | $A-B=A\cap B’$ |
| Symmetric difference | $A\oplus B=(A\cup B)-(A\cap B)$ |
Key parallel: $\cup\leftrightarrow\lor$, $\cap\leftrightarrow\land$, $’\leftrightarrow\sim$, $\emptyset\leftrightarrow f$, $U\leftrightarrow t$. If you know the laws of logic, you know the laws of sets.
Worked example (proof). Prove $A’\cap B’ \subseteq (A\cup B)’$. Let $x \in A’\cap B’$. Then $x\notin A$ and $x\notin B$, so by De Morgan’s law (logic), $x\notin(A\cup B)$, i.e. $x\in(A\cup B)’$. Since x was arbitrary, done.
Worked example (simplification, Oct 2024 paper). Simplify $(A\cap B’) \cup (A’\cap B) \cup (A’\cap B’)$:
\[\begin{aligned} &(A\cap B') \cup [A'\cap(B\cup B')] && [\text{distributive}] \\ &= (A\cap B') \cup (A'\cap U) && [\text{inverse law}] \\ &= (A\cap B') \cup A' && [\text{identity law}] \\ &= (A\cup A') \cap (B'\cup A') && [\text{distributive}] \\ &= U \cap (A'\cup B') && [\text{inverse law}] \\ &= A'\cup B' = (A\cap B)' && [\text{identity, De Morgan}] \end{aligned}\]2.2 The Cartesian Product
$A \times B = \{(a,b) \mid a \in A \land b \in B\}$ — the set of all ordered pairs. $A \times A$ is written $A^2$. Named after Descartes.
Example. $A=\{a,b\}$, $B=\{x,y,z\}$: $A\times B = \{(a,x),(a,y),(a,z),(b,x),(b,y),(b,z)\}$; $B\times A = \{(x,a),\ldots\}$. Note $A\times B \neq B\times A$.
⚠️ $|A\times B| = |A|\cdot|B|$, not $|A|+|B|$ — same “multiply for sequential choices” idea as the Fundamental Counting Principle (Module IV).
(Exam scope: Section 2.2 examinable through Example 2.21 plus Cartesian product; fuzzy sets/operations are optional/non-examined.)
3. The Cardinality of a Set
For finite sets A, B: $|A \cup B| = |A| + |B| - |A \cap B|$.
For three finite sets (inclusion–exclusion):
\[|A\cup B\cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|\]Why the +,−,+ pattern? Adding $|A|+|B|+|C|$ over-counts elements in 2 sets (counted twice) and elements in all 3 (counted thrice). Subtracting pairwise intersections fixes the double-count but removes the triple-overlap element too many times, so it must be added back once.
Worked example (2 sets, Oct 2024). $|A|=3$, $|B|=5$, $|A\cap B|=2$ → $|A\cup B| = 3+5-2 = 6$.
Worked example (3 sets, Oct 2024). $|A|=10,|B|=15,|C|=20,|A\cap B|=5,|A\cap C|=4,|B\cap C|=3,|A\cap B\cap C|=2$ → $|A\cup B\cup C| = 10+15+20-5-4-3+2 = 35$.
Worked example (Oct 2024). Positive integers ≤ 3000 not divisible by 7 or 8: A = multiples of 7 ($\lfloor 3000/7 \rfloor=428$), B = multiples of 8 ($\lfloor 3000/8 \rfloor=375$), $A\cap B$ = multiples of $\text{lcm}(7,8)=56$ ($\lfloor 3000/56 \rfloor=53$). $|A\cup B| = 428+375-53 = 750$. Answer: $3000-750 =$ 2250.
Optional / Not Examined — Counting subsets (Theorem 2.2). A set with $n$ elements has $2^n$ subsets. Idea: let $s_n$ = number of subsets of an $n$-element set $S$; remove one element $x$ to get $S^$ with $n-1$ elements and $s_{n-1}$ subsets. Every subset of $S^$ is a subset of $S$; adding $x$ to each gives another $s_{n-1}$ subsets containing $x$. So $s_n = 2s_{n-1}$, giving $s_n = 2^n$. The formula $|P(A)| = 2^{|A|}$ is worth remembering; the proof itself is not examined.
(Exam scope: 2-set and 3-set cardinality are squarely examinable and appeared repeatedly on the Oct 2024 paper.)
4. Optional / Not Examined — Relations and Digraphs (Module V)
With the Cartesian product available, we can formalise “a relationship between elements of two sets”:
- A relation R from A to B is a subset of A × B: $R \subseteq A \times B$. If $(a,b) \in R$ write $aRb$. A relation from A to A is a relation on A.
- Example. $A=\{1,2,3\}$, $aRb$ iff $a \le b$: $R = \{(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\}$.
- Digraph: draw each element as a vertex; draw an arrow a→b whenever aRb.
- Properties on A: R is reflexive if $aRa$ for all $a$; symmetric if $aRb \Rightarrow bRa$; transitive if $aRb$ and $bRc \Rightarrow aRc$. Reflexive + symmetric + transitive = equivalence relation (partitions A into groups of “equivalent” elements).
This is part of the syllabus’s open-ended Module V and is not externally examined, but follows directly from the Cartesian product above.
Chapter Summary
- Set described by roster or set-builder notation; $A \subseteq B$, $A \subset B$, $A = B$, $\emptyset$, $U$, $P(A)$.
- Operations: $\cup, \cap, -, {}’$ (=$U-A$), $\oplus$; governed by 24 laws mirroring the laws of logic.
- Cartesian product: $A\times B$, $|A\times B| = |A||B|$.
- Cardinality: $|A\cup B| = |A|+|B|-|A\cap B|$; inclusion–exclusion for 3 sets; $|P(A)| = 2^{|A|}$.
- Module V: relations $R \subseteq A\times B$, digraphs, reflexive/symmetric/transitive.
Practice Problems
- Write $\{x \mid x \text{ is a letter in “MALAYALAM”}\}$ using the roster method.
- $A=\{a,b,x,y,z\}$, $B=\{c,d,e,x,y,z\}$, $U=\{a,b,c,d,e,w,x,y,z\}$. Find $(A\cup B)’$ and $A’\cap B’$. What do you notice?
- Find $P(A)$ for $A=\{1,2,3\}$. How many elements?
- $A=\{1,2\}$, $B=\{a,b,c\}$. List $A\times B$ and $B\times A$. Equal as sets?
- Simplify $(A\cap B’) \cup (A’\cap B’) \cup (A\cap B)$ using the laws of sets.
- $|A|=3$, $|B|=5$, $|A\cap B|=2$. Find $|A\cup B|$ and $|A\times B|$.
- Construct your own three-set inclusion-exclusion word problem (100 students, three subjects) and solve it.
- Prove $A\cap B \subseteq A$ using an arbitrary-element argument (not a Venn diagram).
- Find the number of positive integers ≤ 2000 divisible by neither 5 nor 9.
- Give a relation on $A=\{1,2,3,4\}$ that is symmetric but not reflexive; draw its digraph.
- Give a relation on $A=\{1,2,3\}$ that is reflexive and transitive but not symmetric; say which equivalence axiom fails.
- Using the laws of sets, show $A-(B\cup C) = (A-B)\cap(A-C)$.