X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;ds=inline;f=helm%2Fsoftware%2Fmatita%2Fnlibrary%2Ftopology%2Figft.ma;h=5032471e11a9577150873ee9b9f46b2abf4aa24d;hb=7433f1b6439e7c5eb532546b533980686636f468;hp=8e05ca6f45b2e9aa1f93ef7d25b06fe5193ae64d;hpb=cde41460616634f77c2c11b585400dcc613b88f1;p=helm.git diff --git a/helm/software/matita/nlibrary/topology/igft.ma b/helm/software/matita/nlibrary/topology/igft.ma index 8e05ca6f4..5032471e1 100644 --- a/helm/software/matita/nlibrary/topology/igft.ma +++ b/helm/software/matita/nlibrary/topology/igft.ma @@ -1,157 +1,1208 @@ +(*D -include "logic/connectives.ma". +Matita Tutorial: inductively generated formal topologies +======================================================== -nrecord powerset (X : Type[0]) : Type[1] â { char : X â CProp[0] }. +This is a not so short introduction to Matita, based on +the formalization of the paper -interpretation "char" 'subset p = (mk_powerset ? p). +> Between formal topology and game theory: an +> explicit solution for the conditions for an +> inductive generation of formal topologies -interpretation "pwset" 'powerset a = (powerset a). +by S.Berardi and S. Valentini. The tutorial is by Enrico Tassi. -interpretation "in" 'mem a X = (char ? X a). +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 aesthetic +point of view, but also from the practical point of view. Being +consistent allows to follow the paper in a pedantic way, and hopefully +to make the formalization (at least the definitions and proved +statements) readable to the author of the paper. -ndefinition subseteq â λA.λU,V : Ω^A. - âx.x â U â x â V. +Orienteering +------------ -interpretation "subseteq" 'subseteq u v = (subseteq ? u v). +The graphical interface of Matita is composed of three windows: +the script window, on the left, is where you type; the sequent +window on the top right is where the system shows you the ongoing proof; +the error window, on the bottom right, is where the system complains. +On the top of the script window five buttons drive the processing of +the proof script. From left to right the requesting the system to: -ndefinition overlaps â λA.λU,V : Ω^A. - âx.x â U ⧠x â V. +- go back to the beginning of the script +- go back one step +- go to the current cursor position +- advance one step +- advance to the end of the script -interpretation "overlaps" 'overlaps u v = (overlaps ? u v). -(* -ndefinition intersect â λA.λu,v:Ω\sup A.{ y | y â u ⧠y â v }. +When the system processes a command, it locks the part of the script +corresponding to the command, such that you cannot edit it anymore +(without to go back). Locked parts are coloured in blue. -interpretation "intersect" 'intersects u v = (intersect ? u v). -*) -nrecord axiom_set : Type[1] â { - S:> Type[0]; - I: S â Type[0]; - C: âa:S. I a â Ω ^ S +The sequent window is hyper textual, i.e. you can click on symbols +to jump to their definition, or switch between different notation +for the same expression (for example, equality has two notations, +one of them makes the type of the arguments explicit). + +Everywhere in the script you can use the `ncheck (term).` command to +ask for the type a given term. If you that in the middle of a proof, +the term is assumed to live in the current proof context (i.e. can use +variables introduced so far). + +To ease the typing of mathematical symbols, the script window +implements two unusual input facilities: + +- some TeX symbols can be typed using their TeX names, and are + automatically converted to UTF-8 characters. For a list of + the supported TeX names, see the menu: View â¹ TeX/UTF-8 Table. + Moreover some ASCII-art is understood as well, like `=>` and `->` + to mean double or single arrows. + Here we recall some of these "shortcuts": + + - â can be typed with `\Forall` + - λ can be typed with `\lambda` + - â can be typed with `\def` or `:=` + - â can be typed with `to` or `->` + +- some symbols have variants, like the ⤠relation and â¼, â°, â . + The user can cycle between variants typing one of them and then + pressing ALT-L. Note that also letters do have variants, for + example W has Ω, ð and ð, L has Î, ð, and ð, F has Φ, ⦠+ Variants are listed in the aforementioned TeX/UTF-8 table. + +CIC (as implemented in Matita) in a nutshell +-------------------------------------------- + +... + +Type is a set equipped with the Id equality (i.e. an intensional, +not quotiented set). We will avoid using Leibnitz equality Id, +thus we will explicitly equip a set with an equality when needed. +We will call this structure `setoid`. Note that we will +attach the infix = symbols only to the equality of a setoid, +not to Id. + +... + +We write Type[i] to mention a Type in the predicative hierarchy +of types. To ease the comprehension we will use Type[0] for sets, +and Type[1] for classes. + +For every Type[i] there is a corresponding level of predicative +propositions CProp[i]. + +CIC is also equipped with an impredicative sort Prop that we will not +use in this tutorial. + +The standard library and the `include` command +---------------------------------------------- + +Some basic notions, like subset, membership, intersection and union +are part of the standard library of Matita. + +These notions come with some standard notation attached to them: + +- 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 `include` command tells Matita to load a part of the library, +in particular the part that we will use can be loaded as follows: + +D*) + +include "sets/sets.ma". + +(*HIDE*) +(* move away *) +nlemma subseteq_intersection_l: âA.âU,V,W:Ω^A.U â W ⨠V â W â U â© V â W. +#A; #U; #V; #W; *; #H; #x; *; #xU; #xV; napply H; nassumption; +nqed. + +nlemma subseteq_union_l: âA.âU,V,W:Ω^A.U â W â V â W â U ⪠V â W. +#A; #U; #V; #W; #H; #H1; #x; *; #Hx; ##[ napply H; ##| napply H1; ##] nassumption; +nqed. + +nlemma subseteq_intersection_r: âA.âU,V,W:Ω^A.W â U â W â V â W â U â© V. +#A; #U; #V; #W; #H1; #H2; #x; #Hx; @; ##[ napply H1; ##| napply H2; ##] nassumption; +nqed. + +ninductive sigma (A : Type[0]) (P : A â CProp[0]) : Type[0] â + sig_intro : âx:A.P x â sigma A P. + +interpretation "sigma" 'sigma \eta.p = (sigma ? p). +(*UNHIDE*) + +(*D + +Some basic results that we will use are also part of the sets library: + +- subseteq\_union\_l: âA.âU,V,W:Ω^A.U â W â V â W â U ⪠V â W +- subseteq\_intersection\_r: âA.âU,V,W:Ω^A.W â U â W â V â W â U â© V + +Defining Axiom set +------------------ + +A set of axioms is made of a set S, a family of sets I and a +family C of subsets of S indexed by elements a of S and I(a). + +It is desirable to state theorems like "for every set of axioms, â¦" +without explicitly mentioning S, I and C. To do that, the three +components have to be grouped into a record (essentially a dependently +typed tuple). The system is able to generate the projections +of the record for free, and they are named as the fields of +the record. So, given a axiom set `A` we can obtain the set +with `S A`, the family of sets with `I A` and the family of subsets +with `C A`. + +D*) + +nrecord Ax : Type[1] â { + S :> setoid; + I : S â Type[0]; + C : âa:S. I a â Ω ^ S }. -ndefinition cover_set â λc:âA:axiom_set.Ω^A â A â CProp[0].λA,C,U. - ây.y â C â c A U y. +(*D + +Forget for a moment the `:>` that will be detailed later, and focus on +the record definition. It is made of a list of pairs: a name, followed +by `:` and the its type. It is a dependently typed tuple, thus +already defined names (fields) can be used in the types that follow. + +Note that `S` is declared to be a `setoid` and not a Type. The original +paper probably also considers I to generate setoids, and both I and C +to be morphisms. For the sake of simplicity, we will "cheat" and use +setoids only when strictly needed (i.e. where we want to talk about +equality). Setoids will play a role only when we will define +the alternative version of the axiom set. + +Note that the field `S` was declared with `:>` instead of a simple `:`. +This declares the `S` projection to be a coercion. A coercion is +a function case the system automatically inserts when it is needed. +In that case, the projection `S` has type `Ax â setoid`, and whenever +the expected type of a term is `setoid` while its type is `Ax`, the +system inserts the coercion around it, to make the whole term well types. + +When formalizing an algebraic structure, declaring the carrier as a +coercion is a common practice, since it allows to write statements like + + âG:Group.âx:G.x * x^-1 = 1 + +The quantification over `x` of type `G` is ill-typed, since `G` is a term +(of type `Group`) and thus not a type. Since the carrier projection +`carr` of `G` is a coercion, that maps a `Group` into the type of +its elements, the system automatically inserts `carr` around `G`, +obtaining `â¦âx: carr G.â¦`. Coercions are also hidden by the system +when it displays a term. + +In this particular case, the coercion `S` allows to write + + âA:Ax.âa:A.⦠+ +Since `A` is not a type, but it can be turned into a `setoid` by `S` +and a `setoid` can be turned into a type by its `carr` projection, the +composed coercion `carr â S` is silently inserted. + +Implicit arguments +------------------ + +Something that is not still satisfactory, is that the dependent type +of `I` and `C` are abstracted over the Axiom set. To obtain the +precise type of a term, you can use the `ncheck` command as follows. + +D*) + +(* ncheck I. *) +(* ncheck C. *) + +(*D + +One would like to write `I a` and not `I A a` under a context where +`A` is an axiom set and `a` has type `S A` (or thanks to the coercion +mechanism simply `A`). In Matita, a question mark represents an implicit +argument, i.e. a missing piece of information the system is asked to +infer. Matita performs some sort of type inference, thus writing +`I ? a` is enough: since the second argument of `I` is typed by the +first one, the first one can be inferred just computing the type of `a`. + +D*) + +(* ncheck (âA:Ax.âa:A.I ? a). *) + +(*D + +This is still not completely satisfactory, since you have always type +`?`; to fix this minor issue we have to introduce the notational +support built in Matita. + +Notation for I and C +-------------------- + +Matita is quipped with a quite complex notational support, +allowing the user to define and use mathematical notations +([From Notation to Semantics: There and Back Again][1]). + +Since notations are usually ambiguous (e.g. the frequent overloading of +symbols) Matita distinguishes between the term level, the +content level, and the presentation level, allowing multiple +mappings between the content and the term level. + +The mapping between the presentation level (i.e. what is typed on the +keyboard and what is displayed in the sequent window) and the content +level is defined with the `notation` command. When followed by +`>`, it defines an input (only) notation. + +D*) + +notation > "ð term 90 a" non associative with precedence 70 for @{ 'I $a }. +notation > "ð term 90 a term 90 i" non associative with precedence 70 for @{ 'C $a $i }. + +(*D + +The first notation defines the writing `ð a` where `a` is a generic +term of precedence 90, the maximum one. This high precedence forces +parentheses around any term of a lower precedence. For example `ð x` +would be accepted, since identifiers have precedence 90, but +`ð f x` would be interpreted as `(ð f) x`. In the latter case, parentheses +have to be put around `f x`, thus the accepted writing would be `ð (f x)`. + +To obtain the `ð` is enough to type `I` and then cycle between its +similar symbols with ALT-L. The same for `ð`. Notations cannot use +regular letters or the round parentheses, thus their variants (like the +bold ones) have to be used. + +The first notation associates `ð a` with `'I $a` where `'I` is a +new content element to which a term `$a` is passed. + +Content elements have to be interpreted, and possibly multiple, +incompatible, interpretations can be defined. + +D*) + +interpretation "I" 'I a = (I ? a). +interpretation "C" 'C a i = (C ? a i). + +(*D + +The `interpretation` command allows to define the mapping between +the content level and the terms level. Here we associate the `I` and +`C` projections of the Axiom set record, where the Axiom set is an implicit +argument `?` to be inferred by the system. + +Interpretation are bi-directional, thus when displaying a term like +`C _ a i`, the system looks for a presentation for the content element +`'C a i`. + +D*) + +notation < "ð \sub( â¨aâ© )" non associative with precedence 70 for @{ 'I $a }. +notation < "ð \sub( â¨a,\emsp iâ© )" non associative with precedence 70 for @{ 'C $a $i }. + +(*D + +For output purposes we can define more complex notations, for example +we can put bold parentheses around the arguments of `ð` and `ð`, decreasing +the size of the arguments and lowering their baseline (i.e. putting them +as subscript), separating them with a comma followed by a little space. + +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 understanding of the definition of the cover relation +between subsets, we first define the inductive predicate unfolding the +definition, and we later refine it with. + +D*) + +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. + +(*D + +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 abstracted (in the arity +of the inductive predicate) on the right of `:`. + +D*) + +(* ncheck xcreflexivity. *) + +(*D + +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 `â`. + +D*) + +ndefinition cover_set : + âcover: âA:Ax.Ω^A â A â CProp[0]. âA:Ax.âC,U:Ω^A. CProp[0] +â + λcover. λA, C,U. ây.y â C â cover A U y. + +(*D + +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. + +D*) notation "hvbox(a break â b)" non associative with precedence 45 -for @{ 'covers $a $b }. (* a \ltri b *) +for @{ 'covers $a $b }. interpretation "covers set temp" 'covers C U = (cover_set ?? C U). -ninductive cover (A : axiom_set) (U : Ω^A) : A â CProp[0] â -| creflexivity : âa:A. a â U â cover ? U a -| cinfinity : âa:A. âi:I ? a. (C ? a i â U) â cover ? U a. +(*D + +The cover relation +------------------ + +We can now define the cover relation using the `â` notation for +the premise of infinity. + +D*) + +ninductive cover (A : Ax) (U : Ω^A) : A â CProp[0] â +| creflexivity : âa. a â U â cover ? U a +| cinfinity : âa. âi. ð a i â U â cover ? U a. +(** screenshot "cover". *) napply cover; nqed. +(*D + +Note that the system accepts the definition +but prompts the user for the relation the `cover_set` notion is +abstracted on. + + + +The horizontal 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). + +D*) + interpretation "covers" 'covers a U = (cover ? U a). interpretation "covers set" 'covers a U = (cover_set cover ? a U). -ndefinition fish_set â λf:âA:axiom_set.Ω^A â A â CProp[0]. +(*D + +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 the λ-calculus Matita is based on, CIC, proofs +and terms share the same syntax, and it is thus possible to use the +commands devoted to build proof term to build regular definitions. +A tentative semantics for the proof mode commands (called tactics) +in terms of sequent calculus rules are given in the +appendix. + +D*) + +ndefinition xcover_set : + âc: âA:Ax.Ω^A â A â CProp[0]. âA:Ax.âC,U:Ω^A. CProp[0]. + (** screenshot "xcover-set-1". *) +#cover; #A; #C; #U; (** screenshot "xcover-set-2". *) +napply (ây:A.y â C â ?); (** screenshot "xcover-set-3". *) +napply cover; (** screenshot "xcover-set-4". *) +##[ napply A; +##| napply U; +##| napply y; +##] +nqed. + +(*D[xcover-set-1] +The system asks for a proof of the full statement, in an empty context. + +The `#` command is the â-introduction rule, it gives a name to an +assumption putting it in the context, and generates a λ-abstraction +in the proof term. + +D[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. + +D[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 `? ? ?`). + +D[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. +D*) + +(*D + +The fish relation +----------------- + +The definition of fish works exactly the same way as for cover, except +that it is defined as a coinductive proposition. +D*) + +ndefinition fish_set â λf:âA:Ax.Ω^A â A â CProp[0]. λA,U,V. âa.a â V ⧠f A U a. +(* a \ltimes b *) notation "hvbox(a break â b)" non associative with precedence 45 -for @{ 'fish $a $b }. (* a \ltimes b *) +for @{ 'fish $a $b }. interpretation "fish set temp" 'fish A U = (fish_set ?? U A). -ncoinductive fish (A : axiom_set) (F : Ω^A) : A â CProp[0] â -| cfish : âa. a â F â (âi:I ? a.C A a i â F) â fish A F a. +ncoinductive fish (A : Ax) (F : Ω^A) : A â CProp[0] â +| cfish : âa. a â F â (âi:ð a .ð a i â F) â fish A F a. napply fish; nqed. interpretation "fish set" 'fish A U = (fish_set fish ? U A). interpretation "fish" 'fish a U = (fish ? U a). -nlet corec fish_rec (A:axiom_set) (U: Ω^A) +(*D + +Introction rule for fish +------------------------ + +Matita is able to generate elimination rules for inductive types, +but not introduction rules for the coinductive case. + +D*) + +(* ncheck cover_rect_CProp0. *) + +(*D + +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. + +D*) + +nlet corec fish_rec (A:Ax) (U: Ω^A) (P: Ω^A) (H1: P â U) - (H2: âa:A. a â P â âj: I ? a. C ? a j ⬠P): - âa:A. âp: a â P. a â U â ?. -#a; #p; napply cfish; -##[ napply H1; napply p; -##| #i; ncases (H2 a p i); #x; *; #xC; #xP; napply ex_intro; ##[napply x] - napply conj; ##[ 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". *) +##[ nchange in H1 with (âb.bâP â bâU); (** screenshot "def-fish-rec-2-1". *) + napply H1; (** screenshot "def-fish-rec-3". *) + nassumption; +##| #i; ncases (H2 a p i); (** screenshot "def-fish-rec-5". *) + #x; *; #xC; #xP; (** screenshot "def-fish-rec-5-1". *) + @; (** screenshot "def-fish-rec-6". *) + ##[ napply x + ##| @; (** screenshot "def-fish-rec-7". *) + ##[ napply xC; + ##| napply (fish_rec ? U P); (** screenshot "def-fish-rec-9". *) + nassumption; + ##] + ##] +##] +nqed. + +(*D +D[def-fish-rec-1] +Note the first item of the context, it is the corecursive function we are +defining. This item allows to perform the recursive call, but we will be +allowed to do such call only after having generated a constructor of +the fish coinductive type. + +We introduce `a` and `p`, and then return the fish constructor `cfish`. +Since the constructor accepts two arguments, the system asks for them. + +D[def-fish-rec-2] +The first one is a proof that `a â U`. This can be proved using `H1` and `p`. +With the `nchange` tactic we change `H1` into an equivalent form (this step +can be skipped, since the system would be able to unfold the definition +of inclusion by itself) + +D[def-fish-rec-2-1] +It is now clear that `H1` can be applied. Again `napply` adds two +implicit arguments to `H1 ? ?`, obtaining a proof of `? â U` given a proof +that `? â P`. Thanks to unification, the system understands that `?` is actually +`a`, and it asks a proof that `a â P`. + +D[def-fish-rec-3] +The `nassumption` tactic looks for the required proof in the context, and in +that cases finds it in the last context position. + +We move now to the second branch of the proof, corresponding to the second +argument of the `cfish` constructor. + +We introduce `i` and then we destruct `H2 a p i`, that being a proof +of an overlap predicate, give as an element and a proof that it is +both in `ð a i` and `P`. + +D[def-fish-rec-5] +We then introduce `x`, break the conjunction (the `*;` command is the +equivalent of `ncases` but operates on the first hypothesis that can +be introduced. We then introduce the two sides of the conjunction. + +D[def-fish-rec-5-1] +The goal is now the existence of an a point in `ð a i` fished by `U`. +We thus need to use the introduction rule for the existential quantifier. +In CIC it is a defined notion, that is an inductive type with just +one constructor (one introduction rule) holding the witness and the proof +that the witness satisfies a proposition. + +> ncheck Ex. + +Instead of trying to remember the name of the constructor, that should +be used as the argument of `napply`, we can ask the system to find by +itself the constructor name and apply it with the `@` tactic. +Note that some inductive predicates, like the disjunction, have multiple +introduction rules, and thus `@` can be followed by a number identifying +the constructor. + +D[def-fish-rec-6] +After choosing `x` as the witness, we have to prove a conjunction, +and we again apply the introduction rule for the inductively defined +predicate `â§`. + +D[def-fish-rec-7] +The left hand side of the conjunction is trivial to prove, since it +is already in the context. The right hand side needs to perform +the co-recursive call. + +D[def-fish-rec-9] +The co-recursive call needs some arguments, but all of them live +in the context. Instead of explicitly mention them, we use the +`nassumption` tactic, that simply tries to apply every context item. + +D*) + +(*D + +Subset of covered/fished points +------------------------------- + +We now have to define the subset of `S` of points covered by `U`. +We also define a prefix notation for it. Remember that the precedence +of the prefix form of a symbol has to be lower than the precedence +of its infix form. + +D*) + +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). + +(*D + +Here we define the equation characterizing the cover relation. +In the igft.ma file we proved that `âU` is the minimum solution for +such equation, the interested reader should be able to reply the proof +with Matita. + +D*) + +ndefinition cover_equation : âA:Ax.âU,X:Ω^A.CProp[0] â λA,U,X. + âa.a â X â (a â U ⨠âi:ð a.ây.y â ð a i â y â X). + +ntheorem coverage_cover_equation : âA,U. cover_equation A U (âU). +#A; #U; #a; @; #H; +##[ nelim H; #b; (* manca clear *) + ##[ #bU; @1; nassumption; + ##| #i; #CaiU; #IH; @2; @ i; #c; #cCbi; ncases (IH ? cCbi); + ##[ #E; @; napply E; + ##| #_; napply CaiU; nassumption; ##] ##] +##| ncases H; ##[ #E; @; nassumption] + *; #j; #Hj; @2 j; #w; #wC; napply Hj; nassumption; +##] +nqed. + +ntheorem coverage_min_cover_equation : + âA,U,W. cover_equation A U W â âU â W. +#A; #U; #W; #H; #a; #aU; nelim aU; #b; +##[ #bU; ncases (H b); #_; #H1; napply H1; @1; nassumption; +##| #i; #CbiU; #IH; ncases (H b); #_; #H1; napply H1; @2; @i; napply IH; ##] nqed. -alias symbol "covers" = "covers". -alias symbol "covers" = "covers". -ntheorem covers_elim2: - âA: axiom_set. âU:Ω^A.âP: A â CProp[0]. - (âa:A. a â U â P a) â - (âa:A.âV:Ω^A. a â V â V â U â (ây. y â V â P y) â P a) â - âa:A. a â U â P a. -#A; #U; #P; #H1; #H2; #a; #aU; nelim aU; -##[ #b; #H; napply H1; napply H; -##| #b; #i; #CaiU; #H; napply H2; - ##[ napply (C ? b i); - ##| napply cinfinity; ##[ napply i ] nwhd; #y; #H3; napply creflexivity; ##] - nassumption; +(*D + +We similarly define the subset of point fished by `F`, the +equation characterizing `âF` and prove that fish is +the biggest solution for such equation. + +D*) + +notation "âF" non associative with precedence 55 +for @{ 'fished $F }. + +ndefinition fished : âA:Ax.âF:Ω^A.Ω^A â λA,F.{ a | a â F }. + +interpretation "fished fish" 'fished F = (fished ? F). + +ndefinition fish_equation : âA:Ax.âF,X:Ω^A.CProp[0] â λA,F,X. + âa. a â X â a â F ⧠âi:ð a.ây.y â ð a i ⧠y â X. + +ntheorem fished_fish_equation : âA,F. fish_equation A F (âF). +#A; #F; #a; @; (* *; non genera outtype che lega a *) #H; ncases H; +##[ #b; #bF; #H2; @ bF; #i; ncases (H2 i); #c; *; #cC; #cF; @c; @ cC; + napply cF; +##| #aF; #H1; @ aF; napply H1; +##] +nqed. + +ntheorem fished_max_fish_equation : âA,F,G. fish_equation A F G â G â âF. +#A; #F; #G; #H; #a; #aG; napply (fish_rec ⦠aG); +#b; ncases (H b); #H1; #_; #bG; ncases (H1 bG); #E1; #E2; nassumption; +nqed. + +(*D + +Part 2, the new set of axioms +----------------------------- + +Since the name of objects (record included) has to unique +within the same script, we prefix every field name +in the new definition of the axiom set with `n`. + +D*) + +nrecord nAx : Type[2] â { + nS:> setoid; + nI: nS â Type[0]; + nD: âa:nS. nI a â Type[0]; + nd: âa:nS. âi:nI a. nD a i â nS +}. + +(*D + +We again define a notation for the projections, making the +projected record an implicit argument. Note that since we already have +a notation for `ð` we just add another interpretation for it. The +system, looking at the argument of `ð`, will be able to use +the correct interpretation. + +D*) + +notation "ð \sub ( â¨a,\emsp iâ© )" non associative with precedence 70 for @{ 'D $a $i }. +notation "ð \sub ( â¨a,\emsp i,\emsp jâ© )" non associative with precedence 70 for @{ 'd $a $i $j}. + +notation > "ð term 90 a term 90 i" non associative with precedence 70 for @{ 'D $a $i }. +notation > "ð term 90 a term 90 i term 90 j" non associative with precedence 70 for @{ 'd $a $i $j}. + +interpretation "D" 'D a i = (nD ? a i). +interpretation "d" 'd a i j = (nd ? a i j). +interpretation "new I" 'I a = (nI ? a). + +(*D + +The paper defines the image as + +> Im[d(a,i)] = { d(a,i,j) | j : D(a,i) } + +but this cannot be ..... MAIL + +> Im[d(a,i)] â V + +Allora ha una comoda interpretazione (che voi usate liberamente) + +> âj:D(a,i). d(a,i,j) â V + +Ma se voglio usare Im per definire C, che è un subset di S, devo per +forza (almeno credo) definire un subset, ovvero dire che + +> Im[d(a,i)] = { y : S | âj:D(a,i). y = d(a,i,j) } + +Non ci sono problemi di sostanza, per voi S è un set, quindi ha la sua +uguaglianza..., ma quando mi chiedo se l'immagine è contenuta si +scatenano i setoidi. Ovvero Im[d(a,i)] â V diventa il seguente + +> âx:S. ( âj.x = d(a,i,j) ) â x â V + + +D*) + +ndefinition image â λA:nAx.λa:A.λi. { x | âj:ð a i. x = ð a i j }. + +notation > "ðð¦ [ð term 90 a term 90 i]" non associative with precedence 70 for @{ 'Im $a $i }. +notation "ðð¦ [ð \sub ( â¨a,\emsp iâ© )]" non associative with precedence 70 for @{ 'Im $a $i }. + +interpretation "image" 'Im a i = (image ? a i). + +(*D + + + +D*) + +ndefinition Ax_of_nAx : nAx â Ax. +#A; @ A (nI ?); #a; #i; napply (ðð¦ [ð a i]); +nqed. + +ndefinition nAx_of_Ax : Ax â nAx. +#A; @ A (I ?); +##[ #a; #i; napply (Σx:A.x â ð a i); +##| #a; #i; *; #x; #_; napply x; ##] nqed. -STOP +(*D + +We then define the inductive type of ordinals, parametrized over an axiom +set. We also attach some notations to the constructors. + +D*) + +ninductive Ord (A : nAx) : Type[0] â + | oO : Ord A + | oS : Ord A â Ord A + | oL : âa:A.âi.âf:ð a i â Ord A. Ord A. + +notation "0" non associative with precedence 90 for @{ 'oO }. +notation "Î term 90 f" non associative with precedence 50 for @{ 'oL $f }. +notation "x+1" non associative with precedence 50 for @{'oS $x }. + +interpretation "ordinals Zero" 'oO = (oO ?). +interpretation "ordinals Lambda" 'oL f = (oL ? ? ? f). +interpretation "ordinals Succ" 'oS x = (oS ? x). + +(*D + +Note that Matita does not support notation in the left hand side +of a pattern match, and thus the names of the constructors have to +be spelled out verbatim. + +BLA let rec. Bla let_in. + +D*) + +nlet rec famU (A : nAx) (U : Ω^A) (x : Ord A) on x : Ω^A â + match x with + [ oO â U + | oS y â let Un â famU A U y in Un ⪠{ x | âi.ðð¦[ð x i] â Un} + | oL a i f â { x | âj.x â famU A U (f j) } ]. + +notation < "term 90 U \sub (term 90 x)" non associative with precedence 50 for @{ 'famU $U $x }. +notation > "U â½ term 90 x" non associative with precedence 50 for @{ 'famU $U $x }. + +interpretation "famU" 'famU U x = (famU ? U x). + +(*D + +We attach as the input notation for U_x the similar `Uâ½x` where underscore, +that is a character valid for identifier names, has been replaced by `â½` that is +not. The symbol `â½` can act as a separator, and can be typed as an alternative +for `_` (i.e. pressing ALT-L after `_`). + +The notion â(U) has to be defined as the subset of of y +belonging to U_x for some x. Moreover, we have to define the notion +of cover between sets again, since the one defined at the beginning +of the tutorial works only for the old axiom set definition. + +D*) + +ndefinition ord_coverage : âA:nAx.âU:Ω^A.Ω^A â λA,U.{ y | âx:Ord A. y â famU ? U x }. + +ndefinition ord_cover_set â λc:âA:nAx.Ω^A â Ω^A.λA,C,U. + ây.y â C â y â c A U. + +interpretation "coverage new cover" 'coverage U = (ord_coverage ? U). +interpretation "new covers set" 'covers a U = (ord_cover_set ord_coverage ? a U). +interpretation "new covers" 'covers a U = (mem ? (ord_coverage ? U) a). + +(*D + +Before proving that this cover relation validates the reflexivity and infinity +rules, we prove this little technical lemma that is used in the proof for the +infinity rule. + +D*) + +nlemma ord_subset: + âA:nAx.âa:A.âi,f,U.âj:ð a i.Uâ½(f j) â Uâ½(Î f). +#A; #a; #i; #f; #U; #j; #b; #bUf; @ j; nassumption; +nqed. + +(*D + +The proof of infinity uses the following form of the Axiom of choice, +that cannot be prove inside Matita, since the existential quantifier +lives in the sort of predicative propositions while the sigma in the conclusion +lives in the sort of data types, and thus the former cannot be eliminated +to provide the second. + +D*) + +naxiom AC : âA,a,i,U. + (âj:ð a i.âx:Ord A.ð a i j â Uâ½x) â (Σf.âj:ð a i.ð a i j â Uâ½(f j)). + +(*D + +In the proof of infinity, we have to rewrite under the â predicate. +It is clearly possible to show that U_x is an extensional set: + +> a=b â a â U_x â b â U_x + +Anyway this proof in non trivial induction over x, that requires ð and ð to be +declared as morphisms. This poses to problem, but goes out of the scope of the +tutorial and we thus assume it. + +D*) + +naxiom setoidification : + âA:nAx.âa,b:A.âx.âU.a=b â b â Uâ½x â a â Uâ½x. + +(*D + +The reflexivity proof is trivial, it is enough to provide the ordinal 0 +as a witness, then â(U) reduces to U by definition, hence the conclusion. + +D*) +ntheorem new_coverage_reflexive: + âA:nAx.âU:Ω^A.âa. a â U â a â U. +#A; #U; #a; #H; @ (0); napply H; +nqed. + +(*D + +We now proceed with the proof of the infinity rule. + +D*) + +alias symbol "covers" = "new covers set". +alias symbol "covers" = "new covers". +alias symbol "covers" = "new covers set". +alias symbol "covers" = "new covers". +ntheorem new_coverage_infinity: + âA:nAx.âU:Ω^A.âa:A. (âi:ð a. ðð¦[ð a i] â U) â a â U. +#A; #U; #a; (** screenshot "n-cov-inf-1". *) +*; #i; #H; nnormalize in H; (** screenshot "n-cov-inf-2". *) +ncut (ây:ð a i.âx:Ord A.ð a i y â Uâ½x); ##[ (** screenshot "n-cov-inf-3". *) + #z; napply H; @ z; napply #; ##] #H'; (** screenshot "n-cov-inf-4". *) +ncases (AC ⦠H'); #f; #Hf; (** screenshot "n-cov-inf-5". *) +ncut (âj.ð a i j â Uâ½(Î f)); + ##[ #j; napply (ord_subset ⦠f ⦠(Hf j));##] #Hf';(** screenshot "n-cov-inf-6". *) +@ (Î f+1); (** screenshot "n-cov-inf-7". *) +@2; (** screenshot "n-cov-inf-8". *) +@i; #x; *; #d; #Hd; (** screenshot "n-cov-inf-9". *) +napply (setoidification ⦠Hd); napply Hf'; +nqed. + +(*D +D[n-cov-inf-1] +We eliminate the existential, obtaining an `i` and a proof that the +image of d(a,i) is covered by U. The `nnormalize` tactic computes the normal +form of `H`, thus expands the definition of cover between sets. + +D[n-cov-inf-2] +The paper proof considers `H` implicitly substitutes the equation assumed +by `H` in its conclusion. In Matita this step is not completely trivia. +We thus assert (`ncut`) the nicer form of `H`. + +D[n-cov-inf-3] +After introducing `z`, `H` can be applied (choosing `ð a i z` as `y`). +What is the left to prove is that `âj: ð a j. ð a i z = ð a i j`, that +becomes trivial is `j` is chosen to be `z`. In the command `napply #`, +the `#` is a standard notation for the reflexivity property of the equality. + +D[n-cov-inf-4] +Under `H'` the axiom of choice `AC` can be eliminated, obtaining the `f` and +its property. + +D[n-cov-inf-5] +The paper proof does now a forward reasoning step, deriving (by the ord_subset +lemma we proved above) `Hf'` i.e. ð a i j â Uâ½(Îf). + +D[n-cov-inf-6] +To prove that `aâU` we have to exhibit the ordinal x such that `a â Uâ½x`. + +D[n-cov-inf-7] +The definition of `Uâ½(â¦+1)` expands to the union of two sets, and proving +that `a â X ⪠Y` is defined as proving that `a` is in `X` or `Y`. Applying +the second constructor `@2;` of the disjunction, we are left to prove that `a` +belongs to the right hand side. + +D[n-cov-inf-8] +We thus provide `i`, introduce the element being in the image and we are +left to prove that it belongs to `U_(Îf)`. In the meanwhile, since belonging +to the image means that there exists an object in the domain⦠we eliminate the +existential, obtaining `d` (of type `ð a i`) and the equation defining `x`. + +D[n-cov-inf-9] +We just need to use the equational definition of `x` to obtain a conclusion +that can be proved with `Hf'`. We assumed that `U_x` is extensional for +every `x`, thus we are allowed to use `Hd` and close the proof. + +D*) + +(*D + +The next proof is that â(U) is mininal. The hardest part of the proof +it to prepare the goal for the induction. The desiderata is to prove +`Uâ½o â V` by induction on `o`, but the conclusion of the lemma is, +unfolding all definitions: + +> âx. x â { y | âo:Ord A.y â Uâ½o } â x â V + +D*) + +nlemma new_coverage_min : + âA:nAx.âU:Ω^A.âV.U â V â (âa:A.âi.ðð¦[ð a i] â V â a â V) â âU â V. +#A; #U; #V; #HUV; #Im;#b; (** screenshot "n-cov-min-2". *) +*; #o; (** screenshot "n-cov-min-3". *) +ngeneralize in match b; nchange with (Uâ½o â V); (** screenshot "n-cov-min-4". *) +nelim o; (** screenshot "n-cov-min-5". *) +##[ #b; #bU0; napply HUV; napply bU0; +##| #p; #IH; napply subseteq_union_l; ##[ nassumption; ##] + #x; *; #i; #H; napply (Im ? i); napply (subseteq_trans ⦠IH); napply H; +##| #a; #i; #f; #IH; #x; *; #d; napply IH; ##] +nqed. + +(*D +D[n-cov-min-2] +After all the introductions, event the element hidden in the â definition, +we have to eliminate the existential quantifier, obtaining the ordinal `o` + +D[n-cov-min-3] +What is left is almost right, but the element `b` is already in the +context. We thus generalize every occurrence of `b` in +the current goal, obtaining `âc.c â Uâ½o â c â V` that is `Uâ½o â V`. + +D[n-cov-min-4] +We then proceed by induction on `o` obtaining the following goals + +D[n-cov-min-5] +All of them can be proved using simple set theoretic arguments, +the induction hypothesis and the assumption `Im`. + +D*) + + +(*D + +bla bla + +D*) + +nlet rec famF (A: nAx) (F : Ω^A) (x : Ord A) on x : Ω^A â + match x with + [ oO â F + | oS o â let Fo â famF A F o in Fo â© { x | âi:ð x.âj:ð x i.ð x i j â Fo } + | oL a i f â { x | âj:ð a i.x â famF A F (f j) } + ]. + +interpretation "famF" 'famU U x = (famF ? U x). + +ndefinition ord_fished : âA:nAx.âF:Ω^A.Ω^A â λA,F.{ y | âx:Ord A. y â Fâ½x }. + +interpretation "fished new fish" 'fished U = (ord_fished ? U). +interpretation "new fish" 'fish a U = (mem ? (ord_fished ? U) a). + +(*D + +The proof of compatibility uses this little result, that we +factored out. + +D*) +nlemma co_ord_subset: + âA:nAx.âF:Ω^A.âa,i.âf:ð a i â Ord A.âj. Fâ½(Î f) â Fâ½(f j). +#A; #F; #a; #i; #f; #j; #x; #H; napply H; +nqed. + +(*D + +We assume the dual of the axiom of choice, as in the paper proof. + +D*) +naxiom AC_dual : + âA:nAx.âa:A.âi,F. (âf:ð a i â Ord A.âx:ð a i.ð a i x â Fâ½(f x)) â âj:ð a i.âx:Ord A.ð a i j â Fâ½x. + +(*D + +Proving the anti-reflexivity property is simce, since the +assumption `a â F` states that for every ordinal `x` (and thus also 0) +`a â Fâ½x`. If `x` is choosen to be `0`, we obtain the thesis. + +D*) +ntheorem new_fish_antirefl: + âA:nAx.âF:Ω^A.âa. a â F â a â F. +#A; #F; #a; #H; nlapply (H 0); #aFo; napply aFo; +nqed. + +(*D + +bar + +D*) +ntheorem new_fish_compatible: + âA:nAx.âF:Ω^A.âa. a â F â âi:ð a.âj:ð a i.ð a i j â F. +#A; #F; #a; #aF; #i; nnormalize; (** screenshot "n-f-compat-1". *) +napply AC_dual; #f; (** screenshot "n-f-compat-2". *) +nlapply (aF (Îf+1)); #aLf; (** screenshot "n-f-compat-3". *) +nchange in aLf with + (a â Fâ½(Î f) ⧠âi:ð a.âj:ð a i.ð a i j â Fâ½(Î f)); (** screenshot "n-f-compat-4". *) +ncut (âj:ð a i.ð a i j â Fâ½(f j));##[ + ncases aLf; #_; #H; nlapply (H i); (** screenshot "n-f-compat-5". *) + *; #j; #Hj; @j; napply Hj;##] #aLf'; (** screenshot "n-f-compat-6". *) +napply aLf'; +nqed. + +(*D +D[n-f-compat-1] +D[n-f-compat-2] +D[n-f-compat-3] +D[n-f-compat-4] +D[n-f-compat-5] +D[n-f-compat-6] + +D*) + +(*D + +The proof that `â(F)` is maximal is exactly the dual one of the +minimality of `â(U)`. Thus the main problem is to obtain `G â Fâ½o` +before doing the induction over `o`. + +D*) +ntheorem max_new_fished: + âA:nAx.âG:ext_powerclass_setoid A.âF:Ω^A.G â F â (âa.a â G â âi.ðð¦[ð a i] ⬠G) â G â âF. +#A; #G; #F; #GF; #H; #b; #HbG; #o; +ngeneralize in match HbG; ngeneralize in match b; +nchange with (G â Fâ½o); +nelim o; +##[ napply GF; +##| #p; #IH; napply (subseteq_intersection_r ⦠IH); + #x; #Hx; #i; ncases (H ⦠Hx i); #c; *; *; #d; #Ed; #cG; + @d; napply IH; + napply (. Ed^-1â¡#); napply cG; +##| #a; #i; #f; #Hf; nchange with (G â { y | âx. y â Fâ½(f x) }); + #b; #Hb; #d; napply (Hf d); napply Hb; +##] +nqed. + + +(*D +
+Appendix: tactics explanation +----------------------------- + +In this appendix we try to give a description of tactics +in terms of sequent calculus rules annotated with proofs. +The `:` separator has to be read as _is a proof of_, in the spirit +of the Curry-Howard isomorphism. + + Π⢠f : A1 â ⦠â An â B Π⢠?1 : A1 ⦠?n : An + napply f; â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼ + Π⢠(f ?1 ⦠?n ) : B + + Π⢠? : F â B Π⢠f : F + nlapply f; â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼ + Π⢠(? f) : B + + + Î; x : T ⢠? : P(x) + #x; â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼ + Π⢠λx:T.? : âx:T.P(x) + + + Π⢠?_i : args_i â P(k_i args_i) + ncases x; â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼ + Π⢠match x with [ k1 args1 â ?_1 | ⦠| kn argsn â ?_n ] : P(x) + + + Π⢠?i : ât. P(t) â P(k_i ⦠t â¦) + nelim x; â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼ + Π⢠(T_rect_CProp0 ?_1 ⦠?_n) : P(x) -theorem coreflexivity: âA:axiom_set.âa:A.âV. a â V â a â V. - intros; - cases H; - assumption. -qed. +Where `T_rect_CProp0` is the induction principle for the +inductive type `T`. -theorem cotransitivity: - âA:axiom_set.âa:A.âU,V. a â U â (âb:A. b â U â b â V) â a â V. - intros; - apply (fish_rec ?? {a|a â U} ??? H); simplify; intros; - [ apply H1; apply H2; - | cases H2 in j; clear H2; intro i; - cases (H4 i); clear H4; exists[apply a3] assumption] -qed. + Π⢠? : Q Q â¡ P + nchange with Q; â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼ + Π⢠? : P -theorem compatibility: âA:axiom_set.âa:A.âU,V. a â V â a â U â U â V. - intros; - generalize in match H; clear H; - apply (covers_elim ?? {a|a â V â U â V} ??? H1); - clear H1; simplify; intros; - [ exists [apply x] assumption - | cases H2 in j H H1; clear H2 a1; intros; - cases (H1 i); clear H1; apply (H3 a1); assumption] -qed. +Where the equivalence relation between types `â¡` keeps into account +β-reduction, δ-reduction (definition unfolding), ζ-reduction (local +definition unfolding), ι-reduction (pattern matching simplification), +μ-reduction (recursive function computation) and ν-reduction (co-fixpoint +computation). -definition leq â λA:axiom_set.λa,b:A. a â {y|b=y}. -interpretation "covered by one" 'leq a b = (leq ? a b). + Î; H : Q; Π⢠? : G Q â¡ P + nchange in H with Q; â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼ + Î; H : P; Π⢠? : G -theorem leq_refl: âA:axiom_set.âa:A. a ⤠a. - intros; - apply refl; - normalize; - reflexivity. -qed. -theorem leq_trans: âA:axiom_set.âa,b,c:A. a ⤠b â b ⤠c â a ⤠c. - intros; - unfold in H H1 ⢠%; - apply (transitivity ???? H); - constructor 1; - intros; - normalize in H2; - rewrite < H2; - assumption. -qed. -definition uparrow â λA:axiom_set.λa:A.mk_powerset ? (λb:A. a ⤠b). + Π⢠?_2 : T â G Π⢠?_1 : T + ncut T; â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼ + Π⢠(?_2 ?_1) : G -interpretation "uparrow" 'uparrow a = (uparrow ? a). -definition downarrow â λA:axiom_set.λU:Ω \sup A.mk_powerset ? (λa:A. (âa) ⬠U). + Π⢠? : âx.P(x) + ngeneralize in match t; â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼â¼ + Π⢠(? t) : P(t) + +D*) -interpretation "downarrow" 'downarrow a = (downarrow ? a). -definition fintersects â λA:axiom_set.λU,V:Ω \sup A.âU â© âV. +(*D -interpretation "fintersects" 'fintersects U V = (fintersects ? U V). +[1]: http://upsilon.cc/~zack/research/publications/notation.pdf -record convergent_generated_topology : Type â - { AA:> axiom_set; - convergence: âa:AA.âU,V:Ω \sup AA. a â U â a â V â a â (U â V) - }. +D*)