Solution to Let R and S be relations on X. Determine whether each statement is true or … - Sikademy
Author Image

Archangel Macsika

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.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

Solution:

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

It is given that R is transitive.

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

By the definition of the inverse relation:

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

Since R is transitive:

 (c, a) \in R  

By the definition of the inverse relation.

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

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

2. Let a \in A

Since R is reflexive:

(a, a) \in R

Since S is reflexive:

(a, a) \in S

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

(a, a) \in R \circ S

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

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

(a, b) \in R \cap S

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

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

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

Thus,

(a, b) \in R \cap S

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

So, R \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.


Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-2780-qpid-1337