Theorem nnind 8864

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 8868 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 8859	. . . . . 6 |- 1 e. NN
2		nnind.5	. . . . . 6 |- ps
3		nnind.1	. . . . . . 7 |- ( x = 1 -> ( ph <-> ps ) )
4	3	elrab 2877	. . . . . 6 |- ( 1 e. { x e. NN | ph } <-> ( 1 e. NN /\ ps ) )
5	1, 2, 4	mpbir2an 931	. . . . 5 |- 1 e. { x e. NN | ph }
6		elrabi 2874	. . . . . . 7 |- ( y e. { x e. NN | ph } -> y e. NN )
7		peano2nn 8860	. . . . . . . . . 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 2877	. . . . . . . 8 |- ( y e. { x e. NN | ph } <-> ( y e. NN /\ ch ) )
13		nnind.3	. . . . . . . . 9 |- ( x = ( y + 1 ) -> ( ph <-> th ) )
14	13	elrab 2877	. . . . . . . 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 2517	. . . . 5 |- A. y e. { x e. NN | ph } ( y + 1 ) e. { x e. NN | ph }
18		peano5nni 8851	. . . . 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 423	. . . 4 |- NN C_ { x e. NN | ph }
20	19	sseli 3133	. . 3 |- ( A e. NN -> A e. { x e. NN | ph } )
21		nnind.4	. . . 4 |- ( x = A -> ( ph <-> ta ) )
22	21	elrab 2877	. . 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 1342   e. wcel 2135   A.wral 2442   {crab 2446   C_ wss 3111  (class class class)co 5836   1c1 7745   + caddc 7747   NNcn 8848

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 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-ext 2146  ax-sep 4094  ax-cnex 7835  ax-resscn 7836  ax-1re 7838  ax-addrcl 7841

This theorem depends on definitions:  df-bi 116  df-3an 969  df-tru 1345  df-nf 1448  df-sb 1750  df-clab 2151  df-cleq 2157  df-clel 2160  df-nfc 2295  df-ral 2447  df-rex 2448  df-rab 2451  df-v 2723  df-un 3115  df-in 3117  df-ss 3124  df-sn 3576  df-pr 3577  df-op 3579  df-uni 3784  df-int 3819  df-br 3977  df-iota 5147  df-fv 5190  df-ov 5839  df-inn 8849

This theorem is referenced by:  nnindALT  8865  nn1m1nn  8866  nnaddcl  8868  nnmulcl  8869  nnge1  8871  nn1gt1  8882  nnsub  8887  zaddcllempos  9219  zaddcllemneg  9221  nneoor  9284  peano5uzti  9290  nn0ind-raph  9299  indstr  9522  exbtwnzlemshrink  10174  exp3vallem  10446  expcllem  10456  expap0  10475  apexp1  10620  seq3coll  10741  resqrexlemover  10938  resqrexlemlo  10941  resqrexlemcalc3  10944  gcdmultiple  11938  rplpwr  11945  prmind2  12031  prmdvdsexp  12057  sqrt2irr  12071  pw2dvdslemn  12074  pcmpt  12250  dvexp  13216