decidable object

An object $X$ of a well-behaved category (such as a topos) is **decidable** if its equality relation $X\to X\times X$ is complemented, as a subobject of $X\times X$.

This means that in the internal logic of the category, it is true that “for any $x,y\in X$, either $x=y$ or $x\neq y$.” Of course, in a Boolean category, every object is decidable.

In constructive mathematics, where Set is not assumed Boolean, one says that a set $X$ has *decidable equality* if it is a decidable object of $\Set$.

A *decidable subobject* simply means a complemented subobject. Again, in constructive mathematics, a decidable subobject in $\Set$ is called a *decidable subset*.

Revised on July 4, 2009 11:54:06
by Toby Bartels
(71.104.230.172)