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

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, q, r being Element of L st p [= r holds
p "/\" q [= r

proof end;

theorem :: FILTER_0:3

for L being Lattice
for p, q, r 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;
mode Filter of L is non empty final meet-closed Subset of L;

end;

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 Th11: :: FILTER_0:11

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:12

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

proof end;

theorem :: FILTER_0:13

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

proof end;

theorem Th14: :: FILTER_0:14

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 1
the carrier of L;

coherence
the carrier of L is Filter of L by Th14;

end;

:: deftheorem defines <. FILTER_0:def 1 :
for L being Lattice holds <.L.) = the carrier of L;

definition

let L be Lattice;
let p be Element of L;

func <.p.) -> Filter of L equals :: FILTER_0:def 2
{ q where q is Element of L : p [= q } ;

coherence
{ q where q is Element of L : p [= q } is Filter of L

proof end;

end;

:: deftheorem defines <. FILTER_0:def 2 :
for L being Lattice
for p being Element of L holds <.p.) = { q where q is Element of L : p [= q } ;

theorem Th15: :: FILTER_0:15

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

proof end;

theorem Th16: :: FILTER_0:16

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 Th17: :: FILTER_0:17

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 :: FILTER_0:def 3
( 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 defines being_ultrafilter FILTER_0:def 3 :
for L being Lattice
for F being Filter of L holds
( F is being_ultrafilter iff ( F <> the carrier of L & ( for H being Filter of L st F c= H & H <> the carrier of L holds
F = H ) ) );

theorem Th18: :: FILTER_0:18

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 Th19: :: FILTER_0:19

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 Th20: :: FILTER_0:20

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 :Def4: :: FILTER_0:def 4
( D c= it & ( for F being Filter of L st D c= F holds
it c= F ) );

existence
ex b₁ being Filter of L st
( D c= b₁ & ( for F being Filter of L st D c= F holds
b₁ c= F ) )

proof end;

uniqueness
for b₁, b₂ being Filter of L st D c= b₁ & ( for F being Filter of L st D c= F holds
b₁ c= F ) & D c= b₂ & ( for F being Filter of L st D c= F holds
b₂ c= F ) holds
b₁ = b₂ ;

end;

:: deftheorem Def4 defines <. FILTER_0:def 4 :
for L being Lattice
for D being non empty Subset of L
for b₃ being Filter of L holds
( b₃ = <.D.) iff ( D c= b₃ & ( for F being Filter of L st D c= F holds
b₃ c= F ) ) );

theorem Th21: :: FILTER_0:21

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

theorem Th22: :: FILTER_0:22

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

proof end;

theorem Th23: :: FILTER_0:23

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 Th24: :: FILTER_0:24

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 Th25: :: FILTER_0:25

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 Th26: :: FILTER_0:26

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 5
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 5 :
for L being Lattice
for F being Filter of L holds
( F is prime iff for p, q being Element of L holds
( p "\/" q in F iff ( p in F or q in F ) ) );

theorem Th27: :: FILTER_0:27

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 :Def6: :: 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;

:: deftheorem Def6 defines implicative FILTER_0:def 6 :
for IT being non empty LattStr holds
( IT is implicative iff 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 ) ) );

registration

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

existence
ex b₁ being Lattice st
( b₁ is strict & b₁ is implicative )

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 :Def7: :: FILTER_0:def 7
( p "/\" it [= q & ( for r being Element of L st p "/\" r [= q holds
r [= it ) );

existence
ex b₁ being Element of L st
( p "/\" b₁ [= q & ( for r being Element of L st p "/\" r [= q holds
r [= b₁ ) ) by A1, Def6;
correctness
uniqueness
for b₁, b₂ being Element of L st p "/\" b₁ [= q & ( for r being Element of L st p "/\" r [= q holds
r [= b₁ ) & p "/\" b₂ [= q & ( for r being Element of L st p "/\" r [= q holds
r [= b₂ ) holds
b₁ = b₂;

proof end;

end;

:: deftheorem Def7 defines => FILTER_0:def 7 :
for L being Lattice
for p, q being Element of L st L is I_Lattice holds
for b₄ being Element of L holds
( b₄ = p => q iff ( p "/\" b₄ [= q & ( for r being Element of L st p "/\" r [= q holds
r [= b₄ ) ) );

registration

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

coherence
for b₁ being I_Lattice holds b₁ is upper-bounded

proof end;

end;

theorem Th28: :: FILTER_0:28

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

proof end;

registration

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

coherence
for b₁ being I_Lattice holds b₁ is distributive

proof end;

end;

registration

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

coherence
for b₁ being B_Lattice holds b₁ is implicative

proof end;

end;

registration

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

coherence
for b₁ being Lattice st b₁ is implicative holds
b₁ is distributive ;

end;

theorem Th29: :: FILTER_0:29

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 Th30: :: FILTER_0:30

for I being I_Lattice
for i, j 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 8
{ (p "/\" q) where p, q is Element of L : ( p in D1 & q in D2 ) } ;

coherence
{ (p "/\" q) where p, q is Element of L : ( p in D1 & q in D2 ) } is Subset of L

proof end;

end;

:: deftheorem defines "/\" FILTER_0:def 8 :
for L being Lattice
for D1, D2 being non empty Subset of L holds D1 "/\" D2 = { (p "/\" q) where p, q is Element of L : ( p in D1 & q in D2 ) } ;

registration

let L be Lattice;
let D1, D2 be non empty Subset of L;

cluster D1 "/\" D2 -> non empty ;

coherence
not D1 "/\" D2 is empty

proof end;

end;

theorem :: FILTER_0:31

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:32

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 Th33: :: FILTER_0:33

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
( F1 "/\" F2 is final & F1 "/\" F2 is meet-closed )

proof end;

end;

theorem Th34: :: FILTER_0:34

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:35

for L being Lattice
for H, F 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 Th36: :: FILTER_0:36

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

proof end;

theorem Th37: :: FILTER_0:37

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

proof end;

theorem Th38: :: FILTER_0:38

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

proof end;

theorem :: FILTER_0:39

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

proof end;

theorem Th40: :: FILTER_0:40

for I being I_Lattice
for i, j 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 Th41: :: FILTER_0:41

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 Th42: :: FILTER_0:42

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

proof end;

theorem Th43: :: FILTER_0:43

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

proof end;

theorem Th44: :: FILTER_0:44

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:45

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 Th46: :: FILTER_0:46

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:47

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 :Def9: :: FILTER_0:def 9
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
for b₁, b₂ being Lattice st ex o1, o2 being BinOp of F st
( o1 = the L_join of L || F & o2 = the L_meet of L || F & b₁ = LattStr(# F,o1,o2 #) ) & ex o1, o2 being BinOp of F st
( o1 = the L_join of L || F & o2 = the L_meet of L || F & b₂ = LattStr(# F,o1,o2 #) ) holds
b₁ = b₂ ;
existence
ex b₁ being Lattice ex o1, o2 being BinOp of F st
( o1 = the L_join of L || F & o2 = the L_meet of L || F & b₁ = LattStr(# F,o1,o2 #) )

proof end;

end;

:: deftheorem Def9 defines latt FILTER_0:def 9 :
for L being Lattice
for F being Filter of L
for b₃ being Lattice holds
( b₃ = latt F iff ex o1, o2 being BinOp of F st
( o1 = the L_join of L || F & o2 = the L_meet of L || F & b₃ = LattStr(# F,o1,o2 #) ) );

registration

let L be Lattice;
let F be Filter of L;

cluster latt F -> strict ;

coherence
latt F is strict

proof end;

end;

theorem :: FILTER_0:48

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

proof end;

theorem Th49: :: FILTER_0:49

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 Th50: :: FILTER_0:50

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 Th51: :: FILTER_0:51

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 ) by Th50;

theorem Th52: :: FILTER_0:52

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:53

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

proof end;

theorem Th54: :: FILTER_0:54

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

proof end;

theorem :: FILTER_0:55

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

proof end;

registration

let L be Lattice;
let p be Element of L;

cluster latt <.p.) -> lower-bounded ;

coherence
latt <.p.) is lower-bounded

proof end;

end;

theorem Th56: :: FILTER_0:56

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

proof end;

theorem Th57: :: FILTER_0:57

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

proof end;

theorem Th58: :: FILTER_0:58

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

theorem Th59: :: FILTER_0:59

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:60

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 10
(p => q) "/\" (q => p);

correctness
coherence
(p => q) "/\" (q => p) is Element of L;
;

end;

:: deftheorem defines <=> FILTER_0:def 10 :
for L being Lattice
for p, q being Element of L holds p <=> q = (p => q) "/\" (q => p);

theorem :: FILTER_0:61

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

theorem Th62: :: FILTER_0:62

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 :Def11: :: FILTER_0:def 11
( 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
ex b₁ being Relation st
( field b₁ c= the carrier of L & ( for p, q being Element of L holds
( [p,q] in b₁ iff p <=> q in F ) ) )

proof end;

uniqueness
for b₁, b₂ being Relation st field b₁ c= the carrier of L & ( for p, q being Element of L holds
( [p,q] in b₁ iff p <=> q in F ) ) & field b₂ c= the carrier of L & ( for p, q being Element of L holds
( [p,q] in b₂ iff p <=> q in F ) ) holds
b₁ = b₂

proof end;

end;

:: deftheorem Def11 defines equivalence_wrt FILTER_0:def 11 :
for L being Lattice
for F being Filter of L
for b₃ being Relation holds
( b₃ = equivalence_wrt F iff ( field b₃ c= the carrier of L & ( for p, q being Element of L holds
( [p,q] in b₃ iff p <=> q in F ) ) ) );

theorem Th63: :: FILTER_0:63

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

proof end;

theorem Th64: :: FILTER_0:64

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 Th65: :: FILTER_0:65

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

proof end;

theorem Th66: :: FILTER_0:66

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 Th67: :: FILTER_0:67

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:68

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
equivalence_wrt FI is Equivalence_Relation of the carrier of I by Th67;

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
equivalence_wrt FB is Equivalence_Relation of the carrier of B by Th67;

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 :: FILTER_0:def 12
p <=> q in F;

end;

:: deftheorem defines are_equivalence_wrt FILTER_0:def 12 :
for L being Lattice
for F being Filter of L
for p, q being Element of L holds
( p,q are_equivalence_wrt F iff p <=> q in F );

theorem :: FILTER_0:69

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 ) by Def11;

theorem :: FILTER_0:70

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:71

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 ;

theorem :: FILTER_0:72

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 ) ) by Th62;

:: missing, 2006.12.05, AT

theorem :: FILTER_0:73

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:74

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;