by S.Berardi and S. Valentini. The tutorial is by Enrico Tassi.
+The tutorial spends a considerable amount of effort in defining
+notations that resemble the ones used in the original paper. We believe
+this a important part of every formalization, not only for the estetic
+point of view, but also from the practical point of view. Being
+consistent allows to follow the paper in a pedantic way.
+
Orientering
-----------
- A ∪ B `A \cup B`
- A ∩ B `A \cap B`
+- A ≬ B `A \between B`
- x ∈ A `x \in A`
- Ω^A, that is the type of the subsets of A, `\Omega ^ A`
The first (technical) definition
--------------------------------
+Before defining the cover relation as an inductive predicate, one
+has to notice that the infinity rule uses, in its hypotheses, the
+cover relation between two subsets, while the inductive predicate
+we are going to define relates an element and a subset.
+
+An option would be to unfold the definition of cover between subsets,
+but we prefer to define the abstract notion of cover between subsets
+(so that we can attach a (ambiguous) notation to it).
+
+Anyway, to ease the understaing of the definition of the cover relation
+between subsets, we first define the inductive predicate unfolding the
+definition, and we later refine it with.
+
+DOCEND*)
+
+ninductive xcover (A : Ax) (U : Ω^A) : A → CProp[0] ≝
+| xcreflexivity : ∀a:A. a ∈ U → xcover A U a
+| xcinfinity : ∀a:A.∀i:𝐈 a. (∀y.y ∈ 𝐂 a i → xcover A U y) → xcover A U a.
+
+(*DOCBEGIN
+
+We defined the xcover (x will be removed in the final version of the
+definition) as an inductive predicate. The arity of the inductive
+predicate has to be carefully analyzed:
+
+> (A : Ax) (U : Ω^A) : A → CProp[0]
+The syntax separates with `:` abstractions that are fixed for every
+constructor (introduction rule) and abstractions that can change. In that
+case the parameter `U` is abstracted once and forall in front of every
+constructor, and every occurrence of the inductive predicate is applied to
+`U` in a consistent way. Arguments abstracted on the right of `:` are not
+constant, for example the xcinfinity constructor introduces `a ◃ U`,
+but under the assumption that (for every y) `y ◃ U`. In that rule, the left
+had side of the predicate changes, thus it has to be abstrated (in the arity
+of the inductive predicate) on the right of `:`.
+
+DOCEND*)
+
+(* ncheck xcreflexivity. *)
+
+(*DOCBEGIN
+
+We want now to abstract out `(∀y.y ∈ 𝐂 a i → xcover A U y)` and define
+a notion `cover_set` to which a notation `𝐂 a i ◃ U` can be attached.
+
+This notion has to be abstracted over the cover relation (whose
+type is the arity of the inductive `xcover` predicate just defined).
+
+Then it has to be abstracted over the arguments of that cover relation,
+i.e. the axiom set and the set U, and the subset (in that case `𝐂 a i`)
+sitting on the left hand side of `◃`.
DOCEND*)
ndefinition cover_set :
- ∀c: ∀A:Ax.Ω^A → A → CProp[0]. ∀A:Ax.∀C,U:Ω^A. CProp[0]
+ ∀cover: ∀A:Ax.Ω^A → A → CProp[0]. ∀A:Ax.∀C,U:Ω^A. CProp[0]
≝
- λc: ∀A:Ax.Ω^A → A → CProp[0]. λA,C,U.∀y.y ∈ C → c A U y.
+ λcover. λA, C,U. ∀y.y ∈ C → cover A U y.
-ndefinition cover_set_interactive :
- ∀c: ∀A:Ax.Ω^A → A → CProp[0]. ∀A:Ax.∀C,U:Ω^A. CProp[0].
-#cover; #A; #C; #U; napply (∀y:A.y ∈ C → ?); napply cover;
-##[ napply A;
-##| napply U;
-##| napply y;
-##]
-nqed.
+(*DOCBEGIN
+
+The `ndefinition` command takes a name, a type and body (of that type).
+The type can be omitted, and in that case it is inferred by the system.
+If the type is given, the system uses it to infer implicit arguments
+of the body. In that case all types are left implicit in the body.
+
+We now define the notation `a ◃ b`. Here the keywork `hvbox`
+and `break` tell the system how to wrap text when it does not
+fit the screen (they can be safely ignore for the scope of
+this tutorial). we also add an interpretation for that notation,
+where the (abstracted) cover relation is implicit. The system
+will not be able to infer it from the other arguments `C` and `U`
+and will thus prompt the user for it. This is also why we named this
+interpretation `covers set temp`: we will later define another
+interpretation in which the cover relation is the one we are going to
+define.
+
+DOCEND*)
-(* a \ltri b *)
notation "hvbox(a break ◃ b)" non associative with precedence 45
for @{ 'covers $a $b }.
interpretation "covers set temp" 'covers C U = (cover_set ?? C U).
+(*DOCBEGIN
+
+We can now define the cover relation using the `◃` notation for
+the premise of infinity.
+
+DOCEND*)
+
ninductive cover (A : Ax) (U : Ω^A) : A → CProp[0] ≝
-| creflexivity : ∀a:A. a ∈ U → cover ? U a
-| cinfinity : ∀a:A.∀i:𝐈 a. 𝐂 a i ◃ U → cover ? U a.
+| creflexivity : ∀a. a ∈ U → cover ? U a
+| cinfinity : ∀a. ∀i. 𝐂 a i ◃ U → cover ? U a.
+(** screenshot "cover". *)
napply cover;
nqed.
+(*DOCBEGIN
+
+Note that the system accepts the definition
+but prompts the user for the relation the `cover_set` notion is
+abstracted on.
+
+![The system asks for a cover relation][cover]
+
+The orizontal line separates the hypotheses from the conclusion.
+The `napply cover` command tells the system that the relation
+it is looking for is exactly our first context entry (i.e. the inductive
+predicate we are defining, up to α-conversion); while the `nqed` command
+ends a definition or proof.
+
+We can now define the interpretation for the cover relation between an
+element and a subset fist, then between two subsets (but this time
+we fixed the relation `cover_set` is abstracted on).
+
+DOCEND*)
+
interpretation "covers" 'covers a U = (cover ? U a).
-(* interpretation "covers set" 'covers a U = (cover_set cover ? a U). *)
+interpretation "covers set" 'covers a U = (cover_set cover ? a U).
+
+(*DOCBEGIN
+
+We will proceed similarly for the fish relation, but before going
+on it is better to give a short introduction to the proof mode of Matita.
+We define again the `cover_set` term, but this time we will build
+its body interactively. In λ-calculus Matita is based on, CIC, proofs
+and terms share the same syntax, and it thus possible to use the
+commands devoted to build proof term to build regular definitions.
+
+DOCEND*)
+
+
+ndefinition xcover_set :
+ ∀c: ∀A:Ax.Ω^A → A → CProp[0]. ∀A:Ax.∀C,U:Ω^A. CProp[0].
+(** screenshot "xcover-set-1". *)
+(*DOCBEGIN
+The system asks for a proof of the full statement, in an empty context.
+![xcover_set proof step ][xcover-set-1]
+The `#` command in the ∀-introduction rule, it gives a name to an
+assumption putting it in the context, and generates a λ-abstraction
+in the proof term.
+DOCEND*)
+#cover; #A; #C; #U; (** screenshot "xcover-set-2". *)
+(*DOCBEGIN
+![xcover_set proof step ][xcover-set-2]
+We have now to provide a proposition, and we exhibit it. We left
+a part of it implicit; since the system cannot infer it it will
+ask it later. Note that the type of `∀y:A.y ∈ C → ?` is a proposition
+whenever `?` is.
+DOCEND*)
+napply (∀y:A.y ∈ C → ?); (** screenshot "xcover-set-3". *)
+(*DOCBEGIN
+![xcover_set proof step ][xcover-set-3]
+The proposition we want to provide is an application of the
+cover relation we have abstracted in the context. The command
+`napply`, if the given term has not the expected type (in that
+case it is a product versus a proposition) it applies it to as many
+implicit arguments as necessary (in that case `? ? ?`).
+DOCEND*)
+napply cover; (** screenshot "xcover-set-4". *)
+(*DOCBEGIN
+![xcover_set proof step ][xcover-set-4]
+The system will now ask in turn the three implicit arguments
+passed to cover. The syntax `##[` allows to start a branching
+to tackle every sub proof individually, otherwise every command
+is applied to every subrpoof. The command `##|` switches to the next
+subproof and `##]` ends the branching.
+DOCEND*)
+##[ napply A;
+##| napply U;
+##| napply y;
+##]
+nqed.
+
+(*DOCBEGIN
+The definition of fish works exactly the same way as for cover, except
+that it is defined as a coinductive proposition.
+DOCEND*)
ndefinition fish_set ≝ λf:∀A:Ax.Ω^A → A → CProp[0].
λA,U,V.
interpretation "fish set" 'fish A U = (fish_set fish ? U A).
interpretation "fish" 'fish a U = (fish ? U a).
+(*DOCBEGIN
+
+Matita is able to generate elimination rules for inductive types,
+but not introduction rules for the coinductive case.
+
+DOCEND*)
+
+(* ncheck cover_rect_CProp0. *)
+
+(*DOCBEGIN
+
+We thus have to define the introduction rule for fish by corecursion.
+Here we again use the proof mode of Matita to exhibit the body of the
+corecursive function.
+
+DOCEND*)
+
nlet corec fish_rec (A:Ax) (U: Ω^A)
(P: Ω^A) (H1: P ⊆ U)
- (H2: ∀a:A. a ∈ P → ∀j: 𝐈 a. 𝐂 a j ≬ P):
- ∀a:A. ∀p: a ∈ P. a ⋉ U ≝ ?.
-#a; #p; napply cfish; (** screenshot "def-fish-rec". *)
-##[ napply H1; napply p;
-##| #i; ncases (H2 a p i); #x; *; #xC; #xP; @; ##[napply x]
- @; ##[ napply xC ] napply (fish_rec ? U P); nassumption;
+ (H2: ∀a:A. a ∈ P → ∀j: 𝐈 a. 𝐂 a j ≬ P): ∀a:A. ∀p: a ∈ P. a ⋉ U ≝ ?.
+(** screenshot "def-fish-rec-1". *)
+#a; #p; napply cfish;
+##[ (** screenshot "def-fish-rec-2". *) napply H1;
+ (** screenshot "def-fish-rec-3". *) napply p;
+##| (** screenshot "def-fish-rec-4". *) #i; ncases (H2 a p i);
+ (** screenshot "def-fish-rec-5". *) #x; *; #xC; #xP;
+ (** screenshot "def-fish-rec-5". *) @;
+ ##[ (** screenshot "def-fish-rec-6". *) napply x
+ ##| (** screenshot "def-fish-rec-7". *)
+ @; ##[ napply xC;
+ ##| (** screenshot "def-fish-rec-8". *)
+ napply (fish_rec ? U P);
+ nassumption;
+ ##]
+ ##]
##]
nqed.
-notation "◃U" non associative with precedence 55
-for @{ 'coverage $U }.
+(*DOCBEGIN
+![fish proof step][def-fish-rec-1]
+![fish proof step][def-fish-rec-2]
+![fish proof step][def-fish-rec-3]
+![fish proof step][def-fish-rec-4]
+![fish proof step][def-fish-rec-5]
+![fish proof step][def-fish-rec-6]
+![fish proof step][def-fish-rec-7]
+![fish proof step][def-fish-rec-8]
+DOCEND*)
ndefinition coverage : ∀A:Ax.∀U:Ω^A.Ω^A ≝ λA,U.{ a | a ◃ U }.
+notation "◃U" non associative with precedence 55 for @{ 'coverage $U }.
+
interpretation "coverage cover" 'coverage U = (coverage ? U).
ndefinition cover_equation : ∀A:Ax.∀U,X:Ω^A.CProp[0] ≝ λA,U,X.
Bla Bla,
-<div id="figure1" class="img" ><img src="figure1.png"/>foo</div>
DOCEND*)
projects / helm.git / blobdiff