1 include "sets/sets.ma".
3 nrecord Ax : Type[1] ≝ {
4 S:> setoid; (* Type[0]; *)
9 notation "𝐈 \sub( ❨a❩ )" non associative with precedence 70 for @{ 'I $a }.
10 notation "𝐂 \sub ( ❨a,\emsp i❩ )" non associative with precedence 70 for @{ 'C $a $i }.
12 notation > "𝐈 term 90 a" non associative with precedence 70 for @{ 'I $a }.
13 notation > "𝐂 term 90 a term 90 i" non associative with precedence 70 for @{ 'C $a $i }.
15 interpretation "I" 'I a = (I ? a).
16 interpretation "C" 'C a i = (C ? a i).
18 ndefinition cover_set ≝ λc:∀A:Ax.Ω^A → A → CProp[0].λA,C,U.
22 notation "hvbox(a break ◃ b)" non associative with precedence 45
23 for @{ 'covers $a $b }.
25 interpretation "covers set temp" 'covers C U = (cover_set ?? C U).
27 ninductive cover (A : Ax) (U : Ω^A) : A → CProp[0] ≝
28 | creflexivity : ∀a:A. a ∈ U → cover ? U a
29 | cinfinity : ∀a:A.∀i:𝐈 a. 𝐂 a i ◃ U → cover ? U a.
33 interpretation "covers" 'covers a U = (cover ? U a).
34 interpretation "covers set" 'covers a U = (cover_set cover ? a U).
36 ndefinition fish_set ≝ λf:∀A:Ax.Ω^A → A → CProp[0].
41 notation "hvbox(a break ⋉ b)" non associative with precedence 45
44 interpretation "fish set temp" 'fish A U = (fish_set ?? U A).
46 ncoinductive fish (A : Ax) (F : Ω^A) : A → CProp[0] ≝
47 | cfish : ∀a. a ∈ F → (∀i:𝐈 a .𝐂 a i ⋉ F) → fish A F a.
51 interpretation "fish set" 'fish A U = (fish_set fish ? U A).
52 interpretation "fish" 'fish a U = (fish ? U a).
54 nlet corec fish_rec (A:Ax) (U: Ω^A)
56 (H2: ∀a:A. a ∈ P → ∀j: 𝐈 a. 𝐂 a j ≬ P):
57 ∀a:A. ∀p: a ∈ P. a ⋉ U ≝ ?.
59 ##[ napply H1; napply p;
60 ##| #i; ncases (H2 a p i); #x; *; #xC; #xP; @; ##[napply x]
61 @; ##[ napply xC ] napply (fish_rec ? U P); nassumption;
65 notation "◃U" non associative with precedence 55
66 for @{ 'coverage $U }.
68 ndefinition coverage : ∀A:Ax.∀U:Ω^A.Ω^A ≝ λA,U.{ a | a ◃ U }.
70 interpretation "coverage cover" 'coverage U = (coverage ? U).
72 ndefinition cover_equation : ∀A:Ax.∀U,X:Ω^A.CProp[0] ≝ λA,U,X.
73 ∀a.a ∈ X ↔ (a ∈ U ∨ ∃i:𝐈 a.∀y.y ∈ 𝐂 a i → y ∈ X).
75 ntheorem coverage_cover_equation : ∀A,U. cover_equation A U (◃U).
77 ##[ nelim H; #b; (* manca clear *)
78 ##[ #bU; @1; nassumption;
79 ##| #i; #CaiU; #IH; @2; @ i; #c; #cCbi; ncases (IH ? cCbi);
81 ##| #_; napply CaiU; nassumption; ##] ##]
82 ##| ncases H; ##[ #E; @; nassumption]
83 *; #j; #Hj; @2 j; #w; #wC; napply Hj; nassumption;
87 ntheorem coverage_min_cover_equation :
88 ∀A,U,W. cover_equation A U W → ◃U ⊆ W.
89 #A; #U; #W; #H; #a; #aU; nelim aU; #b;
90 ##[ #bU; ncases (H b); #_; #H1; napply H1; @1; nassumption;
91 ##| #i; #CbiU; #IH; ncases (H b); #_; #H1; napply H1; @2; @i; napply IH;
95 notation "⋉F" non associative with precedence 55
98 ndefinition fished : ∀A:Ax.∀F:Ω^A.Ω^A ≝ λA,F.{ a | a ⋉ F }.
100 interpretation "fished fish" 'fished F = (fished ? F).
102 ndefinition fish_equation : ∀A:Ax.∀F,X:Ω^A.CProp[0] ≝ λA,F,X.
103 ∀a. a ∈ X ↔ a ∈ F ∧ ∀i:𝐈 a.∃y.y ∈ 𝐂 a i ∧ y ∈ X.
105 ntheorem fised_fish_equation : ∀A,F. fish_equation A F (⋉F).
106 #A; #F; #a; @; (* bug, fare case sotto diverso da farlo sopra *) #H; ncases H;
107 ##[ #b; #bF; #H2; @ bF; #i; ncases (H2 i); #c; *; #cC; #cF; @c; @ cC;
109 ##| #aF; #H1; @ aF; napply H1;
113 ntheorem fised_max_fish_equation : ∀A,F,G. fish_equation A F G → G ⊆ ⋉F.
114 #A; #F; #G; #H; #a; #aG; napply (fish_rec … aG);
115 #b; ncases (H b); #H1; #_; #bG; ncases (H1 bG); #E1; #E2; nassumption;
118 nrecord nAx : Type[2] ≝ {
119 nS:> setoid; (*Type[0];*)
121 nD: ∀a:nS. nI a → Type[0];
122 nd: ∀a:nS. ∀i:nI a. nD a i → nS
125 notation "𝐃 \sub ( ❨a,\emsp i❩ )" non associative with precedence 70 for @{ 'D $a $i }.
126 notation "𝐝 \sub ( ❨a,\emsp i,\emsp j❩ )" non associative with precedence 70 for @{ 'd $a $i $j}.
128 notation > "𝐃 term 90 a term 90 i" non associative with precedence 70 for @{ 'D $a $i }.
129 notation > "𝐝 term 90 a term 90 i term 90 j" non associative with precedence 70 for @{ 'd $a $i $j}.
131 interpretation "D" 'D a i = (nD ? a i).
132 interpretation "d" 'd a i j = (nd ? a i j).
134 ndefinition image ≝ λA:nAx.λa:A.λi. { x | ∃j:𝐃 a i. x = 𝐝 a i j }.
136 notation > "𝐈𝐦 [𝐝 term 90 a term 90 i]" non associative with precedence 70 for @{ 'Im $a $i }.
137 notation "𝐈𝐦 [𝐝 \sub ( ❨a,\emsp i❩ )]" non associative with precedence 70 for @{ 'Im $a $i }.
139 interpretation "image" 'Im a i = (image ? a i).
141 ndefinition Ax_of_nAx : nAx → Ax.
142 #A; @ A (nI ?); #a; #i; napply (𝐈𝐦 [𝐝 a i]);
145 ninductive sigma (A : Type[0]) (P : A → CProp[0]) : Type[0] ≝
146 sig_intro : ∀x:A.P x → sigma A P.
148 interpretation "sigma" 'sigma \eta.p = (sigma ? p).
150 ndefinition nAx_of_Ax : Ax → nAx.
152 ##[ #a; #i; napply (Σx:A.x ∈ 𝐂 a i);
153 ##| #a; #i; *; #x; #_; napply x;
157 ninductive ord (A : nAx) : Type[0] ≝
160 | oL : ∀a:A.∀i.∀f:𝐃 a i → ord A. ord A.
162 nlet rec famU (A : nAx) (U : Ω^A) (x : ord A) on x : Ω^A ≝
165 | oS y ⇒ let Un ≝ famU A U y in Un ∪ { x | ∃i.∀j:𝐃 x i.𝐝 x i j ∈ Un}
166 | oL a i f ⇒ { x | ∃j.x ∈ famU A U (f j) } ].
168 ndefinition ord_coverage ≝ λA,U.{ y | ∃x:ord A. y ∈ famU ? U x }.