Types of Relations in Discrete Mathematics: Reflexive, Irreflexive, Symmetric, Antisymmetric, and Transitive

Explore key properties of relations in discrete mathematics: reflexive, irreflexive, symmetric, antisymmetric, and transitive. This tutorial provides formal definitions, illustrative examples, and demonstrates how to determine if a given relation satisfies these properties, forming a foundation for understanding relations and their classifications.

Types of Relations in Discrete Mathematics

1. Reflexive Relations

A relation R on a set A is reflexive if every element in A is related to itself. Formally: For every a ∈ A, (a, a) ∈ R.

Example: Reflexive Relation

Let A = {1, 2, 3, 4}. Is R = {(1, 1), (2, 2), (1, 3), (2, 4), (3, 3), (3, 4), (4, 4)} reflexive?

Yes, because (1, 1), (2, 2), (3, 3), and (4, 4) are all in R.

2. Irreflexive Relations

A relation R on a set A is irreflexive if no element in A is related to itself. Formally: For every a ∈ A, (a, a) ∉ R.

Example: Irreflexive Relation

Let A = {1, 2, 3}. Is R = {(1, 2), (2, 2), (3, 1), (1, 3)} irreflexive?

No, because (2, 2) ∈ R.

3. Symmetric Relations

A relation R on a set A is symmetric if whenever (a, b) is in R, then (b, a) is also in R. Formally: (a, b) ∈ R ⟺ (b, a) ∈ R.

Example: Symmetric Relation

Let A = {1, 2, 3}. Is R = {(1, 1), (2, 2), (1, 2), (2, 1), (2, 3), (3, 2)} symmetric?

Yes, because for every pair (a, b) in R, (b, a) is also in R.

(Examples of symmetric relations: perpendicularity and parallelism of lines.)

4. Antisymmetric Relations

A relation R on a set A is antisymmetric if whenever (a, b) and (b, a) are both in R, then a = b. Formally: If (a, b) ∈ R and (b, a) ∈ R, then a = b.

Examples: Antisymmetric Relations

(Two examples illustrating antisymmetric and non-antisymmetric relations are provided in the original text and should be included here.)

5. Asymmetric Relations

A relation R on a set A is asymmetric if whenever (a, b) is in R, then (b, a) is not in R. Formally: (a, b) ∈ R implies (b, a) ∉ R.

6. Transitive Relations

A relation R on a set A is transitive if whenever (a, b) and (b, c) are in R, then (a, c) is also in R. Formally: If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.

Example: Transitive Relation

(An example showing a transitive relation, along with an explanation, is provided in the original text and should be included here. Examples of transitive relations (≤, ⊆, divisibility) and non-transitive relations (perpendicularity) should be given.)

7. Identity Relation

The identity relation I on a set A is defined as I = {(a, a) | a ∈ A}. It's reflexive, symmetric, and transitive (and therefore an equivalence relation).

Example: Identity Relation

For A = {1, 2, 3}, the identity relation is {(1, 1), (2, 2), (3, 3)}.

8. Void (Empty) Relation

The void relation on a set A is the empty set, Ø. It's symmetric and transitive but not reflexive.

9. Universal Relation

The universal relation R on sets A and B is R = A x B (the Cartesian product of A and B). It's reflexive, symmetric, and transitive (and therefore an equivalence relation).

Conclusion

These types of relations are fundamental building blocks in discrete mathematics, forming the basis for understanding more complex relationships and structures within sets.