Understanding Relations in Algebra

In mathematics, particularly in set theory and algebra, a relation is a way to describe a connection or association between elements of two sets. Relations form the foundation for many advanced topics, including functions, equivalence relations, and orderings.

1. Definition of Relation

Given two sets \( A \) and \( B \), a relation \( R \) from \( A \) to \( B \) is a subset of the Cartesian product \( A \times B \). Formally,

where

Each element of \( R \) is an ordered pair \( (a, b) \) indicating that \( a \) is related to \( b \) under the relation \( R \).

2. Domain and Range of a Relation

- The domain of \( R \) is the set of all first elements of the ordered pairs in \( R \):

- The range of \( R \) is the set of all second elements of the ordered pairs in \( R \):

3. Representation of Relations

Relations can be represented in multiple ways:

• Set of ordered pairs: Explicitly listing all pairs in \( R \).
• Matrix representation: Using a 0-1 matrix where rows correspond to elements of \( A \) and columns to elements of \( B \). A 1 indicates the pair is in the relation.
• Graphical representation: Drawing arrows from elements of \( A \) to elements of \( B \) to indicate related pairs.

Example: Let \( A = {1, 2} \), \( B = {3, 4} \), and \( R = {(1, 3), (2, 4)} \).Matrix:   3 41 [1 0]2 [0 1]

4. Types of Relations

When \( A = B \), relations on \( A \) can have special properties:

• Reflexive: \( \forall a \in A, (a, a) \in R \)
• Symmetric: If \( (a, b) \in R \), then \( (b, a) \in R \)
• Transitive: If \( (a, b) \in R \) and \( (b, c) \in R \), then \( (a, c) \in R \)

Relations satisfying all three properties are called equivalence relations. These partition the set into equivalence classes.

5. Set Operations Related to Relations

Relations are subsets of Cartesian products, so set operations apply:

• Union: \( R_1 \cup R_2 \) contains pairs in either \( R_1 \) or \( R_2 \).
• Intersection: \( R_1 \cap R_2 \) contains pairs common to both.
• Difference: \( R_1 - R_2 \) contains pairs in \( R_1 \) but not in \( R_2 \).

Also, the power set \( \mathcal{P}(S) \) of a set \( S \) is the set of all subsets of \( S \). If \( S \) has \( n \) elements, then

6. Important Properties of Sets and Relations

Some key properties and theorems useful in solving problems:

• The null set \( \emptyset \) is a subset of every set.
• Every set is a subset of itself.
• If \( A \subseteq B \), then \( A \cup B = B \) and \( A \cap B = A \).
• For finite sets, \( n(A \cup B) = n(A) + n(B) - n(A \cap B) \).
• The maximum size of \( A \cap B \) is \( \min(n(A), n(B)) \).

7. Cartesian Product and Its Properties

The Cartesian product \( A \times B \) is the set of all ordered pairs \( (a, b) \) with \( a \in A \) and \( b \in B \). Its cardinality is

Note that \( A \times B \neq B \times A \) in general, as ordered pairs are ordered.

8. Symmetric Difference of Sets

The symmetric difference \( A \oplus B \) is defined as

It contains elements in either \( A \) or \( B \), but not in both.

9. Common Mistakes to Avoid

• Confusing equality of sets with equivalence: sets are equal if they have exactly the same elements; they are equivalent if they have the same number of elements.
• For power sets, remember the cardinality is \( 2^n \), not \( n^2 \) or any other formula.
• When dealing with complements, always consider the universal set \( U \).
• Remember that the null set \( \emptyset \) is a subset of every set, but it is not an element of every set.

Worked Examples

Formula Bank

• Relation: \( R \subseteq A \times B \)
• Domain of \( R \): \( { a \in A : \exists b \in B, (a,b) \in R } \)
• Range of \( R \): \( { b \in B : \exists a \in A, (a,b) \in R } \)
• Power set cardinality: \( |\mathcal{P}(S)| = 2^{n(S)} \)
• Union cardinality: \( n(A \cup B) = n(A) + n(B) - n(A \cap B) \)
• Maximum intersection size: \( \max n(A \cap B) = \min(n(A), n(B)) \)
• Cartesian product cardinality: \( n(A \times B) = n(A) \times n(B) \)
• Symmetric difference: \( A \oplus B = (A - B) \cup (B - A) \)
• Subset properties:
  \( \emptyset \subseteq A \), \( A \subseteq A \), \( A \subseteq B \Rightarrow A \cup B = B \), \( A \subseteq B \Rightarrow A \cap B = A \)