Definition : A relation R on a set A is called reflexive if (a, a) ∈ R for every element a ∈ A
Using quantifiers we see that the relation R on the set A is reflexive if ∀a((a, a) ∈ R),
where the universe of discourse is the set of all elements in A
A relation R on a set A is called symmetric if(b, a) ∈ R whenever(a, b) ∈ R, for all a, b ∈ A.
A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b
is called antisymmetric.
Remark: Using quantifiers, we see that the relation R on the set A is symmetric if
∀a∀b((a, b) ∈ R → (b, a) ∈ R). Similarly, the relation R on the set A is antisymmetric if
∀a∀b(((a, b) ∈ R ∧ (b, a) ∈ R) → (a = b)).
That is, a relation is symmetric if and only if a is related to b implies that b is related to a.
A relation is antisymmetric if and only if there are no pairs of distinct elements a and b with a
related to b and b related to a. That is, the only way to have a related to b and b related to a is
for a and b to be the same element. The terms symmetric and antisymmetric are not opposites,
because a relation can have both of these properties or may lack both of them (see Exercise
10). A relation cannot be both symmetric and antisymmetric if it contains some pair of the form
(a, b), where a = b.
Using quantifiers we see that the relation R on the set A is reflexive if ∀a((a, a) ∈ R),
where the universe of discourse is the set of all elements in A
A relation R on a set A is called symmetric if(b, a) ∈ R whenever(a, b) ∈ R, for all a, b ∈ A.
A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b
is called antisymmetric.
Remark: Using quantifiers, we see that the relation R on the set A is symmetric if
∀a∀b((a, b) ∈ R → (b, a) ∈ R). Similarly, the relation R on the set A is antisymmetric if
∀a∀b(((a, b) ∈ R ∧ (b, a) ∈ R) → (a = b)).
That is, a relation is symmetric if and only if a is related to b implies that b is related to a.
A relation is antisymmetric if and only if there are no pairs of distinct elements a and b with a
related to b and b related to a. That is, the only way to have a related to b and b related to a is
for a and b to be the same element. The terms symmetric and antisymmetric are not opposites,
because a relation can have both of these properties or may lack both of them (see Exercise
10). A relation cannot be both symmetric and antisymmetric if it contains some pair of the form
(a, b), where a = b.
A relation R on a set A is called transitive if whenever (a, b) ∈ R and (b, c) ∈ R,
then (a, c) ∈ R, for all a, b, c ∈ A.
Consider the following relations on {1, 2, 3, 4}:
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1)},
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)},
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)},
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)},
R6 = {(3, 4)}.
Reference
Discrete Mathematics and Its Applications - Seventh Edition
Kenneth H. Rosen
No comments:
Post a Comment