Intereting Posts

No maximum(minimum) of rationals whose square is lesser(greater) than $2$.
How can the law of the excluded middle possibly be true if we acknowledge that some logical statements are undefined?
Sub-additivity for $\limsup \limits_{n\to\infty}$
What is the easiest way to generate $\mathrm{GL}(n,\mathbb Z)$?
How many distinct factors of $n$ are less than $x$?
Is “Partition of Unity” a property of B-spline bases
show that the ordered square is locally connected~
Does Stirling's formula give the correct number of digits for $n!\phantom{}$?
Probability question (Birthday problem)
How to prove $\sum\limits_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$?
If $\mathop{\mathrm{Spec}}A$ is not connected then there is a nontrivial idempotent
The relation between rational forms and Jordan forms.
Why is it that $\mathscr{F} \ne 2^{\Omega}$?
Counterexamples in Double Integral
Show that $A_n=\sum\limits_{k=1}^n \sin k $ is bounded?

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?

- There is a well ordering of the class of all finite sequences of ordinals
- Is the Event a Conditional Probability or an Intersection?
- Why non-measurable sets exist?
- Reading, Writing, and Proving Math: Cartesian Product
- Is every injective function invertible?
- Finite Cartesian Product of Countable sets is countable?

- $(A\cap B)\cup C = A \cap (B\cup C)$ if and only if $C \subset A$
- How to divide aleph numbers
- A “Cantor-Schroder-Bernstein” theorem for partially-ordered-sets
- Why is the collection of all groups considered a proper class rather than a set?
- Why cannot a set be its own element?
- Surjectivity of Composition of Surjective Functions
- liminf and limsup with characteristic (indicator) function
- The empty function and constants
- A intersection (A union B)
- Why does Cantor's Proof (that R is uncountable) fail for Q?

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.

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.

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.

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 \in E$. This means we’ve found the smallest (by containment) equivalence relation containing $R$.

- Reconstructing a Matrix in $\Bbb{R}^3$ space with $3$ eigenvalues, from matrices in $\Bbb{R}^2$
- prove the divergence of cauchy product of convergent series $a_{n}:=b_{n}:=\dfrac{(-1)^n}{\sqrt{n+1}}$
- Group structure on pointed homotopy classes
- Given $n$ linear functionals $f_k(x_1,\dotsc,x_n) = \sum_{j=1}^n (k-j)x_j$, what is the dimension of the subspace they annihilate?
- For all $1 \leq i < j \leq k$, the subtrees $T_i$ and $T_j$ have a vertex in common. Show that $T$ has a vertex which is in all of the $T_i$.
- Difference between “space” and “algebraic structure”
- Independence in infinite sequence of random variables
- Completeness of the Natural Numbers
- The general argument to prove a set is closed/open
- A combinatorial task I just can't solve
- Limit of $\sin (a^{n}\theta\pi)$ as $ n \to \infty$ where $a$ is an integer greater than $2$
- How to solve this equation if $x\in \mathbb{R}$, $x ^3+1 =2\sqrt { 2x-1 }$, find $x$
- Tough integrals that can be easily beaten by using simple techniques
- Normalizing every Sylow p-subgroup versus centralizing every Sylow p-subgroup
- What are power series used for? (a reference request)