5.4: Equivalence

A relation on a set is called an equivalence relation if it is reflexive, symmetric, and transitive. The equivalence class of an element \(a\) in a set \(A\) is the set of all elements in \(A\) that are related to a by this relation, denoted by:

\[[a]=\{x \in A \mid x R a\} \nonumber \]

Here, \([a]\) represents the equivalence class of \(a\), comprising all elements in \(A\) that are related to \(a\) through the relation \(R\). This illustrates the grouping of elements into equivalence classes.

Consider a set \(A\) defined as:

\[A=\{x \mid x \text { is a person living in a given building }\} \nonumber\]

# Define the set of people
A = Set(['p_1', 'p_2', 'p_3', 'p_4', 'p_5', 'p_6', 'p_7', 'p_8', 'p_9', 'p_10'])
A

{'p_8', 'p_6', 'p_1', 'p_2', 'p_10', 'p_7', 'p_9', 'p_3', 'p_4', 'p_5'}

Create sets for the people living on each floor of the building:

import pprint

# Define the floors as a dictionary, mapping floor names to sets of people
floors = {
    'first_floor': Set(['p_1', 'p_2', 'p_3', 'p_4']),
    'second_floor': Set(['p_5', 'p_6', 'p_7']),
    'third_floor': Set(['p_8', 'p_9', 'p_10'])
}

pprint.pprint(floors)

{'first_floor': {'p_3', 'p_4', 'p_1', 'p_2'},
 'second_floor': {'p_6', 'p_5', 'p_7'},
 'third_floor': {'p_10', 'p_8', 'p_9'}}

Let \(R\) be the relation on \(A\) described as follows:

\[x R y \text { iff } x \text { and } y \text { live in the same floor of the building. } \nonumber \]

# Define the relation R based on living on the same floor
R = Set([(x, y) for x in A for y in A if any(x in floors[floor] and y in floors[floor] for floor in floors)])
R

{('p_3', 'p_1'), ('p_7', 'p_7'), ('p_4', 'p_1'), ('p_4', 'p_3'), ('p_6', 'p_5'), ('p_9', 'p_9'), ('p_10', 'p_10'), ('p_5', 'p_7'), ('p_1', 'p_3'), ('p_6', 'p_6'), ('p_2', 'p_3'), ('p_1', 'p_1'), ('p_2', 'p_1'), ('p_3', 'p_4'), ('p_10', 'p_8'), ('p_8', 'p_9'), ('p_9', 'p_10'), ('p_4', 'p_4'), ('p_9', 'p_8'), ('p_1', 'p_4'), ('p_7', 'p_5'), ('p_8', 'p_10'), ('p_2', 'p_4'), ('p_7', 'p_6'), ('p_3', 'p_2'), ('p_5', 'p_5'), ('p_8', 'p_8'), ('p_6', 'p_7'), ('p_4', 'p_2'), ('p_5', 'p_6'), ('p_1', 'p_2'), ('p_2', 'p_2'), ('p_10', 'p_9'), ('p_3', 'p_3')}

This relation demonstrates the properties of an equivalence relation:

Reflexive: A person lives in the same floor as themselves.

def is_reflexive_set(A, R):
    reflexive_pairs = Set([(a, a) for a in A])
    return reflexive_pairs.issubset(R)

is_reflexive_set(A, R)

True

Symmetric: If person \(a\) lives in the same floor as person \(b\), then person \(b\) lives in the same floor as person \(a\).

def is_symmetric_set(relation_R):
    inverse_R = Set([(b, a) for (a, b) in relation_R])
    return relation_R == inverse_R

is_symmetric_set(R)

True

Transitive: If person \(a\) lives in the same floor as person \(b\) and person \(b\) lives in the same floor as person \(c\), then person \(a\) lives in the same floor as person \(c\).

G = DiGraph(list(R), loops=true)
G.is_transitive()

True