# Equivalence relations in arbitrary categories

Let $$C$$ be a category and $$A\in\mathrm{ob}(C)$$. A relation is a subobject $$q:Q\hookrightarrow A^{\times 2}$$ and the quotient is defined as the coequalizer $$A/Q:=\mathrm{coeq}\left(Q\stackrel{q}{\hookrightarrow} A^{\times 2}\rightrightarrows A\right)$$ where the two maps are the two projections. Moreover, we can define what it means to be an equivalence relation: The inclusion $$q$$ should satisfy the following:

• Reflexivity: Consider the diagonal $$\Delta:A\to A^{\times 2}$$. Then there should be a map $$i:A\to Q$$ such that $$q\circ i=\Delta$$.
• Symmetry: Consider the flip $$t:A^{\times 2}\to A^{\times 2}$$. Then there should be an automorphism $$s:Q\to Q$$ such that $$t\circ q=q\circ s$$.
• Transitivity: Consider the map $$q\times_A q: Q\times_AQ\to A^{\times 2}\times_AA^{\times 2}$$ and the outer projections $$p:A^{\times 2}\times_AA^{\times 2}\to A^{\times 2}$$. Then there should be a map $$j:Q\times_A Q\to Q$$ such that $$p\circ (q\times_A q)=q\circ j$$.

Given an arbitrary relation $$q:Q\hookrightarrow A^{\times 2}$$, we can define $$\overline{Q}\stackrel{\overline{q}}{\hookrightarrow} A^{\times 2}$$ as the inital equivalence relation having a morphism $$i:Q\to \overline{Q}$$ such that $$\overline{q}\circ i=q$$. I claim that the canonical map $$A/Q\to A/\overline{Q}$$ is an isomorphism. In $$\mathbf{Set}$$, this is clear as building the coequalizer is the same as quotienting out the spanned equivalence relation. Is this also true in other categories?

• You treat $A^{\times 2}$ as an object, and you seem to invoke pullbacks. Do you mean the category has products and pullbacks? Do intend the category to have all finite limits, plus coequalizers? Or do you mean arbitrary categories, where you only require that these products etc exist for the given data? – Colin McLarty Aug 8 '19 at 18:01

Short answer :Yes, assuming $$\overline{Q}$$ exists and $$C$$ has kernel pairs (for example if it has finite limits).

For more details: The relation $$\overline{Q}$$ do not always exists, you need some assumption on the underlying categories, and there are various type of assumption that can work.

For example if $$\mathcal{C}$$ is a pretopos with a parametrized natural number object you can mimick the usual construction of the transitive closure of a relation internall to give a construction of $$\overline{Q}$$.

In a completely different style, if $$Sub(A \times A)$$ is small and order complete then a variant of the small object argument also allows to construct $$\overline{Q}$$.

But, assuming that $$\overline{Q}$$ exists, it is actually easy to see that assuming $$C$$ has Kernel pair, if $$\overline{Q}$$ exists, then the canonical map $$A/Q \rightarrow A/\overline{Q}$$ is always an isomorphisms.

Indeed, let $$R$$ the kernel pair of $$A \rightarrow A/Q$$, $$R$$ is an equivalence relation on $$A$$ containing $$Q$$, so $$\overline{Q} \subset R$$. It follows from the universal property of the quotient that $$A \rightarrow A/Q$$ factors as $$A \rightarrow A/\overline{Q} \rightarrow A/Q$$

the uniqueness part of both universal property shows that the map constructed $$A/\overline{Q} \leftrightarrows A/Q$$ are invers of each other.

The same argument also shows that $$A/R$$ is also isomorphic to these (but $$R$$ can actually be strictly bigger than $$Q$$).