Theorem nnind 9023

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 9027 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 9018	. . . . . 6 |- 1 e. NN
2		nnind.5	. . . . . 6 |- ps
3		nnind.1	. . . . . . 7 |- ( x = 1 -> ( ph <-> ps ) )
4	3	elrab 2920	. . . . . 6 |- ( 1 e. { x e. NN | ph } <-> ( 1 e. NN /\ ps ) )
5	1, 2, 4	mpbir2an 944	. . . . 5 |- 1 e. { x e. NN | ph }
6		elrabi 2917	. . . . . . 7 |- ( y e. { x e. NN | ph } -> y e. NN )
7		peano2nn 9019	. . . . . . . . . 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 335	. . . . . . . 8 |- ( y e. NN -> ( ( y e. NN /\ ch ) -> ( ( y + 1 ) e. NN /\ th ) ) )
11		nnind.2	. . . . . . . . 9 |- ( x = y -> ( ph <-> ch ) )
12	11	elrab 2920	. . . . . . . 8 |- ( y e. { x e. NN | ph } <-> ( y e. NN /\ ch ) )
13		nnind.3	. . . . . . . . 9 |- ( x = ( y + 1 ) -> ( ph <-> th ) )
14	13	elrab 2920	. . . . . . . 8 |- ( ( y + 1 ) e. { x e. NN | ph } <-> ( ( y + 1 ) e. NN /\ th ) )
15	10, 12, 14	3imtr4g 205	. . . . . . 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 2550	. . . . 5 |- A. y e. { x e. NN | ph } ( y + 1 ) e. { x e. NN | ph }
18		peano5nni 9010	. . . . 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 426	. . . 4 |- NN C_ { x e. NN | ph }
20	19	sseli 3180	. . 3 |- ( A e. NN -> A e. { x e. NN | ph } )
21		nnind.4	. . . 4 |- ( x = A -> ( ph <-> ta ) )
22	21	elrab 2920	. . 3 |- ( A e. { x e. NN | ph } <-> ( A e. NN /\ ta ) )
23	20, 22	sylib 122	. 2 |- ( A e. NN -> ( A e. NN /\ ta ) )
24	23	simprd 114	1 |- ( A e. NN -> ta )

Syntax hints:   -> wi 4   /\ wa 104   <-> wb 105   = wceq 1364   e. wcel 2167   A.wral 2475   {crab 2479   C_ wss 3157  (class class class)co 5925   1c1 7897   + caddc 7899   NNcn 9007

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-io 710  ax-5 1461  ax-7 1462  ax-gen 1463  ax-ie1 1507  ax-ie2 1508  ax-8 1518  ax-10 1519  ax-11 1520  ax-i12 1521  ax-bndl 1523  ax-4 1524  ax-17 1540  ax-i9 1544  ax-ial 1548  ax-i5r 1549  ax-ext 2178  ax-sep 4152  ax-cnex 7987  ax-resscn 7988  ax-1re 7990  ax-addrcl 7993

This theorem depends on definitions:  df-bi 117  df-3an 982  df-tru 1367  df-nf 1475  df-sb 1777  df-clab 2183  df-cleq 2189  df-clel 2192  df-nfc 2328  df-ral 2480  df-rex 2481  df-rab 2484  df-v 2765  df-un 3161  df-in 3163  df-ss 3170  df-sn 3629  df-pr 3630  df-op 3632  df-uni 3841  df-int 3876  df-br 4035  df-iota 5220  df-fv 5267  df-ov 5928  df-inn 9008

This theorem is referenced by:  nnindALT  9024  nn1m1nn  9025  nnaddcl  9027  nnmulcl  9028  nnge1  9030  nn1gt1  9041  nnsub  9046  zaddcllempos  9380  zaddcllemneg  9382  nneoor  9445  peano5uzti  9451  nn0ind-raph  9460  indstr  9684  exbtwnzlemshrink  10355  exp3vallem  10649  expcllem  10659  expap0  10678  apexp1  10827  seq3coll  10951  resqrexlemover  11192  resqrexlemlo  11195  resqrexlemcalc3  11198  gcdmultiple  12212  rplpwr  12219  prmind2  12313  prmdvdsexp  12341  sqrt2irr  12355  pw2dvdslemn  12358  pcmpt  12537  prmpwdvds  12549  mulgnnass  13363  dvexp  15031  plycolemc  15078  2sqlem10  15450