Metamath Proof Explorer

Theorem domunsncan

Description: A singleton cancellation law for dominance. (Contributed by Stefan O'Rear, 19-Feb-2015) (Revised by Stefan O'Rear, 5-May-2015)

Ref Expression
Hypotheses domunsncan.a 
|- A e. _V
domunsncan.b 
|- B e. _V
Assertion domunsncan 
|- ( ( -. A e. X /\ -. B e. Y ) -> ( ( { A } u. X ) ~<_ ( { B } u. Y ) <-> X ~<_ Y ) )

Proof

Step Hyp Ref Expression
1 domunsncan.a 
 |-  A e. _V
2 domunsncan.b 
 |-  B e. _V
3 ssun2 
 |-  Y C_ ( { B } u. Y )
4 reldom 
 |-  Rel ~<_
5 4 brrelex2i 
 |-  ( ( { A } u. X ) ~<_ ( { B } u. Y ) -> ( { B } u. Y ) e. _V )
6 5 adantl 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( { A } u. X ) ~<_ ( { B } u. Y ) ) -> ( { B } u. Y ) e. _V )
7 ssexg 
 |-  ( ( Y C_ ( { B } u. Y ) /\ ( { B } u. Y ) e. _V ) -> Y e. _V )
8 3 6 7 sylancr 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( { A } u. X ) ~<_ ( { B } u. Y ) ) -> Y e. _V )
9 brdomi 
 |-  ( ( { A } u. X ) ~<_ ( { B } u. Y ) -> E. f f : ( { A } u. X ) -1-1-> ( { B } u. Y ) )
10 vex 
 |-  f e. _V
11 10 resex 
 |-  ( f |` ( ( { A } u. X ) \ { A } ) ) e. _V
12 simprr 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> f : ( { A } u. X ) -1-1-> ( { B } u. Y ) )
13 difss 
 |-  ( ( { A } u. X ) \ { A } ) C_ ( { A } u. X )
14 f1ores 
 |-  ( ( f : ( { A } u. X ) -1-1-> ( { B } u. Y ) /\ ( ( { A } u. X ) \ { A } ) C_ ( { A } u. X ) ) -> ( f |` ( ( { A } u. X ) \ { A } ) ) : ( ( { A } u. X ) \ { A } ) -1-1-onto-> ( f " ( ( { A } u. X ) \ { A } ) ) )
15 12 13 14 sylancl 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( f |` ( ( { A } u. X ) \ { A } ) ) : ( ( { A } u. X ) \ { A } ) -1-1-onto-> ( f " ( ( { A } u. X ) \ { A } ) ) )
16 f1oen3g 
 |-  ( ( ( f |` ( ( { A } u. X ) \ { A } ) ) e. _V /\ ( f |` ( ( { A } u. X ) \ { A } ) ) : ( ( { A } u. X ) \ { A } ) -1-1-onto-> ( f " ( ( { A } u. X ) \ { A } ) ) ) -> ( ( { A } u. X ) \ { A } ) ~~ ( f " ( ( { A } u. X ) \ { A } ) ) )
17 11 15 16 sylancr 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( ( { A } u. X ) \ { A } ) ~~ ( f " ( ( { A } u. X ) \ { A } ) ) )
18 df-f1 
 |-  ( f : ( { A } u. X ) -1-1-> ( { B } u. Y ) <-> ( f : ( { A } u. X ) --> ( { B } u. Y ) /\ Fun `' f ) )
19 imadif 
 |-  ( Fun `' f -> ( f " ( ( { A } u. X ) \ { A } ) ) = ( ( f " ( { A } u. X ) ) \ ( f " { A } ) ) )
20 18 19 simplbiim 
 |-  ( f : ( { A } u. X ) -1-1-> ( { B } u. Y ) -> ( f " ( ( { A } u. X ) \ { A } ) ) = ( ( f " ( { A } u. X ) ) \ ( f " { A } ) ) )
21 20 ad2antll 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( f " ( ( { A } u. X ) \ { A } ) ) = ( ( f " ( { A } u. X ) ) \ ( f " { A } ) ) )
22 snex 
 |-  { B } e. _V
23 simprl 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> Y e. _V )
24 unexg 
 |-  ( ( { B } e. _V /\ Y e. _V ) -> ( { B } u. Y ) e. _V )
25 22 23 24 sylancr 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( { B } u. Y ) e. _V )
26 25 difexd 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( ( { B } u. Y ) \ { ( f ` A ) } ) e. _V )
27 f1f 
 |-  ( f : ( { A } u. X ) -1-1-> ( { B } u. Y ) -> f : ( { A } u. X ) --> ( { B } u. Y ) )
28 fimass 
 |-  ( f : ( { A } u. X ) --> ( { B } u. Y ) -> ( f " ( { A } u. X ) ) C_ ( { B } u. Y ) )
29 27 28 syl 
 |-  ( f : ( { A } u. X ) -1-1-> ( { B } u. Y ) -> ( f " ( { A } u. X ) ) C_ ( { B } u. Y ) )
30 29 ad2antll 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( f " ( { A } u. X ) ) C_ ( { B } u. Y ) )
31 30 ssdifd 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( ( f " ( { A } u. X ) ) \ ( f " { A } ) ) C_ ( ( { B } u. Y ) \ ( f " { A } ) ) )
32 f1fn 
 |-  ( f : ( { A } u. X ) -1-1-> ( { B } u. Y ) -> f Fn ( { A } u. X ) )
33 32 ad2antll 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> f Fn ( { A } u. X ) )
34 1 snid 
 |-  A e. { A }
35 elun1 
 |-  ( A e. { A } -> A e. ( { A } u. X ) )
36 34 35 ax-mp 
 |-  A e. ( { A } u. X )
37 fnsnfv 
 |-  ( ( f Fn ( { A } u. X ) /\ A e. ( { A } u. X ) ) -> { ( f ` A ) } = ( f " { A } ) )
38 33 36 37 sylancl 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> { ( f ` A ) } = ( f " { A } ) )
39 38 difeq2d 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( ( { B } u. Y ) \ { ( f ` A ) } ) = ( ( { B } u. Y ) \ ( f " { A } ) ) )
40 31 39 sseqtrrd 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( ( f " ( { A } u. X ) ) \ ( f " { A } ) ) C_ ( ( { B } u. Y ) \ { ( f ` A ) } ) )
41 ssdomg 
 |-  ( ( ( { B } u. Y ) \ { ( f ` A ) } ) e. _V -> ( ( ( f " ( { A } u. X ) ) \ ( f " { A } ) ) C_ ( ( { B } u. Y ) \ { ( f ` A ) } ) -> ( ( f " ( { A } u. X ) ) \ ( f " { A } ) ) ~<_ ( ( { B } u. Y ) \ { ( f ` A ) } ) ) )
42 26 40 41 sylc 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( ( f " ( { A } u. X ) ) \ ( f " { A } ) ) ~<_ ( ( { B } u. Y ) \ { ( f ` A ) } ) )
43 ffvelcdm 
 |-  ( ( f : ( { A } u. X ) --> ( { B } u. Y ) /\ A e. ( { A } u. X ) ) -> ( f ` A ) e. ( { B } u. Y ) )
44 27 36 43 sylancl 
 |-  ( f : ( { A } u. X ) -1-1-> ( { B } u. Y ) -> ( f ` A ) e. ( { B } u. Y ) )
45 44 ad2antll 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( f ` A ) e. ( { B } u. Y ) )
46 2 snid 
 |-  B e. { B }
47 elun1 
 |-  ( B e. { B } -> B e. ( { B } u. Y ) )
48 46 47 mp1i 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> B e. ( { B } u. Y ) )
49 difsnen 
 |-  ( ( ( { B } u. Y ) e. _V /\ ( f ` A ) e. ( { B } u. Y ) /\ B e. ( { B } u. Y ) ) -> ( ( { B } u. Y ) \ { ( f ` A ) } ) ~~ ( ( { B } u. Y ) \ { B } ) )
50 25 45 48 49 syl3anc 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( ( { B } u. Y ) \ { ( f ` A ) } ) ~~ ( ( { B } u. Y ) \ { B } ) )
51 domentr 
 |-  ( ( ( ( f " ( { A } u. X ) ) \ ( f " { A } ) ) ~<_ ( ( { B } u. Y ) \ { ( f ` A ) } ) /\ ( ( { B } u. Y ) \ { ( f ` A ) } ) ~~ ( ( { B } u. Y ) \ { B } ) ) -> ( ( f " ( { A } u. X ) ) \ ( f " { A } ) ) ~<_ ( ( { B } u. Y ) \ { B } ) )
52 42 50 51 syl2anc 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( ( f " ( { A } u. X ) ) \ ( f " { A } ) ) ~<_ ( ( { B } u. Y ) \ { B } ) )
53 21 52 eqbrtrd 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( f " ( ( { A } u. X ) \ { A } ) ) ~<_ ( ( { B } u. Y ) \ { B } ) )
54 endomtr 
 |-  ( ( ( ( { A } u. X ) \ { A } ) ~~ ( f " ( ( { A } u. X ) \ { A } ) ) /\ ( f " ( ( { A } u. X ) \ { A } ) ) ~<_ ( ( { B } u. Y ) \ { B } ) ) -> ( ( { A } u. X ) \ { A } ) ~<_ ( ( { B } u. Y ) \ { B } ) )
55 17 53 54 syl2anc 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( ( { A } u. X ) \ { A } ) ~<_ ( ( { B } u. Y ) \ { B } ) )
56 uncom 
 |-  ( { A } u. X ) = ( X u. { A } )
57 56 difeq1i 
 |-  ( ( { A } u. X ) \ { A } ) = ( ( X u. { A } ) \ { A } )
58 difun2 
 |-  ( ( X u. { A } ) \ { A } ) = ( X \ { A } )
59 57 58 eqtri 
 |-  ( ( { A } u. X ) \ { A } ) = ( X \ { A } )
60 difsn 
 |-  ( -. A e. X -> ( X \ { A } ) = X )
61 59 60 eqtrid 
 |-  ( -. A e. X -> ( ( { A } u. X ) \ { A } ) = X )
62 61 ad2antrr 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( ( { A } u. X ) \ { A } ) = X )
63 uncom 
 |-  ( { B } u. Y ) = ( Y u. { B } )
64 63 difeq1i 
 |-  ( ( { B } u. Y ) \ { B } ) = ( ( Y u. { B } ) \ { B } )
65 difun2 
 |-  ( ( Y u. { B } ) \ { B } ) = ( Y \ { B } )
66 64 65 eqtri 
 |-  ( ( { B } u. Y ) \ { B } ) = ( Y \ { B } )
67 difsn 
 |-  ( -. B e. Y -> ( Y \ { B } ) = Y )
68 66 67 eqtrid 
 |-  ( -. B e. Y -> ( ( { B } u. Y ) \ { B } ) = Y )
69 68 ad2antlr 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> ( ( { B } u. Y ) \ { B } ) = Y )
70 55 62 69 3brtr3d 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( Y e. _V /\ f : ( { A } u. X ) -1-1-> ( { B } u. Y ) ) ) -> X ~<_ Y )
71 70 expr 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ Y e. _V ) -> ( f : ( { A } u. X ) -1-1-> ( { B } u. Y ) -> X ~<_ Y ) )
72 71 exlimdv 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ Y e. _V ) -> ( E. f f : ( { A } u. X ) -1-1-> ( { B } u. Y ) -> X ~<_ Y ) )
73 9 72 syl5 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ Y e. _V ) -> ( ( { A } u. X ) ~<_ ( { B } u. Y ) -> X ~<_ Y ) )
74 73 impancom 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( { A } u. X ) ~<_ ( { B } u. Y ) ) -> ( Y e. _V -> X ~<_ Y ) )
75 8 74 mpd 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ ( { A } u. X ) ~<_ ( { B } u. Y ) ) -> X ~<_ Y )
76 en2sn 
 |-  ( ( A e. _V /\ B e. _V ) -> { A } ~~ { B } )
77 1 2 76 mp2an 
 |-  { A } ~~ { B }
78 endom 
 |-  ( { A } ~~ { B } -> { A } ~<_ { B } )
79 77 78 mp1i 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ X ~<_ Y ) -> { A } ~<_ { B } )
80 simpr 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ X ~<_ Y ) -> X ~<_ Y )
81 incom 
 |-  ( { B } i^i Y ) = ( Y i^i { B } )
82 disjsn 
 |-  ( ( Y i^i { B } ) = (/) <-> -. B e. Y )
83 82 biimpri 
 |-  ( -. B e. Y -> ( Y i^i { B } ) = (/) )
84 81 83 eqtrid 
 |-  ( -. B e. Y -> ( { B } i^i Y ) = (/) )
85 84 ad2antlr 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ X ~<_ Y ) -> ( { B } i^i Y ) = (/) )
86 undom 
 |-  ( ( ( { A } ~<_ { B } /\ X ~<_ Y ) /\ ( { B } i^i Y ) = (/) ) -> ( { A } u. X ) ~<_ ( { B } u. Y ) )
87 79 80 85 86 syl21anc 
 |-  ( ( ( -. A e. X /\ -. B e. Y ) /\ X ~<_ Y ) -> ( { A } u. X ) ~<_ ( { B } u. Y ) )
88 75 87 impbida 
 |-  ( ( -. A e. X /\ -. B e. Y ) -> ( ( { A } u. X ) ~<_ ( { B } u. Y ) <-> X ~<_ Y ) )