Definition of smallest equivalence relation

I came across the term 'smallest equivalence relation' in the course of a proof I was working on. I have never thought about ordering relations. I googled the term and checked stackexchange and couldn't find a clear definition.

Is someone able to provide me a definition of what a smallest equivalence relation is and an example of one equivalence relation being smaller than another?

Solution 1:

I’m going to guess that the actual context was more like the smallest equivalence relation on $A$ satisfying such-and-so conditions. If that’s the case, what is intended is the intersection of all equivalence relations on $A$ satisfying the given conditions: the intersection of equivalence relations on $A$ is an equivalence relation on $A$, and this intersection is the smallest subset of $A\times A$ (smallest in the sense of $\subseteq$) that is an equivalence relation on $A$ and satisfies the given conditions.

Solution 2:

An equivalence relation is a set of ordered pairs, and one set can be a subset of another.

For any set $S$ the smallest equivalence relation is the one that contains all the pairs $(s,s)$ for $s \in S$. It has to have those to be reflexive, and any other equivalence relation must have those. The largest equivalence relation is the set of all pairs $(s,t)$.

For some in between examples, consider the set of integers. The equivalence relation "has the same parity as" is in between the smallest and the largest relations.

Think about how the relations "is congruent to mod $n$" are related by inclusion.

As @JiK comments, the equivalence relations get their "less than" order from the natural way that sets have such an order. That order is "partial" since there are pairs of equivalence relations such that neither is a subset of the other.

If you know the theorem that says that equivalence relations naturally correspond to partitions, you can translate the order structure. The partition $P$ is finer than the partition $Q$ if every block of $P$ is completely contained in some block of $Q$. Finer partitions correspond to smaller equivalence relations. In the finest partition every element of $S$ is in a block by itself - the smallest equivalence relation. In the coarsest partition all of $S$ is one block - the largest equivalence relation.

Solution 3:

Equivalence relations are (partially) ordered by implication; $\Theta \leq \Phi$ if and only if $$ x \Theta y \implies x \Phi y $$ is an identity.

In fact, this partial ordering is a complete lattice; the meet operation (a.k.a. the greatest lower bound) is given by logical and. That is, the equivalence relation $\Theta = \bigwedge_{i \in I} \Theta_i$ is the one defined by

$$x \Theta y \Longleftrightarrow \bigwedge_{i \in I} x \Theta_i y$$

or in terms of quantifiers rather than infinitary operations, $$x \Theta y \Longleftrightarrow \forall i \in I: x \Theta_i y $$

If you look at the graph of the relations, this can all be rephrased in terms of subsets and intersections.

A simple source of examples is to use the first isomorphism theorem — there is a bijective correspondence between congruences and quotients.

e.g. in terms of sets, quotients can be viewed as partitions of the set, and the correspondence is that the equivalence classes of an equivalence relation are the parts of the partition.

The smallest equivalence relation on a nonempty set $X$ corresponds to the partition whose classes are all singletons; it is equality. The largest equivalence relation is the one with just a single partition; the corresponding equivalence relation is the one where everything is related. The ordering on equivalence relations corresponds to whether one partition refines another.

Solution 4:

I don't know what you want it for, but it is possible to define the smallest equivalence relation on a set $S$ containing a given relation $R$. Here's the formula:

$$R^e = \bigcup_{n=1}^\infty [R\cup R^{-1} \cup 1_S]^n$$

We know that when $n=1$, we'll have $1_S$, satisfying reflexivity.

Symmetry follows by induction; the base case is clear because we added $R^{-1}$ to get the initial symmetry. Now let $(x,y) \in S^n$. If $(x,y) \in S^{n-1}$ we're done. Otherwise, $(x,y) = (x,a)(a,y)$ with each of those in some $S^k, S^{k'}$ for $k,k' < n$ and $k+k' = n$. In particular, that means that $(a,x),(y,a)$ are in each of those by the inductive hypothesis, and so $(y,a)(a,x) = (y,x) \in S^k S^{k'} = S^n$.

Finally, we know it is transitive because if we have $(x,y) \in R^e$ and $(y,z) \in R^e$ then each is in some $S^m,S^n$, and so their composition will be in $S^{m+n}$.

Finally, note that if $E$ is an equivalence relation containing $R$, we know that it contains $R\cup R^{-1} \cup 1_S$. Moreover, $EE \subseteq E$ because it is an equivalence relation, and so $E^n \subseteq E$, but that means any subset composed $n$ times with itself is in $E$, and that means $R^e \subseteq E$. This means we've found the smallest (by containment) equivalence relation containing $R$.