:: Filters - Part I. Implicative Lattices :: by Grzegorz Bancerek :: :: Received July 3, 1990 :: Copyright (c) 1990-2018 Association of Mizar Users :: (Stowarzyszenie Uzytkownikow Mizara, Bialystok, Poland). :: This code can be distributed under the GNU General Public Licence :: version 3.0 or later, or the Creative Commons Attribution-ShareAlike :: License version 3.0 or later, subject to the binding interpretation :: detailed in file COPYING.interpretation. :: See COPYING.GPL and COPYING.CC-BY-SA for the full text of these :: licenses, or see http://www.gnu.org/licenses/gpl.html and :: http://creativecommons.org/licenses/by-sa/3.0/. environ vocabularies LATTICES, SUBSET_1, XBOOLE_0, PBOOLE, EQREL_1, CARD_FIL, STRUCT_0, TARSKI, ORDINAL1, ZFMISC_1, SETFAM_1, INT_2, XBOOLEAN, BINOP_1, REALSET1, FUNCT_1, RELAT_1, MCART_1, XXREAL_2, RELAT_2, FILTER_0; notations TARSKI, XBOOLE_0, ZFMISC_1, SUBSET_1, SETFAM_1, FUNCT_1, XTUPLE_0, MCART_1, ORDINAL1, RELAT_2, FUNCT_2, BINOP_1, REALSET1, STRUCT_0, LATTICES, DOMAIN_1, RELAT_1, RELSET_1, EQREL_1; constructors SETFAM_1, RELAT_2, ORDINAL1, PARTFUN1, BINOP_1, REALSET1, LATTICES, RELSET_1, XTUPLE_0; registrations XBOOLE_0, SUBSET_1, RELSET_1, STRUCT_0, LATTICES; requirements SUBSET, BOOLE; begin reserve L for Lattice, p,p1,q,q1,r,r1 for Element of L; reserve x,y,z,X,Y,Z,X1,X2 for set; theorem :: FILTER_0:1 for L being join-associative join-commutative meet-commutative join-absorbing meet-absorbing non empty LattStr, p, q, r being Element of L st p [= q holds r "\/" p [= r "\/" q; theorem :: FILTER_0:2 p [= r implies p "/\" q [= r; theorem :: FILTER_0:3 p [= r implies p [= q"\/"r; theorem :: FILTER_0:4 for L being join-absorbing join-commutative join-associative non empty LattStr, a, b, c, d being Element of L st a [= b & c [= d holds a "\/" c [= b "\/" d; theorem :: FILTER_0:5 for L being meet-absorbing meet-commutative join-absorbing meet-associative non empty LattStr, a, b, c, d being Element of L st a [= b & c [= d holds a "/\" c [= b "/\" d; theorem :: FILTER_0:6 for L being join-absorbing join-commutative join-associative meet-absorbing meet-commutative non empty LattStr, a, b, c being Element of L st a [= c & b [= c holds a "\/" b [= c; theorem :: FILTER_0:7 for L being meet-absorbing meet-commutative join-absorbing meet-associative non empty LattStr, a, b, c being Element of L st a [= b & a [= c holds a [= b "/\" c; definition let L; mode Filter of L is non empty meet-closed final Subset of L; end; theorem :: FILTER_0:8 for S being non empty Subset of L holds S is Filter of L iff for p,q being Element of L holds p in S & q in S iff p "/\" q in S; theorem :: FILTER_0:9 for D being non empty Subset of L holds D is Filter of L iff (for p,q st p in D & q in D holds p "/\" q in D) & for p,q st p in D & p [= q holds q in D; reserve H,F for Filter of L; theorem :: FILTER_0:10 p in H implies p"\/"q in H & q"\/"p in H; theorem :: FILTER_0:11 L is 1_Lattice implies Top L in H; theorem :: FILTER_0:12 L is 1_Lattice implies {Top L} is Filter of L; theorem :: FILTER_0:13 {p} is Filter of L implies L is upper-bounded; theorem :: FILTER_0:14 the carrier of L is Filter of L; definition let L; func <.L.) -> Filter of L equals :: FILTER_0:def 1 the carrier of L; end; definition let L,p; func <.p.) -> Filter of L equals :: FILTER_0:def 2 { q : p [= q }; end; theorem :: FILTER_0:15 q in <.p.) iff p [= q; theorem :: FILTER_0:16 p in <.p.) & p "\/" q in <.p.) & q "\/" p in <.p.); theorem :: FILTER_0:17 L is 0_Lattice implies <.L.) = <.Bottom L.); definition let L,F; attr F is being_ultrafilter means :: FILTER_0:def 3 F <> the carrier of L & for H st F c= H & H <> the carrier of L holds F = H; end; theorem :: FILTER_0:18 L is lower-bounded implies for F st F <> the carrier of L ex H st F c= H & H is being_ultrafilter; theorem :: FILTER_0:19 (ex r st p "/\" r <> p) implies <.p.) <> the carrier of L; theorem :: FILTER_0:20 L is 0_Lattice & p <> Bottom L implies ex H st p in H & H is being_ultrafilter; reserve D for non empty Subset of L; definition let L,D; func <.D.) -> Filter of L means :: FILTER_0:def 4 D c= it & for F st D c= F holds it c= F; end; theorem :: FILTER_0:21 <.F.) = F; reserve D1,D2 for non empty Subset of L; theorem :: FILTER_0:22 D1 c= D2 implies <.D1.) c= <.D2.); theorem :: FILTER_0:23 p in D implies <.p.) c= <.D.); theorem :: FILTER_0:24 D = {p} implies <.D.) = <.p.); theorem :: FILTER_0:25 L is 0_Lattice & Bottom L in D implies <.D.) = <.L.) & <.D.) = the carrier of L; theorem :: FILTER_0:26 L is 0_Lattice & Bottom L in F implies F = <.L.) & F = the carrier of L; definition let L,F; attr F is prime means :: FILTER_0:def 5 p "\/" q in F iff p in F or q in F; end; theorem :: FILTER_0:27 L is B_Lattice implies for p,q holds p "/\" (p` "\/" q) [= q & for r st p "/\" r [= q holds r [= p` "\/" q; definition let IT be non empty LattStr; attr IT is implicative means :: FILTER_0:def 6 for p,q being Element of IT ex r being Element of IT st p "/\" r [= q & for r1 being Element of IT st p "/\" r1 [= q holds r1 [= r; end; registration cluster strict implicative for Lattice; end; definition mode I_Lattice is implicative Lattice; end; definition let L,p,q; assume L is I_Lattice; func p => q -> Element of L means :: FILTER_0:def 7 p "/\" it [= q & for r st p "/\" r [= q holds r [= it; end; reserve I for I_Lattice, i,j,k for Element of I; registration cluster -> upper-bounded for I_Lattice; end; theorem :: FILTER_0:28 i => i = Top I; registration cluster -> distributive for I_Lattice; end; reserve B for B_Lattice, FB,HB for Filter of B; registration cluster -> implicative for B_Lattice; end; registration cluster implicative -> distributive for Lattice; end; reserve I for I_Lattice, i,j,k for Element of I, DI for non empty Subset of I, FI for Filter of I; theorem :: FILTER_0:29 i in FI & i => j in FI implies j in FI; theorem :: FILTER_0:30 j in FI implies i => j in FI; definition let L,D1,D2; func D1 "/\" D2 -> Subset of L equals :: FILTER_0:def 8 { p"/\"q : p in D1 & q in D2 }; end; registration let L,D1,D2; cluster D1 "/\" D2 -> non empty; end; theorem :: FILTER_0:31 p in D1 & q in D2 implies p"/\"q in D1 "/\" D2 & q"/\"p in D1 "/\" D2; theorem :: FILTER_0:32 x in D1 "/\" D2 implies ex p,q st x = p"/\"q & p in D1 & q in D2; theorem :: FILTER_0:33 D1 "/\" D2 = D2 "/\" D1; registration let L be D_Lattice; let F1,F2 be Filter of L; cluster F1 "/\" F2 -> final meet-closed; end; theorem :: FILTER_0:34 <.D1 \/ D2.) = <.<.D1.) \/ D2.) & <.D1 \/ D2.) = <.D1 \/ <.D2.) .); theorem :: FILTER_0:35 <.F \/ H.) = { r : ex p,q st p"/\"q [= r & p in F & q in H }; theorem :: FILTER_0:36 F c= F "/\" H & H c= F "/\" H; theorem :: FILTER_0:37 <.F \/ H.) = <.F "/\" H.); reserve F1,F2 for Filter of I; theorem :: FILTER_0:38 <.F1 \/ F2.) = F1 "/\" F2; theorem :: FILTER_0:39 <.FB \/ HB.) = FB "/\" HB; theorem :: FILTER_0:40 j in <.DI \/ {i}.) implies i => j in <.DI.); theorem :: FILTER_0:41 i => j in FI & j => k in FI implies i => k in FI; reserve a,b,c for Element of B; theorem :: FILTER_0:42 a => b = a` "\/" b; theorem :: FILTER_0:43 a [= b iff a"/\"b` = Bottom B; theorem :: FILTER_0:44 FB is being_ultrafilter iff FB <> the carrier of B & for a holds a in FB or a` in FB; theorem :: FILTER_0:45 FB <> <.B.) & FB is prime iff FB is being_ultrafilter; theorem :: FILTER_0:46 FB is being_ultrafilter implies for a holds a in FB iff not a` in FB; theorem :: FILTER_0:47 a <> b implies ex FB st FB is being_ultrafilter & (a in FB & not b in FB or not a in FB & b in FB); reserve o1,o2 for BinOp of F; definition let L,F; func latt F -> Lattice means :: FILTER_0:def 9 ex o1,o2 st o1 = (the L_join of L)||F & o2 = (the L_meet of L)||F & it = LattStr (#F, o1, o2#); end; registration let L,F; cluster latt F -> strict; end; theorem :: FILTER_0:48 for L being strict Lattice holds latt <.L.) = L; theorem :: FILTER_0:49 the carrier of latt F = F & the L_join of latt F = (the L_join of L)||F & the L_meet of latt F = (the L_meet of L)||F; theorem :: FILTER_0:50 for p9,q9 being Element of latt F st p = p9 & q = q9 holds p"\/" q = p9"\/"q9 & p"/\"q = p9"/\"q9; theorem :: FILTER_0:51 for p9,q9 being Element of latt F st p = p9 & q = q9 holds p [= q iff p9 [= q9; theorem :: FILTER_0:52 L is upper-bounded implies latt F is upper-bounded; theorem :: FILTER_0:53 L is modular implies latt F is modular; theorem :: FILTER_0:54 L is distributive implies latt F is distributive; theorem :: FILTER_0:55 L is I_Lattice implies latt F is implicative; registration let L,p; cluster latt <.p.) -> lower-bounded; end; theorem :: FILTER_0:56 Bottom latt <.p.) = p; theorem :: FILTER_0:57 L is upper-bounded implies Top latt <.p.) = Top L; theorem :: FILTER_0:58 L is 1_Lattice implies latt <.p.) is bounded; theorem :: FILTER_0:59 L is C_Lattice & L is M_Lattice implies latt <.p.) is C_Lattice; theorem :: FILTER_0:60 L is B_Lattice implies latt <.p.) is B_Lattice; definition let L,p,q; func p <=> q -> Element of L equals :: FILTER_0:def 10 (p => q)"/\"(q => p); end; theorem :: FILTER_0:61 p <=> q = q <=> p; theorem :: FILTER_0:62 i <=> j in FI & j <=> k in FI implies i <=> k in FI; definition let L,F; func equivalence_wrt F -> Relation means :: FILTER_0:def 11 field it c= the carrier of L & for p,q holds [p,q] in it iff p <=> q in F; end; theorem :: FILTER_0:63 equivalence_wrt F is Relation of the carrier of L; theorem :: FILTER_0:64 L is I_Lattice implies equivalence_wrt F is_reflexive_in the carrier of L; theorem :: FILTER_0:65 equivalence_wrt F is_symmetric_in the carrier of L; theorem :: FILTER_0:66 L is I_Lattice implies equivalence_wrt F is_transitive_in the carrier of L; theorem :: FILTER_0:67 L is I_Lattice implies equivalence_wrt F is Equivalence_Relation of the carrier of L; theorem :: FILTER_0:68 L is I_Lattice implies field equivalence_wrt F = the carrier of L; definition let I,FI; redefine func equivalence_wrt FI -> Equivalence_Relation of the carrier of I; end; definition let B,FB; redefine func equivalence_wrt FB -> Equivalence_Relation of the carrier of B; end; definition let L,F,p,q; pred p,q are_equivalence_wrt F means :: FILTER_0:def 12 p <=> q in F; end; theorem :: FILTER_0:69 p,q are_equivalence_wrt F iff [p,q] in equivalence_wrt F; theorem :: FILTER_0:70 i,i are_equivalence_wrt FI & a,a are_equivalence_wrt FB; theorem :: FILTER_0:71 p,q are_equivalence_wrt F implies q,p are_equivalence_wrt F; theorem :: FILTER_0:72 (i,j are_equivalence_wrt FI & j,k are_equivalence_wrt FI implies i,k are_equivalence_wrt FI) & (a,b are_equivalence_wrt FB & b,c are_equivalence_wrt FB implies a,c are_equivalence_wrt FB); begin :: Addenda :: missing, 2006.12.05, AT theorem :: FILTER_0:73 for L being meet-absorbing meet-commutative meet-associative join-absorbing join-commutative non empty LattStr for x,y,z being Element of L st z [= x & z [= y & for z9 being Element of L st z9 [= x & z9 [= y holds z9 [= z holds z = x "/\" y; theorem :: FILTER_0:74 for L being meet-absorbing meet-commutative join-associative join-absorbing join-commutative non empty LattStr for x,y,z being Element of L st x [= z & y [= z & for z9 being Element of L st x [= z9 & y [= z9 holds z [= z9 holds z = x "\/" y;