FILTER_0: Filters - Part I. Implicative Lattices

:: Filters - Part I. Implicative Lattices
:: by Grzegorz Bancerek
::
:: Received July 3, 1990
:: Copyright (c) 1990 Association of Mizar Users

begin

theorem Th1: :: FILTER_0:1

for L being non empty join-commutative join-associative meet-commutative meet-absorbing join-absorbing LattStr
for p, q, r being Element of L st p [= q holds
r "\/" p [= r "\/" q

proof end;

theorem :: FILTER_0:2

for L being Lattice
for p, r, q being Element of L st p [= r holds
p "/\" q [= r

proof end;

theorem :: FILTER_0:3

for L being Lattice
for p, r, q being Element of L st p [= r holds
p [= q "\/" r

proof end;

theorem Th4: :: FILTER_0:4

for L being non empty join-commutative join-associative join-absorbing LattStr
for a, b, c, d being Element of L st a [= b & c [= d holds
a "\/" c [= b "\/" d

proof end;

theorem Th5: :: FILTER_0:5

for L being non empty meet-commutative meet-associative meet-absorbing join-absorbing LattStr
for a, b, c, d being Element of L st a [= b & c [= d holds
a "/\" c [= b "/\" d

proof end;

theorem Th6: :: FILTER_0:6

for L being non empty join-commutative join-associative meet-commutative meet-absorbing join-absorbing LattStr
for a, b, c being Element of L st a [= c & b [= c holds
a "\/" b [= c

proof end;

theorem Th7: :: FILTER_0:7

for L being non empty meet-commutative meet-associative meet-absorbing join-absorbing LattStr
for a, b, c being Element of L st a [= b & a [= c holds
a [= b "/\" c

proof end;

definition

let L be Lattice;
canceled;
mode Filter of L is non empty final meet-closed Subset of L;

end;

:: deftheorem FILTER_0:def 1 :

theorem Th8: :: FILTER_0:8

for L being Lattice
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 ) )

proof end;

theorem Th9: :: FILTER_0:9

for L being Lattice
for D being non empty Subset of L holds
( D is Filter of L iff ( ( for p, q being Element of L st p in D & q in D holds
p "/\" q in D ) & ( for p, q being Element of L st p in D & p [= q holds
q in D ) ) )

proof end;

theorem Th10: :: FILTER_0:10

for L being Lattice
for p, q being Element of L
for H being Filter of L st p in H holds
( p "\/" q in H & q "\/" p in H )

proof end;

theorem :: FILTER_0:11

canceled;

theorem Th12: :: FILTER_0:12

for L being Lattice
for H being Filter of L st L is 1_Lattice holds
Top L in H

proof end;

theorem :: FILTER_0:13

for L being Lattice st L is 1_Lattice holds
{(Top L)} is Filter of L

proof end;

theorem :: FILTER_0:14

for L being Lattice
for p being Element of L st {p} is Filter of L holds
L is upper-bounded

proof end;

theorem Th15: :: FILTER_0:15

for L being Lattice holds the carrier of L is Filter of L

proof end;

definition

let L be Lattice;
func <.L.) -> Filter of L equals :: FILTER_0:def 2
the carrier of L;
coherence by Th15;

end;

:: deftheorem defines <. FILTER_0:def 2 :

definition

let L be Lattice;
let p be Element of L;
func <.p.) -> Filter of L equals :: FILTER_0:def 3
{ q where q is Element of L : p [= q } ;
coherence

proof end;

end;

:: deftheorem defines <. FILTER_0:def 3 :

theorem :: FILTER_0:16

canceled;

theorem :: FILTER_0:17

canceled;

theorem Th18: :: FILTER_0:18

for L being Lattice
for q, p being Element of L holds
( q in <.p.) iff p [= q )

proof end;

theorem Th19: :: FILTER_0:19

for L being Lattice
for p, q being Element of L holds
( p in <.p.) & p "\/" q in <.p.) & q "\/" p in <.p.) )

proof end;

theorem Th20: :: FILTER_0:20

for L being Lattice st L is 0_Lattice holds
<.L.) = <.(Bottom L).)

proof end;

definition

let L be Lattice;
let F be Filter of L;
attr F is being_ultrafilter means :Def4: :: FILTER_0:def 4
( F <> the carrier of L & ( for H being Filter of L st F c= H & H <> the carrier of L holds
F = H ) );

end;

:: deftheorem Def4 defines being_ultrafilter FILTER_0:def 4 :

theorem :: FILTER_0:21

canceled;

theorem Th22: :: FILTER_0:22

for L being Lattice st L is lower-bounded holds
for F being Filter of L st F <> the carrier of L holds
ex H being Filter of L st
( F c= H & H is being_ultrafilter )

proof end;

theorem Th23: :: FILTER_0:23

for L being Lattice
for p being Element of L st ex r being Element of L st p "/\" r <> p holds
<.p.) <> the carrier of L

proof end;

theorem Th24: :: FILTER_0:24

for L being Lattice
for p being Element of L st L is 0_Lattice & p <> Bottom L holds
ex H being Filter of L st
( p in H & H is being_ultrafilter )

proof end;

definition

let L be Lattice;
let D be non empty Subset of L;
func <.D.) -> Filter of L means :Def5: :: FILTER_0:def 5
( D c= it & ( for F being Filter of L st D c= F holds
it c= F ) );
existence

proof end;

uniqueness

proof end;

end;

:: deftheorem Def5 defines <. FILTER_0:def 5 :

theorem :: FILTER_0:25

canceled;

theorem Th26: :: FILTER_0:26

for L being Lattice
for F being Filter of L holds <.F.) = F

proof end;

theorem Th27: :: FILTER_0:27

for L being Lattice
for D1, D2 being non empty Subset of L st D1 c= D2 holds
<.D1.) c= <.D2.)

proof end;

theorem :: FILTER_0:28

canceled;

theorem Th29: :: FILTER_0:29

for L being Lattice
for p being Element of L
for D being non empty Subset of L st p in D holds
<.p.) c= <.D.)

proof end;

theorem Th30: :: FILTER_0:30

for L being Lattice
for p being Element of L
for D being non empty Subset of L st D = {p} holds
<.D.) = <.p.)

proof end;

theorem Th31: :: FILTER_0:31

for L being Lattice
for D being non empty Subset of L st L is 0_Lattice & Bottom L in D holds
( <.D.) = <.L.) & <.D.) = the carrier of L )

proof end;

theorem Th32: :: FILTER_0:32

for L being Lattice
for F being Filter of L st L is 0_Lattice & Bottom L in F holds
( F = <.L.) & F = the carrier of L )

proof end;

definition

let L be Lattice;
let F be Filter of L;
attr F is prime means :: FILTER_0:def 6
for p, q being Element of L holds
( p "\/" q in F iff ( p in F or q in F ) );

end;

:: deftheorem defines prime FILTER_0:def 6 :

theorem :: FILTER_0:33

canceled;

theorem Th34: :: FILTER_0:34

for L being Lattice st L is B_Lattice holds
for p, q being Element of L holds
( p "/\" ((p `) "\/" q) [= q & ( for r being Element of L st p "/\" r [= q holds
r [= (p `) "\/" q ) )

proof end;

definition

let IT be non empty LattStr ;
attr IT is implicative means :Def7: :: FILTER_0:def 7
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;

:: deftheorem Def7 defines implicative FILTER_0:def 7 :

registration

cluster non empty strict join-commutative join-associative meet-commutative meet-associative meet-absorbing join-absorbing Lattice-like implicative LattStr ;
existence

proof end;

end;

definition

mode I_Lattice is implicative Lattice;

end;

definition

let L be Lattice;
let p, q be Element of L;
assume A1: L is I_Lattice ;
func p => q -> Element of L means :Def8: :: FILTER_0:def 8
( p "/\" it [= q & ( for r being Element of L st p "/\" r [= q holds
r [= it ) );
existence by A1, Def7;
correctness

proof end;

end;

:: deftheorem Def8 defines => FILTER_0:def 8 :

theorem :: FILTER_0:35

canceled;

theorem :: FILTER_0:36

canceled;

theorem :: FILTER_0:37

canceled;

registration

cluster non empty Lattice-like implicative -> upper-bounded LattStr ;
coherence

proof end;

end;

theorem Th38: :: FILTER_0:38

for I being I_Lattice
for i being Element of I holds i => i = Top I

proof end;

theorem :: FILTER_0:39

canceled;

registration

cluster non empty Lattice-like implicative -> distributive LattStr ;
coherence

proof end;

end;

theorem :: FILTER_0:40

canceled;

registration

cluster non empty Lattice-like Boolean -> implicative LattStr ;
coherence

proof end;

end;

registration

cluster non empty Lattice-like implicative -> distributive LattStr ;
coherence ;

end;

theorem Th41: :: FILTER_0:41

for I being I_Lattice
for i, j being Element of I
for FI being Filter of I st i in FI & i => j in FI holds
j in FI

proof end;

theorem Th42: :: FILTER_0:42

for I being I_Lattice
for j, i being Element of I
for FI being Filter of I st j in FI holds
i => j in FI

proof end;

definition

let L be Lattice;
let D1, D2 be non empty Subset of L;
func D1 "/\" D2 -> Subset of L equals :: FILTER_0:def 9
{ (p "/\" q) where p, q is Element of L : ( p in D1 & q in D2 ) } ;
coherence

proof end;

end;

:: deftheorem defines "/\" FILTER_0:def 9 :

registration

let L be Lattice;
let D1, D2 be non empty Subset of L;
cluster D1 "/\" D2 -> non empty ;
coherence

proof end;

end;

theorem :: FILTER_0:43

canceled;

theorem :: FILTER_0:44

for L being Lattice
for p, q being Element of L
for D1, D2 being non empty Subset of L st p in D1 & q in D2 holds
( p "/\" q in D1 "/\" D2 & q "/\" p in D1 "/\" D2 ) ;

theorem :: FILTER_0:45

for L being Lattice
for x being set
for D1, D2 being non empty Subset of L st x in D1 "/\" D2 holds
ex p, q being Element of L st
( x = p "/\" q & p in D1 & q in D2 ) ;

theorem Th46: :: FILTER_0:46

for L being Lattice
for D1, D2 being non empty Subset of L holds D1 "/\" D2 = D2 "/\" D1

proof end;

registration

let L be D_Lattice;
let F1, F2 be Filter of L;
cluster F1 "/\" F2 -> final meet-closed ;
coherence

proof end;

end;

theorem Th47: :: FILTER_0:47

for L being Lattice
for D1, D2 being non empty Subset of L holds
( <.(D1 \/ D2).) = <.(<.D1.) \/ D2).) & <.(D1 \/ D2).) = <.(D1 \/ <.D2.)).) )

proof end;

theorem :: FILTER_0:48

for L being Lattice
for F, H being Filter of L holds <.(F \/ H).) = { r where r is Element of L : ex p, q being Element of L st
( p "/\" q [= r & p in F & q in H ) }

proof end;

theorem Th49: :: FILTER_0:49

for L being Lattice
for F, H being Filter of L holds
( F c= F "/\" H & H c= F "/\" H )

proof end;

theorem Th50: :: FILTER_0:50

for L being Lattice
for F, H being Filter of L holds <.(F \/ H).) = <.(F "/\" H).)

proof end;

theorem Th51: :: FILTER_0:51

for I being I_Lattice
for F1, F2 being Filter of I holds <.(F1 \/ F2).) = F1 "/\" F2

proof end;

theorem :: FILTER_0:52

for B being B_Lattice
for FB, HB being Filter of B holds <.(FB \/ HB).) = FB "/\" HB

proof end;

theorem Th53: :: FILTER_0:53

for I being I_Lattice
for j, i being Element of I
for DI being non empty Subset of I st j in <.(DI \/ {i}).) holds
i => j in <.DI.)

proof end;

theorem Th54: :: FILTER_0:54

for I being I_Lattice
for i, j, k being Element of I
for FI being Filter of I st i => j in FI & j => k in FI holds
i => k in FI

proof end;

theorem Th55: :: FILTER_0:55

for B being B_Lattice
for a, b being Element of B holds a => b = (a `) "\/" b

proof end;

theorem Th56: :: FILTER_0:56

for B being B_Lattice
for a, b being Element of B holds
( a [= b iff a "/\" (b `) = Bottom B )

proof end;

theorem Th57: :: FILTER_0:57

for B being B_Lattice
for FB being Filter of B holds
( FB is being_ultrafilter iff ( FB <> the carrier of B & ( for a being Element of B holds
( a in FB or a ` in FB ) ) ) )

proof end;

theorem :: FILTER_0:58

for B being B_Lattice
for FB being Filter of B holds
( ( FB <> <.B.) & FB is prime ) iff FB is being_ultrafilter )

proof end;

theorem Th59: :: FILTER_0:59

for B being B_Lattice
for FB being Filter of B st FB is being_ultrafilter holds
for a being Element of B holds
( a in FB iff not a ` in FB )

proof end;

theorem :: FILTER_0:60

for B being B_Lattice
for a, b being Element of B st a <> b holds
ex FB being Filter of B st
( FB is being_ultrafilter & ( ( a in FB & not b in FB ) or ( not a in FB & b in FB ) ) )

proof end;

definition

let L be Lattice;
let F be Filter of L;
func latt F -> Lattice means :Def10: :: FILTER_0:def 10
ex o1, o2 being BinOp of F st
( o1 = the L_join of L || F & o2 = the L_meet of L || F & it = LattStr(# F,o1,o2 #) );
uniqueness ;
existence

proof end;

end;

:: deftheorem Def10 defines latt FILTER_0:def 10 :

registration

let L be Lattice;
let F be Filter of L;
cluster latt F -> strict ;
coherence

proof end;

end;

theorem :: FILTER_0:61

canceled;

theorem :: FILTER_0:62

for L being strict Lattice holds latt <.L.) = L

proof end;

theorem Th63: :: FILTER_0:63

for L being Lattice
for F being Filter of L holds
( 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 )

proof end;

theorem Th64: :: FILTER_0:64

for L being Lattice
for p, q being Element of L
for F being Filter of L
for p9, q9 being Element of (latt F) st p = p9 & q = q9 holds
( p "\/" q = p9 "\/" q9 & p "/\" q = p9 "/\" q9 )

proof end;

theorem Th65: :: FILTER_0:65

for L being Lattice
for p, q being Element of L
for F being Filter of L
for p9, q9 being Element of (latt F) st p = p9 & q = q9 holds
( p [= q iff p9 [= q9 )

proof end;

theorem Th66: :: FILTER_0:66

for L being Lattice
for F being Filter of L st L is upper-bounded holds
latt F is upper-bounded

proof end;

theorem :: FILTER_0:67

for L being Lattice
for F being Filter of L st L is modular holds
latt F is modular

proof end;

theorem Th68: :: FILTER_0:68

for L being Lattice
for F being Filter of L st L is distributive holds
latt F is distributive

proof end;

theorem :: FILTER_0:69

for L being Lattice
for F being Filter of L st L is I_Lattice holds
latt F is implicative

proof end;

theorem :: FILTER_0:70

canceled;

registration

let L be Lattice;
let p be Element of L;
cluster latt <.p.) -> lower-bounded ;
coherence

proof end;

end;

theorem Th71: :: FILTER_0:71

for L being Lattice
for p being Element of L holds Bottom (latt <.p.)) = p

proof end;

theorem Th72: :: FILTER_0:72

for L being Lattice
for p being Element of L st L is upper-bounded holds
Top (latt <.p.)) = Top L

proof end;

theorem Th73: :: FILTER_0:73

for L being Lattice
for p being Element of L st L is 1_Lattice holds
latt <.p.) is bounded

proof end;

theorem Th74: :: FILTER_0:74

for L being Lattice
for p being Element of L st L is C_Lattice & L is M_Lattice holds
latt <.p.) is C_Lattice

proof end;

theorem :: FILTER_0:75

for L being Lattice
for p being Element of L st L is B_Lattice holds
latt <.p.) is B_Lattice

proof end;

definition

let L be Lattice;
let p, q be Element of L;
func p <=> q -> Element of L equals :: FILTER_0:def 11
(p => q) "/\" (q => p);
correctness ;

end;

:: deftheorem defines <=> FILTER_0:def 11 :

theorem :: FILTER_0:76

canceled;

theorem :: FILTER_0:77

for L being Lattice
for p, q being Element of L holds p <=> q = q <=> p ;

theorem Th78: :: FILTER_0:78

for I being I_Lattice
for i, j, k being Element of I
for FI being Filter of I st i <=> j in FI & j <=> k in FI holds
i <=> k in FI

proof end;

definition

let L be Lattice;
let F be Filter of L;
func equivalence_wrt F -> Relation means :Def12: :: FILTER_0:def 12
( field it c= the carrier of L & ( for p, q being Element of L holds
( [p,q] in it iff p <=> q in F ) ) );
existence

proof end;

uniqueness

proof end;

end;

:: deftheorem Def12 defines equivalence_wrt FILTER_0:def 12 :

theorem :: FILTER_0:79

canceled;

theorem Th80: :: FILTER_0:80

for L being Lattice
for F being Filter of L holds equivalence_wrt F is Relation of the carrier of L

proof end;

theorem Th81: :: FILTER_0:81

for L being Lattice
for F being Filter of L st L is I_Lattice holds
equivalence_wrt F is_reflexive_in the carrier of L

proof end;

theorem Th82: :: FILTER_0:82

for L being Lattice
for F being Filter of L holds equivalence_wrt F is_symmetric_in the carrier of L

proof end;

theorem Th83: :: FILTER_0:83

for L being Lattice
for F being Filter of L st L is I_Lattice holds
equivalence_wrt F is_transitive_in the carrier of L

proof end;

theorem Th84: :: FILTER_0:84

for L being Lattice
for F being Filter of L st L is I_Lattice holds
equivalence_wrt F is Equivalence_Relation of the carrier of L

proof end;

theorem :: FILTER_0:85

for L being Lattice
for F being Filter of L st L is I_Lattice holds
field (equivalence_wrt F) = the carrier of L

proof end;

definition

let I be I_Lattice;
let FI be Filter of I;
:: original: equivalence_wrt
redefine func equivalence_wrt FI -> Equivalence_Relation of the carrier of I;
coherence by Th84;

end;

definition

let B be B_Lattice;
let FB be Filter of B;
:: original: equivalence_wrt
redefine func equivalence_wrt FB -> Equivalence_Relation of the carrier of B;
coherence by Th84;

end;

definition

let L be Lattice;
let F be Filter of L;
let p, q be Element of L;
pred p,q are_equivalence_wrt F means :Def13: :: FILTER_0:def 13
p <=> q in F;

end;

:: deftheorem Def13 defines are_equivalence_wrt FILTER_0:def 13 :

theorem :: FILTER_0:86

canceled;

theorem :: FILTER_0:87

for L being Lattice
for p, q being Element of L
for F being Filter of L holds
( p,q are_equivalence_wrt F iff [p,q] in equivalence_wrt F )

proof end;

theorem :: FILTER_0:88

for B being B_Lattice
for FB being Filter of B
for I being I_Lattice
for i being Element of I
for FI being Filter of I
for a being Element of B holds
( i,i are_equivalence_wrt FI & a,a are_equivalence_wrt FB )

proof end;

theorem :: FILTER_0:89

for L being Lattice
for p, q being Element of L
for F being Filter of L st p,q are_equivalence_wrt F holds
q,p are_equivalence_wrt F

proof end;

theorem :: FILTER_0:90

for B being B_Lattice
for FB being Filter of B
for I being I_Lattice
for i, j, k being Element of I
for FI being Filter of I
for a, b, c being Element of B holds
( ( 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 ) )

proof end;

begin

theorem :: FILTER_0:91

for L being non empty join-commutative meet-commutative meet-associative meet-absorbing join-absorbing 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

proof end;

theorem :: FILTER_0:92

for L being non empty join-commutative join-associative meet-commutative meet-absorbing join-absorbing 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

proof end;