The trek goes on

More path calculations

Continuing 0011, there are a couple more important theorems that can be proved with similar path calculations. The first one is Hedberg’s theorem: if a type has decidable equality, then it is a set. Or formally:

$$\mathrm{\Pi }(A:\mathcal{U})(\mathrm{\Pi }(xy:A)(x{=}_{A}y)+\mathrm{\neg }(x{=}_{A}y))\to \mathsf{isSet}A$$

A useful observation here is that $A$ having decidable equality implies

$$\begin{array}{}\text{(1)}& \mathrm{\Pi }(xy:A)\Vert x{=}_{A}y\Vert \to x{=}_{A}y\end{array}$$

where $\Vert \mathrm{\_}\Vert$ is propositional truncation (with $|\mathrm{\_}|$ as its constructor). Intuitively, having decidable equality means that for every $x{=}_{A}y$ we can produce an inhabitant or prove that the type is uninhabited, so if we know in advance that $x{=}_{A}y$ is inhabited (that is, we have $\Vert x{=}_{A}y\Vert$), then we can definitely produce an inhabitant. Type $\text{1}$ is a conditional version of $\mathsf{isProp}$, and we can largely repeat the argument in 0011 to create the equality structure required by $\mathsf{isSet}A$. Let $f$ be a function of Type $\text{1}$. Again attempting to relate $fxz$ and $fxy$, we can derive

$$\mathrm{\Pi }(xzy:A)\mathrm{\Pi }(p:z{=}_{A}y)p_{\ast }(fxz)=fxy$$

This is an equality between functions, which implies that applying both sides to the same argument yields the same result:

$$\mathrm{\Pi }(xzy:A)\mathrm{\Pi }(p:z{=}_{A}y)\mathrm{\Pi }(q:\Vert x{=}_{A}y\Vert )p_{\ast }(fxz)q=fxyq$$

To proceed, we need to figure out how the transportation $p_{\ast }$ works. The transportation has type

$$p_{\ast }:(\Vert x{=}_{A}z\Vert \to x{=}_{A}z)\to (\Vert x{=}_{A}y\Vert \to x{=}_{A}y)$$ That is, it needs to produce a function of type $\Vert x{=}_{A}y\Vert \to x{=}_{A}y$ from a function of type $\Vert x{=}_{A}z\Vert \to x{=}_{A}z$, and there seems to be only one sensible way: given an argument of type $\Vert x{=}_{A}y\Vert$, we transport it backwards along $p^{-1}$ to get an argument of type $\Vert x{=}_{A}z\Vert$, which is fed to the given function, producing a result of type $x{=}_{A}z$, and then we transport the result along $p$ to get the final result of type $x{=}_{A}y$. So we can rewrite the left-hand side of the equation and get

$$\mathrm{\Pi }(xzy:A)\mathrm{\Pi }(p:z{=}_{A}y)\mathrm{\Pi }(q:\Vert x{=}_{A}y\Vert )p_{\ast }(fxz(p_{\ast }^{-1}q))=fxyq$$

Here the transportation $p^{\ast }$ is the familiar one between equality types sharing the same base point, so we rewrite the transportation,

$$\mathrm{\Pi }(xzy:A)\mathrm{\Pi }(p:z{=}_{A}y)\mathrm{\Pi }(q:\Vert x{=}_{A}y\Vert )fxz(p_{\ast }^{-1}q)\cdot p=fxyq$$

move $fxz(p_{\ast }^{-1}q)$ to the right-hand side,

$$\mathrm{\Pi }(xzy:A)\mathrm{\Pi }(p:z{=}_{A}y)\mathrm{\Pi }(q:\Vert x{=}_{A}y\Vert )p=(fxz(p_{\ast }^{-1}q){)}^{-1}\cdot fxyq$$

and substitute $x$ for $z$ and $|p|$ for $q$:

$$\mathrm{\Pi }(xy:A)\mathrm{\Pi }(p:x{=}_{A}y)p=(fxx(p_{\ast }^{-1}|p|){)}^{-1}\cdot fxy|p|$$

The exact inhabitant produced on the right-hand side depends on $x$ and $y$ but not $p$ (since the third argument of $f$ is truncated), so for any $p$, $q:x{=}_{A}y$ we have

$$\begin{array}{rl}& p\\ =& (fxx(p_{\ast }^{-1}|p|){)}^{-1}\cdot fxy|p|\\ =& (fxx(q_{\ast }^{-1}|q|){)}^{-1}\cdot fxy|q|\\ =& q\end{array}$$

completing the proof. Note that Type $\text{1}$ is both sufficient (as shown above) and necessary for $A$ being a set. Sufficiency is shown above, and necessity is straightforward: $A$ being a set means that the equality types on $A$ are all mere propositions, so we can just eliminate any given $\Vert x{=}_{A}y\Vert$ with the equality type $x{=}_{A}y$ itself as the target type.

The second theorem says that the unconstrained law of excluded middle is incompatible with univalence, that is,

$$\mathrm{\neg }\mathrm{\Pi }(A:\mathcal{U})A+\mathrm{\neg }A$$

if the universe $\mathcal{U}$ is univalent. The same observation made at the beginning of the proof of Hedberg’s theorem is also useful here: the law of excluded middle implies

$$\begin{array}{}\text{(2)}& \mathrm{\Pi }(A:\mathcal{U})\Vert A\Vert \to A\end{array}$$

that is, from every inhabited type $A$ we can choose an element. Again, a function of Type $\text{2}$ preserves equality, which in this case implies that the function must make its choice for each type stably even when the elements of the type are permuted because univalence gives us the ability to permute the elements of a type by supplying an automorphism as an equivalence, but such choices are impossible. Technically, we start with a function $f$ of Type $\text{2}$, which preserves equality as before:

$$\mathrm{\Pi }(AB:\mathcal{U})\mathrm{\Pi }(p:A{=}_{\mathcal{U}}B)p_{\ast }(fA)=fB$$

Again this is an equation on functions, which should map equal arguments to equal results:

$$\mathrm{\Pi }(AB:\mathcal{U})\mathrm{\Pi }(p:A{=}_{\mathcal{U}}B)\mathrm{\Pi }(b:\Vert B\Vert )p_{\ast }(fA)b=fBb$$

The transportation $p_{\ast }:(\Vert A\Vert \to A)\to (\Vert B\Vert \to B)$ is one between functions, and hence can be expanded to transportations of arguments and results as before:

$$\mathrm{\Pi }(AB:\mathcal{U})\mathrm{\Pi }(p:A{=}_{\mathcal{U}}B)\mathrm{\Pi }(b:\Vert B\Vert )p_{\ast }(fA(p_{\ast }^{-1}b))=fBb$$

Since the second argument of $f$ is irrelevant, what this says is that the element chosen from $A$ by $f$, when transported along $p$, should be the same as the element chosen from $B$ by $f$. If we allow non-trivial transportation when $A$ and $B$ are the same, then the equation will lead to a contradiction, but this non-trivial transportation is exactly one of the things univalence can give us. Concretely, substitute $\mathsf{Bool}$ for both $A$ and $B$, the equality $\mathsf{ua}(\mathsf{not})$ manufactured by univalence from the bijective function $\mathsf{not}:\mathsf{Bool}\to \mathsf{Bool}$ for $p$, and an arbitrary element — say $|\mathsf{true}|$ — for $b$, and we’ll get

$$\mathsf{ua}(\mathsf{not}{)}_{\ast }(f\mathsf{Bool}(\mathsf{ua}(\mathsf{not}{)}_{\ast }^{-1}|\mathsf{true}|))=f\mathsf{Bool}|\mathsf{true}|$$

Rewriting the inner $\mathsf{ua}(\mathsf{not}{)}_{\ast }^{-1}|\mathsf{true}|$ to just $|\mathsf{true}|$ (which is ok since any two elements of a truncated type are equal) and observing that the outer $\mathsf{ua}(\mathsf{not}{)}_{\ast }:\mathsf{Bool}\to \mathsf{Bool}$ is just applying the function $\mathsf{not}$, we get

$$\mathsf{not}(f\mathsf{Bool}|\mathsf{true}|)=f\mathsf{Bool}|\mathsf{true}|$$

which is clearly contradictory since $\mathsf{not}$ doesn’t have a fixed point.