nLab
inhabited set

Context

Type theory

natural deduction metalanguage, practical foundations

  1. type formation rule
  2. term introduction rule
  3. term elimination rule
  4. computation rule

type theory (dependent, intensional, observational type theory, homotopy type theory)

syntax object language

computational trinitarianism = propositions as types +programs as proofs +relation type theory/category theory

logiccategory theorytype theory
trueterminal object/(-2)-truncated objecth-level 0-type/unit type
falseinitial objectempty type
proposition(-1)-truncated objecth-proposition, mere proposition
proofgeneralized elementprogram
cut rulecomposition of classifying morphisms / pullback of display mapssubstitution
cut elimination? for implicationcounit for hom-tensor adjunctionbeta reduction
introduction rule for implicationunit for hom-tensor adjunctioneta conversion
conjunctionproductproduct type
disjunctioncoproduct ((-1)-truncation of)sum type (bracket type of)
implicationinternal homfunction type
negationinternal hom into initial objectfunction type into empty type
universal quantificationdependent productdependent product type
existential quantificationdependent sum ((-1)-truncation of)dependent sum type (bracket type of)
equivalencepath space objectidentity type
equivalence classquotientquotient type
inductioncolimitinductive type, W-type, M-type
higher inductionhigher colimithigher inductive type
completely presented setdiscrete object/0-truncated objecth-level 2-type/preset/h-set
setinternal 0-groupoidBishop set/setoid
universeobject classifiertype of types
modalityclosure operator, (idemponent) monadmodal type theory, monad (in computer science)
linear logic(symmetric, closed) monoidal categorylinear type theory/quantum computation
proof netstring diagramquantum circuit
(absence of) contraction rule(absence of) diagonalno-cloning theorem
synthetic mathematicsdomain specific embedded programming language

homotopy levels

semantics

Contents

Idea

In set theory, an inhabited set or occupied set is a set that contains an element.

More generally, in type theory an inhabited type is a type that has a term.

At least assuming classical logic, this is the same thing as a set that is not empty. Usually inhabited sets are simply called ‘non-empty’, but the positive word ‘inhabited’ reminds us that this is the simpler notion, which emptiness is defined as the negation of.

The terms ‘inhabited’ and ‘occupied’ come from constructive mathematics. In constructive mathematics (such as the internal logic of some topos or generally in type theory), a set/type that is not empty is not already necessarily inhabited. This is because double negation is nontrivial in intuitionistic logic. All the same, many constructive mathematicians use the old word ‘non-empty’ with the understanding that it really means inhabited.

There is a distinction between ‘inhabited’ and ‘occupied’ spaces in Abstract Stone Duality (which probably corresponds to something about locales, should explain that here).

An inhabited set is the special case of an inhabited object in the topos Set.

Internal and external notions

In topos theory, one should distinguish two notions of “inhabited”. An object XX is internally inhabited if the unique morphism X1X \to 1 to a terminal object is an epimorphism. It is externally inhabited if there exists a global element, i.e., a morphism 1X1 \to X; such forces X1X \to 1 to be a retraction and hence epic, i.e., forces XX to be internally inhabited. The two notions coincide if the terminal object is projective.

A generally useful principle in formulating appropriate categorical properties of Set is that external and internal notions should coincide. A general default understanding across the nLab is that SetSet is a well-pointed topos whose terminal object 11 is projective and indecomposable. These latter properties of the terminal object hold for any well-pointed topos if the metalogic is classical; for purposes of constructive mathematics, we usually agree to add them in. In any event, we present a constructive/intuitionistic proof of the following result.

Proposition

In a well-pointed topos, an object XX which is not internally inhabited is empty (is an initial object).

Note that the negation “not” in this statement is an external one, which is what makes it nontrivial. If an object is internally “not inhabited”, then it is empty essentially by definition.

Proof

Let XU1X \to U \hookrightarrow 1 be the epi-mono factorization of the unique map X1X \to 1. Here m:U1m: U \hookrightarrow 1 is monic but not epic if X1X \to 1 is not epic, and we use this to prove U0U \cong 0. In that case, we have a map X0X \to 0, whence X0X \cong 0 since in a topos initial objects are strict. (For given X0X \to 0, the projection π 1:X×0X\pi_1: X \times 0 \to X has a section, and it follows that X0X \cong 0 since X×00X \times 0 \cong 0 and retracts of initial objects are initial. This also implies that for any VV the map i:0Vi: 0 \to V is monic: for it is obviously true that for any pair of maps h,k:A0h, k: A \to 0 we have that ih=iki h = i k implies h=kh = k, as AA is initial by strictness and this makes h=kh = k automatic.)

Let f:UΩf: U \to \Omega be the classifying map of the mono 1 U:UU1_U: U \to U, and let g:UΩg: U \to \Omega be the classifying map of the mono 0U0 \to U. There is no map 1U1 \to U, else m:U1m: U \to 1 would retract it and hence be epic. Hence it is vacuously true that fx=gxf x = g x for all x:1Ux: 1 \to U, and so f=gf = g by well-pointedness. Hence the subobjects 1 U1_U and 00 coincide, forcing U0U \cong 0. (In other words, the presence of a subobject classifier causes any generator to be a strong generator.)

Revised on May 19, 2014 06:15:37 by Mike Shulman (192.195.154.58)