Answer to Question #218080 in Discrete Mathematics for Josh

Question

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⁻¹ 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⁻¹ is antisymmetric.

Answer 1

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⁻¹ is antisymmetric.

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

2. Assume that R⁻¹ is not antisymmetric. (Proof by contradiction)

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

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

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

6. The assumption of step 2 is false: R⁻¹ is antisymmetric.