• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q52E

Expert-verified Found in: Page 583 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Show that the relation $$R$$ on a set $$A$$ is antisymmetric if and only if $$R \cap {R^{ - 1}}$$ is a subset of the diagonal relation $$\Delta = \{ (a,a)\mid a \in A\}$$.

$$R$$ is antisymmetric if and only if $$R \cap {R^{ - 1}} \subseteq \Delta$$

See the step by step solution

## Step 1: Given Data

Given: Relation $$R$$ on a set $$A$$ and $${R^{ - 1}}$$ is the inverse relation of $$R$$.

$$\Delta = \{ (a,a)\mid a \in A\}$$

## Step 2: Concept of the antisymmetric, inverse relation and Intersection

Antisymmetric: A relation $$R$$ on a set $$A$$is antisymmetric if $$(b,a) \in R$$ and $$(a,b) \in R$$ implies $$a = b$$

The inverse relation: $${R^{ - 1}}$$ is the set $$\{ (b,a)\mid (a,b) \in R\}$$

Intersection $$A \cap B$$: All elements that are both in $$A$$ AND in $$B$$.

## Step 3: Proof that $$R \cap {R^{ - 1}} \subseteq \Delta$$

First part Let us assume that $$R$$ is antisymmetric.

If $$R \cap {R^{ - 1}}$$ is the empty set, then $$R \cap {R^{ - 1}}$$ is a subset of $$\Delta$$ (since the empty set is a subset of all sets).

Let us assume that $$R \cap {R^{ - 1}}$$ is not empty and let $$(a,b) \in R \cap {R^{ - 1}}$$.

An element is in the intersection, if the element is in both sets:

$$\begin{array}{l}(a,b) \in R\\(a,b) \in {R^{ - 1}}\end{array}$$

By the definition of the inverse relation

$$(b,a) \in R$$

We then know that $$(a,b) \in R$$and $$(b,a) \in R$$. Since $$R$$ is antisymmetric:

$$a = b$$

We then know that $$R \cap {R^{ - 1}}$$ only contains elements of the form $$(a,a)$$. Since $$(a,a) \in \Delta$$ :

$$R \cap {R^{ - 1}} \subseteq \Delta$$

## Step 4: Proof that $$R$$ is antisymmetric

Second part Let us assume that $$R \cap {R^{ - 1}} \subseteq \Delta$$. Let $$(a,b) \in R$$ and $$(b,a) \in R$$.

Since $${R^{ - 1}} = \{ (b,a)\mid (a,b) \in R\}$$

$$\begin{array}{l}(a,b) \in {R^{ - 1}}\\(b,a) \in {R^{ - 1}}\end{array}$$

An element is in the intersection if it is in both subsets:

$$\begin{array}{l}(a,b) \in R \cap {R^{ - 1}}\\(b,a) \in R \cap {R^{ - 1}}\end{array}$$

Since $$R \cap {R^{ - 1}} \subseteq \Delta$$

$$\begin{array}{l}(a,b) \in {\rm{ Delta }}\\(b,a) \in {\rm{ Delta }}\end{array}$$

Since $$\Delta = \{ (a,a)\mid a \in A\}$$

$$a = b$$

$$R$$ is antisymmetric.

If $$R$$ is antisymmetric, then $$R \cap {R^{ - 1}} \subseteq \Delta$$ and If $$R \cap {R^{ - 1}} \subseteq \Delta$$, then $$R$$ is antisymmetric.

This is equivalent with $$R$$ is antisymmetric if and only if $$R \cap {R^{ - 1}} \subseteq \Delta$$ ### Want to see more solutions like these? 