Equivalence Classes

Given a set, \(S\) and an equivalence relation, \(\sim\), the equivalence class, \(\alpha\), is defined as,

\[ \{ x \in S | x \sim \alpha \}\,.\]

An equivalence relation on a set \(X\) must satisfy three properties.

1. \(\alpha \sim \alpha\) for all \(\alpha\) in \(X\) (reflexivity)

2. \(\alpha \sim \beta\) implies \(\beta \sim \alpha\) for all \(\alpha\) and \(\beta\) in \(X\) (symmetry)

3. If \(\alpha \sim \beta\) and \(\beta \sim \gamma\), then \(\alpha \sim \gamma\) for all \(\alpha\), \(\beta\), and \(\gamma\) in \(X\) (transitivity)

Suppose we have a set \(S \subseteq \mathbb{Z}\) and \(X_i\), where \(i \in [ 0, N )\), are the equivalency classes. Then,

\[ S = \bigcup_{i = 0}^N X_i \,,\]

such that the infinite union of \(X_i\) covers \(S\) because each \(X_i\) consists of those integers where \(i\) equal \(k \in \mathbb{N}\) modulo \(N\).

For example, suppose \(N = 3\). The set \(X_0\) consists of \(\{ \dots, -6, -3, 0, 3, 6, 9, \dots \}\), \(X_1\) consists of \(\{ \dots, -5, -2, 1, 4, 7, 10, \dots \}\), and \(X_2\) consists of \(\{ \dots, -4, -1, 2, 5, 8, 11, \dots \}\). These union of these three sets cover the entire set of integers.

function generate_equivclasses(N; S)
    X = Array{Set{eltype(S)}, 1}(undef, N)
    for k in [0, 1, 2]
        X[k+1] = Set(filter(x -> mod(x, N) == k, S))
    end
    return X
end

N = 3;
S = collect(-15:15);

X = reduce((iter, el) -> union(iter, el), 
        generate_equivclasses(N, S=S))

@show X
> X = Set([-12, -11, 5, 12, -3, -6, 8, 1, 0, 6, -5,
>  -1, 11, 9, -2, 14, 3, -15, 7, -8, -7, -9, 4, 15,
>  13, 2, 10, -10, -13, -4, -14])

@show X == Set(S)
> X == Set(S) = true