category of sets and relations

notation: $\mathbf{Rel}$
objects: sets
morphisms: A morphism from $A$ to $B$ is a relation, i.e. a subset of $A \times B$ .
nLab Link
Related categories: $\mathbf{Set}$

This category is self-dual as it can be: There is an isomorphism $\mathbf{Rel} \cong \mathbf{Rel}^{\mathrm{op}}$ that is the identity on objects and maps a relation to its opposite relation. It is the prototype of a dagger-category.

Properties

Properties from the database

Deduced properties

is locally essentially small

Since it is locally small, we deduce that it is locally essentially small.
has zero morphisms

Since it is pointed, we deduce that it has zero morphisms.
has an initial object

Since it is pointed, we deduce that it has an initial object.
has coproducts

Since it has disjoint coproducts, we deduce that it has coproducts.
has disjoint finite coproducts

Since it has disjoint coproducts, we deduce that it has disjoint finite coproducts.
has finite coproducts

Since it has disjoint finite coproducts, we deduce that it has finite coproducts.
is inhabited

Since it has a generator, we deduce that it is inhabited.
has countable coproducts

Since it has coproducts, we deduce that it has countable coproducts.
has binary coproducts

Since it has finite coproducts, we deduce that it has binary coproducts.
is connected

Since it has an initial object, we deduce that it is connected.
has a terminal object

Since it is pointed, we deduce that it has a terminal object.
is well-copowered

Since it is self-dual and is well-powered, we deduce that it is well-copowered.
has products

Since it is self-dual and has coproducts, we deduce that it has products.
has finite products

Since it is self-dual and has finite coproducts, we deduce that it has finite products.
has binary products

Since it is self-dual and has binary coproducts, we deduce that it has binary products.
has countable products

Since it is self-dual and has countable coproducts, we deduce that it has countable products.
has a cogenerator

Since it is self-dual and has a generator, we deduce that it has a cogenerator.

Non-Properties

Non-Properties from the database

is not preadditive
is not Cauchy complete
is not skeletal

trivial

Deduced Non-Properties*

is not small

Assume for a contradiction that it is small. Since it is small, we deduce that it is essentially small. Since it is essentially small and has products, we deduce that it is thin. Since it is thin, we deduce that it has equalizers. Since it has equalizers, we deduce that it is Cauchy complete. This is a contradiction since we already know that it is not Cauchy complete.
is not complete

Assume for a contradiction that it is complete. Since it is complete, we deduce that it has equalizers. Since it has equalizers, we deduce that it is Cauchy complete. This is a contradiction since we already know that it is not Cauchy complete.
is not cocomplete

Assume for a contradiction that it is cocomplete. Since it is cocomplete, we deduce that it has coequalizers. Since it has coequalizers, we deduce that it is Cauchy complete. This is a contradiction since we already know that it is not Cauchy complete.
is not cartesian closed

Assume for a contradiction that it is cartesian closed. Since it is pointed and is cartesian closed, we deduce that it is trivial. Since it is trivial, we deduce that it is essentially finite. Since it is essentially finite and has finite coproducts, we deduce that it is thin. Since it is thin, we deduce that it has coequalizers. Since it has coproducts and has coequalizers, we deduce that it is cocomplete. This is a contradiction since we already know that it is not cocomplete.
is not additive

Assume for a contradiction that it is additive. Since it is additive, we deduce that it is preadditive. This is a contradiction since we already know that it is not preadditive.
is not abelian

Assume for a contradiction that it is abelian. Since it is abelian, we deduce that it is additive. This is a contradiction since we already know that it is not additive.
is not finitely complete

Assume for a contradiction that it is finitely complete. Since it is finitely complete, we deduce that it has equalizers. Since it has equalizers, we deduce that it is Cauchy complete. This is a contradiction since we already know that it is not Cauchy complete.
is not finitely cocomplete

Assume for a contradiction that it is finitely cocomplete. Since it is finitely cocomplete, we deduce that it has coequalizers. Since it has coequalizers, we deduce that it is Cauchy complete. This is a contradiction since we already know that it is not Cauchy complete.
is not locally finitely presentable

Assume for a contradiction that it is locally finitely presentable. Since it is locally finitely presentable, we deduce that it is locally presentable. Since it is locally presentable and is self-dual, we deduce that it is thin. Since it is thin, we deduce that it has coequalizers. Since it has coproducts and has coequalizers, we deduce that it is cocomplete. This is a contradiction since we already know that it is not cocomplete.
is not locally presentable

Assume for a contradiction that it is locally presentable. Since it is locally presentable, we deduce that it is complete. This is a contradiction since we already know that it is not complete.
is not locally ℵ₁-presentable

Assume for a contradiction that it is locally ℵ₁-presentable. Since it is locally ℵ₁-presentable, we deduce that it is locally presentable. This is a contradiction since we already know that it is not locally presentable.
is not an elementary topos

Assume for a contradiction that it is an elementary topos. Since it is an elementary topos, we deduce that it is cartesian closed. This is a contradiction since we already know that it is not cartesian closed.
is not a Grothendieck topos

Assume for a contradiction that it is a Grothendieck topos. Since it is a Grothendieck topos, we deduce that it is an elementary topos. This is a contradiction since we already know that it is not an elementary topos.
does not have equalizers

Assume for a contradiction that it has equalizers. Since it has products and has equalizers, we deduce that it is complete. This is a contradiction since we already know that it is not complete.
does not have coequalizers

Assume for a contradiction that it has coequalizers. Since it has coproducts and has coequalizers, we deduce that it is cocomplete. This is a contradiction since we already know that it is not cocomplete.
does not have connected limits

Assume for a contradiction that it has connected limits. Since it has connected limits, we deduce that it has equalizers. This is a contradiction since we already know that it does not have equalizers.
does not have connected colimits

Assume for a contradiction that it has connected colimits. Since it has connected colimits, we deduce that it has coequalizers. This is a contradiction since we already know that it does not have coequalizers.
does not have a strict initial object

Assume for a contradiction that it has a strict initial object. Since it has a strict initial object and is pointed, we deduce that it is trivial. Since it is trivial, we deduce that it is a Grothendieck topos. This is a contradiction since we already know that it is not a Grothendieck topos.
does not have a strict terminal object

Assume for a contradiction that it has a strict terminal object. Since it is self-dual and has a strict terminal object, we deduce that it has a strict initial object. This is a contradiction since we already know that it does not have a strict initial object.
is not a groupoid

Assume for a contradiction that it is a groupoid. Since it is a groupoid, we deduce that it is left cancellative. Since it is left cancellative and has a terminal object, we deduce that it has a strict terminal object. This is a contradiction since we already know that it does not have a strict terminal object.
is not essentially small

Assume for a contradiction that it is essentially small. Since it is essentially small and has products, we deduce that it is thin. Since it is thin, we deduce that it has equalizers. This is a contradiction since we already know that it does not have equalizers.
is not thin

Assume for a contradiction that it is thin. Since it is thin, we deduce that it has equalizers. This is a contradiction since we already know that it does not have equalizers.
is not discrete

Assume for a contradiction that it is discrete. Since it is discrete, we deduce that it is skeletal. This is a contradiction since we already know that it is not skeletal.
is not essentially discrete

Assume for a contradiction that it is essentially discrete. Since it is essentially discrete, we deduce that it is thin. This is a contradiction since we already know that it is not thin.
is not finitary algebraic

Assume for a contradiction that it is finitary algebraic. Since it is finitary algebraic, we deduce that it is locally finitely presentable. This is a contradiction since we already know that it is not locally finitely presentable.
is not finite

Assume for a contradiction that it is finite. Since it is finite, we deduce that it is small. This is a contradiction since we already know that it is not small.
is not essentially finite

Assume for a contradiction that it is essentially finite. Since it is essentially finite and has finite products, we deduce that it is thin. This is a contradiction since we already know that it is not thin.
does not have pullbacks

Assume for a contradiction that it has pullbacks. Since it has binary products and has pullbacks, we deduce that it has equalizers. This is a contradiction since we already know that it does not have equalizers.
does not have pushouts

Assume for a contradiction that it has pushouts. Since it has binary coproducts and has pushouts, we deduce that it has coequalizers. This is a contradiction since we already know that it does not have coequalizers.
is not trivial

Assume for a contradiction that it is trivial. Since it is trivial, we deduce that it is finitary algebraic. This is a contradiction since we already know that it is not finitary algebraic.
does not have a subobject classifier

Assume for a contradiction that it has a subobject classifier. Since it has a subobject classifier, we deduce that it is finitely complete. This is a contradiction since we already know that it is not finitely complete.
is not infinitary distributive

Assume for a contradiction that it is infinitary distributive. Since it is infinitary distributive, we deduce that it is distributive. Since it is distributive, we deduce that it has a strict initial object. This is a contradiction since we already know that it does not have a strict initial object.
is not distributive

Assume for a contradiction that it is distributive. Since it is distributive, we deduce that it has a strict initial object. This is a contradiction since we already know that it does not have a strict initial object.
does not have exact filtered colimits

Assume for a contradiction that it has exact filtered colimits. Since it has exact filtered colimits, we deduce that it is finitely complete. This is a contradiction since we already know that it is not finitely complete.
is not Grothendieck abelian

Assume for a contradiction that it is Grothendieck abelian. Since it is Grothendieck abelian, we deduce that it is abelian. This is a contradiction since we already know that it is not abelian.
is not left cancellative

Assume for a contradiction that it is left cancellative. Since it is left cancellative and has an initial object, we deduce that it has a strict initial object. This is a contradiction since we already know that it does not have a strict initial object.
is not right cancellative

Assume for a contradiction that it is right cancellative. Since it is right cancellative and has an initial object, we deduce that it has a strict initial object. This is a contradiction since we already know that it does not have a strict initial object.
does not have wide pullbacks

Assume for a contradiction that it has wide pullbacks. Since it has wide pullbacks and has a terminal object, we deduce that it is complete. This is a contradiction since we already know that it is not complete.
does not have wide pushouts

Assume for a contradiction that it has wide pushouts. Since it has wide pushouts and has an initial object, we deduce that it is cocomplete. This is a contradiction since we already know that it is not cocomplete.
is not split abelian

Assume for a contradiction that it is split abelian. Since it is split abelian, we deduce that it is abelian. This is a contradiction since we already know that it is not abelian.
is not Malcev

Assume for a contradiction that it is Malcev. Since it is Malcev, we deduce that it is finitely complete. This is a contradiction since we already know that it is not finitely complete.

*This also uses the deduced properties.

Unknown properties

For these properties the database currently doesn't have an answer if they are satisfied or not. Please help to complete the data!

Special morphisms

Isomorphisms: bijective functions

For the non-trivial direction, assume that $R : A \to B$ is a relation which has an inverse relation $S : B \to A$ . For every $a \in A$ we have $(a,a) \in \mathrm{id}_A = S \circ R$ , so there is some $b \in B$ with $(a,b) \in R$ (and $(b,a) \in S$ ). This shows that $R$ is left-total, and for right-total the argument is similar. By symmetry, this also holds for $S$ . To show that $R$ is a function, assume $(a,b), (a,b') \in R$ . Choose some $b'' \in B$ with $(b'',a) \in S$ . It follows $(b'',b) \in S \circ R = \mathrm{id}_A$ , so $b'' = b$ . Similarly, $(b'',b') \in S \circ R = \mathrm{id}_A$ , so $b'' = b'$ . This shows that $R$ is a function, i.e. left-unique. That $R$ is injective, i.e. right-unique, follows by symmetry. Finally, $R$ is surjective since it is right-total.
Monomorphisms: A relation $R : A \to B$ is a monomorphism iff the map $R_* : P(A) \to P(B)$ defined by $T \mapsto \{b \in B : \exists \, a \in T: (a,b) \in R \}$ is injective.
Epimorphisms: A relation $R : A \to B$ is an epimorphism iff the map $R^* : P(B) \to P(A)$ defined by $S \mapsto \{a \in A : \exists \, b \in S: (a,b) \in R \}$ is injective.