Theorem nn0ind 9296

Description: Principle of Mathematical Induction (inference schema) on nonnegative integers. The first four hypotheses give us the substitution instances we need; the last two are the basis and the induction step. (Contributed by NM, 13-May-2004.)

Hypotheses

Ref	Expression
nn0ind.1	|- ( x = 0 -> ( ph <-> ps ) )
nn0ind.2	|- ( x = y -> ( ph <-> ch ) )
nn0ind.3	|- ( x = ( y + 1 ) -> ( ph <-> th ) )
nn0ind.4	|- ( x = A -> ( ph <-> ta ) )
nn0ind.5	|- ps
nn0ind.6	|- ( y e. NN0 -> ( ch -> th ) )

Assertion

Ref	Expression
nn0ind	|- ( A e. NN0 -> ta )

Distinct variable groups:   x, y   x, A   ps, x   ch, x   th, x   ta, x   ph, y

Allowed substitution hints:   ph( x)   ps( y)   ch( y)   th( y)   ta( y)   A( y)

Proof of Theorem nn0ind

Step	Hyp	Ref	Expression
1		elnn0z 9195	. 2 |- ( A e. NN0 <-> ( A e. ZZ /\ 0 <_ A ) )
2		0z 9193	. . 3 |- 0 e. ZZ
3		nn0ind.1	. . . 4 |- ( x = 0 -> ( ph <-> ps ) )
4		nn0ind.2	. . . 4 |- ( x = y -> ( ph <-> ch ) )
5		nn0ind.3	. . . 4 |- ( x = ( y + 1 ) -> ( ph <-> th ) )
6		nn0ind.4	. . . 4 |- ( x = A -> ( ph <-> ta ) )
7		nn0ind.5	. . . . 5 |- ps
8	7	a1i 9	. . . 4 |- ( 0 e. ZZ -> ps )
9		elnn0z 9195	. . . . . 6 |- ( y e. NN0 <-> ( y e. ZZ /\ 0 <_ y ) )
10		nn0ind.6	. . . . . 6 |- ( y e. NN0 -> ( ch -> th ) )
11	9, 10	sylbir 134	. . . . 5 |- ( ( y e. ZZ /\ 0 <_ y ) -> ( ch -> th ) )
12	11	3adant1 1004	. . . 4 |- ( ( 0 e. ZZ /\ y e. ZZ /\ 0 <_ y ) -> ( ch -> th ) )
13	3, 4, 5, 6, 8, 12	uzind 9293	. . 3 |- ( ( 0 e. ZZ /\ A e. ZZ /\ 0 <_ A ) -> ta )
14	2, 13	mp3an1 1313	. 2 |- ( ( A e. ZZ /\ 0 <_ A ) -> ta )
15	1, 14	sylbi 120	1 |- ( A e. NN0 -> ta )

Syntax hints:   -> wi 4   /\ wa 103   <-> wb 104   = wceq 1342   e. wcel 2135   class class class wbr 3976  (class class class)co 5836   0cc0 7744   1c1 7745   + caddc 7747   <_ cle 7925   NN0cn0 9105   ZZcz 9182

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 105  ax-ia2 106  ax-ia3 107  ax-in1 604  ax-in2 605  ax-io 699  ax-5 1434  ax-7 1435  ax-gen 1436  ax-ie1 1480  ax-ie2 1481  ax-8 1491  ax-10 1492  ax-11 1493  ax-i12 1494  ax-bndl 1496  ax-4 1497  ax-17 1513  ax-i9 1517  ax-ial 1521  ax-i5r 1522  ax-13 2137  ax-14 2138  ax-ext 2146  ax-sep 4094  ax-pow 4147  ax-pr 4181  ax-un 4405  ax-setind 4508  ax-cnex 7835  ax-resscn 7836  ax-1cn 7837  ax-1re 7838  ax-icn 7839  ax-addcl 7840  ax-addrcl 7841  ax-mulcl 7842  ax-addcom 7844  ax-addass 7846  ax-distr 7848  ax-i2m1 7849  ax-0lt1 7850  ax-0id 7852  ax-rnegex 7853  ax-cnre 7855  ax-pre-ltirr 7856  ax-pre-ltwlin 7857  ax-pre-lttrn 7858  ax-pre-ltadd 7860

This theorem depends on definitions:  df-bi 116  df-3or 968  df-3an 969  df-tru 1345  df-fal 1348  df-nf 1448  df-sb 1750  df-eu 2016  df-mo 2017  df-clab 2151  df-cleq 2157  df-clel 2160  df-nfc 2295  df-ne 2335  df-nel 2430  df-ral 2447  df-rex 2448  df-reu 2449  df-rab 2451  df-v 2723  df-sbc 2947  df-dif 3113  df-un 3115  df-in 3117  df-ss 3124  df-pw 3555  df-sn 3576  df-pr 3577  df-op 3579  df-uni 3784  df-int 3819  df-br 3977  df-opab 4038  df-id 4265  df-xp 4604  df-rel 4605  df-cnv 4606  df-co 4607  df-dm 4608  df-iota 5147  df-fun 5184  df-fv 5190  df-riota 5792  df-ov 5839  df-oprab 5840  df-mpo 5841  df-pnf 7926  df-mnf 7927  df-xr 7928  df-ltxr 7929  df-le 7930  df-sub 8062  df-neg 8063  df-inn 8849  df-n0 9106  df-z 9183

This theorem is referenced by:  zindd  9300  uzaddcl  9515  frecfzennn  10351  mulexp  10484  expadd  10487  expmul  10490  leexp1a  10500  bernneq  10564  modqexp  10570  nn0ltexp2  10612  faccl  10637  facdiv  10640  facwordi  10642  faclbnd  10643  faclbnd6  10646  facubnd  10647  bccl  10669  cjexp  10821  absexp  11007  binom  11411  bcxmas  11416  fprodfac  11542  demoivreALT  11700  odd2np1lem  11794  alginv  11958  prmfac1  12061  pcfac  12257  ennnfonelemhf1o  12283  expcncf  13133