nLab
decidable object

An object X of a well-behaved category (such as a topos) is decidable if its equality relation XX×X is complemented, as a subobject of X×X.

This means that in the internal logic of the category, it is true that “for any x,yX, either x=y or xy.” 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)