Theorem nnind 8881

Description: Principle of Mathematical Induction (inference schema). The first four hypotheses give us the substitution instances we need; the last two are the basis and the induction step. See nnaddcl 8885 for an example of its use. This is an alternative for Metamath 100 proof #74. (Contributed by NM, 10-Jan-1997.) (Revised by Mario Carneiro, 16-Jun-2013.)

Hypotheses

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

Assertion

Ref	Expression
nnind	|- ( A e. NN -> 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 nnind

Step	Hyp	Ref	Expression
1		1nn 8876	. . . . . 6 |- 1 e. NN
2		nnind.5	. . . . . 6 |- ps
3		nnind.1	. . . . . . 7 |- ( x = 1 -> ( ph <-> ps ) )
4	3	elrab 2886	. . . . . 6 |- ( 1 e. { x e. NN | ph } <-> ( 1 e. NN /\ ps ) )
5	1, 2, 4	mpbir2an 937	. . . . 5 |- 1 e. { x e. NN | ph }
6		elrabi 2883	. . . . . . 7 |- ( y e. { x e. NN | ph } -> y e. NN )
7		peano2nn 8877	. . . . . . . . . 10 |- ( y e. NN -> ( y + 1 ) e. NN )
8	7	a1d 22	. . . . . . . . 9 |- ( y e. NN -> ( y e. NN -> ( y + 1 ) e. NN ) )
9		nnind.6	. . . . . . . . 9 |- ( y e. NN -> ( ch -> th ) )
10	8, 9	anim12d 333	. . . . . . . 8 |- ( y e. NN -> ( ( y e. NN /\ ch ) -> ( ( y + 1 ) e. NN /\ th ) ) )
11		nnind.2	. . . . . . . . 9 |- ( x = y -> ( ph <-> ch ) )
12	11	elrab 2886	. . . . . . . 8 |- ( y e. { x e. NN | ph } <-> ( y e. NN /\ ch ) )
13		nnind.3	. . . . . . . . 9 |- ( x = ( y + 1 ) -> ( ph <-> th ) )
14	13	elrab 2886	. . . . . . . 8 |- ( ( y + 1 ) e. { x e. NN | ph } <-> ( ( y + 1 ) e. NN /\ th ) )
15	10, 12, 14	3imtr4g 204	. . . . . . 7 |- ( y e. NN -> ( y e. { x e. NN | ph } -> ( y + 1 ) e. { x e. NN | ph } ) )
16	6, 15	mpcom 36	. . . . . 6 |- ( y e. { x e. NN | ph } -> ( y + 1 ) e. { x e. NN | ph } )
17	16	rgen 2523	. . . . 5 |- A. y e. { x e. NN | ph } ( y + 1 ) e. { x e. NN | ph }
18		peano5nni 8868	. . . . 5 |- ( ( 1 e. { x e. NN | ph } /\ A. y e. { x e. NN | ph } ( y + 1 ) e. { x e. NN | ph } ) -> NN C_ { x e. NN | ph } )
19	5, 17, 18	mp2an 424	. . . 4 |- NN C_ { x e. NN | ph }
20	19	sseli 3143	. . 3 |- ( A e. NN -> A e. { x e. NN | ph } )
21		nnind.4	. . . 4 |- ( x = A -> ( ph <-> ta ) )
22	21	elrab 2886	. . 3 |- ( A e. { x e. NN | ph } <-> ( A e. NN /\ ta ) )
23	20, 22	sylib 121	. 2 |- ( A e. NN -> ( A e. NN /\ ta ) )
24	23	simprd 113	1 |- ( A e. NN -> ta )

Syntax hints:   -> wi 4   /\ wa 103   <-> wb 104   = wceq 1348   e. wcel 2141   A.wral 2448   {crab 2452   C_ wss 3121  (class class class)co 5850   1c1 7762   + caddc 7764   NNcn 8865

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-io 704  ax-5 1440  ax-7 1441  ax-gen 1442  ax-ie1 1486  ax-ie2 1487  ax-8 1497  ax-10 1498  ax-11 1499  ax-i12 1500  ax-bndl 1502  ax-4 1503  ax-17 1519  ax-i9 1523  ax-ial 1527  ax-i5r 1528  ax-ext 2152  ax-sep 4105  ax-cnex 7852  ax-resscn 7853  ax-1re 7855  ax-addrcl 7858

This theorem depends on definitions:  df-bi 116  df-3an 975  df-tru 1351  df-nf 1454  df-sb 1756  df-clab 2157  df-cleq 2163  df-clel 2166  df-nfc 2301  df-ral 2453  df-rex 2454  df-rab 2457  df-v 2732  df-un 3125  df-in 3127  df-ss 3134  df-sn 3587  df-pr 3588  df-op 3590  df-uni 3795  df-int 3830  df-br 3988  df-iota 5158  df-fv 5204  df-ov 5853  df-inn 8866

This theorem is referenced by:  nnindALT  8882  nn1m1nn  8883  nnaddcl  8885  nnmulcl  8886  nnge1  8888  nn1gt1  8899  nnsub  8904  zaddcllempos  9236  zaddcllemneg  9238  nneoor  9301  peano5uzti  9307  nn0ind-raph  9316  indstr  9539  exbtwnzlemshrink  10192  exp3vallem  10464  expcllem  10474  expap0  10493  apexp1  10639  seq3coll  10764  resqrexlemover  10961  resqrexlemlo  10964  resqrexlemcalc3  10967  gcdmultiple  11962  rplpwr  11969  prmind2  12061  prmdvdsexp  12089  sqrt2irr  12103  pw2dvdslemn  12106  pcmpt  12282  prmpwdvds  12294  dvexp  13428  2sqlem10  13714