MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  nnind Structured version   Unicode version

Theorem nnind 10343
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 10347 for an example of its use. See nn0ind 10741 for induction on nonnegative integers and uzind 10736, uzind4 10915 for induction on an arbitrary upper set of integers. See indstr 10926 for strong induction. See also nnindALT 10344. 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
StepHypRef Expression
1 1nn 10336 . . . . . 6  |-  1  e.  NN
2 nnind.5 . . . . . 6  |-  ps
3 nnind.1 . . . . . . 7  |-  ( x  =  1  ->  ( ph 
<->  ps ) )
43elrab 3120 . . . . . 6  |-  ( 1  e.  { x  e.  NN  |  ph }  <->  ( 1  e.  NN  /\  ps ) )
51, 2, 4mpbir2an 911 . . . . 5  |-  1  e.  { x  e.  NN  |  ph }
6 elrabi 3117 . . . . . . 7  |-  ( y  e.  { x  e.  NN  |  ph }  ->  y  e.  NN )
7 peano2nn 10337 . . . . . . . . . 10  |-  ( y  e.  NN  ->  (
y  +  1 )  e.  NN )
87a1d 25 . . . . . . . . 9  |-  ( y  e.  NN  ->  (
y  e.  NN  ->  ( y  +  1 )  e.  NN ) )
9 nnind.6 . . . . . . . . 9  |-  ( y  e.  NN  ->  ( ch  ->  th ) )
108, 9anim12d 563 . . . . . . . 8  |-  ( y  e.  NN  ->  (
( y  e.  NN  /\ 
ch )  ->  (
( y  +  1 )  e.  NN  /\  th ) ) )
11 nnind.2 . . . . . . . . 9  |-  ( x  =  y  ->  ( ph 
<->  ch ) )
1211elrab 3120 . . . . . . . 8  |-  ( y  e.  { x  e.  NN  |  ph }  <->  ( y  e.  NN  /\  ch ) )
13 nnind.3 . . . . . . . . 9  |-  ( x  =  ( y  +  1 )  ->  ( ph 
<->  th ) )
1413elrab 3120 . . . . . . . 8  |-  ( ( y  +  1 )  e.  { x  e.  NN  |  ph }  <->  ( ( y  +  1 )  e.  NN  /\  th ) )
1510, 12, 143imtr4g 270 . . . . . . 7  |-  ( y  e.  NN  ->  (
y  e.  { x  e.  NN  |  ph }  ->  ( y  +  1 )  e.  { x  e.  NN  |  ph }
) )
166, 15mpcom 36 . . . . . 6  |-  ( y  e.  { x  e.  NN  |  ph }  ->  ( y  +  1 )  e.  { x  e.  NN  |  ph }
)
1716rgen 2784 . . . . 5  |-  A. y  e.  { x  e.  NN  |  ph }  ( y  +  1 )  e. 
{ x  e.  NN  |  ph }
18 peano5nni 10328 . . . . 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 } )
195, 17, 18mp2an 672 . . . 4  |-  NN  C_  { x  e.  NN  |  ph }
2019sseli 3355 . . 3  |-  ( A  e.  NN  ->  A  e.  { x  e.  NN  |  ph } )
21 nnind.4 . . . 4  |-  ( x  =  A  ->  ( ph 
<->  ta ) )
2221elrab 3120 . . 3  |-  ( A  e.  { x  e.  NN  |  ph }  <->  ( A  e.  NN  /\  ta ) )
2320, 22sylib 196 . 2  |-  ( A  e.  NN  ->  ( A  e.  NN  /\  ta ) )
2423simprd 463 1  |-  ( A  e.  NN  ->  ta )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    <-> wb 184    /\ wa 369    = wceq 1369    e. wcel 1756   A.wral 2718   {crab 2722    C_ wss 3331  (class class class)co 6094   1c1 9286    + caddc 9288   NNcn 10325
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1591  ax-4 1602  ax-5 1670  ax-6 1708  ax-7 1728  ax-8 1758  ax-9 1760  ax-10 1775  ax-11 1780  ax-12 1792  ax-13 1943  ax-ext 2423  ax-sep 4416  ax-nul 4424  ax-pow 4473  ax-pr 4534  ax-un 6375  ax-1cn 9343
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 966  df-3an 967  df-tru 1372  df-ex 1587  df-nf 1590  df-sb 1701  df-eu 2257  df-mo 2258  df-clab 2430  df-cleq 2436  df-clel 2439  df-nfc 2571  df-ne 2611  df-ral 2723  df-rex 2724  df-reu 2725  df-rab 2727  df-v 2977  df-sbc 3190  df-csb 3292  df-dif 3334  df-un 3336  df-in 3338  df-ss 3345  df-pss 3347  df-nul 3641  df-if 3795  df-pw 3865  df-sn 3881  df-pr 3883  df-tp 3885  df-op 3887  df-uni 4095  df-iun 4176  df-br 4296  df-opab 4354  df-mpt 4355  df-tr 4389  df-eprel 4635  df-id 4639  df-po 4644  df-so 4645  df-fr 4682  df-we 4684  df-ord 4725  df-on 4726  df-lim 4727  df-suc 4728  df-xp 4849  df-rel 4850  df-cnv 4851  df-co 4852  df-dm 4853  df-rn 4854  df-res 4855  df-ima 4856  df-iota 5384  df-fun 5423  df-fn 5424  df-f 5425  df-f1 5426  df-fo 5427  df-f1o 5428  df-fv 5429  df-ov 6097  df-om 6480  df-recs 6835  df-rdg 6869  df-nn 10326
This theorem is referenced by:  nnindALT  10344  nn1m1nn  10345  nnaddcl  10347  nnmulcl  10348  nnge1  10351  nnsub  10363  nneo  10728  peano5uzi  10733  uzindOLD  10739  nn0ind-raph  10745  ser1const  11865  expcllem  11879  expeq0  11897  seqcoll  12219  climcndslem2  13316  sqr2irr  13534  gcdmultiple  13737  rplpwr  13743  prmind2  13777  prmdvdsexp  13803  eulerthlem2  13860  pcmpt  13957  prmpwdvds  13968  vdwlem10  14054  mulgnnass  15658  imasdsf1olem  19951  ovolunlem1a  20982  ovolicc2lem3  21005  voliunlem1  21034  volsup  21040  dvexp  21430  plyco  21712  dgrcolem1  21743  vieta1  21781  emcllem6  22397  bposlem5  22630  2sqlem10  22716  dchrisum0flb  22762  iuninc  25914  ofldchr  26285  nexple  26451  esumfzf  26521  rrvsum  26840  subfacp1lem6  27076  cvmliftlem10  27186  faclimlem1  27552  incsequz  28647  bfplem1  28724  2nn0ind  29289  expmordi  29291  fmuldfeq  29767  stoweidlem20  29818  wallispilem4  29866  wallispi2lem1  29869  wallispi2lem2  29870
  Copyright terms: Public domain W3C validator