Theorem nn0ind 10957

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 10877	. 2 |- ( A e. NN0 <-> ( A e. ZZ /\ 0 <_ A ) )
2		0z 10875	. . 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 11	. . . 4 |- ( 0 e. ZZ -> ps )
9		elnn0z 10877	. . . . . 6 |- ( y e. NN0 <-> ( y e. ZZ /\ 0 <_ y ) )
10		nn0ind.6	. . . . . 6 |- ( y e. NN0 -> ( ch -> th ) )
11	9, 10	sylbir 213	. . . . 5 |- ( ( y e. ZZ /\ 0 <_ y ) -> ( ch -> th ) )
12	11	3adant1 1014	. . . 4 |- ( ( 0 e. ZZ /\ y e. ZZ /\ 0 <_ y ) -> ( ch -> th ) )
13	3, 4, 5, 6, 8, 12	uzind 10952	. . 3 |- ( ( 0 e. ZZ /\ A e. ZZ /\ 0 <_ A ) -> ta )
14	2, 13	mp3an1 1311	. 2 |- ( ( A e. ZZ /\ 0 <_ A ) -> ta )
15	1, 14	sylbi 195	1 |- ( A e. NN0 -> ta )

Syntax hints:   -> wi 4   <-> wb 184   /\ wa 369   = wceq 1379   e. wcel 1767   class class class wbr 4447  (class class class)co 6284   0cc0 9492   1c1 9493   + caddc 9495   <_ cle 9629   NN0cn0 10795   ZZcz 10864

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1601  ax-4 1612  ax-5 1680  ax-6 1719  ax-7 1739  ax-8 1769  ax-9 1771  ax-10 1786  ax-11 1791  ax-12 1803  ax-13 1968  ax-ext 2445  ax-sep 4568  ax-nul 4576  ax-pow 4625  ax-pr 4686  ax-un 6576  ax-resscn 9549  ax-1cn 9550  ax-icn 9551  ax-addcl 9552  ax-addrcl 9553  ax-mulcl 9554  ax-mulrcl 9555  ax-mulcom 9556  ax-addass 9557  ax-mulass 9558  ax-distr 9559  ax-i2m1 9560  ax-1ne0 9561  ax-1rid 9562  ax-rnegex 9563  ax-rrecex 9564  ax-cnre 9565  ax-pre-lttri 9566  ax-pre-lttrn 9567  ax-pre-ltadd 9568  ax-pre-mulgt0 9569

This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 974  df-3an 975  df-tru 1382  df-ex 1597  df-nf 1600  df-sb 1712  df-eu 2279  df-mo 2280  df-clab 2453  df-cleq 2459  df-clel 2462  df-nfc 2617  df-ne 2664  df-nel 2665  df-ral 2819  df-rex 2820  df-reu 2821  df-rab 2823  df-v 3115  df-sbc 3332  df-csb 3436  df-dif 3479  df-un 3481  df-in 3483  df-ss 3490  df-pss 3492  df-nul 3786  df-if 3940  df-pw 4012  df-sn 4028  df-pr 4030  df-tp 4032  df-op 4034  df-uni 4246  df-iun 4327  df-br 4448  df-opab 4506  df-mpt 4507  df-tr 4541  df-eprel 4791  df-id 4795  df-po 4800  df-so 4801  df-fr 4838  df-we 4840  df-ord 4881  df-on 4882  df-lim 4883  df-suc 4884  df-xp 5005  df-rel 5006  df-cnv 5007  df-co 5008  df-dm 5009  df-rn 5010  df-res 5011  df-ima 5012  df-iota 5551  df-fun 5590  df-fn 5591  df-f 5592  df-f1 5593  df-fo 5594  df-f1o 5595  df-fv 5596  df-riota 6245  df-ov 6287  df-oprab 6288  df-mpt2 6289  df-om 6685  df-recs 7042  df-rdg 7076  df-er 7311  df-en 7517  df-dom 7518  df-sdom 7519  df-pnf 9630  df-mnf 9631  df-xr 9632  df-ltxr 9633  df-le 9634  df-sub 9807  df-neg 9808  df-nn 10537  df-n0 10796  df-z 10865

This theorem is referenced by:  nn0indALT  10958  zindd  10962  fzennn  12046  mulexp  12173  expadd  12176  expmul  12179  leexp1a  12192  bernneq  12260  modexp  12269  faccl  12331  facdiv  12333  facwordi  12335  faclbnd  12336  faclbnd6  12345  facubnd  12346  bccl  12368  wrdind  12665  wrd2ind  12666  cshweqrep  12752  cjexp  12946  absexp  13100  iseraltlem2  13468  binom  13605  bcxmas  13610  climcndslem1  13624  demoivreALT  13797  ruclem8  13831  odd2np1lem  13904  bitsinv1  13951  sadcadd  13967  sadadd2  13969  saddisjlem  13973  smu01lem  13994  smumullem  14001  alginv  14063  prmfac1  14118  pcfac  14277  ramcl  14406  mhmmulg  15984  psgnunilem3  16327  sylow1lem1  16424  efgsrel  16558  efgsfo  16563  efgred  16572  srgmulgass  16984  srgpcomp  16985  srgbinom  16998  lmodvsmmulgdi  17347  assamulgscm  17798  mplcoe3  17927  mplcoe3OLD  17928  cnfldexp  18250  tmdmulg  20354  expcn  21139  dvnadd  22095  dvnres  22097  dvnfre  22118  ply1divex  22300  fta1g  22331  plyco  22401  dgrco  22434  dvnply2  22445  plydivex  22455  fta1  22466  cxpmul2  22826  dchrisumlem1  23430  qabvle  23566  qabvexp  23567  ostth2lem2  23575  rusgranumwlk  24661  eupath2  24684  gxnn0add  24980  gxnn0mul  24983  nn0indd  27305  facgam  28276  subfacval2  28299  cvmliftlem7  28404  relexpsucl  28558  relexpcnv  28559  relexpdm  28561  relexprn  28562  relexpadd  28564  relexpindlem  28565  rtrclreclem.min  28573  binomfallfac  28768  faclim  28776  faclim2  28778  heiborlem4  29941  mzpexpmpt  30309  pell14qrexpclnn0  30434  rmxypos  30517  jm2.17a  30530  jm2.17b  30531  rmygeid  30534  jm2.19lem3  30565  hbtlem5  30709  cnsrexpcl  30747  fperiodmullem  31108  m1expeven  31169  stoweidlem17  31345  stoweidlem19  31347  wallispilem3  31395  lmodvsmdi  32074