1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
(* Title: HoTT/Sum.thy
Author: Josh Chen
Dependent sum type.
*)
theory Sum
imports HoTT_Base Prod
begin
axiomatization
Sum :: "[Term, Term ⇒ Term] ⇒ Term" and
pair :: "[Term, Term] ⇒ Term" ("(1'(_,/ _'))") and
indSum :: "(Term ⇒ Term) ⇒ Term"
syntax
"_SUM" :: "[idt, Term, Term] ⇒ Term" ("(3∑_:_./ _)" 20)
"_SUM_ASCII" :: "[idt, Term, Term] ⇒ Term" ("(3SUM _:_./ _)" 20)
translations
"∑x:A. B" ⇌ "CONST Sum A (λx. B)"
"SUM x:A. B" ⇀ "CONST Sum A (λx. B)"
axiomatization where
Sum_form [intro]: "⋀A B. ⟦A : U; B: A → U⟧ ⟹ ∑x:A. B(x) : U"
and
Sum_intro [intro]: "⋀A B a b. ⟦a : A; b : B(a)⟧ ⟹ (a, b) : ∑x:A. B(x)"
and
Sum_elim [elim]: "⋀A B C f p.
⟦ C: ∑x:A. B(x) → U;
f : ∏x:A. ∏y:B(x). C((x,y));
p : ∑x:A. B(x) ⟧ ⟹ indSum(C)`f`p : C(p)"
and
Sum_comp [simp]: "⋀(C::Term ⇒ Term) (f::Term) (a::Term) (b::Term). indSum(C)`f`(a,b) ≡ f`a`b"
text "We choose to formulate the elimination rule by using the object-level function type and function application as much as possible.
Hence only the type family ‹C› is left as a meta-level argument to the inductor indSum."
― ‹Nondependent pair›
abbreviation Pair :: "[Term, Term] ⇒ Term" (infixr "×" 50)
where "A×B ≡ ∑_:A. B"
subsubsection ‹Projections›
consts
fst :: "[Term, 'a] ⇒ Term" ("(1fst[/_,/ _])")
snd :: "[Term, 'a] ⇒ Term" ("(1snd[/_,/ _])")
overloading
fst_dep ≡ fst
snd_dep ≡ snd
fst_nondep ≡ fst
snd_nondep ≡ snd
begin
definition fst_dep :: "[Term, Term ⇒ Term] ⇒ Term" where
"fst_dep A B ≡ indSum(λ_. A)`(❙λx:A. ❙λy:B(x). x)"
definition snd_dep :: "[Term, Term ⇒ Term] ⇒ Term" where
"snd_dep A B ≡ indSum(λ_. A)`(❙λx:A. ❙λy:B(x). y)"
definition fst_nondep :: "[Term, Term] ⇒ Term" where
"fst_nondep A B ≡ indSum(λ_. A)`(❙λx:A. ❙λy:B. x)"
definition snd_nondep :: "[Term, Term] ⇒ Term" where
"snd_nondep A B ≡ indSum(λ_. A)`(❙λx:A. ❙λy:B. y)"
end
text "Simplification rules for the projections:"
lemma fst_dep_comp: "⟦a : A; b : B(a)⟧ ⟹ fst[A,B]`(a,b) ≡ a" unfolding fst_dep_def by simp
lemma snd_dep_comp: "⟦a : A; b : B(a)⟧ ⟹ snd[A,B]`(a,b) ≡ b" unfolding snd_dep_def by simp
lemma fst_nondep_comp: "⟦a : A; b : B⟧ ⟹ fst[A,B]`(a,b) ≡ a" unfolding fst_nondep_def by simp
lemma snd_nondep_comp: "⟦a : A; b : B⟧ ⟹ snd[A,B]`(a,b) ≡ b" unfolding snd_nondep_def by simp
lemmas fst_snd_simps [simp] = fst_dep_comp snd_dep_comp fst_nondep_comp snd_nondep_comp
end
|
