Metamath Proof Explorer


Theorem pw2f1ocnv

Description: Define a bijection between characteristic functions and subsets. EDITORIAL: extracted from pw2en , which can be easily reproved in terms of this. (Contributed by Stefan O'Rear, 18-Jan-2015) (Revised by Stefan O'Rear, 9-Jul-2015)

Ref Expression
Hypothesis pw2f1o2.f F=x2𝑜Ax-11𝑜
Assertion pw2f1ocnv AVF:2𝑜A1-1 onto𝒫AF-1=y𝒫AzAifzy1𝑜

Proof

Step Hyp Ref Expression
1 pw2f1o2.f F=x2𝑜Ax-11𝑜
2 vex xV
3 2 cnvex x-1V
4 imaexg x-1Vx-11𝑜V
5 3 4 mp1i AVx2𝑜Ax-11𝑜V
6 mptexg AVzAifzy1𝑜V
7 6 adantr AVy𝒫AzAifzy1𝑜V
8 2on 2𝑜On
9 elmapg 2𝑜OnAVx2𝑜Ax:A2𝑜
10 8 9 mpan AVx2𝑜Ax:A2𝑜
11 10 anbi1d AVx2𝑜Ay=x-11𝑜x:A2𝑜y=x-11𝑜
12 1oex 1𝑜V
13 12 sucid 1𝑜suc1𝑜
14 df-2o 2𝑜=suc1𝑜
15 13 14 eleqtrri 1𝑜2𝑜
16 0ex V
17 16 prid1
18 df2o2 2𝑜=
19 17 18 eleqtrri 2𝑜
20 15 19 ifcli ifzy1𝑜2𝑜
21 20 rgenw zAifzy1𝑜2𝑜
22 eqid zAifzy1𝑜=zAifzy1𝑜
23 22 fmpt zAifzy1𝑜2𝑜zAifzy1𝑜:A2𝑜
24 21 23 mpbi zAifzy1𝑜:A2𝑜
25 simpr yAx=zAifzy1𝑜x=zAifzy1𝑜
26 25 feq1d yAx=zAifzy1𝑜x:A2𝑜zAifzy1𝑜:A2𝑜
27 24 26 mpbiri yAx=zAifzy1𝑜x:A2𝑜
28 iftrue wyifwy1𝑜=1𝑜
29 noel ¬
30 iffalse ¬wyifwy1𝑜=
31 30 eqeq1d ¬wyifwy1𝑜=1𝑜=1𝑜
32 0lt1o 1𝑜
33 eleq2 =1𝑜1𝑜
34 32 33 mpbiri =1𝑜
35 31 34 syl6bi ¬wyifwy1𝑜=1𝑜
36 29 35 mtoi ¬wy¬ifwy1𝑜=1𝑜
37 36 con4i ifwy1𝑜=1𝑜wy
38 28 37 impbii wyifwy1𝑜=1𝑜
39 25 fveq1d yAx=zAifzy1𝑜xw=zAifzy1𝑜w
40 elequ1 z=wzywy
41 40 ifbid z=wifzy1𝑜=ifwy1𝑜
42 12 16 ifcli ifwy1𝑜V
43 41 22 42 fvmpt wAzAifzy1𝑜w=ifwy1𝑜
44 39 43 sylan9eq yAx=zAifzy1𝑜wAxw=ifwy1𝑜
45 44 eqeq1d yAx=zAifzy1𝑜wAxw=1𝑜ifwy1𝑜=1𝑜
46 38 45 bitr4id yAx=zAifzy1𝑜wAwyxw=1𝑜
47 fvex xwV
48 47 elsn xw1𝑜xw=1𝑜
49 46 48 bitr4di yAx=zAifzy1𝑜wAwyxw1𝑜
50 49 pm5.32da yAx=zAifzy1𝑜wAwywAxw1𝑜
51 ssel yAwywA
52 51 adantr yAx=zAifzy1𝑜wywA
53 52 pm4.71rd yAx=zAifzy1𝑜wywAwy
54 ffn x:A2𝑜xFnA
55 elpreima xFnAwx-11𝑜wAxw1𝑜
56 27 54 55 3syl yAx=zAifzy1𝑜wx-11𝑜wAxw1𝑜
57 50 53 56 3bitr4d yAx=zAifzy1𝑜wywx-11𝑜
58 57 eqrdv yAx=zAifzy1𝑜y=x-11𝑜
59 27 58 jca yAx=zAifzy1𝑜x:A2𝑜y=x-11𝑜
60 simpr x:A2𝑜y=x-11𝑜y=x-11𝑜
61 cnvimass x-11𝑜domx
62 fdm x:A2𝑜domx=A
63 62 adantr x:A2𝑜y=x-11𝑜domx=A
64 61 63 sseqtrid x:A2𝑜y=x-11𝑜x-11𝑜A
65 60 64 eqsstrd x:A2𝑜y=x-11𝑜yA
66 simplr x:A2𝑜y=x-11𝑜wAy=x-11𝑜
67 66 eleq2d x:A2𝑜y=x-11𝑜wAwywx-11𝑜
68 54 adantr x:A2𝑜y=x-11𝑜xFnA
69 fnbrfvb xFnAwAxw=1𝑜wx1𝑜
70 68 69 sylan x:A2𝑜y=x-11𝑜wAxw=1𝑜wx1𝑜
71 1on 1𝑜On
72 vex wV
73 72 eliniseg 1𝑜Onwx-11𝑜wx1𝑜
74 71 73 ax-mp wx-11𝑜wx1𝑜
75 70 74 bitr4di x:A2𝑜y=x-11𝑜wAxw=1𝑜wx-11𝑜
76 67 75 bitr4d x:A2𝑜y=x-11𝑜wAwyxw=1𝑜
77 76 biimpa x:A2𝑜y=x-11𝑜wAwyxw=1𝑜
78 28 adantl x:A2𝑜y=x-11𝑜wAwyifwy1𝑜=1𝑜
79 77 78 eqtr4d x:A2𝑜y=x-11𝑜wAwyxw=ifwy1𝑜
80 ffvelcdm x:A2𝑜wAxw2𝑜
81 80 adantlr x:A2𝑜y=x-11𝑜wAxw2𝑜
82 df2o3 2𝑜=1𝑜
83 81 82 eleqtrdi x:A2𝑜y=x-11𝑜wAxw1𝑜
84 47 elpr xw1𝑜xw=xw=1𝑜
85 83 84 sylib x:A2𝑜y=x-11𝑜wAxw=xw=1𝑜
86 85 ord x:A2𝑜y=x-11𝑜wA¬xw=xw=1𝑜
87 86 76 sylibrd x:A2𝑜y=x-11𝑜wA¬xw=wy
88 87 con1d x:A2𝑜y=x-11𝑜wA¬wyxw=
89 88 imp x:A2𝑜y=x-11𝑜wA¬wyxw=
90 30 adantl x:A2𝑜y=x-11𝑜wA¬wyifwy1𝑜=
91 89 90 eqtr4d x:A2𝑜y=x-11𝑜wA¬wyxw=ifwy1𝑜
92 79 91 pm2.61dan x:A2𝑜y=x-11𝑜wAxw=ifwy1𝑜
93 43 adantl x:A2𝑜y=x-11𝑜wAzAifzy1𝑜w=ifwy1𝑜
94 92 93 eqtr4d x:A2𝑜y=x-11𝑜wAxw=zAifzy1𝑜w
95 94 ralrimiva x:A2𝑜y=x-11𝑜wAxw=zAifzy1𝑜w
96 ffn zAifzy1𝑜:A2𝑜zAifzy1𝑜FnA
97 24 96 ax-mp zAifzy1𝑜FnA
98 eqfnfv xFnAzAifzy1𝑜FnAx=zAifzy1𝑜wAxw=zAifzy1𝑜w
99 68 97 98 sylancl x:A2𝑜y=x-11𝑜x=zAifzy1𝑜wAxw=zAifzy1𝑜w
100 95 99 mpbird x:A2𝑜y=x-11𝑜x=zAifzy1𝑜
101 65 100 jca x:A2𝑜y=x-11𝑜yAx=zAifzy1𝑜
102 59 101 impbii yAx=zAifzy1𝑜x:A2𝑜y=x-11𝑜
103 11 102 bitr4di AVx2𝑜Ay=x-11𝑜yAx=zAifzy1𝑜
104 velpw y𝒫AyA
105 104 anbi1i y𝒫Ax=zAifzy1𝑜yAx=zAifzy1𝑜
106 103 105 bitr4di AVx2𝑜Ay=x-11𝑜y𝒫Ax=zAifzy1𝑜
107 1 5 7 106 f1ocnvd AVF:2𝑜A1-1 onto𝒫AF-1=y𝒫AzAifzy1𝑜