Metamath Proof Explorer

Theorem ackendofnn0

Description: The Ackermann function at any nonnegative integer is an endofunction on the nonnegative integers. (Contributed by AV, 8-May-2024)

Ref Expression
Assertion ackendofnn0 
|- ( M e. NN0 -> ( Ack ` M ) : NN0 --> NN0 )

Proof

Step Hyp Ref Expression
1 fveq2 
 |-  ( x = 0 -> ( Ack ` x ) = ( Ack ` 0 ) )
2 1 feq1d 
 |-  ( x = 0 -> ( ( Ack ` x ) : NN0 --> NN0 <-> ( Ack ` 0 ) : NN0 --> NN0 ) )
3 fveq2 
 |-  ( x = y -> ( Ack ` x ) = ( Ack ` y ) )
4 3 feq1d 
 |-  ( x = y -> ( ( Ack ` x ) : NN0 --> NN0 <-> ( Ack ` y ) : NN0 --> NN0 ) )
5 fveq2 
 |-  ( x = ( y + 1 ) -> ( Ack ` x ) = ( Ack ` ( y + 1 ) ) )
6 5 feq1d 
 |-  ( x = ( y + 1 ) -> ( ( Ack ` x ) : NN0 --> NN0 <-> ( Ack ` ( y + 1 ) ) : NN0 --> NN0 ) )
7 fveq2 
 |-  ( x = M -> ( Ack ` x ) = ( Ack ` M ) )
8 7 feq1d 
 |-  ( x = M -> ( ( Ack ` x ) : NN0 --> NN0 <-> ( Ack ` M ) : NN0 --> NN0 ) )
9 ackval0 
 |-  ( Ack ` 0 ) = ( n e. NN0 |-> ( n + 1 ) )
10 peano2nn0 
 |-  ( n e. NN0 -> ( n + 1 ) e. NN0 )
11 9 10 fmpti 
 |-  ( Ack ` 0 ) : NN0 --> NN0
12 nn0ex 
 |-  NN0 e. _V
13 12 a1i 
 |-  ( ( ( y e. NN0 /\ ( Ack ` y ) : NN0 --> NN0 ) /\ n e. NN0 ) -> NN0 e. _V )
14 simplr 
 |-  ( ( ( y e. NN0 /\ ( Ack ` y ) : NN0 --> NN0 ) /\ n e. NN0 ) -> ( Ack ` y ) : NN0 --> NN0 )
15 10 adantl 
 |-  ( ( ( y e. NN0 /\ ( Ack ` y ) : NN0 --> NN0 ) /\ n e. NN0 ) -> ( n + 1 ) e. NN0 )
16 13 14 15 itcovalendof 
 |-  ( ( ( y e. NN0 /\ ( Ack ` y ) : NN0 --> NN0 ) /\ n e. NN0 ) -> ( ( IterComp ` ( Ack ` y ) ) ` ( n + 1 ) ) : NN0 --> NN0 )
17 1nn0 
 |-  1 e. NN0
18 ffvelrn 
 |-  ( ( ( ( IterComp ` ( Ack ` y ) ) ` ( n + 1 ) ) : NN0 --> NN0 /\ 1 e. NN0 ) -> ( ( ( IterComp ` ( Ack ` y ) ) ` ( n + 1 ) ) ` 1 ) e. NN0 )
19 16 17 18 sylancl 
 |-  ( ( ( y e. NN0 /\ ( Ack ` y ) : NN0 --> NN0 ) /\ n e. NN0 ) -> ( ( ( IterComp ` ( Ack ` y ) ) ` ( n + 1 ) ) ` 1 ) e. NN0 )
20 eqid 
 |-  ( n e. NN0 |-> ( ( ( IterComp ` ( Ack ` y ) ) ` ( n + 1 ) ) ` 1 ) ) = ( n e. NN0 |-> ( ( ( IterComp ` ( Ack ` y ) ) ` ( n + 1 ) ) ` 1 ) )
21 19 20 fmptd 
 |-  ( ( y e. NN0 /\ ( Ack ` y ) : NN0 --> NN0 ) -> ( n e. NN0 |-> ( ( ( IterComp ` ( Ack ` y ) ) ` ( n + 1 ) ) ` 1 ) ) : NN0 --> NN0 )
22 ackvalsuc1mpt 
 |-  ( y e. NN0 -> ( Ack ` ( y + 1 ) ) = ( n e. NN0 |-> ( ( ( IterComp ` ( Ack ` y ) ) ` ( n + 1 ) ) ` 1 ) ) )
23 22 adantr 
 |-  ( ( y e. NN0 /\ ( Ack ` y ) : NN0 --> NN0 ) -> ( Ack ` ( y + 1 ) ) = ( n e. NN0 |-> ( ( ( IterComp ` ( Ack ` y ) ) ` ( n + 1 ) ) ` 1 ) ) )
24 23 feq1d 
 |-  ( ( y e. NN0 /\ ( Ack ` y ) : NN0 --> NN0 ) -> ( ( Ack ` ( y + 1 ) ) : NN0 --> NN0 <-> ( n e. NN0 |-> ( ( ( IterComp ` ( Ack ` y ) ) ` ( n + 1 ) ) ` 1 ) ) : NN0 --> NN0 ) )
25 21 24 mpbird 
 |-  ( ( y e. NN0 /\ ( Ack ` y ) : NN0 --> NN0 ) -> ( Ack ` ( y + 1 ) ) : NN0 --> NN0 )
26 25 ex 
 |-  ( y e. NN0 -> ( ( Ack ` y ) : NN0 --> NN0 -> ( Ack ` ( y + 1 ) ) : NN0 --> NN0 ) )
27 2 4 6 8 11 26 nn0ind 
 |-  ( M e. NN0 -> ( Ack ` M ) : NN0 --> NN0 )