PGDDSA Study · Semester 1

PGD01C01

Module 1 · Set Theory, Relations and Combinatorics

Denumerable Sets and Partial Order Relations

Core Titles

Key headlines and terms for quick recall

Countable / Denumerable set — bijection with $\mathbb{N}$
Uncountable — no such bijection (e.g., $\mathbb{R}$ )
Cantor's diagonal argument
Partial order = reflexive + antisymmetric + transitive
Poset $(A, \le)$
Hasse diagram
Total order, Chain, Antichain
Maximal, Minimal, Greatest, Least elements

Basic Idea

What it is, why it matters, how it works

Denumerable sets

A set $A$ is denumerable (countably infinite) if there is a bijection $f : \mathbb{N} \to A$ .

Examples.

$\mathbb{N}, \mathbb{Z}, \mathbb{Q}$ are all denumerable.
$\mathbb{R}$ is uncountable (Cantor's diagonal argument).

Why $\mathbb{Q}$ is denumerable. Arrange fractions $p/q$ in a 2-D grid by $p$ and $q$ , then snake along diagonals — gives a list.

Partial order relations

A partial order $\le$ on $A$ is:

Reflexive: $a \le a$
Antisymmetric: $a \le b \text{ and } b \le a \Rightarrow a = b$
Transitive: $a \le b \text{ and } b \le c \Rightarrow a \le c$

$(A, \le)$ is called a poset.

Total order vs partial order

Total (linear) order: every pair is comparable — $\mathbb{N}$ with $\le$ .
Partial: some pairs incomparable — divisibility on positive integers, subset relation.

Hasse diagram

Drawing of a poset that omits reflexive and transitive edges. Bigger elements drawn higher.

Special elements

Maximal: no element strictly greater.
Greatest: greater than every other (unique if exists).
Chain: a totally-ordered subset.
Antichain: a subset of pairwise-incomparable elements.

Why this matters in Data Science

Topological sort uses posets. Concept hierarchies in data warehouses (region → country → continent) are posets. Lattice structures appear in formal concept analysis and clustering.

Mind Map

Visual structure of the concept

DENUMERABILITY
├── Bijection with ℕ ⇒ denumerable
├── ℕ, ℤ, ℚ countable
├── ℝ uncountable (Cantor diagonal)
└── A countable ⇔ finite ∨ denumerable

PARTIAL ORDERS
├── (Reflexive + Antisymmetric + Transitive)
├── Poset (A, ≤)
├── Examples
│   ├── (ℕ, |)        — divisibility
│   ├── (𝒫(X), ⊆)    — subsets
│   └── (ℝ, ≤)         — also total
├── Hasse Diagram
└── Elements
    ├── Maximal / Minimal
    ├── Greatest / Least
    ├── Chain (totally ordered)
    └── Antichain (incomparable)

Exam Q&A

Part A (2 marks) and Part B (20 marks) style questions

Part A (2 marks each)

Q1. Define a denumerable set. A set in bijection with $\mathbb{N}$ , the set of natural numbers.

Q2. Is $\mathbb{Q}$ denumerable? Why? Yes. The rationals can be listed by arranging $p/q$ in a 2-D grid and traversing diagonals.

Q3. Define a partial order. A relation that is reflexive, antisymmetric and transitive.

Q4. What is an antichain in a poset? A subset in which any two elements are incomparable.

Part B (20 marks)

Q. Show that the set of rational numbers is denumerable, but the set of real numbers in $(0,1)$ is not. Define a poset and draw the Hasse diagram of $\{1,2,3,4,6,12\}$ under divisibility.

Part 1 — $\mathbb{Q}$ is denumerable. Arrange positive rationals $p/q$ in an infinite grid where the row is $p$ and column is $q$ . Traverse along diagonals: $1/1, 1/2, 2/1, 1/3, 2/2, 3/1, \dots$ , skipping duplicates (e.g., $2/2 = 1/1$ ). This gives a one-to-one listing $f : \mathbb{N} \to \mathbb{Q}^+$ . Pair this with negatives and zero to enumerate all of $\mathbb{Q}$ . Hence $\mathbb{Q}$ is denumerable.

Part 2 — $(0,1) \subset \mathbb{R}$ is uncountable (Cantor). Suppose for contradiction it is denumerable: write all reals as $r_1, r_2, r_3, \dots$ in decimal form. Construct $r^* = 0.d_1 d_2 d_3 \dots$ where $d_i$ differs from the $i$ -th decimal of $r_i$ (avoiding 0 and 9 to dodge ambiguity). Then $r^*$ differs from every $r_i$ in at least one digit, so $r^* \notin$ the list — contradiction. Hence $(0,1)$ is uncountable. ∎

Part 3 — Poset. A set $A$ with a relation $\le$ that is reflexive, antisymmetric and transitive.

Hasse diagram of $\{1,2,3,4,6,12\}$ under " $a$ divides $b$ ":

        12
       /  \
      4    6
      |   / \
      2  3   (2 also divides 6)
       \ /
        1

1 is the least element (divides everything).
12 is the greatest.
$\{4, 6\}$ is an antichain (neither divides the other).
$1 \mid 2 \mid 4 \mid 12$ is a chain.

Relations, Equivalence Relations and Partitions Mathematical Induction