equality (definitional, propositional, computational, judgemental, extensional, intensional, decidable)
isomorphism, weak equivalence, homotopy equivalence, weak homotopy equivalence, equivalence in an (∞,1)-category
Examples.
basic constructions:
strong axioms
further
In constructive mathematics, a set has decidable equality if any two elements of are either equal or not equal. Equivalently, has decidable equality if its equality relation is a decidable subset of . Sometimes one says that such a set is discrete, although of course this term has many meanings. Of course, in classical mathematics, every set has decidable equality. But the concept generalises in topos theory to the notion of decidable object.
Every finite set has decidable equality (though the same is not true for finitely-indexed or subfinite sets).
The natural numbers have decidable equality.
In fact, these examples come close to to exhausting the sets than can be proven to have decidable equality in intuitionistic logic; by BauerSwan18 there is a topos (the function realizability topos, which moreover satisfies countable choice, Markov's principle, and other axioms) in which all sets with decidable equality are countable (admit a surjection from a decidable subset of ). More precisely, although the statement “all sets with decidable equality are countable” is not true in that topos, every global object with decidable equality in that topos is countable.
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 constructively the set of real numbers may not have decidable equality.
In type-theoretic foundations, there are two different notions of decidable equality, depending on whether “or” is interpreted using sum types or disjunctions , i.e. the bracket type of sum types. The former notion of decidable equality is called untruncated decidable equality, while the latter notion is called truncated decidable equality. Since every type maps to its bracket, untruncated decidable equality implies truncated decidable equality.
On the other hand, if truncated decidable equality holds and is an h-set, i.e. it satisfies uniqueness of identity proofs, then and represent disjoint subobjects of . Thus is already a subobject of , so it is equivalent to its bracket, and untruncated decidable equality also holds.
The converse of this is also true: if untruncated decidable equality holds, then not only does truncated decidable equality also hold, but in fact is an h-set. This was first proven by Michael Hedberg; a proof can be found at Hedberg's theorem and in the references below. This fact is useful in homotopy type theory to show that many familiar types, such as the natural numbers, are h-sets.
For non-h-sets, the difference between untruncated decidable equality and truncated decidable equality can be dramatic. For instance, if we model homotopy type theory in a Boolean -topos (such as constructed classically), then every type satisfies truncated decidable equality (which is what it means for the logic to be boolean), but only the h-sets satisfy untruncated decidable equality (in accordance with Hedberg's theorem).
There is also a few definitions of decidable equality in dependent type theory, which rely on the boolean domain with its extensionality principle and the fact that that the decidable equality is always valued in the boolean domain.
The first definition states that decidable equality on a type is a binary function which comes with a family of equivalences
The second also relies on the fact that the boolean domain forms a univalent Tarski universe . Here, decidable equality on a type is a binary function which comes with a family of equivalences
Either way, this is typically how the natural numbers type is proven to have decidable equality, by defining a binary function into the boolean domain called observational equality and using the extensionality principle of the natural numbers.
Every set with decidable equality is locally finite.
Michael Hedberg, A coherence theorem for Martin-Löf’s type theory, J. Functional Programming, 1998
Nicolai Kraus, A direct proof of Hedberg’s theorem, blog post
Andrej Bauer and Andrew Swan, Every metric space is separable in function realizability, 2018, arxiv
Last revised on August 15, 2023 at 14:36:53. See the history of this page for a list of all contributions to it.