natural deduction metalanguage, practical foundations
type theory (dependent, intensional, observational type theory, homotopy type theory)
computational trinitarianism =
propositions as types +programs as proofs +relation type theory/category theory
There are various different paradigms for the interpretation of predicate logic in type theory. In “logic-enriched type theory”, there is a separate class of “propositions” from the class of “types”. But we can also identify propositions with particular types. In the propositions as types-paradigm, every proposition is a type, and also every type is identified with a proposition (the proposition that it is an inhabited type).
By contrast, in the paradigm that may be called propositions as some types, every proposition is a type, but not every type is a proposition. The types which are propositions are generally those which “have at most one inhabitant” — in homotopy type theory this is called being of h-level 1 or being a (-1)-type. This paradigm is often used in the categorical semantics of type theory, such as the internal logic of various kinds of categories.
Under “propositions as types”, all type-theoretic operations represent corresponding logical operations (dependent sum is the existential quantifier, dependent product the universal quantifier, and so on). However, under “propositions as some types”, not every such operation preserves the class of propositions; this is particularly the case for dependent sum and disjunction(or). Thus, in order to obtain the correct logical operations, we need to reflect these constructions back into propositions somehow, finding the “underlying proposition”, corresponding to the (-1)-truncation/h-level 1-projection. This operation in type theory is called the bracket type (when denoted $[A]$); in homotopy type theory it can be identified with the higher inductive type $isInhab$.
In dependent type theory, the propositional truncation of a type $A$ is defined as the higher inductive type generated by the two constructors
In any dependent type theory with identity types, given type $A$, the support of $A$ denoted $supp(A)$ or $isInhab(A)$ or $\tau_{-1} A$ or $\| A \|_{-1}$ or $\| A \|$ or, lastly, $[A]$, is the higher inductive type defined by the two constructors
where in the last sequent on the right we have the identity type. (Voevodsky, HoTTLibrary)
This says that $supp(A)$ is the type which is universal with the property that the terms of $A$ map to it and that any two term of $A$ become equivalent in $supp(A)$.
data isinhab {i : Level} (A : Set i) : Set i where
inhab : A → isinhab A
inhab-path : (x y : isinhab A) → x ≡ y
The recursion principle for $supp(A)$ says that if $B$ is a mere proposition and we have $f: A \to B$, then there is an induced $g : supp(A) \to B$ such that $g(isinhab(a)) \equiv f(a)$ for all $a:A$. In other words, any mere proposition which follows from (the inhabitedness of) $A$ already follows from $supp(A)$. Thus, $supp(A)$, as a mere proposition, contains no more information than the inhabitedness of $A$.
The induction principle states that if we have a family of mere propositions $B(x)$ indexed by $x:A$ and we have $f:\prod_{x:A} B(isinhab(x))$, then there is an induced $g:\prod_{z:supp(A)} B(z)$ such that $g(isinhab(a)) \equiv f(a)$ for all $a:A$.
The inference rules for bracket types are as follows:
Suppose the dependent type theory has a univalent type of all propositions $(\mathrm{Prop}, \mathrm{El})$. Then the bracket type of $A$ could be defined as the type
Let $\mathbb{1}$ be the unit type and let $\mathbb{2}$ be the boolean domain. The bracket type of a type $A$ is the localization of $A$ at the unique function $\mathbb{2} \to \mathbb{1}$.
By definition, the type of functions $(\mathbb{1} \to \left[A\right]) \to (\mathbb{2} \to \left[A\right])$ is an equivalence of types.
This is the special case of the n-truncation modality as the n-truncation modality is localization at the unique map from the $(n + 1)$-dimensional sphere type to the unit type, and $\mathbb{2}$ is the zero-dimensional sphere type.
For more see at n-truncation modality.
Let $A * B$ denote the join type of $A$ and $B$, and let $A^{*(n)}$ be the iterated join type, inductively defined on the natural numbers by $A^{*(0)} \coloneqq \emptyset$ and $A^{*(n + 1)} \coloneqq A^{*(n)} * A$.
Then the propositional truncation of $A$ is the sequential colimit of the sequence of functions
Let $A$ be a type and $R(x, y)$ be a binary family of contractible types indexed by $x:A$ and $y:A$, so that the product projection function for the dependent sum type
is an equivalence of types. Then the propositional truncation of $A$ is the quotient set $A / R$. (The quotient set in dependent type theory can be defined using inference rules without propositional truncations.)
There is another definition of the bracket type as a higher inductive type using functions from the boolean domain. The bracket type is generated by the two constructors
The induction principle states that if we have a family of mere propositions $B(x)$ indexed by $x:A$ and we have $f:\prod_{x:A} B(\mathrm{isinhab}(x))$, then there is an induced $g:\prod_{z:\mathrm{supp}(A)} B(z)$ such that $g(\mathrm{isinhab}(a)) \equiv f(a)$ for all $a:A$. Here, a mere proposition is defined as a type $A$ for which every function from the boolean domain is a weakly constant function, or equivalently, that $f:\mathrm{bool} \to A$ satisfies $f(\mathrm{false}) =_A f(\mathrm{true})$.
In section 7.3 of the HoTT Book UFP13, the authors give another definition of the propositional truncation using the hubs and spokes construction developed in section 6.7. Since the boolean domain is the zero-dimensional sphere, the propositional truncation of $A$ is a higher inductive type generated by
A function $[-]:A \to [A]$
For each function $r:\mathrm{bool} \to A$, a hub point $h(r):A$
For each function $r:\mathrm{bool} \to A$ and each boolean $x:\mathrm{bool}$, a spoke path $s_r(x):r(x) =_A h(r)$
In dependent type theory, a weakly constant function from type $A$ to $B$ is a function $f:A \to B$ with a dependent function $p:\prod_{x:A} \prod_{y:A} f(x) =_B f(y)$.
Given a weakly constant function $f:A \to B$ with $p:\prod_{x:A} \prod_{y:A} f(x) =_B f(y)$, by the recursion principle of bracket types, one has
such that
In particular, by the judgmental congruence rule for the introduction rule of function types, every weakly constant function $f:A \to B$ with $p:\prod_{x:A} \prod_{y:A} f(x) =_B f(y)$ factors through $[A]$ by
Weakly constant functions can also be regarded directly as functions $[A] \to B$, similar to how paths in $A$ can be regarded as functions $\mathbb{I} \to A$ from the the interval type rather than the application of said function along the path generator of the interval type.
Given a type $A$, there exists a function $A \to A \to \mathbb{I} \to [A]$ defined by
One presentation of the internal type theory of regular categories consists of dependent type theory with the unit type, strong extensional equality types?, strong dependent sums, and bracket types. (The internal logic of a regular category can alternatively be presented as a logic-enriched type theory?.)
The semantics of bracket types in a regular category $C$ is as follows.
A dependent type (a type in context $X$)
is interpreted in $C$ as an arbitrary morphism
The corresponding bracket type
is interpreted then as the image-factorization
Therefore $[A] \to X$ is a monomorphism, and hence the interpretation of a proposition about the elements of $X$.
homotopy level | n-truncation | homotopy theory | higher category theory | higher topos theory | homotopy type theory |
---|---|---|---|---|---|
h-level 0 | (-2)-truncated | contractible space | (-2)-groupoid | true/unit type/contractible type | |
h-level 1 | (-1)-truncated | contractible-if-inhabited | (-1)-groupoid/truth value | (0,1)-sheaf/ideal | mere proposition/h-proposition |
h-level 2 | 0-truncated | homotopy 0-type | 0-groupoid/set | sheaf | h-set |
h-level 3 | 1-truncated | homotopy 1-type | 1-groupoid/groupoid | (2,1)-sheaf/stack | h-groupoid |
h-level 4 | 2-truncated | homotopy 2-type | 2-groupoid | (3,1)-sheaf/2-stack | h-2-groupoid |
h-level 5 | 3-truncated | homotopy 3-type | 3-groupoid | (4,1)-sheaf/3-stack | h-3-groupoid |
h-level $n+2$ | $n$-truncated | homotopy n-type | n-groupoid | (n+1,1)-sheaf/n-stack | h-$n$-groupoid |
h-level $\infty$ | untruncated | homotopy type | ∞-groupoid | (∞,1)-sheaf/∞-stack | h-$\infty$-groupoid |
The original articles are
(which speaks of “mono types”) and
Frank Pfenning, Intensionality, extensionality, and proof irrelevance in modal type theory, In Proceedings of the 16th Annual Symposium on Logic in Computer Science (LICS’01), June 2001.
Steve Awodey, Andrej Bauer, Propositions as $[$Types$]$, Journal of Logic and Computation, 14 (2004) 447-471 [doi:10.1093/logcom/14.4.447, pdf]
Discussion in the context of homotopy type theory:
Exposition:
Formalization:
Vladimir Voevodsky, The hProp version of the “inhabited” construction. (web)
Discussion in the more general context of $n$-truncations:
More on the universal property of propositional truncation:
For propositional truncations as sequential colimits, see section 26.5 of
as well as section 16.2 of the lecture notes:
For n-truncations as localizations at sphere types, see:
That propositional truncations with judgmental computation rules along with the boolean domain imply function extensionality:
Last revised on July 6, 2024 at 11:37:49. See the history of this page for a list of all contributions to it.