Theorem nn0ind 11304

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	⊢ (𝑥 = 0 → (𝜑 ↔ 𝜓))
nn0ind.2	⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜒))
nn0ind.3	⊢ (𝑥 = (𝑦 + 1) → (𝜑 ↔ 𝜃))
nn0ind.4	⊢ (𝑥 = 𝐴 → (𝜑 ↔ 𝜏))
nn0ind.5	⊢ 𝜓
nn0ind.6	⊢ (𝑦 ∈ ℕ0 → (𝜒 → 𝜃))

Assertion

Ref	Expression
nn0ind	⊢ (𝐴 ∈ ℕ0 → 𝜏)

Distinct variable groups:   𝑥,𝑦   𝑥,𝐴   𝜓,𝑥   𝜒,𝑥   𝜃,𝑥   𝜏,𝑥   𝜑,𝑦

Allowed substitution hints:   𝜑(𝑥)   𝜓(𝑦)   𝜒(𝑦)   𝜃(𝑦)   𝜏(𝑦)   𝐴(𝑦)

Proof of Theorem nn0ind

Step	Hyp	Ref	Expression
1		elnn0z 11223	. 2 ⊢ (𝐴 ∈ ℕ0 ↔ (𝐴 ∈ ℤ ∧ 0 ≤ 𝐴))
2		0z 11221	. . 3 ⊢ 0 ∈ ℤ
3		nn0ind.1	. . . 4 ⊢ (𝑥 = 0 → (𝜑 ↔ 𝜓))
4		nn0ind.2	. . . 4 ⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜒))
5		nn0ind.3	. . . 4 ⊢ (𝑥 = (𝑦 + 1) → (𝜑 ↔ 𝜃))
6		nn0ind.4	. . . 4 ⊢ (𝑥 = 𝐴 → (𝜑 ↔ 𝜏))
7		nn0ind.5	. . . . 5 ⊢ 𝜓
8	7	a1i 11	. . . 4 ⊢ (0 ∈ ℤ → 𝜓)
9		elnn0z 11223	. . . . . 6 ⊢ (𝑦 ∈ ℕ0 ↔ (𝑦 ∈ ℤ ∧ 0 ≤ 𝑦))
10		nn0ind.6	. . . . . 6 ⊢ (𝑦 ∈ ℕ0 → (𝜒 → 𝜃))
11	9, 10	sylbir 223	. . . . 5 ⊢ ((𝑦 ∈ ℤ ∧ 0 ≤ 𝑦) → (𝜒 → 𝜃))
12	11	3adant1 1071	. . . 4 ⊢ ((0 ∈ ℤ ∧ 𝑦 ∈ ℤ ∧ 0 ≤ 𝑦) → (𝜒 → 𝜃))
13	3, 4, 5, 6, 8, 12	uzind 11301	. . 3 ⊢ ((0 ∈ ℤ ∧ 𝐴 ∈ ℤ ∧ 0 ≤ 𝐴) → 𝜏)
14	2, 13	mp3an1 1402	. 2 ⊢ ((𝐴 ∈ ℤ ∧ 0 ≤ 𝐴) → 𝜏)
15	1, 14	sylbi 205	1 ⊢ (𝐴 ∈ ℕ0 → 𝜏)

Syntax hints:   → wi 4   ↔ wb 194   ∧ wa 382   = wceq 1474   ∈ wcel 1976   class class class wbr 4577  (class class class)co 6527  0cc0 9792  1c1 9793   + caddc 9795   ≤ cle 9931  ℕ₀cn0 11139  ℤcz 11210

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1712  ax-4 1727  ax-5 1826  ax-6 1874  ax-7 1921  ax-8 1978  ax-9 1985  ax-10 2005  ax-11 2020  ax-12 2033  ax-13 2233  ax-ext 2589  ax-sep 4703  ax-nul 4712  ax-pow 4764  ax-pr 4828  ax-un 6824  ax-resscn 9849  ax-1cn 9850  ax-icn 9851  ax-addcl 9852  ax-addrcl 9853  ax-mulcl 9854  ax-mulrcl 9855  ax-mulcom 9856  ax-addass 9857  ax-mulass 9858  ax-distr 9859  ax-i2m1 9860  ax-1ne0 9861  ax-1rid 9862  ax-rnegex 9863  ax-rrecex 9864  ax-cnre 9865  ax-pre-lttri 9866  ax-pre-lttrn 9867  ax-pre-ltadd 9868  ax-pre-mulgt0 9869

This theorem depends on definitions:  df-bi 195  df-or 383  df-an 384  df-3or 1031  df-3an 1032  df-tru 1477  df-ex 1695  df-nf 1700  df-sb 1867  df-eu 2461  df-mo 2462  df-clab 2596  df-cleq 2602  df-clel 2605  df-nfc 2739  df-ne 2781  df-nel 2782  df-ral 2900  df-rex 2901  df-reu 2902  df-rab 2904  df-v 3174  df-sbc 3402  df-csb 3499  df-dif 3542  df-un 3544  df-in 3546  df-ss 3553  df-pss 3555  df-nul 3874  df-if 4036  df-pw 4109  df-sn 4125  df-pr 4127  df-tp 4129  df-op 4131  df-uni 4367  df-iun 4451  df-br 4578  df-opab 4638  df-mpt 4639  df-tr 4675  df-eprel 4939  df-id 4943  df-po 4949  df-so 4950  df-fr 4987  df-we 4989  df-xp 5034  df-rel 5035  df-cnv 5036  df-co 5037  df-dm 5038  df-rn 5039  df-res 5040  df-ima 5041  df-pred 5583  df-ord 5629  df-on 5630  df-lim 5631  df-suc 5632  df-iota 5754  df-fun 5792  df-fn 5793  df-f 5794  df-f1 5795  df-fo 5796  df-f1o 5797  df-fv 5798  df-riota 6489  df-ov 6530  df-oprab 6531  df-mpt2 6532  df-om 6935  df-wrecs 7271  df-recs 7332  df-rdg 7370  df-er 7606  df-en 7819  df-dom 7820  df-sdom 7821  df-pnf 9932  df-mnf 9933  df-xr 9934  df-ltxr 9935  df-le 9936  df-sub 10119  df-neg 10120  df-nn 10868  df-n0 11140  df-z 11211

This theorem is referenced by:  nn0indALT  11305  nn0indd  11306  zindd  11310  fzennn  12584  mulexp  12716  expadd  12719  expmul  12722  leexp1a  12736  bernneq  12807  modexp  12816  faccl  12887  facdiv  12891  facwordi  12893  faclbnd  12894  faclbnd6  12903  facubnd  12904  bccl  12926  brfi1indALT  13083  brfi1indALTOLD  13089  wrdind  13274  wrd2ind  13275  cshweqrep  13364  rtrclreclem4  13595  relexpindlem  13597  cjexp  13684  absexp  13838  iseraltlem2  14207  binom  14347  bcxmas  14352  climcndslem1  14366  binomfallfac  14557  demoivreALT  14716  ruclem8  14751  odd2np1lem  14848  bitsinv1  14948  sadcadd  14964  sadadd2  14966  saddisjlem  14970  smu01lem  14991  smumullem  14998  alginv  15072  prmfac1  15215  pcfac  15387  ramcl  15517  mhmmulg  17352  psgnunilem3  17685  sylow1lem1  17782  efgsrel  17916  efgsfo  17921  efgred  17930  srgmulgass  18300  srgpcomp  18301  srgbinom  18314  lmodvsmmulgdi  18667  assamulgscm  19117  mplcoe3  19233  cnfldexp  19544  tmdmulg  21648  expcn  22414  dvnadd  23415  dvnres  23417  dvnfre  23438  ply1divex  23617  fta1g  23648  plyco  23718  dgrco  23752  dvnply2  23763  plydivex  23773  fta1  23784  cxpmul2  24152  facgam  24509  dchrisumlem1  24895  qabvle  25031  qabvexp  25032  ostth2lem2  25040  rusgranumwlk  26250  eupath2  26273  ex-ind-dvds  26476  subfacval2  30229  cvmliftlem7  30333  bccolsum  30684  faclim  30691  faclim2  30693  heiborlem4  32579  mzpexpmpt  36122  pell14qrexpclnn0  36244  rmxypos  36328  jm2.17a  36341  jm2.17b  36342  rmygeid  36345  jm2.19lem3  36372  hbtlem5  36513  cnsrexpcl  36550  relexpiidm  36811  fperiodmullem  38254  stoweidlem17  38707  stoweidlem19  38709  wallispilem3  38757  fmtnorec2  39791  rusgrnumwwlk  41173  eupth2  41402  lmodvsmdi  41952