# 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