Problem 8 - Applied Discrete Structures

Question

(a) Prove that if \(r\) is a transitive relation on a set \(A,\) then \(r^{2} \subseteq r\) (b) Find an example of a transitive relation for which \(r^{2} \neq r\).

Step-by-Step Solution

Answer

(a) If \( r \) is transitive, then \( r^2 \subseteq r \). (b) Example: \( A = \{1, 2, 3\} \), \( r = \{(1, 2), (2, 3)\} \), initially \( r^2 \neq r \).

Step 1: Understanding Transitive Relations

A relation \( r \) on a set \( A \) is called transitive if for all \( a, b, c \in A \), whenever \( (a, b) \in r \) and \( (b, c) \in r \), it follows that \( (a, c) \in r \). Our task is to show that if \( r \) is transitive, then the set of all elements in \( r^2 \) is a subset of \( r \).

Step 2: Define r^2

The relation \( r^2 \) consists of all pairs \( (a, c) \) for which there exists an element \( b \in A \) such that \( (a, b) \in r \) and \( (b, c) \in r \). This is the composition of \( r \) with itself.

Step 3: Prove r^2 is a Subset of r

Assume \( (a, c) \in r^2 \). By definition of \( r^2 \), there exists a \( b \) such that \( (a, b) \in r \) and \( (b, c) \in r \). Using the transitivity of \( r \), since both \( (a, b) \) and \( (b, c) \) are in \( r \), it follows that \( (a, c) \) must also be in \( r \). Therefore, every pair in \( r^2 \) is also in \( r \), which means \( r^2 \subseteq r \).

Step 4: Identify the Requirement for r^2 ≠ r

For \( r^2 eq r \), we need a situation where \( r \) includes pairs such that \( (a, c) \) is not initially in \( r \) but added due to transitivity.

Step 5: Example of a Transitive Relation Where r^2 ≠ r

Consider a set \( A = \{ 1, 2, 3 \} \) and let \( r = \{ (1, 2), (2, 3) \} \). Check transitivity: by definition, since \( (1, 2) \) and \( (2, 3) \) are in \( r \), transitivity requires \( (1, 3) \) to be added to \( r \), making it a transitive closure. Hence, initially \( r^2 = \{ (1, 3) \} eq r \). So, after transitive closure, \( r = \{ (1, 2), (2, 3), (1, 3) \} \).

Key Concepts

Subset

A subset is one of the fundamental concepts in set theory. When we say a set \(B\) is a subset of a set \(A\) (denoted as \(B \subseteq A\)), it means that every element of \(B\) is also an element of \(A\).
This is crucial in understanding why \( r^2 \subseteq r\) when \(r\) is a transitive relation. Here, \(r^2\) is derived by composing \(r\) with itself, taking pairs from \(r\) to form new pairs. Given the transitivity of \(r\), these newly formed pairs must also belong within \(r\). Therefore, every element of \(r^2\) is indeed contained in \(r\).
For example, if \(r\) consists of items like \((a, b)\) and \((b, c)\), then composing these within \(r^2\) leads to \((a, c)\). Due to the transitive nature of \(r\), it's guaranteed that \((a, c)\) will also reappear in the original relation \(r\). Hence, \(r^2\) cannot introduce anything that’s outside of \(r\) and must be a subset.

Relation Composition

Relation composition is a way of combining two relations to form a new relation. Given two relations \(r\) and \(s\) on a set \(A\), the composition \(r \circ s\) consists of pairs \((a, c)\) such that there exists an element \(b\) making \((a, b) \in r\) and \((b, c) \in s\).
This plays a vital role when dealing with transitive relations. In our specific case, where we investigate \(r^2\), which is \(r\) composed with itself. Simply put, for any \((a, c) \in r^2\), there must be an intermediary \(b\) such that the journey from \(a\) to \(b\) and then \(b\) to \(c\) is fully described within \(r\).
Think of it as a pathway where the nodes (or steps) between \(a\) and \(c\) are accounted for within the relation. Under the definition of a transitive relation, \(r\), this pathway is automatically validated, ensuring that any short-cut added by \(r^2\) naturally exists in \(r\) itself.

Transitive Closure

The transitive closure of a relation \(r\) on a set \(A\) is the smallest transitive relation on \(A\) that contains \(r\). In simpler terms, it's about filling in the gaps that transitivity requires by adding any missing direct connections between elements.
To determine the transitive closure, consider all pairs of elements where transitiveness forces new connections. Establish any new relations that allow indirect paths to become direct. In mathematical terms, it involves securing that for any object combinations \((a, b)\) and \((b, c)\), the pair \((a, c)\) is directly included.
For example, let's consider a scenario with a set \(A = \{1, 2, 3\}\). If \(r = \{(1, 2), (2, 3)\}\), transitivity implies \((1, 3)\) should be included. So initially \((1, 3)\) isn't there, making \(r\) non-transitive before closure. Completing the transitive closure transforms \(r\) into \(\{(1, 2), (2, 3), (1, 3)\}\), by directly incorporating the link \((1, 3)\), fully satisfying the transitive property.