Martin Escardo, 24th March 2022
with minor improvements and additions June 2024.
This file is a apropos the discussion at the end of the file
Ordinals.NotationInterpretation2.
\begin{code}
{-# OPTIONS --safe --without-K #-}
open import UF.FunExt
module Taboos.P2 (fe : Fun-Ext) where
private
fe' : FunExt
fe' π€ π₯ = fe {π€} {π₯}
open import MLTT.Spartan
open import MLTT.Two-Properties
open import UF.Base
open import UF.ClassicalLogic
open import UF.DiscreteAndSeparated
open import UF.Equiv
open import UF.Equiv-FunExt
open import UF.Retracts
open import UF.Subsingletons
open import UF.Subsingletons-FunExt
\end{code}
The following map plays a central role in the investigations of this
file.
\begin{code}
Ο : (X : π€ Μ ) β π β (X β π)
Ο X n = Ξ» _ β n
\end{code}
Abbreviations.
\begin{code}
Οβ : {X : π€ Μ } β (X β π)
Οβ {π€} {X} = Ο X β
Οβ : {X : π€ Μ } β (X β π)
Οβ {π€} {X} = Ο X β
\end{code}
Recall that we say that a type X is empty to mean Β¬ X, namely X β π,
and nonempty to mean ¬¬ X.
In general, if the type X is a proposition we will write "Β¬ X" rather
than the synonym "is-empty X", and "¬¬ X" rather than the synonym
"is-nonempty X". Also, we will pronounce "¬¬ X" as "X is irrefutable"
when X is a proposition.
\begin{code}
emptiness-criterion : (X : π€ Μ ) β is-empty X β (Οβ οΌ Οβ)
emptiness-criterion {π€} X = (f , g)
where
f : Β¬ X β Οβ οΌ Οβ
f Ξ½ = dfunext fe (Ξ» (x : X) β π-elim (Ξ½ x))
g : Οβ οΌ Οβ β Β¬ X
g e x = zero-is-not-one
(β οΌβ¨ refl β©
Οβ x οΌβ¨ happly e x β©
Οβ x οΌβ¨ refl β©
β β)
nonemptiness-criterion : (X : π€ Μ ) β is-nonempty X β (Οβ β Οβ)
nonemptiness-criterion {π€} X = I (emptiness-criterion X)
where
I : type-of (emptiness-criterion X) β ¬¬ X β (Οβ β Οβ)
I (f , g) = (Ξ» (Ξ½ : ¬¬ X) (e : Οβ οΌ Οβ) β Ξ½ (g e)) ,
contrapositive f
\end{code}
The main notion studied in this file is the following:
\begin{code}
is-thinly-inhabited : π€ Μ β π€ Μ
is-thinly-inhabited X = is-equiv (Ο X)
being-thinly-inhabited-is-prop : {X : π€ Μ } β is-prop (is-thinly-inhabited X)
being-thinly-inhabited-is-prop {π€} {X} = being-equiv-is-prop fe' (Ο X)
\end{code}
The idea of the terminology "thinly" is that there are very few
elements in the type, but at the same time the type is nonempty. As we
shall see, this is actually a notion stronger than nonemptiness. But
this idea works only for types that have enough functions into the
booleans, called totally separated. We show below that if X is totally
separated and thinly inhabited then X is a proposition.
Exercise. A type X is thinly inhabited if and only if there is *any*
equivalence π β (X β π).
For propositions X, the thin inhabitedness of X is equivalent to the
map Ο X having a retraction Ο.
Ο X
π βͺ (X β π)
π β (X β π)
Ο
In general there can be many maps Ο with Ο β Ο X βΌ id, but there is at
most one if X is a proposition. We use the following lemma to prove
this:
\begin{code}
retraction-of-Ο-is-section : {P : π€ Μ }
β is-prop P
β (Ο : (P β π) β π)
β Ο β Ο P βΌ id
β Ο P β Ο βΌ id
retraction-of-Ο-is-section {π€} {P} i Ο h f = IV
where
I : (p : P) β Ο f οΌ f p
I p = Ο f οΌβ¨ ap Ο III β©
Ο (Ο P (f p)) οΌβ¨ h (f p) β©
f p β
where
II : f βΌ Ο P (f p)
II q = f q οΌβ¨ ap f (i q p) β©
f p οΌβ¨ refl β©
Ο P (f p) q β
III : f οΌ Ο P (f p)
III = dfunext fe II
IV : Ο P (Ο f) οΌ f
IV = dfunext fe I
Ο-having-retraction-is-prop : {X : π€ Μ }
β is-prop X
β is-prop (has-retraction (Ο X))
Ο-having-retraction-is-prop {π€} {X} i =
prop-criterion
(Ξ» (Ο , ΟΟ) β sections-have-at-most-one-retraction fe' (Ο X)
(Ο , retraction-of-Ο-is-section i Ο ΟΟ))
retraction-of-Ο-gives-thinly-inhabited : {P : π€ Μ }
β is-prop P
β has-retraction (Ο P)
β is-thinly-inhabited P
retraction-of-Ο-gives-thinly-inhabited {π€} {P} i (Ο , ΟΟ) =
qinvs-are-equivs (Ο P) (Ο , ΟΟ , retraction-of-Ο-is-section i Ο ΟΟ)
\end{code}
For the converse we don't need X to be a proposition, of course.
\begin{code}
thinly-inhabited-gives-retraction-of-Ο : {X : π€ Μ }
β is-thinly-inhabited X
β has-retraction (Ο X)
thinly-inhabited-gives-retraction-of-Ο {π€} {X} = equivs-are-sections (Ο X)
\end{code}
By construction, every π-valued function on a thinly inhabited type is
constant.
\begin{code}
constancy : {X : π€ Μ }
β is-thinly-inhabited X
β (f : X β π)
β Ξ£ n κ π , f οΌ Ξ» _ β n
constancy {π€} {X} ti f = β e ββ»ΒΉ f , ((inverses-are-sections' e f)β»ΒΉ)
where
e : π β (X β π)
e = Ο X , ti
\end{code}
Next we want to show that
P β is-thinly-inhabited P
for any proposition P, and we use the following lemma.
\begin{code}
point-gives-retraction-of-Ο : {X : π€ Μ }
β X
β has-retraction (Ο X)
point-gives-retraction-of-Ο {π€} {X} x = (Ξ³ , Ξ³Ο)
where
Ξ³ : (X β π) β π
Ξ³ f = f x
Ξ³Ο : Ξ³ β Ο X βΌ id
Ξ³Ο n = refl
point-gives-is-thinly-inhabited : {P : π€ Μ }
β is-prop P
β P
β is-thinly-inhabited P
point-gives-is-thinly-inhabited {π€} {P} i p =
retraction-of-Ο-gives-thinly-inhabited i (point-gives-retraction-of-Ο p)
\end{code}
Notice, however, that pointed types X other than propositions are not
thinly inhabited in general. An example is the type X := π, because there
are four maps X β π in this case, and we need exactly two to have an
equivalence.
We will see later that the following implication can't be reversed,
even for just propositions, unless weak excluded middle holds, so that
the notion of being thinly inhabited is stronger, in general, than
that of being nonempty.
\begin{code}
thinly-inhabited-gives-nonempty : {X : π€ Μ }
β is-thinly-inhabited X
β is-nonempty X
thinly-inhabited-gives-nonempty {π€} {X} ti Ξ½ = III
where
e : π β (X β π)
e = Ο X , ti
I : β e ββ»ΒΉ Οβ οΌ β e ββ»ΒΉ Οβ
I = ap (β e ββ»ΒΉ) (Οβ οΌβ¨ dfunext fe (Ξ» x β π-elim (Ξ½ x)) β©
Οβ β)
II = β οΌβ¨ (inverses-are-retractions' e β)β»ΒΉ β©
β e ββ»ΒΉ Οβ οΌβ¨ I β©
β e ββ»ΒΉ Οβ οΌβ¨ inverses-are-retractions' e β β©
β β
III : π
III = zero-is-not-one II
\end{code}
In some cases the implication
P β is-thinly-inhabited P
can be reversed:
\begin{code}
thinly-inhabited-emptiness-gives-emptiness
: {X : π€ Μ }
β is-thinly-inhabited (is-empty X)
β is-empty X
thinly-inhabited-emptiness-gives-emptiness h =
three-negations-imply-one (thinly-inhabited-gives-nonempty h)
thinly-inhabited-nonemptiness-gives-nonemptiness
: {X : π€ Μ }
β is-thinly-inhabited (is-nonempty X)
β is-nonempty X
thinly-inhabited-nonemptiness-gives-nonemptiness {π€} {X} =
thinly-inhabited-emptiness-gives-emptiness {π€} {is-empty X}
\end{code}
The following is a digression from our main aims. Recall that a type
is called discrete if it has decidable equality.
\begin{code}
Xβπ-discreteness-criterion : {X : π€ Μ }
β is-empty X + is-thinly-inhabited X
β is-discrete (X β π)
Xβπ-discreteness-criterion (inl Ξ½) f g = inl (dfunext fe (Ξ» x β π-elim (Ξ½ x)))
Xβπ-discreteness-criterion (inr h) f g = retract-is-discrete
(β-gives-β· (Ο _ , h))
π-is-discrete
f g
Pβπ-discreteness-criterion-necessity : {P : π€ Μ }
β is-prop P
β is-discrete (P β π)
β Β¬ P + is-thinly-inhabited P
Pβπ-discreteness-criterion-necessity {π€} {P} i Ξ΄ = Ο (Ξ΄ Οβ Οβ)
where
Ο : is-decidable (Οβ οΌ Οβ) β Β¬ P + is-thinly-inhabited P
Ο (inl e) = inl (fact e)
where
fact : Οβ οΌ Οβ β Β¬ P
fact e p = zero-is-not-one (ap (Ξ» f β f p) e)
Ο (inr n) = inr (retraction-of-Ο-gives-thinly-inhabited i (Ξ³ , Ξ³Ο))
where
h : (f : P β π) β is-decidable (f οΌ Οβ) β π
h f (inl _) = β
h f (inr _) = β
Ξ³ : (P β π) β π
Ξ³ f = h f (Ξ΄ f Οβ)
hβ : (d : is-decidable (Οβ οΌ Οβ)) β h Οβ d οΌ β
hβ (inl _) = refl
hβ (inr d) = π-elim (d refl)
hβ : (d : is-decidable (Οβ οΌ Οβ)) β h Οβ d οΌ β
hβ (inl e) = π-elim (n (e β»ΒΉ))
hβ (inr _) = refl
Ξ³Ο : Ξ³ β Ο P βΌ id
Ξ³Ο β = hβ (Ξ΄ Οβ Οβ)
Ξ³Ο β = hβ (Ξ΄ Οβ Οβ)
\end{code}
Added 25th March 2022. If every nonempty proposition is thinly inhabited,
then weak excluded middle holds. We use the following lemma to prove
this. Recall that the principle of weak excluded middle, which is
equivalent to De Morgan's Law, says that for every proposition P,
either ¬ P or ¬¬ P holds.
\begin{code}
thinly-inhabited-wem-lemma : (X : π€ Μ )
β is-thinly-inhabited (X + is-empty X)
β is-empty X + is-nonempty X
thinly-inhabited-wem-lemma X ti = II
where
Y = X + Β¬ X
f : Y β π
f (inl _) = β
f (inr _) = β
n : π
n = inverse (Ο Y) ti f
I : (k : π) β n οΌ k β Β¬ X + ¬¬ X
I β e = inr Ο
where
Iβ = f οΌβ¨ (inverses-are-sections (Ο Y) ti f)β»ΒΉ β©
Ο Y n οΌβ¨ ap (Ο Y) e β©
(Ξ» _ β β) β
Ο : ¬¬ X
Ο u = zero-is-not-one
(β οΌβ¨ (ap (Ξ» - β - (inr u)) Iβ)β»ΒΉ β©
f (inr u) οΌβ¨ refl β©
β β)
I β e = inl u
where
Iβ = f οΌβ¨ (inverses-are-sections (Ο Y) ti f)β»ΒΉ β©
Ο Y n οΌβ¨ ap (Ο Y) e β©
(Ξ» _ β β) β
u : Β¬ X
u q = zero-is-not-one
(β οΌβ¨ refl β©
f (inl q) οΌβ¨ ap (Ξ» - β - (inl q)) Iβ β©
β β)
II : ¬ X + ¬¬ X
II = I n refl
\end{code}
As promised above, thin inhabitedness is stronger than nonemptiness in
general, because WEM is not provable or disprovable, as it is true in
some models and false in others, and this is the main observation in
this file so far.
\begin{code}
irrefutable-props-are-thinly-inhabited-gives-WEM
: ((P : π€ Μ ) β is-prop P β ¬¬ P β is-thinly-inhabited P)
β typal-WEM π€
irrefutable-props-are-thinly-inhabited-gives-WEM {π€} Ξ± = I
where
module _ (Q : π€ Μ ) (i : is-prop Q) where
P = Q + Β¬ Q
ν : ¬¬ P
Ξ½ Ο = Ο (inr (Ξ» q β Ο (inl q)))
h : is-thinly-inhabited P
h = Ξ± P (decidability-of-prop-is-prop fe i) Ξ½
I : typal-WEM π€
I = WEM-gives-typal-WEM fe (Ξ» Q i β thinly-inhabited-wem-lemma Q (h Q i))
\end{code}
Nathanael Rosnik proved the above independently within a few
hours of difference here:
https://gist.github.com/nrosnick/922250ddcc6bd04272199f59443d7510
A minor observation, giving another instance of an implication
is-thinly-inhabited P β P.
\begin{code}
thinly-inhabited-wem-special : (X : π€ Μ )
β is-thinly-inhabited (is-empty X + is-nonempty X)
β is-empty X + is-nonempty X
thinly-inhabited-wem-special X h =
Cases (thinly-inhabited-wem-lemma (Β¬ X) h)
inr
(inl β three-negations-imply-one)
\end{code}
Digression. A monad on propositions (or even a wild monad on all types?).
\begin{code}
module retraction-monad where
Ξ· : {X : π€ Μ } β X β has-retraction (Ο X)
Ξ· x = (Ξ» f β f x) , (Ξ» n β refl)
_β― : {X : π€ Μ } {Y : π₯ Μ }
β (X β has-retraction (Ο Y))
β (has-retraction (Ο X) β has-retraction (Ο Y))
_β― {π€} {π₯} {X} {Y} h (Ο , ΟΟ) = q
where
a : X β (Y β π) β π
a x = retraction-of (Ο Y) (h x)
b : (x : X) (n : π) β a x (Ο Y n) οΌ n
b x = retraction-equation (Ο Y) (h x)
u : (Y β π) β π
u g = Ο (Ξ» x β a x g)
v : u β Ο Y βΌ id
v n = (u β Ο Y) n οΌβ¨ refl β©
Ο (Ξ» x β a x (Ο Y n)) οΌβ¨ ap Ο (dfunext fe (Ξ» x β b x n)) β©
Ο (Ξ» _ β n) οΌβ¨ refl β©
Ο (Ο X n) οΌβ¨ ΟΟ n β©
n β
q : has-retraction (Ο Y)
q = u , v
functor : {X : π€ Μ } {Y : π₯ Μ }
β (X β Y)
β (has-retraction (Ο X) β has-retraction (Ο Y))
functor f = (Ξ· β f) β―
ΞΌ : (X : π€ Μ )
β has-retraction (Ο (has-retraction (Ο X)))
β has-retraction (Ο X)
ΞΌ X = id β―
\end{code}
TODO. It doesn't seem to be possible to give the structure of a monad
to is-thinly-inhabited.
Added 13th June 2024. The homotopy circle SΒΉ is thinly inhabited
because, as it is a connected 1-type, all functions SΒΉ β π are
constant as π is a set. As another example, the type β of Dedekind
reals is a set, but still there may be no function β β π other than
the constant functions, because "all functions β β π are continuous"
is a consistent axiom. But if a totally separated type (which is
necessarily a set) is thinly inhabited, then it must be a proposition.
Recall that x οΌβ y is defined to mean that p x = p y for all p : X β π,
that is, x and y satisfy the same boolean-valued properties. When
x οΌβ y holds for all x and y in X, we say that X is connectedβ. And
recall that, in another extreme, when x οΌβ y implies x οΌ y for all x
and y, we say that X is totally separated.
\begin{code}
open import TypeTopology.TotallySeparated
open import TypeTopology.DisconnectedTypes
thinly-inhabited-types-are-connectedβ : {X : π€ Μ }
β is-thinly-inhabited X
β is-connectedβ X
thinly-inhabited-types-are-connectedβ {π€} {X} ti x y = I
where
e : π β (X β π)
e = Ο X , ti
I : (p : X β π) β p x οΌ p y
I p = p x οΌβ¨ happly ((inverses-are-sections' e p)β»ΒΉ) x β©
β e β (β e ββ»ΒΉ p) x οΌβ¨ refl β©
β e ββ»ΒΉ p οΌβ¨ refl β©
β e β (β e ββ»ΒΉ p) y οΌβ¨ happly (inverses-are-sections' e p) y β©
p y β
totally-separated-thinly-inhabited-types-are-props : {X : π€ Μ }
β is-totally-separated X
β is-thinly-inhabited X
β is-prop X
totally-separated-thinly-inhabited-types-are-props ts ti x y = I
where
I : x οΌ y
I = ts (thinly-inhabited-types-are-connectedβ ti x y)
\end{code}
If replace the type π by the type Ξ© of propositions in the notion of
thin inhabitedness, then we can replace the assumption
"is-totally-separated X" by "is-set X" to get the same conclusion
(exercise). And if we replace π by some universe π€, no assumption is
needed to conclude that thinly inhabited types are propositions:
\begin{code}
module universe-discussion where
ΞΊ : (X : π€ Μ ) β π€ Μ β (X β π€ Μ )
ΞΊ X Y = Ξ» (_ : X) β Y
is-thinly-inhabited' : π€ Μ β π€ βΊ Μ
is-thinly-inhabited' X = is-equiv (ΞΊ X)
thinly-inhabited'-types-are-props : {X : π€ Μ }
β is-thinly-inhabited' X
β is-prop X
thinly-inhabited'-types-are-props {π€} {X} ti x y = III
where
e : π€ Μ β (X β π€ Μ )
e = ΞΊ X , ti
I : (p : X β π€ Μ ) β p x οΌ p y
I p = p x οΌβ¨ happly ((inverses-are-sections' e p)β»ΒΉ) x β©
β e β (β e ββ»ΒΉ p) x οΌβ¨ refl β©
β e ββ»ΒΉ p οΌβ¨ refl β©
β e β (β e ββ»ΒΉ p) y οΌβ¨ happly (inverses-are-sections' e p) y β©
p y β
II : (x οΌ x) οΌ (x οΌ y)
II = I (x οΌ_)
III : x οΌ y
III = idtofun' II refl
Ξ· : {X : π€ Μ } β is-prop X β X β is-thinly-inhabited' X
Ξ· {π€} {X} i xβ = qinvs-are-equivs (ΞΊ X) (s , sΞΊ , ΞΊs)
where
s : (X β π€ Μ ) β π€ Μ
s A = A xβ
sΞΊ : s β ΞΊ X βΌ id
sΞΊ Y = refl
ΞΊs : ΞΊ X β s βΌ id
ΞΊs A = dfunext fe (Ξ» x β ap A (i xβ x))
thinly-inhabited'-gives-nonempty : {X : π€ Μ }
β is-thinly-inhabited' X
β is-nonempty X
thinly-inhabited'-gives-nonempty {π€} {X} ti Ξ½ = III
where
e : π€ Μ β (X β π€ Μ )
e = ΞΊ X , ti
I : β e ββ»ΒΉ (β e β π) οΌ β e ββ»ΒΉ (β e β π)
I = ap (β e ββ»ΒΉ) (β e β π οΌβ¨ dfunext fe (Ξ» x β π-elim (Ξ½ x)) β©
β e β π β)
II = π οΌβ¨ (inverses-are-retractions' e π)β»ΒΉ β©
β e ββ»ΒΉ (β e β π) οΌβ¨ I β©
β e ββ»ΒΉ (β e β π) οΌβ¨ inverses-are-retractions' e π β©
π β
III : π {π€β}
III = π-elim (idtofun' II β)
\end{code}
We now come back to the original notion of thin inhabitedness studied
in this file.
TODO. Derive a constructive taboo from the hypothesis
(P : π€ Μ ) β is-prop P β is-thinly-inhabited P β P.
The difficulty, of course, is to come up with a type P which we can
prove to be thinly inhabited but (we can't prove to be pointed and)
whose pointedness would give a constructive taboo.