Unit 3 - Notes

MTH401

Unit 3: Counting Principles and Relations

1. Counting Principles

1.1 The Principle of Inclusion-Exclusion (PIE)

The Principle of Inclusion-Exclusion provides a method for determining the cardinality (size) of the union of finite sets. It accounts for over-counting when sets overlap.

For Two Sets:
If $A$ and $B$ are finite sets, the number of elements in their union is:

|A \cup B| = |A| + |B| - |A \cap B|

For Three Sets:

|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|

General Formula (for $n$ sets):
To find the cardinality of the union of $n$ sets $A_1, A_2, ..., A_n$ :

Sum the cardinalities of the individual sets.
Subtract the cardinalities of the intersections of every pair of sets.
Add the cardinalities of the intersections of every triple of sets.
Subtract the intersections of every quadruple, and so on, alternating signs.

\left| \bigcup_{i=1}^n A_i \right| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} |A_1 \cap \dots \cap A_n|

1.2 The Pigeonhole Principle

Basic Principle:
If $k+1$ or more objects (pigeons) are placed into $k$ boxes (pigeonholes), then there is at least one box containing two or more objects.

Formal Statement: If a function $f: A \to B$ is defined where $|A| > |B|$ , then $f$ is not injective (one-to-one).
Example: In a group of 13 people, at least two must have been born in the same month.

The Generalized Pigeonhole Principle:
If $N$ objects are placed into $k$ boxes, then there is at least one box containing at least $\lceil N/k \rceil$ objects.
(Where $\lceil x \rceil$ is the ceiling function, representing the smallest integer greater than or equal to $x$ .)

Application: Useful for determining the worst-case scenario required to guarantee a specific outcome.
Example: How many cards must be selected from a standard deck of 52 to guarantee at least 3 cards of the same suit?
- $k = 4$ (suits). We want the box to contain 3.
- Formula: $\lceil N/4 \rceil \ge 3$ .
- If we pick 8 cards, $\lceil 8/4 \rceil = 2$ (not guaranteed).
- If we pick 9 cards, $\lceil 9/4 \rceil = 3$ . Answer: 9 cards.

2. Relations and Their Properties

2.1 Definition

Let $A$ and $B$ be sets. A binary relation $R$ from $A$ to $B$ is a subset of the Cartesian product $A \times B$ .

If $(a, b) \in R$ , we write $aRb$ (a is related to b).
If $A = B$ , we say $R$ is a relation on set $A$ .

2.2 Properties of Relations on a Set $A$

Reflexive: .
- Every element is related to itself.
- Matrix diagonal contains only 1s. Graph has self-loops on every node.
Irreflexive: .
- No element is related to itself.
Symmetric: , if , then .
- Matrix is symmetric ( $M_{ij} = M_{ji}$ ). Graph edges are bidirectional (or undirected).
Antisymmetric: , if and , then .
- There is no pair of distinct elements related to each other in both directions.
- Note: Antisymmetric is not the opposite of Symmetric. A relation can be neither, or both (e.g., equality).
Transitive: , if and , then .
- "Shortcuts" exist in the graph.

2.3 Combining Relations

Since relations are sets (subsets of $A \times B$ ), standard set operations apply. Let $R_1$ and $R_2$ be relations from $A$ to $B$ :

Union: $R_1 \cup R_2$
Intersection: $R_1 \cap R_2$
Difference: $R_1 - R_2$
XOR: $R_1 \oplus R_2$

2.4 Composition of Relations

Let $R$ be a relation from $A$ to $B$ , and $S$ be a relation from $B$ to $C$ . The composition of $S$ and $R$ , denoted $S \circ R$ , is a relation from $A$ to $C$ .

S \circ R = \{ (a, c) \mid \exists b \in B \text{ such that } (a, b) \in R \text{ and } (b, c) \in S \}

Order matters: $S \circ R$ means $R$ is applied first, then $S$ .
Powers of a Relation: $R^n$ is the composition of $R$ with itself $n$ times. $R^1 = R$ , $R^2 = R \circ R$ , etc. A relation is transitive if and only if $R^n \subseteq R$ for all $n \ge 1$ .

2.5 Inverse Relation

The inverse of relation $R$ , denoted $R^{-1}$ , swaps the order of elements:

R^{-1} = \{ (b, a) \mid (a, b) \in R \}

3. Representing Relations

3.1 Zero-One Matrices

Let $A = \{a_1, ..., a_m\}$ and $B = \{b_1, ..., b_n\}$ . A relation $R$ can be represented by an $m \times n$ matrix $M_R = [m_{ij}]$ where:

$m_{ij} = 1$ if $(a_i, b_j) \in R$
$m_{ij} = 0$ if $(a_i, b_j) \notin R$

Matrix Operations corresponding to Relations:

Union: $M_{R_1 \cup R_2} = M_{R_1} \lor M_{R_2}$ (element-wise Boolean OR)
Intersection: $M_{R_1 \cap R_2} = M_{R_1} \land M_{R_2}$ (element-wise Boolean AND)
Composition: (Boolean Matrix Product)
- Boolean product replaces multiplication with AND, and addition with OR.

3.2 Directed Graphs (Digraphs)

For a relation on set $A$ :

Vertices (Nodes): Elements of $A$ .
Edges (Arcs): An arrow from $a$ to $b$ exists if $(a, b) \in R$ .

Visualizing Properties in Digraphs:

Reflexive: Loop at every vertex.
Symmetric: If an arrow goes $a \to b$ , one must go $b \to a$ .
Antisymmetric: If $a \to b$ exists (and $a \neq b$ ), $b \to a$ cannot exist.
Transitive: If $a \to b$ and $b \to c$ , there must be an arrow $a \to c$ .

4. Equivalence Relations

4.1 Definition

A relation $R$ on a set $A$ is an Equivalence Relation if it satisfies three properties:

Reflexive
Symmetric
Transitive

Example:

The relation "is equal to" ( $=$ ) on integers.
The relation "congruence modulo $m$ " on integers ( $a \equiv b \pmod m$ ).
The relation "lives in the same house as" on a set of people.

4.2 Equivalence Classes

Let $R$ be an equivalence relation on $A$ . The equivalence class of an element $a \in A$ , denoted $[a]_R$ (or simply $[a]$ ), is the set of all elements related to $a$ :

[a]_R = \{ s \mid (a, s) \in R \}

Representative: Any element $b \in [a]_R$ is called a representative of the class.

4.3 Partitions

Equivalence classes split the set $A$ into disjoint subsets.

The union of all equivalence classes is $A$ .
The intersection of any two distinct equivalence classes is empty.
Theorem: An equivalence relation induces a partition on a set, and conversely, any partition of a set induces an equivalence relation.

5. Partial and Total Ordering

5.1 Partial Ordering (Poset)

A relation $R$ on set $S$ is a Partial Ordering if it is:

Reflexive
Antisymmetric
Transitive

The pair $(S, R)$ is called a Partially Ordered Set or POSET. The symbol $\preceq$ is often used for the relation.

Examples:

$(\mathbb{Z}, \le)$ : Integers with "less than or equal to".
$(P(S), \subseteq)$ : Power set of $S$ with "subset of".
$(\mathbb{Z}^+, |)$ : Positive integers with "divides".

5.2 Comparability

In a poset $(S, \preceq)$ :

Two elements $a, b$ are comparable if either $a \preceq b$ or $b \preceq a$ .
They are incomparable if neither holds.

5.3 Total Ordering (Linear Ordering)

If $(S, \preceq)$ is a poset and every pair of elements in $S$ is comparable, it is a Total Ordering (or Totally Ordered Set / Chain).

Example: $(\mathbb{Z}, \le)$ is a total order.
Counter-example: $(\mathbb{Z}^+, |)$ is not a total order (e.g., 2 and 3 are incomparable).

6. Hasse Diagrams

A Hasse diagram is a simplified graphical representation of a finite Poset.

6.1 Construction Algorithm

To convert the digraph of a poset to a Hasse diagram:

Remove Loops: Since posets are reflexive, loops at vertices are implied.
Remove Transitive Edges: If $a \to b$ and $b \to c$ , remove $a \to c$ (transitivity is implied).
Orientation: Arrange elements so that if $a \preceq b$ , then $b$ is drawn higher than $a$ .
Remove Arrows: Replace directed edges with line segments. The upward direction indicates the relation.

6.2 Components and Terminology of Posets/Hasse Diagrams

Let $(S, \preceq)$ be a poset and $A \subseteq S$ .

Maximal Element: An element $m \in S$ such that no element comes "after" it. (There is no $x \in S$ where $m \preceq x$ and $m \neq x$ ). There can be multiple maximal elements.
Minimal Element: An element $m \in S$ such that no element comes "before" it.
Greatest Element (Maximum): A unique element $g \in S$ such that $a \preceq g$ for all $a \in S$ . (Top of the diagram connected to everything). Not all posets have one.
Least Element (Minimum): A unique element $l \in S$ such that $l \preceq a$ for all $a \in S$ . (Bottom of the diagram).
Upper Bound: An element $u \in S$ is an upper bound of subset $A$ if $a \preceq u$ for all $a \in A$ .
Lower Bound: An element $l \in S$ is a lower bound of subset $A$ if $l \preceq a$ for all $a \in A$ .
Least Upper Bound (LUB / Supremum): The smallest of all upper bounds.
Greatest Lower Bound (GLB / Infimum): The largest of all lower bounds.

7. Lattices

7.1 Definition

A Lattice is a specific type of Poset $(L, \preceq)$ in which every pair of elements $a, b \in L$ has both:

A Least Upper Bound (LUB), denoted $a \lor b$ (called the Join).
A Greatest Lower Bound (GLB), denoted $a \land b$ (called the Meet).

Note: The symbols $\lor$ and $\land$ here refer to Join and Meet operations, not logical OR/AND, though they behave similarly in Boolean algebra lattices.

7.2 Properties of Lattices

For any $a, b, c \in L$ :

Commutative: $a \lor b = b \lor a$ and $a \land b = b \land a$ .
Associative: $a \lor (b \lor c) = (a \lor b) \lor c$ .
Absorption Laws:
- $a \lor (a \land b) = a$
- $a \land (a \lor b) = a$
Idempotent: $a \lor a = a$ and $a \land a = a$ .

7.3 Sub-Lattice

A subset $M$ of a lattice $L$ is a sub-lattice if $M$ is closed under the meet and join operations defined in $L$ .

Meaning: For any $a, b \in M$ , their join ( $a \lor b$ ) and meet ( $a \land b$ ) (as calculated in the original lattice $L$ ) must also be present in $M$ .

7.4 Types of Lattices (Brief Overview)

Bounded Lattice: Has a Greatest element ($1$ or $I$ ) and a Least element ($0$ or $O$ ).
Complemented Lattice: A bounded lattice where every element $a$ has a complement $a'$ such that $a \lor a' = 1$ and $a \land a' = 0$ .
Distributive Lattice: Distributive laws hold (e.g., $a \land (b \lor c) = (a \land b) \lor (a \land c)$ ).