Relations

Binary Relations

A binary relation $R$ on a set $A$ is a subset of $A \times A$. We write $aRb$ (or $(a,b) \in R$) when $a$ is related to $b$.

Key Properties

Equivalence Relations

A relation that is reflexive, symmetric, and transitive is an equivalence relation. It partitions the domain into disjoint equivalence classes $[a] = \{b : aRb\}$.

Example: "same remainder mod 3" is an equivalence relation on $\mathbb{Z}$, with classes $[0], [1], [2]$.

def is_equivalence(relation, domain):
    return (is_reflexive(relation, domain) and
            is_symmetric(relation) and
            is_transitive(relation))

# R = {(1,1),(2,2),(3,3),(1,2),(2,1)} — two classes: {1,2} and {3}
R = {(1,1),(2,2),(3,3),(1,2),(2,1)}
print(is_equivalence(R, {1,2,3}))  # True

Your Task

Implement is_reflexive, is_symmetric, is_transitive, and is_equivalence.