Metamath Proof Explorer

Theorem sticksstones8

Description: Establish mapping between strictly monotone functions and functions that sum to a fixed non-negative integer. (Contributed by metakunt, 1-Oct-2024)

Ref Expression
Hypotheses sticksstones8.1 
|- ( ph -> N e. NN0 )
sticksstones8.2 
|- ( ph -> K e. NN0 )
sticksstones8.3 
|- F = ( a e. A |-> ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) )
sticksstones8.4 
|- A = { g | ( g : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( g ` i ) = N ) }
sticksstones8.5 
|- B = { f | ( f : ( 1 ... K ) --> ( 1 ... ( N + K ) ) /\ A. x e. ( 1 ... K ) A. y e. ( 1 ... K ) ( x < y -> ( f ` x ) < ( f ` y ) ) ) }
Assertion sticksstones8 
|- ( ph -> F : A --> B )

Proof

Step Hyp Ref Expression
1 sticksstones8.1 
 |-  ( ph -> N e. NN0 )
2 sticksstones8.2 
 |-  ( ph -> K e. NN0 )
3 sticksstones8.3 
 |-  F = ( a e. A |-> ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) )
4 sticksstones8.4 
 |-  A = { g | ( g : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( g ` i ) = N ) }
5 sticksstones8.5 
 |-  B = { f | ( f : ( 1 ... K ) --> ( 1 ... ( N + K ) ) /\ A. x e. ( 1 ... K ) A. y e. ( 1 ... K ) ( x < y -> ( f ` x ) < ( f ` y ) ) ) }
6 eqidd 
 |-  ( ( ph /\ a e. A /\ j e. ( 1 ... K ) ) -> ( e e. ( 1 ... K ) |-> ( e + sum_ l e. ( 1 ... e ) ( a ` l ) ) ) = ( e e. ( 1 ... K ) |-> ( e + sum_ l e. ( 1 ... e ) ( a ` l ) ) ) )
7 simpr 
 |-  ( ( ( ph /\ a e. A /\ j e. ( 1 ... K ) ) /\ e = j ) -> e = j )
8 7 oveq2d 
 |-  ( ( ( ph /\ a e. A /\ j e. ( 1 ... K ) ) /\ e = j ) -> ( 1 ... e ) = ( 1 ... j ) )
9 8 sumeq1d 
 |-  ( ( ( ph /\ a e. A /\ j e. ( 1 ... K ) ) /\ e = j ) -> sum_ l e. ( 1 ... e ) ( a ` l ) = sum_ l e. ( 1 ... j ) ( a ` l ) )
10 7 9 oveq12d 
 |-  ( ( ( ph /\ a e. A /\ j e. ( 1 ... K ) ) /\ e = j ) -> ( e + sum_ l e. ( 1 ... e ) ( a ` l ) ) = ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) )
11 simp3 
 |-  ( ( ph /\ a e. A /\ j e. ( 1 ... K ) ) -> j e. ( 1 ... K ) )
12 ovexd 
 |-  ( ( ph /\ a e. A /\ j e. ( 1 ... K ) ) -> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) e. _V )
13 6 10 11 12 fvmptd 
 |-  ( ( ph /\ a e. A /\ j e. ( 1 ... K ) ) -> ( ( e e. ( 1 ... K ) |-> ( e + sum_ l e. ( 1 ... e ) ( a ` l ) ) ) ` j ) = ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) )
14 1 3ad2ant1 
 |-  ( ( ph /\ a e. A /\ j e. ( 1 ... K ) ) -> N e. NN0 )
15 2 3ad2ant1 
 |-  ( ( ph /\ a e. A /\ j e. ( 1 ... K ) ) -> K e. NN0 )
16 simpr 
 |-  ( ( ph /\ a e. A ) -> a e. A )
17 4 a1i 
 |-  ( ( ph /\ a e. A ) -> A = { g | ( g : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( g ` i ) = N ) } )
18 17 eqcomd 
 |-  ( ( ph /\ a e. A ) -> { g | ( g : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( g ` i ) = N ) } = A )
19 16 18 eleqtrrd 
 |-  ( ( ph /\ a e. A ) -> a e. { g | ( g : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( g ` i ) = N ) } )
20 feq1 
 |-  ( g = a -> ( g : ( 1 ... ( K + 1 ) ) --> NN0 <-> a : ( 1 ... ( K + 1 ) ) --> NN0 ) )
21 simpl 
 |-  ( ( g = a /\ i e. ( 1 ... ( K + 1 ) ) ) -> g = a )
22 21 fveq1d 
 |-  ( ( g = a /\ i e. ( 1 ... ( K + 1 ) ) ) -> ( g ` i ) = ( a ` i ) )
23 22 sumeq2dv 
 |-  ( g = a -> sum_ i e. ( 1 ... ( K + 1 ) ) ( g ` i ) = sum_ i e. ( 1 ... ( K + 1 ) ) ( a ` i ) )
24 23 eqeq1d 
 |-  ( g = a -> ( sum_ i e. ( 1 ... ( K + 1 ) ) ( g ` i ) = N <-> sum_ i e. ( 1 ... ( K + 1 ) ) ( a ` i ) = N ) )
25 20 24 anbi12d 
 |-  ( g = a -> ( ( g : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( g ` i ) = N ) <-> ( a : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( a ` i ) = N ) ) )
26 25 elabg 
 |-  ( a e. A -> ( a e. { g | ( g : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( g ` i ) = N ) } <-> ( a : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( a ` i ) = N ) ) )
27 16 26 syl 
 |-  ( ( ph /\ a e. A ) -> ( a e. { g | ( g : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( g ` i ) = N ) } <-> ( a : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( a ` i ) = N ) ) )
28 27 biimpd 
 |-  ( ( ph /\ a e. A ) -> ( a e. { g | ( g : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( g ` i ) = N ) } -> ( a : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( a ` i ) = N ) ) )
29 19 28 mpd 
 |-  ( ( ph /\ a e. A ) -> ( a : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( a ` i ) = N ) )
30 29 simpld 
 |-  ( ( ph /\ a e. A ) -> a : ( 1 ... ( K + 1 ) ) --> NN0 )
31 30 3adant3 
 |-  ( ( ph /\ a e. A /\ j e. ( 1 ... K ) ) -> a : ( 1 ... ( K + 1 ) ) --> NN0 )
32 eqid 
 |-  ( e e. ( 1 ... K ) |-> ( e + sum_ l e. ( 1 ... e ) ( a ` l ) ) ) = ( e e. ( 1 ... K ) |-> ( e + sum_ l e. ( 1 ... e ) ( a ` l ) ) )
33 fveq2 
 |-  ( i = l -> ( a ` i ) = ( a ` l ) )
34 nfcv 
 |-  F/_ l ( 1 ... ( K + 1 ) )
35 nfcv 
 |-  F/_ i ( 1 ... ( K + 1 ) )
36 nfcv 
 |-  F/_ l ( a ` i )
37 nfcv 
 |-  F/_ i ( a ` l )
38 33 34 35 36 37 cbvsum 
 |-  sum_ i e. ( 1 ... ( K + 1 ) ) ( a ` i ) = sum_ l e. ( 1 ... ( K + 1 ) ) ( a ` l )
39 29 simprd 
 |-  ( ( ph /\ a e. A ) -> sum_ i e. ( 1 ... ( K + 1 ) ) ( a ` i ) = N )
40 38 39 eqtr3id 
 |-  ( ( ph /\ a e. A ) -> sum_ l e. ( 1 ... ( K + 1 ) ) ( a ` l ) = N )
41 40 3adant3 
 |-  ( ( ph /\ a e. A /\ j e. ( 1 ... K ) ) -> sum_ l e. ( 1 ... ( K + 1 ) ) ( a ` l ) = N )
42 14 15 31 11 32 41 sticksstones7 
 |-  ( ( ph /\ a e. A /\ j e. ( 1 ... K ) ) -> ( ( e e. ( 1 ... K ) |-> ( e + sum_ l e. ( 1 ... e ) ( a ` l ) ) ) ` j ) e. ( 1 ... ( N + K ) ) )
43 13 42 eqeltrrd 
 |-  ( ( ph /\ a e. A /\ j e. ( 1 ... K ) ) -> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) e. ( 1 ... ( N + K ) ) )
44 43 3expa 
 |-  ( ( ( ph /\ a e. A ) /\ j e. ( 1 ... K ) ) -> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) e. ( 1 ... ( N + K ) ) )
45 eqid 
 |-  ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) = ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) )
46 44 45 fmptd 
 |-  ( ( ph /\ a e. A ) -> ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) : ( 1 ... K ) --> ( 1 ... ( N + K ) ) )
47 1 ad3antrrr 
 |-  ( ( ( ( ph /\ a e. A ) /\ x e. ( 1 ... K ) ) /\ y e. ( 1 ... K ) ) -> N e. NN0 )
48 47 adantr 
 |-  ( ( ( ( ( ph /\ a e. A ) /\ x e. ( 1 ... K ) ) /\ y e. ( 1 ... K ) ) /\ x < y ) -> N e. NN0 )
49 2 ad3antrrr 
 |-  ( ( ( ( ph /\ a e. A ) /\ x e. ( 1 ... K ) ) /\ y e. ( 1 ... K ) ) -> K e. NN0 )
50 49 adantr 
 |-  ( ( ( ( ( ph /\ a e. A ) /\ x e. ( 1 ... K ) ) /\ y e. ( 1 ... K ) ) /\ x < y ) -> K e. NN0 )
51 26 adantl 
 |-  ( ( ph /\ a e. A ) -> ( a e. { g | ( g : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( g ` i ) = N ) } <-> ( a : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( a ` i ) = N ) ) )
52 51 biimpd 
 |-  ( ( ph /\ a e. A ) -> ( a e. { g | ( g : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( g ` i ) = N ) } -> ( a : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( a ` i ) = N ) ) )
53 19 52 mpd 
 |-  ( ( ph /\ a e. A ) -> ( a : ( 1 ... ( K + 1 ) ) --> NN0 /\ sum_ i e. ( 1 ... ( K + 1 ) ) ( a ` i ) = N ) )
54 53 simpld 
 |-  ( ( ph /\ a e. A ) -> a : ( 1 ... ( K + 1 ) ) --> NN0 )
55 54 adantr 
 |-  ( ( ( ph /\ a e. A ) /\ x e. ( 1 ... K ) ) -> a : ( 1 ... ( K + 1 ) ) --> NN0 )
56 55 adantr 
 |-  ( ( ( ( ph /\ a e. A ) /\ x e. ( 1 ... K ) ) /\ y e. ( 1 ... K ) ) -> a : ( 1 ... ( K + 1 ) ) --> NN0 )
57 56 adantr 
 |-  ( ( ( ( ( ph /\ a e. A ) /\ x e. ( 1 ... K ) ) /\ y e. ( 1 ... K ) ) /\ x < y ) -> a : ( 1 ... ( K + 1 ) ) --> NN0 )
58 simpllr 
 |-  ( ( ( ( ( ph /\ a e. A ) /\ x e. ( 1 ... K ) ) /\ y e. ( 1 ... K ) ) /\ x < y ) -> x e. ( 1 ... K ) )
59 simplr 
 |-  ( ( ( ( ( ph /\ a e. A ) /\ x e. ( 1 ... K ) ) /\ y e. ( 1 ... K ) ) /\ x < y ) -> y e. ( 1 ... K ) )
60 simpr 
 |-  ( ( ( ( ( ph /\ a e. A ) /\ x e. ( 1 ... K ) ) /\ y e. ( 1 ... K ) ) /\ x < y ) -> x < y )
61 48 50 57 58 59 60 45 sticksstones6 
 |-  ( ( ( ( ( ph /\ a e. A ) /\ x e. ( 1 ... K ) ) /\ y e. ( 1 ... K ) ) /\ x < y ) -> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` x ) < ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` y ) )
62 61 ex 
 |-  ( ( ( ( ph /\ a e. A ) /\ x e. ( 1 ... K ) ) /\ y e. ( 1 ... K ) ) -> ( x < y -> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` x ) < ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` y ) ) )
63 62 ralrimiva 
 |-  ( ( ( ph /\ a e. A ) /\ x e. ( 1 ... K ) ) -> A. y e. ( 1 ... K ) ( x < y -> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` x ) < ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` y ) ) )
64 63 ralrimiva 
 |-  ( ( ph /\ a e. A ) -> A. x e. ( 1 ... K ) A. y e. ( 1 ... K ) ( x < y -> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` x ) < ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` y ) ) )
65 46 64 jca 
 |-  ( ( ph /\ a e. A ) -> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) : ( 1 ... K ) --> ( 1 ... ( N + K ) ) /\ A. x e. ( 1 ... K ) A. y e. ( 1 ... K ) ( x < y -> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` x ) < ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` y ) ) ) )
66 fzfid 
 |-  ( ( ph /\ a e. A ) -> ( 1 ... K ) e. Fin )
67 46 66 fexd 
 |-  ( ( ph /\ a e. A ) -> ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) e. _V )
68 feq1 
 |-  ( f = ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) -> ( f : ( 1 ... K ) --> ( 1 ... ( N + K ) ) <-> ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) : ( 1 ... K ) --> ( 1 ... ( N + K ) ) ) )
69 fveq1 
 |-  ( f = ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) -> ( f ` x ) = ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` x ) )
70 fveq1 
 |-  ( f = ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) -> ( f ` y ) = ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` y ) )
71 69 70 breq12d 
 |-  ( f = ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) -> ( ( f ` x ) < ( f ` y ) <-> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` x ) < ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` y ) ) )
72 71 imbi2d 
 |-  ( f = ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) -> ( ( x < y -> ( f ` x ) < ( f ` y ) ) <-> ( x < y -> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` x ) < ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` y ) ) ) )
73 72 2ralbidv 
 |-  ( f = ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) -> ( A. x e. ( 1 ... K ) A. y e. ( 1 ... K ) ( x < y -> ( f ` x ) < ( f ` y ) ) <-> A. x e. ( 1 ... K ) A. y e. ( 1 ... K ) ( x < y -> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` x ) < ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` y ) ) ) )
74 68 73 anbi12d 
 |-  ( f = ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) -> ( ( f : ( 1 ... K ) --> ( 1 ... ( N + K ) ) /\ A. x e. ( 1 ... K ) A. y e. ( 1 ... K ) ( x < y -> ( f ` x ) < ( f ` y ) ) ) <-> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) : ( 1 ... K ) --> ( 1 ... ( N + K ) ) /\ A. x e. ( 1 ... K ) A. y e. ( 1 ... K ) ( x < y -> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` x ) < ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` y ) ) ) ) )
75 74 elabg 
 |-  ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) e. _V -> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) e. { f | ( f : ( 1 ... K ) --> ( 1 ... ( N + K ) ) /\ A. x e. ( 1 ... K ) A. y e. ( 1 ... K ) ( x < y -> ( f ` x ) < ( f ` y ) ) ) } <-> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) : ( 1 ... K ) --> ( 1 ... ( N + K ) ) /\ A. x e. ( 1 ... K ) A. y e. ( 1 ... K ) ( x < y -> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` x ) < ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` y ) ) ) ) )
76 67 75 syl 
 |-  ( ( ph /\ a e. A ) -> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) e. { f | ( f : ( 1 ... K ) --> ( 1 ... ( N + K ) ) /\ A. x e. ( 1 ... K ) A. y e. ( 1 ... K ) ( x < y -> ( f ` x ) < ( f ` y ) ) ) } <-> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) : ( 1 ... K ) --> ( 1 ... ( N + K ) ) /\ A. x e. ( 1 ... K ) A. y e. ( 1 ... K ) ( x < y -> ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` x ) < ( ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) ` y ) ) ) ) )
77 65 76 mpbird 
 |-  ( ( ph /\ a e. A ) -> ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) e. { f | ( f : ( 1 ... K ) --> ( 1 ... ( N + K ) ) /\ A. x e. ( 1 ... K ) A. y e. ( 1 ... K ) ( x < y -> ( f ` x ) < ( f ` y ) ) ) } )
78 5 a1i 
 |-  ( ( ph /\ a e. A ) -> B = { f | ( f : ( 1 ... K ) --> ( 1 ... ( N + K ) ) /\ A. x e. ( 1 ... K ) A. y e. ( 1 ... K ) ( x < y -> ( f ` x ) < ( f ` y ) ) ) } )
79 77 78 eleqtrrd 
 |-  ( ( ph /\ a e. A ) -> ( j e. ( 1 ... K ) |-> ( j + sum_ l e. ( 1 ... j ) ( a ` l ) ) ) e. B )
80 79 3 fmptd 
 |-  ( ph -> F : A --> B )