Built with Alectryon, running Coq+SerAPI v8.19.0+0.19.3. Bubbles () indicate interactive fragments: hover for details, tap to reveal contents. Use Ctrl+↑Ctrl+↓ to navigate, Ctrl+🖱️ to focus. On Mac, use ⌘ instead of Ctrl.
[Loading ML file number_string_notation_plugin.cmxs (using legacy method) ... done]
Require Import Extensions Limits.Pullback.Require Import Modality Lex Open Closed Nullification.LocalOpen Scope path_scope.(** * The lex-modal fracture theorem *)(** The fracture theorem for two modalities [O1] and [O2] and a type [A], when it holds, states that the naturality square<< A --> O1 A | | | | V VO2 A --> O2 (O1 A)>>is a pullback. This says in a certain precise sense that [A] can be recovered from its [O1]- and [O2]-reflections together with some information about how they fit together. If we think of [O1] and [O2] as subuniverses or subtoposes, then the fracture theorem says that their "union", or more precisely their *gluing*, is the whole universe.We will prove the fracture theorem holds under the assumptions that [O2] is lex, and that [O1]-connected types are [O2]-modal. Note that like lex-ness, the latter is also a "large" hypothesis. But also as with lex-ness, rather than hypothesize it polymorphically with a module type, we just hypothesize it in the obvious way and allow the polymorphism of the resulting theorem to be computed automatically. This actually gives more precise information: the fracture theorem for a particular type [A] only depends on this hypothesis for types [B] lying in the same universe as [A]. (In fact, as we will see, it only needs the special cases of the fibers of [to O1 A], but in examples it seems no harder to verify the general case.)It may sometimes happen that in addition, the "intersection" of [O1] and [O2] is trivial. This is naturally expressed in the context of the fracture theorem by saying that [O2]-modal types are [O1]-connected, i.e. the converse of the second hypothesis of our fracture theorem. When this also holds, we can show that the universe [Type] can actually be reconstructed, up to equivalence, from the universes of [O1]- and [O2]-modal types and the [O2]-reflection from the first to the second, using the "Artin gluing construction" from topos theory. *)(** ** The fracture theorem *)SectionFractureTheorem.Context (O1O2 : Modality).Definitionfracture_square (A : Type)
: O_functor O2 (to O1 A) o to O2 A == to O2 (O1 A) o to O1 A
:= to_O_natural O2 (to O1 A).(** Here are the hypotheses of the fracture theorem *)Context `{Lex O2}.DefinitionGluable : Type
:= forall (A : Type), IsConnected O1 A -> In O2 A.Context (ino2_isconnectedo1 : Gluable).(** The fracture theorem. *)
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable A: Type
IsPullback (fracture_square A)
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable A: Type
IsPullback (fracture_square A)
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable A: Type
IsPullback (funa : A => (fracture_square A a)^)
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable A: Type
Lex O2
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable A: Type
O_inverts O2 (to O2 A)
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable A: Type
O_inverts O2 (to O2 (O_reflector O1 A))
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable A: Type
MapIn O2 (to O1 A)
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable A: Type
MapIn O2 (O_functor O2 (to O1 A))
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable A: Type
MapIn O2 (to O1 A)
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable A: Type
MapIn O2 (O_functor O2 (to O1 A))
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable A: Type
MapIn O2 (to O1 A)
intros x; exact (ino2_isconnectedo1 _ _).Defined.(** ** The fracture gluing theorem *)(** We now also assume the converse of the second hypothesis *)DefinitionDisjoint : Type
:= forall (A : Type), In O2 A -> IsConnected O1 A.Context (isconnectedo1_ino2 : Disjoint).(** This implies that the universe decomposes into an [O1]-part, an [O2]-part, and a gluing map. We define these pieces separately in order to make the maps transparent but the homotopies opaque. *)Definitionfracture_glue_uncurried
: { B : Type_ O1 & { C : Type_ O2 & C -> O2 B }} -> Type
:= funBCf => Pullback BCf.2.2 (to O2 BCf.1).Definitionfracture_glue
(BC : Type) `{HB: In O1 B} `{HC: In O2 C} (f : C -> O2 B)
: Type
:= fracture_glue_uncurried ((B;HB);((C;HC);f)).Definitionfracture_unglue
: Type -> { B : Type_ O1 & { C : Type_ O2 & C -> O2 B }}
:= funA => ((O1 A ; O_inO A) ; ((O2 A ; O_inO A) ; O_functor O2 (to O1 A))).
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable isconnectedo1_ino2: Disjoint H: Univalence B: Type_ O1 C: Type_ O2 f: C -> O2 B X: IsEquiv (O_rec ((to O2 B) ^*' f)) X0: IsEquiv (O_rec (f^* (to O2 B))) c: C
transport O2
(ap (TypeO_pr1 O1)
(path_TypeO O1
(O1 (fracture_glue_uncurried (B; C; f));
O_inO (fracture_glue_uncurried (B; C; f))) B
(path_universe (O_rec ((to O2 B) ^*' f)))))
(O_functor O2
(to O1 (fracture_glue_uncurried (B; C; f)))
(transport (TypeO_pr1 O2)
(path_TypeO O2
(O2 (fracture_glue_uncurried (B; C; f));
O_inO (fracture_glue_uncurried (B; C; f)))
C (path_universe (O_rec (f^* (to O2 B)))))^
c)) = f c
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable isconnectedo1_ino2: Disjoint H: Univalence B: Type_ O1 C: Type_ O2 f: C -> O2 B X: IsEquiv (O_rec ((to O2 B) ^*' f)) X0: IsEquiv (O_rec (f^* (to O2 B))) c: C
transport idmap
(ap O2
(ap (TypeO_pr1 O1)
(path_TypeO O1
(O1 (fracture_glue_uncurried (B; C; f));
O_inO (fracture_glue_uncurried (B; C; f)))
B (path_universe (O_rec ((to O2 B) ^*' f))))))
(O_functor O2
(to O1 (fracture_glue_uncurried (B; C; f)))
(transport (TypeO_pr1 O2)
(path_TypeO O2
(O2 (fracture_glue_uncurried (B; C; f));
O_inO (fracture_glue_uncurried (B; C; f)))
C (path_universe (O_rec (f^* (to O2 B)))))^
c)) = f c
(** Now we have to compute through the action of [ap] and [transport] on paths in sigmas and the universe. In applying these it helps to specify a couple of intermediate steps explicitly. *)
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable isconnectedo1_ino2: Disjoint H: Univalence B: Type_ O1 C: Type_ O2 f: C -> O2 B X: IsEquiv (O_rec ((to O2 B) ^*' f)) X0: IsEquiv (O_rec (f^* (to O2 B))) c: C
ap (TypeO_pr1 O1)
(path_TypeO O1
(O1 (fracture_glue_uncurried (B; C; f));
O_inO (fracture_glue_uncurried (B; C; f))) B
(path_universe (O_rec ((to O2 B) ^*' f)))) =
path_universe (O_rec ((to O2 B) ^*' f))
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable isconnectedo1_ino2: Disjoint H: Univalence B: Type_ O1 C: Type_ O2 f: C -> O2 B X: IsEquiv (O_rec ((to O2 B) ^*' f)) X0: IsEquiv (O_rec (f^* (to O2 B))) c: C
transport (TypeO_pr1 O2)
(path_TypeO O2
(O2 (fracture_glue_uncurried (B; C; f));
O_inO (fracture_glue_uncurried (B; C; f))) C
(path_universe (O_rec (f^* (to O2 B)))))^ c =
(O_rec (f^* (to O2 B)))^-1 c
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable isconnectedo1_ino2: Disjoint H: Univalence B: Type_ O1 C: Type_ O2 f: C -> O2 B X: IsEquiv (O_rec ((to O2 B) ^*' f)) X0: IsEquiv (O_rec (f^* (to O2 B))) c: C
transport idmap
(ap O2 (path_universe (O_rec ((to O2 B) ^*' f))))
(O_functor O2 (to O1 (Pullback f (to O2 B)))
((O_rec (f^* (to O2 B)))^-1 c)) =
O_functor O2 (O_rec ((to O2 B) ^*' f))
(O_functor O2 (to O1 (Pullback f (to O2 B)))
((O_rec (f^* (to O2 B)))^-1 c))
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable isconnectedo1_ino2: Disjoint H: Univalence B: Type_ O1 C: Type_ O2 f: C -> O2 B X: IsEquiv (O_rec ((to O2 B) ^*' f)) X0: IsEquiv (O_rec (f^* (to O2 B))) c: C
O_functor O2 (O_rec ((to O2 B) ^*' f))
(O_functor O2 (to O1 (Pullback f (to O2 B)))
((O_rec (f^* (to O2 B)))^-1 c)) =
f c
O1, O2: Modality Lex0: Lex O2 ino2_isconnectedo1: Gluable isconnectedo1_ino2: Disjoint H: Univalence B: Type_ O1 C: Type_ O2 f: C -> O2 B X: IsEquiv (O_rec ((to O2 B) ^*' f)) X0: IsEquiv (O_rec (f^* (to O2 B))) c: C
ap (TypeO_pr1 O1)
(path_TypeO O1
(O1 (fracture_glue_uncurried (B; C; f));
O_inO (fracture_glue_uncurried (B; C; f))) B
(path_universe (O_rec ((to O2 B) ^*' f)))) =
path_universe (O_rec ((to O2 B) ^*' f))
exact (Build_Equiv _ _ (pullback_corec (fracture_square A))
(ispullback_fracture_square A)).Qed.Definitionisequiv_fracture_unglue `{Univalence}
: IsEquiv fracture_unglue
:= isequiv_adjointify
fracture_unglue
fracture_glue_uncurried
fracture_unglue_isretr
fracture_unglue_issect.Definitionequiv_fracture_unglue `{Univalence}
: Type <~> { B : Type_ O1 & { C : Type_ O2 & C -> O2 B }}
:= Build_Equiv _ _ fracture_unglue isequiv_fracture_unglue.EndFractureTheorem.(** ** The propositional fracture theorem *)(** An easy example of the lex-modal fracture theorem is supplied by the open and closed modalities for an hprop [U]. *)
H: Funext U: HProp
Gluable (Op U) (Cl U)
H: Funext U: HProp
Gluable (Op U) (Cl U)
H: Funext U: HProp A: Type
IsConnected (Op U) A -> In (Cl U) A
H: Funext U: HProp A: Type X: Contr (U -> A) u: U
Contr A
H: Funext U: HProp A: Type X: Contr (U -> A) u: U a: A
forally : U -> A,
(funu : U => leti := uc u in center A) = y
H: Funext U: HProp A: Type uc: U -> Contr A f: U -> A u: U
(leti := uc u in center A) = f u
pose (uc u); apply path_contr.Defined.(** We can also prove the same thing without funext if we use the nullification versions of these modalities. *)
U: HProp
Gluable (Op' U) (Cl' U)
U: HProp
Gluable (Op' U) (Cl' U)
U: HProp A: Type X: IsConnected (Op' U) A u: U
ooExtendableAlong (fun_ : Empty => tt) (unit_name A)
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U
ooExtendableAlong (fun_ : Empty => tt) (unit_name A)
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U
Contr A
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U X1: Contr A
ooExtendableAlong (fun_ : Empty => tt) (unit_name A)
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U
Contr A
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U
Op' U A -> A
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U
IsEquiv ?f
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U
Op' U A -> A
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U
In (Op' U) A
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U
ooExtendableAlong (fun_ : U => tt) (unit_name A)
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U
IsEquiv (fun_ : U => tt)
exact (equiv_isequiv (@equiv_contr_contr U Unit _ _)).
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U
IsEquiv (O_rec idmap)
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U
(funx : A => O_rec idmap (to (Op' U) A x)) == idmap
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U
(funx : O_reflector (Op' U) A =>
to (Op' U) A (O_rec idmap x)) == idmap
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U
(funx : A => O_rec idmap (to (Op' U) A x)) == idmap
intros a; apply O_rec_beta.
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U
(funx : O_reflector (Op' U) A =>
to (Op' U) A (O_rec idmap x)) == idmap
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U
(funx : A => loc x) == (funx : A => loc x)
reflexivity.
U: HProp A: Type X: IsConnected (Op' U) A u: U X0: Contr U X1: Contr A
ooExtendableAlong (fun_ : Empty => tt) (unit_name A)
apply ooextendable_contr; exact _.Defined.
U: HProp
Disjoint (Op' U) (Cl' U)
U: HProp
Disjoint (Op' U) (Cl' U)
U: HProp A: Type An: In (Cl' U) A
IsConnected (Op' U) A
U: HProp A: Type An: In (Cl' U) A C: Type Cn: In (Op' U) C f: A -> C
NullHomotopy.NullHomotopy f
U: HProp A: Type An: In (Cl' U) A C: Type Cn: In (Op' U) C f: A -> C
U -> C
U: HProp A: Type An: In (Cl' U) A C: Type Cn: In (Op' U) C f: A -> C
forallx : A,
f x =
local_rec
(Accessible.null_to_local_generators
{|
Accessible.ngen_indices := Unit;
Accessible.ngen_type := unit_name U
|}) ?Goal tt
U: HProp A: Type An: In (Cl' U) A C: Type Cn: In (Op' U) C f: A -> C
U -> C
U: HProp A: Type An: In (Cl' U) A C: Type Cn: In (Op' U) C f: A -> C u: U
C
exact (f (@local_rec _ A An u Empty_rec tt)).
U: HProp A: Type An: In (Cl' U) A C: Type Cn: In (Op' U) C f: A -> C
forallx : A,
f x =
local_rec
(Accessible.null_to_local_generators
{|
Accessible.ngen_indices := Unit;
Accessible.ngen_type := unit_name U
|})
(funu : U =>
f
(local_rec
(Accessible.null_to_local_generators
{|
Accessible.ngen_indices := U;
Accessible.ngen_type :=
fun_ : U => Empty
|}) Empty_rec tt)) tt
U: HProp A: Type An: In (Cl' U) A C: Type Cn: In (Op' U) C f: A -> C a: A
f a =
local_rec
(Accessible.null_to_local_generators
{|
Accessible.ngen_indices := Unit;
Accessible.ngen_type := unit_name U
|})
(funu : U =>
f
(local_rec
(Accessible.null_to_local_generators
{|
Accessible.ngen_indices := U;
Accessible.ngen_type :=
fun_ : U => Empty
|}) Empty_rec tt)) tt
U: HProp A: Type An: Accessible.IsLocal_Internal.IsLocal
(Accessible.null_to_local_generators
{|
Accessible.ngen_indices := U;
Accessible.ngen_type := fun_ : U => Empty
|}) A C: Type Cn: Accessible.IsLocal_Internal.IsLocal
(Accessible.null_to_local_generators
{|
Accessible.ngen_indices := Unit;
Accessible.ngen_type := unit_name U
|}) C f: A -> C a: A u: U
f a =
local_rec
(Accessible.null_to_local_generators
{|
Accessible.ngen_indices := Unit;
Accessible.ngen_type := unit_name U
|})
(funu : U =>
f
(local_rec
(Accessible.null_to_local_generators
{|
Accessible.ngen_indices := U;
Accessible.ngen_type :=
fun_ : U => Empty
|}) Empty_rec tt)) tt
U: HProp A: Type An: Accessible.IsLocal_Internal.IsLocal
(Accessible.null_to_local_generators
{|
Accessible.ngen_indices := U;
Accessible.ngen_type := fun_ : U => Empty
|}) A C: Type Cn: Accessible.IsLocal_Internal.IsLocal
(Accessible.null_to_local_generators
{|
Accessible.ngen_indices := Unit;
Accessible.ngen_type := unit_name U
|}) C f: A -> C a: A u: U
f a =
f
(local_rec
(Accessible.null_to_local_generators
{|
Accessible.ngen_indices := U;
Accessible.ngen_type := fun_ : U => Empty
|}) Empty_rec tt)
U: HProp A: Type An: Accessible.IsLocal_Internal.IsLocal
(Accessible.null_to_local_generators
{|
Accessible.ngen_indices := U;
Accessible.ngen_type := fun_ : U => Empty
|}) A C: Type Cn: Accessible.IsLocal_Internal.IsLocal
(Accessible.null_to_local_generators
{|
Accessible.ngen_indices := Unit;
Accessible.ngen_type := unit_name U
|}) C f: A -> C a: A u: U
a =
local_rec
(Accessible.null_to_local_generators
{|
Accessible.ngen_indices := U;
Accessible.ngen_type := fun_ : U => Empty
|}) Empty_rec tt
exact (@local_indpaths _ A An u (fun_ => a) _ (Empty_ind _) tt).Defined.