Question

Since relations are sets, it is possible to define union, intersection, relative complement, and absolute complement on pairs of relations. A natural question is which properties of the original relations still hold for the resulting new relation. Fill in the following table with \(Y / N,\) representing YES and NO, respectively. If the entry is \(N,\) find an example that shows the property is not preserved under the operation. For instance, enter a \(Y\) in the first row, second column, if the intersection of two reflexive relations is still reflexive; otherwise, enter an \(N\). $$\begin{array}{|l|l|l|l|l|}\hline & \text { Union } & \text { Intersection } & \begin{array}{l}\text { Relative } \\\\\text { Complement }\end{array} & \begin{array}{l}\text { Absolute } \\\\\text { Complement }\end{array} \\\\\hline \text { Reflexive } & & & & \\\\\hline \text { Irrefiexive } & & & & \\\\\hline \text { Symmetric } & & & & \\\\\hline \text { Antisymmetric } & & & & \\\\\hline \text { Transitive } & & & & \\\\\hline\end{array}$$

Short answer

YNYNN, NYYN, YYYY, NYYN, NYNN

Step-by-step solution

Check Reflexivity

To examine reflexivity, consider two reflexive relations, say \(R\) and \(S\). A relation is reflexive if for every element \(a\), the pair \((a, a)\) is in the relation.- **Union**: The union \(R \cup S\) will include all pairs from both \(R\) and \(S\), including all \((a, a)\), so the result is reflexive (**Y**). - **Intersection**: The intersection \(R \cap S\) will include pairs present in both \(R\) and \(S\). If both are reflexive, \((a, a)\) is in both, hence reflective (**Y**).- **Relative Complement**: \(R \setminus S\) removes pairs in \(S\) from \(R\). If \(S\) contains some \((a, a)\) but not \(R\), these will be removed, potentially not reflexive (**N**).- **Absolute Complement**: Complements can remove \((a, a)\) as not all elements in the set might be reflexive, potentially resulting in non-reflexiveness (**N**).

Check Irreflexivity

A relation is irreflexive if no \((a, a)\) pairs exist.- **Union**: The union of two irreflexive relations may still contain \((a, a)\) if one contains it, losing irreflexivity (**N**). Example: \(R = \emptyset\) and \(S = \{(a, a)\}\), \(R \cup S = \{(a, a)\}\).- **Intersection**: If both \(R\) and \(S\) are irreflexive, then \(R \cap S\) is irreflexive as it contains no \((a, a)\) (**Y**).- **Relative Complement**: \(R \setminus S\) is irreflexive if \(R\) is irreflexive, as removing cannot add \((a, a)\) (**Y**).- **Absolute Complement**: The absolute complement generally can introduce \((a, a)\) as it includes pairs not in the original, potentially not irreflexive (**N**).

Check Symmetry

Check if the relation remains symmetric.- **Union**: If both relations are symmetric (contain \((a, b)\) and \((b, a)\)), then \(R \cup S\) is symmetric (**Y**).- **Intersection**: Symmetry is retained if pairs exist in both \(R\) and \(S\), keeping symmetry (**Y**).- **Relative Complement**: Pair removal in \(R \setminus S\) may remove \((a, b)\) or \((b, a)\), losing symmetry (**N**). Example: \(R = \{(a, b), (b, a)\}\) and \(S = \{(b, a)\}\), \(R \setminus S = \{(a, b)\}\).- **Absolute Complement**: Complement may not hold both pairs needed for symmetry, not symmetric **(N)**.

Check Antisymmetry

Analyze antisymmetry, which needs \((a, b)\) and \((b, a)\) implying \(a = b\).- **Union**: Union of two antisymmetric relations might introduce pairs, removing antisymmetry (**N**). Example: \(R = \{(a, b)\}\), \(S = \{(b, a)\}\), \(R \cup S = \{(a, b), (b, a)\}\).- **Intersection**: Both \((a, b)\) and \((b, a)\) absent in \(R \cap S\), maintaining antisymmetry (**Y**).- **Relative Complement**: \(R \setminus S\) may remove pairs without disrupting antisymmetry (**Y**).- **Absolute Complement**: Can introduce pairs, thus removing antisymmetry (**N**).

Check Transitivity

Determine whether transitivity is preserved.- **Union**: Adding pairs in \(R \cup S\) may break transitivity (**N**). Example: \(R = \{(a, b)\}\) and \(S = \{(b, c)\}\), \((a, c)\) may not exist.- **Intersection**: Both transitive gives \(R \cap S\) as transitive (**Y**).- **Relative Complement**: Removal of sufficient pairs in \(R \setminus S\) loses transitivity (**N**). Example: \(R = \{(a, b), (b, c), (a, c)\}\) and \(S = \{(b, c)\}\).- **Absolute Complement**: The complement can break the chain, often not transitive (**N**).

Key concepts

Reflexive Relations

A relation on a set is considered reflexive if every element in the set is related to itself. Imagine you have a set of people, and you have a relation "is a friend of." This relation is reflexive if every person is friends with themselves. Mathematically, for every element \( a \) in the set, the pair \((a, a)\) must be in the relation.

In operations, reflexivity holds for union and intersection:

• **Union**: This operation brings together all pairs from two reflexive relations. If both are reflexive, the union will contain all necessary \((a, a)\) pairs, thus remaining reflexive.
• **Intersection**: Likewise, the intersection of reflexive relations retains reflexivity because each relation individually contains every \((a, a)\) pair.

However, reflexivity does not always hold for complements:

• **Relative Complement**: This operation might take away some \((a, a)\) pairs if they are present in both relations, leading to non-reflexivity.
• **Absolute Complement**: Generally, this can remove any reflexive pairs, resulting in a non-reflexive relation.

Symmetric Relations

Symmetry in a relation means if an element \( a \) is related to another element \( b \), then \( b \) is related back to \( a \). Picture two people who always reciprocate friendships. Symbolically, if \((a, b)\) is in the relation, \((b, a)\) must also be in the relation.

This property behaves predictably with operations:

• **Union**: The union of symmetric relations remains symmetric because both \((a, b)\) and \((b, a)\) from either relation will be included.
• **Intersection**: If both relations are symmetric, their intersection will certainly keep both pairs \((a, b)\) and \((b, a)\).

The situation changes with complements:

• **Relative Complement**: Removing pairs from one relation might destroy some symmetry, especially if it leaves solitary pairs like \((a, b)\) without \((b, a)\).
• **Absolute Complement**: This could introduce or remove pairs arbitrarily, generally making the result non-symmetric.

Antisymmetric Relations

Antisymmetry in a relation means if \( a \) and \( b \) are distinct elements and \((a, b)\) is in the relation, \((b, a)\) cannot also be present unless \( a = b \). For example, in a set of employees, if "has supervised" is the relation, typically, if one supervises the other, it cannot happen the other way around.

Let's consider how operations affect antisymmetry:

• **Union**: This can introduce pairs that break antisymmetry. Imagine if two antisymmetric relations separately contain \((a, b)\) and \((b, a)\). Their union will contain both, violating antisymmetry.
• **Intersection**: Antisymmetry is preserved when intersecting two such relations, as any conflicting pairs would be absent.

Concerning complements:

• **Relative Complement**: Here, antisymmetry might be retained if only non-violating pairs are removed.
• **Absolute Complement**: New conflicting pairs could easily be introduced, eroding antisymmetry.

Transitive Relations

Transitivity implies the ability to 'chain' relationships. For example, if in a group of people, one person is older than another, and that person is in turn older than a third, transitivity would mean the first person is older than the third. Formally, if \((a, b)\) and \((b, c)\) are in a relation, then \((a, c)\) should be as well.

The influence of operations on transitivity varies:

• **Union**: Joining two relations may disrupt transitivity because merging doesn't necessarily preserve the chain of \((a, b), (b, c)\) leading to \((a, c)\).
• **Intersection**: Both original relations being transitive ensures the intersection remains transitive since shared chains \((a, b), (b, c)\) exist in both.

With complements, transitivity is often lost:

• **Relative Complement**: This operation may eliminate necessary pairs that form the transitive chain, resulting in non-transitive relations.
• **Absolute Complement**: The removal of key pairs tends to break transitive sequences, making this usually non-transitive.