Metamath Proof Explorer

Theorem fargshiftfo

Description: If a function is onto, then also the shifted function is onto. (Contributed by Alexander van der Vekens, 24-Nov-2017)

Ref Expression
Hypothesis fargshift.g 
|- G = ( x e. ( 0 ..^ ( # ` F ) ) |-> ( F ` ( x + 1 ) ) )
Assertion fargshiftfo 
|- ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> G : ( 0 ..^ ( # ` F ) ) -onto-> dom E )

Proof

Step Hyp Ref Expression
1 fargshift.g 
 |-  G = ( x e. ( 0 ..^ ( # ` F ) ) |-> ( F ` ( x + 1 ) ) )
2 fof 
 |-  ( F : ( 1 ... N ) -onto-> dom E -> F : ( 1 ... N ) --> dom E )
3 1 fargshiftf 
 |-  ( ( N e. NN0 /\ F : ( 1 ... N ) --> dom E ) -> G : ( 0 ..^ ( # ` F ) ) --> dom E )
4 2 3 sylan2 
 |-  ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> G : ( 0 ..^ ( # ` F ) ) --> dom E )
5 1 rnmpt 
 |-  ran G = { y | E. x e. ( 0 ..^ ( # ` F ) ) y = ( F ` ( x + 1 ) ) }
6 fofn 
 |-  ( F : ( 1 ... N ) -onto-> dom E -> F Fn ( 1 ... N ) )
7 fnrnfv 
 |-  ( F Fn ( 1 ... N ) -> ran F = { y | E. z e. ( 1 ... N ) y = ( F ` z ) } )
8 6 7 syl 
 |-  ( F : ( 1 ... N ) -onto-> dom E -> ran F = { y | E. z e. ( 1 ... N ) y = ( F ` z ) } )
9 8 adantl 
 |-  ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> ran F = { y | E. z e. ( 1 ... N ) y = ( F ` z ) } )
10 df-fo 
 |-  ( F : ( 1 ... N ) -onto-> dom E <-> ( F Fn ( 1 ... N ) /\ ran F = dom E ) )
11 10 biimpi 
 |-  ( F : ( 1 ... N ) -onto-> dom E -> ( F Fn ( 1 ... N ) /\ ran F = dom E ) )
12 11 adantl 
 |-  ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> ( F Fn ( 1 ... N ) /\ ran F = dom E ) )
13 eqeq1 
 |-  ( ran F = dom E -> ( ran F = { y | E. z e. ( 1 ... N ) y = ( F ` z ) } <-> dom E = { y | E. z e. ( 1 ... N ) y = ( F ` z ) } ) )
14 eqcom 
 |-  ( dom E = { y | E. z e. ( 1 ... N ) y = ( F ` z ) } <-> { y | E. z e. ( 1 ... N ) y = ( F ` z ) } = dom E )
15 13 14 bitrdi 
 |-  ( ran F = dom E -> ( ran F = { y | E. z e. ( 1 ... N ) y = ( F ` z ) } <-> { y | E. z e. ( 1 ... N ) y = ( F ` z ) } = dom E ) )
16 ffn 
 |-  ( F : ( 1 ... N ) --> dom E -> F Fn ( 1 ... N ) )
17 fseq1hash 
 |-  ( ( N e. NN0 /\ F Fn ( 1 ... N ) ) -> ( # ` F ) = N )
18 16 17 sylan2 
 |-  ( ( N e. NN0 /\ F : ( 1 ... N ) --> dom E ) -> ( # ` F ) = N )
19 2 18 sylan2 
 |-  ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> ( # ` F ) = N )
20 fz0add1fz1 
 |-  ( ( N e. NN0 /\ x e. ( 0 ..^ N ) ) -> ( x + 1 ) e. ( 1 ... N ) )
21 nn0z 
 |-  ( N e. NN0 -> N e. ZZ )
22 fzval3 
 |-  ( N e. ZZ -> ( 1 ... N ) = ( 1 ..^ ( N + 1 ) ) )
23 21 22 syl 
 |-  ( N e. NN0 -> ( 1 ... N ) = ( 1 ..^ ( N + 1 ) ) )
24 nn0cn 
 |-  ( N e. NN0 -> N e. CC )
25 1cnd 
 |-  ( N e. NN0 -> 1 e. CC )
26 24 25 addcomd 
 |-  ( N e. NN0 -> ( N + 1 ) = ( 1 + N ) )
27 26 oveq2d 
 |-  ( N e. NN0 -> ( 1 ..^ ( N + 1 ) ) = ( 1 ..^ ( 1 + N ) ) )
28 23 27 eqtrd 
 |-  ( N e. NN0 -> ( 1 ... N ) = ( 1 ..^ ( 1 + N ) ) )
29 28 eleq2d 
 |-  ( N e. NN0 -> ( z e. ( 1 ... N ) <-> z e. ( 1 ..^ ( 1 + N ) ) ) )
30 29 biimpa 
 |-  ( ( N e. NN0 /\ z e. ( 1 ... N ) ) -> z e. ( 1 ..^ ( 1 + N ) ) )
31 21 adantr 
 |-  ( ( N e. NN0 /\ z e. ( 1 ... N ) ) -> N e. ZZ )
32 fzosubel3 
 |-  ( ( z e. ( 1 ..^ ( 1 + N ) ) /\ N e. ZZ ) -> ( z - 1 ) e. ( 0 ..^ N ) )
33 30 31 32 syl2anc 
 |-  ( ( N e. NN0 /\ z e. ( 1 ... N ) ) -> ( z - 1 ) e. ( 0 ..^ N ) )
34 oveq1 
 |-  ( x = ( z - 1 ) -> ( x + 1 ) = ( ( z - 1 ) + 1 ) )
35 34 eqeq2d 
 |-  ( x = ( z - 1 ) -> ( z = ( x + 1 ) <-> z = ( ( z - 1 ) + 1 ) ) )
36 35 adantl 
 |-  ( ( ( N e. NN0 /\ z e. ( 1 ... N ) ) /\ x = ( z - 1 ) ) -> ( z = ( x + 1 ) <-> z = ( ( z - 1 ) + 1 ) ) )
37 elfzelz 
 |-  ( z e. ( 1 ... N ) -> z e. ZZ )
38 37 zcnd 
 |-  ( z e. ( 1 ... N ) -> z e. CC )
39 38 adantl 
 |-  ( ( N e. NN0 /\ z e. ( 1 ... N ) ) -> z e. CC )
40 1cnd 
 |-  ( ( N e. NN0 /\ z e. ( 1 ... N ) ) -> 1 e. CC )
41 39 40 npcand 
 |-  ( ( N e. NN0 /\ z e. ( 1 ... N ) ) -> ( ( z - 1 ) + 1 ) = z )
42 41 eqcomd 
 |-  ( ( N e. NN0 /\ z e. ( 1 ... N ) ) -> z = ( ( z - 1 ) + 1 ) )
43 33 36 42 rspcedvd 
 |-  ( ( N e. NN0 /\ z e. ( 1 ... N ) ) -> E. x e. ( 0 ..^ N ) z = ( x + 1 ) )
44 fveq2 
 |-  ( z = ( x + 1 ) -> ( F ` z ) = ( F ` ( x + 1 ) ) )
45 44 eqeq2d 
 |-  ( z = ( x + 1 ) -> ( y = ( F ` z ) <-> y = ( F ` ( x + 1 ) ) ) )
46 45 adantl 
 |-  ( ( N e. NN0 /\ z = ( x + 1 ) ) -> ( y = ( F ` z ) <-> y = ( F ` ( x + 1 ) ) ) )
47 20 43 46 rexxfrd 
 |-  ( N e. NN0 -> ( E. z e. ( 1 ... N ) y = ( F ` z ) <-> E. x e. ( 0 ..^ N ) y = ( F ` ( x + 1 ) ) ) )
48 47 adantr 
 |-  ( ( N e. NN0 /\ ( # ` F ) = N ) -> ( E. z e. ( 1 ... N ) y = ( F ` z ) <-> E. x e. ( 0 ..^ N ) y = ( F ` ( x + 1 ) ) ) )
49 oveq2 
 |-  ( ( # ` F ) = N -> ( 0 ..^ ( # ` F ) ) = ( 0 ..^ N ) )
50 49 rexeqdv 
 |-  ( ( # ` F ) = N -> ( E. x e. ( 0 ..^ ( # ` F ) ) y = ( F ` ( x + 1 ) ) <-> E. x e. ( 0 ..^ N ) y = ( F ` ( x + 1 ) ) ) )
51 50 bibi2d 
 |-  ( ( # ` F ) = N -> ( ( E. z e. ( 1 ... N ) y = ( F ` z ) <-> E. x e. ( 0 ..^ ( # ` F ) ) y = ( F ` ( x + 1 ) ) ) <-> ( E. z e. ( 1 ... N ) y = ( F ` z ) <-> E. x e. ( 0 ..^ N ) y = ( F ` ( x + 1 ) ) ) ) )
52 51 adantl 
 |-  ( ( N e. NN0 /\ ( # ` F ) = N ) -> ( ( E. z e. ( 1 ... N ) y = ( F ` z ) <-> E. x e. ( 0 ..^ ( # ` F ) ) y = ( F ` ( x + 1 ) ) ) <-> ( E. z e. ( 1 ... N ) y = ( F ` z ) <-> E. x e. ( 0 ..^ N ) y = ( F ` ( x + 1 ) ) ) ) )
53 48 52 mpbird 
 |-  ( ( N e. NN0 /\ ( # ` F ) = N ) -> ( E. z e. ( 1 ... N ) y = ( F ` z ) <-> E. x e. ( 0 ..^ ( # ` F ) ) y = ( F ` ( x + 1 ) ) ) )
54 19 53 syldan 
 |-  ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> ( E. z e. ( 1 ... N ) y = ( F ` z ) <-> E. x e. ( 0 ..^ ( # ` F ) ) y = ( F ` ( x + 1 ) ) ) )
55 54 abbidv 
 |-  ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> { y | E. z e. ( 1 ... N ) y = ( F ` z ) } = { y | E. x e. ( 0 ..^ ( # ` F ) ) y = ( F ` ( x + 1 ) ) } )
56 55 eqeq1d 
 |-  ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> ( { y | E. z e. ( 1 ... N ) y = ( F ` z ) } = dom E <-> { y | E. x e. ( 0 ..^ ( # ` F ) ) y = ( F ` ( x + 1 ) ) } = dom E ) )
57 56 biimpcd 
 |-  ( { y | E. z e. ( 1 ... N ) y = ( F ` z ) } = dom E -> ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> { y | E. x e. ( 0 ..^ ( # ` F ) ) y = ( F ` ( x + 1 ) ) } = dom E ) )
58 15 57 biimtrdi 
 |-  ( ran F = dom E -> ( ran F = { y | E. z e. ( 1 ... N ) y = ( F ` z ) } -> ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> { y | E. x e. ( 0 ..^ ( # ` F ) ) y = ( F ` ( x + 1 ) ) } = dom E ) ) )
59 58 com23 
 |-  ( ran F = dom E -> ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> ( ran F = { y | E. z e. ( 1 ... N ) y = ( F ` z ) } -> { y | E. x e. ( 0 ..^ ( # ` F ) ) y = ( F ` ( x + 1 ) ) } = dom E ) ) )
60 59 adantl 
 |-  ( ( F Fn ( 1 ... N ) /\ ran F = dom E ) -> ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> ( ran F = { y | E. z e. ( 1 ... N ) y = ( F ` z ) } -> { y | E. x e. ( 0 ..^ ( # ` F ) ) y = ( F ` ( x + 1 ) ) } = dom E ) ) )
61 12 60 mpcom 
 |-  ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> ( ran F = { y | E. z e. ( 1 ... N ) y = ( F ` z ) } -> { y | E. x e. ( 0 ..^ ( # ` F ) ) y = ( F ` ( x + 1 ) ) } = dom E ) )
62 9 61 mpd 
 |-  ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> { y | E. x e. ( 0 ..^ ( # ` F ) ) y = ( F ` ( x + 1 ) ) } = dom E )
63 5 62 eqtrid 
 |-  ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> ran G = dom E )
64 dffo2 
 |-  ( G : ( 0 ..^ ( # ` F ) ) -onto-> dom E <-> ( G : ( 0 ..^ ( # ` F ) ) --> dom E /\ ran G = dom E ) )
65 4 63 64 sylanbrc 
 |-  ( ( N e. NN0 /\ F : ( 1 ... N ) -onto-> dom E ) -> G : ( 0 ..^ ( # ` F ) ) -onto-> dom E )