Question

Let \(X=\\{1,2,3,4,5,6\\},\) and define a relation \(R\) on \(X\) as $$R=\\{(1,2),(2,1),(2,3),(3,4),(4,5),(5,6)\\}$$ (a) Find the reflexive closure of \(R\). (b) Find the symmetric closure of \(R\). (c) Find the transitive closure of \(R\). (d) Find the reflexive and transitive closure of \(R\).

Short answer

(a) Reflexive closure: \(\{(1,2),(2,1),(2,3),(3,4),(4,5),(5,6),(1,1),(2,2),(3,3),(4,4),(5,5),(6,6)\}\); (b) Symmetric closure: \(\{(1,2),(2,1),(2,3),(3,4),(4,5),(5,6),(3,2),(4,3),(5,4),(6,5)\}\); (c) Transitive closure: \(\{(1,2),(2,1),(2,3),(3,4),(4,5),(5,6),(1,3),(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,5),(3,6),(4,6)\}\); (d) Reflexive and transitive closure: \(\{(1,2),(2,1),(2,3),(3,4),(4,5),(5,6),(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(1,3),(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,5),(3,6),(4,6)\}\)

Step-by-step solution

Define Reflexive Closure

The reflexive closure of a relation \(R\) on a set \(X\) includes every element relating to itself in the form \((x, x)\) where \(x \in X\). For the given set \(X = \{1, 2, 3, 4, 5, 6\}\), add the missing reflexive pairs \((1,1), (2,2), (3,3), (4,4), (5,5), (6,6)\) to \(R\). Therefore, the reflexive closure \(R_r\) is: \[R_r = R \cup \{(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)\}\]

Determine Symmetric Closure

The symmetric closure of a relation \(R\) includes both \((a, b)\) and \((b, a)\) for every element in \(R\). For \(R=\{(1,2), (2,1), (2,3), (3,4), (4,5), (5,6)\}\), ensure all symmetric pairs exist: \((2, 3)\) needs \((3, 2)\), \((3, 4)\) needs \((4, 3)\), \((4, 5)\) needs \((5, 4)\), and \((5, 6)\) needs \((6, 5)\). The symmetric closure \(R_s\) is: \[R_s = R \cup \{(3, 2), (4, 3), (5, 4), (6, 5)\}\]

Find Transitive Closure

The transitive closure of a relation is constructed by adding relations such that if \((a, b)\) and \((b, c)\) are in the union, then \((a, c)\) is also included. Repeatedly apply this rule to \(R\). First, since \((1,2)\) and \((2,3)\) exist, add \((1,3)\). Then, \((2,3)\) and \((3,4)\) implies \((2,4)\). Continue until no new pairs can be added: \[R_t = R \cup \{(1, 3), (1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 5), (3, 6), (4, 6)\}\]

Calculate Reflexive and Transitive Closure

This closure is obtained by combining reflexive and transitive properties. Start with the reflexive closure of \(R\) and apply transitive closure. Using \(R_r\) from step 1 and applying transitivity rule, ensure all possible transitive links are present. The closure \(R_{rt}\) is: \[R_{rt} = R_t \cup \{(1,1), (2,2), (3,3), (4,4), (5,5), (6,6)\}\]

Key concepts

Set Theory

Set theory is a branch of mathematical logic that studies sets, which are collections of objects. Sets can contain numbers, people, letters, or any other well-defined items. There are several key concepts and operations associated with set theory, including:

• Subsets: A set "A" is a subset of a set "B" if every element of "A" is also an element of "B".
• Union: The union of two sets consists of all elements that are in either set.
• Intersection: The intersection of two sets consists of all elements that are in both sets.
• Empty Set: A set with no elements, often denoted by \(\emptyset\).

Understanding these basic concepts helps in grasping more complex structures like relations and their closures as seen in discrete mathematics.

Relations

In discrete mathematics, a relation from a set \(X\) to a set \(Y\) is a collection of ordered pairs (a, b) where \(a\) is an element of \(X\) and \(b\) is an element of \(Y\). A relation on a set \(X\) is particularly understood as a subset of the Cartesian product \(X \times X\).For example, given the set \(X = \{1, 2, 3, 4, 5, 6\}\), a relation can be expressed as a set of ordered pairs from this set and has properties such as reflexivity, symmetry, and transitivity. Each of these properties can be explored to find closures, which are minimal expansions of the relation maintaining the property.

Reflexive Closure

The reflexive closure of a relation \(R\) on a set \(X\) is the smallest reflexive relation that contains \(R\). To make \(R\) reflexive, it must include every possible pair \((x, x)\) where \(x\) is an element of \(X\).This means that for any relation \(R\) given on a set \(X\), reflexive closure would be found by adding all the pairs \((x, x)\) that are not already present in \(R\). Therefore, if \(R\) originally lacks pairs like \((1, 1)\) or \((2, 2)\), these must be added to achieve the reflexive closure.

Symmetric Closure

The symmetric closure of a relation \(R\) means including both \((a, b)\) and \((b, a)\) for any pair in the relation. This closure ensures that if you can travel from one element to another, there is also a direct path back.For instance, if the relation consists of the pair \((3, 4)\), then its symmetric closure must also contain \((4, 3)\). Symmetric closure ensures that all direct connections have their mirrors within the relation, maintaining bidirectional travel between related elements.

Transitive Closure

A transitive closure of relation \(R\) is achieved by ensuring that whenever \((a, b)\) and \((b, c)\) are in \(R\), the pair \((a, c)\) is also in the relation. This property is useful for understanding indirect connections.To build the transitive closure, you iteratively add all necessary pairs until no further pairs can be added without breaking the transitive property. For example, if \((1, 2)\) and \((2, 3)\) are in the relation, then \((1, 3)\) must be added to form the transitive closure.The goal is to connect all indirectly related entities through a direct path, creating a chain of relations that becomes complete and unbroken.