Metamath Proof Explorer

Theorem hashfun

Description: A finite set is a function iff it is equinumerous to its domain. (Contributed by Mario Carneiro, 26-Sep-2013) (Revised by Mario Carneiro, 12-Mar-2015)

Ref Expression
Assertion hashfun 
|- ( F e. Fin -> ( Fun F <-> ( # ` F ) = ( # ` dom F ) ) )

Proof

Step Hyp Ref Expression
1 funfn 
 |-  ( Fun F <-> F Fn dom F )
2 hashfn 
 |-  ( F Fn dom F -> ( # ` F ) = ( # ` dom F ) )
3 1 2 sylbi 
 |-  ( Fun F -> ( # ` F ) = ( # ` dom F ) )
4 dmfi 
 |-  ( F e. Fin -> dom F e. Fin )
5 hashcl 
 |-  ( dom F e. Fin -> ( # ` dom F ) e. NN0 )
6 4 5 syl 
 |-  ( F e. Fin -> ( # ` dom F ) e. NN0 )
7 6 nn0red 
 |-  ( F e. Fin -> ( # ` dom F ) e. RR )
8 7 adantr 
 |-  ( ( F e. Fin /\ -. Rel F ) -> ( # ` dom F ) e. RR )
9 df-rel 
 |-  ( Rel F <-> F C_ ( _V X. _V ) )
10 dfss3 
 |-  ( F C_ ( _V X. _V ) <-> A. x e. F x e. ( _V X. _V ) )
11 9 10 bitri 
 |-  ( Rel F <-> A. x e. F x e. ( _V X. _V ) )
12 11 notbii 
 |-  ( -. Rel F <-> -. A. x e. F x e. ( _V X. _V ) )
13 rexnal 
 |-  ( E. x e. F -. x e. ( _V X. _V ) <-> -. A. x e. F x e. ( _V X. _V ) )
14 12 13 bitr4i 
 |-  ( -. Rel F <-> E. x e. F -. x e. ( _V X. _V ) )
15 dmun 
 |-  dom ( ( F \ { x } ) u. { x } ) = ( dom ( F \ { x } ) u. dom { x } )
16 15 fveq2i 
 |-  ( # ` dom ( ( F \ { x } ) u. { x } ) ) = ( # ` ( dom ( F \ { x } ) u. dom { x } ) )
17 dmsnn0 
 |-  ( x e. ( _V X. _V ) <-> dom { x } =/= (/) )
18 17 biimpri 
 |-  ( dom { x } =/= (/) -> x e. ( _V X. _V ) )
19 18 necon1bi 
 |-  ( -. x e. ( _V X. _V ) -> dom { x } = (/) )
20 19 3ad2ant3 
 |-  ( ( F e. Fin /\ x e. F /\ -. x e. ( _V X. _V ) ) -> dom { x } = (/) )
21 20 uneq2d 
 |-  ( ( F e. Fin /\ x e. F /\ -. x e. ( _V X. _V ) ) -> ( dom ( F \ { x } ) u. dom { x } ) = ( dom ( F \ { x } ) u. (/) ) )
22 un0 
 |-  ( dom ( F \ { x } ) u. (/) ) = dom ( F \ { x } )
23 21 22 eqtrdi 
 |-  ( ( F e. Fin /\ x e. F /\ -. x e. ( _V X. _V ) ) -> ( dom ( F \ { x } ) u. dom { x } ) = dom ( F \ { x } ) )
24 23 fveq2d 
 |-  ( ( F e. Fin /\ x e. F /\ -. x e. ( _V X. _V ) ) -> ( # ` ( dom ( F \ { x } ) u. dom { x } ) ) = ( # ` dom ( F \ { x } ) ) )
25 16 24 eqtrid 
 |-  ( ( F e. Fin /\ x e. F /\ -. x e. ( _V X. _V ) ) -> ( # ` dom ( ( F \ { x } ) u. { x } ) ) = ( # ` dom ( F \ { x } ) ) )
26 diffi 
 |-  ( F e. Fin -> ( F \ { x } ) e. Fin )
27 dmfi 
 |-  ( ( F \ { x } ) e. Fin -> dom ( F \ { x } ) e. Fin )
28 26 27 syl 
 |-  ( F e. Fin -> dom ( F \ { x } ) e. Fin )
29 hashcl 
 |-  ( dom ( F \ { x } ) e. Fin -> ( # ` dom ( F \ { x } ) ) e. NN0 )
30 28 29 syl 
 |-  ( F e. Fin -> ( # ` dom ( F \ { x } ) ) e. NN0 )
31 30 nn0red 
 |-  ( F e. Fin -> ( # ` dom ( F \ { x } ) ) e. RR )
32 hashcl 
 |-  ( ( F \ { x } ) e. Fin -> ( # ` ( F \ { x } ) ) e. NN0 )
33 26 32 syl 
 |-  ( F e. Fin -> ( # ` ( F \ { x } ) ) e. NN0 )
34 33 nn0red 
 |-  ( F e. Fin -> ( # ` ( F \ { x } ) ) e. RR )
35 peano2re 
 |-  ( ( # ` ( F \ { x } ) ) e. RR -> ( ( # ` ( F \ { x } ) ) + 1 ) e. RR )
36 34 35 syl 
 |-  ( F e. Fin -> ( ( # ` ( F \ { x } ) ) + 1 ) e. RR )
37 fidomdm 
 |-  ( ( F \ { x } ) e. Fin -> dom ( F \ { x } ) ~<_ ( F \ { x } ) )
38 26 37 syl 
 |-  ( F e. Fin -> dom ( F \ { x } ) ~<_ ( F \ { x } ) )
39 hashdom 
 |-  ( ( dom ( F \ { x } ) e. Fin /\ ( F \ { x } ) e. Fin ) -> ( ( # ` dom ( F \ { x } ) ) <_ ( # ` ( F \ { x } ) ) <-> dom ( F \ { x } ) ~<_ ( F \ { x } ) ) )
40 28 26 39 syl2anc 
 |-  ( F e. Fin -> ( ( # ` dom ( F \ { x } ) ) <_ ( # ` ( F \ { x } ) ) <-> dom ( F \ { x } ) ~<_ ( F \ { x } ) ) )
41 38 40 mpbird 
 |-  ( F e. Fin -> ( # ` dom ( F \ { x } ) ) <_ ( # ` ( F \ { x } ) ) )
42 34 ltp1d 
 |-  ( F e. Fin -> ( # ` ( F \ { x } ) ) < ( ( # ` ( F \ { x } ) ) + 1 ) )
43 31 34 36 41 42 lelttrd 
 |-  ( F e. Fin -> ( # ` dom ( F \ { x } ) ) < ( ( # ` ( F \ { x } ) ) + 1 ) )
44 43 3ad2ant1 
 |-  ( ( F e. Fin /\ x e. F /\ -. x e. ( _V X. _V ) ) -> ( # ` dom ( F \ { x } ) ) < ( ( # ` ( F \ { x } ) ) + 1 ) )
45 25 44 eqbrtrd 
 |-  ( ( F e. Fin /\ x e. F /\ -. x e. ( _V X. _V ) ) -> ( # ` dom ( ( F \ { x } ) u. { x } ) ) < ( ( # ` ( F \ { x } ) ) + 1 ) )
46 snfi 
 |-  { x } e. Fin
47 disjdifr 
 |-  ( ( F \ { x } ) i^i { x } ) = (/)
48 hashun 
 |-  ( ( ( F \ { x } ) e. Fin /\ { x } e. Fin /\ ( ( F \ { x } ) i^i { x } ) = (/) ) -> ( # ` ( ( F \ { x } ) u. { x } ) ) = ( ( # ` ( F \ { x } ) ) + ( # ` { x } ) ) )
49 46 47 48 mp3an23 
 |-  ( ( F \ { x } ) e. Fin -> ( # ` ( ( F \ { x } ) u. { x } ) ) = ( ( # ` ( F \ { x } ) ) + ( # ` { x } ) ) )
50 26 49 syl 
 |-  ( F e. Fin -> ( # ` ( ( F \ { x } ) u. { x } ) ) = ( ( # ` ( F \ { x } ) ) + ( # ` { x } ) ) )
51 hashsng 
 |-  ( x e. _V -> ( # ` { x } ) = 1 )
52 51 elv 
 |-  ( # ` { x } ) = 1
53 52 oveq2i 
 |-  ( ( # ` ( F \ { x } ) ) + ( # ` { x } ) ) = ( ( # ` ( F \ { x } ) ) + 1 )
54 50 53 eqtr2di 
 |-  ( F e. Fin -> ( ( # ` ( F \ { x } ) ) + 1 ) = ( # ` ( ( F \ { x } ) u. { x } ) ) )
55 54 3ad2ant1 
 |-  ( ( F e. Fin /\ x e. F /\ -. x e. ( _V X. _V ) ) -> ( ( # ` ( F \ { x } ) ) + 1 ) = ( # ` ( ( F \ { x } ) u. { x } ) ) )
56 45 55 breqtrd 
 |-  ( ( F e. Fin /\ x e. F /\ -. x e. ( _V X. _V ) ) -> ( # ` dom ( ( F \ { x } ) u. { x } ) ) < ( # ` ( ( F \ { x } ) u. { x } ) ) )
57 difsnid 
 |-  ( x e. F -> ( ( F \ { x } ) u. { x } ) = F )
58 57 dmeqd 
 |-  ( x e. F -> dom ( ( F \ { x } ) u. { x } ) = dom F )
59 58 fveq2d 
 |-  ( x e. F -> ( # ` dom ( ( F \ { x } ) u. { x } ) ) = ( # ` dom F ) )
60 59 3ad2ant2 
 |-  ( ( F e. Fin /\ x e. F /\ -. x e. ( _V X. _V ) ) -> ( # ` dom ( ( F \ { x } ) u. { x } ) ) = ( # ` dom F ) )
61 57 fveq2d 
 |-  ( x e. F -> ( # ` ( ( F \ { x } ) u. { x } ) ) = ( # ` F ) )
62 61 3ad2ant2 
 |-  ( ( F e. Fin /\ x e. F /\ -. x e. ( _V X. _V ) ) -> ( # ` ( ( F \ { x } ) u. { x } ) ) = ( # ` F ) )
63 56 60 62 3brtr3d 
 |-  ( ( F e. Fin /\ x e. F /\ -. x e. ( _V X. _V ) ) -> ( # ` dom F ) < ( # ` F ) )
64 63 rexlimdv3a 
 |-  ( F e. Fin -> ( E. x e. F -. x e. ( _V X. _V ) -> ( # ` dom F ) < ( # ` F ) ) )
65 14 64 biimtrid 
 |-  ( F e. Fin -> ( -. Rel F -> ( # ` dom F ) < ( # ` F ) ) )
66 65 imp 
 |-  ( ( F e. Fin /\ -. Rel F ) -> ( # ` dom F ) < ( # ` F ) )
67 8 66 gtned 
 |-  ( ( F e. Fin /\ -. Rel F ) -> ( # ` F ) =/= ( # ` dom F ) )
68 67 ex 
 |-  ( F e. Fin -> ( -. Rel F -> ( # ` F ) =/= ( # ` dom F ) ) )
69 68 necon4bd 
 |-  ( F e. Fin -> ( ( # ` F ) = ( # ` dom F ) -> Rel F ) )
70 69 imp 
 |-  ( ( F e. Fin /\ ( # ` F ) = ( # ` dom F ) ) -> Rel F )
71 2nalexn 
 |-  ( -. A. x A. y A. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> y = z ) <-> E. x E. y -. A. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> y = z ) )
72 df-ne 
 |-  ( y =/= z <-> -. y = z )
73 72 anbi2i 
 |-  ( ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) <-> ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ -. y = z ) )
74 annim 
 |-  ( ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ -. y = z ) <-> -. ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> y = z ) )
75 73 74 bitri 
 |-  ( ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) <-> -. ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> y = z ) )
76 75 exbii 
 |-  ( E. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) <-> E. z -. ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> y = z ) )
77 exnal 
 |-  ( E. z -. ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> y = z ) <-> -. A. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> y = z ) )
78 76 77 bitr2i 
 |-  ( -. A. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> y = z ) <-> E. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) )
79 78 2exbii 
 |-  ( E. x E. y -. A. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> y = z ) <-> E. x E. y E. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) )
80 71 79 bitri 
 |-  ( -. A. x A. y A. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> y = z ) <-> E. x E. y E. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) )
81 7 adantr 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( # ` dom F ) e. RR )
82 2re 
 |-  2 e. RR
83 diffi 
 |-  ( F e. Fin -> ( F \ { <. x , y >. , <. x , z >. } ) e. Fin )
84 dmfi 
 |-  ( ( F \ { <. x , y >. , <. x , z >. } ) e. Fin -> dom ( F \ { <. x , y >. , <. x , z >. } ) e. Fin )
85 83 84 syl 
 |-  ( F e. Fin -> dom ( F \ { <. x , y >. , <. x , z >. } ) e. Fin )
86 hashcl 
 |-  ( dom ( F \ { <. x , y >. , <. x , z >. } ) e. Fin -> ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) e. NN0 )
87 85 86 syl 
 |-  ( F e. Fin -> ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) e. NN0 )
88 87 nn0red 
 |-  ( F e. Fin -> ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) e. RR )
89 88 adantr 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) e. RR )
90 readdcl 
 |-  ( ( 2 e. RR /\ ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) e. RR ) -> ( 2 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) e. RR )
91 82 89 90 sylancr 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( 2 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) e. RR )
92 hashcl 
 |-  ( F e. Fin -> ( # ` F ) e. NN0 )
93 92 nn0red 
 |-  ( F e. Fin -> ( # ` F ) e. RR )
94 93 adantr 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( # ` F ) e. RR )
95 1re 
 |-  1 e. RR
96 readdcl 
 |-  ( ( 1 e. RR /\ ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) e. RR ) -> ( 1 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) e. RR )
97 95 88 96 sylancr 
 |-  ( F e. Fin -> ( 1 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) e. RR )
98 97 adantr 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( 1 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) e. RR )
99 82 88 90 sylancr 
 |-  ( F e. Fin -> ( 2 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) e. RR )
100 99 adantr 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( 2 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) e. RR )
101 opex 
 |-  <. x , y >. e. _V
102 opex 
 |-  <. x , z >. e. _V
103 101 102 prss 
 |-  ( ( <. x , y >. e. F /\ <. x , z >. e. F ) <-> { <. x , y >. , <. x , z >. } C_ F )
104 undif 
 |-  ( { <. x , y >. , <. x , z >. } C_ F <-> ( { <. x , y >. , <. x , z >. } u. ( F \ { <. x , y >. , <. x , z >. } ) ) = F )
105 103 104 sylbb 
 |-  ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> ( { <. x , y >. , <. x , z >. } u. ( F \ { <. x , y >. , <. x , z >. } ) ) = F )
106 105 dmeqd 
 |-  ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> dom ( { <. x , y >. , <. x , z >. } u. ( F \ { <. x , y >. , <. x , z >. } ) ) = dom F )
107 dmun 
 |-  dom ( { <. x , y >. , <. x , z >. } u. ( F \ { <. x , y >. , <. x , z >. } ) ) = ( dom { <. x , y >. , <. x , z >. } u. dom ( F \ { <. x , y >. , <. x , z >. } ) )
108 106 107 eqtr3di 
 |-  ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> dom F = ( dom { <. x , y >. , <. x , z >. } u. dom ( F \ { <. x , y >. , <. x , z >. } ) ) )
109 vex 
 |-  y e. _V
110 vex 
 |-  z e. _V
111 109 110 dmprop 
 |-  dom { <. x , y >. , <. x , z >. } = { x , x }
112 dfsn2 
 |-  { x } = { x , x }
113 111 112 eqtr4i 
 |-  dom { <. x , y >. , <. x , z >. } = { x }
114 113 uneq1i 
 |-  ( dom { <. x , y >. , <. x , z >. } u. dom ( F \ { <. x , y >. , <. x , z >. } ) ) = ( { x } u. dom ( F \ { <. x , y >. , <. x , z >. } ) )
115 108 114 eqtrdi 
 |-  ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> dom F = ( { x } u. dom ( F \ { <. x , y >. , <. x , z >. } ) ) )
116 115 fveq2d 
 |-  ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> ( # ` dom F ) = ( # ` ( { x } u. dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
117 116 ad2antrl 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( # ` dom F ) = ( # ` ( { x } u. dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
118 hashun2 
 |-  ( ( { x } e. Fin /\ dom ( F \ { <. x , y >. , <. x , z >. } ) e. Fin ) -> ( # ` ( { x } u. dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) <_ ( ( # ` { x } ) + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
119 46 85 118 sylancr 
 |-  ( F e. Fin -> ( # ` ( { x } u. dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) <_ ( ( # ` { x } ) + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
120 52 oveq1i 
 |-  ( ( # ` { x } ) + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) = ( 1 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) )
121 119 120 breqtrdi 
 |-  ( F e. Fin -> ( # ` ( { x } u. dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) <_ ( 1 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
122 121 adantr 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( # ` ( { x } u. dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) <_ ( 1 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
123 117 122 eqbrtrd 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( # ` dom F ) <_ ( 1 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
124 1lt2 
 |-  1 < 2
125 ltadd1 
 |-  ( ( 1 e. RR /\ 2 e. RR /\ ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) e. RR ) -> ( 1 < 2 <-> ( 1 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) < ( 2 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) ) )
126 95 82 88 125 mp3an12i 
 |-  ( F e. Fin -> ( 1 < 2 <-> ( 1 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) < ( 2 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) ) )
127 124 126 mpbii 
 |-  ( F e. Fin -> ( 1 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) < ( 2 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
128 127 adantr 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( 1 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) < ( 2 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
129 81 98 100 123 128 lelttrd 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( # ` dom F ) < ( 2 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
130 fidomdm 
 |-  ( ( F \ { <. x , y >. , <. x , z >. } ) e. Fin -> dom ( F \ { <. x , y >. , <. x , z >. } ) ~<_ ( F \ { <. x , y >. , <. x , z >. } ) )
131 83 130 syl 
 |-  ( F e. Fin -> dom ( F \ { <. x , y >. , <. x , z >. } ) ~<_ ( F \ { <. x , y >. , <. x , z >. } ) )
132 hashdom 
 |-  ( ( dom ( F \ { <. x , y >. , <. x , z >. } ) e. Fin /\ ( F \ { <. x , y >. , <. x , z >. } ) e. Fin ) -> ( ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) <_ ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) <-> dom ( F \ { <. x , y >. , <. x , z >. } ) ~<_ ( F \ { <. x , y >. , <. x , z >. } ) ) )
133 85 83 132 syl2anc 
 |-  ( F e. Fin -> ( ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) <_ ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) <-> dom ( F \ { <. x , y >. , <. x , z >. } ) ~<_ ( F \ { <. x , y >. , <. x , z >. } ) ) )
134 131 133 mpbird 
 |-  ( F e. Fin -> ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) <_ ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) )
135 hashcl 
 |-  ( ( F \ { <. x , y >. , <. x , z >. } ) e. Fin -> ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) e. NN0 )
136 83 135 syl 
 |-  ( F e. Fin -> ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) e. NN0 )
137 136 nn0red 
 |-  ( F e. Fin -> ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) e. RR )
138 leadd2 
 |-  ( ( ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) e. RR /\ ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) e. RR /\ 2 e. RR ) -> ( ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) <_ ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) <-> ( 2 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) <_ ( 2 + ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) ) ) )
139 82 138 mp3an3 
 |-  ( ( ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) e. RR /\ ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) e. RR ) -> ( ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) <_ ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) <-> ( 2 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) <_ ( 2 + ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) ) ) )
140 88 137 139 syl2anc 
 |-  ( F e. Fin -> ( ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) <_ ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) <-> ( 2 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) <_ ( 2 + ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) ) ) )
141 134 140 mpbid 
 |-  ( F e. Fin -> ( 2 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) <_ ( 2 + ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
142 141 adantr 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( 2 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) <_ ( 2 + ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
143 prfi 
 |-  { <. x , y >. , <. x , z >. } e. Fin
144 disjdif 
 |-  ( { <. x , y >. , <. x , z >. } i^i ( F \ { <. x , y >. , <. x , z >. } ) ) = (/)
145 hashun 
 |-  ( ( { <. x , y >. , <. x , z >. } e. Fin /\ ( F \ { <. x , y >. , <. x , z >. } ) e. Fin /\ ( { <. x , y >. , <. x , z >. } i^i ( F \ { <. x , y >. , <. x , z >. } ) ) = (/) ) -> ( # ` ( { <. x , y >. , <. x , z >. } u. ( F \ { <. x , y >. , <. x , z >. } ) ) ) = ( ( # ` { <. x , y >. , <. x , z >. } ) + ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
146 143 144 145 mp3an13 
 |-  ( ( F \ { <. x , y >. , <. x , z >. } ) e. Fin -> ( # ` ( { <. x , y >. , <. x , z >. } u. ( F \ { <. x , y >. , <. x , z >. } ) ) ) = ( ( # ` { <. x , y >. , <. x , z >. } ) + ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
147 83 146 syl 
 |-  ( F e. Fin -> ( # ` ( { <. x , y >. , <. x , z >. } u. ( F \ { <. x , y >. , <. x , z >. } ) ) ) = ( ( # ` { <. x , y >. , <. x , z >. } ) + ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
148 147 adantr 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( # ` ( { <. x , y >. , <. x , z >. } u. ( F \ { <. x , y >. , <. x , z >. } ) ) ) = ( ( # ` { <. x , y >. , <. x , z >. } ) + ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
149 105 fveq2d 
 |-  ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> ( # ` ( { <. x , y >. , <. x , z >. } u. ( F \ { <. x , y >. , <. x , z >. } ) ) ) = ( # ` F ) )
150 149 ad2antrl 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( # ` ( { <. x , y >. , <. x , z >. } u. ( F \ { <. x , y >. , <. x , z >. } ) ) ) = ( # ` F ) )
151 vex 
 |-  x e. _V
152 151 109 opth 
 |-  ( <. x , y >. = <. x , z >. <-> ( x = x /\ y = z ) )
153 152 simprbi 
 |-  ( <. x , y >. = <. x , z >. -> y = z )
154 153 necon3i 
 |-  ( y =/= z -> <. x , y >. =/= <. x , z >. )
155 hashprg 
 |-  ( ( <. x , y >. e. _V /\ <. x , z >. e. _V ) -> ( <. x , y >. =/= <. x , z >. <-> ( # ` { <. x , y >. , <. x , z >. } ) = 2 ) )
156 101 102 155 mp2an 
 |-  ( <. x , y >. =/= <. x , z >. <-> ( # ` { <. x , y >. , <. x , z >. } ) = 2 )
157 154 156 sylib 
 |-  ( y =/= z -> ( # ` { <. x , y >. , <. x , z >. } ) = 2 )
158 157 oveq1d 
 |-  ( y =/= z -> ( ( # ` { <. x , y >. , <. x , z >. } ) + ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) ) = ( 2 + ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
159 158 ad2antll 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( ( # ` { <. x , y >. , <. x , z >. } ) + ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) ) = ( 2 + ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) ) )
160 148 150 159 3eqtr3rd 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( 2 + ( # ` ( F \ { <. x , y >. , <. x , z >. } ) ) ) = ( # ` F ) )
161 142 160 breqtrd 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( 2 + ( # ` dom ( F \ { <. x , y >. , <. x , z >. } ) ) ) <_ ( # ` F ) )
162 81 91 94 129 161 ltletrd 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( # ` dom F ) < ( # ` F ) )
163 81 162 gtned 
 |-  ( ( F e. Fin /\ ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) ) -> ( # ` F ) =/= ( # ` dom F ) )
164 163 ex 
 |-  ( F e. Fin -> ( ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) -> ( # ` F ) =/= ( # ` dom F ) ) )
165 164 exlimdv 
 |-  ( F e. Fin -> ( E. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) -> ( # ` F ) =/= ( # ` dom F ) ) )
166 165 exlimdvv 
 |-  ( F e. Fin -> ( E. x E. y E. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) /\ y =/= z ) -> ( # ` F ) =/= ( # ` dom F ) ) )
167 80 166 biimtrid 
 |-  ( F e. Fin -> ( -. A. x A. y A. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> y = z ) -> ( # ` F ) =/= ( # ` dom F ) ) )
168 167 necon4bd 
 |-  ( F e. Fin -> ( ( # ` F ) = ( # ` dom F ) -> A. x A. y A. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> y = z ) ) )
169 168 imp 
 |-  ( ( F e. Fin /\ ( # ` F ) = ( # ` dom F ) ) -> A. x A. y A. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> y = z ) )
170 dffun4 
 |-  ( Fun F <-> ( Rel F /\ A. x A. y A. z ( ( <. x , y >. e. F /\ <. x , z >. e. F ) -> y = z ) ) )
171 70 169 170 sylanbrc 
 |-  ( ( F e. Fin /\ ( # ` F ) = ( # ` dom F ) ) -> Fun F )
172 171 ex 
 |-  ( F e. Fin -> ( ( # ` F ) = ( # ` dom F ) -> Fun F ) )
173 3 172 impbid2 
 |-  ( F e. Fin -> ( Fun F <-> ( # ` F ) = ( # ` dom F ) ) )