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

Theorem eulerpart 27949
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 . . . 4  |-  P  =  { f  e.  ( NN0  ^m  NN )  |  ( ( `' f " NN )  e.  Fin  /\  sum_ k  e.  NN  (
( f `  k
)  x.  k )  =  N ) }
2 eulerpart.o . . . 4  |-  O  =  { g  e.  P  |  A. n  e.  ( `' g " NN )  -.  2  ||  n }
3 eulerpart.d . . . 4  |-  D  =  { g  e.  P  |  A. n  e.  NN  ( g `  n
)  <_  1 }
4 eqid 2462 . . . 4  |-  { z  e.  NN  |  -.  2  ||  z }  =  { z  e.  NN  |  -.  2  ||  z }
5 oveq2 6285 . . . . 5  |-  ( a  =  x  ->  (
( 2 ^ b
)  x.  a )  =  ( ( 2 ^ b )  x.  x ) )
6 oveq2 6285 . . . . . 6  |-  ( b  =  y  ->  (
2 ^ b )  =  ( 2 ^ y ) )
76oveq1d 6292 . . . . 5  |-  ( b  =  y  ->  (
( 2 ^ b
)  x.  x )  =  ( ( 2 ^ y )  x.  x ) )
85, 7cbvmpt2v 6354 . . . 4  |-  ( 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 nfcv 2624 . . . . . 6  |-  F/_ m
( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )
10 nfcv 2624 . . . . . 6  |-  F/_ r
( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )
11 nfv 1678 . . . . . 6  |-  F/ m
( r supp  (/) )  e. 
Fin
12 nfv 1678 . . . . . 6  |-  F/ r ( m supp  (/) )  e. 
Fin
13 eqidd 2463 . . . . . 6  |-  ( r  =  m  ->  (
( ~P NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  =  ( ( ~P
NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } ) )
14 oveq1 6284 . . . . . . 7  |-  ( r  =  m  ->  (
r supp  (/) )  =  ( m supp  (/) ) )
1514eleq1d 2531 . . . . . 6  |-  ( r  =  m  ->  (
( r supp  (/) )  e. 
Fin 
<->  ( m supp  (/) )  e. 
Fin ) )
169, 10, 11, 12, 13, 15cbvrabcsf 3465 . . . . 5  |-  { 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 }
1716eqcomi 2475 . . . 4  |-  { 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 }
18 fveq1 5858 . . . . . . . . 9  |-  ( t  =  r  ->  (
t `  a )  =  ( r `  a ) )
1918eleq2d 2532 . . . . . . . 8  |-  ( t  =  r  ->  (
b  e.  ( t `
 a )  <->  b  e.  ( r `  a
) ) )
2019anbi2d 703 . . . . . . 7  |-  ( t  =  r  ->  (
( a  e.  {
z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) )  <->  ( a  e. 
{ z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( r `  a ) ) ) )
2120opabbidv 4505 . . . . . 6  |-  ( 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 ) ) } )
2221cbvmptv 4533 . . . . 5  |-  ( 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 ) ) } )
23 nfcv 2624 . . . . . . . 8  |-  F/_ s
( ( ~P NN0  i^i 
Fin )  ^m  {
z  e.  NN  |  -.  2  ||  z } )
24 nfv 1678 . . . . . . . 8  |-  F/ s ( m supp  (/) )  e. 
Fin
25 nfv 1678 . . . . . . . 8  |-  F/ m
( s supp  (/) )  e. 
Fin
26 eqidd 2463 . . . . . . . 8  |-  ( m  =  s  ->  (
( ~P NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } )  =  ( ( ~P
NN0  i^i  Fin )  ^m  { z  e.  NN  |  -.  2  ||  z } ) )
27 oveq1 6284 . . . . . . . . 9  |-  ( m  =  s  ->  (
m supp  (/) )  =  ( s supp  (/) ) )
2827eleq1d 2531 . . . . . . . 8  |-  ( m  =  s  ->  (
( m supp  (/) )  e. 
Fin 
<->  ( s supp  (/) )  e. 
Fin ) )
2923, 9, 24, 25, 26, 28cbvrabcsf 3465 . . . . . . 7  |-  { 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 }
3029eqcomi 2475 . . . . . 6  |-  { 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 }
31 simpl 457 . . . . . . . . 9  |-  ( ( a  =  x  /\  b  =  y )  ->  a  =  x )
3231eleq1d 2531 . . . . . . . 8  |-  ( ( a  =  x  /\  b  =  y )  ->  ( a  e.  {
z  e.  NN  |  -.  2  ||  z }  <-> 
x  e.  { z  e.  NN  |  -.  2  ||  z } ) )
33 simpr 461 . . . . . . . . 9  |-  ( ( a  =  x  /\  b  =  y )  ->  b  =  y )
3431fveq2d 5863 . . . . . . . . 9  |-  ( ( a  =  x  /\  b  =  y )  ->  ( r `  a
)  =  ( r `
 x ) )
3533, 34eleq12d 2544 . . . . . . . 8  |-  ( ( a  =  x  /\  b  =  y )  ->  ( b  e.  ( r `  a )  <-> 
y  e.  ( r `
 x ) ) )
3632, 35anbi12d 710 . . . . . . 7  |-  ( ( 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 ) ) ) )
3736cbvopabv 4511 . . . . . 6  |-  { <. 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 ) ) }
3830, 37mpteq12i 4526 . . . . 5  |-  ( 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 ) ) } )
3922, 38eqtri 2491 . . . 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.  {
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 ) ) } )
40 cnveq 5169 . . . . . . 7  |-  ( h  =  f  ->  `' h  =  `' f
)
4140imaeq1d 5329 . . . . . 6  |-  ( h  =  f  ->  ( `' h " NN )  =  ( `' f
" NN ) )
4241eleq1d 2531 . . . . 5  |-  ( h  =  f  ->  (
( `' h " NN )  e.  Fin  <->  ( `' f " NN )  e.  Fin )
)
4342cbvabv 2605 . . . 4  |-  { h  |  ( `' h " NN )  e.  Fin }  =  { f  |  ( `' f " NN )  e.  Fin }
4441sseq1d 3526 . . . . 5  |-  ( h  =  f  ->  (
( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z }  <->  ( `' f " NN )  C_  { z  e.  NN  |  -.  2  ||  z } ) )
4544cbvrabv 3107 . . . 4  |-  { 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 } }
46 reseq1 5260 . . . . . . . . . 10  |-  ( o  =  q  ->  (
o  |`  { z  e.  NN  |  -.  2  ||  z } )  =  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) )
4746coeq2d 5158 . . . . . . . . 9  |-  ( o  =  q  ->  (bits  o.  ( o  |`  { z  e.  NN  |  -.  2  ||  z } ) )  =  (bits  o.  ( q  |`  { z  e.  NN  |  -.  2  ||  z } ) ) )
4847fveq2d 5863 . . . . . . . 8  |-  ( 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 } ) ) ) )
4948imaeq2d 5330 . . . . . . 7  |-  ( 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 } ) ) ) ) )
5049fveq2d 5863 . . . . . 6  |-  ( 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 } ) ) ) ) ) )
5150cbvmptv 4533 . . . . 5  |-  ( 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 } ) ) ) ) ) )
528eqcomi 2475 . . . . . . . . 9  |-  ( 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
) )
5352imaeq1i 5327 . . . . . . . 8  |-  ( ( 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 } ) ) ) )
54 eqid 2462 . . . . . . . . . . . . 13  |-  { <. 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 ) ) }
5516, 54mpteq12i 4526 . . . . . . . . . . . 12  |-  ( 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 ) ) } )
5655, 38eqtr4i 2494 . . . . . . . . . . 11  |-  ( 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.  {
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 ) ) } )
57 fveq1 5858 . . . . . . . . . . . . . . 15  |-  ( r  =  t  ->  (
r `  a )  =  ( t `  a ) )
5857eleq2d 2532 . . . . . . . . . . . . . 14  |-  ( r  =  t  ->  (
b  e.  ( r `
 a )  <->  b  e.  ( t `  a
) ) )
5958anbi2d 703 . . . . . . . . . . . . 13  |-  ( r  =  t  ->  (
( a  e.  {
z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( r `  a ) )  <->  ( a  e. 
{ z  e.  NN  |  -.  2  ||  z }  /\  b  e.  ( t `  a ) ) ) )
6059opabbidv 4505 . . . . . . . . . . . 12  |-  ( 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 ) ) } )
6160cbvmptv 4533 . . . . . . . . . . 11  |-  ( 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 ) ) } )
6256, 61eqtri 2491 . . . . . . . . . 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 ) ) } )  =  ( 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 ) ) } )
6362fveq1i 5860 . . . . . . . . 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 ) ) } ) `  (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 } ) ) )
6463imaeq2i 5328 . . . . . . . 8  |-  ( ( 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 } ) ) ) )
6553, 64eqtri 2491 . . . . . . 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 ) )
" ( ( 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 } ) ) ) )
6665fveq2i 5862 . . . . . 6  |-  ( (𝟭 `  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 } ) ) ) ) )
6766mpteq2i 4525 . . . . 5  |-  ( 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 } ) ) ) ) ) )
6851, 67eqtri 2491 . . . 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 ) `  ( (
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 } ) ) ) ) ) )
69 eqid 2462 . . . 4  |-  ( 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
) )
701, 2, 3, 4, 8, 17, 39, 43, 45, 68, 69eulerpartlemn 27948 . . 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 ) : O -1-1-onto-> D
71 ovex 6302 . . . . . . . 8  |-  ( NN0 
^m  NN )  e. 
_V
7271rabex 4593 . . . . . . 7  |-  { h  e.  ( NN0  ^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  e.  _V
7372inex1 4583 . . . . . 6  |-  ( { h  e.  ( NN0 
^m  NN )  |  ( `' h " NN )  C_  { z  e.  NN  |  -.  2  ||  z } }  i^i  { h  |  ( `' h " NN )  e.  Fin } )  e.  _V
7473mptex 6124 . . . . 5  |-  ( 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
7574resex 5310 . . . 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 } ) ) ) ) ) )  |`  O )  e.  _V
76 f1oeq1 5800 . . . 4  |-  ( 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
) )
7775, 76spcev 3200 . . 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 ) : O -1-1-onto-> D  ->  E. g  g : O -1-1-onto-> D )
7870, 77ax-mp 5 . 2  |-  E. g 
g : O -1-1-onto-> D
79 bren 7517 . . 3  |-  ( O 
~~  D  <->  E. g 
g : O -1-1-onto-> D )
80 hasheni 12378 . . 3  |-  ( O 
~~  D  ->  ( # `
 O )  =  ( # `  D
) )
8179, 80sylbir 213 . 2  |-  ( E. g  g : O -1-1-onto-> D  ->  ( # `  O
)  =  ( # `  D ) )
8278, 81ax-mp 5 1  |-  ( # `  O )  =  (
# `  D )
Colors of variables: wff setvar class
Syntax hints:   -. wn 3    /\ wa 369    = wceq 1374   E.wex 1591    e. wcel 1762   {cab 2447   A.wral 2809   {crab 2813    i^i cin 3470    C_ wss 3471   (/)c0 3780   ~Pcpw 4005   class class class wbr 4442   {copab 4499    |-> cmpt 4500   `'ccnv 4993    |` cres 4996   "cima 4997    o. ccom 4998   -1-1-onto->wf1o 5580   ` cfv 5581  (class class class)co 6277    |-> cmpt2 6279   supp csupp 6893    ^m cmap 7412    ~~ cen 7505   Fincfn 7508   1c1 9484    x. cmul 9488    <_ cle 9620   NNcn 10527   2c2 10576   NN0cn0 10786   ^cexp 12124   #chash 12362   sum_csu 13459    || cdivides 13838  bitscbits 13919  𝟭cind 27652
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1596  ax-4 1607  ax-5 1675  ax-6 1714  ax-7 1734  ax-8 1764  ax-9 1766  ax-10 1781  ax-11 1786  ax-12 1798  ax-13 1963  ax-ext 2440  ax-rep 4553  ax-sep 4563  ax-nul 4571  ax-pow 4620  ax-pr 4681  ax-un 6569  ax-inf2 8049  ax-ac2 8834  ax-cnex 9539  ax-resscn 9540  ax-1cn 9541  ax-icn 9542  ax-addcl 9543  ax-addrcl 9544  ax-mulcl 9545  ax-mulrcl 9546  ax-mulcom 9547  ax-addass 9548  ax-mulass 9549  ax-distr 9550  ax-i2m1 9551  ax-1ne0 9552  ax-1rid 9553  ax-rnegex 9554  ax-rrecex 9555  ax-cnre 9556  ax-pre-lttri 9557  ax-pre-lttrn 9558  ax-pre-ltadd 9559  ax-pre-mulgt0 9560  ax-pre-sup 9561
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 969  df-3an 970  df-tru 1377  df-fal 1380  df-ex 1592  df-nf 1595  df-sb 1707  df-eu 2274  df-mo 2275  df-clab 2448  df-cleq 2454  df-clel 2457  df-nfc 2612  df-ne 2659  df-nel 2660  df-ral 2814  df-rex 2815  df-reu 2816  df-rmo 2817  df-rab 2818  df-v 3110  df-sbc 3327  df-csb 3431  df-dif 3474  df-un 3476  df-in 3478  df-ss 3485  df-pss 3487  df-nul 3781  df-if 3935  df-pw 4007  df-sn 4023  df-pr 4025  df-tp 4027  df-op 4029  df-uni 4241  df-int 4278  df-iun 4322  df-disj 4413  df-br 4443  df-opab 4501  df-mpt 4502  df-tr 4536  df-eprel 4786  df-id 4790  df-po 4795  df-so 4796  df-fr 4833  df-se 4834  df-we 4835  df-ord 4876  df-on 4877  df-lim 4878  df-suc 4879  df-xp 5000  df-rel 5001  df-cnv 5002  df-co 5003  df-dm 5004  df-rn 5005  df-res 5006  df-ima 5007  df-iota 5544  df-fun 5583  df-fn 5584  df-f 5585  df-f1 5586  df-fo 5587  df-f1o 5588  df-fv 5589  df-isom 5590  df-riota 6238  df-ov 6280  df-oprab 6281  df-mpt2 6282  df-om 6674  df-1st 6776  df-2nd 6777  df-supp 6894  df-recs 7034  df-rdg 7068  df-1o 7122  df-2o 7123  df-oadd 7126  df-er 7303  df-map 7414  df-pm 7415  df-en 7509  df-dom 7510  df-sdom 7511  df-fin 7512  df-fsupp 7821  df-sup 7892  df-oi 7926  df-card 8311  df-acn 8314  df-ac 8488  df-cda 8539  df-pnf 9621  df-mnf 9622  df-xr 9623  df-ltxr 9624  df-le 9625  df-sub 9798  df-neg 9799  df-div 10198  df-nn 10528  df-2 10585  df-3 10586  df-n0 10787  df-z 10856  df-uz 11074  df-rp 11212  df-fz 11664  df-fzo 11784  df-fl 11888  df-mod 11955  df-seq 12066  df-exp 12125  df-hash 12363  df-cj 12884  df-re 12885  df-im 12886  df-sqr 13020  df-abs 13021  df-clim 13262  df-sum 13460  df-dvds 13839  df-bits 13922  df-ind 27653
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator