Relations
Intuition
To understand the concept of a relation, let's consider both a real-world example and a mathematical one.
Example 1: Actors and Movies
Suppose we have two sets:
-
Set \( A \): Names of well-known actors,
\[ A = \{\text{Daniel Radcliffe}, \text{Emma Watson}, \text{Brad Pitt}, \text{Meryl Streep}, \text{Leonardo DiCaprio}\} \] -
Set \( B \): Titles of popular movies,
\[ B = \{\text{Harry Potter}, \text{Inception}, \text{Fight Club}, \text{The Devil Wears Prada}, \text{Little Women}, \text{Titanic}\} \]
The Cartesian product \( A \times B \) includes all possible pairs of actors with these movie titles, creating pairs like:
This set contains every possible pairing, even if most don't make sense, like "Emma Watson in Fight Club" or "Brad Pitt in Harry Potter."
To define a relation, we select only pairs in which the actor actually starred in the movie. For instance:
This subset of pairs represents the true relationship between actors and movies they starred in.
Example 2: Prime Numbers and Divisibility
Now, let’s look at a mathematical example of a relation based on divisibility.
Suppose we have two sets:
-
Set \( A \): The first five prime numbers,
\[ A = \{2, 3, 5, 7, 11\} \] -
Set \( B \): A set of composite numbers,
\[ B = \{6, 10, 15, 21, 22, 33\} \]
The Cartesian product \( A \times B \) includes all possible pairs of primes and composite numbers:
However, we’re only interested in pairs where the prime number from \( A \) divides the composite number from \( B \). This gives us the subset:
This subset represents a relation where each prime number in \( A \) is related to a composite number in \( B \) if it divides that number exactly.
Definition of a Relation
A relation from a set \( A \) to a set \( B \) is a subset of the Cartesian product \( A \times B \). It includes pairs \( (a, b) \) where each \( a \in A \) is associated with a particular \( b \in B \) based on some specific condition or rule.
In both examples, we used a condition to filter pairs from the Cartesian product:
- In the actor-movie example, the condition was that the actor starred in the movie.
- In the prime-composite example, the condition was that the prime divides the composite number.
This idea of selecting specific pairs is the essence of defining a relation.
Example
Let \( F \) be the set of names of fathers, and \( C \) be the set of names of children. The Cartesian product \( F \times C \) contains all possible pairs of a father and a child.
Let
The Cartesian product \( F \times C \) is:
Now define the relation \( R \) such that \( R = \text{“is father of”} \). This relation includes pairs \( (f, c) \in F \times C \) where \( f \) is the actual father of \( c \). Based on factual information, let:
Understanding \( aRb \) Notation:
- \( (\text{John}, \text{Emma}) \in R \) means "John is the father of Emma." This is denoted as \( \text{John} \, R \, \text{Emma} \).
- \( (\text{Raj}, \text{Aryan}) \in R \) means "Raj is the father of Aryan." This is denoted as \( \text{Raj} \, R \, \text{Aryan} \).
- \( (\text{Ali}, \text{Sana}) \in R \) means "Ali is the father of Sana." This is denoted as \( \text{Ali} \, R \, \text{Sana} \).
Pairs not in \( R \), such as \( (\text{John}, \text{Chris}) \), indicate that there is no father-child relationship between the respective elements.
Thus, \( R \) in roster form is:
Example
Let \( L = \{l_1, l_2, l_3, l_4\} \), where \( l_1, l_2, l_3, l_4 \) represent specific straight lines in a plane. Define a relation \( S \subseteq L \times L \), where two lines \( l_1, l_2 \in L \) are related if and only if \( l_1 \parallel l_2 \) (i.e., \( l_1 \) is parallel to \( l_2 \)).
Suppose, it is known that:
- \( l_1 \parallel l_2 \),
- \( l_3 \parallel l_4 \),
- \( l_1 \) and \( l_3 \) are not parallel.
The Cartesian product \( L \times L \) contains all possible ordered pairs of lines:
The relation \( S \), defined by "is parallel to," is:
Image, Preimage, Domain and Range
Consider a relation \( R \) from the set \( A = \{1, 2, 3, 4, 5, 6, 7\} \) to the set \( B = \{1, 2, 3, 4, 5, 6, 7, 8, 9\} \), defined by \( x R y \) if and only if \( x + y = 6 \). The relation \( R \) is explicitly given as:
Definitions:
Consider a relation \( R \) from the set \( A = \{1, 2, 3, 4, 5, 6, 7\} \) to the set \( B = \{1, 2, 3, 4, 5, 6, 7, 8, 9\} \), defined by \( x R y \) if and only if \( x + y = 6 \). The relation \( R \) is explicitly given as:
-
Image:
If \( x \) is related to \( y \) under the relation \( R \), then \( y \) is called the image of \( x \). In this example:
- The image of \( 1 \) is \( 5 \), as \( (1, 5) \in R \).
- The image of \( 2 \) is \( 4 \), as \( (2, 4) \in R \).
- Similarly, the image of \( 3 \) is \( 3 \), the image of \( 4 \) is \( 2 \), and the image of \( 5 \) is \( 1 \).
-
Preimage:
If \( y \) is related to \( x \) under the relation \( R \), then \( x \) is called the preimage of \( y \). In this example:
- The preimage of \( 5 \) is \( 1 \), as \( (1, 5) \in R \).
- The preimage of \( 4 \) is \( 2 \), the preimage of \( 3 \) is \( 3 \), the preimage of \( 2 \) is \( 4 \), and the preimage of \( 1 \) is \( 5 \).
-
Domain:
The domain of a relation \( R \) is the set of all elements in \( A \) that have at least one image in \( B \).
From the given relation, the domain is:\[ \text{Domain of } R = \{1, 2, 3, 4, 5\}. \] -
Codomain:
The codomain of a relation \( R \) is the entire set \( B \), irrespective of whether all its elements are images of elements in \( A \).
For this example, the codomain is:\[ \text{Codomain of } R = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}. \] -
Range:
The range of a relation \( R \) is the set of all elements in \( B \) that are images of elements in \( A \). It is the set of all \( y \)-values in the ordered pairs of \( R \):
\[ \text{Range of } R = \{5, 4, 3, 2, 1\}. \]
Domain, Range and Codomain
Consider a relation \( S \) from the set \( A = \{-2, -1, 0, 1, 2, 3\} \) to the set \( B = \{0, 1, 2, 3, 4, 5\} \), defined by \( x S y \) if and only if \( y = x^2 - 1 \). The relation \( S \) is explicitly given as:
Using this relation, we can identify the following:
-
Domain of \( S \):
The domain consists of all elements in \( A \) that are related to some element in \( B \). From the ordered pairs in \( S \), the domain is:
\[ \text{Domain of } S = \{-2,\ -1,\ 1,\ 2\}. \] -
Range of \( S \):
The range includes all elements in \( B \) that are images of elements from \( A \). From the relation \( S \), the range is:
\[ \text{Range of } S = \{0,\ 3\}. \] -
Codomain of \( S \):
The codomain is the entire set \( B \), regardless of whether every element is an image of an element from \( A \):
\[ \text{Codomain of } S = \{0,\ 1,\ 2,\ 3,\ 4,\ 5\}. \]
Ways of Representing a Relation
-
Set-Builder Form:
A relation can be defined in set-builder form like in the following example. Consider a relation \( R \) from the set \( A \) to the set \( B \) (take \( A \) and \( B \) as before). An element in set \( A \), say \( x \), is related to an element in set \( B \), say \( y \), under relation \( R \) if and only if \( y = \pm x^2 \). We can write this concisely as:
\( R \) is a relation from set \( A \) to set \( B \) such that for all \( x \in A \) and \( y \in B \), \( x R y \) \((x, y) \in R\) if and only if \( y = \pm x^2 \).We can also express this in set-builder form as:
\[ R = \{(x, y) \in A \times B : y = \pm x^2\}. \] -
Roster Form:
In this method, all the elements of the relation are explicitly listed. This is useful for finite sets where listing elements is feasible.
For the above example, the relation \( R \) in roster form becomes:\[ R = \{(1, 1), (1, -1), (2, 4), (3, 9)\}. \] -
Mappings:
Relations defined on finite sets can be visually represented using mappings. A mapping diagram displays the elements of set \( A \) on the left and those of set \( B \) on the right. Arrows are drawn from each element of \( A \) to its related element(s) in \( B \) as per the relation.
For instance, consider the above example. The mapping diagram is illustrated as follows:
These mappings clearly represent the connections between elements of sets \( A \) and \( B \).
Mapping diagrams are particularly useful for understanding relations at a glance, making them a preferred choice in visualizing finite relations.
-
Relation Matrix:
A relation matrix is an efficient way to represent relations defined on finite sets. It organizes the elements of the sets involved into rows and columns to provide a clear visual representation of the relation.
Example
Consider a relation \( R \) defined on the sets \( A = \{1, 2, 3, 4\} \) and \( B = \{-1, 0, 1, 2, 3, 4\} \), where \( x R y \) if and only if \( y = x - 1 \). For this relation, the set of ordered pairs is:
\[ R = \{(1, 0), (2, 1), (3, 2), (4, 3)\}. \]For this example, the matrix is:
Structure of the Matrix:
- Rows: Represent the elements of the first set (\( A \)).
- Columns: Represent the elements of the second set (\( B \)).
-
Entries: At the intersection of a row (corresponding to an element \( x \in A \)) and a column (corresponding to an element \( y \in B \)), the value is:
- \( 1 \), if \( (x, y) \in R \) (i.e., \( x \) is related to \( y \)), or
- \( 0 \), if \( (x, y) \notin R \).
Explanation:
- For \( x = 1 \), \( y = 0 \) satisfies \( y = x - 1 \), so a \( 1 \) is placed in the row for \( 1 \) and column for \( 0 \).
- For \( x = 2 \), \( y = 1 \) satisfies the condition, so a \( 1 \) is placed in the corresponding row and column.
- This process is repeated for all pairs in \( R \).
General Rule:
If \( M \) is the relation matrix of \( R \), then for any element \( x_i \in A \) and \( y_j \in B \):
\[ M_{ij} = \begin{cases} 1, & \text{if } (x_i, y_j) \in R \\ 0, & \text{if } (x_i, y_j) \notin R \end{cases}. \]This method provides a structured way to capture the relationship between elements of the two sets.
-
Graphical Representation of Relations
Relations can be effectively represented using graphs on a Cartesian coordinate system. These visual representations help in understanding the structure and properties of the relation. Let's explore this with two examples:
Example 1: Finite Sets
Let \( A = \{1, 2, 3, 4, 5\} \) and \( B = \{3, 4, 5\} \). The Cartesian product \( A \times B \) represents all ordered pairs \((x, y)\), forming a lattice of points in the Cartesian plane.
Now, define a relation \( T \) as \( x T y \iff x < y \).
The relation \( T \) is a subset of \( A \times B \), consisting of all points where the \( x \)-coordinate is less than the \( y \)-coordinate.For \( A = \{1, 2, 3, 4, 5\} \) and \( B = \{3, 4, 5\} \):
\[ T = \{(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)\}. \]In the Cartesian plane, these points form part of the lattice and can be plotted as individual dots where \( x < y \).
Example 2: Intervals
Let \( A = [2, 5] \) and \( B = [4, 6] \). These are intervals, meaning they are sets containing infinitely many elements (all real numbers between the specified bounds). The Cartesian product \( A \times B \) is a rectangle in the Cartesian plane, with \( A \) as the range for the \( x \)-coordinate and \( B \) as the range for the \( y \)-coordinate.
Now, define a relation \( S \) as \( x S y \iff y = x + 2 \).
The relation \( S \) consists of all points \((x, y)\) in \( A \times B \) that satisfy \( y = x + 2 \). This is a straight line passing through the rectangle, as it satisfies the equation of a line.
For example:
- If \( x = 3 \), then \( y = 3 + 2 = 5 \), so \( (3, 5) \in S \).
- Similarly, for other values of \( x \) in \( A \), their corresponding \( y \) values form a line.
The graphical representation of \( S \) is a diagonal line cutting through the rectangular region \( A \times B \), as shown in the figure.
- For Finite Sets: The relation is represented as a subset of lattice points, making it easy to see which elements of \( A \) are related to elements of \( B \).
- For Intervals: The relation is a continuous line, curve, or other geometrical shape within the region defined by \( A \times B \), depending on the rule defining the relation.
Example
Consider the relation \( R = \{(x, y) \in \mathbb{R}^2 : x = \sin y\} \).
The graph represents all points \( (x, y) \) where the \( x \)-coordinate is the sine of the \( y \)-coordinate. Since \( \sin y \) oscillates between \( -1 \) and \( 1 \) periodically, the graph is a continuous, wavy curve extending infinitely along the \( y \)-axis, with \( x \) oscillating between \( -1 \) and \( 1 \).
Number of Relations (Finite Sets)
If set \( A \) has \( m \) elements and set \( B \) has \( n \) elements, then the Cartesian product \( A \times B \) contains \( m \cdot n \) ordered pairs. A relation \( R \) from \( A \) to \( B \) is a subset of \( A \times B \). Therefore, the total number of relations that can be defined from \( A \) to \( B \) is equal to the number of subsets of \( A \times B \), which is \( 2^{mn} \).
Example:
Let \( A = \{1, 2\} \) and \( B = \{a, b, c\} \).
- The set \( A \) has \( m = 2 \) elements, and the set \( B \) has \( n = 3 \) elements.
-
The Cartesian product \( A \times B \) consists of \( m \cdot n = 2 \cdot 3 = 6 \) ordered pairs:
\[ A \times B = \{(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)\}. \] -
A relation \( R \) from \( A \) to \( B \) is any subset of \( A \times B \).
- The total number of subsets of \( A \times B \) is \( 2^{mn} = 2^6 = 64 \).
Thus, there are \( 64 \) different relations that can be defined from \( A \) to \( B \).
Relation on a Set
A relation on a set refers to a situation where the relation is defined between elements of the same set. Formally, if a relation \( R \) is defined from a set \( A \) to itself, then \( R \) is a subset of the Cartesian product \( A \times A \). In other words, every ordered pair in \( R \) consists of elements that both belong to \( A \). Such a relation is said to be defined on the set \( A \).
Example:
Let \( A = \{1, 2, 3\} \), and consider a relation \( R \) given by:
Here:
-
\( A \times A \) is the set of all possible ordered pairs of \( A \):
\[ A \times A = \{(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)\}. \] -
The relation \( R \) is a subset of \( A \times A \) because all the ordered pairs in \( R \), namely \((1, 2)\), \((2, 3)\), and \((1, 1)\), belong to \( A \times A \).
Types of Relations
Relations between two sets \( A \) and \( B \) can be categorized based on how elements of \( A \) are related to elements of \( B \). Below are the main types:
-
One-to-One Relation (Injective Relation)
A relation \( R \) is called one-to-one if each element of \( A \) is related to a unique element in \( B \), and no two elements of \( A \) are related to the same element in \( B \).
Example:
Let \( A = \{1, 2, 3\} \) and \( B = \{a, b, c\} \), and the relation \( R = \{(1, a), (2, b), (3, c)\} \).
Here, each element of \( A \) is related to exactly one unique element of \( B \), and no two elements in \( A \) share the same image.
-
Many-to-One Relation
A relation \( R \) is many-to-one if multiple elements of \( A \) are related to the same element in \( B \).
Example:
Let \( A = \{1, 2, 3\} \) and \( B = \{a, b\} \), and the relation \( R = \{(1, a), (2, a), (3, b)\} \).
Here, \( 1 \) and \( 2 \) are both related to \( a \), which makes the relation many-to-one.
-
One-to-Many Relation
A relation \( R \) is one-to-many if a single element of \( A \) is related to multiple elements in \( B \). Such a relation does not represent a function, as a function requires every element in \( A \) to be related to at most one element in \( B \).
Example:
Let \( A = \{1, 2\} \) and \( B = \{a, b, c\} \), and the relation \( R = \{(1, a), (1, b), (2, c)\} \).
Here, \( 1 \) is related to both \( a \) and \( b \), making the relation one-to-many.
-
Many-to-Many Relation
A relation \( R \) is many-to-many if multiple elements in \( A \) are related to multiple elements in \( B \).
Example:
Let \( A = \{1, 2\} \) and \( B = \{a, b\} \), and the relation \( R = \{(1, a), (1, b), (2, a), (2, b)\} \).
Here, both \( 1 \) and \( 2 \) are related to both \( a \) and \( b \), making it a many-to-many relation.
Summary Table:
| Type | Description | Example |
|---|---|---|
| One-to-One | Each \( a \in A \) relates to a unique \( b \in B \). | \( R = \{(1, a), (2, b), (3, c)\} \) |
| Many-to-One | Multiple \( a \in A \) relate to the same \( b \in B \). | \( R = \{(1, a), (2, a), (3, b)\} \) |
| One-to-Many | A single \( a \in A \) relates to multiple \( b \in B \). | \( R = \{(1, a), (1, b), (2, c)\} \) |
| Many-to-Many | Multiple \( a \in A \) relate to multiple \( b \in B \). | \( R = \{(1, a), (1, b), (2, a), (2, b)\} \) |
Empty and Universal Relations
Relations can also be classified as empty or universal based on whether they include no pairs or all possible pairs from the Cartesian product \( A \times B \).
Empty Relation
A relation \( R \) from set \( A \) to set \( B \) is an empty relation if no ordered pair from \( A \times B \) satisfies the given condition. In this case, \( R = \emptyset \).
Example:
Let \( A = \{1, 2, 3\} \) and \( B = \{2, 3, 4, 5\} \). Define a relation \( R \) as:
For \( x \in A \) and \( y \in B \), observe that:
- \( 1 + 2 = 3 \), not \( 1 \),
- \( 1 + 3 = 4 \), not \( 1 \), and similarly for all other pairs.
No ordered pair satisfies \( x + y = 1 \). Hence:
In this case, \( R \) is an empty relation as it contains no elements.
Universal Relation
A relation \( R \) from set \( A \) to set \( B \) is a universal relation if every ordered pair in \( A \times B \) satisfies the given condition. In this case, \( R = A \times B \).
Example:
Let \( A = \{1, 2, 3\} \) and \( B = \{2, 3, 4, 5\} \). Define a relation \( R \) as:
For all \( x \in A \) and \( y \in B \):
- \( 1 + 2 = 3 > 1 \),
- \( 1 + 3 = 4 > 1 \), and so on for all pairs in \( A \times B \).
Every pair satisfies \( x + y > 1 \). Hence:
In this case, \( R \) is a universal relation as it includes all possible pairs from \( A \times B \).
Types of Relations on a set
We are interested in four important types of relations defined on a set: reflexive, symmetric, transitive, and equivalence relations. These classifications form the foundation for understanding the structure and properties of relations in mathematics.
Reflexive Relation
Let \( A \) be a set, and \( R \) be a relation on \( A \). The relation \( R \) is called reflexive if every element of \( A \) is related to itself.
This means that for all \( a \in A \), \( a R a \) (i.e., \((a, a) \in R\)).
In simpler terms, if a relation is reflexive, then every element in the set appears as a pair with itself in the relation.
Examples of Reflexive Relations
Example 1:
Let \( A = \{1, 2, 3\} \), and \( R = \{(1, 1), (2, 2), (3, 3), (1, 2)\} \).
Here:
- Every element in \( A \) is related to itself: \( (1, 1) \), \( (2, 2) \), and \( (3, 3) \) are in \( R \).
- In addition, \( R \) includes the pair \( (1, 2) \), but this does not affect reflexivity, as reflexivity only requires \( (a, a) \) for all \( a \in A \).
Thus, \( R \) is reflexive because it satisfies the condition \( a R a \) for all \( a \in A \).
Example 2:
Let \( S \) be the set of all lines in a plane, and define a relation \( R \) as "is parallel to."
For two lines \( L_1 \) and \( L_2 \), \( L_1 R L_2 \) means \( L_1 \) is parallel to \( L_2 \).
This relation is reflexive because:
- Every line is parallel to itself (by definition of parallelism).
Hence, \( R \) satisfies \( L R L \) for all lines \( L \) in \( S \).
Example 3:
Let \( Z \) be the set of integers, and define a relation \( M \) on \( Z \) by:
To check reflexivity, consider any integer \( x \in Z \):
- For \( x \), \( |x - x| = 0 \), and \( 0 \) is divisible by \( 3 \).
This means \( x M x \) holds for all \( x \in Z \).
Thus, \( M \) is reflexive because every integer \( x \) is related to itself.
Proving a Relation is Reflexive
To prove that a relation \( R \) on a set \( A \) is reflexive, we use the Principle of Universal Generalization.
Principle of Universal Generalization:
This principle states that to prove a property holds for all elements of a set, it is sufficient to prove the property for an arbitrary element of the set. If the property is shown to hold for an arbitrary element, it applies universally to every element of the set.
Consider the theorem: The sum of the angles of a triangle is 180°.
You did not prove this for every triangle in existence. Instead, you proved it for an arbitrary triangle using geometric properties. Since the choice of the triangle was arbitrary, the proof applies to all triangles.
Using this principle, to prove reflexivity:
- Assume an arbitrary element \( a \in A \).
- Prove that \( a R a \) (i.e., \( (a, a) \in R \)).
If this is shown to hold for an arbitrary \( a \), it is true for every \( a \in A \), and hence the relation is reflexive.
A Reflexive Relation
Consider a relation \( R \) defined on the set of natural numbers \( \mathbb{N} \), where \( R \subseteq \mathbb{N} \times \mathbb{N} \). The relation is defined as:
To prove that \( R \) is reflexive, we must show that for every \( x \in \mathbb{N} \), \( x R x \) holds. This means \( 3x + 4x \) must be divisible by \( 7 \).
- Consider an arbitrary \( x \in \mathbb{N} \).
-
For \( x R x \), substitute \( y = x \) in the condition:
\[ 3x + 4x = 7x. \] -
Clearly, \( 7x \) is divisible by \( 7 \) for all \( x \in \mathbb{N} \).
Thus, \( x R x \) holds for every \( x \in \mathbb{N} \).
Since \( x R x \) is true for every \( x \in \mathbb{N} \), the relation \( R \) is reflexive. This conclusion follows from the Principle of Universal Generalization, as we proved the property for an arbitrary \( x \), thereby showing it is true for all \( x \) in \( \mathbb{N} \).
Disproving Reflexivity
To disprove that a relation is reflexive, it is sufficient to find one counterexample where an element \( a \in A \) is not related to itself (i.e., \( (a, a) \notin R \)).
This single counterexample is enough to conclude that the relation is not reflexive.
Example
Let \( A = \{1, 2, 3\} \), and \( R = \{(1, 2), (2, 3)\} \).
Here:
- The pair \( (1, 1) \), representing \( 1 R 1 \), is missing.
- Similarly, \( (2, 2) \) and \( (3, 3) \) are not in \( R \).
Thus, \( R \) is not reflexive because at least one element of \( A \) is not related to itself.
A Non-Reflexive Relation
Consider a set \( A = \{1, 2, 3, 3, 4, 5, 6, 7\} \). Let \( S \) be the set of all subsets of \( A \). Define a relation \( R \) on \( S \) as follows:
This relation states that two subsets \( X \) and \( Y \) are related if their intersection is not empty (i.e., \( X \cap Y \neq \emptyset \)).
Reflexivity Check:
To determine if \( R \) is reflexive, we must check whether every subset \( X \in S \) satisfies \( X R X \) (i.e., \( X \cap X \neq \emptyset \)).
-
Empty Subset (\( \emptyset \)):
- The empty subset \( \emptyset \in S \), as \( \emptyset \) is a subset of \( A \).
- For \( X = \emptyset \), \( X \cap X = \emptyset \cap \emptyset = \emptyset \).
- Since \( \emptyset \neq \emptyset \) is false, \( \emptyset \) is not related to itself.
- Thus, \( R \) is not reflexive because \( \emptyset R \emptyset \) does not hold.
-
Non-Empty Subsets (\( X \neq \emptyset \)):\
- For any non-empty subset \( X \in S \), \( X \cap X = X \), which is not empty.
- Hence, every non-empty subset is related to itself under \( R \).
Conclusion:
This relation \( R \) is not reflexive because \( \emptyset \in S \), and \( \emptyset \cap \emptyset = \emptyset \), which fails the condition \( X \cap X \neq \emptyset \). Even though all other non-empty subsets \( X \) in \( S \) are related to themselves, the failure for \( \emptyset \) to satisfy reflexivity makes \( R \) a non-reflexive relation.
Key Observation:
To disprove reflexivity, it is sufficient to find one counterexample where an element \( X \in S \) is not related to itself. In this case, \( \emptyset \) serves as the counterexample.
Symmetric Relation
Consider a relation \( R \) defined on a set \( A \). The relation \( R \) is said to be symmetric if:
In other words, if \( (x, y) \in R \), then \( (y, x) \in R \) as well. This property ensures that the relation is "bidirectional" — whenever \( x \) is related to \( y \), \( y \) must also be related to \( x \).
To understand the exact meaning of the above definition, consider the following illustration:
Let \( R \) be a relation defined on \( A = \{1, 2, 3, 4\} \) as:
This relation is symmetric, as for every pair \((x, y) \in R\), the pair \((y, x)\) is also in \( R \). Let’s verify this:
- The pair \((1, 1)\) is symmetric because reversing the order gives the same pair \((1, 1)\), with no change.
- The pair \((1, 2)\) has its reverse pair \((2, 1)\) also present in \( R \), ensuring symmetry.
- Similarly, \((3, 4)\) and \((4, 3)\) form a symmetric pair.
Hence, this \( R \) satisfies the condition of symmetry.
Now, suppose we remove \((4, 3)\) from \( R \), leaving:
In this case, the relation is no longer symmetric because \((3, 4) \in R\), but its reverse pair \((4, 3)\) is not present. This absence violates the symmetry condition.
Another example of a symmetric relation is \( S = \{(1, 1), (2, 2)\} \) on the same set \( A \). Here, every pair is symmetric because reversing the pairs \((1, 1)\) and \((2, 2)\) has no effect. Thus, \( S \) satisfies symmetry.
Interestingly, the empty relation, \( R_1 = \emptyset \), is also symmetric. Since there are no pairs in \( R_1 \), it does not contain any pair that could potentially violate the symmetry condition. This makes it symmetric by default, a concept known as being vacuously symmetric.
On the other hand, consider \( R_2 = \{(1, 2)\} \). This relation is not symmetric because the reverse pair \((2, 1)\) is not present in \( R_2 \). Thus, symmetry fails as soon as one pair lacks its reverse.
In summary, symmetry requires every pair in the relation to have its reverse also present. A relation can fail this condition if even a single reverse pair is missing, as seen in \( R_2 \). Meanwhile, both the empty relation and relations where all pairs satisfy the reverse condition, like \( R \) and \( S \), maintain symmetry.
Example
Consider a relation \( R \) defined on the set of integers \( \mathbb{Z} \), where:
Proof of Symmetry:
To prove that \( R \) is symmetric, assume \( x R y \). By the definition of the relation, this implies that \( |x - y| \) is divisible by 3. That is:
Now consider \( y R x \). For this to hold, we must show that \( |y - x| \) is divisible by 3. Using the property of absolute values, we know:
Since \( |x - y| \) is divisible by 3, it follows that \( |y - x| \) is also divisible by 3. Thus, \( y R x \) holds whenever \( x R y \) holds.
Conclusion:
By showing that \( x R y \) implies \( y R x \), we conclude that the relation \( R \) is symmetric. This symmetry arises from the fact that absolute differences \( |x - y| \) and \( |y - x| \) are equal, preserving divisibility by 3 in both directions.
is perpendicular to
Let \( S \) be the set of all possible straight lines in a plane. Define a relation \( R \) on \( S \) as follows:
To prove that \( R \) is symmetric, assume \( L_1 R L_2 \). By the definition of the relation, this means that \( L_1 \) is perpendicular to \( L_2 \). In geometry, if one line is perpendicular to another, the reverse is also true. That is:
Hence, if \( L_1 R L_2 \), it follows that \( L_2 R L_1 \).
Since \( L_1 R L_2 \) implies \( L_2 R L_1 \), the relation \( R \) is symmetric. This symmetry is inherent to the geometric property of perpendicularity, which ensures that if one line is perpendicular to another, the reverse is automatically true.
Another sysmmetric relation
Let a relation \( R \) be defined on the set of natural numbers \( \mathbb{N} \), where:
Proof of Symmetry:
To prove that \( R \) is symmetric, assume \( x R y \). By the definition of \( R \), this implies:
We need to prove \( y R x \), which means we must show that \( 3y + 4x \) is divisible by 7.
Start with the given condition:
Rewriting \( 3x + 4y \) to find \( 3y + 4x \), we use modular arithmetic. Multiply \( x \) and \( y \) by \( (7 - 4) \) and \( (7 - 3) \), respectively, to balance the coefficients:
Expanding the terms gives:
Simplify:
Since \( x, y, k \in \mathbb{N} \), \( x + y - k \in \mathbb{N} \). This shows that \( 3y + 4x \) is divisible by 7.
Thus:
Since \( x R y \) implies \( y R x \), the relation \( R \) is symmetric. This follows from the arithmetic properties of divisibility and the structure of natural numbers.
Transitive Relation
Consider a relation \( R \) defined on a set \( A \). The relation \( R \) is said to be transitive if:
In other words, if under a given relation \( R \), \( x \) is related to \( y \), and \( y \) is related to \( z \), then \( x \) must also be related to \( z \). This property ensures that the relation logically connects elements in a chain-like manner.
The concept of transitivity can be explored with simple questions. Consider the relationship "is a brother of." If \( A \) is the brother of \( B \), and \( B \) is the brother of \( C \), can we conclude that \( A \) is the brother of \( C \)? Yes, we can! This makes "brother" a transitive relationship. Now think about the relationship "is the father of." If \( A \) is the father of \( B \), and \( B \) is the father of \( C \), can we conclude that \( A \) is the father of \( C \)? No, we cannot! Hence, "brother" is transitive, but "father" is not.
To understand in depth consider the following examples:
Examples of Transitive and Non-Transitive Relations
Consider a set \( A = \{1, 2, 3, 4, 5\} \), and the following relations defined on \( A \):
1. Relation \( R = \{(1, 1), (1, 2), (2, 3), (1, 3)\} \)
We check whether \( R \) is transitive by analyzing the pairs:
- \( (1, 2) \in R \) and \( (2, 3) \in R \).
- By the condition for transitivity, if \( 1 R 2 \) and \( 2 R 3 \), then \( 1 R 3 \) must also hold.
- Since \( (1, 3) \in R \), the condition is satisfied.
Thus, \( R \) is a transitive relation because it contains all required pairs to maintain transitivity.
2. Relation \( R_1 = \{(1, 2), (2, 3), (4, 5)\} \)
Here, we again check for transitivity:
- \( (1, 2) \in R_1 \) and \( (2, 3) \in R_1 \).
- For transitivity, \( 1 R 2 \) and \( 2 R 3 \) should imply \( 1 R 3 \), but \( (1, 3) \notin R_1 \).
- This absence violates the transitivity condition.
Thus, \( R_1 \) is not transitive, as it lacks the pair \( (1, 3) \).
3. Relation \( R_2 = \emptyset \)
The relation \( R_2 \) contains no pairs. For a relation to be non-transitive, there must exist pairs \( (x, y) \) and \( (y, z) \) such that \( (x, z) \) is not in the relation. However, since \( R_2 \) contains no pairs at all, there is no sequence of pairs that could violate transitivity.
By the principle of vacuous truth, \( R_2 \) is transitive because it does not fail the transitivity condition.
4. Relation \( R_4 = \{(1, 2)\} \)
This relation contains only a single pair. For transitivity, there must exist pairs \( (x, y) \) and \( (y, z) \) such that \( (x, z) \) needs to be checked. Since \( R_4 \) has only one pair, no such sequence exists, and hence transitivity is not violated.
Thus, \( R_4 \) is transitive, as it does not fail the condition.
These examples illustrate how transitivity depends on the logical connections between pairs in a relation.
How to prove that a relation is transitive or non-transitive?
To prove that a relation is not transitive, look for a counterexample. Specifically, find two pairs \( x R y \) and \( y R z \) in the relation, where \( x R z \) is not included. If such a counterexample exists, the relation is not transitive. This single example is enough to show that transitivity does not hold.
To prove that a relation is transitive, check every pair \( x R y \) and \( y R z \) in the relation to make sure that \( x R z \) is also included. If this holds for all pairs, then the relation is transitive. For relations on finite sets, you can check all pairs manually since there are a limited number of pairs to verify.
For relations on infinite sets, it’s impossible to check all pairs manually. Instead, we use logical reasoning. Assume \( x R y \) and \( y R z \) hold, and then use the definition of the relation to logically deduce whether \( x R z \) also holds. If this works for any arbitrary \( x \), \( y \), and \( z \), the relation is transitive.
For example, if a relation \( R \) is defined as \( x R y \iff f(x, y) \text{ holds} \), you use the properties of \( f(x, y) \) to show that \( x R y \) and \( y R z \) imply \( x R z \).
A Transitive Relation
Consider a relation \( R \) defined on a set \( S \), where \( S \) is the set of all possible straight lines in a plane. A line \( L_1 \in S \) is related to a line \( L_2 \in S \) if and only if \( L_1 \) is parallel to \( L_2 \). We aim to check if this relation is transitive.
To prove transitivity, assume \( L_1 R L_2 \) and \( L_2 R L_3 \). By the definition of the relation:
- \( L_1 R L_2 \) means \( L_1 \) is parallel to \( L_2 \), and
- \( L_2 R L_3 \) means \( L_2 \) is parallel to \( L_3 \).
By the geometric property of parallel lines, if \( L_1 \) is parallel to \( L_2 \), and \( L_2 \) is parallel to \( L_3 \), then \( L_1 \) is also parallel to \( L_3 \). Thus, \( L_1 R L_3 \).
Since \( L_1 R L_2 \) and \( L_2 R L_3 \) imply \( L_1 R L_3 \), the relation "is parallel to" is transitive.
Example
Consider a relation \( R \) defined on the set of natural numbers \( \mathbb{N} \), where:
Proof of Transitivity:
To prove that \( R \) is transitive, assume \( x R y \) and \( y R z \). By the definition of the relation:
- \( x R y \) implies \( 3x + 4y = 7k_1 \), where \( k_1 \in \mathbb{N} \), and
- \( y R z \) implies \( 3y + 4z = 7k_2 \), where \( k_2 \in \mathbb{N} \).
Adding these two equations gives:
Simplify:
Rearranging:
Factorize:
Since \( k_1 + k_2 - y \) is an integer (as \( k_1, k_2, y \in \mathbb{N} \)), this shows that \( 3x + 4z \) is divisible by 7. Hence, \( x R z \).
Conclusion:
Since \( x R y \) and \( y R z \) imply \( x R z \), the relation \( R \) is transitive. This follows directly from the arithmetic structure of the relation and logical reasoning.
Equivalence Relation
An equivalence relation on a set \( A \) is a relation \( R \subseteq A \times A \) that satisfies the following three properties for all \( a, b, c \in A \):
- Reflexive: Every element is related to itself. That is, \( a R a \) for all \( a \in A \).
- Symmetric: If \( a R b \), then \( b R a \). In other words, if one element is related to another, the reverse must also hold.
- Transitive: If \( a R b \) and \( b R c \), then \( a R c \). This means that if an element is related to a second and the second is related to a third, then the first is related to the third.
A relation \( R \) that satisfies all three of these properties is called an equivalence relation. Equivalence relations partition the set \( A \) into disjoint subsets called equivalence classes, where all elements in the same class are related to each other under \( R \).
Example
Consider the set \( A = \{1, 2, 3\} \) and the relation \( R = \{(1, 1), (2, 2), (3, 3)\} \).
Reflexive:
The relation \( R \) is reflexive because every element in \( A \) is related to itself:
Thus, \( R \) satisfies reflexivity.
Symmetric:
The relation \( R \) is symmetric because for every pair \( (x, y) \in R \), the reverse pair \( (y, x) \) is also in \( R \). In this case, since \( R \) contains only reflexive pairs (like \( (1, 1) \)), reversing the pairs has no effect. Thus, \( R \) satisfies symmetry.
Transitive:
The relation \( R \) is transitive because for any \( (x, y) \in R \) and \( (y, z) \in R \), we have \( (x, z) \in R \). For example:
- If \( (1, 1) \in R \) and \( (1, 1) \in R \), then \( (1, 1) \in R \).
- Similarly for \( (2, 2) \) and \( (3, 3) \). [No need to check like this though ever again]
Thus, \( R \) satisfies transitivity.
Hence, it si an equivalence relation.
is parallel to
Consider the set \( S \) of all possible straight lines in a plane. Define a relation \( R \) on \( S \) as follows:
This is a classic example of an equivalence relation, as it satisfies the properties of reflexivity, symmetry, and transitivity.
Reflexive:
The relation \( R \) is reflexive because every line is parallel to itself. For any line \( L \in S \):
Thus, \( R \) satisfies reflexivity.
Symmetric:
The relation \( R \) is symmetric because if one line is parallel to another, the reverse is also true. For any lines \( L_1, L_2 \in S \):
This holds true by the geometric property of parallelism.
Transitive:
The relation \( R \) is transitive because if one line is parallel to a second, and the second is parallel to a third, then the first line is parallel to the third. For any lines \( L_1, L_2, L_3 \in S \):
This follows directly from the definition of parallel lines.
Conclusion:
Since the relation "is parallel to" satisfies reflexivity, symmetry, and transitivity, it is an equivalence relation.
Example
Consider a relation \( R \) defined on the set of integers \( \mathbb{Z} \), where:
We will show that this relation is reflexive, symmetric, and transitive, and hence an equivalence relation.
Reflexive:
For any \( x \in \mathbb{Z} \), consider \( |x - x| \).
Thus, \( x R x \), proving reflexivity.
Symmetric:
Assume \( x R y \). By definition, \( |x - y| \) is a multiple of 7.
Since \( |x - y| = |y - x| \), it follows that \( |y - x| \) is also a multiple of 7.
Thus, \( y R x \), proving symmetry.
Transitive:
Assume \( x R y \) and \( y R z \). By the definition of the relation:
This implies:
Adding these equations:
Since \( y \) cancels out, we get:
Taking mod on both sides,
Thus, \( |x - z| \) is a multiple of 7, meaning \( x R z \). Hence, \( R \) is transitive.
Skip if you do not know complex numbers
A relation \( R \) on the set of complex numbers \( \mathbb{C} \) is defined as:
We will prove that \( R \) is an equivalence relation by verifying reflexivity, symmetry, and transitivity.
Reflexivity:
To prove reflexivity, we need to show that any complex number \( z \) is related to itself under \( R \). For \( z_1 = z_2 = z \):
which is a real number. Hence, \( z R z \), and \( R \) is reflexive.
Symmetry:
To prove symmetry, assume \( z_1 R z_2 \). By definition, this implies:
Now consider \( z_2 R z_1 \). Reversing \( z_1 \) and \( z_2 \), we have:
Since \( -\frac{z_1 - z_2}{z_1 + z_2} \) is also real, \( z_2 R z_1 \). Thus, \( R \) is symmetric.
Transitivity:
To prove transitivity, assume \( z_1 R z_2 \) and \( z_2 R z_3 \). By definition, this means:
where \( k_1, k_2 \in \mathbb{R} \).
Rewriting these:
Now calculate:
Thus:
Since \( \frac{p - q}{p + q} \) is real, \( z_1 R z_3 \). Hence, \( R \) is transitive.
Since \( R \) is reflexive, symmetric, and transitive, we can conclude that it is an equivalence relation on \( \mathbb{C} \).
Inverse Relation
Let \( R \) be a relation defined from a set \( A \) to a set \( B \). The inverse relation of \( R \), denoted as \( R^{-1} \), is obtained by swapping the positions of the elements in each ordered pair of \( R \). Formally, it is defined as:
This means that if \( (a, b) \) is in \( R \), then \( (b, a) \) will be in \( R^{-1} \). The inverse relation is useful when reversing the direction of the relationship between elements in \( A \) and \( B \).
Examples:
-
Finite Relation:
Let \( R = \{(1, 2), (1, 3), (2, 4), (3, 2)\} \).
To find \( R^{-1} \), swap each pair:\[ R^{-1} = \{(2, 1), (3, 1), (4, 2), (2, 3)\}. \]This means that if \( 1 \) is related to \( 2 \) in \( R \), then \( 2 \) is related to \( 1 \) in \( R^{-1} \).
-
Relation on \( \mathbb{R}^2 \):
Consider \( S = \{(x, y) \in \mathbb{R}^2 : 3x + 4y = 1\} \).
For \( R^{-1} \), interchange \( x \) and \( y \) in the equation:\[ S^{-1} = \{(x, y) \in \mathbb{R}^2 : 3y + 4x = 1\}. \]This means the inverse relation reverses the roles of \( x \) and \( y \) in the original equation.
-
Graphical Relation:
Consider \( T = \{(x, y) \in \mathbb{R}^2 : x = \sin y\} \).
To find \( T^{-1} \), swap \( x \) and \( y \) in the relation:
\[ T^{-1} = \{(x, y) \in \mathbb{R}^2 : y = \sin x\}. \]The inverse switches the input and output of the sine function.
The inverse relation is obtained by interchanging the elements in each ordered pair or swapping the variables in the defining equation. This process effectively reverses the direction of the original relation. For instance:
- If \( R \) represents "is the parent of," then \( R^{-1} \) would represent "is the child of."
- If \( R \) is a line equation, its inverse flips the roles of \( x \) and \( y \), altering its interpretation geometrically.
Composition of Relations
A relation \( R \) between two sets \( A \) and \( B \) is a subset of the Cartesian product \( A \times B \), defined as \( R \subseteq A \times B \). Similarly, a relation \( S \) between sets \( B \) and \( C \) is a subset of \( B \times C \), defined as \( S \subseteq B \times C \).
The composition of relations, denoted as \( S \circ R \), is a relation between \( A \) and \( C \) such that:
In simpler terms, the composition \( S \circ R \) relates an element \( a \in A \) to an element \( c \in C \) if there exists an intermediate element \( b \in B \) such that \( a \) is related to \( b \) through \( R \), and \( b \) is related to \( c \) through \( S \).
Take a look at the following example to understand the above definition:
Consider the sets:
- \( A = \{\text{Richard}, \text{Robert}, \text{Alexander}, \text{Amelia}\} \): representing individuals in the first generation.
- \( B = \{\text{John}, \text{Max}, \text{Jimmy}, \text{Sophia}, \text{Justin}\} \): representing individuals in the second generation.
- \( C = \{\text{June}, \text{Kyle}, \text{Eden}, \text{Billie}, \text{Tim}\} \): representing individuals in the third generation.
Define two relations:
-
\( R \): "is the father of," which relates elements in \( A \) to \( B \):
\[ R = \{(\text{Richard}, \text{John}), (\text{Richard}, \text{Jimmy}). (\text{Robert}, \text{Max}), (\text{Alexander}, \text{Sophia}), (\text{Amelia}, \text{Justin})\}. \] -
\( S \): "is the father of," which relates elements in \( B \) to \( C \):
\[ S = \{(\text{John}, \text{Kyle}), (\text{John}, \text{Eden}), (\text{Max}, \text{Billie}), (\text{Jimmy}, \text{June}), (\text{Jimmy}, \text{Tim})\}. \]
Now, the composite relation \( S \circ R \) is defined as "is the grandfather of," directly relating elements of \( A \) to \( C \).
We compute \( S \circ R \) by looking for pairs \( (a, c) \) where \( a \in A \), \( c \in C \), and there exists \( b \in B \) such that \( (a, b) \in R \) and \( (b, c) \in S \).
-
From \( (\text{Richard}, \text{John}) \in R \) and \( (\text{John}, \text{Kyle}) \in S \), we get: \( (\text{Richard}, \text{Kyle}) \in S \circ R \).
-
From \( (\text{Richard}, \text{John}) \in R \) and \( (\text{John}, \text{Eden}) \in S \), we get: \( (\text{Richard}, \text{Eden}) \in S \circ R \).
-
From \( (\text{Richard}, \text{Jimmy}) \in R \) and \( (\text{Jimmy}, \text{June}) \in S \), we get: \( (\text{Richard}, \text{June}) \in S \circ R \).
-
From \( (\text{Richard}, \text{Jimmy}) \in R \) and \( (\text{Jimmy}, \text{Tim}) \in S \), we get: \( (\text{Richard}, \text{Tim}) \in S \circ R \).
-
From \( (\text{Robert}, \text{Max}) \in R \) and \( (\text{Max}, \text{Billie}) \in S \), we get:\( (\text{Robert}, \text{Billie}) \in S \circ R \).
Similarly, \( (\text{Robert}, \text{Billie}) \in S \circ R \) because \( (\text{Max}, \text{Billie}) \in S \).
Thus, the composite relation is:
The composition of relations \( S \circ R \) combines two consecutive relationships into one, bypassing the intermediate set. In this example, \( S \circ R \) defines "is the grandfather of" by combining two "is the father of" relations.
Example
Consider three sets:
A = {1, 2, 3, 4},
B = {a, b, c, d, e},
C = {0, 1, 5, 6, 7, 8}.
Define two relations:
The relation \( R \) is defined between \( A \) and \( B \):
\( R = \{(1, a), (2, a), (3, b), (3, c), (4, e)\} \).
The relation \( S \) is defined between \( B \) and \( C \):
\( S = \{(a, 1), (b, 5), (c, 5), (d, 6)\} \).
The goal is to find the composition \( S \circ R \), which directly relates elements in \( A \) to \( C \) by combining \( R \) and \( S \).
To compute \( S \circ R \), we need to find all pairs \((x, z)\) such that there exists a \( y \in B \) where \((x, y) \in R\) and \((y, z) \in S\).
-
From \((1, a) \in R\) and \((a, 1) \in S\), we conclude \((1, 1) \in S \circ R\). [shown by dotted lines in the figure]
-
From \((2, a) \in R\) and \((a, 1) \in S\), we conclude \((2, 1) \in S \circ R\).
-
From \((3, b) \in R\) and \((b, 5) \in S\), we conclude \((3, 5) \in S \circ R\).
-
From \((3, c) \in R\) and \((c, 5) \in S\), we again find \((3, 5) \in S \circ R\), which is already included.
Thus, the composite relation is:
\( S \circ R = \{(1, 1), (2, 1), (3, 5)\} \).
This composition shows the direct connection between elements of \( A \) and \( C \) by bypassing the intermediate set \( B \). For example, 1 is related to 1, 2 is related to 1, and 3 is related to 5. This process simplifies relationships across multiple sets while maintaining logical consistency.
Composition using Matrix Multiplication
We can also calculate the composition of relations using matrix representation, which is particularly useful for large relations. This method involves representing the relations as matrices and then using logical operations instead of arithmetic operations to compute the composition.
Let us consider an example to demonstrate this process.
Consider the sets:
A = {1, 2, 3, 4},
B = {a, b, c, d, e},
C = {0, 1, 5, 6, 7, 8}.
Define two relations:
R is a relation from A to B, where
R = {(1, a), (2, a), (3, b), (3, c), (4, e)}.
S is a relation from B to C, where
S = {(a, 1), (b, 5), (c, 5), (d, 6)}.
To calculate the composition \( S \circ R \), we will first represent these relations as matrices.
The relation matrix for \( R \) is constructed by assigning rows to elements of \( A \) and columns to elements of \( B \). If \((a, b) \in R\), then the corresponding entry in the matrix is 1; otherwise, it is 0. For \( R \), the matrix is:
Similarly, the relation matrix for \( S \) is constructed by assigning rows to elements of \( B \) and columns to elements of \( C \). For \( S \), the matrix is:
Now, to compute \( S \circ R \), we multiply \( M_R \) and \( M_S \) using logical operations: - Replace multiplication with AND (\(\land\)). - Replace addition with OR (\(\lor\)).
The resulting matrix represents the composition \( S \circ R \), which relates elements of \( A \) directly to \( C \). The calculation gives:
From this matrix, we extract the composite relation \( S \circ R \) by identifying non-zero entries. For instance:
- The first row corresponds to \( (1, 1) \in S \circ R \),
- The second row corresponds to \( (2, 1) \in S \circ R \),
- The third row corresponds to \( (3, 5) \in S \circ R \).
Thus, the composition \( S \circ R \) is:
\( S \circ R = \{(1, 1), (2, 1), (3, 5)\} \).
Equivalence Classes
Consider a set \( C \), which consists of all circles in a plane. Define a relation \( R \) on \( C \) such that \( c_1 R c_2 \) if and only if the circle \( c_1 \) is concentric to the circle \( c_2 \). In this context, \( c_1 \) and \( c_2 \) are concentric if they share the same center.
The relation \( R \) is an equivalence relation because it satisfies the properties of reflexivity, symmetry, and transitivity:
- Reflexivity: For any circle \( c \in C \), \( c R c \), because every circle is concentric to itself.
- Symmetry: If \( c_1 R c_2 \), then \( c_2 R c_1 \), because if \( c_1 \) is concentric to \( c_2 \), then \( c_2 \) must also be concentric to \( c_1 \).
- Transitivity: If \( c_1 R c_2 \) and \( c_2 R c_3 \), then \( c_1 R c_3 \), because if \( c_1 \) and \( c_2 \) share the same center, and \( c_2 \) and \( c_3 \) also share the same center, then \( c_1 \) and \( c_3 \) must have the same center.
Thus, \( R \) is an equivalence relation.
An interesting property of equivalence relations is that they partition the set \( C \) into distinct subsets called equivalence classes. In this case, each equivalence class consists of all circles that are concentric with a specific circle.
For example, consider a circle \( c_1 \in C \). All circles that are concentric to \( c_1 \) form one equivalence class. Let us call this class "Class 1." Similarly, if there is another circle \( c_2 \notin \text{Class 1} \), all circles concentric to \( c_2 \) form a different equivalence class, say "Class 2." This process continues, and each equivalence class represents a distinct group of concentric circles.
From the diagram, you can see multiple equivalence classes of circles. Each group of concentric circles forms one class, and no circle in one class is concentric to any circle in another class. For example:
- Class 1 contains all circles concentric to a circle \( c_1 \).
- Class 2 contains all circles concentric to a circle \( c_2 \), which is not concentric with \( c_1 \).
Within each equivalence class, any circle can be chosen as the representative of the class. For instance, \( c_1 \) may represent Class 1, and \( c_2 \) may represent Class 2. We denote the equivalence class of \( c_1 \) as \( [c_1] \), which is defined as:
This definition implies that \( [c_1] \) contains all circles in \( C \) that are concentric to \( c_1 \). Similarly, the equivalence class of \( c_2 \) is \( [c_2] \), containing all circles concentric to \( c_2 \).
In conclusion, the set \( C \) is partitioned into equivalence classes by the relation \( R \), where each equivalence class represents a unique group of concentric circles. This idea generalizes to any equivalence relation, as it always divides the set into non-overlapping equivalence classes.
Definition
An equivalence class is a subset of a set \( A \) formed under an equivalence relation \( R \). For an element \( a \in A \), the equivalence class \( [a] \) consists of all elements \( x \in A \) that are related to \( a \) by \( R \). Formally, it is defined as
This means that every element in \( [a] \) shares the property defined by the relation \( R \) that makes it equivalent to \( a \).
Within an equivalence class, any element can act as a representative of the class. For instance, if \( [a] \) is the equivalence class containing \( a \), then \( a \) is a natural choice as a representative. However, any other element \( b \in [a] \) can also serve as a representative, because if \( b \in [a] \), it implies \( b R a \), meaning \( b \) is equivalent to \( a \). Thus, the equivalence class \( [a] \) can be referred to as \( [b] \), as long as \( b \) belongs to \( [a] \).
If two elements \( a, b \in A \) are related, i.e., \( a R b \), then their equivalence classes are the same, \( [a] = [b] \). This follows from the definition of equivalence classes, as \( a R b \) ensures that every element related to \( a \) is also related to \( b \), and vice versa. In contrast, if \( a \not R b \), their equivalence classes \( [a] \) and \( [b] \) are distinct and disjoint. That is, no element can belong to both \( [a] \) and \( [b] \), and the intersection of these classes is empty, \( [a] \cap [b] = \emptyset \).
This disjointness arises naturally from the properties of an equivalence relation. If any element \( x \) belonged to both \( [a] \) and \( [b] \), it would mean \( x R a \) and \( x R b \), which implies \( a R b \). This contradicts the assumption that \( a \not R b \). Therefore, the equivalence classes partition the set \( A \) into non-overlapping subsets, ensuring that each element of \( A \) belongs to exactly one equivalence class.
In summary, an equivalence class is defined as the set of all elements related to a specific element \( a \). These classes partition the set \( A \) into distinct groups. Any element of a class can act as its representative, and equivalence classes are either identical (if their representatives are related) or disjoint (if their representatives are not related). This structure provides a clear way to organize elements of \( A \) based on the equivalence relation \( R \).
Prove that the relation \( R \) on \( \mathbb{Z} \) defined by \( x R y \) if and only if \( x - y \) is divisible by 2 is an equivalence relation. Find all equivalence classes of this relation.
Solution:
To show that \( R \) is an equivalence relation, we must verify that it satisfies reflexivity, symmetry, and transitivity.
-
Reflexivity: For any \( x \in \mathbb{Z} \), the difference \( x - x = 0 \), which is divisible by 2. Hence, \( x R x \), proving reflexivity. This means every integer is related to itself because the difference is always zero, which is divisible by any number, including 2.
-
Symmetry: If \( x R y \), then \( x - y \) is divisible by 2. In this case, the negative of this difference, \( -(x - y) = y - x \), is also divisible by 2. Thus, \( y R x \), proving symmetry. This reflects that if \( x \) is related to \( y \), \( y \) must also be related to \( x \), as the divisibility condition holds regardless of the direction of the subtraction.
-
Transitivity: If \( x R y \) and \( y R z \), then \( x - y \) and \( y - z \) are divisible by 2. Adding these, we get:
which is also divisible by 2. Hence, \( x R z \), proving transitivity. This property ensures that if \( x \) is related to \( y \) and \( y \) is related to \( z \), \( x \) is automatically related to \( z \).
Since \( R \) satisfies all three properties, it is an equivalence relation.
Next, we determine the equivalence classes under \( R \).
- Consider \( 0 \in \mathbb{Z} \). For any \( a \in \mathbb{Z} \), if \( a R 0 \), then \( a - 0 = a \) is divisible by 2. This means all integers that are multiples of 2 (even numbers) belong to the equivalence class of \( 0 \). Thus, the equivalence class \( [0] \) is:
Here, the class \( [0] \) groups all even numbers because they differ from \( 0 \) by a multiple of 2.
- Now consider \( 1 \in \mathbb{Z} \). For any \( a \in \mathbb{Z} \), if \( a R 1 \), then \( a - 1 \) is divisible by 2. This implies \( a = 2k + 1 \) for some \( k \in \mathbb{Z} \). Thus, all integers that are odd belong to the equivalence class of \( 1 \). Hence, the equivalence class \( [1] \) is:
This class groups all odd numbers because they differ from \( 1 \) by a multiple of 2.
Since every integer is either even or odd, these two equivalence classes, \( [0] \) and \( [1] \), cover all integers.
It is also important to note that the equivalence classes \( [0] \) and \( [1] \) are disjoint. If \( a \in [0] \), it means \( a \) is even, and if \( b \in [1] \), it means \( b \) is odd. There is no overlap between even and odd numbers, so \( [0] \cap [1] = \emptyset \). Furthermore, the union of these two classes is all integers, \( [0] \cup [1] = \mathbb{Z} \), confirming that these are the only equivalence classes.
Finally, any member of an equivalence class can serve as its representative. For instance, the class \( [0] \), which represents all even numbers, could also be written as \( [2] \), \( [4] \), or any other even number, because all even numbers are equivalent. Similarly, the class \( [1] \), which represents all odd numbers, could also be written as \( [-1] \), \( [3] \), or any other odd number. This shows the flexibility in choosing a representative.
Finally, the equivalence classes are:
These classes represent all even and odd integers, respectively. Together, they form a partition of \( \mathbb{Z} \), with no overlap and no integers left out.
Partitioning a Set
A partition of a set \( S \) is a collection of non-empty subsets \( S_1, S_2, \dots, S_n \) such that:
- The subsets are pairwise disjoint, meaning \( S_i \cap S_j = \emptyset \) for all \( i \neq j \), and
- The union of all subsets equals the entire set, \( S_1 \cup S_2 \cup \dots \cup S_n = S \).
In other words, a partition divides \( S \) into distinct pieces where every element of \( S \) belongs to exactly one subset \( S_i \).
Theorem: Equivalence Relation Induces a Partition
If we have an equivalence relation \( R \) defined on a set \( S \), then the set of all equivalence classes formed by \( R \) is a partition of \( S \).
Proof:
Each element \( a \in S \) belongs to an equivalence class \( [a] \). By the properties of equivalence relations:
1. Pairwise Disjointness: If \( [a] \neq [b] \), then \( [a] \cap [b] = \emptyset \). This is because if there is any overlap between two classes, their representatives \( a \) and \( b \) would be related, implying \( [a] = [b] \).
2. Exhaustiveness: The union of all equivalence classes covers the entire set \( S \), as every element \( a \in S \) is in its own equivalence class \( [a] \).
Thus, the set of equivalence classes \( \{[a] : a \in S\} \) forms a partition of \( S \).
Converse: Does Every Partition Create an Equivalence Relation?
Yes, every partition of a set \( S \) creates an equivalence relation.
Proof:
Suppose the set \( S \) is partitioned into subsets \( S_1, S_2, \dots, S_n \), where:
- \( S_i \cap S_j = \emptyset \) for \( i \neq j \), and
- \( S_1 \cup S_2 \cup \dots \cup S_n = S \).
Define a relation \( R \) on \( S \) as:
- Reflexivity: For any \( x \in S \), \( x \) belongs to some \( S_i \). Since \( x \) is in the same subset as itself, \( x R x \).
- Symmetry: If \( x R y \), then \( x \) and \( y \) are in the same subset \( S_i \). This means \( y R x \).
- Transitivity: If \( x R y \) and \( y R z \), then \( x \) and \( y \) are in the same subset \( S_i \), and \( y \) and \( z \) are also in \( S_i \). Thus, \( x \) and \( z \) are in \( S_i \), and \( x R z \).
Therefore, \( R \) is an equivalence relation. This shows that any partition of \( S \) naturally defines an equivalence relation on \( S \).
Counting Total Number of Equivalence Relations on a Set
The total number of equivalence relations on a set \( A \) is equal to the number of partitions that can be formed on \( A \). Each equivalence relation divides the set into disjoint equivalence classes, and these equivalence classes correspond directly to the partitions of the set.
A partition of a set \( A \) is a collection of non-empty, disjoint subsets such that every element of \( A \) belongs to exactly one subset. For a set of size \( n \), the number of partitions is given by the Bell number, \( B_n \).
Example: Partitions of \( A = \{a, b, c, d\} \)
Here are the 15 possible partitions of \( A = \{a, b, c, d\} \):
- \( \{a\}, \{b, c, d\} \)
- \( \{b\}, \{a, c, d\} \)
- \( \{c\}, \{a, b, d\} \)
- \( \{d\}, \{a, b, c\} \)
- \( \{a, b\}, \{c, d\} \)
- \( \{a, c\}, \{b, d\} \)
- \( \{a, d\}, \{b, c\} \)
- \( \{a\}, \{b\}, \{c, d\} \)
- \( \{a\}, \{c\}, \{b, d\} \)
- \( \{a\}, \{d\}, \{b, c\} \)
- \( \{b\}, \{c\}, \{a, d\} \)
- \( \{b\}, \{d\}, \{a, c\} \)
- \( \{c\}, \{d\}, \{a, b\} \)
- \( \{a\}, \{b\}, \{c\}, \{d\} \)
- \( \{a, b, c, d\} \)
Conclusion
For the set \( A = \{a, b, c, d\} \), there are 15 distinct partitions. Each partition corresponds to a unique equivalence relation on \( A \). Hence, there are exactly 15 equivalence relations possible on a set of size 4.