Set Theory, Relations, and Functions

Overview

In this chapter, we shall explore the fundamental discrete structures that form the bedrock of theoretical computer science: sets, relations, and functions. These concepts are not merely abstract mathematical exercises; rather, they provide the formal language and analytical tools necessary to model computational problems, define data structures, and reason about algorithmic processes. A mastery of this material is therefore essential, as questions derived from these principles appear consistently in the GATE examination, both directly and as prerequisites for understanding more advanced topics such as graph theory, databases, and automata theory.

Our study will proceed in a logical progression, beginning with the elementary concept of a set as a collection of objects. We will then build upon this foundation to examine relations, which formally describe the connections between elements within or across sets. This leads naturally to the study of functions, a specialized and ubiquitous type of relation that maps inputs to unique outputs, a concept central to the very idea of computation. Finally, we will investigate more complex algebraic structures, namely partial orders and lattices, which provide a framework for ordering and comparing elements in a set. Throughout this chapter, the emphasis will be on rigorous definition, the analysis of properties, and the application of these structures to problems relevant to a computer science engineer.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Sets | Fundamental properties and operations on collections. |
| 2 | Relations | Defining relationships between elements of sets. |
| 3 | Functions | Specialized relations with unique output mappings. |
| 4 | Partial Orders and Lattices | Structures for ordering and comparing elements. |

---

Learning Objectives

---

We now turn our attention to Sets...

Part 1: Sets

Introduction

The theory of sets is a fundamental branch of mathematics that serves as the bedrock for many areas within Computer Science, including discrete mathematics, database theory, automata theory, and algorithm design. A set is, in essence, the most basic way to group objects, and the study of these collections provides the language and tools necessary to reason about discrete structures. For the GATE examination, a firm grasp of set theory is indispensable for understanding more advanced topics such as relations, functions, and graph theory.

Our study will begin with the formal definition of a set and its various representations. We will then proceed to explore the relationships between sets, such as subsets and supersets, leading to the concept of the power set. The core of our discussion will focus on the operations that can be performed on sets—union, intersection, difference, and complement—along with the algebraic laws that govern them. Finally, we will examine the concepts of set cardinality and the Cartesian product, which are essential for combinatorial analysis.

---

Key Concepts

1. Representation of Sets

A set can be represented in two primary forms:

* Roster or Tabular Form: The elements of the set are listed explicitly, separated by commas, and enclosed in curly braces `{}`. For example, the set $V$ of vowels in the English alphabet is $V = \{a, e, i, o, u\}$.
* Set-Builder or Rule Form: The elements are described by a common property. We write this as $\{x \mid P(x)\}$ or $\{x : P(x)\}$, which reads "the set of all elements $x$ such that $x$ satisfies the property $P$." For example, $V = \{x \mid x \text{ is a vowel in the English alphabet}\}$.

2. Subsets, Power Sets, and Cardinality

Let us consider two sets, $A$ and $B$.

The cardinality of a finite set $A$, denoted by $|A|$, is the number of distinct elements in the set. The empty set, denoted by $\emptyset$ or $\{\}$, is a set with no elements, and its cardinality is $|\emptyset| = 0$.

A particularly important concept is the collection of all possible subsets of a given set.

Worked Example:

Problem: Find the power set of $S = \{1, 2\}$ and determine its cardinality.

Solution:

Step 1: Identify the elements of the set $S$.
The elements are $1$ and $2$. The cardinality is $|S| = 2$.

Step 2: List all possible subsets of $S$.
The subsets are:

• The empty set: $\emptyset$


• Subsets with one element: $\{1\}$, $\{2\}$


• The set itself: $\{1, 2\}$

Step 3: Collect all subsets into a set to form the power set $\mathcal{P}(S)$.

Step 4: Calculate the cardinality of the power set using the formula.

Answer: The power set is $\mathcal{P}(S) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$ and its cardinality is $4$.

3. Set Operations

We can combine or modify sets using several fundamental operations. Let $A$ and $B$ be two sets within a universal set $U$.

U




A
B

A ∩ B
A - B
B - A

* Union ($A \cup B$): The set of all elements that are in $A$, or in $B$, or in both.

* Intersection ($A \cap B$): The set of all elements that are in both $A$ and $B$.

* Difference ($A - B$): The set of all elements that are in $A$ but not in $B$.

* Complement ($A'$ or $A^c$): The set of all elements in the universal set $U$ that are not in $A$.

4. Principle of Inclusion-Exclusion

This principle is a counting technique used to find the number of elements in the union of two or more sets.

---

Problem-Solving Strategies

---

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Let $A = \{1, \{2, 3\}, 4\}$. Which of the following statements is true?" options=["$\{2, 3\} \subset A$","$\{2, 3\} \in A$","$\{1, 4\} \in A$","$2 \in A$"] answer="{2, 3} $\in$ A" hint="Distinguish between an element that is a set and a subset of the main set. Analyze the top-level elements of A." solution="
Step 1: Identify the elements of set $A$.
The set $A$ is given by $A = \{1, \{2, 3\}, 4\}$. The distinct elements of $A$ are the number $1$, the set $\{2, 3\}$, and the number $4$.

Step 2: Evaluate each option.

• Option A: $\{2, 3\} \subset A$: This statement claims that $\{2, 3\}$ is a proper subset of $A$. For this to be true, every element of $\{2, 3\}$ must be an element of $A$. The elements of $\{2, 3\}$ are $2$ and $3$. However, neither $2$ nor $3$ are elements of $A$. Thus, this statement is false.


• Option B: $\{2, 3\} \in A$: This statement claims that the set $\{2, 3\}$ is an element of $A$. Looking at the definition of $A$, we can see that $\{2, 3\}$ is indeed listed as one of the three elements. Thus, this statement is true.


• Option C: $\{1, 4\} \in A$: This statement claims that the set $\{1, 4\}$ is an element of $A$. The elements of $A$ are $1$, $\{2, 3\}$, and $4$. The set $\{1, 4\}$ is not one of these elements. Thus, this statement is false.


• Option D: $2 \in A$: This statement claims that the number $2$ is an element of $A$. The elements of $A$ are $1$, $\{2, 3\}$, and $4$. The number $2$ is not an element of $A$; it is an element of the set $\{2, 3\}$ which is an element of $A$. Thus, this statement is false.

Result: The only true statement is $\{2, 3\} \in A$.
Answer: $\boxed{\{2, 3\} \in A}$
"
:::

:::question type="NAT" question="In a class of 60 students, 35 students play Cricket and 20 students play both Cricket and Tennis. All students play at least one of the two games. How many students play Tennis?" answer="45" hint="Use the Principle of Inclusion-Exclusion. You are given the total number of students (the union), the number who play Cricket, and the number who play both (the intersection)." solution="
Step 1: Define the sets.
Let $C$ be the set of students who play Cricket.
Let $T$ be the set of students who play Tennis.
The total number of students is 60, and every student plays at least one game, so $|C \cup T| = 60$.

Step 2: List the given cardinalities.
$|C \cup T| = 60$
$|C| = 35$
$|C \cap T| = 20$

Step 3: Apply the Principle of Inclusion-Exclusion.
The formula is $|C \cup T| = |C| + |T| - |C \cap T|$.

Step 4: Substitute the known values and solve for $|T|$.

Result: 45 students play Tennis.
Answer: $\boxed{45}$
"
:::

:::question type="MSQ" question="Let $A$ and $B$ be two non-empty sets in a universal set $U$. Which of the following statements are always true?" options=["$A - B = A \cap B'$","$A \cup A' = U$","$A \subseteq A \cup B$","If $A \cap B = \emptyset$, then $A \subset B'$"] answer="A - B = A $\cap$ B',A $\cup$ A' = U,A $\subseteq$ A $\cup$ B,If A $\cap$ B = $\emptyset$, then A $\subset$ B'" hint="Evaluate each identity using the definitions of set operations and the complement." solution="
Let's analyze each statement:

• $A - B = A \cap B'$: By definition, $A - B$ contains all elements that are in $A$ but not in $B$. The set $B'$ contains all elements not in $B$. The intersection $A \cap B'$ contains all elements that are in $A$ AND not in $B$. These two definitions are identical. Thus, this statement is always true.

• $A \cup A' = U$: The set $A$ contains some elements of the universal set $U$. The set $A'$ contains all elements of $U$ that are not in $A$. Their union therefore contains all elements of $U$. This is the definition of the complement law. Thus, this statement is always true.

• $A \subseteq A \cup B$: The union $A \cup B$ contains all elements of $A$ and all elements of $B$. By definition, every element of $A$ is present in $A \cup B$. Therefore, $A$ is a subset of $A \cup B$. Thus, this statement is always true.

• If $A \cap B = \emptyset$, then $A \subset B'$: If $A \cap B = \emptyset$, it means that $A$ and $B$ are disjoint. This implies that every element of $A$ is not in $B$, and therefore must be in $B'$ (the complement of $B$). So, $A \subseteq B'$. Since $A$ and $B$ are non-empty, $A$ cannot be equal to $B'$ (as $B$ contains elements not in $B'$), making $A$ a proper subset of $B'$. Thus, this statement is always true.

All four statements represent fundamental and correct properties of sets. Answer: $\boxed{A - B = A \cap B', A \cup A' = U, A \subseteq A \cup B, \text{If } A \cap B = \emptyset, \text{ then } A \subset B'}$ " :::

---

Summary

---

What's Next?

---

---

Part 2: Relations

Introduction

In the discipline of discrete mathematics, the concept of a relation provides a formal framework for describing connections between elements of sets. A relation is, in essence, a generalization of a function. While a function must map each input from its domain to a single, unique output, a relation allows for more flexible associations: an element may be related to multiple elements, or to none at all. This framework is fundamental to numerous areas within computer science, including database theory (relational databases), graph theory, and the formal verification of algorithms.

Our study will begin with the foundational definitions, establishing a relation as a subset of a Cartesian product. We will then proceed to a systematic examination of the properties that a relation on a set may possess, such as reflexivity, symmetry, and transitivity. The culmination of these properties leads to the particularly important concept of an equivalence relation, which partitions a set into disjoint subsets known as equivalence classes. For the GATE examination, a thorough understanding of these properties and the structure of equivalence relations is not merely advantageous but essential for solving a class of problems that test deep conceptual clarity.

---

Key Concepts

1. Fundamental Definitions and Representations

Let us first establish the necessary groundwork. The Cartesian product of two sets, $A$ and $B$, denoted $A \times B$, is the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$.

A relation is simply any subset of this product. The set $A$ is called the domain of the relation, and the set $B$ is the codomain. The range of a relation $R$ is the set of all second elements of the pairs in $R$, i.e., $\{b \in B \mid \exists a \in A, (a, b) \in R\}$.

Relations can be represented in several ways, each offering a different perspective.

* Set-Roster Notation: The relation is explicitly listed as a set of ordered pairs. For $A = \{1, 2, 3\}$, a relation $R$ could be $R = \{(1, 2), (1, 3), (3, 2)\}$.
* Matrix Representation: For a relation $R$ from $A=\{a_1, ..., a_m\}$ to $B=\{b_1, ..., b_n\}$, we can construct an $m \times n$ matrix $M_R = [m_{ij}]$ where $m_{ij} = 1$ if $(a_i, b_j) \in R$ and $m_{ij} = 0$ otherwise.
* Directed Graph (Digraph): For a relation on a set $A$, we can draw a graph where the vertices represent the elements of $A$. A directed edge is drawn from vertex $a$ to vertex $b$ if and only if $(a, b) \in R$.

Consider the set $A = \{1, 2, 3, 4\}$ and the relation $R = \{(1, 1), (1, 2), (2, 3), (3, 4), (4, 1)\}$. The digraph representation provides an intuitive visualization of this structure.

1


2


3


4

---

2. Properties of Relations on a Set

When a relation $R$ is defined on a single set $A$ (i.e., $R \subseteq A \times A$), it can exhibit several important properties. Let us consider a relation $R$ on a set $A$.

* Reflexive: A relation $R$ is reflexive if every element is related to itself.

In matrix form, all diagonal entries must be 1. In a digraph, every vertex must have a self-loop.

* Irreflexive: A relation $R$ is irreflexive if no element is related to itself.

In matrix form, all diagonal entries must be 0. In a digraph, no vertex has a self-loop.

* Symmetric: A relation $R$ is symmetric if for every pair $(a,b)$ in $R$, the pair $(b,a)$ is also in $R$.

In matrix form, the matrix $M_R$ is equal to its transpose ($M_R = M_R^T$). In a digraph, for every edge from $a$ to $b$, there must be a corresponding edge from $b$ to $a$.

* Antisymmetric: A relation $R$ is antisymmetric if the only way for both $(a,b)$ and $(b,a)$ to be in $R$ is if $a=b$.

This property is crucial for defining partial orderings.

* Transitive: A relation $R$ is transitive if a "chain" of relations implies a direct relation.

In a digraph, if there is a path of length 2 from vertex $a$ to $c$ (via $b$), there must be a direct edge from $a$ to $c$.

* Circular: This is a less common but tested property. A relation is circular if a chain of two relations implies a "reversed" relation.

---

3. Equivalence Relations

An equivalence relation is a fundamental structure that generalizes the concept of equality. It groups elements of a set that are similar in some specified manner.

The canonical example is the equality relation "=" on the set of integers. Another is the congruence modulo $n$ relation, where $a \equiv b \pmod n$ if $n$ divides $(a-b)$.

An equivalence relation on a set $A$ induces a partition of $A$. A partition is a collection of non-empty, disjoint subsets of $A$ whose union is $A$. These subsets are called equivalence classes.

Worked Example:

Problem: Let $A = \{1, 2, 3, 4, 5\}$ and define a relation $R$ on $A$ such that $aRb$ if and only if $a \equiv b \pmod 3$. Determine the equivalence classes.

Solution:

Step 1: Understand the relation. $a \equiv b \pmod 3$ means that $a-b$ is an integer multiple of 3. We verify this is an equivalence relation (it is reflexive, symmetric, and transitive).

Step 2: Find the equivalence class of 1, denoted $[1]$. We seek all $x \in A$ such that $x \equiv 1 \pmod 3$.

• $1-1 = 0$, which is $0 \times 3$. So $1 \in [1]$.


• $2-1 = 1$, not a multiple of 3.


• $3-1 = 2$, not a multiple of 3.


• $4-1 = 3$, which is $1 \times 3$. So $4 \in [1]$.


• $5-1 = 4$, not a multiple of 3.

Step 3: Find the equivalence class of 2, denoted $[2]$. We seek all $x \in A$ such that $x \equiv 2 \pmod 3$.

• $2-2 = 0$. So $2 \in [2]$.


• $5-2 = 3$. So $5 \in [2]$.

Step 4: Find the equivalence class of 3, denoted $[3]$. We seek all $x \in A$ such that $x \equiv 3 \pmod 3$, which is the same as $x \equiv 0 \pmod 3$.

• $3-3 = 0$. So $3 \in [3]$.

Step 5: Verify the partition. The equivalence classes are $\{1, 4\}$, $\{2, 5\}$, and $\{3\}$. These are disjoint, non-empty, and their union is $\{1, 2, 3, 4, 5\} = A$.

Answer: The equivalence classes are $\{1, 4\}$, $\{2, 5\}$, and $\{3\}$. The quotient set is $A/R = \{\{1, 4\}, \{2, 5\}, \{3\}\}$.

---

4. The Circular Relation Property

As observed in GATE examinations, non-standard properties may be introduced to test fundamental reasoning. The circular property is one such example. A key result connects it directly to equivalence relations.

Let us prove this significant result.

Proof:

Part 1: Equivalence $\implies$ Reflexive and Circular

Assume $R$ is an equivalence relation. By definition, $R$ is reflexive. We must show it is circular.
Let $(a, b) \in R$ and $(b, c) \in R$.
Since $R$ is transitive, $(a, c) \in R$.
Since $R$ is symmetric, $(a, c) \in R \implies (c, a) \in R$.
Thus, $(a, b) \in R \land (b, c) \in R \implies (c, a) \in R$. This is the definition of a circular relation.

Part 2: Reflexive and Circular $\implies$ Equivalence

Assume $R$ is reflexive and circular. We must show $R$ is symmetric and transitive.

* Symmetry:
Let $(a, b) \in R$. We want to show $(b, a) \in R$.
Since $R$ is reflexive, we know that $(b, b) \in R$.
We have $(a, b) \in R$ and $(b, b) \in R$.
By the circular property, these two imply $(b, a) \in R$.
Thus, $R$ is symmetric.

* Transitivity:
Let $(a, b) \in R$ and $(b, c) \in R$. We want to show $(a, c) \in R$.
By the circular property, $(a, b) \in R \land (b, c) \in R \implies (c, a) \in R$.
We have just proven that $R$ is symmetric.
Therefore, since $(c, a) \in R$, it must be that $(a, c) \in R$.
Thus, $R$ is transitive.

Since $R$ is reflexive (by assumption), symmetric, and transitive, it is an equivalence relation. This completes the proof.

---

---

#
## 5. Relations Induced by Functions

A function can be used to define an equivalence relation on its domain. This construction is a powerful idea that connects the study of functions to relations and partitions.

Consider a function $f: A \to B$. We can define a relation $\sim$ on the domain $A$ as follows:

This relation groups together elements of the domain that map to the same element in the codomain. We can demonstrate that this is always an equivalence relation.

Reflexivity: For any $a \in A$, $f(a) = f(a)$, so $a \sim a$. It is reflexive.

Symmetry: If $a_1 \sim a_2$, then $f(a_1) = f(a_2)$. This implies $f(a_2) = f(a_1)$, so $a_2 \sim a_1$. It is symmetric.

Transitivity: If $a_1 \sim a_2$ and $a_2 \sim a_3$, then $f(a_1) = f(a_2)$ and $f(a_2) = f(a_3)$. This implies $f(a_1) = f(a_3)$, so $a_1 \sim a_3$. It is transitive.

Since $\sim$ is an equivalence relation, it partitions $A$ into equivalence classes. Let $\mathcal{E} = A/\sim$ be the set of these equivalence classes. We can now define a new function $F: \mathcal{E} \to B$ by the rule:

A crucial question arises: is this function $F$ well-defined? A function is well-defined if its output depends only on the input, not on how the input is represented. Here, the input is an equivalence class $[x]$, which can be represented by any of its members. If we choose a different representative, say $y \in [x]$, will we get the same output?

Let $[x] = [y]$. By definition of an equivalence class, this means $x \sim y$. By the definition of our relation $\sim$, this means $f(x) = f(y)$.
Therefore, $F([x]) = f(x)$ and $F([y]) = f(y)$, which are equal.
So, $F([x]) = F([y])$. The output of $F$ is independent of the choice of representative from the equivalence class. Thus, the function $F$ is always well-defined.

Now, let us analyze the properties of this new function $F$.

* Injectivity (One-to-one): $F$ is always injective.
To prove this, assume $F([x]) = F([y])$. By definition of $F$, this means $f(x) = f(y)$. By definition of $\sim$, this implies $x \sim y$. If $x$ and $y$ are equivalent, they belong to the same equivalence class, so $[x] = [y]$. We have shown that $F([x]) = F([y]) \implies [x] = [y]$, which is the definition of injectivity.

* Surjectivity (Onto): The surjectivity of $F$ depends on the surjectivity of the original function $f$.
If $f$ is surjective, then for any $b \in B$, there exists some $a \in A$ such that $f(a) = b$. Now consider the equivalence class $[a] \in \mathcal{E}$. The function $F$ maps this class as $F([a]) = f(a) = b$. So, for any element $b$ in the codomain, we have found a pre-image $[a]$ in the domain $\mathcal{E}$. Therefore, if $f$ is surjective, then $F$ is also surjective.

* Bijectivity: A function is bijective if it is both injective and surjective. From our analysis, $F$ is always injective. It is surjective if and only if $f$ is surjective. Therefore, if $f$ is surjective, then $F$ is bijective.

This result is a simplified version of the First Isomorphism Theorem for sets and provides a canonical way to construct a bijection from a surjection.

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Let $A = \{1, 2, 3, 4\}$. Consider the relation $R = \{(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)\}$. Which of the following properties does $R$ possess?" options=["Reflexive and Transitive","Symmetric but not Transitive","Transitive but not Symmetric","Neither Symmetric nor Transitive"] answer="Symmetric but not Transitive" hint="Check each property systematically. For reflexivity, ensure all elements of A have self-loops. For transitivity, look for paths of length 2." solution="
Step 1: Check Reflexivity.
The set is $A = \{1, 2, 3, 4\}$. A reflexive relation on $A$ must contain $(1,1), (2,2), (3,3), (4,4)$. The relation $R$ is missing $(4,4)$. Therefore, $R$ is not reflexive.

Step 2: Check Symmetry.
We check each pair.

• $(1,2) \in R$. The pair $(2,1)$ is also in $R$. This is satisfied.


• $(2,3) \in R$. The pair $(3,2)$ is also in $R$. This is satisfied.

All other pairs are of the form $(a,a)$, which are trivially symmetric. Thus, $R$ is symmetric.

Step 3: Check Transitivity.
We look for pairs $(a,b)$ and $(b,c)$ in $R$.

• We have $(1,2) \in R$ and $(2,3) \in R$. For transitivity, we must have $(1,3) \in R$.


• The pair $(1,3)$ is not in $R$.

Therefore, $R$ is not transitive.

Result: The relation is symmetric but not transitive.
Answer: \boxed{\text{Symmetric but not Transitive}}
"
:::

:::question type="NAT" question="Let $S$ be a set with 4 elements. What is the number of reflexive relations on $S$?" answer="4096" hint="A relation on a set with $n$ elements is a subset of a Cartesian product of size $n \times n$. For a relation to be reflexive, which pairs must be included?" solution="
Step 1: Define the set and the Cartesian product.
Let the set be $S$. The size of $S$ is $|S| = 4$.
A relation on $S$ is a subset of $S \times S$.
The size of the Cartesian product is $|S \times S| = |S| \times |S| = 4 \times 4 = 16$.
The total number of relations on $S$ is the number of subsets of $S \times S$, which is $2^{16}$.

Step 2: Apply the reflexive property constraint.
A relation $R$ on $S$ is reflexive if for every $x \in S$, the pair $(x,x)$ is in $R$.
The pairs on the main diagonal of the matrix representation are $(s_1, s_1), (s_2, s_2), (s_3, s_3), (s_4, s_4)$. There are 4 such pairs.
For $R$ to be reflexive, these 4 pairs must be included in the relation. There is no choice for them.

Step 3: Count the remaining choices.
There are a total of 16 pairs in $S \times S$.
The 4 diagonal pairs have a fixed choice (they must be in $R$).
The remaining $16 - 4 = 12$ off-diagonal pairs can either be in the relation or not. For each of these 12 pairs, we have 2 choices.

Step 4: Calculate the total number of reflexive relations.
The total number of ways to form the relation is the product of the number of choices for each pair.
Number of relations = $1^4 \times 2^{12} = 2^{12}$.

Step 5: Compute the final value.

Result: The number of reflexive relations on a set with 4 elements is 4096.
Answer: \boxed{4096}
"
:::

:::question type="MSQ" question="Let the set of integers be $\mathbb{Z}$. Define a function $g: \mathbb{Z} \to \mathbb{Z}$ as $g(x) = x^2$. Let $\sim$ be a relation on $\mathbb{Z}$ defined by $a \sim b$ if $g(a) = g(b)$. Let $\mathcal{E}$ be the set of equivalence classes of $\sim$. Let a new function $G: \mathcal{E} \to \mathbb{Z}$ be defined as $G([x]) = g(x)$. Which of the following statements is/are TRUE?" options=["The function $g$ is surjective.","The relation $\sim$ is an equivalence relation.","The function $G$ is injective (one-to-one).","The function $G$ is surjective (onto)."] answer="The relation $\sim$ is an equivalence relation.,The function $G$ is injective (one-to-one)." hint="Analyze the properties of the function $g(x)=x^2$ on the domain of integers. Recall the properties of the induced function G." solution="
Statement 1: The function $g$ is surjective.
A function is surjective if its range equals its codomain. Here, the codomain is $\mathbb{Z}$. The range of $g(x) = x^2$ for $x \in \mathbb{Z}$ is the set of perfect squares $\{0, 1, 4, 9, ...\}$. This is not equal to all integers $\mathbb{Z}$. For example, there is no integer $x$ such that $x^2 = -1$. Therefore, $g$ is not surjective. This statement is FALSE.

Statement 2: The relation $\sim$ is an equivalence relation.
The relation is defined as $a \sim b \iff g(a) = g(b)$. As proven in the notes, any relation defined this way from a function is an equivalence relation.

• Reflexive: $g(a) = g(a) \implies a \sim a$.


• Symmetric: $a \sim b \implies g(a)=g(b) \implies g(b)=g(a) \implies b \sim a$.


• Transitive: $a \sim b \land b \sim c \implies g(a)=g(b) \land g(b)=g(c) \implies g(a)=g(c) \implies a \sim c$.

The relation is reflexive, symmetric, and transitive. This statement is TRUE.

Statement 3: The function $G$ is injective (one-to-one).
The function $G$ is defined from the set of equivalence classes $\mathcal{E}$ to $\mathbb{Z}$. As proven in the notes, such a function $G([x]) = g(x)$ is always injective.
To verify: Assume $G([x]) = G([y])$. This means $g(x) = g(y)$. By definition of the relation $\sim$, this means $x \sim y$. If $x \sim y$, then they belong to the same equivalence class, i.e., $[x] = [y]$. Since $G([x]) = G([y]) \implies [x] = [y]$, the function $G$ is injective. This statement is TRUE.

Statement 4: The function $G$ is surjective (onto).
The function $G$ is surjective if and only if the original function $g$ is surjective. We already established in Statement 1 that $g$ is not surjective. Therefore, $G$ is also not surjective. This statement is FALSE.

Result: The correct statements are "The relation $\sim$ is an equivalence relation." and "The function $G$ is injective (one-to-one)."
Answer: \boxed{\text{The relation $\sim$ is an equivalence relation.,The function $G$ is injective (one-to-one).}}
"
:::

---

Summary

---

What's Next?

---

---

---

Part 3: Functions

Introduction

In the study of discrete mathematics, the concept of a function is of paramount importance. A function serves as a fundamental mechanism for formally describing a relationship between two sets, where each element of the first set is associated with exactly one element of the second. This simple yet powerful idea forms the bedrock upon which more complex structures in computer science are built, including data structures, algorithms, computability theory, and formal languages.

For the GATE examination, a robust understanding of functions is not merely a prerequisite for this topic alone; it is intrinsically linked to the study of relations, set theory, and counting principles. We will explore the formal definition of a function, classify functions based on their mapping properties—namely injectivity, surjectivity, and bijectivity—and investigate the composition of functions. Mastery of these concepts is essential for solving a significant class of problems that frequently appear in the examination, often requiring the application of function properties to arguments about set cardinalities.

---

Key Concepts

1. Domain, Codomain, Range, and Image

While the domain and codomain define the function's scope, the concepts of image and range describe its actual output.

• Domain ($A$): The set of all possible inputs to the function.
• Codomain ($B$): The set of all possible outputs, as declared in the function's definition.
• Image: The image of an element $a \in A$ under $f$ is the output element $f(a) \in B$.
• Range (or Image of $f$): The set of all actual output values produced by the function. The range of $f$ is a subset of the codomain $B$, denoted as $f(A)$ or $\operatorname{Range}(f)$. Formally, $\operatorname{Range}(f) = \{b \in B \mid \exists a \in A, f(a) = b\}$.

We observe that the range is always a subset of the codomain, i.e., $\operatorname{Range}(f) \subseteq B$.

Domain (A)

a1

a2

a3


Codomain (B)

Range


b1

b2

b3

b4

In the diagram, $f(a_1) = b_1$, $f(a_2) = b_2$, and $f(a_3) = b_1$. The domain is $\{a_1, a_2, a_3\}$. The codomain is $\{b_1, b_2, b_3, b_4\}$. The range is $\{b_1, b_2\}$, which is a proper subset of the codomain.

---

2. Types of Functions

The properties of the mapping give rise to a critical classification of functions.

Injective (One-to-One) Function

A function is injective if distinct elements in the domain map to distinct elements in the codomain.

For finite sets, an injection from $A$ to $B$ can only exist if the number of elements in the domain is less than or equal to the number of elements in the codomain.

Surjective (Onto) Function

A function is surjective if every element in the codomain is an image of at least one element from the domain.

For finite sets, a surjection from $A$ to $B$ can only exist if the number of elements in the domain is greater than or equal to the number of elements in the codomain.

Bijective Function

A function is bijective if it is both injective and surjective.

A bijection establishes a perfect one-to-one correspondence between the elements of two sets.

Injective (Not Surjective)








Surjective (Not Injective)

Bijective

---

3. Cardinality and Functions

For finite sets, the existence of certain types of functions imposes constraints on their cardinalities. These rules are fundamental for solving many GATE problems.

Furthermore, we can count the number of functions between two finite sets.

Worked Example:

Problem: Let $S_A$ be the set of all functions from $A = \{1, 2, 3\}$ to $B = \{0, 1\}$. Let $S_B$ be the set of all $2 \times 2$ binary matrices. Does a bijection exist between $S_A$ and $S_B$?

Solution:

Step 1: Calculate the cardinality of the set $S_A$.
The domain is $A$ with $|A|=3$. The codomain is $B$ with $|B|=2$. The number of functions from $A$ to $B$ is $|B|^{|A|}$.

Step 2: Calculate the cardinality of the set $S_B$.
A $2 \times 2$ binary matrix has $2 \times 2 = 4$ entries. Each entry can be either 0 or 1 (2 choices).

Step 3: Compare the cardinalities to determine if a bijection can exist.
A bijection between two finite sets can only exist if their cardinalities are equal.

Since $|S_A| \neq |S_B|$, no bijection can exist between $S_A$ and $S_B$.

Answer: $\boxed{\text{No, a bijection does not exist.}}$

---

---

4. Composition of Functions

We can combine functions to create new ones through an operation called composition.

The properties of a composite function depend on the properties of its constituent functions. These relationships are frequently tested in GATE.

Worked Example:

Problem: Let $f: \mathbb{Z} \to \mathbb{Z}$ be defined by $f(x) = x+1$, and $g: \mathbb{Z} \to \mathbb{Z}$ be defined by $g(x) = 2x$. Is the composite function $f \circ g$ surjective? Is $g \circ f$ surjective?

Solution:

Part 1: Analyze $f \circ g$

Step 1: Define the composite function $f \circ g$.

Step 2: Check for surjectivity.
A function is surjective if its range equals its codomain ($\mathbb{Z}$). The range of $(f \circ g)(x) = 2x+1$ consists of all odd integers.

Step 3: Compare the range to the codomain.
The range (all odd integers) is a proper subset of the codomain (all integers). For example, there is no integer $x$ such that $2x+1 = 2$. Therefore, the function is not surjective.

Part 2: Analyze $g \circ f$

Step 1: Define the composite function $g \circ f$.

Step 2: Check for surjectivity.
The range of $(g \circ f)(x) = 2x+2$ consists of all even integers.

Step 3: Compare the range to the codomain.
The range (all even integers) is a proper subset of the codomain (all integers). For example, there is no integer $x$ such that $2x+2 = 3$. Therefore, this function is also not surjective.

Answer: Neither $f \circ g$ nor $g \circ f$ is surjective.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Let $f: A \to B$ and $g: B \to C$ be functions. If their composition $g \circ f: A \to C$ is an injective function, which of the following must be true?" options=["$f$ is injective.", "$g$ is injective.", "$f$ is surjective.", "$g$ is surjective."] answer="$f$ is injective." hint="Consider the definition of injectivity for the composite function:

. What does this imply about $f(a_1)$ and $f(a_2)$?" solution="
Step 1: State the premise.
We are given that $g \circ f$ is injective. This means that for any $a_1, a_2 \in A$:

Step 2: Expand the definition of composition.

Step 3: Analyze the implication for function $f$.
We want to prove that $f$ is injective. To do this, we must show that

.
Let us assume .

Step 4: Apply function $g$ to both sides.
If $f(a_1) = f(a_2)$, then applying the function $g$ to these equal elements must yield an equal result:

Step 5: Use the premise from Step 2.
From our premise, we know that if

, it must follow that .

Step 6: Conclude the proof for $f$.
We have successfully shown that assuming

leads to the conclusion . This is precisely the definition of an injective function. Therefore, $f$ must be injective.

(Note: $g$ is not necessarily injective. Consider $A=\{1\}, B=\{2,3\}, C=\{4\}$, with $f(1)=2$ and $g(2)=4, g(3)=4$. Here $g \circ f$ is injective, but $g$ is not.)
"
:::

:::question type="NAT" question="Let $P(S)$ denote the power set of a set $S$. Let $A$ be a finite set. A bijective function exists from $P(A)$ to the set $B = \{1, 2, 3, \dots, 1024\}$. What is the cardinality of set $A$?" answer="10" hint="Recall the formula for the cardinality of a power set. A bijection implies that the domain and codomain have equal cardinality." solution="
Step 1: Understand the relationship between bijection and cardinality.
The existence of a bijective function from a set $S_1$ to a set $S_2$ implies that their cardinalities are equal, i.e., $|S_1| = |S_2|$.

Step 2: Identify the sets and their cardinalities.
The domain is $P(A)$, the power set of $A$. The codomain is $B = \{1, 2, 3, \dots, 1024\}$.
The cardinality of the codomain is $|B| = 1024$.

Step 3: Use the bijection property to equate cardinalities.

Step 4: Use the formula for the cardinality of a power set.
The cardinality of the power set of a set $S$ with $|S|=n$ is given by $|P(S)| = 2^n$. Let $|A| = k$.

Step 5: Solve for $|A|$.
We have the equation:

We recognize that $1024$ is a power of 2.

Therefore,

.

Result:
The cardinality of set $A$ is 10.
"
:::

:::question type="MSQ" question="Let $A = \{1, 2, 3\}$ and $B = \{a, b, c, d\}$. Let $S$ be the set of all functions from $A$ to $B$. Which of the following statements is/are correct?" options=["The total number of functions in $S$ is 81.", "No function in $S$ can be surjective.", "There exists at least one function in $S$ that is injective.", "The total number of functions in $S$ is 64."] answer="No function in $S$ can be surjective.,There exists at least one function in $S$ that is injective.,The total number of functions in $S$ is 64." hint="First, calculate the cardinalities of $A$ and $B$. Then, apply the cardinality rules for the existence of injections and surjections. Use the formula for the total number of functions." solution="
Statement 1 & 4: Total number of functions
The number of functions from a set $A$ to a set $B$ is $|B|^{|A|}$.
Here, $|A| = 3$ and $|B| = 4$.
Total functions = $4^3 = 64$.
Therefore, "The total number of functions in $S$ is 64" is correct, and "The total number of functions in $S$ is 81" is incorrect.

Statement 2: Surjective functions
For a surjective function from $A$ to $B$ to exist, we must have $|A| \ge |B|$.
Here, $|A| = 3$ and $|B| = 4$. Since $3 < 4$, it is not possible to create a surjective function from $A$ to $B$. The range of any function from $A$ can have at most 3 elements, but the codomain $B$ has 4 elements. Thus, the range can never equal the codomain.
Therefore, "No function in $S$ can be surjective" is correct.

Statement 3: Injective functions
For an injective function from $A$ to $B$ to exist, we must have $|A| \le |B|$.
Here, $|A| = 3$ and $|B| = 4$. Since $3 \le 4$, an injective function can exist.
For example, we can define $f(1)=a, f(2)=b, f(3)=c$. This is a valid injective function as distinct elements in $A$ map to distinct elements in $B$.
Therefore, "There exists at least one function in $S$ that is injective" is correct.

The correct options are the ones stating that the total number of functions is 64, no function can be surjective, and at least one injective function exists.
"
:::

---

Summary

---

---

What's Next?

---

---

Part 4: Partial Orders and Lattices

Introduction

In our study of discrete mathematical structures, relations form a fundamental building block. While equivalence relations partition a set into disjoint classes, another class of relations, known as partial orders, imposes a hierarchical structure. Partial orders allow us to compare elements of a set in a way that captures notions of precedence, containment, or hierarchy, without requiring that every pair of elements be comparable. This is a natural generalization of the familiar "less than or equal to" relation on numbers.

This chapter introduces the formal definition of a partially ordered set (poset) and its standard graphical representation, the Hasse diagram. We will then explore key concepts within posets, such as bounds, maximal and minimal elements, which culminate in the definition of a lattice. A lattice is a special type of poset with a highly regular structure, ensuring that any two elements have a unique least upper bound and a unique greatest lower bound. Though not frequently tested in GATE, a firm grasp of these concepts is essential for a complete understanding of discrete structures.

---

Key Concepts

1. Hasse Diagrams

A finite poset can be represented by a directed graph. However, this graph often contains redundant information. A Hasse diagram is a simplified graphical representation that captures the essential structure of a finite poset.

To construct a Hasse diagram for a poset $(S, \preceq)$:

Start with the directed graph of the relation.

Remove all self-loops, as reflexivity is assumed for any poset.

Remove all transitive edges. An edge $(a, c)$ is transitive if there exists an element $b$ such that $a \preceq b$ and $b \preceq c$. We only keep the "covering" relations.

Arrange the vertices such that all edges point upwards. This allows us to remove the arrowheads from the edges, as the direction is implied by the vertical placement.

The resulting graph, with vertices as points and covering relations as lines, is the Hasse diagram.

Worked Example:

Problem: Let $S = \{1, 2, 3, 4, 6, 12\}$ and let the relation be divisibility, denoted by '$\mid$'. Draw the Hasse diagram for the poset $(S, \mid)$.

Solution:

Step 1: Verify that $(S, \mid)$ is a poset.

• Reflexivity: $a \mid a$ for any integer $a$. (True)


• Antisymmetry: If $a \mid b$ and $b \mid a$, then $a = b$ for positive integers $a, b$. (True)


• Transitivity: If $a \mid b$ and $b \mid c$, then $a \mid c$. (True)

Thus, $(S, \mid)$ is a poset.

Step 2: Identify the covering relations.
We draw an edge from $a$ to $b$ if $a \mid b$ and there is no $c$ (where $c \neq a, c \neq b$) such that $a \mid c$ and $c \mid b$.

• 1 covers 2, 3.


• 2 covers 4, 6.


• 3 covers 6.


• 4 covers 12.


• 6 covers 12.

Step 3: Draw the Hasse diagram.
Place the elements at different levels. The "smaller" elements (divisors) are at the bottom.

1

2

3

4

6

12

Answer: The diagram above is the Hasse diagram for the poset $(S, \mid)$.

---

2. Bounds and Lattices

Within a poset, we can analyze the relationship between elements of a subset. This leads to the concepts of upper and lower bounds.

The lub and glb, if they exist, are unique. The existence of a unique lub and glb for every pair of elements gives a poset a special structure, which we define as a lattice.

In the Hasse diagram for $(S=\{1, 2, 3, 4, 6, 12\}, \mid)$, consider the subset $A = \{4, 6\}$.

• The upper bounds are elements that are multiples of both 4 and 6. In $S$, only 12 is a multiple of both. So, the set of upper bounds is $\{12\}$. The lub is therefore 12.


• The lower bounds are elements that divide both 4 and 6. In $S$, these are 1 and 2. The set of lower bounds is $\{1, 2\}$. The greatest among these is 2. The glb is therefore 2.

Since every pair in this poset has a unique lub and glb, $(S, \mid)$ is a lattice.

---

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Let $S = \{a, b, c\}$. Which of the following relations on the power set $P(S)$ is a partial order but NOT a total order?" options=["Set Equality (=)","Set Intersection ($\cap$)","Set Union ($\cup$)","Set Subset ($\subseteq$)"] answer="Set Subset ($\subseteq$)" hint="A total order requires every pair of elements to be comparable. Consider two sets like $\{a\}$ and $\{b\}$ from $P(S)$ and check if they are comparable under the given relations." solution="Let us analyze the options for the poset $(P(S), R)$.

Set Equality (=): This is an equivalence relation, not a partial order (it is not antisymmetric in the general sense required for ordering distinct elements).

Set Intersection ($\cap$): This is an operation, not a relation of the required form.

Set Union ($\cup$): This is also an operation.

Set Subset ($\subseteq$):

- Reflexive: $A \subseteq A$ for any set $A$. (True)
- Antisymmetric: If $A \subseteq B$ and $B \subseteq A$, then $A = B$. (True)
- Transitive: If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$. (True)
Therefore, $(P(S), \subseteq)$ is a poset.

Is it a total order? A total order requires that for any two elements $X, Y \in P(S)$, either $X \subseteq Y$ or $Y \subseteq X$. Consider $X = \{a\}$ and $Y = \{b\}$. Neither $\{a\} \subseteq \{b\}$ nor $\{b\} \subseteq \{a\}$ is true. Thus, the elements are incomparable, and it is not a total order.

Hence, set subset ($\subseteq$) is the correct answer."
:::

:::question type="NAT" question="Consider the set $D_{30} = \{1, 2, 3, 5, 6, 10, 15, 30\}$ with the partial order of divisibility. What is the greatest lower bound (glb) of the set $\{10, 15\}$?" answer="5" hint="The glb of two numbers under the divisibility relation is their greatest common divisor (GCD)." solution="
Step 1: Identify the poset and the subset.
The poset is $(D_{30}, \mid)$, where $D_{30}$ is the set of divisors of 30. The subset is $A = \{10, 15\}$.

Step 2: Find the set of all lower bounds of $A$.
A lower bound $l$ must satisfy $l \mid 10$ and $l \mid 15$. In other words, we are looking for the common divisors of 10 and 15.
Divisors of 10 are $\{1, 2, 5, 10\}$.
Divisors of 15 are $\{1, 3, 5, 15\}$.
The set of common divisors (lower bounds) is $\{1, 5\}$.

Step 3: Find the greatest element in the set of lower bounds.
The set of lower bounds is $\{1, 5\}$. The greatest element in this set under the divisibility relation (or standard $\le$) is 5.

Result:
Answer: \boxed{5}
"
:::

:::question type="MSQ" question="Let $(S, \preceq)$ be the poset represented by the following Hasse diagram. The set is $S = \{a, b, c, d, e, f\}$. Which of the following statements are true?

a

b

c

d

e

f






" options=["The poset has a unique minimal element.","The lub of $\{b, c\}$ is $f$.","The poset is a lattice.","The element $a$ is the least element."] answer="The element $a$ is the least element.,The poset has a unique minimal element." hint="Analyze the structure of the diagram. A least element is one that is 'below' all others. For the lattice property, check if incomparable pairs like $\{d, e\}$ have a unique lub and glb." solution="
Let's evaluate each statement:

The poset has a unique minimal element. A minimal element has no elements below it. In the diagram, only element 'a' has no incoming edges from below. Thus, 'a' is the unique minimal element. This statement is true.

The lub of $\{b, c\}$ is $f$. The upper bounds of $\{b, c\}$ are elements that are reachable from both $b$ and $c$ by an upward path. Following the paths, we see that $d$, $e$, and $f$ are not upper bounds. In fact, there are no common upper bounds for $\{b, c\}$ in the diagram. This statement is false.

The poset is a lattice. A poset is a lattice if every pair of elements has a unique lub and a unique glb. Let's consider the pair $\{d, e\}$. The upper bounds of $\{d, e\}$ must be above both. The only element above both $d$ and $e$ is $f$. So, $lub(d, e) = f$. The lower bounds of $\{d, e\}$ must be below both. Following paths down from $d$ and $e$, we find the common lower bounds are $\{b, c, a\}$. The greatest elements in this set of lower bounds are $b$ and $c$. Since there are two 'greatest' lower bounds ($b$ and $c$ are incomparable), there is no unique glb. Therefore, the poset is not a lattice. This statement is false.

The element $a$ is the least element. A least element must be related to every other element (i.e., $a \preceq x$ for all $x \in S$). From the diagram, there is an upward path from 'a' to every other node. Thus, 'a' is the least element. This statement is true.

"
:::

---

Summary

---

What's Next?

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Let $A = \{1, 2, 3, 4\}$ and let $R$ be a relation on $A$ defined as $R = \{(x, y) \mid x, y \in A \text{ and } f(x) = f(y)\}$ for some function $f: A \to \{a, b, c\}$. Which of the following statements about $R$ must be true, regardless of the choice of $f$?" options=["$R$ is a partial order.","$R$ is an equivalence relation.","The number of ordered pairs in $R$ is at most 4.","$R$ is the identity relation, i.e., $R = \{(1,1), (2,2), (3,3), (4,4)\}.$"] answer="B" hint="Test the properties of reflexivity, symmetry, and transitivity based on the definition $f(x) = f(y)$." solution="
The relation $R$ is defined on $A$ such that $(x, y) \in R$ if and only if $f(x) = f(y)$. We must check the properties that hold for any function $f: A \to \{a, b, c\}$.

Reflexivity: For any $x \in A$, we have $f(x) = f(x)$. Therefore, $(x, x) \in R$ for all $x \in A$. The relation is reflexive.

Symmetry: Assume $(x, y) \in R$. By definition, this means $f(x) = f(y)$. Since equality is symmetric, this implies $f(y) = f(x)$. Therefore, $(y, x) \in R$. The relation is symmetric.

Transitivity: Assume $(x, y) \in R$ and $(y, z) \in R$. By definition, $f(x) = f(y)$ and $f(y) = f(z)$. Since equality is transitive, this implies $f(x) = f(z)$. Therefore, $(x, z) \in R$. The relation is transitive.

Since $R$ is reflexive, symmetric, and transitive, it is an equivalence relation. This holds true for any function $f$.

Let us examine why the other options are not necessarily true:

• A) $R$ is a partial order: A partial order must be antisymmetric. If we choose a function that is not injective, e.g., $f(1) = a$ and $f(2) = a$, then $(1, 2) \in R$ and $(2, 1) \in R$, but $1 \neq 2$. Thus, $R$ is not necessarily antisymmetric.


• C) The number of ordered pairs in $R$ is at most 4: If we choose a constant function, e.g., $f(x) = a$ for all $x \in A$, then $f(x) = f(y)$ for all pairs $(x, y)$. In this case, $R = A \times A$, and $|R| = |A|^2 = 4^2 = 16$. This is greater than 4.


• D) $R$ is the identity relation: This only occurs if the function $f$ is injective (one-to-one). However, since $|A|=4$ and the codomain has size 3, by the Pigeonhole Principle, no injective function from $A$ to $\{a, b, c\}$ exists. Therefore, $R$ can never be the identity relation in this specific case.

Thus, the only statement that must be true is that $R$ is an equivalence relation.
"
:::

:::question type="NAT" question="Let $A$ be a set with 5 elements and $B$ be a set with 3 elements. The number of surjective (onto) functions from $A$ to $B$ is ______." answer="150" hint="Use the Principle of Inclusion-Exclusion. Start with the total number of functions and subtract those that are not onto." solution="
Let $|A| = m = 5$ and $|B| = n = 3$.
The total number of functions from $A$ to $B$ is $n^m = 3^5$.

A function is surjective if every element in the codomain $B$ is mapped to by at least one element from the domain $A$. We can count the number of surjective functions using the Principle of Inclusion-Exclusion.

The formula for the number of surjective functions from a set of size $m$ to a set of size $n$ is:

Here, $m=5$ and $n=3$.

Let's calculate each term:

• Term 1: $\binom{3}{0} \cdot 3^5 = 1 \cdot 243 = 243$. (This is the total number of functions).


• Term 2: $\binom{3}{1} \cdot 2^5 = 3 \cdot 32 = 96$. (This subtracts functions that miss at least one specific element).


• Term 3: $\binom{3}{2} \cdot 1^5 = 3 \cdot 1 = 3$. (This adds back functions that miss at least two specific elements, as they were subtracted twice).


• Term 4: $\binom{3}{3} \cdot 0^5 = 1 \cdot 0 = 0$. (This subtracts functions that miss three elements, which is impossible).

Combining these results:

Therefore, the number of surjective functions from $A$ to $B$ is 150.
Answer: \boxed{150}"
:::

:::question type="MCQ" question="Consider the set of divisors of 36, $D_{36} = \{1, 2, 3, 4, 6, 9, 12, 18, 36\}$. Let the relation be 'divides', denoted by '$\mid$'. Which of the following statements about the poset $(D_{36}, \mid)$ is FALSE?" options=["The poset is a lattice.","The greatest lower bound of $\{12, 18\}$ is 6.","The least upper bound of $\{4, 9\}$ is 36.","The element 2 is a minimal element."] answer="D" hint="Recall the definitions of minimal element, GLB (meet), LUB (join), and lattice. A minimal element is one with no elements strictly smaller than it." solution="
Let us analyze the poset $(D_{36}, \mid)$. The relation is divisibility.
In this context:

• The greatest lower bound (GLB) of two numbers is their greatest common divisor (GCD).


• The least upper bound (LUB) of two numbers is their least common multiple (LCM).

We will evaluate each statement:

A) The poset is a lattice.
For any pair of elements $\{a, b\}$ in $D_{36}$, their GCD and LCM must also be in $D_{36}$. Since all elements are divisors of 36, the GCD of any two elements will also be a divisor of 36. Similarly, the LCM of any two elements that are divisors of 36 will also be a divisor of 36. For example, $LUB(\{12, 18\}) = LCM(12, 18) = 36$, which is in $D_{36}$. $GLB(\{12, 18\}) = GCD(12, 18) = 6$, which is in $D_{36}$. This holds for all pairs. Therefore, the poset is a lattice. This statement is TRUE.

B) The greatest lower bound of $\{12, 18\}$ is 6.
$GLB(\{12, 18\}) = GCD(12, 18)$. The divisors of 12 are $\{1, 2, 3, 4, 6, 12\}$. The divisors of 18 are $\{1, 2, 3, 6, 9, 18\}$. The greatest common divisor is 6. This statement is TRUE.

C) The least upper bound of $\{4, 9\}$ is 36.
$LUB(\{4, 9\}) = LCM(4, 9)$. Since $GCD(4, 9) = 1$, the $LCM(4, 9) = 4 \times 9 = 36$. This statement is TRUE.

D) The element 2 is a minimal element.
A minimal element is an element $m$ such that there is no other element $x$ in the set for which $x \mid m$ and $x \neq m$. In our set $D_{36}$, the element 1 is present. We have $1 \mid 2$ and $1 \neq 2$. Therefore, 2 is not a minimal element. The only minimal element in this poset is 1, which is also the least element. This statement is FALSE.
"
:::

:::question type="NAT" question="In a class, 40% of students enrolled for Mathematics, 70% enrolled for Computer Science. If 15% of the students enrolled for both Mathematics and Computer Science, and every student enrolled for at least one of the two subjects, what is the total number of students in the class if 35 students enrolled for Mathematics only?" answer="200" hint="Let the total number of students be $N$. Express the number of students in each category as a percentage of $N$ and use the given absolute number to solve for $N$." solution="
Let $M$ be the set of students enrolled for Mathematics and $C$ be the set of students enrolled for Computer Science. Let the total number of students in the class be $N$.

From the problem statement, we have:

• $|M| = 0.40 N$


• $|C| = 0.70 N$


• $|M \cap C| = 0.15 N$

The number of students who enrolled for Mathematics only is given by $|M| - |M \cap C|$.
We are given that this number is 35.
So, we can set up the equation:

Substituting the percentage values in terms of $N$:

The information that "every student enrolled for at least one" leads to $|M \cup C| = |M| + |C| - |M \cap C| = 0.40 N + 0.70 N - 0.15 N = 0.95 N$. If every student enrolled for at least one, then $|M \cup C| = N$, which implies $0.95 N = N$, or $0.05 N = 0$, meaning $N=0$. This is a contradiction with the existence of 35 students. We proceed by assuming this clause is an error in the problem statement, as the rest of the data is consistent and allows for a unique solution for $N$.

The total number of students in the class is 140.
Answer: \boxed{140}"
:::

---

What's Next?