decidable subset

In constructive mathematics, a subset $A$ of a set $X$ is called **decidable** if it is classified by a function from $X$ to the Boolean domain $\mathbf{2} = \{\bot, \top\}$ of classical truth values. Of course, in classical mathematics, $\mathbf{2}$ is the set of *all* truth values, so there every subset is decidable. (A decidable subset is alternatively called a **detachable** subset, at least in Fred Richman’s school.)

Equivalently, $A$ is a decidable subset of $X$ if every element of $X$ either does or does not belong to $A$.

A set $X$ has decidable equality if the equality relation is decidable as a subset of $X \times X$. This generalises in topos theory to the notion of decidable object.

Working with decidable subsets of sets with decidable equality makes constructive mathematics very much like classical mathematics. This is why constructivism has few consequences for basic combinatorics and algebra (although it does have important consequences for more advanced topics in those fields). In analysis, in contrast, constructivism matters right away, because the set of real numbers may have very few decidable subsets.

Revised on July 24, 2014 06:43:40
by Toby Bartels
(98.23.133.202)