Sets and Relations

Overview

Welcome to the foundational chapter on Sets and Relations, the bedrock upon which much of Discrete Mathematics – and indeed, many advanced topics in Data Science – is built. This chapter is absolutely critical for your Masters in Data Science journey at CMI, as it equips you with the precise language and conceptual tools to formally define, manipulate, and reason about collections of objects (data points, entities) and the connections that exist between them. A strong grasp of these fundamentals is not merely academic; it's a prerequisite for understanding data structures, database theory, graph theory, and the theoretical underpinnings of algorithms and machine learning.

In the CMI context, proficiency in Sets and Relations will directly impact your ability to tackle problem-solving questions. You'll find these concepts permeating various exam topics, from defining sample spaces in probability and characterizing data structures to understanding graph connectivity and formalizing algorithmic logic. This chapter will enable you to describe complex systems with mathematical rigor, ensuring clarity and precision in your data science work.

By mastering the principles laid out here, you will develop the analytical rigor necessary to articulate problems, design solutions, and interpret results in a mathematically sound manner. This foundational knowledge will empower you to build robust models and algorithms, making it an indispensable part of your toolkit for success in both your coursework and future career.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Set Theory | Define, operate, and represent collections of items. |
| 2 | Relations | Model connections between elements within sets. |

---

Learning Objectives

---

Now let's begin with Set Theory...
## Part 1: Set Theory

Introduction

Set theory forms the bedrock of discrete mathematics, providing a fundamental language and framework for organizing, classifying, and reasoning about collections of objects. In the CMI Masters in Data Science curriculum, a solid grasp of set theory is indispensable. It underpins concepts in logic, relations, functions, graph theory, and probability, which are crucial for understanding algorithms, data structures, and statistical models. This unit covers the core definitions, operations, and principles of set theory, focusing on the cardinality of sets and the Principle of Inclusion-Exclusion, which are frequently tested in CMI examinations for their application in counting problems and data analysis scenarios.

---

---

Key Concepts

1. Basic Definitions and Notations

Sets can be described in two primary ways:

Roster Method: Listing all elements explicitly within curly braces.

Example: The set of even numbers less than 10 is $E = \{2, 4, 6, 8\}$.

Set-Builder Notation: Describing the properties that elements must satisfy.

Example: The set of all natural numbers less than 10 is $N = \{x \mid x \in \mathbb{N} \text{ and } x < 10\}$.

Worked Example:

Problem: Given the set $S = \{a, b, c\}$. Determine its power set.

Solution:

Step 1: Identify the elements of the set $S$.

Step 2: List all subsets, starting with the empty set and single-element subsets.

Step 3: List all two-element subsets.

Step 4: List the set itself (the three-element subset).

Step 5: Combine all identified subsets to form the power set.

Answer: The power set $P(S)$ has $2^3 = \boxed{8}$ elements, as listed above.

---

2. Set Operations

Properties of Set Operations:
Set operations follow several algebraic laws, analogous to arithmetic operations. Key ones include:

* Commutative Laws:

* Associative Laws:

* Distributive Laws:

* De Morgan's Laws:

These laws are fundamental for simplifying set expressions and proving identities.

---

3. Cardinality of Sets and Inclusion-Exclusion Principle

The cardinality of a set $A$, denoted by $|A|$, is the number of distinct elements in the set.

Other useful cardinality relations:

*

* (where $U$ is the universal set)
*
*

Worked Example:

Problem: In a class of 50 students, 30 like Math, 25 like Physics, and 10 like both. How many students like neither Math nor Physics?

Solution:

Step 1: Define the sets and given cardinalities.
Let $M$ be the set of students who like Math.
Let $P$ be the set of students who like Physics.
Universal set $U$ is the class of students.

Step 2: Use the Inclusion-Exclusion Principle to find the number of students who like Math or Physics (or both).

Step 3: Find the number of students who like neither Math nor Physics by taking the complement of $(M \cup P)$ with respect to the universal set.

Answer: $\boxed{5}$ students like neither Math nor Physics.

---

---

4. Venn Diagrams

Venn diagrams are visual representations of sets and their relationships, typically using overlapping circles within a rectangle representing the universal set. They are incredibly useful for visualizing set operations and understanding the regions corresponding to different combinations of sets.

U

A
B
C

The diagram above shows a universal set $U$ and three sets $A, B, C$. Each distinct region in a Venn diagram corresponds to a unique combination of elements belonging or not belonging to the sets. For example:
* The region where all three circles overlap represents $A \cap B \cap C$.
* The region inside circle $A$ but outside $B$ and $C$ represents $A - (B \cup C)$.
* The region outside all circles but inside the rectangle represents $(A \cup B \cup C)^c$.

Understanding how to shade specific regions and translate them into set expressions (and vice versa) is crucial for solving problems involving multiple sets.

---

5. Real Number Intervals

While sets often deal with discrete elements, they can also represent continuous ranges of real numbers, known as intervals. This concept is particularly relevant for problems involving time, duration, or continuous measurements, as seen in some CMI questions.

Set operations like union and intersection apply to intervals as well.

Worked Example:

Problem: Find the intersection of the intervals $I_1 = [2, 7]$ and $I_2 = (5, 10]$.

Solution:

Step 1: Visualize the intervals on a number line.
$I_1$ includes 2 and 7, and all numbers between.
$I_2$ includes numbers strictly greater than 5 up to and including 10.

Step 2: Identify the overlap.
For $x$ to be in both intervals, it must satisfy $2 \le x \le 7$ AND $5 < x \le 10$.
Combining these conditions:
The lower bound must be the maximum of the lower bounds: $\max(2, 5) = 5$. Since $I_2$ is open at 5, the intersection will be open at 5.
The upper bound must be the minimum of the upper bounds: $\min(7, 10) = 7$. Since $I_1$ is closed at 7, the intersection will be closed at 7.

Step 3: Write the resulting interval.

Answer: The intersection is $(5, 7]$.

---

Problem-Solving Strategies

---

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="A survey of 100 students revealed that 60 students like Math, 50 students like Science, and 40 students like History. 30 students like Math and Science, 25 like Math and History, 20 like Science and History, and 10 students like all three subjects. How many students like none of the three subjects?" options=["10","15","20","25"] answer="15" hint="Use the Inclusion-Exclusion Principle for three sets to find the total number of students who like at least one subject, then subtract from the total number of students." solution="Let $M$ be the set of students who like Math, $S$ for Science, and $H$ for History.
We are given:
$|U| = 100$
$|M| = 60$
$|S| = 50$
$|H| = 40$
$|M \cap S| = 30$
$|M \cap H| = 25$
$|S \cap H| = 20$
$|M \cap S \cap H| = 10$

First, find the number of students who like at least one subject using the Inclusion-Exclusion Principle for three sets:

The number of students who like none of the three subjects is the total number of students minus those who like at least one:

Answer: $\boxed{15}$"
:::

---

---

Part 2: Relations

Introduction

Relations are fundamental mathematical structures that describe connections or associations between elements within sets. In the realm of Discrete Mathematics, particularly for a Masters in Data Science, understanding relations is crucial for modeling relationships in data, designing databases, analyzing network structures, and formalizing logical deductions. This topic lays the groundwork for advanced concepts in graph theory, order theory, and the construction of abstract data types.

At its core, a relation formalizes the intuitive idea of "being related to." For instance, in a set of people, "is a sibling of" or "is taller than" are relations. In data science, "is connected to" in a social network, "is an instance of" in an object-oriented model, or "is a prerequisite for" in a course catalog are all examples of relations. This chapter will delve into the formal definitions, various properties, and classifications of relations, equipping you with the tools to analyze and apply them effectively in CMI examinations.

---

Key Concepts

1. Definition and Representation of Relations

A relation can be represented in several ways, each offering a different perspective, which is useful for different types of problems.

Ordered Pairs

The most direct way to represent a relation is as a set of ordered pairs.

Example:
Let $A = \{1, 2, 3\}$ and $R$ be the relation "$x$ divides $y$" on $A$.
The relation $R$ can be written as:

Relation Matrix

For relations on finite sets, a relation matrix (or adjacency matrix) provides a compact representation. If $R$ is a relation on $A = \{a_1, a_2, \ldots, a_n\}$, the relation matrix $M_R$ is an $n \times n$ binary matrix where the entry $M_R(i, j)$ is $1$ if $(a_i, a_j) \in R$ and $0$ otherwise.

Worked Example:

Problem: Let $A = \{a, b, c\}$ and $R = \{(a,a), (a,c), (b,c), (c,b)\}$. Represent $R$ as a relation matrix.

Solution:

Step 1: Order the elements of $A$. Let $a_1=a, a_2=b, a_3=c$.

Step 2: Fill in the matrix entries based on the definition of $R$.
For $m_{ij}=1$ if $(a_i, a_j) \in R$, and $0$ otherwise.

Answer:
The relation matrix is $\begin{pmatrix} 1 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$.

Directed Graph (Digraph)

A relation $R$ on a set $A$ can be visualized as a directed graph. The elements of $A$ are the vertices (nodes) of the graph, and an ordered pair $(a, b) \in R$ corresponds to a directed edge (arc) from vertex $a$ to vertex $b$.

Worked Example:

Problem: Let $A = \{1, 2, 3, 4\}$ and $R = \{(1,2), (2,2), (2,3), (3,4), (4,1)\}$. Draw the digraph representing $R$.

Solution:

Step 1: Represent each element of $A$ as a vertex.

1


2


4


3

Step 2: Draw an arrow from $x$ to $y$ for each $(x,y) \in R$. A loop is drawn for $(x,x)$.

1


2


3


4

Answer: The diagram above visually represents the relation $R$.

---

2. Properties of Relations

Understanding the properties of relations is crucial for classifying them and predicting their behavior. These properties are frequently tested in CMI.

a. Reflexivity

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

Matrix Representation: All diagonal entries $m_{ii}$ are $1$.
Digraph Representation: Every vertex has a loop.

b. Irreflexivity

A relation $R$ on a set $A$ is irreflexive if no element is related to itself.

Matrix Representation: All diagonal entries $m_{ii}$ are $0$.
Digraph Representation: No vertex has a loop.

c. Symmetry

A relation $R$ on a set $A$ is symmetric if whenever $a$ is related to $b$, then $b$ is also related to $a$.

Matrix Representation: $M_R$ is a symmetric matrix (i.e., $M_R = M_R^T$, or $m_{ij} = m_{ji}$).
Digraph Representation: If there is an edge from $a$ to $b$, there is also an edge from $b$ to $a$.

d. Antisymmetry

A relation $R$ on a set $A$ is antisymmetric if the only way for $a$ to be related to $b$ and $b$ to be related to $a$ is if $a$ and $b$ are the same element. This is a critical property, often confused with asymmetry.

Matrix Representation: For $i \neq j$, if $m_{ij}=1$, then $m_{ji}=0$. (Diagonal entries can be $0$ or $1$).
Digraph Representation: For any two distinct vertices $a, b$, if there is an edge from $a$ to $b$, there cannot be an edge from $b$ to $a$.

e. Asymmetry

A relation $R$ on a set $A$ is asymmetric if it is both irreflexive and antisymmetric.

Matrix Representation: For all $i,j$, if $m_{ij}=1$, then $m_{ji}=0$. (This implies $m_{ii}=0$ for all $i$).
Digraph Representation: No loops, and if there is an edge from $a$ to $b$, there is no edge from $b$ to $a$.

f. Transitivity

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 also related to $c$.

Matrix Representation: If $M_R^2$ is computed using Boolean matrix multiplication (where multiplication is replaced by logical AND, and addition by logical OR), then $M_R(i,j)=1$ implies $(M_R^2)(i,j)=1$. More simply, if there is a path of length 2 from $a_i$ to $a_j$, there must be a direct edge from $a_i$ to $a_j$.
Digraph Representation: If there's a path of length two from $a$ to $c$ (i.e., $a \to b \to c$), then there must be a direct edge from $a$ to $c$.

Worked Example (Properties):

Problem: Consider the relation $R = \{(1,1), (1,2), (2,1), (2,2), (3,3)\}$ on the set $A = \{1,2,3\}$. Determine if $R$ is reflexive, symmetric, antisymmetric, and transitive.

Solution:

Step 1: Check for Reflexivity.
For $R$ to be reflexive, all $(a,a)$ for $a \in A$ must be in $R$.
The pairs are $(1,1), (2,2), (3,3)$.
All these pairs are in $R$.
So, $R$ is reflexive.

Step 2: Check for Symmetry.
For $R$ to be symmetric, if $(a,b) \in R$, then $(b,a) \in R$.
Consider $(1,2) \in R$. Is $(2,1) \in R$? Yes.
Consider $(2,1) \in R$. Is $(1,2) \in R$? Yes.
All other pairs are $(a,a)$ type, which trivially satisfy symmetry.
So, $R$ is symmetric.

Step 3: Check for Antisymmetry.
For $R$ to be antisymmetric, if $(a,b) \in R$ and $(b,a) \in R$, then $a=b$.
Consider $(1,2) \in R$ and $(2,1) \in R$. Here, $a=1, b=2$. But $1 \neq 2$.
This violates the condition for antisymmetry.
So, $R$ is not antisymmetric.

Step 4: Check for Transitivity.
For $R$ to be transitive, if $(a,b) \in R$ and $(b,c) \in R$, then $(a,c) \in R$.
Consider $(1,2) \in R$ and $(2,1) \in R$. We must have $(1,1) \in R$. Yes, it is.
Consider $(2,1) \in R$ and $(1,2) \in R$. We must have $(2,2) \in R$. Yes, it is.
Consider $(1,1) \in R$ and $(1,2) \in R$. We must have $(1,2) \in R$. Yes, it is.
Consider $(2,2) \in R$ and $(2,1) \in R$. We must have $(2,1) \in R$. Yes, it is.
Other combinations are similar or involve $(3,3)$ which only relates to itself.
So, $R$ is transitive.

Answer: $R$ is reflexive, symmetric, and transitive, but not antisymmetric.

---

---

#
## 3. Special Types of Relations

#
### a. Equivalence Relations
An equivalence relation partitions a set into disjoint subsets called equivalence classes. This concept is fundamental in many areas of mathematics and computer science.

Worked Example (Equivalence Relation):

Problem: Let $A = \{1, 2, 3, 4, 5, 6\}$ and let $R$ be the relation on $A$ defined by $(a,b) \in R$ if $a \equiv b \pmod 3$. Show that $R$ is an equivalence relation and find its equivalence classes.

Solution:

Step 1: Check Reflexivity.
For any $a \in A$, $a-a = 0$, and $0$ is divisible by $3$.
So, $a \equiv a \pmod 3$, which means $(a,a) \in R$.
$R$ is reflexive.

Step 2: Check Symmetry.
Assume $(a,b) \in R$. This means $a \equiv b \pmod 3$, so $a-b = 3k$ for some integer $k$.
Then $b-a = -3k = 3(-k)$. Since $-k$ is an integer, $b \equiv a \pmod 3$.
So, $(b,a) \in R$.
$R$ is symmetric.

Step 3: Check Transitivity.
Assume $(a,b) \in R$ and $(b,c) \in R$.
This means $a \equiv b \pmod 3$ and $b \equiv c \pmod 3$.
So, $a-b = 3k$ and $b-c = 3m$ for some integers $k, m$.
Adding these equations:

Since $k+m$ is an integer, $a \equiv c \pmod 3$.
So, $(a,c) \in R$.
$R$ is transitive.

Since $R$ is reflexive, symmetric, and transitive, it is an equivalence relation.

Step 4: Find Equivalence Classes.
The equivalence classes are determined by the remainder when divided by $3$.
$[1]_R = \{x \in A \mid x \equiv 1 \pmod 3\} = \{1, 4\}$
$[2]_R = \{x \in A \mid x \equiv 2 \pmod 3\} = \{2, 5\}$
$[3]_R = \{x \in A \mid x \equiv 0 \pmod 3\} = \{3, 6\}$

Answer: $R$ is an equivalence relation. The equivalence classes are $\{1, 4\}$, $\{2, 5\}$, and $\{3, 6\}$.

#
### b. Partial Order Relations
Partial order relations establish a hierarchy or ordering among elements, not necessarily requiring every pair of elements to be comparable.

Example:

• The "less than or equal to" relation ($\le$) on the set of real numbers.


• The "subset of" relation ($\subseteq$) on the power set of a set.


• The "divides" relation ($\mid$) on the set of positive integers.

Example: The "less than or equal to" relation ($\le$) on the set of real numbers is a total order. The "divides" relation on integers is not a total order because, e.g., $2$ does not divide $3$ and $3$ does not divide $2$.

---

#
## 4. Operations on Relations

Relations, being sets, can be combined using set operations.

#
### a. Union of Relations
The union of two relations $R_1$ and $R_2$ on a set $A$ is $R_1 \cup R_2$. An ordered pair $(a,b)$ is in $R_1 \cup R_2$ if it is in $R_1$ or in $R_2$.

Property: The union of two equivalence relations is not always an equivalence relation. It might fail transitivity or reflexivity if the sets are different. For example, if $R_1$ and $R_2$ are equivalence relations on $A$, $R_1 \cup R_2$ is reflexive and symmetric, but not necessarily transitive.
Consider $A = \{1,2,3\}$, $R_1 = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$, $R_2 = \{(1,1), (2,2), (3,3), (2,3), (3,2)\}$.
$R_1 \cup R_2 = \{(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)\}$.
Here, $(1,2) \in R_1 \cup R_2$ and $(2,3) \in R_1 \cup R_2$, but $(1,3) \notin R_1 \cup R_2$. Thus, $R_1 \cup R_2$ is not transitive.

#
### b. Intersection of Relations
The intersection of two relations $R_1$ and $R_2$ on a set $A$ is $R_1 \cap R_2$. An ordered pair $(a,b)$ is in $R_1 \cap R_2$ if it is in both $R_1$ and $R_2$.

Property: The intersection of two equivalence relations is always an equivalence relation.

• Reflexivity: If $R_1, R_2$ are reflexive, then $(a,a) \in R_1$ and $(a,a) \in R_2$ for all $a$. So $(a,a) \in R_1 \cap R_2$.


• Symmetry: If $(a,b) \in R_1 \cap R_2$, then $(a,b) \in R_1$ and $(a,b) \in R_2$. By symmetry of $R_1, R_2$, $(b,a) \in R_1$ and $(b,a) \in R_2$. So $(b,a) \in R_1 \cap R_2$.


• Transitivity: If $(a,b) \in R_1 \cap R_2$ and $(b,c) \in R_1 \cap R_2$, then $(a,b) \in R_1$, $(b,c) \in R_1$ and $(a,b) \in R_2$, $(b,c) \in R_2$. By transitivity of $R_1, R_2$, $(a,c) \in R_1$ and $(a,c) \in R_2$. So $(a,c) \in R_1 \cap R_2$.

#
### c. Composition of Relations
The composition of relations is analogous to function composition.

Note: The order of composition is crucial. $R_2 \circ R_1$ means apply $R_1$ first, then $R_2$. This is consistent with function notation $(f \circ g)(x) = f(g(x))$.

Matrix Multiplication for Composition: If $M_{R_1}$ is the matrix for $R_1$ from $A$ to $B$, and $M_{R_2}$ is the matrix for $R_2$ from $B$ to $C$, then the matrix for $R_2 \circ R_1$ is given by the Boolean product $M_{R_1} \cdot M_{R_2}$. Note that some texts define $M_{R_2 \circ R_1} = M_{R_1} \cdot M_{R_2}$ and others $M_{R_2 \circ R_1} = M_{R_2} \cdot M_{R_1}$. It depends on whether matrix multiplication is $M_{ij} = \sum_k A_{ik} B_{kj}$ (row-column) or $M_{ij} = \sum_k A_{kj} B_{ik}$ (column-row). C.L. Liu uses $M_{R_2 \circ R_1} = M_{R_1} \cdot M_{R_2}$ with standard row-column product.

Worked Example (Composition):

Problem: Let $A = \{1,2,3\}$, $R_1 = \{(1,2), (2,3)\}$ on $A$, and $R_2 = \{(1,1), (2,1), (3,2)\}$ on $A$. Find $R_2 \circ R_1$.

Solution:

Step 1: Identify pairs $(a,b) \in R_1$ and $(b,c) \in R_2$.
We need to find $a \in A, b \in A, c \in A$ such that $(a,b) \in R_1$ and $(b,c) \in R_2$.

Step 2: List potential compositions.

• From $(1,2) \in R_1$:

- Check for pairs in $R_2$ starting with $2$: $(2,1) \in R_2$.
- This gives $(1,1) \in R_2 \circ R_1$.

• From $(2,3) \in R_1$:

- Check for pairs in $R_2$ starting with $3$: $(3,2) \in R_2$.
- This gives $(2,2) \in R_2 \circ R_1$.

Step 3: Collect all resulting pairs.

Answer: $R_2 \circ R_1 = \{(1,1), (2,2)\}$.

---

#
## 5. Relation Closures

Sometimes a relation may not possess a desired property (e.g., transitivity). We can add the minimum number of ordered pairs to make it possess that property, resulting in a "closure" of the original relation. This concept is crucial for problems involving "paths" or "reachability."

The concept of "path" and "finitely many applications" in PYQ 1/7 directly relates to the transitive closure of the relation defined by the transformation rules. If $x$ can be transformed into $y$, $(x,y)$ is in the transitive closure of the base transformation relation.

---

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Let $A = \{a, b, c, d\}$ and $R$ be a relation on $A$ represented by the matrix:

Which of the following statements about $R$ is true?" options=["A. $R$ is reflexive and antisymmetric.","B. $R$ is symmetric and transitive, but not reflexive.","C. $R$ is an equivalence relation.","D. $R$ is neither symmetric nor antisymmetric."] answer="C. $R$ is an equivalence relation." hint="Convert the matrix to ordered pairs if it helps, then check reflexivity, symmetry, and transitivity." solution="
Step 1: Convert $M_R$ to a set of ordered pairs.
$R = \{(a,a), (a,b), (b,a), (b,b), (c,c), (c,d), (d,c), (d,d)\}$

Step 2: Check Reflexivity.
All diagonal elements are 1 ($m_{11}, m_{22}, m_{33}, m_{44}$ are all 1).
So, $(a,a), (b,b), (c,c), (d,d) \in R$. $R$ is reflexive.

Step 3: Check Symmetry.
The matrix $M_R$ is symmetric ($M_R = M_R^T$).
For example, $(a,b) \in R \implies (b,a) \in R$. $(c,d) \in R \implies (d,c) \in R$.
So, $R$ is symmetric.

Step 4: Check Antisymmetry.
For $R$ to be antisymmetric, if $(x,y) \in R$ and $(y,x) \in R$, then $x=y$.
We have $(a,b) \in R$ and $(b,a) \in R$, but $a \neq b$.
So, $R$ is NOT antisymmetric.

Step 5: Check Transitivity.
We need to check if $(x,y) \in R$ and $(y,z) \in R \implies (x,z) \in R$.
Consider $(a,b) \in R$ and $(b,a) \in R \implies (a,a) \in R$. (Holds)
Consider $(a,b) \in R$ and $(b,b) \in R \implies (a,b) \in R$. (Holds)
Consider $(b,a) \in R$ and $(a,b) \in R \implies (b,b) \in R$. (Holds)
Consider $(c,d) \in R$ and $(d,c) \in R \implies (c,c) \in R$. (Holds)
All possible paths of length 2 lead to an existing edge. For example, $M_R \cdot M_R = M_R$ (using Boolean multiplication).
So, $R$ is transitive.

Step 6: Evaluate the options.

• A. $R$ is reflexive and antisymmetric. (False, not antisymmetric)


• B. $R$ is symmetric and transitive, but not reflexive. (False, $R$ is reflexive)


• C. $R$ is an equivalence relation. (True, $R$ is reflexive, symmetric, and transitive)


• D. $R$ is neither symmetric nor antisymmetric. (False, $R$ is symmetric)

Therefore, $R$ is an equivalence relation.
Answer: \boxed{C. R \text{ is an equivalence relation.}}
"
:::

:::question type="NAT" question="A conference has $150$ attendees. Some attendees exchange business cards. Each attendee recorded the number of cards they received. The sum of all recorded numbers is $320$. How many business card exchanges occurred in total?" answer="160" hint="Consider the problem as a graph where attendees are vertices and an exchange is an edge. Each exchange involves two cards." solution="
Step 1: Understand the problem in terms of graph theory.
Let the attendees be vertices $V$ of a graph.
Let an exchange of business cards be an edge $E$.
If person A exchanges a card with person B, this implies two cards are exchanged: A gives one to B, and B gives one to A. This is a single edge between A and B in an undirected graph.

Step 2: Relate recorded numbers to graph properties.
Each attendee records the number of cards they received. If A exchanges with B, A receives a card from B, and B receives a card from A.
The number of cards an attendee receives is equal to the number of people they exchanged cards with. This is precisely the degree of the vertex representing that attendee in the graph.

Step 3: Apply the Handshaking Lemma.
The sum of all recorded numbers is the sum of the degrees of all vertices in the graph.
Let $N$ be the sum of all recorded numbers.
$N = \sum_{v \in V} \deg(v) = 320$.
According to the Handshaking Lemma, $N = 2|E|$, where $|E|$ is the total number of edges (business card exchanges).

Step 4: Calculate the total number of exchanges.

Thus, $160$ business card exchanges occurred in total.
Answer: \boxed{160}
"
:::

:::question type="MSQ" question="Let $R_1$ and $R_2$ be two equivalence relations on a non-empty set $A$. Which of the following statements is/are true?" options=["A. $R_1 \cup R_2$ is always an equivalence relation.","B. $R_1 \cap R_2$ is always an equivalence relation.","C. If $A=\{1,2,3\}$, $R_1=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$, and $R_2=\{(1,1),(2,2),(3,3),(2,3),(3,2)\}$, then $R_1 \cup R_2$ is not transitive.","D. If $R_1$ and $R_2$ are partial orders on $A$, then $R_1 \cup R_2$ is always a partial order.""] answer="B,C" hint="Recall the properties of union and intersection of relations. For union, consider a counterexample for transitivity." solution="
Step 1: Evaluate Option A: $R_1 \cup R_2$ is always an equivalence relation.
This statement is False. While $R_1 \cup R_2$ will be reflexive and symmetric if $R_1$ and $R_2$ are, it is not necessarily transitive.
Consider the counterexample provided in the notes:
Let $A = \{1,2,3\}$.
$R_1 = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$ (equivalence relation on $A$).
$R_2 = \{(1,1), (2,2), (3,3), (2,3), (3,2)\}$ (equivalence relation on $A$).
Then $R_1 \cup R_2 = \{(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)\}$.
We have $(1,2) \in R_1 \cup R_2$ and $(2,3) \in R_1 \cup R_2$. For transitivity, $(1,3)$ must be in $R_1 \cup R_2$, but it is not.
So, $R_1 \cup R_2$ is not transitive, and thus not an equivalence relation.

Step 2: Evaluate Option B: $R_1 \cap R_2$ is always an equivalence relation.
This statement is True. As discussed in the notes:

• Reflexivity: If $R_1, R_2$ are reflexive, then for all $a \in A$, $(a,a) \in R_1$ and $(a,a) \in R_2$. Thus $(a,a) \in R_1 \cap R_2$.


• Symmetry: If $(a,b) \in R_1 \cap R_2$, then $(a,b) \in R_1$ and $(a,b) \in R_2$. Since $R_1, R_2$ are symmetric, $(b,a) \in R_1$ and $(b,a) \in R_2$. Thus $(b,a) \in R_1 \cap R_2$.


• Transitivity: If $(a,b) \in R_1 \cap R_2$ and $(b,c) \in R_1 \cap R_2$, then $(a,b) \in R_1$, $(b,c) \in R_1$ and $(a,b) \in R_2$, $(b,c) \in R_2$. Since $R_1, R_2$ are transitive, $(a,c) \in R_1$ and $(a,c) \in R_2$. Thus $(a,c) \in R_1 \cap R_2$.

Step 3: Evaluate Option C: If $A=\{1,2,3\}$, $R_1=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$, and $R_2=\{(1,1),(2,2),(3,3),(2,3),(3,2)\}$, then $R_1 \cup R_2$ is not transitive.
This statement is True. This is the exact counterexample used for Option A. As shown in Step 1, $R_1 \cup R_2$ for these specific relations is not transitive because $(1,2) \in R_1 \cup R_2$ and $(2,3) \in R_1 \cup R_2$, but $(1,3) \notin R_1 \cup R_2$.

Step 4: Evaluate Option D: If $R_1$ and $R_2$ are partial orders on $A$, then $R_1 \cup R_2$ is always a partial order.
This statement is False. A partial order must be reflexive, antisymmetric, and transitive.
While $R_1 \cup R_2$ will be reflexive (if $A$ is non-empty), it is not necessarily antisymmetric or transitive.
Counterexample for antisymmetry: Let $A=\{1,2,3\}$.
$R_1 = \{(1,1), (2,2), (3,3), (1,2)\}$ (partial order).
$R_2 = \{(1,1), (2,2), (3,3), (2,1)\}$ (partial order).
$R_1 \cup R_2 = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$.
This union is not antisymmetric because $(1,2) \in R_1 \cup R_2$ and $(2,1) \in R_1 \cup R_2$, but $1 \neq 2$.
Counterexample for transitivity (similar to equivalence relations):
Let $A=\{1,2,3\}$.
$R_1 = \{(1,1), (2,2), (3,3), (1,2)\}$
$R_2 = \{(1,1), (2,2), (3,3), (2,3)\}$
$R_1 \cup R_2 = \{(1,1), (2,2), (3,3), (1,2), (2,3)\}$.
Here, $(1,2) \in R_1 \cup R_2$ and $(2,3) \in R_1 \cup R_2$, but $(1,3) \notin R_1 \cup R_2$. So it's not transitive.

Final Answer: Options B and C are true.
Answer: \boxed{B,C}
"
:::

:::question type="SUB" question="Let $A = \{1, 2, 3\}$. A relation $R$ on $A$ is defined as $R = \{(1,2), (2,3)\}$. Find the smallest relation $R'$ on $A$ that contains $R$ and is an equivalence relation. List all ordered pairs in $R'$." answer="R' = {(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2), (1,3), (3,1)}" hint="To make $R$ an equivalence relation, you must ensure it is reflexive, symmetric, and transitive. Start by adding pairs for reflexivity, then symmetry, then transitivity. Repeat until all conditions are met." solution="
Step 1: Start with the given relation $R$.

Step 2: Make $R$ reflexive.
To be reflexive, all $(a,a)$ for $a \in A$ must be in the relation. Add $(1,1), (2,2), (3,3)$.

Step 3: Make $R_1$ symmetric.
For every $(a,b) \in R_1$, $(b,a)$ must also be in $R_1$.
From $(1,2) \in R_1$, add $(2,1)$.
From $(2,3) \in R_1$, add $(3,2)$.

At this point, $R_2$ is reflexive and symmetric.

Step 4: Make $R_2$ transitive.
We need to check all pairs $(a,b)$ and $(b,c)$ in $R_2$ and ensure $(a,c)$ is also in $R_2$.

• $(1,2) \in R_2$ and $(2,1) \in R_2 \implies (1,1) \in R_2$ (already present).


• $(1,2) \in R_2$ and $(2,3) \in R_2 \implies (1,3)$ must be in $R_2$. Add $(1,3)$.


• $(2,1) \in R_2$ and $(1,2) \in R_2 \implies (2,2) \in R_2$ (already present).


• $(2,3) \in R_2$ and $(3,2) \in R_2 \implies (2,2) \in R_2$ (already present).


• $(3,2) \in R_2$ and $(2,1) \in R_2 \implies (3,1)$ must be in $R_2$. Add $(3,1)$.


• $(3,2) \in R_2$ and $(2,3) \in R_2 \implies (3,3) \in R_2$ (already present).

Let's update the relation after adding $(1,3)$ and $(3,1)$:

Step 5: Re-check symmetry for $R_3$.
We added $(1,3)$, so we need $(3,1)$. This was added.
We added $(3,1)$, so we need $(1,3)$. This was added.
$R_3$ is still symmetric.

Step 6: Re-check transitivity for $R_3$ (newly formed chains).

• $(1,3) \in R_3$ and $(3,1) \in R_3 \implies (1,1) \in R_3$ (present).


• $(3,1) \in R_3$ and $(1,3) \in R_3 \implies (3,3) \in R_3$ (present).


• $(1,3) \in R_3$ and $(3,2) \in R_3 \implies (1,2) \in R_3$ (present).


• $(2,1) \in R_3$ and $(1,3) \in R_3 \implies (2,3) \in R_3$ (present).

All other chains involve elements already checked or identity elements.
The relation $R_3$ is now reflexive, symmetric, and transitive.

The smallest equivalence relation $R'$ containing $R$ is $R_3$.

Answer: \boxed{R' = \{(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2), (1,3), (3,1)\}}
"
:::

:::question type="NAT" question="Consider the set $A = \{(x,y) \in \mathbb{Z} \times \mathbb{Z} \mid |x| + |y| = 5\}$. How many points in $A$ have coordinates where $x \ge 0$ and $y \ge 0$?" answer="6" hint="This is a counting problem based on absolute value equations. Break it down by quadrants or cases for $x, y \ge 0$." solution="
Step 1: Understand the given set $A$.
The set $A$ consists of integer coordinate points $(x,y)$ such that $|x| + |y| = 5$.

Step 2: Focus on the condition $x \ge 0$ and $y \ge 0$.
If $x \ge 0$ and $y \ge 0$, then $|x| = x$ and $|y| = y$.
The equation becomes $x + y = 5$.

Step 3: List integer solutions for $x+y=5$ where $x \ge 0$ and $y \ge 0$.
Possible pairs $(x,y)$ are:

• If $x=0$, then $y=5$. So $(0,5)$.


• If $x=1$, then $y=4$. So $(1,4)$.


• If $x=2$, then $y=3$. So $(2,3)$.


• If $x=3$, then $y=2$. So $(3,2)$.


• If $x=4$, then $y=1$. So $(4,1)$.


• If $x=5$, then $y=0$. So $(5,0)$.

Step 4: Count the number of such points.
There are $6$ distinct points that satisfy the conditions.
Answer: \boxed{6}
"
:::

:::question type="MCQ" question="Let $P$ be the power set of $\{a, b\}$. A relation $R$ on $P$ is defined as $X R Y$ if and only if $X \subseteq Y$. Which of the following properties does $R$ possess?" options=["A. Reflexive, Symmetric, Not Transitive","B. Reflexive, Antisymmetric, Transitive","C. Irreflexive, Symmetric, Transitive","D. Irreflexive, Antisymmetric, Not Transitive"] answer="B. Reflexive, Antisymmetric, Transitive" hint="Recall the properties of the subset relation ($\subseteq$)." solution="
Step 1: Determine the set $P$.
The power set of $\{a, b\}$ is $P = \{\emptyset, \{a\}, \{b\}, \{a,b\}\}$.

Step 2: List the relation $R$ explicitly.
$X R Y \iff X \subseteq Y$.

Step 3: Check Reflexivity.
For any $X \in P$, $X \subseteq X$ is always true.
So, $(\emptyset, \emptyset), (\{a\}, \{a\}), (\{b\}, \{b\}), (\{a,b\}, \{a,b\})$ are all in $R$.
$R$ is reflexive.

Step 4: Check Symmetry.
If $X R Y$, does $Y R X$ imply $X=Y$? No, for symmetry, if $X R Y$, then $Y R X$ must hold without $X=Y$.
Consider $(\emptyset, \{a\}) \in R$. For $R$ to be symmetric, $(\{a\}, \emptyset)$ must be in $R$. But $\{a\} \not\subseteq \emptyset$.
So, $R$ is NOT symmetric.

Step 5: Check Antisymmetry.
If $X R Y$ and $Y R X$, then $X=Y$.
This means if $X \subseteq Y$ and $Y \subseteq X$, then $X=Y$. This is a fundamental property of sets.
So, $R$ IS antisymmetric.

Step 6: Check Transitivity.
If $X R Y$ and $Y R Z$, then $X R Z$.
This means if $X \subseteq Y$ and $Y \subseteq Z$, then $X \subseteq Z$. This is also a fundamental property of sets.
So, $R$ IS transitive.

Step 7: Evaluate the options.

• A. Reflexive, Symmetric, Not Transitive (False, not symmetric, is transitive)


• B. Reflexive, Antisymmetric, Transitive (True)


• C. Irreflexive, Symmetric, Transitive (False, is reflexive, not symmetric)


• D. Irreflexive, Antisymmetric, Not Transitive (False, is reflexive, is transitive)

Therefore, $R$ is reflexive, antisymmetric, and transitive. This means $R$ is a partial order.
Answer: \boxed{B. Reflexive, Antisymmetric, Transitive}
"
:::

---

---

Summary

---

What's Next?

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Let $A = \{1, 2, 3, 4\}$. Consider two relations $R_1$ and $R_2$ on $A$.
$R_1 = \{(x, y) \in A \times A \mid x+y \text{ is even}\}$
$R_2 = \{(x, y) \in A \times A \mid x \text{ divides } y\}$

Which of the following statements about $R_1 \cap R_2$ is true?" options=["(A) $R_1 \cap R_2$ is reflexive but not symmetric." "(B) $R_1 \cap R_2$ is symmetric but not reflexive." "(C) $R_1 \cap R_2$ is an equivalence relation." "(D) $R_1 \cap R_2$ is neither reflexive nor symmetric."] answer="(A)" hint="First, list the elements of $R_1$ and $R_2$. Then find $R_1 \cap R_2$. Finally, check its properties: reflexivity, symmetry, and transitivity." solution="Let's first list the elements of $R_1$ and $R_2$:

$R_1 = \{(x, y) \in A \times A \mid x+y \text{ is even}\}$. This means $x$ and $y$ must have the same parity (both even or both odd).

$R_2 = \{(x, y) \in A \times A \mid x \text{ divides } y\}$.

Now, let's find $R_1 \cap R_2$:

Let's check the properties of $R_1 \cap R_2$:

Reflexivity: A relation $R$ on $A$ is reflexive if $(x,x) \in R$ for all $x \in A$.

For $A = \{1, 2, 3, 4\}$, we need $(1,1), (2,2), (3,3), (4,4)$ to be in $R_1 \cap R_2$.
All these pairs are present in $R_1 \cap R_2$.
Therefore, $R_1 \cap R_2$ is reflexive.

Symmetry: A relation $R$ is symmetric if whenever $(x,y) \in R$, then $(y,x) \in R$.

Consider $(1,3) \in R_1 \cap R_2$. For $R_1 \cap R_2$ to be symmetric, $(3,1)$ must also be in $R_1 \cap R_2$.
However, $(3,1) \notin R_1 \cap R_2$ (it is in $R_1$ but not in $R_2$ because $3$ does not divide $1$).
Therefore, $R_1 \cap R_2$ is not symmetric.

Since $R_1 \cap R_2$ is reflexive but not symmetric, it cannot be an equivalence relation (which requires symmetry).
The correct statement is (A).

Let's quickly check transitivity for completeness, though not required by options:
Consider $(1,3) \in R_1 \cap R_2$ and there is no $(3,z) \in R_1 \cap R_2$ where $z \ne 1$.
Consider $(2,4) \in R_1 \cap R_2$. There is no $(4,z) \in R_1 \cap R_2$ where $z \ne 4$.
It might seem transitive, but let's be careful. If $(x,y) \in R_1 \cap R_2$ and $(y,z) \in R_1 \cap R_2$, then $(x,z)$ must be in $R_1 \cap R_2$.
For example, $(1,1) \in R_1 \cap R_2$ and $(1,3) \in R_1 \cap R_2$. Then $(1,3)$ must be in $R_1 \cap R_2$, which it is.
If we had $(1,2)$ in $R_1 \cap R_2$ and $(2,4)$ in $R_1 \cap R_2$, then $(1,4)$ would need to be in $R_1 \cap R_2$. But $(1,2) \notin R_1 \cap R_2$.
The relation $R_1 \cap R_2$ is indeed transitive, but since it is not symmetric, it is not an equivalence relation.

The final answer is $\boxed{\text{(A)}}$"
:::

:::question type="NAT" question="Let $S$ be a finite set with $|S|=n$. What is the number of relations on $S$ that are both reflexive and symmetric?" answer="2^{n(n-1)/2}" hint="A relation $R$ on $S$ is a subset of $S \times S$. Consider the conditions for reflexivity and symmetry on the elements $(x,y) \in S \times S$." solution="Let $S$ be a set with $|S|=n$. A relation $R$ on $S$ is a subset of $S \times S$. The total number of possible ordered pairs in $S \times S$ is $n^2$.

Reflexivity condition: For $R$ to be reflexive, all pairs $(x,x)$ for $x \in S$ must be in $R$. There are $n$ such diagonal pairs: $(1,1), (2,2), \dots, (n,n)$. The inclusion of these $n$ pairs is mandatory.

Symmetry condition: For $R$ to be symmetric, if $(x,y) \in R$, then $(y,x)$ must also be in $R$.

Consider the off-diagonal pairs, where $x \ne y$. There are $n^2 - n = n(n-1)$ such pairs.
These off-diagonal pairs can be grouped into $\frac{n(n-1)}{2}$ distinct pairs of the form $\{(x,y), (y,x)\}$ where $x \ne y$. For example, if $n=3$, $S \times S$ has 9 pairs.
Diagonal pairs: $(1,1), (2,2), (3,3)$. (3 pairs)
Off-diagonal pairs: $(1,2), (2,1), (1,3), (3,1), (2,3), (3,2)$. (6 pairs)
These form 3 sets: $\{(1,2), (2,1)\}$, $\{(1,3), (3,1)\}$, $\{(2,3), (3,2)\}$.

For each of these $\frac{n(n-1)}{2}$ groups of two distinct off-diagonal pairs $\{(x,y), (y,x)\}$, we have two choices for $R$:
* Include both $(x,y)$ and $(y,x)$ in $R$.
* Include neither $(x,y)$ nor $(y,x)$ in $R$.
We cannot include one without the other, as that would violate symmetry.

So, for the $n$ diagonal pairs, there is only 1 choice (they must all be in $R$).
For the $\frac{n(n-1)}{2}$ groups of off-diagonal pairs, there are 2 choices for each group.

Therefore, the total number of relations that are both reflexive and symmetric is $1 \times 2^{\frac{n(n-1)}{2}}$.

The final answer is $\boxed{2^{n(n-1)/2}}$"
:::

:::question type="NAT" question="Let $A = \{1, 2, 3, 4, 5, 6\}$. How many functions $f: A \to A$ are there such that $f$ is injective and $f(x) \ne x$ for all $x \in A$?" answer="265" hint="An injective function from $A$ to $A$ is a permutation. The condition $f(x) \ne x$ means it's a derangement. Recall the formula for derangements." solution="The set $A$ has $|A|=6$ elements.
A function $f: A \to A$ that is injective (one-to-one) is also surjective (onto) when the domain and codomain are the same finite set. Such a function is called a permutation of $A$.
The condition $f(x) \ne x$ for all $x \in A$ means that $f$ is a derangement. A derangement is a permutation where no element is mapped to itself.

The number of derangements of a set of $n$ elements, denoted by $D_n$ or $!n$, is given by the formula:

For $n=6$, we need to calculate $D_6$:

The final answer is $\boxed{265}$"
:::

:::question type="NAT" question="Let $S = \{1, 2, 3, \ldots, 10\}$. How many non-empty proper subsets of $S$ contain exactly 3 even numbers?" answer="320" hint="Break the problem into choosing even numbers and choosing odd numbers. Remember the conditions: non-empty and proper." solution="Let $S = \{1, 2, 3, \ldots, 10\}$.
The even numbers in $S$ are $E = \{2, 4, 6, 8, 10\}$, so $|E|=5$.
The odd numbers in $S$ are $O = \{1, 3, 5, 7, 9\}$, so $|O|=5$.

We are looking for the number of subsets $A \subseteq S$ such that:

$A$ is non-empty.

$A$ is a proper subset of $S$ (i.e., $A \ne S$).

$A$ contains exactly 3 even numbers.

Let's construct such a subset $A$.
Step 1: Choose the even numbers for $A$.
Since $A$ must contain exactly 3 even numbers, we choose 3 elements from the set $E$.
The number of ways to do this is $\binom{|E|}{3} = \binom{5}{3}$.

Step 2: Choose the odd numbers for $A$.
The remaining elements of $A$ (if any) must be chosen from the set $O$. We can choose any number of odd elements (from 0 to all $|O|$).
For each of the 5 odd numbers in $O$, we have two choices: either include it in $A$ or not.
The number of ways to choose odd numbers for $A$ is $2^{|O|} = 2^5 = 32$.

Step 3: Combine the choices.
The total number of subsets that contain exactly 3 even numbers is the product of the choices from Step 1 and Step 2:

Step 4: Check the conditions (non-empty and proper subset).
* Non-empty: Any subset constructed this way will always contain 3 even numbers, so it will have at least 3 elements. Thus, all 320 subsets are non-empty.
* Proper subset: A subset $A$ is proper if $A \ne S$. The set $S$ contains 5 even numbers. Since all our constructed subsets $A$ contain exactly 3 even numbers (which is not 5), none of these subsets can be equal to $S$. Thus, all 320 subsets are proper subsets.

Therefore, the number of non-empty proper subsets of $S$ that contain exactly 3 even numbers is 320.

The final answer is $\boxed{320}$"
:::

---

What's Next?