Inhabited set

Wikipedia, the free encyclopedia - Cite This Source

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

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.

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 $phi$, it is necessary for a specific value of z satisfying $phi$ 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).

References

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

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)
This article is licensed under the GNU Free Documentation License.
Last updated on Thursday October 04, 2007 at 08:01:53 PDT (GMT -0700)
View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation