Question #218080

Let R and S be relations on X. Determine whether each statement is true or false. If the statement is true, prove it; otherwise, give a counterexample.

 

1.     If R is transitive, then R−1 is transitive.

2.     If R and S are reflexive, then R ◦ S is reflexive

3.     If R and S are symmetric, then R ∩ S is symmetric.

4.     If R and S are antisymmetric, then R ∪ S is antisymmetric.

5.     If R is antisymmetric, then R−1 is antisymmetric.



1
Expert's answer
2021-07-20T11:24:58-0400

Solution:

1.      Yes, R1R^{-1} is transitive.

It is given that R is transitive.

Let (a,b)R1 and (b,c)R1(a, b) \in R^{-1}\ and\ (b, c) \in R^{-1} .

By the definition of the inverse relation:

 (b,a)R(c,b)R\begin{aligned} &(b, a) \in R \\ &(c, b) \in R \end{aligned}  

Since R is transitive:

 (c,a)R(c, a) \in R  

By the definition of the inverse relation.

 (a,c)R1(a, c) \in R^{-1}  

Since (a,b)R1 and (b,c)R1    (a,c)R1,R1(a, b) \in R^{-1}\ and\ (b, c) \in R^{-1} \implies (a, c) \in R^{-1}, R^{-1} is transitive.

2. Let aAa \in A

Since R is reflexive:

(a,a)R(a, a) \in R

Since S is reflexive:

(a,a)S(a, a) \in S

By the definition of the composite, if (a,a)R and (a,a)S(a, a) \in R\ and\ (a, a) \in S , then:

(a,a)RS(a, a) \in R \circ S

Be the definition of reflexive, RSR \circ S is then reflexive (as we know that(a,a)RS(a, a) \in R \circ S for every element aAa \in A ).

3. Let a,bAa, b \in A such that (a,b)RS(a, b) \in R \cap S . Then,

(a,b)RS(a, b) \in R \cap S

(a,b)R and (a,b)S\Rightarrow(a, b) \in R\ and\ (a, b) \in S

(b,a)R and (b,a)S\Rightarrow(b, a) \in R\ and\ (b, a) \in S \quad [ Since R and S are symmetric]

(b,a)RS\Rightarrow(b, a) \in R \cap S

Thus,

(a,b)RS(a, b) \in R \cap S

(b,a)RSa,bA\Rightarrow(b, a) \in R \cap S \forall a, b \in A

So, RSR \cap S is symmetric on A.

4.

If R and S are antisymmetric, then R ∪ S is antisymmetric. We disprove the statement.

(1) Let T = {a, b}, R = {(a, b)}, and S = {(b, a)}.

(2). R and S are antisymmetric. (Defn. of antisymmetric)

(3). R ∪ S = {(a, b),(b, a)}. (Defn. of ∪)

(4). ∃a, b,(a, b) ∈ R ∪ S ∧ (b, a) ∈ R ∪ S ∧ a 6= b. (Step 3)

(5). R ∪ S is not antisymmetric. (Step 4 and defn. of antysymmetric)

5.

To prove: If relation R is antisymmetric then R−1 is antisymmetric.

1. Let R ⊆ S × S be antisymmetric, for arbitrary set S.

2. Assume that R−1 is not antisymmetric. (Proof by contradiction)

3. ∃x, y ∈ S, xR−1 y ∧ yR−1x ∧ x \ne y. (Step 2 and defn. of antisymmetry)

4. ∃x, y ∈ S, xRy ∧ yRx ∧ x \ne y. (Step 3 and defn. of R−1 )

5. R is not antisymmetric, contradicting step 1. (Steps 4 and defn. of antisymmetry)

6. The assumption of step 2 is false: R−1 is antisymmetric.


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!
LATEST TUTORIALS
APPROVED BY CLIENTS