nLab decidable relation

Idea

A relation in which either it or its negation is true.

Definition

A decidable binary relation $R$ on a set $S$ is a relation such that for all elements $a \in S$ and $b \in S$, $R(a, b)$ or $\neg R(a, b)$.

Examples

• Every set with decidable equality has a decidable equality relation and a decidable denial inequality relation.

• In the presence of excluded middle, every relation is a decidable relation.

See also

• decidable equality

• stable relation