Inhabited set

From Wikipedia, the free encyclopedia

In mathematics, a set A is inhabited if there exists an element a\in A. This is distinct from the set being nonempty in many forms of intuitionistic logic.

[edit] Comparison with nonempty sets

In classical logic, a set is inhabited if and only if it is not the empty set. These definitions diverge in intuitionistic logic, however. A set A is nonempty if it is not empty, that is, if

\lnot [\forall z (z \not \in A)].

It is inhabited if

\exists z (z \in A).

In intuitionistic logic, the negation of a universal quantifier is weaker than an existential quantifer, not equivalent to it as in classical logic.

[edit] Example

Because inhabited sets are the same as nonempty sets in classical logic, it is not possible to produce a model in the classical sense that contains a nonempty, noninhabited set. But it is possible to construct a Kripke model that does. It is also possible to use the BHK interpretation of intuitionism to produce an example of a nonempty, noninhabited set.

In each of these settings, the construction of a nonempty, noninhabited set relies on the intuitionistic interpretation of the existential quantifier. In an intutionistic setting, in order for \exists z \phi(z) to hold, for some formula φ, it is necessary for a specific value of z satisfying φ to be known.

For example, consider a subset X of {0,1} specified by the following rule: 0 belongs to X if and only if the Riemann hypothesis is true, and 1 belongs to X if and only if the Riemann hypothesis is false. Then X is not empty (since assuming that it is empty leads to a contradiction), but X is it not currently known to be occupied either. Indeed, if X is occupied, then either 0 belongs to it or 1 belongs to it, so the Riemann hypothesis is either true or false, but neither of these possibilities has yet been proved. By replacing the Riemann hypothesis in this example by a generic proposition, one can construct a Kripke model with a set that is neither empty nor inhabited (even if the Riemann hypothesis itself is ever proved or refuted).

[edit] References

D. Bridges and F. Richman. 1987. Varieties of Constructive Mathematics. Oxford University Press. ISBN 978-0521318020

This article incorporates material from Inhabited set on PlanetMath, which is licensed under the GFDL.