MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  hashdom Unicode version

Theorem hashdom 11582
Description: Dominance relation for the size function. (Contributed by Mario Carneiro, 22-Sep-2013.) (Revised by Mario Carneiro, 22-Apr-2015.)
Assertion
Ref Expression
hashdom  |-  ( ( A  e.  Fin  /\  B  e.  V )  ->  ( ( # `  A
)  <_  ( # `  B
)  <->  A  ~<_  B )
)

Proof of Theorem hashdom
Dummy variables  x  f  y are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 fzfi 11240 . . . . . . . 8  |-  ( 1 ... ( ( # `  B )  -  ( # `
 A ) ) )  e.  Fin
2 ficardom 7783 . . . . . . . 8  |-  ( ( 1 ... ( (
# `  B )  -  ( # `  A
) ) )  e. 
Fin  ->  ( card `  (
1 ... ( ( # `  B )  -  ( # `
 A ) ) ) )  e.  om )
31, 2ax-mp 8 . . . . . . 7  |-  ( card `  ( 1 ... (
( # `  B )  -  ( # `  A
) ) ) )  e.  om
4 eqid 2389 . . . . . . . . . . . . . 14  |-  ( rec ( ( x  e. 
_V  |->  ( x  + 
1 ) ) ,  0 )  |`  om )  =  ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om )
54hashgval 11550 . . . . . . . . . . . . 13  |-  ( A  e.  Fin  ->  (
( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( card `  A ) )  =  ( # `  A
) )
65ad2antrr 707 . . . . . . . . . . . 12  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  (
( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( card `  A ) )  =  ( # `  A
) )
74hashgval 11550 . . . . . . . . . . . . . 14  |-  ( ( 1 ... ( (
# `  B )  -  ( # `  A
) ) )  e. 
Fin  ->  ( ( rec ( ( x  e. 
_V  |->  ( x  + 
1 ) ) ,  0 )  |`  om ) `  ( card `  (
1 ... ( ( # `  B )  -  ( # `
 A ) ) ) ) )  =  ( # `  (
1 ... ( ( # `  B )  -  ( # `
 A ) ) ) ) )
81, 7ax-mp 8 . . . . . . . . . . . . 13  |-  ( ( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( card `  ( 1 ... (
( # `  B )  -  ( # `  A
) ) ) ) )  =  ( # `  ( 1 ... (
( # `  B )  -  ( # `  A
) ) ) )
9 hashcl 11568 . . . . . . . . . . . . . . . 16  |-  ( A  e.  Fin  ->  ( # `
 A )  e. 
NN0 )
109ad2antrr 707 . . . . . . . . . . . . . . 15  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  ( # `
 A )  e. 
NN0 )
11 hashcl 11568 . . . . . . . . . . . . . . . 16  |-  ( B  e.  Fin  ->  ( # `
 B )  e. 
NN0 )
1211ad2antlr 708 . . . . . . . . . . . . . . 15  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  ( # `
 B )  e. 
NN0 )
13 simpr 448 . . . . . . . . . . . . . . 15  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  ( # `
 A )  <_ 
( # `  B ) )
14 nn0sub2 10269 . . . . . . . . . . . . . . 15  |-  ( ( ( # `  A
)  e.  NN0  /\  ( # `  B )  e.  NN0  /\  ( # `
 A )  <_ 
( # `  B ) )  ->  ( ( # `
 B )  -  ( # `  A ) )  e.  NN0 )
1510, 12, 13, 14syl3anc 1184 . . . . . . . . . . . . . 14  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  (
( # `  B )  -  ( # `  A
) )  e.  NN0 )
16 hashfz1 11559 . . . . . . . . . . . . . 14  |-  ( ( ( # `  B
)  -  ( # `  A ) )  e. 
NN0  ->  ( # `  (
1 ... ( ( # `  B )  -  ( # `
 A ) ) ) )  =  ( ( # `  B
)  -  ( # `  A ) ) )
1715, 16syl 16 . . . . . . . . . . . . 13  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  ( # `
 ( 1 ... ( ( # `  B
)  -  ( # `  A ) ) ) )  =  ( (
# `  B )  -  ( # `  A
) ) )
188, 17syl5eq 2433 . . . . . . . . . . . 12  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  (
( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( card `  ( 1 ... ( ( # `  B
)  -  ( # `  A ) ) ) ) )  =  ( ( # `  B
)  -  ( # `  A ) ) )
196, 18oveq12d 6040 . . . . . . . . . . 11  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  (
( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( card `  A
) )  +  ( ( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( card `  ( 1 ... ( ( # `  B
)  -  ( # `  A ) ) ) ) ) )  =  ( ( # `  A
)  +  ( (
# `  B )  -  ( # `  A
) ) ) )
209nn0cnd 10210 . . . . . . . . . . . . 13  |-  ( A  e.  Fin  ->  ( # `
 A )  e.  CC )
2111nn0cnd 10210 . . . . . . . . . . . . 13  |-  ( B  e.  Fin  ->  ( # `
 B )  e.  CC )
22 pncan3 9247 . . . . . . . . . . . . 13  |-  ( ( ( # `  A
)  e.  CC  /\  ( # `  B )  e.  CC )  -> 
( ( # `  A
)  +  ( (
# `  B )  -  ( # `  A
) ) )  =  ( # `  B
) )
2320, 21, 22syl2an 464 . . . . . . . . . . . 12  |-  ( ( A  e.  Fin  /\  B  e.  Fin )  ->  ( ( # `  A
)  +  ( (
# `  B )  -  ( # `  A
) ) )  =  ( # `  B
) )
2423adantr 452 . . . . . . . . . . 11  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  (
( # `  A )  +  ( ( # `  B )  -  ( # `
 A ) ) )  =  ( # `  B ) )
2519, 24eqtrd 2421 . . . . . . . . . 10  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  (
( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( card `  A
) )  +  ( ( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( card `  ( 1 ... ( ( # `  B
)  -  ( # `  A ) ) ) ) ) )  =  ( # `  B
) )
26 ficardom 7783 . . . . . . . . . . . 12  |-  ( A  e.  Fin  ->  ( card `  A )  e. 
om )
2726ad2antrr 707 . . . . . . . . . . 11  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  ( card `  A )  e. 
om )
284hashgadd 11580 . . . . . . . . . . 11  |-  ( ( ( card `  A
)  e.  om  /\  ( card `  ( 1 ... ( ( # `  B
)  -  ( # `  A ) ) ) )  e.  om )  ->  ( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( ( card `  A
)  +o  ( card `  ( 1 ... (
( # `  B )  -  ( # `  A
) ) ) ) ) )  =  ( ( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( card `  A
) )  +  ( ( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( card `  ( 1 ... ( ( # `  B
)  -  ( # `  A ) ) ) ) ) ) )
2927, 3, 28sylancl 644 . . . . . . . . . 10  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  (
( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  (
( card `  A )  +o  ( card `  (
1 ... ( ( # `  B )  -  ( # `
 A ) ) ) ) ) )  =  ( ( ( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( card `  A ) )  +  ( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( card `  (
1 ... ( ( # `  B )  -  ( # `
 A ) ) ) ) ) ) )
304hashgval 11550 . . . . . . . . . . 11  |-  ( B  e.  Fin  ->  (
( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( card `  B ) )  =  ( # `  B
) )
3130ad2antlr 708 . . . . . . . . . 10  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  (
( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( card `  B ) )  =  ( # `  B
) )
3225, 29, 313eqtr4d 2431 . . . . . . . . 9  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  (
( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  (
( card `  A )  +o  ( card `  (
1 ... ( ( # `  B )  -  ( # `
 A ) ) ) ) ) )  =  ( ( rec ( ( x  e. 
_V  |->  ( x  + 
1 ) ) ,  0 )  |`  om ) `  ( card `  B
) ) )
3332fveq2d 5674 . . . . . . . 8  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  ( `' ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( ( card `  A
)  +o  ( card `  ( 1 ... (
( # `  B )  -  ( # `  A
) ) ) ) ) ) )  =  ( `' ( rec ( ( x  e. 
_V  |->  ( x  + 
1 ) ) ,  0 )  |`  om ) `  ( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( card `  B
) ) ) )
344hashgf1o 11239 . . . . . . . . 9  |-  ( rec ( ( x  e. 
_V  |->  ( x  + 
1 ) ) ,  0 )  |`  om ) : om -1-1-onto-> NN0
35 nnacl 6792 . . . . . . . . . 10  |-  ( ( ( card `  A
)  e.  om  /\  ( card `  ( 1 ... ( ( # `  B
)  -  ( # `  A ) ) ) )  e.  om )  ->  ( ( card `  A
)  +o  ( card `  ( 1 ... (
( # `  B )  -  ( # `  A
) ) ) ) )  e.  om )
3627, 3, 35sylancl 644 . . . . . . . . 9  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  (
( card `  A )  +o  ( card `  (
1 ... ( ( # `  B )  -  ( # `
 A ) ) ) ) )  e. 
om )
37 f1ocnvfv1 5955 . . . . . . . . 9  |-  ( ( ( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) : om -1-1-onto-> NN0  /\  ( ( card `  A
)  +o  ( card `  ( 1 ... (
( # `  B )  -  ( # `  A
) ) ) ) )  e.  om )  ->  ( `' ( rec ( ( x  e. 
_V  |->  ( x  + 
1 ) ) ,  0 )  |`  om ) `  ( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( ( card `  A
)  +o  ( card `  ( 1 ... (
( # `  B )  -  ( # `  A
) ) ) ) ) ) )  =  ( ( card `  A
)  +o  ( card `  ( 1 ... (
( # `  B )  -  ( # `  A
) ) ) ) ) )
3834, 36, 37sylancr 645 . . . . . . . 8  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  ( `' ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( ( card `  A
)  +o  ( card `  ( 1 ... (
( # `  B )  -  ( # `  A
) ) ) ) ) ) )  =  ( ( card `  A
)  +o  ( card `  ( 1 ... (
( # `  B )  -  ( # `  A
) ) ) ) ) )
39 ficardom 7783 . . . . . . . . . 10  |-  ( B  e.  Fin  ->  ( card `  B )  e. 
om )
4039ad2antlr 708 . . . . . . . . 9  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  ( card `  B )  e. 
om )
41 f1ocnvfv1 5955 . . . . . . . . 9  |-  ( ( ( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) : om -1-1-onto-> NN0  /\  ( card `  B
)  e.  om )  ->  ( `' ( rec ( ( x  e. 
_V  |->  ( x  + 
1 ) ) ,  0 )  |`  om ) `  ( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( card `  B
) ) )  =  ( card `  B
) )
4234, 40, 41sylancr 645 . . . . . . . 8  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  ( `' ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( card `  B
) ) )  =  ( card `  B
) )
4333, 38, 423eqtr3d 2429 . . . . . . 7  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  (
( card `  A )  +o  ( card `  (
1 ... ( ( # `  B )  -  ( # `
 A ) ) ) ) )  =  ( card `  B
) )
44 oveq2 6030 . . . . . . . . 9  |-  ( y  =  ( card `  (
1 ... ( ( # `  B )  -  ( # `
 A ) ) ) )  ->  (
( card `  A )  +o  y )  =  ( ( card `  A
)  +o  ( card `  ( 1 ... (
( # `  B )  -  ( # `  A
) ) ) ) ) )
4544eqeq1d 2397 . . . . . . . 8  |-  ( y  =  ( card `  (
1 ... ( ( # `  B )  -  ( # `
 A ) ) ) )  ->  (
( ( card `  A
)  +o  y )  =  ( card `  B
)  <->  ( ( card `  A )  +o  ( card `  ( 1 ... ( ( # `  B
)  -  ( # `  A ) ) ) ) )  =  (
card `  B )
) )
4645rspcev 2997 . . . . . . 7  |-  ( ( ( card `  (
1 ... ( ( # `  B )  -  ( # `
 A ) ) ) )  e.  om  /\  ( ( card `  A
)  +o  ( card `  ( 1 ... (
( # `  B )  -  ( # `  A
) ) ) ) )  =  ( card `  B ) )  ->  E. y  e.  om  ( ( card `  A
)  +o  y )  =  ( card `  B
) )
473, 43, 46sylancr 645 . . . . . 6  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  ( # `  A
)  <_  ( # `  B
) )  ->  E. y  e.  om  ( ( card `  A )  +o  y
)  =  ( card `  B ) )
4847ex 424 . . . . 5  |-  ( ( A  e.  Fin  /\  B  e.  Fin )  ->  ( ( # `  A
)  <_  ( # `  B
)  ->  E. y  e.  om  ( ( card `  A )  +o  y
)  =  ( card `  B ) ) )
49 cardnn 7785 . . . . . . . . . 10  |-  ( y  e.  om  ->  ( card `  y )  =  y )
5049adantl 453 . . . . . . . . 9  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  y  e.  om )  ->  ( card `  y
)  =  y )
5150oveq2d 6038 . . . . . . . 8  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  y  e.  om )  ->  ( ( card `  A )  +o  ( card `  y ) )  =  ( ( card `  A )  +o  y
) )
5251eqeq1d 2397 . . . . . . 7  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  y  e.  om )  ->  ( ( (
card `  A )  +o  ( card `  y
) )  =  (
card `  B )  <->  ( ( card `  A
)  +o  y )  =  ( card `  B
) ) )
53 fveq2 5670 . . . . . . . 8  |-  ( ( ( card `  A
)  +o  ( card `  y ) )  =  ( card `  B
)  ->  ( ( rec ( ( x  e. 
_V  |->  ( x  + 
1 ) ) ,  0 )  |`  om ) `  ( ( card `  A
)  +o  ( card `  y ) ) )  =  ( ( rec ( ( x  e. 
_V  |->  ( x  + 
1 ) ) ,  0 )  |`  om ) `  ( card `  B
) ) )
54 nnfi 7237 . . . . . . . . 9  |-  ( y  e.  om  ->  y  e.  Fin )
55 ficardom 7783 . . . . . . . . . . . . . 14  |-  ( y  e.  Fin  ->  ( card `  y )  e. 
om )
564hashgadd 11580 . . . . . . . . . . . . . 14  |-  ( ( ( card `  A
)  e.  om  /\  ( card `  y )  e.  om )  ->  (
( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  (
( card `  A )  +o  ( card `  y
) ) )  =  ( ( ( rec ( ( x  e. 
_V  |->  ( x  + 
1 ) ) ,  0 )  |`  om ) `  ( card `  A
) )  +  ( ( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( card `  y ) ) ) )
5726, 55, 56syl2an 464 . . . . . . . . . . . . 13  |-  ( ( A  e.  Fin  /\  y  e.  Fin )  ->  ( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( ( card `  A
)  +o  ( card `  y ) ) )  =  ( ( ( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( card `  A ) )  +  ( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( card `  y
) ) ) )
584hashgval 11550 . . . . . . . . . . . . . 14  |-  ( y  e.  Fin  ->  (
( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( card `  y ) )  =  ( # `  y
) )
595, 58oveqan12d 6041 . . . . . . . . . . . . 13  |-  ( ( A  e.  Fin  /\  y  e.  Fin )  ->  ( ( ( rec ( ( x  e. 
_V  |->  ( x  + 
1 ) ) ,  0 )  |`  om ) `  ( card `  A
) )  +  ( ( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( card `  y ) ) )  =  ( (
# `  A )  +  ( # `  y
) ) )
6057, 59eqtrd 2421 . . . . . . . . . . . 12  |-  ( ( A  e.  Fin  /\  y  e.  Fin )  ->  ( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( ( card `  A
)  +o  ( card `  y ) ) )  =  ( ( # `  A )  +  (
# `  y )
) )
6160adantlr 696 . . . . . . . . . . 11  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  y  e.  Fin )  ->  ( ( rec ( ( x  e. 
_V  |->  ( x  + 
1 ) ) ,  0 )  |`  om ) `  ( ( card `  A
)  +o  ( card `  y ) ) )  =  ( ( # `  A )  +  (
# `  y )
) )
6230ad2antlr 708 . . . . . . . . . . 11  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  y  e.  Fin )  ->  ( ( rec ( ( x  e. 
_V  |->  ( x  + 
1 ) ) ,  0 )  |`  om ) `  ( card `  B
) )  =  (
# `  B )
)
6361, 62eqeq12d 2403 . . . . . . . . . 10  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  y  e.  Fin )  ->  ( ( ( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( (
card `  A )  +o  ( card `  y
) ) )  =  ( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( card `  B
) )  <->  ( ( # `
 A )  +  ( # `  y
) )  =  (
# `  B )
) )
64 hashcl 11568 . . . . . . . . . . . . . . 15  |-  ( y  e.  Fin  ->  ( # `
 y )  e. 
NN0 )
6564nn0ge0d 10211 . . . . . . . . . . . . . 14  |-  ( y  e.  Fin  ->  0  <_  ( # `  y
) )
6665adantl 453 . . . . . . . . . . . . 13  |-  ( ( A  e.  Fin  /\  y  e.  Fin )  ->  0  <_  ( # `  y
) )
679nn0red 10209 . . . . . . . . . . . . . 14  |-  ( A  e.  Fin  ->  ( # `
 A )  e.  RR )
6864nn0red 10209 . . . . . . . . . . . . . 14  |-  ( y  e.  Fin  ->  ( # `
 y )  e.  RR )
69 addge01 9472 . . . . . . . . . . . . . 14  |-  ( ( ( # `  A
)  e.  RR  /\  ( # `  y )  e.  RR )  -> 
( 0  <_  ( # `
 y )  <->  ( # `  A
)  <_  ( ( # `
 A )  +  ( # `  y
) ) ) )
7067, 68, 69syl2an 464 . . . . . . . . . . . . 13  |-  ( ( A  e.  Fin  /\  y  e.  Fin )  ->  ( 0  <_  ( # `
 y )  <->  ( # `  A
)  <_  ( ( # `
 A )  +  ( # `  y
) ) ) )
7166, 70mpbid 202 . . . . . . . . . . . 12  |-  ( ( A  e.  Fin  /\  y  e.  Fin )  ->  ( # `  A
)  <_  ( ( # `
 A )  +  ( # `  y
) ) )
7271adantlr 696 . . . . . . . . . . 11  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  y  e.  Fin )  ->  ( # `  A
)  <_  ( ( # `
 A )  +  ( # `  y
) ) )
73 breq2 4159 . . . . . . . . . . 11  |-  ( ( ( # `  A
)  +  ( # `  y ) )  =  ( # `  B
)  ->  ( ( # `
 A )  <_ 
( ( # `  A
)  +  ( # `  y ) )  <->  ( # `  A
)  <_  ( # `  B
) ) )
7472, 73syl5ibcom 212 . . . . . . . . . 10  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  y  e.  Fin )  ->  ( ( (
# `  A )  +  ( # `  y
) )  =  (
# `  B )  ->  ( # `  A
)  <_  ( # `  B
) ) )
7563, 74sylbid 207 . . . . . . . . 9  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  y  e.  Fin )  ->  ( ( ( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( (
card `  A )  +o  ( card `  y
) ) )  =  ( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( card `  B
) )  ->  ( # `
 A )  <_ 
( # `  B ) ) )
7654, 75sylan2 461 . . . . . . . 8  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  y  e.  om )  ->  ( ( ( rec ( ( x  e.  _V  |->  ( x  +  1 ) ) ,  0 )  |`  om ) `  ( (
card `  A )  +o  ( card `  y
) ) )  =  ( ( rec (
( x  e.  _V  |->  ( x  +  1
) ) ,  0 )  |`  om ) `  ( card `  B
) )  ->  ( # `
 A )  <_ 
( # `  B ) ) )
7753, 76syl5 30 . . . . . . 7  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  y  e.  om )  ->  ( ( (
card `  A )  +o  ( card `  y
) )  =  (
card `  B )  ->  ( # `  A
)  <_  ( # `  B
) ) )
7852, 77sylbird 227 . . . . . 6  |-  ( ( ( A  e.  Fin  /\  B  e.  Fin )  /\  y  e.  om )  ->  ( ( (
card `  A )  +o  y )  =  (
card `  B )  ->  ( # `  A
)  <_  ( # `  B
) ) )
7978rexlimdva 2775 . . . . 5  |-  ( ( A  e.  Fin  /\  B  e.  Fin )  ->  ( E. y  e. 
om  ( ( card `  A )  +o  y
)  =  ( card `  B )  ->  ( # `
 A )  <_ 
( # `  B ) ) )
8048, 79impbid 184 . . . 4  |-  ( ( A  e.  Fin  /\  B  e.  Fin )  ->  ( ( # `  A
)  <_  ( # `  B
)  <->  E. y  e.  om  ( ( card `  A
)  +o  y )  =  ( card `  B
) ) )
81 nnawordex 6818 . . . . 5  |-  ( ( ( card `  A
)  e.  om  /\  ( card `  B )  e.  om )  ->  (
( card `  A )  C_  ( card `  B
)  <->  E. y  e.  om  ( ( card `  A
)  +o  y )  =  ( card `  B
) ) )
8226, 39, 81syl2an 464 . . . 4  |-  ( ( A  e.  Fin  /\  B  e.  Fin )  ->  ( ( card `  A
)  C_  ( card `  B )  <->  E. y  e.  om  ( ( card `  A )  +o  y
)  =  ( card `  B ) ) )
83 finnum 7770 . . . . 5  |-  ( A  e.  Fin  ->  A  e.  dom  card )
84 finnum 7770 . . . . 5  |-  ( B  e.  Fin  ->  B  e.  dom  card )
85 carddom2 7799 . . . . 5  |-  ( ( A  e.  dom  card  /\  B  e.  dom  card )  ->  ( ( card `  A )  C_  ( card `  B )  <->  A  ~<_  B ) )
8683, 84, 85syl2an 464 . . . 4  |-  ( ( A  e.  Fin  /\  B  e.  Fin )  ->  ( ( card `  A
)  C_  ( card `  B )  <->  A  ~<_  B ) )
8780, 82, 863bitr2d 273 . . 3  |-  ( ( A  e.  Fin  /\  B  e.  Fin )  ->  ( ( # `  A
)  <_  ( # `  B
)  <->  A  ~<_  B )
)
8887adantlr 696 . 2  |-  ( ( ( A  e.  Fin  /\  B  e.  V )  /\  B  e.  Fin )  ->  ( ( # `  A )  <_  ( # `
 B )  <->  A  ~<_  B ) )
89 hashxrcl 11569 . . . . . 6  |-  ( A  e.  Fin  ->  ( # `
 A )  e. 
RR* )
9089ad2antrr 707 . . . . 5  |-  ( ( ( A  e.  Fin  /\  B  e.  V )  /\  -.  B  e. 
Fin )  ->  ( # `
 A )  e. 
RR* )
91 pnfge 10661 . . . . 5  |-  ( (
# `  A )  e.  RR*  ->  ( # `  A
)  <_  +oo )
9290, 91syl 16 . . . 4  |-  ( ( ( A  e.  Fin  /\  B  e.  V )  /\  -.  B  e. 
Fin )  ->  ( # `
 A )  <_  +oo )
93 hashinf 11552 . . . . 5  |-  ( ( B  e.  V  /\  -.  B  e.  Fin )  ->  ( # `  B
)  =  +oo )
9493adantll 695 . . . 4  |-  ( ( ( A  e.  Fin  /\  B  e.  V )  /\  -.  B  e. 
Fin )  ->  ( # `
 B )  = 
+oo )
9592, 94breqtrrd 4181 . . 3  |-  ( ( ( A  e.  Fin  /\  B  e.  V )  /\  -.  B  e. 
Fin )  ->  ( # `
 A )  <_ 
( # `  B ) )
96 isinffi 7814 . . . . . 6  |-  ( ( -.  B  e.  Fin  /\  A  e.  Fin )  ->  E. f  f : A -1-1-> B )
9796ancoms 440 . . . . 5  |-  ( ( A  e.  Fin  /\  -.  B  e.  Fin )  ->  E. f  f : A -1-1-> B )
9897adantlr 696 . . . 4  |-  ( ( ( A  e.  Fin  /\  B  e.  V )  /\  -.  B  e. 
Fin )  ->  E. f 
f : A -1-1-> B
)
99 brdomg 7056 . . . . 5  |-  ( B  e.  V  ->  ( A  ~<_  B  <->  E. f 
f : A -1-1-> B
) )
10099ad2antlr 708 . . . 4  |-  ( ( ( A  e.  Fin  /\  B  e.  V )  /\  -.  B  e. 
Fin )  ->  ( A  ~<_  B  <->  E. f 
f : A -1-1-> B
) )
10198, 100mpbird 224 . . 3  |-  ( ( ( A  e.  Fin  /\  B  e.  V )  /\  -.  B  e. 
Fin )  ->  A  ~<_  B )
10295, 1012thd 232 . 2  |-  ( ( ( A  e.  Fin  /\  B  e.  V )  /\  -.  B  e. 
Fin )  ->  (
( # `  A )  <_  ( # `  B
)  <->  A  ~<_  B )
)
10388, 102pm2.61dan 767 1  |-  ( ( A  e.  Fin  /\  B  e.  V )  ->  ( ( # `  A
)  <_  ( # `  B
)  <->  A  ~<_  B )
)
Colors of variables: wff set class
Syntax hints:   -. wn 3    -> wi 4    <-> wb 177    /\ wa 359   E.wex 1547    = wceq 1649    e. wcel 1717   E.wrex 2652   _Vcvv 2901    C_ wss 3265   class class class wbr 4155    e. cmpt 4209   omcom 4787   `'ccnv 4819   dom cdm 4820    |` cres 4822   -1-1->wf1 5393   -1-1-onto->wf1o 5395   ` cfv 5396  (class class class)co 6022   reccrdg 6605    +o coa 6659    ~<_ cdom 7045   Fincfn 7047   cardccrd 7757   CCcc 8923   RRcr 8924   0cc0 8925   1c1 8926    + caddc 8928    +oocpnf 9052   RR*cxr 9054    <_ cle 9056    - cmin 9225   NN0cn0 10155   ...cfz 10977   #chash 11547
This theorem is referenced by:  hashdomi  11583  hashsdom  11584  hashun2  11586  hashsslei  11614  hashfun  11629  hashf1  11635  isercoll  12390  phicl2  13086  phibnd  13089  prmreclem2  13214  prmreclem3  13215  4sqlem11  13252  vdwlem11  13288  ramub2  13311  0ram  13317  ram0  13319  sylow1lem4  15164  pgpssslw  15177  fislw  15188  znfld  16766  znidomb  16767  fta1blem  19960  birthdaylem3  20661  basellem4  20735  ppiwordi  20814  musum  20845  ppiub  20857  chpub  20873  lgsqrlem4  20997  umgraex  21227  sizeusglecusg  21363  konigsberg  21559  derangenlem  24638  subfaclefac  24643  erdsze2lem1  24670  snmlff  24797  idomsubgmo  27185
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1552  ax-5 1563  ax-17 1623  ax-9 1661  ax-8 1682  ax-13 1719  ax-14 1721  ax-6 1736  ax-7 1741  ax-11 1753  ax-12 1939  ax-ext 2370  ax-sep 4273  ax-nul 4281  ax-pow 4320  ax-pr 4346  ax-un 4643  ax-cnex 8981  ax-resscn 8982  ax-1cn 8983  ax-icn 8984  ax-addcl 8985  ax-addrcl 8986  ax-mulcl 8987  ax-mulrcl 8988  ax-mulcom 8989  ax-addass 8990  ax-mulass 8991  ax-distr 8992  ax-i2m1 8993  ax-1ne0 8994  ax-1rid 8995  ax-rnegex 8996  ax-rrecex 8997  ax-cnre 8998  ax-pre-lttri 8999  ax-pre-lttrn 9000  ax-pre-ltadd 9001  ax-pre-mulgt0 9002
This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3or 937  df-3an 938  df-tru 1325  df-ex 1548  df-nf 1551  df-sb 1656  df-eu 2244  df-mo 2245  df-clab 2376  df-cleq 2382  df-clel 2385  df-nfc 2514  df-ne 2554  df-nel 2555  df-ral 2656  df-rex 2657  df-reu 2658  df-rab 2660  df-v 2903  df-sbc 3107  df-csb 3197  df-dif 3268  df-un 3270  df-in 3272  df-ss 3279  df-pss 3281  df-nul 3574  df-if 3685  df-pw 3746  df-sn 3765  df-pr 3766  df-tp 3767  df-op 3768  df-uni 3960  df-int 3995  df-iun 4039  df-br 4156  df-opab 4210  df-mpt 4211  df-tr 4246  df-eprel 4437  df-id 4441  df-po 4446  df-so 4447  df-fr 4484  df-we 4486  df-ord 4527  df-on 4528  df-lim 4529  df-suc 4530  df-om 4788  df-xp 4826  df-rel 4827  df-cnv 4828  df-co 4829  df-dm 4830  df-rn 4831  df-res 4832  df-ima 4833  df-iota 5360  df-fun 5398  df-fn 5399  df-f 5400  df-f1 5401  df-fo 5402  df-f1o 5403  df-fv 5404  df-ov 6025  df-oprab 6026  df-mpt2 6027  df-1st 6290  df-2nd 6291  df-riota 6487  df-recs 6571  df-rdg 6606  df-1o 6662  df-oadd 6666  df-er 6843  df-en 7048  df-dom 7049  df-sdom 7050  df-fin 7051  df-card 7761  df-pnf 9057  df-mnf 9058  df-xr 9059  df-ltxr 9060  df-le 9061  df-sub 9227  df-neg 9228  df-nn 9935  df-n0 10156  df-z 10217  df-uz 10423  df-fz 10978  df-hash 11548
  Copyright terms: Public domain W3C validator