Ian Ray, 23rd July 2024
Modifications made by Ian Ray on 26th September 2024.
Modifications made by Ian Ray on 17th December 2024.
We define connected types and maps. We then explore relationships, closure
properties and characterizations of interest pertaining to the concept of
connectedness.
\begin{code}
{-# OPTIONS --safe --without-K #-}
open import UF.FunExt
module UF.ConnectedTypes
(fe : Fun-Ext)
where
open import MLTT.Spartan hiding (_+_)
open import Notation.Order
open import UF.Base
open import UF.Equiv
open import UF.EquivalenceExamples
open import UF.PropTrunc
open import UF.Retracts
open import UF.Subsingletons
open import UF.Subsingletons-FunExt
open import UF.TruncatedTypes fe
open import UF.Truncations fe
open import UF.TruncationLevels
open import UF.Univalence
open import UF.Yoneda
\end{code}
We now define the notion of connectedness for types and functions with respect
to truncation levels.
\begin{code}
private
fe' : FunExt
fe' π€ π₯ = fe {π€} {π₯}
module connectedness-results (te : general-truncations-exist) where
private
pt : propositional-truncations-exist
pt = general-truncations-give-propositional-truncations te
open general-truncations-exist te
open propositional-truncations-exist pt
open import UF.ImageAndSurjection pt
_is_connected : π€ Μ β βββ β π€ Μ
X is k connected = is-contr (β₯ X β₯[ k ])
_is_connected-map : {X : π€ Μ } {Y : π₯ Μ } β (f : X β Y) β βββ β π€ β π₯ Μ
f is k connected-map = each-fiber-of f (Ξ» - β - is k connected)
being-connected-is-prop : {k : βββ} {X : π€ Μ }
β is-prop (X is k connected)
being-connected-is-prop = being-truncated-is-prop
being-connected-map-is-prop : {k : βββ} {X : π€ Μ } {Y : π₯ Μ } {f : X β Y}
β is-prop (f is k connected-map)
being-connected-map-is-prop = Ξ -is-prop fe (Ξ» y β being-connected-is-prop)
connected-if-contr : {X : π€ Μ } {k : βββ}
β is-contr X
β X is k connected
connected-if-contr {_} {X} {β2} X-is-contr = β2-trunc-is-contr
connected-if-contr {_} {X} {succ k} (c , C) = (β£ c β£[ k + 1 ] , C')
where
C'' : (x : X) β β£ c β£[ k + 1 ] οΌ β£ x β£[ k + 1 ]
C'' x = canonical-identity-trunc-map β£ C x β£[ k ]
C' : is-central β₯ X β₯[ k + 1 ] β£ c β£[ k + 1 ]
C' = β₯β₯β-ind (Ξ» v β Ξ» p q β truncation-levels-closed-under-Id
(β₯β₯β-is-truncated β£ c β£[ succ k ] v) p q) C''
\end{code}
TODO: show that connectedness as defined elsewhere in the library is
a special case of k-connectedness. Connectedness typically means set
connectedness, by our convention it will mean 0-connectedness.
We characterize β1-connected types as inhabited types and β1-connected maps as
surjections.
\begin{code}
β1-connected-types-are-inhabited : {X : π€ Μ }
β X is β1 connected β β₯ X β₯
β1-connected-types-are-inhabited X-1-conn =
β1-trunc-to-prop-trunc pt (center X-1-conn)
inhabited-types-are-β1-connected : {X : π€ Μ }
β β₯ X β₯ β X is β1 connected
inhabited-types-are-β1-connected x-anon =
pointed-props-are-singletons (prop-trunc-to-β1-trunc pt x-anon)
β1-trunc-is-prop
β1-connected-iff-inhabited : {X : π€ Μ }
β X is β1 connected β β₯ X β₯
β1-connected-iff-inhabited =
(β1-connected-types-are-inhabited , inhabited-types-are-β1-connected)
β1-connected-maps-are-surjections : {X : π€ Μ } {Y : π₯ Μ } {f : X β Y}
β f is β1 connected-map β is-surjection f
β1-connected-maps-are-surjections m y = β1-connected-types-are-inhabited (m y)
surjections-are-β1-connected : {X : π€ Μ } {Y : π₯ Μ } {f : X β Y}
β is-surjection f β f is β1 connected-map
surjections-are-β1-connected f-is-surj y =
inhabited-types-are-β1-connected (f-is-surj y)
β1-connected-map-iff-surjection : {X : π€ Μ } {Y : π₯ Μ } {f : X β Y}
β f is β1 connected-map β is-surjection f
β1-connected-map-iff-surjection =
(β1-connected-maps-are-surjections , surjections-are-β1-connected)
\end{code}
We develop some closure conditions pertaining to connectedness. Connectedness
is closed under retracts and equivalence as expected, but more importantly
connectedness extends below:
more precisely if a type is k connected then it is l connected for all l β€ k.
We provide a few incarnations of this fact below which may prove useful.
\begin{code}
retract-is-connected : {X : π€ Μ } {Y : π₯ Μ } {k : βββ}
β retract Y of X
β X is k connected
β Y is k connected
retract-is-connected R X-conn =
retract-of-singleton (truncation-closed-under-retract R) X-conn
connectedness-closed-under-equiv : {X : π€ Μ } {Y : π₯ Μ } {k : βββ}
β X β Y
β Y is k connected
β X is k connected
connectedness-closed-under-equiv e Y-con =
equiv-to-singleton (truncation-closed-under-equiv e) Y-con
contractible-types-are-connected : {X : π€ Μ } {k : βββ}
β is-contr X
β X is k connected
contractible-types-are-connected {π€} {X} {k} (c , C) = ((β£ c β£[ k ]) , C')
where
C' : (s : β₯ X β₯[ k ]) β (β£ c β£[ k ]) οΌ s
C' = β₯β₯β-ind (truncation-levels-closed-under-Id β₯β₯β-is-truncated (β£ c β£[ k ]))
(Ξ» x β ap β£_β£[ k ] (C x))
connectedness-is-lower-closed : {X : π€ Μ } {k : βββ}
β X is (k + 1) connected
β X is k connected
connectedness-is-lower-closed {π€} {X} {k} X-succ-con =
equiv-to-singleton successive-truncations-equiv
(contractible-types-are-connected X-succ-con)
connectedness-is-lower-closed-+ : {X : π€ Μ } {l : βββ} {k : β}
β X is (l + k) connected
β X is l connected
connectedness-is-lower-closed-+ {π€} {X} {l} {0} X-con = X-con
connectedness-is-lower-closed-+ {π€} {X} {l} {succ k} X-con =
connectedness-is-lower-closed-+ (connectedness-is-lower-closed X-con)
connectedness-is-lower-closed' : {X : π€ Μ } {k l : βββ}
β (l β€ k)
β X is k connected
β X is l connected
connectedness-is-lower-closed' {π€} {X} {k} {l} o X-con =
connectedness-is-lower-closed-+ (transport (Ξ» z β X is z connected) p X-con)
where
m : β
m = subtraction-βββ-term l k o
p = k οΌβ¨ subtraction-βββ-identification l k o β»ΒΉ β©
l + m β
map-connectedness-is-lower-closed : {X : π€ Μ } {Y : π₯ Μ } {f : X β Y} {k l : βββ}
β (l β€ k)
β f is k connected-map
β f is l connected-map
map-connectedness-is-lower-closed o f-k-con y =
connectedness-is-lower-closed' o (f-k-con y)
\end{code}
We characterize connected types in terms of inhabitedness and connectedness of
the identity type at one level below. We will assume univalence only when necessary.
\begin{code}
connected-types-are-inhabited : {X : π€ Μ } {k : βββ}
β X is (k + 1) connected β β₯ X β₯
connected-types-are-inhabited {_} {_} {k} X-conn =
β1-connected-types-are-inhabited (connectedness-is-lower-closed' β X-conn)
_is-locally_connected : (X : π€ Μ ) (k : βββ) β π€ Μ
X is-locally k connected = (x y : X) β (x οΌ y) is k connected
connected-types-are-locally-connected : {X : π€ Μ } {k : βββ}
β is-univalent π€
β X is (k + 1) connected
β X is-locally k connected
connected-types-are-locally-connected {_} {_} {k} ua X-conn x y =
equiv-to-singleton (eliminated-trunc-identity-char ua)
(is-prop-implies-is-prop' (singletons-are-props X-conn)
β£ x β£[ succ k ] β£ y β£[ succ k ])
connected-types-are-inhabited-and-locally-connected : {X : π€ Μ } {k : βββ}
β is-univalent π€
β X is (k + 1) connected
β β₯ X β₯
Γ X is-locally k connected
connected-types-are-inhabited-and-locally-connected ua X-conn =
(connected-types-are-inhabited X-conn , connected-types-are-locally-connected ua X-conn)
inhabited-and-locally-connected-types-are-connected : {X : π€ Μ } {k : βββ}
β is-univalent π€
β β₯ X β₯
β X is-locally k connected
β X is (k + 1) connected
inhabited-and-locally-connected-types-are-connected
{_} {_} {β2} ua anon-x id-conn =
pointed-props-are-singletons (prop-trunc-to-β1-trunc pt anon-x) β1-trunc-is-prop
inhabited-and-locally-connected-types-are-connected
{_} {_} {succ k} ua anon-x id-conn =
β₯β₯-rec (being-singleton-is-prop fe)
(Ξ» x β (β£ x β£[ (k + 1) + 1 ]
, β₯β₯β-ind (Ξ» v β truncation-levels-are-upper-closed
(Ξ» p q β β₯β₯β-is-truncated β£ x β£[ (k + 1) + 1 ] v p q))
(Ξ» y β forth-trunc-id-char ua (center (id-conn x y)))))
anon-x
connected-characterization : {X : π€ Μ } {k : βββ}
β is-univalent π€
β X is (k + 1) connected
β β₯ X β₯ Γ X is-locally k connected
connected-characterization ua =
(connected-types-are-inhabited-and-locally-connected ua
, uncurry (inhabited-and-locally-connected-types-are-connected ua))
ap-is-less-connected : {X : π€ Μ } {Y : π₯ Μ } {k : βββ}
β (ua : is-univalent (π€ β π₯))
β (f : X β Y)
β f is (k + 1) connected-map
β {x x' : X}
β (ap f {x} {x'}) is k connected-map
ap-is-less-connected ua f f-conn {x} {x'} p =
equiv-to-singleton (truncation-closed-under-equiv (fiber-of-ap-β f p))
(connected-types-are-locally-connected ua (f-conn (f x'))
(x , p) (x' , refl))
\end{code}
We prove a characterization of connectedness from the HoTT book
(see Corollary 7.5.9.). Notice we choose to directly prove this result
rather than instantiate it as a special case of a more general result
(Lemma 7.5.7.) which is stated below.
NOTE: We will NOT state the corollary as an iff statement due to a large
quantification issue.
\begin{code}
private
consts : (X : π€ Μ ) (Y : π₯ Μ )
β Y β (X β Y)
consts X Y y x = y
maps-with-connected-dom-truncated-cod-are-constant : {X : π€ Μ } {Y : π₯ Μ } {n : βββ}
β X is n connected
β Y is n truncated
β Y β (X β Y)
maps-with-connected-dom-truncated-cod-are-constant {π€} {_} {X} {Y} {n}
X-conn Y-trunc = e
where
e : Y β (X β Y)
e = Y ββ¨ πβ fe β©
(π {π€} β Y) ββ¨ βcong'' fe fe I β©
(β₯ X β₯[ n ] β Y) ββ¨ β₯β₯β-universal-property Y-trunc β©
(X β Y) β
where
I : π {π€} β β₯ X β₯[ n ]
I = singleton-β-π' X-conn
observation : consts X Y οΌ β e β
observation = refl
constants-map-from-truncated-type-is-equiv : {X : π€ Μ } {n : βββ}
β (Y : π₯ Μ )
β X is n connected
β Y is n truncated
β is-equiv (consts X Y)
constants-map-from-truncated-type-is-equiv Y X-conn Y-trunc =
ββ-is-equiv (maps-with-connected-dom-truncated-cod-are-constant X-conn Y-trunc)
connected-when-consts-is-equiv : {X : π€ Μ } {n : βββ}
β ({π₯ : Universe} (Y : π₯ Μ )
β Y is n truncated
β is-equiv (consts X Y))
β X is n connected
connected-when-consts-is-equiv {_} {X} {n} is-equiv-from-trunc = (c , G)
where
s : (X β β₯ X β₯[ n ]) β β₯ X β₯[ n ]
s = section-map (consts X β₯ X β₯[ n ])
(equivs-have-sections (consts X β₯ X β₯[ n ])
(is-equiv-from-trunc β₯ X β₯[ n ] β₯β₯β-is-truncated))
H : (consts X β₯ X β₯[ n ]) β s βΌ id
H = section-equation (consts X β₯ X β₯[ n ])
(equivs-have-sections (consts X β₯ X β₯[ n ])
(is-equiv-from-trunc β₯ X β₯[ n ] β₯β₯β-is-truncated))
c : β₯ X β₯[ n ]
c = s β£_β£[ n ]
H' : (consts X β₯ X β₯[ n ]) c οΌ β£_β£[ n ]
H' = H β£_β£[ n ]
G : (v : β₯ X β₯[ n ]) β c οΌ v
G = β₯β₯β-ind (Ξ» - β truncation-levels-are-upper-closed β₯β₯β-is-truncated c -)
(Ξ» x β happly H' x)
\end{code}
We will now prove a general result from the HoTT book that characterizes when
a map is connected (see Lemma 7.5.7.)
\begin{code}
dependent-equiv-from-truncated-fam-connected-map
: {X : π€ Μ } {Y : π₯ Μ } {n : βββ}
β (f : X β Y)
β (P : Y β π¦ Μ )
β ((y : Y) β (P y) is n truncated)
β f is n connected-map
β ((y : Y) β P y) β ((x : X) β P (f x))
dependent-equiv-from-truncated-fam-connected-map
{_} {_} {_} {X} {Y} {n} f P
P-trunc f-conn = e
where
e : ((y : Y) β P y) β ((x : X) β P (f x))
e = ((y : Y) β P y) ββ¨ I β©
((y : Y) β (fiber f y β P y)) ββ¨ II β©
((y : Y) β (x : X) β (p : f x οΌ y) β P y) ββ¨ Ξ -flip' β©
((x : X) β (y : Y) β (p : f x οΌ y) β P y) ββ¨ III β©
((x : X) β P (f x)) β
where
I = Ξ -cong fe fe (Ξ» - β maps-with-connected-dom-truncated-cod-are-constant
(f-conn -) (P-trunc -))
II = Ξ -cong fe fe (Ξ» - β curry-uncurry' fe fe)
III = Ξ -cong fe fe (Ξ» - β β-sym (Yoneda-equivalence fe' (f -) P))
observation : β e β οΌ dprecomp P f
observation = refl
dep-precomp-from-truncated-family-is-equiv
: {X : π€ Μ } {Y : π₯ Μ } {n : βββ}
β (f : X β Y)
β (P : Y β π¦ Μ )
β ((y : Y) β (P y) is n truncated)
β f is n connected-map
β is-equiv (dprecomp P f)
dep-precomp-from-truncated-family-is-equiv f P P-trunc f-conn =
ββ-is-equiv (dependent-equiv-from-truncated-fam-connected-map f P P-trunc f-conn)
dep-precomp-has-section-if-is-equiv
: {X : π€ Μ } {Y : π₯ Μ }
β (f : X β Y)
β (P : Y β π¦ Μ )
β is-equiv (dprecomp P f)
β has-section (dprecomp P f)
dep-precomp-has-section-if-is-equiv f P = equivs-have-sections (dprecomp P f)
map-is-connected-if-dep-precomp-from-truncated-family-has-section
: {X : π€ Μ } {Y : π₯ Μ } {n : βββ}
β (f : X β Y)
β ({π¦ : Universe} (P : Y β π¦ Μ ) β ((y : Y) β (P y) is n truncated)
β has-section (dprecomp P f))
β f is n connected-map
map-is-connected-if-dep-precomp-from-truncated-family-has-section
{π€} {π₯} {X} {Y} {n} f sec-from-trunc y = (c y , C)
where
Q : Y β π€ β π₯ Μ
Q y = β₯ fiber f y β₯[ n ]
c' : ((x : X) β β₯ fiber f (f x) β₯[ n ])
β ((y : Y) β β₯ fiber f y β₯[ n ])
c' = section-map (dprecomp Q f) (sec-from-trunc Q (Ξ» - β β₯β₯β-is-truncated))
c : (y : Y) β β₯ fiber f y β₯[ n ]
c = c' (Ξ» - β β£ (- , refl) β£[ n ])
H' : (dprecomp Q f) β c' βΌ id
H' = section-equation (dprecomp Q f)
(sec-from-trunc Q (Ξ» - β β₯β₯β-is-truncated))
H : (x : X) β c (f x) οΌ β£ (x , refl) β£[ n ]
H = happly' ((dprecomp Q f β c') (Ξ» - β β£ (- , refl) β£[ n ]))
(Ξ» - β β£ (- , refl) β£[ n ]) (H' (Ξ» - β β£ (- , refl) β£[ n ]))
C : (w : β₯ fiber f y β₯[ n ]) β c y οΌ w
C = β₯β₯β-ind (Ξ» - β truncation-levels-are-upper-closed β₯β₯β-is-truncated
(c y) -)
C'
where
C' : ((x , p) : fiber f y) β c y οΌ β£ (x , p) β£[ n ]
C' (x , refl) = H x
\end{code}
We show that the n-truncation map is n-connected.
\begin{code}
trunc-map-is-connected : {X : π€ Μ } {n : βββ}
β β£_β£[ n ] is n connected-map
trunc-map-is-connected {_} {X} {n} =
map-is-connected-if-dep-precomp-from-truncated-family-has-section
β£_β£[ n ] has-sec
where
has-sec : {π¦ : Universe}
β (P : β₯ X β₯[ n ] β π¦ Μ )
β ((v : β₯ X β₯[ n ]) β P v is n truncated)
β has-section (dprecomp P β£_β£[ n ])
has-sec {_} P P-trunc = (β₯β₯β-ind P-trunc , comp-rule)
where
comp-rule : dprecomp P β£_β£[ n ] β β₯β₯β-ind P-trunc βΌ id
comp-rule h = (dprecomp P β£_β£[ n ]) (β₯β₯β-ind P-trunc h) οΌβ¨reflβ©
(β₯β₯β-ind P-trunc h) β β£_β£[ n ] οΌβ¨ I β©
h β
where
I = dfunext fe (β₯β₯β-ind-comp P-trunc h)
\end{code}
We provide a useful result about maps from the constant type to a connected
type (see Lemma 7.5.11 of the HoTT book for the full statement). Observe we
do assume univalence locally here (the HoTT book assumes it implicitly).
\begin{code}
basepoint-map-is-less-connected : {X : π€ Μ } {n : βββ}
β is-univalent π€
β (xβ : π {π€} β X)
β X is (n + 1) connected
β xβ is n connected-map
basepoint-map-is-less-connected {_} {X} {n} ua xβ X-con x =
connectedness-closed-under-equiv π-lneutral
(connected-types-are-locally-connected ua X-con (xβ β) x)
\end{code}