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

Theorem fsumf1o 13317
Description: Re-index a finite sum using a bijection. (Contributed by Mario Carneiro, 20-Apr-2014.)
Hypotheses
Ref Expression
fsumf1o.1  |-  ( k  =  G  ->  B  =  D )
fsumf1o.2  |-  ( ph  ->  C  e.  Fin )
fsumf1o.3  |-  ( ph  ->  F : C -1-1-onto-> A )
fsumf1o.4  |-  ( (
ph  /\  n  e.  C )  ->  ( F `  n )  =  G )
fsumf1o.5  |-  ( (
ph  /\  k  e.  A )  ->  B  e.  CC )
Assertion
Ref Expression
fsumf1o  |-  ( ph  -> 
sum_ k  e.  A  B  =  sum_ n  e.  C  D )
Distinct variable groups:    k, n, A    B, n    C, n    D, k    n, F    k, G    ph, k, n
Allowed substitution hints:    B( k)    C( k)    D( n)    F( k)    G( n)

Proof of Theorem fsumf1o
Dummy variables  f  m are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 sum0 13315 . . . 4  |-  sum_ k  e.  (/)  B  =  0
2 fsumf1o.3 . . . . . . . 8  |-  ( ph  ->  F : C -1-1-onto-> A )
3 f1oeq2 5740 . . . . . . . 8  |-  ( C  =  (/)  ->  ( F : C -1-1-onto-> A  <->  F : (/) -1-1-onto-> A ) )
42, 3syl5ibcom 220 . . . . . . 7  |-  ( ph  ->  ( C  =  (/)  ->  F : (/) -1-1-onto-> A ) )
54imp 429 . . . . . 6  |-  ( (
ph  /\  C  =  (/) )  ->  F : (/) -1-1-onto-> A )
6 f1ofo 5755 . . . . . 6  |-  ( F : (/)
-1-1-onto-> A  ->  F : (/) -onto-> A )
7 fo00 5781 . . . . . . 7  |-  ( F : (/) -onto-> A  <->  ( F  =  (/)  /\  A  =  (/) ) )
87simprbi 464 . . . . . 6  |-  ( F : (/) -onto-> A  ->  A  =  (/) )
95, 6, 83syl 20 . . . . 5  |-  ( (
ph  /\  C  =  (/) )  ->  A  =  (/) )
109sumeq1d 13295 . . . 4  |-  ( (
ph  /\  C  =  (/) )  ->  sum_ k  e.  A  B  =  sum_ k  e.  (/)  B )
11 simpr 461 . . . . . 6  |-  ( (
ph  /\  C  =  (/) )  ->  C  =  (/) )
1211sumeq1d 13295 . . . . 5  |-  ( (
ph  /\  C  =  (/) )  ->  sum_ n  e.  C  D  =  sum_ n  e.  (/)  D )
13 sum0 13315 . . . . 5  |-  sum_ n  e.  (/)  D  =  0
1412, 13syl6eq 2511 . . . 4  |-  ( (
ph  /\  C  =  (/) )  ->  sum_ n  e.  C  D  =  0 )
151, 10, 143eqtr4a 2521 . . 3  |-  ( (
ph  /\  C  =  (/) )  ->  sum_ k  e.  A  B  =  sum_ n  e.  C  D )
1615ex 434 . 2  |-  ( ph  ->  ( C  =  (/)  -> 
sum_ k  e.  A  B  =  sum_ n  e.  C  D ) )
17 fveq2 5798 . . . . . . . . 9  |-  ( m  =  ( f `  n )  ->  ( F `  m )  =  ( F `  ( f `  n
) ) )
1817fveq2d 5802 . . . . . . . 8  |-  ( m  =  ( f `  n )  ->  (
( k  e.  A  |->  B ) `  ( F `  m )
)  =  ( ( k  e.  A  |->  B ) `  ( F `
 ( f `  n ) ) ) )
19 simprl 755 . . . . . . . 8  |-  ( (
ph  /\  ( ( # `
 C )  e.  NN  /\  f : ( 1 ... ( # `
 C ) ) -1-1-onto-> C ) )  ->  ( # `
 C )  e.  NN )
20 simprr 756 . . . . . . . 8  |-  ( (
ph  /\  ( ( # `
 C )  e.  NN  /\  f : ( 1 ... ( # `
 C ) ) -1-1-onto-> C ) )  ->  f : ( 1 ... ( # `  C
) ) -1-1-onto-> C )
21 f1of 5748 . . . . . . . . . . . 12  |-  ( F : C -1-1-onto-> A  ->  F : C
--> A )
222, 21syl 16 . . . . . . . . . . 11  |-  ( ph  ->  F : C --> A )
2322ffvelrnda 5951 . . . . . . . . . 10  |-  ( (
ph  /\  m  e.  C )  ->  ( F `  m )  e.  A )
24 fsumf1o.5 . . . . . . . . . . . 12  |-  ( (
ph  /\  k  e.  A )  ->  B  e.  CC )
25 eqid 2454 . . . . . . . . . . . 12  |-  ( k  e.  A  |->  B )  =  ( k  e.  A  |->  B )
2624, 25fmptd 5975 . . . . . . . . . . 11  |-  ( ph  ->  ( k  e.  A  |->  B ) : A --> CC )
2726ffvelrnda 5951 . . . . . . . . . 10  |-  ( (
ph  /\  ( F `  m )  e.  A
)  ->  ( (
k  e.  A  |->  B ) `  ( F `
 m ) )  e.  CC )
2823, 27syldan 470 . . . . . . . . 9  |-  ( (
ph  /\  m  e.  C )  ->  (
( k  e.  A  |->  B ) `  ( F `  m )
)  e.  CC )
2928adantlr 714 . . . . . . . 8  |-  ( ( ( ph  /\  (
( # `  C )  e.  NN  /\  f : ( 1 ... ( # `  C
) ) -1-1-onto-> C ) )  /\  m  e.  C )  ->  ( ( k  e.  A  |->  B ) `  ( F `  m ) )  e.  CC )
302adantr 465 . . . . . . . . . . . 12  |-  ( (
ph  /\  ( ( # `
 C )  e.  NN  /\  f : ( 1 ... ( # `
 C ) ) -1-1-onto-> C ) )  ->  F : C -1-1-onto-> A )
31 f1oco 5770 . . . . . . . . . . . 12  |-  ( ( F : C -1-1-onto-> A  /\  f : ( 1 ... ( # `  C
) ) -1-1-onto-> C )  ->  ( F  o.  f ) : ( 1 ... ( # `  C
) ) -1-1-onto-> A )
3230, 20, 31syl2anc 661 . . . . . . . . . . 11  |-  ( (
ph  /\  ( ( # `
 C )  e.  NN  /\  f : ( 1 ... ( # `
 C ) ) -1-1-onto-> C ) )  ->  ( F  o.  f ) : ( 1 ... ( # `  C
) ) -1-1-onto-> A )
33 f1of 5748 . . . . . . . . . . 11  |-  ( ( F  o.  f ) : ( 1 ... ( # `  C
) ) -1-1-onto-> A  ->  ( F  o.  f ) : ( 1 ... ( # `  C ) ) --> A )
3432, 33syl 16 . . . . . . . . . 10  |-  ( (
ph  /\  ( ( # `
 C )  e.  NN  /\  f : ( 1 ... ( # `
 C ) ) -1-1-onto-> C ) )  ->  ( F  o.  f ) : ( 1 ... ( # `  C
) ) --> A )
35 fvco3 5876 . . . . . . . . . 10  |-  ( ( ( F  o.  f
) : ( 1 ... ( # `  C
) ) --> A  /\  n  e.  ( 1 ... ( # `  C
) ) )  -> 
( ( ( k  e.  A  |->  B )  o.  ( F  o.  f ) ) `  n )  =  ( ( k  e.  A  |->  B ) `  (
( F  o.  f
) `  n )
) )
3634, 35sylan 471 . . . . . . . . 9  |-  ( ( ( ph  /\  (
( # `  C )  e.  NN  /\  f : ( 1 ... ( # `  C
) ) -1-1-onto-> C ) )  /\  n  e.  ( 1 ... ( # `  C
) ) )  -> 
( ( ( k  e.  A  |->  B )  o.  ( F  o.  f ) ) `  n )  =  ( ( k  e.  A  |->  B ) `  (
( F  o.  f
) `  n )
) )
37 f1of 5748 . . . . . . . . . . . 12  |-  ( f : ( 1 ... ( # `  C
) ) -1-1-onto-> C  ->  f :
( 1 ... ( # `
 C ) ) --> C )
3837ad2antll 728 . . . . . . . . . . 11  |-  ( (
ph  /\  ( ( # `
 C )  e.  NN  /\  f : ( 1 ... ( # `
 C ) ) -1-1-onto-> C ) )  ->  f : ( 1 ... ( # `  C
) ) --> C )
39 fvco3 5876 . . . . . . . . . . 11  |-  ( ( f : ( 1 ... ( # `  C
) ) --> C  /\  n  e.  ( 1 ... ( # `  C
) ) )  -> 
( ( F  o.  f ) `  n
)  =  ( F `
 ( f `  n ) ) )
4038, 39sylan 471 . . . . . . . . . 10  |-  ( ( ( ph  /\  (
( # `  C )  e.  NN  /\  f : ( 1 ... ( # `  C
) ) -1-1-onto-> C ) )  /\  n  e.  ( 1 ... ( # `  C
) ) )  -> 
( ( F  o.  f ) `  n
)  =  ( F `
 ( f `  n ) ) )
4140fveq2d 5802 . . . . . . . . 9  |-  ( ( ( ph  /\  (
( # `  C )  e.  NN  /\  f : ( 1 ... ( # `  C
) ) -1-1-onto-> C ) )  /\  n  e.  ( 1 ... ( # `  C
) ) )  -> 
( ( k  e.  A  |->  B ) `  ( ( F  o.  f ) `  n
) )  =  ( ( k  e.  A  |->  B ) `  ( F `  ( f `  n ) ) ) )
4236, 41eqtrd 2495 . . . . . . . 8  |-  ( ( ( ph  /\  (
( # `  C )  e.  NN  /\  f : ( 1 ... ( # `  C
) ) -1-1-onto-> C ) )  /\  n  e.  ( 1 ... ( # `  C
) ) )  -> 
( ( ( k  e.  A  |->  B )  o.  ( F  o.  f ) ) `  n )  =  ( ( k  e.  A  |->  B ) `  ( F `  ( f `  n ) ) ) )
4318, 19, 20, 29, 42fsum 13314 . . . . . . 7  |-  ( (
ph  /\  ( ( # `
 C )  e.  NN  /\  f : ( 1 ... ( # `
 C ) ) -1-1-onto-> C ) )  ->  sum_ m  e.  C  ( (
k  e.  A  |->  B ) `  ( F `
 m ) )  =  (  seq 1
(  +  ,  ( ( k  e.  A  |->  B )  o.  ( F  o.  f )
) ) `  ( # `
 C ) ) )
44 fsumf1o.4 . . . . . . . . . . . . . 14  |-  ( (
ph  /\  n  e.  C )  ->  ( F `  n )  =  G )
4522ffvelrnda 5951 . . . . . . . . . . . . . 14  |-  ( (
ph  /\  n  e.  C )  ->  ( F `  n )  e.  A )
4644, 45eqeltrrd 2543 . . . . . . . . . . . . 13  |-  ( (
ph  /\  n  e.  C )  ->  G  e.  A )
47 fsumf1o.1 . . . . . . . . . . . . . 14  |-  ( k  =  G  ->  B  =  D )
4847, 25fvmpti 5881 . . . . . . . . . . . . 13  |-  ( G  e.  A  ->  (
( k  e.  A  |->  B ) `  G
)  =  (  _I 
`  D ) )
4946, 48syl 16 . . . . . . . . . . . 12  |-  ( (
ph  /\  n  e.  C )  ->  (
( k  e.  A  |->  B ) `  G
)  =  (  _I 
`  D ) )
5044fveq2d 5802 . . . . . . . . . . . 12  |-  ( (
ph  /\  n  e.  C )  ->  (
( k  e.  A  |->  B ) `  ( F `  n )
)  =  ( ( k  e.  A  |->  B ) `  G ) )
51 eqid 2454 . . . . . . . . . . . . . 14  |-  ( n  e.  C  |->  D )  =  ( n  e.  C  |->  D )
5251fvmpt2i 5888 . . . . . . . . . . . . 13  |-  ( n  e.  C  ->  (
( n  e.  C  |->  D ) `  n
)  =  (  _I 
`  D ) )
5352adantl 466 . . . . . . . . . . . 12  |-  ( (
ph  /\  n  e.  C )  ->  (
( n  e.  C  |->  D ) `  n
)  =  (  _I 
`  D ) )
5449, 50, 533eqtr4rd 2506 . . . . . . . . . . 11  |-  ( (
ph  /\  n  e.  C )  ->  (
( n  e.  C  |->  D ) `  n
)  =  ( ( k  e.  A  |->  B ) `  ( F `
 n ) ) )
5554ralrimiva 2829 . . . . . . . . . 10  |-  ( ph  ->  A. n  e.  C  ( ( n  e.  C  |->  D ) `  n )  =  ( ( k  e.  A  |->  B ) `  ( F `  n )
) )
56 nffvmpt1 5806 . . . . . . . . . . . 12  |-  F/_ n
( ( n  e.  C  |->  D ) `  m )
5756nfeq1 2630 . . . . . . . . . . 11  |-  F/ n
( ( n  e.  C  |->  D ) `  m )  =  ( ( k  e.  A  |->  B ) `  ( F `  m )
)
58 fveq2 5798 . . . . . . . . . . . 12  |-  ( n  =  m  ->  (
( n  e.  C  |->  D ) `  n
)  =  ( ( n  e.  C  |->  D ) `  m ) )
59 fveq2 5798 . . . . . . . . . . . . 13  |-  ( n  =  m  ->  ( F `  n )  =  ( F `  m ) )
6059fveq2d 5802 . . . . . . . . . . . 12  |-  ( n  =  m  ->  (
( k  e.  A  |->  B ) `  ( F `  n )
)  =  ( ( k  e.  A  |->  B ) `  ( F `
 m ) ) )
6158, 60eqeq12d 2476 . . . . . . . . . . 11  |-  ( n  =  m  ->  (
( ( n  e.  C  |->  D ) `  n )  =  ( ( k  e.  A  |->  B ) `  ( F `  n )
)  <->  ( ( n  e.  C  |->  D ) `
 m )  =  ( ( k  e.  A  |->  B ) `  ( F `  m ) ) ) )
6257, 61rspc 3171 . . . . . . . . . 10  |-  ( m  e.  C  ->  ( A. n  e.  C  ( ( n  e.  C  |->  D ) `  n )  =  ( ( k  e.  A  |->  B ) `  ( F `  n )
)  ->  ( (
n  e.  C  |->  D ) `  m )  =  ( ( k  e.  A  |->  B ) `
 ( F `  m ) ) ) )
6355, 62mpan9 469 . . . . . . . . 9  |-  ( (
ph  /\  m  e.  C )  ->  (
( n  e.  C  |->  D ) `  m
)  =  ( ( k  e.  A  |->  B ) `  ( F `
 m ) ) )
6463adantlr 714 . . . . . . . 8  |-  ( ( ( ph  /\  (
( # `  C )  e.  NN  /\  f : ( 1 ... ( # `  C
) ) -1-1-onto-> C ) )  /\  m  e.  C )  ->  ( ( n  e.  C  |->  D ) `  m )  =  ( ( k  e.  A  |->  B ) `  ( F `  m )
) )
6564sumeq2dv 13297 . . . . . . 7  |-  ( (
ph  /\  ( ( # `
 C )  e.  NN  /\  f : ( 1 ... ( # `
 C ) ) -1-1-onto-> C ) )  ->  sum_ m  e.  C  ( (
n  e.  C  |->  D ) `  m )  =  sum_ m  e.  C  ( ( k  e.  A  |->  B ) `  ( F `  m ) ) )
66 fveq2 5798 . . . . . . . 8  |-  ( m  =  ( ( F  o.  f ) `  n )  ->  (
( k  e.  A  |->  B ) `  m
)  =  ( ( k  e.  A  |->  B ) `  ( ( F  o.  f ) `
 n ) ) )
6726adantr 465 . . . . . . . . 9  |-  ( (
ph  /\  ( ( # `
 C )  e.  NN  /\  f : ( 1 ... ( # `
 C ) ) -1-1-onto-> C ) )  ->  (
k  e.  A  |->  B ) : A --> CC )
6867ffvelrnda 5951 . . . . . . . 8  |-  ( ( ( ph  /\  (
( # `  C )  e.  NN  /\  f : ( 1 ... ( # `  C
) ) -1-1-onto-> C ) )  /\  m  e.  A )  ->  ( ( k  e.  A  |->  B ) `  m )  e.  CC )
6966, 19, 32, 68, 36fsum 13314 . . . . . . 7  |-  ( (
ph  /\  ( ( # `
 C )  e.  NN  /\  f : ( 1 ... ( # `
 C ) ) -1-1-onto-> C ) )  ->  sum_ m  e.  A  ( (
k  e.  A  |->  B ) `  m )  =  (  seq 1
(  +  ,  ( ( k  e.  A  |->  B )  o.  ( F  o.  f )
) ) `  ( # `
 C ) ) )
7043, 65, 693eqtr4rd 2506 . . . . . 6  |-  ( (
ph  /\  ( ( # `
 C )  e.  NN  /\  f : ( 1 ... ( # `
 C ) ) -1-1-onto-> C ) )  ->  sum_ m  e.  A  ( (
k  e.  A  |->  B ) `  m )  =  sum_ m  e.  C  ( ( n  e.  C  |->  D ) `  m ) )
71 sumfc 13303 . . . . . 6  |-  sum_ m  e.  A  ( (
k  e.  A  |->  B ) `  m )  =  sum_ k  e.  A  B
72 sumfc 13303 . . . . . 6  |-  sum_ m  e.  C  ( (
n  e.  C  |->  D ) `  m )  =  sum_ n  e.  C  D
7370, 71, 723eqtr3g 2518 . . . . 5  |-  ( (
ph  /\  ( ( # `
 C )  e.  NN  /\  f : ( 1 ... ( # `
 C ) ) -1-1-onto-> C ) )  ->  sum_ k  e.  A  B  =  sum_ n  e.  C  D
)
7473expr 615 . . . 4  |-  ( (
ph  /\  ( # `  C
)  e.  NN )  ->  ( f : ( 1 ... ( # `
 C ) ) -1-1-onto-> C  ->  sum_ k  e.  A  B  =  sum_ n  e.  C  D ) )
7574exlimdv 1691 . . 3  |-  ( (
ph  /\  ( # `  C
)  e.  NN )  ->  ( E. f 
f : ( 1 ... ( # `  C
) ) -1-1-onto-> C  ->  sum_ k  e.  A  B  =  sum_ n  e.  C  D ) )
7675expimpd 603 . 2  |-  ( ph  ->  ( ( ( # `  C )  e.  NN  /\ 
E. f  f : ( 1 ... ( # `
 C ) ) -1-1-onto-> C )  ->  sum_ k  e.  A  B  =  sum_ n  e.  C  D ) )
77 fsumf1o.2 . . 3  |-  ( ph  ->  C  e.  Fin )
78 fz1f1o 13304 . . 3  |-  ( C  e.  Fin  ->  ( C  =  (/)  \/  (
( # `  C )  e.  NN  /\  E. f  f : ( 1 ... ( # `  C ) ) -1-1-onto-> C ) ) )
7977, 78syl 16 . 2  |-  ( ph  ->  ( C  =  (/)  \/  ( ( # `  C
)  e.  NN  /\  E. f  f : ( 1 ... ( # `  C ) ) -1-1-onto-> C ) ) )
8016, 76, 79mpjaod 381 1  |-  ( ph  -> 
sum_ k  e.  A  B  =  sum_ n  e.  C  D )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    \/ wo 368    /\ wa 369    = wceq 1370   E.wex 1587    e. wcel 1758   A.wral 2798   (/)c0 3744    |-> cmpt 4457    _I cid 4738    o. ccom 4951   -->wf 5521   -onto->wfo 5523   -1-1-onto->wf1o 5524   ` cfv 5525  (class class class)co 6199   Fincfn 7419   CCcc 9390   0cc0 9392   1c1 9393    + caddc 9395   NNcn 10432   ...cfz 11553    seqcseq 11922   #chash 12219   sum_csu 13280
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1592  ax-4 1603  ax-5 1671  ax-6 1710  ax-7 1730  ax-8 1760  ax-9 1762  ax-10 1777  ax-11 1782  ax-12 1794  ax-13 1955  ax-ext 2432  ax-rep 4510  ax-sep 4520  ax-nul 4528  ax-pow 4577  ax-pr 4638  ax-un 6481  ax-inf2 7957  ax-cnex 9448  ax-resscn 9449  ax-1cn 9450  ax-icn 9451  ax-addcl 9452  ax-addrcl 9453  ax-mulcl 9454  ax-mulrcl 9455  ax-mulcom 9456  ax-addass 9457  ax-mulass 9458  ax-distr 9459  ax-i2m1 9460  ax-1ne0 9461  ax-1rid 9462  ax-rnegex 9463  ax-rrecex 9464  ax-cnre 9465  ax-pre-lttri 9466  ax-pre-lttrn 9467  ax-pre-ltadd 9468  ax-pre-mulgt0 9469  ax-pre-sup 9470
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 966  df-3an 967  df-tru 1373  df-fal 1376  df-ex 1588  df-nf 1591  df-sb 1703  df-eu 2266  df-mo 2267  df-clab 2440  df-cleq 2446  df-clel 2449  df-nfc 2604  df-ne 2649  df-nel 2650  df-ral 2803  df-rex 2804  df-reu 2805  df-rmo 2806  df-rab 2807  df-v 3078  df-sbc 3293  df-csb 3395  df-dif 3438  df-un 3440  df-in 3442  df-ss 3449  df-pss 3451  df-nul 3745  df-if 3899  df-pw 3969  df-sn 3985  df-pr 3987  df-tp 3989  df-op 3991  df-uni 4199  df-int 4236  df-iun 4280  df-br 4400  df-opab 4458  df-mpt 4459  df-tr 4493  df-eprel 4739  df-id 4743  df-po 4748  df-so 4749  df-fr 4786  df-se 4787  df-we 4788  df-ord 4829  df-on 4830  df-lim 4831  df-suc 4832  df-xp 4953  df-rel 4954  df-cnv 4955  df-co 4956  df-dm 4957  df-rn 4958  df-res 4959  df-ima 4960  df-iota 5488  df-fun 5527  df-fn 5528  df-f 5529  df-f1 5530  df-fo 5531  df-f1o 5532  df-fv 5533  df-isom 5534  df-riota 6160  df-ov 6202  df-oprab 6203  df-mpt2 6204  df-om 6586  df-1st 6686  df-2nd 6687  df-recs 6941  df-rdg 6975  df-1o 7029  df-oadd 7033  df-er 7210  df-en 7420  df-dom 7421  df-sdom 7422  df-fin 7423  df-sup 7801  df-oi 7834  df-card 8219  df-pnf 9530  df-mnf 9531  df-xr 9532  df-ltxr 9533  df-le 9534  df-sub 9707  df-neg 9708  df-div 10104  df-nn 10433  df-2 10490  df-3 10491  df-n0 10690  df-z 10757  df-uz 10972  df-rp 11102  df-fz 11554  df-fzo 11665  df-seq 11923  df-exp 11982  df-hash 12220  df-cj 12705  df-re 12706  df-im 12707  df-sqr 12841  df-abs 12842  df-clim 13083  df-sum 13281
This theorem is referenced by:  fsumss  13319  fsum2dlem  13354  fsumcnv  13357  fsumrev  13363  fsumshft  13364  ackbijnn  13408  incexclem  13416  ovoliunlem1  21116  ovolicc2lem4  21134  itg1addlem4  21309  itg1mulc  21314  basellem3  22552  basellem5  22554  fsumdvdscom  22657  dvdsflsumcom  22660  musum  22663  fsumdvdsmul  22667  sgmppw  22668  fsumvma  22684  dchrsum2  22739  sumdchr2  22741  dchrisumlem1  22870  dchrisum0flblem1  22889  dchrisum0fno1  22892  eulerpartlemgs2  26906  phisum  29714
  Copyright terms: Public domain W3C validator