We begin with the elementary properties of propositions and sets needed for the construction of the natural numbers.

Definition 10.1.1. An anima \(P\) is called a proposition if the map \(p_P\colon P \to *\) is an embedding. Equivalently, the diagonal \(\Delta \colon P \to P \times P\) is an equivalence.

If a proposition \(P\) admits an absolute object \(x\colon * \to P\), then \(x\) is a section of the embedding \(p_P\colon P \to *\). Hence \(p_P\) is an equivalence by Lemma 1.6.24. In particular, if an absolute object of \(P\) exists, it is unique.

Definition 10.1.2. A set is an anima \(X\) such that the diagonal \(\Delta \colon X \to X \times X\) is an embedding, in the sense of Definition 1.6.19. We denote by \(\Set \subseteq \An\) the full subcategory spanned by the sets.

Thus a set is an anima in which equality of two objects is a property: if an isomorphism between them exists, it is unique.

Lemma 10.1.3 (Identity types of sets). An anima \(X\) is a set if and only if for every two objects \(x\) and \(y\) of \(X\) the mapping anima \(X(x,y)\) is a proposition.

Proof

Since \(X\) satisfies the groupoid condition, we have \(X \iso \Fun([1],X)\), and consequently the mapping anima \(X(x,y)\) fits in a pullback square as follows: Commutative diagram; see the PDF for its LaTeX source Since embeddings are closed under pullback, this proves the forward implication. Conversely, apply the hypothesis in context \(X\times X\) to the objects \(x=\pr_1\) and \(y=\pr_2\). Their mapping anima is the diagonal of \(X\), so the diagonal is an embedding.

Notation 10.1.4. Let \(X\) be a set and let \(x\) and \(y\) be objects of \(X\). We write \(x=y\) for the mapping anima \(X(x,y)\). Thus \(x=y\) is a proposition, and to give \(p:x=y\) is to identify \(x\) and \(y\).

We use the following standard terminology for sets.

Terminology 10.1.5. Let \(X\) and \(Y\) be sets.

  1. (i) An elementIn [LR03] this is called a generalized element. of \(X\), written \(x \in X\), is an object \(x\) of \(X\).

  2. (ii) A function \(f\colon X \to Y\) is a functor from \(X\) to \(Y\). Given an element \(x\) of \(X\) we write \(f(x)\) for the resulting element in \(Y\) (given by composing \(x\) and \(f\)).

  3. (iii) We say two functions \(f,g\colon X \to Y\) are equal, written \(f = g\), if there exists a (necessarily unique) identification between them.

  4. (iv) We say that \(f\) is a bijection if it is an equivalence. This is the case if and only if there exists a function \(g\colon Y \to X\) satisfying \(gf = \id_X\) and \(fg = \id_Y\).

Observation 10.1.6. When \(X\) and \(Y\) are sets, the category \(\Fun(X,Y)\) is again a set. Its elements are functions from \(X\) to \(Y\).

Example 10.1.7. Note that the terminal category \(*\) is a set: the diagonal \(\Delta\colon * \to * \times *\) is even an equivalence. We refer to \(*\) as the one-point set. Similarly the initial category \(\emptyset\) is a set, which we will refer to as the empty set.

Example 10.1.8. We will prove in Corollary 10.2.18 that the anima of natural numbers \(\N\) is a set. We will also see in Lemma 10.2.14 that the successor function identifies \(\N\) with the positive natural numbers. Together with the element \(0\), this gives a bijection \(\{0\}\sqcup\N\iso\N\).

Lemma 10.1.9 (Characterizations of propositions). Let \(X\) be an anima. The following are logically equivalent:

  1. (1) \(X\) is a proposition.

  2. (2) For any two \(x,y:X\), the type \(X(x,y)\) is contractible; in formulas \(\prod_{x,y:X} \isContr X(x,y)\).

  3. (3) For any two \(x,y:X\) we have an identification \(p : X(x,y)\); in formulas \(\prod_{x,y:X} X(x,y)\).

  4. (4) If we have an inhabitant \(x : X\), then \(X\) is contractible; in formulas \(X \to \isContr X\).

Proof

The equivalence between (1) and (2) follows from the characterization of embeddings between animae as fully faithful functors. The implication from (2) to (3) is obtained by forgetting the contraction.

Assume (3), and write \(f : \prod_{x,y:X}X(x,y)\) for the given family. If \(c : X\), then \(f(c,-)\) contracts \(X\) onto \(c\). This proves (4).

Finally, assume (4) and let \(x,y : X\). Since \(x\) inhabits \(X\), the anima \(X\) is contractible. It follows that \(X(x,y)\) is contractible, which proves (2).

Lemma 10.1.10 (Propositions are closed under exponentiation). Let \(Z\) be an anima and let \(P\) be a proposition. Then the mapping anima \(\Map(Z,P)\) is a proposition.

Proof

Under the canonical equivalence \[ \Map(Z,P\times P)\simeq\Map(Z,P)\times\Map(Z,P), \] the map induced by the diagonal \(\Delta_P\colon P\to P\times P\) identifies with the diagonal of \(\Map(Z,P)\). Since \(P\) is a proposition, \(\Delta_P\) is an equivalence, and hence so is the diagonal of \(\Map(Z,P)\).

Example 10.1.11 (Negations are propositions). For any anima \(Z\), its negation is the anima \[ \neg Z\coloneqq\Map(Z,\emptyset). \] Since \(\emptyset\) is a proposition, Lemma 10.1.10 shows that \(\neg Z\) is a proposition. For \(x,y:X\), we abbreviate \(x\neq y\coloneqq\neg(x=y)\). This does not require \(X\) to be a set.

To recognize a set, it suffices to consider automorphisms.

Lemma 10.1.12 (Characterizations of sets). Let \(X\) be an anima. The following are logically equivalent:

  1. (1) \(X\) is a set.

  2. (2) For any \(x,y : X\) and any two identities \(p,q : x=y\), we have \(p=q\).

  3. (3) For every \(x : X\) and every \(p : X(x,x)\), we have \(p=\id_x\).

Proof

The equivalence between (1) and (2) follows from Lemmas 10.1.3 and 10.1.9. The implication from (2) to (3) is the special case \(x=y\) and \(q=\id_x\).

Conversely, assume (3) and let \(p,q : x=y\). The composite \(q^{-1}\circ p\) is an automorphism of \(x\), hence is equal to \(\id_x\). Composing this equality with \(q\) gives \(p=q\), which proves (2).

10.1.1 Decidable equality

Definition 10.1.13. An anima \(X\) is said to have decidable equality if for each \(x,y: X\) we either have \(x=y\) or \(x\neq y\). In formulas \[ \texttt{hasDecidableEquality}(X) := \prod_{x,y : X} (x=y) \sqcup (x\neq y). \]

Hedberg’s theorem [Hed98] says that an anima with decidable equality is a set. Its proof uses the following notion.

Definition 10.1.14. We say that a map \(f\colon X\to Y\) of animae is wildly constant if we have a section of \(X\times_Y X \to X\times X\), i.e., an inhabitant of \[ \texttt{wconstant}(f) := \prod_{x,y:X} f(x) = f(y). \]

Lemma 10.1.15 (Hedberg). Let \(X\) be an anima and assume that for each \(x,y : X\) we have a wildly constant map \(x=y \to x=y\). Then \(X\) is a set.

Proof

Assume that for each \(x,y\) we have a wildly constant map \(f_{x,y} : x=y \to x=y\). First we note that for each \(p : x=y\) we have \(f_{x,y}(p) = p \circ f_{x,x}(\id_x)\); indeed, path induction on \(p\) reduces this assertion to the reflexivity identification at \(x\). Then for two arbitrary \(p,q : x=y\) we obtain an identification \[ p = f_{x,y}(p) \circ f_{x,x}(\id_x)^{-1} = f_{x,y}(q) \circ f_{x,x}(\id_x)^{-1} = q \] where we use the equality \(f_{x,y}(p)=f_{x,y}(q)\) coming from the fact that \(f_{x,y}\) is wildly constant.

Since \(p,q\) were arbitrary, it follows from Lemma 10.1.12 that \(X\) is a set.

Corollary 10.1.16 (Decidable equality implies being a set). Let \(X\) be an anima with decidable equality. Then \(X\) is a set.

Proof

By Hedberg’s lemma it suffices, for each \(x,y:X\), to construct a wildly constant map \(f\colon x=y \to x=y\). Decidable equality gives two cases.

  • • If \(p:x=y\), let \(f\) be the constant map with value \(p\).

  • • If \(e:x\neq y\), let \(f\) be the composite \(x=y \xrightarrow{e} \emptyset \to x=y\).

In the first case the map is constant by construction. In the second its domain is empty, so it is again wildly constant.

Exercise 10.1.17. Assuming the law of excluded middle (i.e. that there is a term \(\mathrm{LEM}_P : P\sqcup \neg P\) for each proposition \(P\)), prove the converse of Corollary 10.1.16, i.e., that every set has decidable equality.