Users' Mathboxes Mathbox for Thierry Arnoux < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  eulerpart Structured version   Visualization version   Unicode version

Theorem eulerpart 29227
Description: Euler's theorem on partitions, also known as a special case of Glaisher's theorem. Let  P be the set of all partitions of  N, represented as multisets of positive integers, which is to say functions from  NN to  NN0 where the value of the function represents the number of repetitions of an individual element, and the sum of all the elements with repetition equals  N. Then the set 
O of all partitions that only consist of odd numbers and the set  D of all partitions which have no repeated elements have the same cardinality. This is Metamath 100 proof #45. (Contributed by Thierry Arnoux, 14-Aug-2018.) (Revised by Thierry Arnoux, 1-Sep-2019.)
Hypotheses
Ref Expression
eulerpart.p  |-  P  =  { f  e.  ( NN0  ^m  NN )  |  ( ( `' f " NN )  e.  Fin  /\  sum_ k  e.  NN  (
( f `  k
)  x.  k )  =  N ) }
eulerpart.o  |-  O  =  { g  e.  P  |  A. n  e.  ( `' g " NN )  -.  2  ||  n }
eulerpart.d  |-  D  =  { g  e.  P  |  A. n  e.  NN  ( g `  n
)  <_  1 }
Assertion
Ref Expression
eulerpart  |-  ( # `  O )  =  (
# `  D )
Distinct variable groups:    f, g,
k, n    D, g    f, N, g, k, n   
g, O, n    P, g, k, n
Allowed substitution hints:    D( f, k, n)    P( f)    O( f, k)

Proof of Theorem eulerpart
Dummy variables  a 
b  h  m  o  q  r  s  t  x  y  z are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 eulerpart.p . . 3  |-  P  =  { f  e.  ( NN0  ^m  NN )  |  ( ( `' f " NN )  e.  Fin  /\  sum_ k  e.  NN  (
( f `  k
)  x.  k )  =  N ) }
2 eulerpart.o . . 3  |-  O  =  { g  e.  P  |  A. n  e.  ( `' g " NN )  -.  2  ||  n }
3 eulerpart.d . . 3  |-  D  =  { g  e.  P  |  A. n  e.  NN  ( g `  n
)  <_  1 }
4 eqid 2453 . . 3  |-  { z  e.  NN  |  -.  2  ||  z }  =  { z  e.  NN  |  -.  2  ||  z }
5 oveq2 6303 . . . 4  |-  ( a  =  x  ->  (
( 2 ^ b
)  x.  a )  =  ( ( 2 ^ b )  x.  x ) )
6 oveq2 6303 . . . . 5  |-  ( b  =  y  ->  (
2 ^ b )  =  ( 2 ^ y ) )
76oveq1d 6310 . . . 4  |-  ( b  =  y  ->  (
( 2 ^ b
)  x.  x )  =  ( ( 2 ^ y )  x.  x ) )
85, 7cbvmpt2v 6376 . . 3  |-  ( a  e.  { z  e.  NN  |  -.  2  ||  z } ,  b  e.  NN0  |->  ( ( 2 ^ b )  x.  a ) )  =  ( x  e. 
{ z  e.  NN  |  -.  2  ||  z } ,  y  e.  NN0  |->  ( ( 2 ^ y )  x.  x
) )
9 oveq1 6302 . . . . . 6  |-  ( r  =  m  ->  (
r supp  (/) )  =  ( m supp  (/) ) )
109eleq1d 2515 . . . . 5  |-  ( r  =  m  ->  (
( r supp  (/) )  e. 
Fin 
<->  ( m supp  (/) )  e. 
Fin ) )
1110cbvrabv 3046 . . . 4  |-  { r  e.  ( ( ~P
NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin }  =  { m  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( m supp  (/) )  e.  Fin }
1211eqcomi 2462 . . 3  |-  { m  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( m supp  (/) )  e.  Fin }  =  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin }
13 fveq1 5869 . . . . . . . 8  |-  ( t  =  r  ->  (
t `  a )  =  ( r `  a ) )
1413eleq2d 2516 . . . . . . 7  |-  ( t  =  r  ->  (
b  e.  ( t `
 a )  <->  b  e.  ( r `  a
) ) )
1514anbi2d 711 . . . . . 6  |-  ( t  =  r  ->  (
( a  e.  {
z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) )  <->  ( a  e. 
{ z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( r `  a ) ) ) )
1615opabbidv 4469 . . . . 5  |-  ( t  =  r  ->  { <. a ,  b >.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) ) }  =  { <. a ,  b >.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( r `  a ) ) } )
1716cbvmptv 4498 . . . 4  |-  ( t  e.  { s  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( s supp  (/) )  e.  Fin } 
|->  { <. a ,  b
>.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) ) } )  =  ( r  e.  {
s  e.  ( ( ~P NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  |  ( s supp  (/) )  e. 
Fin }  |->  { <. a ,  b >.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( r `  a ) ) } )
18 oveq1 6302 . . . . . . . 8  |-  ( m  =  s  ->  (
m supp  (/) )  =  ( s supp  (/) ) )
1918eleq1d 2515 . . . . . . 7  |-  ( m  =  s  ->  (
( m supp  (/) )  e. 
Fin 
<->  ( s supp  (/) )  e. 
Fin ) )
2019cbvrabv 3046 . . . . . 6  |-  { m  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( m supp  (/) )  e.  Fin }  =  { s  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( s supp  (/) )  e.  Fin }
2120eqcomi 2462 . . . . 5  |-  { s  e.  ( ( ~P
NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  |  ( s supp  (/) )  e.  Fin }  =  { m  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( m supp  (/) )  e.  Fin }
22 simpl 459 . . . . . . . 8  |-  ( ( a  =  x  /\  b  =  y )  ->  a  =  x )
2322eleq1d 2515 . . . . . . 7  |-  ( ( a  =  x  /\  b  =  y )  ->  ( a  e.  {
z  e.  NN  |  -.  2  ||  z }  <-> 
x  e.  { z  e.  NN  |  -.  2  ||  z } ) )
24 simpr 463 . . . . . . . 8  |-  ( ( a  =  x  /\  b  =  y )  ->  b  =  y )
2522fveq2d 5874 . . . . . . . 8  |-  ( ( a  =  x  /\  b  =  y )  ->  ( r `  a
)  =  ( r `
 x ) )
2624, 25eleq12d 2525 . . . . . . 7  |-  ( ( a  =  x  /\  b  =  y )  ->  ( b  e.  ( r `  a )  <-> 
y  e.  ( r `
 x ) ) )
2723, 26anbi12d 718 . . . . . 6  |-  ( ( a  =  x  /\  b  =  y )  ->  ( ( a  e. 
{ z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( r `  a ) )  <->  ( x  e. 
{ z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) ) )
2827cbvopabv 4475 . . . . 5  |-  { <. a ,  b >.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( r `  a ) ) }  =  { <. x ,  y >.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) }
2921, 28mpteq12i 4490 . . . 4  |-  ( r  e.  { s  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( s supp  (/) )  e.  Fin } 
|->  { <. a ,  b
>.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( r `  a ) ) } )  =  ( r  e.  {
m  e.  ( ( ~P NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  |  ( m supp  (/) )  e. 
Fin }  |->  { <. x ,  y >.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } )
3017, 29eqtri 2475 . . 3  |-  ( t  e.  { s  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( s supp  (/) )  e.  Fin } 
|->  { <. a ,  b
>.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) ) } )  =  ( r  e.  {
m  e.  ( ( ~P NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  |  ( m supp  (/) )  e. 
Fin }  |->  { <. x ,  y >.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } )
31 cnveq 5011 . . . . . 6  |-  ( h  =  f  ->  `' h  =  `' f
)
3231imaeq1d 5170 . . . . 5  |-  ( h  =  f  ->  ( `' h " NN )  =  ( `' f
" NN ) )
3332eleq1d 2515 . . . 4  |-  ( h  =  f  ->  (
( `' h " NN )  e.  Fin  <->  ( `' f " NN )  e.  Fin )
)
3433cbvabv 2577 . . 3  |-  { h  |  ( `' h " NN )  e.  Fin }  =  { f  |  ( `' f " NN )  e.  Fin }
3532sseq1d 3461 . . . 4  |-  ( h  =  f  ->  (
( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z }  <->  ( `' f " NN )  C_  { z  e.  NN  |  -.  2  ||  z } ) )
3635cbvrabv 3046 . . 3  |-  { h  e.  ( NN0  ^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  =  { f  e.  ( NN0  ^m  NN )  |  ( `' f " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }
37 reseq1 5102 . . . . . . . . 9  |-  ( o  =  q  ->  (
o  |`  { z  e.  NN  |  -.  2  ||  z } )  =  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) )
3837coeq2d 5000 . . . . . . . 8  |-  ( o  =  q  ->  (bits  o.  ( o  |`  { z  e.  NN  |  -.  2  ||  z } ) )  =  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) )
3938fveq2d 5874 . . . . . . 7  |-  ( o  =  q  ->  (
( r  e.  {
r  e.  ( ( ~P NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e. 
Fin }  |->  { <. x ,  y >.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( o  |`  { z  e.  NN  |  -.  2  ||  z } ) ) )  =  ( ( r  e.  {
r  e.  ( ( ~P NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e. 
Fin }  |->  { <. x ,  y >.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) )
4039imaeq2d 5171 . . . . . 6  |-  ( o  =  q  ->  (
( x  e.  {
z  e.  NN  |  -.  2  ||  z } ,  y  e.  NN0  |->  ( ( 2 ^ y )  x.  x
) ) " (
( r  e.  {
r  e.  ( ( ~P NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e. 
Fin }  |->  { <. x ,  y >.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( o  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) )  =  ( ( x  e. 
{ z  e.  NN  |  -.  2  ||  z } ,  y  e.  NN0  |->  ( ( 2 ^ y )  x.  x
) ) " (
( r  e.  {
r  e.  ( ( ~P NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e. 
Fin }  |->  { <. x ,  y >.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) )
4140fveq2d 5874 . . . . 5  |-  ( o  =  q  ->  (
(𝟭 `  NN ) `  ( ( x  e. 
{ z  e.  NN  |  -.  2  ||  z } ,  y  e.  NN0  |->  ( ( 2 ^ y )  x.  x
) ) " (
( r  e.  {
r  e.  ( ( ~P NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e. 
Fin }  |->  { <. x ,  y >.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( o  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) )  =  ( (𝟭 `  NN ) `  ( (
x  e.  { z  e.  NN  |  -.  2  ||  z } , 
y  e.  NN0  |->  ( ( 2 ^ y )  x.  x ) )
" ( ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) ) )
4241cbvmptv 4498 . . . 4  |-  ( o  e.  ( { h  e.  ( NN0  ^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  i^i  { h  |  ( `' h " NN )  e.  Fin } )  |->  ( (𝟭 `  NN ) `  ( (
x  e.  { z  e.  NN  |  -.  2  ||  z } , 
y  e.  NN0  |->  ( ( 2 ^ y )  x.  x ) )
" ( ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( o  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) ) )  =  ( q  e.  ( { h  e.  ( NN0  ^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  i^i  { h  |  ( `' h " NN )  e.  Fin } ) 
|->  ( (𝟭 `  NN ) `  ( (
x  e.  { z  e.  NN  |  -.  2  ||  z } , 
y  e.  NN0  |->  ( ( 2 ^ y )  x.  x ) )
" ( ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) ) )
438eqcomi 2462 . . . . . . . 8  |-  ( x  e.  { z  e.  NN  |  -.  2  ||  z } ,  y  e.  NN0  |->  ( ( 2 ^ y )  x.  x ) )  =  ( a  e. 
{ z  e.  NN  |  -.  2  ||  z } ,  b  e.  NN0  |->  ( ( 2 ^ b )  x.  a
) )
4443imaeq1i 5168 . . . . . . 7  |-  ( ( x  e.  { z  e.  NN  |  -.  2  ||  z } , 
y  e.  NN0  |->  ( ( 2 ^ y )  x.  x ) )
" ( ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) )  =  ( ( a  e.  { z  e.  NN  |  -.  2  ||  z } , 
b  e.  NN0  |->  ( ( 2 ^ b )  x.  a ) )
" ( ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) )
45 eqid 2453 . . . . . . . . . . 11  |-  { <. x ,  y >.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) }  =  { <. x ,  y >.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) }
4611, 45mpteq12i 4490 . . . . . . . . . 10  |-  ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } )  =  ( r  e.  {
m  e.  ( ( ~P NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  |  ( m supp  (/) )  e. 
Fin }  |->  { <. x ,  y >.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } )
47 fveq1 5869 . . . . . . . . . . . . . 14  |-  ( r  =  t  ->  (
r `  a )  =  ( t `  a ) )
4847eleq2d 2516 . . . . . . . . . . . . 13  |-  ( r  =  t  ->  (
b  e.  ( r `
 a )  <->  b  e.  ( t `  a
) ) )
4948anbi2d 711 . . . . . . . . . . . 12  |-  ( r  =  t  ->  (
( a  e.  {
z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( r `  a ) )  <->  ( a  e. 
{ z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) ) ) )
5049opabbidv 4469 . . . . . . . . . . 11  |-  ( r  =  t  ->  { <. a ,  b >.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( r `  a ) ) }  =  { <. a ,  b >.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) ) } )
5150cbvmptv 4498 . . . . . . . . . 10  |-  ( r  e.  { s  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( s supp  (/) )  e.  Fin } 
|->  { <. a ,  b
>.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( r `  a ) ) } )  =  ( t  e.  {
s  e.  ( ( ~P NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  |  ( s supp  (/) )  e. 
Fin }  |->  { <. a ,  b >.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) ) } )
5246, 29, 513eqtr2i 2481 . . . . . . . . 9  |-  ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } )  =  ( t  e.  {
s  e.  ( ( ~P NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  |  ( s supp  (/) )  e. 
Fin }  |->  { <. a ,  b >.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) ) } )
5352fveq1i 5871 . . . . . . . 8  |-  ( ( r  e.  { r  e.  ( ( ~P
NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) )  =  ( ( t  e.  { s  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( s supp  (/) )  e.  Fin } 
|->  { <. a ,  b
>.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) )
5453imaeq2i 5169 . . . . . . 7  |-  ( ( a  e.  { z  e.  NN  |  -.  2  ||  z } , 
b  e.  NN0  |->  ( ( 2 ^ b )  x.  a ) )
" ( ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) )  =  ( ( a  e.  { z  e.  NN  |  -.  2  ||  z } , 
b  e.  NN0  |->  ( ( 2 ^ b )  x.  a ) )
" ( ( t  e.  { s  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( s supp  (/) )  e.  Fin } 
|->  { <. a ,  b
>.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) )
5544, 54eqtri 2475 . . . . . 6  |-  ( ( x  e.  { z  e.  NN  |  -.  2  ||  z } , 
y  e.  NN0  |->  ( ( 2 ^ y )  x.  x ) )
" ( ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) )  =  ( ( a  e.  { z  e.  NN  |  -.  2  ||  z } , 
b  e.  NN0  |->  ( ( 2 ^ b )  x.  a ) )
" ( ( t  e.  { s  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( s supp  (/) )  e.  Fin } 
|->  { <. a ,  b
>.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) )
5655fveq2i 5873 . . . . 5  |-  ( (𝟭 `  NN ) `  (
( x  e.  {
z  e.  NN  |  -.  2  ||  z } ,  y  e.  NN0  |->  ( ( 2 ^ y )  x.  x
) ) " (
( r  e.  {
r  e.  ( ( ~P NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e. 
Fin }  |->  { <. x ,  y >.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) )  =  ( (𝟭 `  NN ) `  ( (
a  e.  { z  e.  NN  |  -.  2  ||  z } , 
b  e.  NN0  |->  ( ( 2 ^ b )  x.  a ) )
" ( ( t  e.  { s  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( s supp  (/) )  e.  Fin } 
|->  { <. a ,  b
>.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) )
5756mpteq2i 4489 . . . 4  |-  ( q  e.  ( { h  e.  ( NN0  ^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  i^i  { h  |  ( `' h " NN )  e.  Fin } )  |->  ( (𝟭 `  NN ) `  ( (
x  e.  { z  e.  NN  |  -.  2  ||  z } , 
y  e.  NN0  |->  ( ( 2 ^ y )  x.  x ) )
" ( ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) ) )  =  ( q  e.  ( { h  e.  ( NN0  ^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  i^i  { h  |  ( `' h " NN )  e.  Fin } ) 
|->  ( (𝟭 `  NN ) `  ( (
a  e.  { z  e.  NN  |  -.  2  ||  z } , 
b  e.  NN0  |->  ( ( 2 ^ b )  x.  a ) )
" ( ( t  e.  { s  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( s supp  (/) )  e.  Fin } 
|->  { <. a ,  b
>.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) ) )
5842, 57eqtri 2475 . . 3  |-  ( o  e.  ( { h  e.  ( NN0  ^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  i^i  { h  |  ( `' h " NN )  e.  Fin } )  |->  ( (𝟭 `  NN ) `  ( (
x  e.  { z  e.  NN  |  -.  2  ||  z } , 
y  e.  NN0  |->  ( ( 2 ^ y )  x.  x ) )
" ( ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( o  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) ) )  =  ( q  e.  ( { h  e.  ( NN0  ^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  i^i  { h  |  ( `' h " NN )  e.  Fin } ) 
|->  ( (𝟭 `  NN ) `  ( (
a  e.  { z  e.  NN  |  -.  2  ||  z } , 
b  e.  NN0  |->  ( ( 2 ^ b )  x.  a ) )
" ( ( t  e.  { s  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( s supp  (/) )  e.  Fin } 
|->  { <. a ,  b
>.  |  ( a  e.  { z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) ) } ) `  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) ) )
59 eqid 2453 . . 3  |-  ( f  e.  ( ( NN0 
^m  NN )  i^i 
{ h  |  ( `' h " NN )  e.  Fin } ) 
|->  sum_ k  e.  NN  ( ( f `  k )  x.  k
) )  =  ( f  e.  ( ( NN0  ^m  NN )  i^i  { h  |  ( `' h " NN )  e.  Fin } )  |->  sum_ k  e.  NN  ( ( f `  k )  x.  k
) )
601, 2, 3, 4, 8, 12, 30, 34, 36, 58, 59eulerpartlemn 29226 . 2  |-  ( ( o  e.  ( { h  e.  ( NN0 
^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  i^i  { h  |  ( `' h " NN )  e.  Fin } ) 
|->  ( (𝟭 `  NN ) `  ( (
x  e.  { z  e.  NN  |  -.  2  ||  z } , 
y  e.  NN0  |->  ( ( 2 ^ y )  x.  x ) )
" ( ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( o  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) ) )  |`  O ) : O -1-1-onto-> D
61 ovex 6323 . . . . . . 7  |-  ( NN0 
^m  NN )  e. 
_V
6261rabex 4557 . . . . . 6  |-  { h  e.  ( NN0  ^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  e.  _V
6362inex1 4547 . . . . 5  |-  ( { h  e.  ( NN0 
^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  i^i  { h  |  ( `' h " NN )  e.  Fin } )  e.  _V
6463mptex 6141 . . . 4  |-  ( o  e.  ( { h  e.  ( NN0  ^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  i^i  { h  |  ( `' h " NN )  e.  Fin } )  |->  ( (𝟭 `  NN ) `  ( (
x  e.  { z  e.  NN  |  -.  2  ||  z } , 
y  e.  NN0  |->  ( ( 2 ^ y )  x.  x ) )
" ( ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( o  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) ) )  e. 
_V
6564resex 5151 . . 3  |-  ( ( o  e.  ( { h  e.  ( NN0 
^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  i^i  { h  |  ( `' h " NN )  e.  Fin } ) 
|->  ( (𝟭 `  NN ) `  ( (
x  e.  { z  e.  NN  |  -.  2  ||  z } , 
y  e.  NN0  |->  ( ( 2 ^ y )  x.  x ) )
" ( ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( o  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) ) )  |`  O )  e.  _V
66 f1oeq1 5810 . . 3  |-  ( g  =  ( ( o  e.  ( { h  e.  ( NN0  ^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  i^i  { h  |  ( `' h " NN )  e.  Fin } )  |->  ( (𝟭 `  NN ) `  ( (
x  e.  { z  e.  NN  |  -.  2  ||  z } , 
y  e.  NN0  |->  ( ( 2 ^ y )  x.  x ) )
" ( ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( o  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) ) )  |`  O )  ->  (
g : O -1-1-onto-> D  <->  ( (
o  e.  ( { h  e.  ( NN0 
^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  i^i  { h  |  ( `' h " NN )  e.  Fin } ) 
|->  ( (𝟭 `  NN ) `  ( (
x  e.  { z  e.  NN  |  -.  2  ||  z } , 
y  e.  NN0  |->  ( ( 2 ^ y )  x.  x ) )
" ( ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( o  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) ) )  |`  O ) : O -1-1-onto-> D
) )
6765, 66spcev 3143 . 2  |-  ( ( ( o  e.  ( { h  e.  ( NN0  ^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  i^i  { h  |  ( `' h " NN )  e.  Fin } ) 
|->  ( (𝟭 `  NN ) `  ( (
x  e.  { z  e.  NN  |  -.  2  ||  z } , 
y  e.  NN0  |->  ( ( 2 ^ y )  x.  x ) )
" ( ( r  e.  { r  e.  ( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )  |  ( r supp  (/) )  e.  Fin } 
|->  { <. x ,  y
>.  |  ( x  e.  { z  e.  NN  |  -.  2  ||  z }  /\  y  e.  ( r `  x ) ) } ) `  (bits  o.  ( o  |`  { z  e.  NN  |  -.  2  ||  z } ) ) ) ) ) )  |`  O ) : O -1-1-onto-> D  ->  E. g  g : O -1-1-onto-> D )
68 bren 7583 . . 3  |-  ( O 
~~  D  <->  E. g 
g : O -1-1-onto-> D )
69 hasheni 12538 . . 3  |-  ( O 
~~  D  ->  ( # `
 O )  =  ( # `  D
) )
7068, 69sylbir 217 . 2  |-  ( E. g  g : O -1-1-onto-> D  ->  ( # `  O
)  =  ( # `  D ) )
7160, 67, 70mp2b 10 1  |-  ( # `  O )  =  (
# `  D )
Colors of variables: wff setvar class
Syntax hints:   -. wn 3    /\ wa 371    = wceq 1446   E.wex 1665    e. wcel 1889   {cab 2439   A.wral 2739   {crab 2743    i^i cin 3405    C_ wss 3406   (/)c0 3733   ~Pcpw 3953   class class class wbr 4405   {copab 4463    |-> cmpt 4464   `'ccnv 4836    |` cres 4839   "cima 4840    o. ccom 4841   -1-1-onto->wf1o 5584   ` cfv 5585  (class class class)co 6295    |-> cmpt2 6297   supp csupp 6919    ^m cmap 7477    ~~ cen 7571   Fincfn 7574   1c1 9545    x. cmul 9549    <_ cle 9681   NNcn 10616   2c2 10666   NN0cn0 10876   ^cexp 12279   #chash 12522   sum_csu 13764    || cdvds 14317  bitscbits 14404  𝟭cind 28844
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1671  ax-4 1684  ax-5 1760  ax-6 1807  ax-7 1853  ax-8 1891  ax-9 1898  ax-10 1917  ax-11 1922  ax-12 1935  ax-13 2093  ax-ext 2433  ax-rep 4518  ax-sep 4528  ax-nul 4537  ax-pow 4584  ax-pr 4642  ax-un 6588  ax-inf2 8151  ax-ac2 8898  ax-cnex 9600  ax-resscn 9601  ax-1cn 9602  ax-icn 9603  ax-addcl 9604  ax-addrcl 9605  ax-mulcl 9606  ax-mulrcl 9607  ax-mulcom 9608  ax-addass 9609  ax-mulass 9610  ax-distr 9611  ax-i2m1 9612  ax-1ne0 9613  ax-1rid 9614  ax-rnegex 9615  ax-rrecex 9616  ax-cnre 9617  ax-pre-lttri 9618  ax-pre-lttrn 9619  ax-pre-ltadd 9620  ax-pre-mulgt0 9621  ax-pre-sup 9622
This theorem depends on definitions:  df-bi 189  df-or 372  df-an 373  df-3or 987  df-3an 988  df-tru 1449  df-fal 1452  df-ex 1666  df-nf 1670  df-sb 1800  df-eu 2305  df-mo 2306  df-clab 2440  df-cleq 2446  df-clel 2449  df-nfc 2583  df-ne 2626  df-nel 2627  df-ral 2744  df-rex 2745  df-reu 2746  df-rmo 2747  df-rab 2748  df-v 3049  df-sbc 3270  df-csb 3366  df-dif 3409  df-un 3411  df-in 3413  df-ss 3420  df-pss 3422  df-nul 3734  df-if 3884  df-pw 3955  df-sn 3971  df-pr 3973  df-tp 3975  df-op 3977  df-uni 4202  df-int 4238  df-iun 4283  df-disj 4377  df-br 4406  df-opab 4465  df-mpt 4466  df-tr 4501  df-eprel 4748  df-id 4752  df-po 4758  df-so 4759  df-fr 4796  df-se 4797  df-we 4798  df-xp 4843  df-rel 4844  df-cnv 4845  df-co 4846  df-dm 4847  df-rn 4848  df-res 4849  df-ima 4850  df-pred 5383  df-ord 5429  df-on 5430  df-lim 5431  df-suc 5432  df-iota 5549  df-fun 5587  df-fn 5588  df-f 5589  df-f1 5590  df-fo 5591  df-f1o 5592  df-fv 5593  df-isom 5594  df-riota 6257  df-ov 6298  df-oprab 6299  df-mpt2 6300  df-om 6698  df-1st 6798  df-2nd 6799  df-supp 6920  df-wrecs 7033  df-recs 7095  df-rdg 7133  df-1o 7187  df-2o 7188  df-oadd 7191  df-er 7368  df-map 7479  df-pm 7480  df-en 7575  df-dom 7576  df-sdom 7577  df-fin 7578  df-fsupp 7889  df-sup 7961  df-inf 7962  df-oi 8030  df-card 8378  df-acn 8381  df-ac 8552  df-cda 8603  df-pnf 9682  df-mnf 9683  df-xr 9684  df-ltxr 9685  df-le 9686  df-sub 9867  df-neg 9868  df-div 10277  df-nn 10617  df-2 10675  df-3 10676  df-n0 10877  df-z 10945  df-uz 11167  df-rp 11310  df-fz 11792  df-fzo 11923  df-fl 12035  df-mod 12104  df-seq 12221  df-exp 12280  df-hash 12523  df-cj 13174  df-re 13175  df-im 13176  df-sqrt 13310  df-abs 13311  df-clim 13564  df-sum 13765  df-dvds 14318  df-bits 14407  df-ind 28845
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator