Metamath Proof Explorer

Theorem pwrssmgc

Description: Given a function F , exhibit a Galois connection between subsets of its domain and subsets of its range. (Contributed by Thierry Arnoux, 26-Apr-2024)

Ref Expression
Hypotheses pwrssmgc.1 
|- G = ( n e. ~P Y |-> ( `' F " n ) )
pwrssmgc.2 
|- H = ( m e. ~P X |-> { y e. Y | ( `' F " { y } ) C_ m } )
pwrssmgc.3 
|- V = ( toInc ` ~P Y )
pwrssmgc.4 
|- W = ( toInc ` ~P X )
pwrssmgc.5 
|- ( ph -> X e. A )
pwrssmgc.6 
|- ( ph -> Y e. B )
pwrssmgc.7 
|- ( ph -> F : X --> Y )
Assertion pwrssmgc 
|- ( ph -> G ( V MGalConn W ) H )

Proof

Step Hyp Ref Expression
1 pwrssmgc.1 
 |-  G = ( n e. ~P Y |-> ( `' F " n ) )
2 pwrssmgc.2 
 |-  H = ( m e. ~P X |-> { y e. Y | ( `' F " { y } ) C_ m } )
3 pwrssmgc.3 
 |-  V = ( toInc ` ~P Y )
4 pwrssmgc.4 
 |-  W = ( toInc ` ~P X )
5 pwrssmgc.5 
 |-  ( ph -> X e. A )
6 pwrssmgc.6 
 |-  ( ph -> Y e. B )
7 pwrssmgc.7 
 |-  ( ph -> F : X --> Y )
8 5 adantr 
 |-  ( ( ph /\ n e. ~P Y ) -> X e. A )
9 cnvimass 
 |-  ( `' F " n ) C_ dom F
10 9 7 fssdm 
 |-  ( ph -> ( `' F " n ) C_ X )
11 10 adantr 
 |-  ( ( ph /\ n e. ~P Y ) -> ( `' F " n ) C_ X )
12 8 11 sselpwd 
 |-  ( ( ph /\ n e. ~P Y ) -> ( `' F " n ) e. ~P X )
13 12 1 fmptd 
 |-  ( ph -> G : ~P Y --> ~P X )
14 pwexg 
 |-  ( Y e. B -> ~P Y e. _V )
15 3 ipobas 
 |-  ( ~P Y e. _V -> ~P Y = ( Base ` V ) )
16 6 14 15 3syl 
 |-  ( ph -> ~P Y = ( Base ` V ) )
17 pwexg 
 |-  ( X e. A -> ~P X e. _V )
18 4 ipobas 
 |-  ( ~P X e. _V -> ~P X = ( Base ` W ) )
19 5 17 18 3syl 
 |-  ( ph -> ~P X = ( Base ` W ) )
20 16 19 feq23d 
 |-  ( ph -> ( G : ~P Y --> ~P X <-> G : ( Base ` V ) --> ( Base ` W ) ) )
21 13 20 mpbid 
 |-  ( ph -> G : ( Base ` V ) --> ( Base ` W ) )
22 6 adantr 
 |-  ( ( ph /\ m e. ~P X ) -> Y e. B )
23 ssrab2 
 |-  { y e. Y | ( `' F " { y } ) C_ m } C_ Y
24 23 a1i 
 |-  ( ( ph /\ m e. ~P X ) -> { y e. Y | ( `' F " { y } ) C_ m } C_ Y )
25 22 24 sselpwd 
 |-  ( ( ph /\ m e. ~P X ) -> { y e. Y | ( `' F " { y } ) C_ m } e. ~P Y )
26 25 2 fmptd 
 |-  ( ph -> H : ~P X --> ~P Y )
27 19 16 feq23d 
 |-  ( ph -> ( H : ~P X --> ~P Y <-> H : ( Base ` W ) --> ( Base ` V ) ) )
28 26 27 mpbid 
 |-  ( ph -> H : ( Base ` W ) --> ( Base ` V ) )
29 21 28 jca 
 |-  ( ph -> ( G : ( Base ` V ) --> ( Base ` W ) /\ H : ( Base ` W ) --> ( Base ` V ) ) )
30 sneq 
 |-  ( y = j -> { y } = { j } )
31 30 imaeq2d 
 |-  ( y = j -> ( `' F " { y } ) = ( `' F " { j } ) )
32 31 sseq1d 
 |-  ( y = j -> ( ( `' F " { y } ) C_ v <-> ( `' F " { j } ) C_ v ) )
33 simplr 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> u e. ( Base ` V ) )
34 16 ad2antrr 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ~P Y = ( Base ` V ) )
35 33 34 eleqtrrd 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> u e. ~P Y )
36 35 adantr 
 |-  ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ ( `' F " u ) C_ v ) -> u e. ~P Y )
37 36 elpwid 
 |-  ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ ( `' F " u ) C_ v ) -> u C_ Y )
38 37 sselda 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ ( `' F " u ) C_ v ) /\ j e. u ) -> j e. Y )
39 7 ffund 
 |-  ( ph -> Fun F )
40 39 ad4antr 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ ( `' F " u ) C_ v ) /\ j e. u ) -> Fun F )
41 snssi 
 |-  ( j e. u -> { j } C_ u )
42 41 adantl 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ ( `' F " u ) C_ v ) /\ j e. u ) -> { j } C_ u )
43 sspreima 
 |-  ( ( Fun F /\ { j } C_ u ) -> ( `' F " { j } ) C_ ( `' F " u ) )
44 40 42 43 syl2anc 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ ( `' F " u ) C_ v ) /\ j e. u ) -> ( `' F " { j } ) C_ ( `' F " u ) )
45 simplr 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ ( `' F " u ) C_ v ) /\ j e. u ) -> ( `' F " u ) C_ v )
46 44 45 sstrd 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ ( `' F " u ) C_ v ) /\ j e. u ) -> ( `' F " { j } ) C_ v )
47 32 38 46 elrabd 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ ( `' F " u ) C_ v ) /\ j e. u ) -> j e. { y e. Y | ( `' F " { y } ) C_ v } )
48 47 ex 
 |-  ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ ( `' F " u ) C_ v ) -> ( j e. u -> j e. { y e. Y | ( `' F " { y } ) C_ v } ) )
49 48 ssrdv 
 |-  ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ ( `' F " u ) C_ v ) -> u C_ { y e. Y | ( `' F " { y } ) C_ v } )
50 simplr 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ u C_ { y e. Y | ( `' F " { y } ) C_ v } ) /\ i e. ( `' F " u ) ) -> u C_ { y e. Y | ( `' F " { y } ) C_ v } )
51 7 ffnd 
 |-  ( ph -> F Fn X )
52 51 ad4antr 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ u C_ { y e. Y | ( `' F " { y } ) C_ v } ) /\ i e. ( `' F " u ) ) -> F Fn X )
53 simpr 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ u C_ { y e. Y | ( `' F " { y } ) C_ v } ) /\ i e. ( `' F " u ) ) -> i e. ( `' F " u ) )
54 elpreima 
 |-  ( F Fn X -> ( i e. ( `' F " u ) <-> ( i e. X /\ ( F ` i ) e. u ) ) )
55 54 biimpa 
 |-  ( ( F Fn X /\ i e. ( `' F " u ) ) -> ( i e. X /\ ( F ` i ) e. u ) )
56 52 53 55 syl2anc 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ u C_ { y e. Y | ( `' F " { y } ) C_ v } ) /\ i e. ( `' F " u ) ) -> ( i e. X /\ ( F ` i ) e. u ) )
57 56 simprd 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ u C_ { y e. Y | ( `' F " { y } ) C_ v } ) /\ i e. ( `' F " u ) ) -> ( F ` i ) e. u )
58 50 57 sseldd 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ u C_ { y e. Y | ( `' F " { y } ) C_ v } ) /\ i e. ( `' F " u ) ) -> ( F ` i ) e. { y e. Y | ( `' F " { y } ) C_ v } )
59 sneq 
 |-  ( y = ( F ` i ) -> { y } = { ( F ` i ) } )
60 59 imaeq2d 
 |-  ( y = ( F ` i ) -> ( `' F " { y } ) = ( `' F " { ( F ` i ) } ) )
61 60 sseq1d 
 |-  ( y = ( F ` i ) -> ( ( `' F " { y } ) C_ v <-> ( `' F " { ( F ` i ) } ) C_ v ) )
62 61 elrab 
 |-  ( ( F ` i ) e. { y e. Y | ( `' F " { y } ) C_ v } <-> ( ( F ` i ) e. Y /\ ( `' F " { ( F ` i ) } ) C_ v ) )
63 62 simprbi 
 |-  ( ( F ` i ) e. { y e. Y | ( `' F " { y } ) C_ v } -> ( `' F " { ( F ` i ) } ) C_ v )
64 58 63 syl 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ u C_ { y e. Y | ( `' F " { y } ) C_ v } ) /\ i e. ( `' F " u ) ) -> ( `' F " { ( F ` i ) } ) C_ v )
65 56 simpld 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ u C_ { y e. Y | ( `' F " { y } ) C_ v } ) /\ i e. ( `' F " u ) ) -> i e. X )
66 eqidd 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ u C_ { y e. Y | ( `' F " { y } ) C_ v } ) /\ i e. ( `' F " u ) ) -> ( F ` i ) = ( F ` i ) )
67 fniniseg 
 |-  ( F Fn X -> ( i e. ( `' F " { ( F ` i ) } ) <-> ( i e. X /\ ( F ` i ) = ( F ` i ) ) ) )
68 67 biimpar 
 |-  ( ( F Fn X /\ ( i e. X /\ ( F ` i ) = ( F ` i ) ) ) -> i e. ( `' F " { ( F ` i ) } ) )
69 52 65 66 68 syl12anc 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ u C_ { y e. Y | ( `' F " { y } ) C_ v } ) /\ i e. ( `' F " u ) ) -> i e. ( `' F " { ( F ` i ) } ) )
70 64 69 sseldd 
 |-  ( ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ u C_ { y e. Y | ( `' F " { y } ) C_ v } ) /\ i e. ( `' F " u ) ) -> i e. v )
71 70 ex 
 |-  ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ u C_ { y e. Y | ( `' F " { y } ) C_ v } ) -> ( i e. ( `' F " u ) -> i e. v ) )
72 71 ssrdv 
 |-  ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ u C_ { y e. Y | ( `' F " { y } ) C_ v } ) -> ( `' F " u ) C_ v )
73 49 72 impbida 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ( ( `' F " u ) C_ v <-> u C_ { y e. Y | ( `' F " { y } ) C_ v } ) )
74 simpr 
 |-  ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ n = u ) -> n = u )
75 74 imaeq2d 
 |-  ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ n = u ) -> ( `' F " n ) = ( `' F " u ) )
76 fex 
 |-  ( ( F : X --> Y /\ X e. A ) -> F e. _V )
77 7 5 76 syl2anc 
 |-  ( ph -> F e. _V )
78 cnvexg 
 |-  ( F e. _V -> `' F e. _V )
79 imaexg 
 |-  ( `' F e. _V -> ( `' F " u ) e. _V )
80 77 78 79 3syl 
 |-  ( ph -> ( `' F " u ) e. _V )
81 80 ad2antrr 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ( `' F " u ) e. _V )
82 1 75 35 81 fvmptd2 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ( G ` u ) = ( `' F " u ) )
83 82 sseq1d 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ( ( G ` u ) C_ v <-> ( `' F " u ) C_ v ) )
84 simpr 
 |-  ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ m = v ) -> m = v )
85 84 sseq2d 
 |-  ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ m = v ) -> ( ( `' F " { y } ) C_ m <-> ( `' F " { y } ) C_ v ) )
86 85 rabbidv 
 |-  ( ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) /\ m = v ) -> { y e. Y | ( `' F " { y } ) C_ m } = { y e. Y | ( `' F " { y } ) C_ v } )
87 simpr 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> v e. ( Base ` W ) )
88 5 17 syl 
 |-  ( ph -> ~P X e. _V )
89 88 ad2antrr 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ~P X e. _V )
90 89 18 syl 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ~P X = ( Base ` W ) )
91 87 90 eleqtrrd 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> v e. ~P X )
92 6 ad2antrr 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> Y e. B )
93 ssrab2 
 |-  { y e. Y | ( `' F " { y } ) C_ v } C_ Y
94 93 a1i 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> { y e. Y | ( `' F " { y } ) C_ v } C_ Y )
95 92 94 sselpwd 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> { y e. Y | ( `' F " { y } ) C_ v } e. ~P Y )
96 2 86 91 95 fvmptd2 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ( H ` v ) = { y e. Y | ( `' F " { y } ) C_ v } )
97 96 sseq2d 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ( u C_ ( H ` v ) <-> u C_ { y e. Y | ( `' F " { y } ) C_ v } ) )
98 73 83 97 3bitr4d 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ( ( G ` u ) C_ v <-> u C_ ( H ` v ) ) )
99 13 ad2antrr 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> G : ~P Y --> ~P X )
100 99 35 ffvelrnd 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ( G ` u ) e. ~P X )
101 eqid 
 |-  ( le ` W ) = ( le ` W )
102 4 101 ipole 
 |-  ( ( ~P X e. _V /\ ( G ` u ) e. ~P X /\ v e. ~P X ) -> ( ( G ` u ) ( le ` W ) v <-> ( G ` u ) C_ v ) )
103 89 100 91 102 syl3anc 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ( ( G ` u ) ( le ` W ) v <-> ( G ` u ) C_ v ) )
104 6 14 syl 
 |-  ( ph -> ~P Y e. _V )
105 104 ad2antrr 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ~P Y e. _V )
106 26 ad2antrr 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> H : ~P X --> ~P Y )
107 106 91 ffvelrnd 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ( H ` v ) e. ~P Y )
108 eqid 
 |-  ( le ` V ) = ( le ` V )
109 3 108 ipole 
 |-  ( ( ~P Y e. _V /\ u e. ~P Y /\ ( H ` v ) e. ~P Y ) -> ( u ( le ` V ) ( H ` v ) <-> u C_ ( H ` v ) ) )
110 105 35 107 109 syl3anc 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ( u ( le ` V ) ( H ` v ) <-> u C_ ( H ` v ) ) )
111 98 103 110 3bitr4d 
 |-  ( ( ( ph /\ u e. ( Base ` V ) ) /\ v e. ( Base ` W ) ) -> ( ( G ` u ) ( le ` W ) v <-> u ( le ` V ) ( H ` v ) ) )
112 111 anasss 
 |-  ( ( ph /\ ( u e. ( Base ` V ) /\ v e. ( Base ` W ) ) ) -> ( ( G ` u ) ( le ` W ) v <-> u ( le ` V ) ( H ` v ) ) )
113 112 ralrimivva 
 |-  ( ph -> A. u e. ( Base ` V ) A. v e. ( Base ` W ) ( ( G ` u ) ( le ` W ) v <-> u ( le ` V ) ( H ` v ) ) )
114 eqid 
 |-  ( Base ` V ) = ( Base ` V )
115 eqid 
 |-  ( Base ` W ) = ( Base ` W )
116 eqid 
 |-  ( V MGalConn W ) = ( V MGalConn W )
117 3 ipopos 
 |-  V e. Poset
118 posprs 
 |-  ( V e. Poset -> V e. Proset )
119 117 118 mp1i 
 |-  ( ph -> V e. Proset )
120 4 ipopos 
 |-  W e. Poset
121 posprs 
 |-  ( W e. Poset -> W e. Proset )
122 120 121 mp1i 
 |-  ( ph -> W e. Proset )
123 114 115 108 101 116 119 122 mgcval 
 |-  ( ph -> ( G ( V MGalConn W ) H <-> ( ( G : ( Base ` V ) --> ( Base ` W ) /\ H : ( Base ` W ) --> ( Base ` V ) ) /\ A. u e. ( Base ` V ) A. v e. ( Base ` W ) ( ( G ` u ) ( le ` W ) v <-> u ( le ` V ) ( H ` v ) ) ) ) )
124 29 113 123 mpbir2and 
 |-  ( ph -> G ( V MGalConn W ) H )