StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q52E

Expert-verifiedFound in: Page 583

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 \)

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

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

**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\).**

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 \)

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 \)

94% of StudySmarter users get better grades.

Sign up for free