Here is a clear, complete, and exam-oriented explanation of Introduction to Relations in Discrete Structures.
⭐ Introduction to Relations
A relation is a fundamental concept in discrete mathematics, computer science, and database theory.
It describes how elements of one set are related to elements of the same or another set.
✔️ Formal Definition
Let A and B be two sets.
A relation R from A to B is defined as:
[
R \subseteq A \times B
]
That means:
- A relation is a subset of the Cartesian product of A and B.
- A relation consists of ordered pairs (a, b) where
( a \in A ) and ( b \in B ), and a is related to b.
Example:
Let
A = {1, 2, 3}
B = {x, y}
A relation R from A to B may be:
[
R = {(1,x), (2,y)}
]
Here,
- 1 is related to x
- 2 is related to y
⭐ Relation on a Set (A to A)
If A = B, then relation is called a relation on set A.
Example:
A = {1, 2, 3}
Possible relation R:
[
R = {(1,1), (2,3), (3,3)}
]
⭐ How Relation is Formed?
Steps:
- Take two sets A and B
- Form all ordered pairs (Cartesian product)
- Choose any subset of A × B — this subset is a relation
⭐ Types of Relations (Overview)
These come after introduction, but listing them helps:
- Reflexive Relation
- Symmetric Relation
- Transitive Relation
- Equivalence Relation
- Antisymmetric Relation
- Partial Order Relation
(You can ask for detailed explanation of these.)
⭐ Representation of Relations
Relations can be represented in several ways:
1. Set of Ordered Pairs
Example:
R = {(1,2), (2,3), (3,3)}
2. Arrow Diagram
Draw arrows from elements of A to B.
3. Matrix Representation
If A = {a₁, a₂} and B = {b₁, b₂}, then relation can be shown as:
| b₁ | b₂ | |
|---|---|---|
| a₁ | 1 | 0 |
| a₂ | 0 | 1 |
1 means related; 0 means not related.
4. Directed Graph (Digraph)
For relations on a set A, we use nodes and directed edges.
⭐ Real-Life Examples of Relations
✔ Student–Course Relation
R = {(student, course)}
✔ Employee–Manager Relation
(employee, manager)
✔ Precedence Relation (≤)
(2 ≤ 5)
✔ Database table rows
Each row is a set of related values → a relation.
⭐ Domain and Range of a Relation
For a relation
[
R \subseteq A \times B
]
- Domain(R): all first elements of ordered pairs
- Range(R): all second elements of ordered pairs
Example:
R = {(1,2), (3,4), (5,2)}
Domain = {1, 3, 5}
Range = {2, 4}
⭐ Important Observations
- A relation can contain any number of ordered pairs
- It can be empty
- Maximum number of relations from A to B is:
[
2^{|A| \times |B|}
]