Relations: Definition and Properties

Relations: Definition and Properties

A relation is a fundamental concept in mathematics and computer science that describes a connection between elements of two sets. In this topic, you will learn about the definition of relations, their properties, and how to represent them.

Definition of a Relation

A relation R from a set A to a set B is a subset of the Cartesian product A × B. The Cartesian product A × B consists of all possible ordered pairs (a, b) where a is an element of A and b is an element of B. This means that a relation can be thought of as a collection of pairs that relate elements from set A to elements from set B.

For example, let A = {1, 2, 3} and B = {a, b}. The Cartesian product A × B is:

(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)

A possible relation R could be R = {(1, a), (2, b)}. This relation indicates that 1 is related to a and 2 is related to b.

Types of Relations

Relations can be classified into different types based on their properties. The main types are:

• Reflexive Relation: A relation R on a set A is reflexive if for every element a in A, the pair (a, a) is in R. For example, if A = {1, 2}, then R = {(1, 1), (2, 2)} is reflexive.
• Symmetric Relation: A relation R is symmetric if for every pair (a, b) in R, the pair (b, a) is also in R. For example, if R = {(1, 2), (2, 1)}, then R is symmetric.
• Transitive Relation: A relation R is transitive if whenever (a, b) is in R and (b, c) is in R, then (a, c) is also in R. For example, if R = {(1, 2), (2, 3)}, then R is transitive if it also contains (1, 3).

Properties of Relations

Let R be a relation on a set A. The properties of R can be summarised as follows:

• Reflexive: For all a in A, (a, a) is in R.
• Symmetric: If (a, b) is in R, then (b, a) is in R.
• Transitive: If (a, b) is in R and (b, c) is in R, then (a, c) is in R.
• Antisymmetric: A relation R is antisymmetric if for all a, b in A, if (a, b) is in R and (b, a) is in R, then a must equal b. For example, R = {(1, 2), (2, 1)} is not antisymmetric, but R = {(1, 2), (2, 3)} is antisymmetric.

Examples of Relations

Let us consider the set A = {1, 2, 3} and define several relations on A.

Example 1: Reflexive Relation

Define R1 = {(1, 1), (2, 2), (3, 3)}. This relation is reflexive because it contains all pairs (a, a) for a in A.

Example 2: Symmetric Relation

Define R2 = {(1, 2), (2, 1)}. This relation is symmetric because it contains both (1, 2) and (2, 1).

Example 3: Transitive Relation

Define R3 = {(1, 2), (2, 3), (1, 3)}. This relation is transitive because it contains (1, 2) and (2, 3), and also contains (1, 3).

Example 4: Antisymmetric Relation

Define R4 = {(1, 2), (2, 3)}. This relation is antisymmetric because it does not contain both (a, b) and (b, a) for any a and b in A.

Graphical Representation of Relations

Relations can be represented graphically using directed graphs. In a directed graph, each element of the set is represented as a vertex. An arrow from vertex a to vertex b indicates that (a, b) is in the relation.

For example, consider the relation R = {(1, 2), (2, 3)}. The directed graph representation is:

• Vertices: 1, 2, 3
• Edges: An arrow from 1 to 2 and an arrow from 2 to 3

Matrix Representation of Relations

Relations can also be represented using matrices. For a relation R on a set A with n elements, you can create an n × n matrix M where M[i][j] = 1 if (a_i, a_j) is in R, and M[i][j] = 0 otherwise.

For example, if A = {1, 2, 3} and R = {(1, 2), (2, 3)}, the matrix M will look like this:

  1  2  3
1 0  1  0
2 0  0  1
3 0  0  0

In this matrix, the rows and columns correspond to the elements of set A. The entry M[1][2] is 1 because (1, 2) is in R, and M[2][3] is 1 because (2, 3) is in R.

Operations on Relations

There are several operations that can be performed on relations, including:

• Union: The union of two relations R1 and R2, denoted R1 ∪ R2, is the set of all pairs that are in R1 or R2 or both.
• Intersection: The intersection of two relations R1 and R2, denoted R1 ∩ R2, is the set of all pairs that are in both R1 and R2.
• Complement: The complement of a relation R, denoted R', is the set of all pairs (a, b) that are not in R.

Example of Union and Intersection

Let R1 = {(1, 2), (2, 3)} and R2 = {(2, 3), (3, 4)}. Then:

• The union R1 ∪ R2 = {(1, 2), (2, 3), (3, 4)}
• The intersection R1 ∩ R2 = {(2, 3)}

Check your understanding

1. Define a relation and give an example.
2. What are the properties of a reflexive relation?
3. How can you represent a relation using a matrix?
4. What is the difference between the union and intersection of two relations?

Summary

• A relation is a subset of the Cartesian product of two sets.
• Relations can be reflexive, symmetric, transitive, or antisymmetric.
• Relations can be represented using directed graphs or matrices.
• Operations on relations include union, intersection, and complement.