Question

Find the reflexive, symmetric, and transitive closures of the following relations: \((a)=\) on \(\mathbb{N}\) (b) \(<\) on \(\mathbb{N}\) (c) \(\leq\) on \(\mathbb{N}\) (d) \(R\) on \(\mathbb{N}\) where \(R(x, y)\) if and only if \(y=x+1\) (e) \(R\) on \(\mathbb{R}\) where \(R(x, y)\) if and only if \(y=x+1\) (f) \(R\) on \(\mathbb{R}\) where \(R(x, y)\) if and only if \(|x-y|<0.0005\).

Short answer

Most reflexive closures involve adding pairs \((a,a)\); some symmetric and transitive closures do not exist without contradictions.

Step-by-step solution

Reflexive Closure for Equality

Equality (a) is already reflexive because for any natural number \( n \), \( n = n \) is true.

Symmetric Closure for Equality

Equality is symmetric since if \( a = b \), then \( b = a \). Therefore, no changes are needed.

Transitive Closure for Equality

Equality is also transitive because if \( a = b \) and \( b = c \), then \( a = c \). Thus, no changes are necessary.

Reflexive Closure for Less Than

To make less than \((<)\) reflexive, we must add pairs \((a, a)\) for every \(a \in \mathbb{N}\), even though typically \((a, a)\) is not part of \(<\).

Symmetric Closure for Less Than

Less than is not inherently symmetric. In fact, adding symmetry would result in contradictions; therefore, symmetric closure does not exist in standard terms for \(<\).

Transitive Closure for Less Than

The relation was already transitive since if \( a < b \) and \( b < c \), then \( a < c \). Thus, no changes are needed.

Reflexive Closure for Less Than or Equal

The relation \( \leq \) is already reflexive because \( a \leq a \).

Symmetric Closure for Less Than or Equal

Less than or equal is not symmetric in its standard form as neither \( a \leq b \) implies \( b \leq a \). A symmetric closure would be the complete relation, which does not adhere to standard constraints.

Transitive Closure for Less Than or Equal

The relation \( \leq \) is transitive because if \( a \leq b \) and \( b \leq c \), then \( a \leq c \).

Reflexive Closure for Successor Function on Natural Numbers

Add pairs \((a, a)\) for reflexivity to the successor relation \( R(x, y) \), even though it fundamentally represents \( y = x + 1 \).

Symmetric Closure for Successor Function on Natural Numbers

In a typical natural number succession, symmetry results in contradictions (e.g., \( x \rightarrow x+1 \) cannot be reversed). Symmetric closure does not meaningfully exist here.

Transitive Closure for Successor Function on Natural Numbers

Chain successes: for this to be transitive, allow hops such that if \( y = x+1 \) and \( z = y+1 \), making \( z = x+2 \) valid, and continue this pattern.

Reflexive Closure for Successor Function on Real Numbers

As with natural numbers, to reflexively close \( R(x, y) = (y = x+1) \), include \((a, a)\) for all \( a \in \mathbb{R} \).

Symmetric Closure for Successor Function on Real Numbers

Real numbers do not allow symmetry since \( y = x + 1 \) cannot revert to \( x = y + 1 \). Hence, symmetry results in contradictions.

Transitive Closure for Successor Function on Real Numbers

Transitive closure would require identifying all sequences increasing by 1 (e.g., \( z = x+2, z = x+3, \ldots \)).

Reflexive Closure for Close Approximation Relation on Real Numbers

Ensure every real number \( x \) is related to itself, covering reflexivity by adding \( |x-x| < 0.0005 \).

Symmetric Closure for Close Approximation Relation on Real Numbers

Already symmetric: if \( |x-y| < 0.0005 \), then \( |y-x| < 0.0005 \). Closing symmetry is unnecessary.

Transitive Closure for Close Approximation Relation on Real Numbers

Approximate transitivity by connecting sequences where, if \( |x-y| < 0.0005 \) and \( |y-z| < 0.0005 \), consider chains potentially making \( |x-z| < 0.001 \).

Final Observation

In many cases, specific symmetries and transitive properties cannot be forced without violating the logical structure of the relations.

Key concepts

Relations in Mathematics

Relations in mathematics are a way to describe how elements from one set relate to elements of another set, or sometimes the same set. Mathematically, a relation is a set of ordered pairs. If we have two sets, say, Set A and Set B, a relation is any subset of the Cartesian product of these two sets: \( A \times B \). Relations can also be defined on single sets, relating elements within the same set.
Each ordered pair includes a first element and a second element, indicating the direction or nature of the relationship. For example, the less than \((<)\) relation between the numbers 2 and 3 is written as \((2, 3)\). Relations can have various properties, such as being reflexive, symmetric, or transitive. These properties define the nature and behavior of the relation in different contexts. Studying these properties helps to understand complex systems and solve various mathematical problems related to order, hierarchy, and structure.

Reflexive Closure

A relation is considered reflexive if every element in the set is related to itself. For example, the relation "is equal to" \((=)\) is reflexive in terms of numbers because every number is equal to itself, i.e., \(a = a\).
Reflexive closure is the process of ensuring that a relation has the reflexive property. If a relation doesn't already include all pairs \((a, a)\) for every element \(a\), we add these pairs to make it reflexive. This is particularly significant when working on mathematical problems requiring all elements to possess this self-related property.
The reflexive closure of a relation is useful in various applications, such as computer science algorithms, where the completeness of data relations is crucial to ensuring cohesive and fully representative systems.

Symmetric Closure

A symmetric relation means that if a pair \((a, b)\) is in the relation, then the pair \((b, a)\) must also be in the relation. The "is equal to" \((=)\) relation exemplifies symmetry because if \(a = b\), then it follows logically that \(b = a\).
To achieve symmetric closure, we ensure that for every pair in the relation, its converse pair is also included. If the relation lacks this property, the symmetric closure adds such pairs to create symmetry. This can sometimes lead to contradictions in certain contexts, such as the "less than" \((<)\) relation, where having both \((a, b)\) and \((b, a)\) would contradict their logical meanings. Therefore, symmetric closure is not feasible for all types of relations.
Understanding symmetric closure helps in situations such as communication networks, where bi-directional communication is necessary for functional operations.

Transitive Closure

A transitive relation requires that if a pair \((a, b)\) is in the relation and \((b, c)\) is also in the relation, then \((a, c)\) must be included too. This property is naturally present in the "less than or equal to" \((\leq)\) relation, as if \(a \leq b\) and \(b \leq c\), then \(a \leq c\).
Transitive closure adds necessary pairs to a relation so it fulfills this property entirely. To form the transitive closure, we effectively chain pairs together within the relation until no further additions can be made without breaking its structure.
This concept is integral in many mathematical and computational contexts, such as database theory, where transitive dependencies must be resolved to ensure the accuracy and efficiency of data retrieval and interaction.