Question

Let \(R, S,\) and \(T\) be binary relations on a set \(X\). (a) Prove that \(R \subseteq S\) if and only if \(R^{-1} \subseteq S^{-1}\). (b) Prove that if \(R \subseteq S,\) then \(R \circ T \subseteq S \circ T\) and \(T \circ R \subseteq T \circ S\). (c) If \(R \circ T \subseteq S \circ T\) and \(T \circ R \subseteq T \circ S\) for some relation \(T\), does it follow that \(R \subseteq S ?\)

Short answer

(a) \(R^{-1} \subseteq S^{-1}\) iff \(R \subseteq S.\) (b) \(R \subseteq S\) implies \(R \circ T \subseteq S \circ T\) and \(T \circ R \subseteq T \circ S\). (c) No, it does not necessarily follow.

Step-by-step solution

Understand the Definitions

Recall that if \(R, S,\) and \(T\) are relations on a set \(X\), we say \(R \subseteq S\) if for every \((x, y) \in R\), \((x, y) \in S\). The inverse of a relation \(R\), denoted \(R^{-1}\), contains the pair \((y, x)\) if \((x, y) \in R\). The composition \(R \circ T\) contains \((x, z)\) if there exists \(y\) such that \((x, y) \in R\) and \((y, z) \in T\).

Prove (a): \(R \, \subseteq S\) if and only if \(R^{-1} \, \subseteq S^{-1}\)

Assume \(R \subseteq S\). Then for every \((x, y) \in R\), \((x, y) \in S\). Thus, \((y, x) \in R^{-1}\) implies \((y, x) \in S^{-1}\), hence \(R^{-1} \subseteq S^{-1}\). Conversely, assume \(R^{-1} \subseteq S^{-1}\). Then for every \((y, x) \in R^{-1}\), \((y, x) \in S^{-1}\). Thus, \((x, y) \in R\) implies \((x, y) \in S\), hence \(R \subseteq S\).

Prove (b): \(R \, \subseteq S\) implies \(R \circ T \, \subseteq S \circ T\) and \(T \circ R \, \subseteq T \circ S\)

Assume \(R \subseteq S\). Take any \((x, z) \in R \circ T\). There exists a \(y\) such that \((x, y) \in R\) and \((y, z) \in T\). Since \(R \subseteq S\), \((x, y) \in S\). Hence, \((x, z) \in S \circ T\), proving \(R \circ T \subseteq S \circ T\). Similarly, for \(T \circ R\), take \((z, x) \in T \circ R\). There exists a \(y\) such that \((z, y) \in T\) and \((y, x) \in R\). Since \(R \subseteq S\), \((y, x) \in S\). Hence, \((z, x) \in T \circ S\), proving \(T \circ R \subseteq T \circ S\).

Prove (c): Determine if \(R \circ T \subseteq S \circ T\) and \(T \circ R \subseteq T \circ S\) implies \(R \subseteq S\)

Suppose \(R \circ T \subseteq S \circ T\) and \(T \circ R \subseteq T \circ S\). Consider counter-examples where \(R\) and \(S\) differ outside their compositions with a specific \(T\). For example, if \(X = \{a, b, c\}\), \(R = \{(a, b)\}\), \(S = \{(a, c)\}\), and \(T = \{(b, c)\}\), we can have \(R \circ T = S \circ T = \{(a, c)\}\) and \(T \circ R = T \circ S = \emptyset\), but \(R ot\subseteq S\). This shows the condition does not necessarily hold.

Key concepts

Binary Relations

Binary relations are an essential concept in discrete mathematics. At their core, binary relations involve pairs of elements. Imagine a set, say, \(X\). A binary relation \(R\) on \(X\) is simply a collection of ordered pairs \((x, y)\) where both \(x\) and \(y\) are elements of \(X\).

To visualize, consider any two elements \(a\) and \(b\) in a set of people. If "likes" is our relation \(R\), then \((a, b)\) in \(R\) might mean "a likes b". This creates a direct, binary connection between the two elements, forming the relationship.

Binary relations can express various interactions and associations, such as equality, order, and more, within a specific set. Importantly, we often explore how one relation compares or overlaps with another, typically using subset notation \(R \subseteq S\), which indicates all pairs in \(R\) are also in another relation \(S\).

Relation Inverses

An inverse relation can be thought of as flipping the direction of a relationship. If you have a relation \(R\), its inverse, denoted \(R^{-1}\), involves swapping every pair's elements so that \((x, y)\) becomes \((y, x)\).

This concept can be applied remember our earlier example where "a likes b." In the inverse relation, it would be represented as "b likes a."

A critical property of relation inverses is that if one entire relation is a subset of another, then their inverses also maintain this subset condition. Specifically, if \(R \subseteq S\), then \(R^{-1} \subseteq S^{-1}\). This is intuitive because reversing a subset still retains the order and inclusion of elements in relation to each other.

Relation Composition

In relation composition, two relations get combined to form a new connection between different elements. Suppose \(R\) and \(T\) are two relations. The composition of \(R\) and \(T\), notated as \(R \circ T\), links elements \(x\) to \(z\) if there exists an intermediary \(y\) such that \((x, y) \in R\) and \((y, z) \in T\).

This concept is useful when you wish to establish more complex interactions. For example, if \(R\) is a relation indicating friendships \((a, b) \in R\) means "a knows b," and \(T\) represents events only friends attend, \((b, c) \in T\). Then, \(R \circ T\) would show who ultimately connects through friendship to attend events.

Importantly, if one relation is covered by another \((R \subseteq S)\), then their compositions with any third relation \(T\) will follow the same inclusion pattern: \(R \circ T \subseteq S \circ T\) and \(T \circ R \subseteq T \circ S\), illustrating how composition maintains the subset hierarchy.

Subset Relations

Subset relations speak to the inclusion or hierarchy between different sets or, in this context, different relations. When we denote \(R \subseteq S\), it means every pair belonging to relation \(R\) is also found in \(S\). This hierarchical view applies similarly to relations, ensuring any transformation or operation like inverses or compositions honors this foundational structure.

It's crucial to understand how operations influence these relations. An action like composing with a third relation, \(T\), may not always preserve the original relation's identity. For instance, even if \(R \circ T = S \circ T\) or \(T \circ R = T \circ S\), it might not necessarily mean \(R\) is a subset of \(S\).

This highlights the importance of careful analysis to determine how and when one relation is genuinely encompassed by another. Subset relations provide a simple yet powerful way to understand the connection structures within sets and their relations.