1
$\begingroup$

I'm tasked with proving (or disproving) $Rel \cong Rel^{op}$. I just want to double-check my reasoning. Also keep in mind this is mostly a sketch proof - I'm just showing my overall thinking, and not looking to display formality, at least in this post. But if there are glaring errors, yeah, I'd like to deal with those.


So first we consider the categories $Rel, Rel^{op}$. Objects in each are sets, and arrows are relations. Specifically, $R$ is an arrow $R : A \rightarrow B$ defined by $R(A) = \{ (a,b) \in A \times B \;\;\; | \;\;\; a \; R \; b \}$

A noteworthy tidbit is that $Rel = Rel^{op}$. In the respect of the objects in each, that much is obvious; less trivial is the arrows. We take note: if $R : A \rightarrow B$, we can define an arrow by the converse relation $S : B \rightarrow A$.

Since there exists only one arrow in $Hom_{Rel}(A,B)$ corresponding to a given relation $R$ (things either are or are not related), then any such arrow $A \rightarrow B$ is unique for that $R$. Therefore, similarly, the arrow $A \rightarrow A$ is unique, for a fixed relation on $A$, and therefore $S \circ R = 1_A$ and $R \circ S = 1_B$.

(Note of contention: I'm not sure if I have to prove from the definitions of relations that the composition gives the identity. Personally I like the "uniqueness" argument, even if my wording is a bit murky, but I'm not sure if that's good enough. Point being, to any relation R from A to B, we can find an inverse relation S, and their composition gives the identity.)

In the dual category $Rel^{op}$, arrows reverse. But we have the uniqueness of arrows, so $R$ in $Rel$ becomes $S$ in $Rel^{op}$ (using our above definitions for arrows). This generalizes across all the arrows - each arrow becomes its inverse, and since all arrows are invertible, we get the original set of arrows - and (I think) suffices to show $Rel = Rel^{op}$.

Finally, regarding isomorphism, it is trivial. Assuming all the above is correct thus far, then we consider the category of small categories, i.e. $Cat$. Since it's a category itself and $Rel$ is a category there, it follows there is an identity functor to itself. Identity functors are trivially isomorphisms, and since $Rel = Rel^{op}$, $Rel \cong Rel$ implies $Rel \cong Rel^{op}.$


I'm very much not confident where relations are concerned, and the same for functors since they're new to me. Informality aside, though, is this a sufficient argument?

For the record, the idea of $Rel$ being self-dual came from Wikipedia:

https://en.wikipedia.org/wiki/Category_of_relations

A morphism in Rel is a relation, and the corresponding morphism in the opposite category to Rel has arrows reversed, just the converse relation. Thus Rel contains its opposite and is self-dual.

$\endgroup$
  • 2
    $\begingroup$ Saying that $\textbf{Rel} = \textbf{Rel}^\text{op}$ is a bit "evil". If you want to prove that $\textbf{Rel}$ is isomorphic to $\textbf{Rel}^\text{op}$ you should exhibit functors $F :\textbf{Rel} \to \textbf{Rel}^\text{op}$, and $G : \textbf{Rel}^\text{op} \to \textbf{Rel}$ such that $FG = Id_{\textbf{Rel}^\text{op}}$ and $GF = Id_{\textbf{Rel}}$. $\endgroup$ – Daniel Mroz Oct 24 '18 at 8:30
  • $\begingroup$ Well ... if we continue on my chain of logic that each arrow in $Rel$ is invertible/unique, and all arrows/objects of one are in the other, I think would be trivial to define a functor $F$ who sends each arrow to its inverse in $Rel^{op}$, another $G : Rel^{op} \rightarrow Rel$ that sends each arrow to its inverse in $Rel$, and both just send the sets to themselves. I think that might be sufficient (along with the uniqueness and invertibility from before) to show $FG$ and $GF$ are both identities and thus each is an isomorphism? Just kinda spitballing since it's late and I'm about to go to bed $\endgroup$ – Eevee Trainer Oct 24 '18 at 8:38
  • 2
    $\begingroup$ Not every arrow is invertible. Try the empty relation $\{*\}\to \{*\}$ $\endgroup$ – Maxime Ramzi Oct 24 '18 at 8:51
  • 2
    $\begingroup$ I think you are confused about the difference between the inverse relation and the converse. If $R : A \to B$ is a relation the converse relation $R^\dagger : B \to A$ always exists. It is defined by $(b,a) \in R^\dagger \iff (a,b) \in R$. But we do not in general have $R^\dagger \circ R = id$ (as Max says, consider the empty relation). So, you have the right idea for defining $F$ and $G$, but the key property you want to check is that $(R^\dagger)^\dagger = R$, not that $R^\dagger \circ R = id$. $\endgroup$ – Daniel Mroz Oct 24 '18 at 8:53
  • 2
    $\begingroup$ Yes, that would work. (Just make sure to show that the map sending objects to themselves and relations to their converse is indeed a functor, i.e. it preserves the identity, and composition.) $\endgroup$ – Daniel Mroz Oct 24 '18 at 10:05
0
$\begingroup$

Your situation follows from the following general claim by showing that converse is an involution.


Suppose we have a “contravariant identity on objects” functor $\_˘ : 𝒞 ⟶ 𝒞$, then 𝒞 is isomorphic to its dual.

Indeed, by definition, if $f : A → B ∈ 𝒞$ then $f ˘ : B → A ∈ 𝒞$ which is the same as saying $f ˘ : A → B ∈ 𝒞ᵒᵖ$. Hence, the functor $\_˘$ serves as a natural candidate to witness the isomorphism.

That it is an isomorphism follows immediately from that fact that it is an involution.


Examples of this include:

  • Relations with converse: $y \; R˘ \; x \quad≡\quad x \; R \; y$.
  • Groupoids with inverse: $f˘ \;:=\; f^{-1}$.
  • Matrices with transpose: $(A_{ji})˘ = A_{ij}$.
  • Monoids with any involution; e.g., lists with reversal.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.