Properties of Relations

 

 

Examples:

 

\(\bullet \quad R_1 = \{ (a,a), (a, b), (b,b) \} \) is not reflexive because there exists an element \( c \in A \) such that \( (c, c ) \notin R_1 \).

\(\bullet \quad R_2 = \{ (a,a), (a, c), (b,b), (c,c) \} \) is reflexive.

 

Strategy:

 

To test whether a relation \(R \subset A \times A\) defined by \(R = \{(x,y)\mid x \in A \text{ and } y \in A\}\) is reflexive, substitute \(x\) for \(y\) in the given condition. If the resulting statement is an identity that holds true for all \(x \in A\), then the relation is reflexive.

 

Example:

 

Let us analyze whether the relation \(R \subset \mathbb{R}^{-} \times \mathbb{R}^{-}\) defined by \(R= \{(x,y)\mid |y| + x = 0\}\) is reflexive.

Substituting \(x\) for \(y\) in the conditional equation yields \(|x| + x = 0\). For any \(x \in \mathbb{R}^{-}\), the expression evaluates to \(-x + x = 0\), which is identically true. Therefore, this relation is reflexive.

 

Example:

 

Let us analyze whether the relation \(R \subset \mathbb{R} \times \mathbb{R}\) defined by \(R = \{(x,y) \mid y < x\}\) is reflexive.

Substituting \(x\) for \(y\) yields the inequality \(x < x\). Since this statement is false for all \(\forall x \in \mathbb{R}\), the relation is not reflexive.

 

Total Number of Reflexive Relations:

 

If the cardinality of set \(A\) is \(n\) (i.e., \(s(A) = n\)), the number of distinct reflexive relations that can be defined on \(A\) is given by:
\[\Large 2^{n^2 – n}\]

 

Example:

 

On the set \(A = \{1, 2, 3, 4, 5\}\), a total of \[[2^{5^2 – 5} = 2^{20}\] distinct reflexive relations can be defined.

 

2. Symmetric Property:

 

Let \(R\) be a relation defined on a set \(A\).
\[\forall (x,y) \in R \implies (y,x) \in R, \text{ then } R \text{ satisfies the symmetric property, meaning } R \text{ is a symmetric relation.} \]

 

Strategy:

 

The symmetric counterpart of any ordered pair \((a,b)\) across the diagonal line \(y = x\) is given by the pair \((b,a)\).

For a relation to be symmetric, the symmetric counterpart of every single ordered pair belonging to the relation must also be included. If even a single ordered pair lacks its symmetric counterpart, the relation cannot be symmetric.

 

Examples:

 

Consider the following relations defined on the set \(A = \{1, 2, 3, 4\}\):

\(\bullet \) \(R_{1} = \{(1,1), (1,2), (2,3), (3,2)\}\) is not symmetric because \((1,2) \in R_{1}\) but its symmetric counterpart \((2,1) \notin R_{1}\).

\(\bullet \) \(R_{2} = \{(1,2), (1,3), (3,3), (3,1), (2,1)\} \) is symmetric.

\(\bullet \)\( R_{3} = \{(1,1), (2,2), (3,3)\} \) is symmetric.

 

Property:

 

A relation \(R\) is symmetric if and only if it is identical to its inverse relation, meaning \(R= R^{-1}\).

 

Example:

 

For the relation \( R= \{ (1,1), (1,2), (2,2), (2,1) \} \) defined on the set \( A = \{ 1, 2 \} \), the inverse relation is evaluated as \( R^{-1} = \{ (1,1), (2,1), (2,2), (1,2) \} \). Since both sets contain identical elements, \( R= R^{-1} \).

 

Strategy:

 

To algebraically test whether a relation \( R\subset A \times A \) defined by \( R= \{ (x,y) \mid x \in A \text{ and } y \in A \} \) is symmetric, swap the variables \( x \) and \( y \) in the defining condition. If the resulting condition is logically equivalent to the original one, the relation is symmetric.

 

Example:

 

Let us investigate whether the relation \( R\subset Z \times Z \) defined by \( R= \{ (x,y) : 5 \mid (x-y) \} \) (where \(5\) divides the difference \(x – y\)) is symmetric.

For any integer \( k \in Z \), the divisibility condition yields:
\[ 5 \mid (x-y) \Rightarrow \frac{x – y}{5} = k \Rightarrow x – y = 5k \]
Interchanging \( x \) and \( y \) gives \( y – x = -5k = 5(-k) \). Since \(-k \in Z\), this preserves the structural divisibility condition. Thus, the relation \( R\) is symmetric.

 

Example:

 

Let us investigate whether the relation \( R \subset Z \times Z \) defined by \( R= \{ (x,y) \mid y = |x| \} \) is symmetric.

Swapping the variables \( x \) and \( y \) yields the equation \( x = |y| \). Since this equation defines a completely different solution set, the relation \( R \) is not symmetric.

 

Total Number of Symmetric Relations:

 

If the cardinality of set \( A \) is \( n \) (\( s(A) = n \)), the total number of distinct symmetric relations that can be defined on \( A \) is:
\[ \large 2^{\frac{n^2 + n}{2}} \]

 

3. Antisymmetric Property:

 

Let \(R\) be a relation defined on a set \(A\).

\[\text{If } \forall (x, y ) \in R \text{ and } (y, x ) \in R \implies x = y, \]

 

Examples:

 

Consider the following relations defined on the set \(A = \{ 1, 2, 3, 4, 5 \}\):

\(\bullet \quad R_{1} = \{ (1, 1), (2, 2), (1, 2), (3, 2), (2, 1) \}\) is not antisymmetric because both \((1, 2) \in R_{1}\) and its distinct counterpart \((2, 1) \in R_{1}\) coexist.

\(\bullet \quad R_{2} = \{ (1, 1), (1, 3), (2, 3), (3, 3) \}\) is antisymmetric.

 

Property:

 

Symmetry and antisymmetry are not mutually exclusive or polar opposites. A relation being non-symmetric does not automatically imply that it is antisymmetric, nor does lack of antisymmetry imply symmetry.

 

Example:

 

Consider the relation defined on the set \(A = \{ a, b, c, d \}\):

\(R= \{ (a, a), (b, c), (c, d), (c, b) \}\) is not symmetric because \((c, d) \in R\) but \((d, c) \notin R\). Concurrently, it is not antisymmetric either, because both \((b, c) \in R\) and \((c, b) \in R\) belong to the relation while \(b \neq c\).

 

Example:

 

The identity relation defined on the set \(A = \{ 1, 2, 3 \}\):

\(R= \{ (1, 1), (2, 2), (3, 3) \}\) is simultaneously symmetric and antisymmetric.

 

Strategy:

 

To algebraically test a relation \(R\subset A \times A\) defined by \(R= \{ (x, y) \mid x \in A \text{ and } y \in A \}\) for antisymmetry, swap the variables \(x\) and \(y\) to generate a dual equation system. Solve these equations simultaneously under the distinct constraint \(x \neq y\). If this constraints yields an empty solution set, the relation is antisymmetric.

 

Example:

 

Let us investigate whether the relation \(R\subset Z \times Z\) defined by \(R= \{ (x, y) \mid x^2 + 3y = 7 \}\) is antisymmetric.

Swapping the variables \(x\) and \(y\) yields a second equation to solve simultaneously:

\[y^2 + 3x = 7\quad\text{and} \quad x^2 + 3y = 7\]
Equating both expressions since they share a constant value:

\[ y^2 + 3x = x^2 + 3y \quad \]
\[ \Rightarrow \quad y^2 – x^2 + 3x – 3y = 0 \]

\[\Rightarrow (y – x)(y + x) – 3(y – x) = 0 \]

\[ \Rightarrow (y – x)(y + x – 3) = 0 \]

Imposing the constraint for distinct elements (\( y \neq x \implies y – x \neq 0\)), we divide by the shared term, leaving:
\[ y + x – 3 = 0 \quad \text{Rightarrow} \quad y = 3 – x \]
Substituting this linear constraint back into the primary relation equation:
\[ x^2 + 3y = 7 \]

\[\Rightarrow x^2 + 3(3 – x) = 7 \]

\[ \Rightarrow x^2 – 3x + 9 = 7 \]

\[ \Rightarrow x^2 – 3x + 2 = 0 \]

\[ \Rightarrow(x – 1)(x – 2) = 0 \]

Which yields the roots:
\[
x_1 = 1 \quad\text{or}\quad x_2 = 2
\]
Mapping these back to find the corresponding values for \(y\):
\[
y_1 = 2
\quad\text{or}\quad
y_2 = 1
\]
Consequently, the distinct ordered pairs \((1,2)\) and \((2,1)\) both satisfy the relation, proving that it is not antisymmetric.

 

4. Transitive Property:

 

Let \(R\) be a relation defined on a set \(A\).

\[ \text{If } \forall(x,y)\in R \text{ and } \forall(y,z) \in R \implies (x,z) \in R, \text{ then } R \text{ is a transitive relation.} \]
Note that if an ordered pair \((x,y) \in R \) has no matching pair in the relation starting with the element \(y\), then \((x,y)\) cannot violate transitivity. In such cases, the transitivity condition is satisfied vacuously.

 

Examples:

 

Consider the following relations defined on the set \(A = \{ 1, 2, 3, 4 \} \):

\( \bullet \) \(R_1 = \{ (1,1), (1,2), (2,3), (1,3), (2,4) \} \) is not transitive because \((1,2) \in R_1\) and \( (2,4) \in R_1 \) are included, but \( (1,4) \notin R_1 \).

\( \bullet \) \(R_2 = \{ (2,1), (1,2), (2,2), (2,3) \} \) is not transitive because \((1,2) \in R_2\) and \((2,3)\in R_2\) are included, but \((1,3) \notin R_2\).

\( \bullet \) \(R_3 = \{ (1,3), (2,4), (4,3), (1,2), (2,3) \} \) is not transitive because \( (1,2) \in R_3 \) and \( (2,4) \in R_3 \) are included, but \( (1,4) \notin R_3\).

\( \bullet \) \(R_4 = \{ (1,1), (1,3), (3,4), (1,4) \} \) is transitive.

\( \bullet \) \(R_5 = \{(1,1), (2,3), (2,4)\} \) is transitive (vacuously satisfied).

\( \bullet \) \(R_6 = \{(3,4)\} \) is transitive (vacuously satisfied).

 

Strategy:

 

To algebraically test a relation \( R \subset A \times A \) defined by \( R = \{(x,y) \mid x \in A \text{ and } y \in A\} \) for transitivity, substitute \( y \) for \( x \) and \( z \) for \( y \) to build the condition for adjacent pairs. Combine these systems to eliminate the intermediate variable \( y \). If this yields the structural condition confirming \( (x,z) \in R \), the relation is transitive.

 

Example:

 

Let us investigate whether the relation \( R \subset \mathbb{Z} \times \mathbb{Z} \) defined by \( R = \{(x,y) \mid x – y = k, \ k \in \mathbb{Z} \} \) is transitive.

Setting up the conditional equations for the pairs \((x,y)\) and \((y,z)\):

\[
\begin{aligned}
& y – z = n \quad (n \in \mathbb{Z}) \\
+ \quad & x – y = k \quad (k \in \mathbb{Z}) \\
\hline \\
& x – z = n + k
\end{aligned}
\]

Since the sum of two integers satisfies closure (\( (n + k) \in \mathbb{Z} \)), it follows that \( (x,z) \in R \). Therefore, the relation is transitive.

 

Property:

 

In a discrete Cartesian graph, the linear path defined by \( y = x \) is called the main diagonal.

We can analyze the global properties of a relation directly from its plotted matrix:

\(1.) \) Reflexive: Every coordinate index along the main diagonal must contain a plotted point.
\(2.) \) Symmetric: The matrix plot must display perfect reflectional symmetry across the main diagonal.
\(3.) \) Antisymmetric: Except for the entries on the main diagonal, no plotted coordinate can have a reflectional counterpart across the diagonal.

 

Example:

 

Let us consider the set \( A = \{1, 2, 3\} \):

The relation matrix \( R \) shown above satisfies both the reflexive and symmetric properties.

 

Example:

 

Let us consider the set \( A = \{1, 2, 3, 4 \} \) :

The relation matrix \( R \) shown above satisfies both the reflexive and antisymmetric properties.

 

Equivalence Relations:

 

Let \( R\) be a relation defined on a set \( A \). If \( R\) simultaneously satisfies the reflexive, symmetric, and transitive properties, then \( R \) is classified as an equivalence relation on \( A \). Within an equivalence relation, if \( (x, y) \in R \), the elements \(x\) and \( y\) are said to be equivalent under \( R \), denoted notationally as \( x \equiv y \).

 

Example:

 

Let us prove that the relation \( R= \{ (x, y) \mid x – y = 2k, k \in \mathbb{Z} \} \) defined on the set \( A = \{ x \mid -20 < x < 20, x \in \mathbb{Z} \} \) is an equivalence relation.

\( 1) \) Substituting \( x \) for \( y \) yields \( x – x = 0 = 2(0) \). Since \( 0 \in \mathbb{Z} \), the relation is reflexive.

\( 2) \) Interchanging \( x\) and \(y \) yields \(y-x= -2k = 2(-k) \). Since \(-k \in \mathbb{Z}\), this is structurally identical to the initial condition, proving symmetry.

\( 3) \) Let us construct adjacent pairs by substituting \( y \) for \( x \) and \( z \) for \( y \):

\[\begin{aligned} &y-z= 2n \quad (n \in Z ) \\+ \quad & x-y = 2k \quad (k \in Z ) \\ \hline \\ &x-z= 2(n+k) \end{aligned}\]

Because the sum of integers satisfies closure (\( n+k \in Z \)), it follows that \( (x, z) \in R \). Therefore, the relation is transitive. Since all three conditions are satisfied, \( R\) is an equivalence relation.

 

Example:

 

Let \(A\) be the set of all straight lines in a plane. Let us prove that the geometric relation \(R\) defined as “line parallelism” is an equivalence relation on \(A\).

This relation consists of pairs of lines that are either parallel or coincident. Assuming lines \(d_1, d_2, d_3 \in A\):

\(d_1 \in A, \quad d_2 \in A \quad \text{and} \quad d_3 \in A\) yields:

\( 1) \) Since any line is parallel or coincident to itself (\( d_1 \parallel d_1 \)), it follows that \( (d_1, d_1) \in R \). Thus, \( R \) is reflexive.

\( 2) \) If line 1 is parallel to line 2 (\(d_1 \parallel d_2 \)), then line 2 must be parallel to line 1 (\( d_2 \parallel d_1 \)). This shows that \( (d_1, d_2) \in R \implies (d_2, d_1) \in R \), so \( R \) is symmetric.

\( 3) \) If \( d_1 \parallel d_2 \) and \( d_2 \parallel d_3 \), geometric transitivity guarantees that \( d_1 \parallel d_3 \). Thus, \((d_1, d_2) \in R\) and \((d_2, d_3) \in R \implies (d_1, d_3) \in R\), meaning \( R \) is transitive. Consequently, \( R \) is an equivalence relation.

 

Equivalence Classes:

 

Let \( R \) be an equivalence relation defined on a set \( A \). For any element \( x \in A \), the subset containing all elements in \(A\) that map to \( x\) under \( R\) is called the equivalence class of \( x \) and is denoted by \( \bar{x} \) or \([x]\). Thus:

\[
\bar{x} = \{ y \in A \mid (x, y) \in R \}
\]

 

Example:

 

\[
\text{Consider the relation defined on the set } A = \{ 0, 1, 2, 3, 4 \}:
\]

\[
R= \{ (x, y) : 3 \mid (x – y) \} \quad \text{(where 3 divides the difference } x – y\text{)}
\]

Let us prove that this relation is an equivalence relation and determine the equivalence classes for the elements 1 and 2.

The divisibility condition can be structurally written using an integer constant \(k \in \mathbb{Z}\):
\[
3 \mid (x – y) \Rightarrow \frac{x – y}{3} = k \quad (k \in \mathbb{Z})
\]

Listing the ordered pairs that satisfy this modular arithmetic rule:

\[ R= \{ (0,0), (0,3), (1,1), (1,4), (2,2), (3,0), (3,3), (4,1), (4,4) \} \]

Since this relation satisfies reflexivity, symmetry, and transitivity, \( R \) is verified as an equivalence relation. Grouping the mapped elements yields the partition subsets:

\[ \bar{1} = \{1,4\}, \quad \bar{2} = \{2\} \]

 

Property:

 

An equivalence relation \( R \) defined on a set \( A \) induces a partition of \( A \). This means that the equivalence classes are mutually disjoint subsets whose union exactly reconstructs the original set \( A \). In the previous example, evaluating the remaining modular class:

\[ \bar{0} = \{0,3\} \]
\[\bar{1} = \{1,4\}\]
\[\bar{2} = \{2\}\]
\[A = \bar{0} \cup \bar{1} \cup \bar{2} = \{0,1,2,3,4\}\]

 

QUESTION 8

 

The relation
\[
R = \{ (x,y) \mid x^2 + x = y^2 + y, \quad (x,y) \in \mathbb{Z} \times \mathbb{Z} \}
\] is an equivalence relation.

Determine the equivalence class of 1.

\[
\text{A)} \{ 1,2 \} \quad
\text{B) } \{ -1, 1 \} \quad
\text{C) } \{ 1 \} \quad
\text{D) } \{ -3,1 \} \quad
\text{E) } \{ -2, 1 \}
\]

 

Solution:

 

To find the equivalence class of 1, we find all integer values of \(y \) that satisfy the relation mapping when \( x = 1 \).

\[ x^2 + x = y^2 + y \Rightarrow 1^2 + 1 = y^2 + y \]

\[ \Rightarrow y^2 + y – 2 = 0 \]

\[ \Rightarrow (y – 1)(y + 2) = 0 \]

Solving this quadratic equation yields the roots:
\[ \Rightarrow y_1 = 1 \quad \text{or} \quad y_2 = -2 \]

Gathering these distinct solutions into a partition set:

\[ \bar{1} = \{-2,1\} \]

 

\(\textbf{Correct Answer: E} \)

 

Partial Order Relations:

 

Let \(R\) be a relation defined on a set \( A\). If \(R\) simultaneously satisfies the reflexive, antisymmetric, and transitive properties, then \(R\) is classified as a partial order relation (or simply an order relation) on \(A\).

 

Example:

 

Let us prove that the relation
\[
R = \{ (x, y) \mid x \geq y, (x, y) \in \mathbb{R} \times \mathbb{R} \}
\]
is a partial order relation.

\( 1) \) Since any real number is identically equal to itself, \(x \geq x \) is universally true. Thus, \( \forall x \in \mathbb{R} \implies (x, x) \in R \), proving reflexivity.

\( 2) \) For any distinct elements where \( x \neq y \), if the inequality \(x \geq y\) holds true, its converse \(y \geq x \) must be false. The conditions can only be simultaneously met if \(x = y\). Except for identical diagonal terms, no pair has a symmetric counterpart, proving antisymmetry.

\( 3) \) If \(x \geq y \) and \( y \geq z \), the order axioms of real numbers guarantee that \( x \geq z \). Thus, \( R \) is transitive. Combining these features proves that \( R \) is a partial order relation.

 

Example:

 

Consider a biological relation \( R\) defined on the set of human blood types, mapping compatibility where a type can safely donate blood to another type. Let us show that this system forms a partial order relation.

\[R= \{ (A,A), (O,O), (B,B), (AB,AB), (A,AB), (O,B), (B,AB), (O,AB), (O,A) \} \]

We can verify the structural properties of this network:
* Reflexive: Every blood type is compatible with its own identical type (all main diagonal pairs exist).
* Antisymmetric: Except for identical types, blood donation is strictly unidirectional. For instance, type \(O\) can donate to type \(A\), but type \(A\) cannot donate back to type \(O\).
* Transitive: If type \(O\) can donate to type \(A\), and type \(A\) can donate to type \(AB\), then type \(O\) can safely donate to type \(AB\).

Since the relation is reflexive, antisymmetric, and transitive, it is a verified partial order relation.

 

 

 

← Previous Page | Next Page →