Practice MCQ

Unit 1 - Notes

MTH265 9 min read

Unit 1: Relations

1. Introduction to Relations

In discrete mathematics, a relation is a fundamental concept used to describe an association or connection between elements of two sets.

Basic Definitions

Cartesian Product: The Cartesian product of two sets and , denoted as , is the set of all possible ordered pairs where and .
- $A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}$
Binary Relation: A binary relation from a set to a set is a subset of the Cartesian product .
- $R \subseteq A \times B$
- If $(a, b) \in R$ , we say that " $a$ is related to $b$ by $R$ ", often written as $aRb$ .
- If $(a, b) \notin R$ , we write $a \cancel{R} b$ .
Relation on a Set: A relation from a set $A$ to itself (i.e., a subset of $A \times A$ ) is simply called a "relation on $A$ ".
Domain and Range:
- Domain: The set of all first elements $a$ of the ordered pairs in $R$ .
- Range (or Image): The set of all second elements $b$ of the ordered pairs in $R$ .

Representation of Relations

Relations can be represented in multiple ways:

Set Roster Notation: Listing the ordered pairs, e.g., $R = \{(1,2), (2,3), (3,1)\}$ .
Matrix Representation (Zero-One Matrix): If $A$ has $m$ elements and $B$ has $n$ elements, $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$ and $0$ otherwise.
Directed Graph (Digraph): For a relation on a single set $A$ , elements are represented as vertices (nodes), and ordered pairs $(a,b) \in R$ are represented as directed edges (arrows) pointing from $a$ to $b$ .

2. Types of Relations

Relations on a set $A$ are categorized based on the properties they exhibit. Let $R$ be a relation on a set $A$ .

Reflexive Relations

A relation $R$ on a set $A$ is reflexive if every element in $A$ is related to itself.

Formal Definition: $\forall a \in A, (a, a) \in R$ .
Matrix View: The main diagonal of the matrix $M_R$ consists entirely of 1s.
Digraph View: Every vertex has a self-loop.
Example: Let $A = \{1, 2, 3\}$ . $R = \{(1,1), (2,2), (3,3), (1,2)\}$ is reflexive. $R' = \{(1,1), (2,2), (1,2)\}$ is not reflexive because $(3,3) \notin R'$ .
Note: Do not confuse with Irreflexive. A relation is irreflexive if $\forall a \in A, (a, a) \notin R$ (no element is related to itself).

Symmetric Relations

A relation $R$ on a set $A$ is symmetric if for every pair $(a, b)$ in $R$ , the reverse pair $(b, a)$ is also in $R$ .

Formal Definition: $\forall a, b \in A$ , if $(a, b) \in R \implies (b, a) \in R$ .
Matrix View: The matrix is symmetric ( $M_R = M_R^T$ ).
Digraph View: Every directed edge between two distinct vertices has an edge going in the opposite direction.
Example: Let $A = \{1, 2, 3\}$ . $R = \{(1,2), (2,1), (3,3)\}$ is symmetric.

Antisymmetric Relations

A relation $R$ on a set $A$ is antisymmetric if there are no distinct elements $a$ and $b$ such that $a$ is related to $b$ and $b$ is related to $a$ .

Formal Definition: $\forall a, b \in A$ , if $(a, b) \in R$ and $(b, a) \in R \implies a = b$ .
Matrix View: For $i \neq j$ , if $m_{ij} = 1$ , then $m_{ji} = 0$ . (The matrix never has a 1 across the diagonal from another 1).
Digraph View: There are no two-way directed edges between distinct vertices.
Example: The "less than or equal to" ( $\leq$ ) relation on the set of integers. If $x \leq y$ and $y \leq x$ , then $x$ must equal $y$ .
Note: "Antisymmetric" is NOT the opposite of "Symmetric". A relation can be both (e.g., equality relation) or neither.

Transitive Relations

A relation $R$ on a set $A$ is transitive if whenever $a$ is related to $b$ , and $b$ is related to $c$ , then $a$ is related to $c$ .

Formal Definition: $\forall a, b, c \in A$ , if $(a, b) \in R$ and $(b, c) \in R \implies (a, c) \in R$ .
Matrix View: If $M_R^2$ has a non-zero entry at $(i, j)$ , then $M_R$ must have a 1 at $(i, j)$ .
Digraph View: If there is a path from vertex $x$ to $y$ and a path from $y$ to $z$ , there must be a direct edge from $x$ to $z$ .
Example: Let $A = \{1, 2, 3\}$ . $R = \{(1,2), (2,3), (1,3)\}$ is transitive. The relation "divides" ( $a \mid b$ ) on the set of positive integers is transitive.

3. Closure Properties of Relations

If a relation $R$ lacks a certain property (reflexivity, symmetry, or transitivity), we can add the minimum number of ordered pairs to make it possess that property. This new, expanded relation is called a closure.

Formally, the closure of $R$ with respect to a property $P$ is the smallest relation $S$ that contains $R$ and has property $P$ .

Reflexive Closure

To find the reflexive closure of $R$ , add all pairs $(a, a)$ for every element $a \in A$ that are not already in $R$ .

Formula: $S = R \cup \Delta$ , where $\Delta = \{(a,a) \mid a \in A\}$ (the diagonal relation).
Example: $A = \{1, 2\}$ , $R = \{(1, 2)\}$ . Reflexive closure $= \{(1, 2), (1, 1), (2, 2)\}$ .

Symmetric Closure

To find the symmetric closure of $R$ , add the reverse of every ordered pair in $R$ .

Formula: $S = R \cup R^{-1}$ , where $R^{-1} = \{(b, a) \mid (a, b) \in R\}$ (the inverse relation).
Example: $A = \{1, 2, 3\}$ , $R = \{(1, 2), (2, 3)\}$ . Symmetric closure $= \{(1, 2), (2, 1), (2, 3), (3, 2)\}$ .

Transitive Closure

Finding the transitive closure is more complex because adding a pair to satisfy transitivity might create new chains that require even more pairs.

Definition: The transitive closure of $R$ , often denoted $R^*$ , is the connectivity relation. It contains a pair $(a, b)$ if there is a path of any length from $a$ to $b$ in the digraph of $R$ .
Formula: $R^* = R \cup R^2 \cup R^3 \cup \dots \cup R^n$ (where $n$ is the cardinality of set $A$ ).
Algorithm: Warshall's Algorithm is an efficient computational method using matrices to compute the transitive closure of a relation.

4. Equivalence Relations

An equivalence relation is a relation that groups elements into categories where members of the same category share a specific common trait.

Definition

A relation $R$ on a set $A$ is an Equivalence Relation if and only if it is:

Reflexive
Symmetric
Transitive

Example: The "equals" ( $=$ ) relation is the prototypical equivalence relation.
Example: Congruence modulo $n$ . Let $A = \mathbb{Z}$ (integers). Define $a \equiv b \pmod n$ if $n$ divides $(a - b)$ . This relation is reflexive, symmetric, and transitive.

Equivalence Classes

If $R$ is an equivalence relation on a set $A$ , the equivalence class of an element $a \in A$ , denoted by $[a]_R$ or simply $[a]$ , is the set of all elements in $A$ that are related to $a$ .

Definition: $[a] = \{x \in A \mid (x, a) \in R\}$ .
Properties of Equivalence Classes:
1. $a \in [a]$ (because $R$ is reflexive).
2. If $aRb$ , then $[a] = [b]$ .
3. If $a \cancel{R} b$ , then $[a] \cap [b] = \emptyset$ .

5. Partitions

A partition is a way of dividing a set into non-overlapping "chunks" that collectively cover the entire set.

Definition

A partition of a set $A$ is a collection of non-empty subsets $A_1, A_2, \dots, A_k$ of $A$ such that:

Mutually Disjoint: $A_i \cap A_j = \emptyset$ for $i \neq j$ . (No two subsets overlap).
Exhaustive: $\bigcup_{i=1}^k A_i = A$ . (The union of all subsets equals the original set).

The Fundamental Theorem of Equivalence Relations

There is a direct, bijective relationship between equivalence relations and partitions:

If $R$ is an equivalence relation on $A$ , the set of all distinct equivalence classes of $R$ forms a partition of $A$ .
Conversely, given any partition of $A$ , there exists an equivalence relation $R$ on $A$ whose equivalence classes are exactly the subsets in the partition. (Two elements are related if they belong to the same subset).

6. Partial Ordering Relations

While equivalence relations abstract the concept of "equality," partial ordering relations abstract the concept of "hierarchy" or "sequence."

Definition

A relation $R$ on a set $A$ is a Partial Ordering (or partial order) if it is:

Reflexive
Antisymmetric
Transitive

Notation: A set $A$ together with a partial ordering $R$ is called a Partially Ordered Set or Poset, denoted by $(A, \preceq)$ .
Examples:
- The "less than or equal to" ( $\leq$ ) relation on the set of real numbers.
- The "subset" ( $\subseteq$ ) relation on the power set of a set.
- The "divides" ( $|$ ) relation on the set of positive integers.

Comparability and Total Order

Comparable Elements: In a poset $(A, \preceq)$ , two elements $a$ and $b$ are comparable if either $a \preceq b$ or $b \preceq a$ .
Incomparable Elements: If neither $a \preceq b$ nor $b \preceq a$ , they are incomparable. (This is why it's called a partial ordering).
Total Order (Linear Order): If every pair of elements in a poset is comparable, the relation is called a total ordering or linear ordering.
- Example: $(\mathbb{Z}, \leq)$ is a totally ordered set.
- Example: $(\mathbb{Z}^+, \mid)$ is only partially ordered because, for instance, neither $3 \mid 5$ nor $5 \mid 3$ is true.

Hasse Diagrams

A Hasse Diagram is a graphical representation of a poset. It simplifies the directed graph of the relation by removing redundant information.

How to construct a Hasse Diagram:
1. Start with the directed graph of the poset.
2. Remove all self-loops (implied by reflexivity).
3. Remove all transitive edges (e.g., if there is an edge from $a \to b$ and $b \to c$ , remove the edge $a \to c$ , as it's implied by transitivity).
4. Arrange the vertices so that all arrows point strictly upwards.
5. Remove the arrowheads (the upward direction is universally understood).
Elements in a Poset (Visible via Hasse Diagrams):
- Maximal element: An element that is not smaller than any other element (top-most nodes).
- Minimal element: An element that is not greater than any other element (bottom-most nodes).
- Greatest element: An element greater than all other elements (only one can exist).
- Least element: An element smaller than all other elements (only one can exist).

Unit 2

Unit 1 - Notes

Table of Contents

Unit 1: Relations

1. Introduction to Relations

Basic Definitions

Representation of Relations

2. Types of Relations

Reflexive Relations

Symmetric Relations

Antisymmetric Relations

Transitive Relations

3. Closure Properties of Relations

Reflexive Closure

Symmetric Closure

Transitive Closure

4. Equivalence Relations

Definition

Equivalence Classes

5. Partitions

Definition

The Fundamental Theorem of Equivalence Relations

6. Partial Ordering Relations

Definition

Comparability and Total Order

Hasse Diagrams