Theorem nn0ind 11926

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 11842	. 2 ⊢ (𝐴 ∈ ℕ0 ↔ (𝐴 ∈ ℤ ∧ 0 ≤ 𝐴))
2		0z 11840	. . 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 11842	. . . . . 6 ⊢ (𝑦 ∈ ℕ0 ↔ (𝑦 ∈ ℤ ∧ 0 ≤ 𝑦))
10		nn0ind.6	. . . . . 6 ⊢ (𝑦 ∈ ℕ0 → (𝜒 → 𝜃))
11	9, 10	sylbir 236	. . . . 5 ⊢ ((𝑦 ∈ ℤ ∧ 0 ≤ 𝑦) → (𝜒 → 𝜃))
12	11	3adant1 1123	. . . 4 ⊢ ((0 ∈ ℤ ∧ 𝑦 ∈ ℤ ∧ 0 ≤ 𝑦) → (𝜒 → 𝜃))
13	3, 4, 5, 6, 8, 12	uzind 11923	. . 3 ⊢ ((0 ∈ ℤ ∧ 𝐴 ∈ ℤ ∧ 0 ≤ 𝐴) → 𝜏)
14	2, 13	mp3an1 1440	. 2 ⊢ ((𝐴 ∈ ℤ ∧ 0 ≤ 𝐴) → 𝜏)
15	1, 14	sylbi 218	1 ⊢ (𝐴 ∈ ℕ0 → 𝜏)

Syntax hints:   → wi 4   ↔ wb 207   ∧ wa 396   = wceq 1522   ∈ wcel 2081   class class class wbr 4962  (class class class)co 7016  0cc0 10383  1c1 10384   + caddc 10386   ≤ cle 10522  ℕ₀cn0 11745  ℤcz 11829

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1777  ax-4 1791  ax-5 1888  ax-6 1947  ax-7 1992  ax-8 2083  ax-9 2091  ax-10 2112  ax-11 2126  ax-12 2141  ax-13 2344  ax-ext 2769  ax-sep 5094  ax-nul 5101  ax-pow 5157  ax-pr 5221  ax-un 7319  ax-resscn 10440  ax-1cn 10441  ax-icn 10442  ax-addcl 10443  ax-addrcl 10444  ax-mulcl 10445  ax-mulrcl 10446  ax-mulcom 10447  ax-addass 10448  ax-mulass 10449  ax-distr 10450  ax-i2m1 10451  ax-1ne0 10452  ax-1rid 10453  ax-rnegex 10454  ax-rrecex 10455  ax-cnre 10456  ax-pre-lttri 10457  ax-pre-lttrn 10458  ax-pre-ltadd 10459  ax-pre-mulgt0 10460

This theorem depends on definitions:  df-bi 208  df-an 397  df-or 843  df-3or 1081  df-3an 1082  df-tru 1525  df-ex 1762  df-nf 1766  df-sb 2043  df-mo 2576  df-eu 2612  df-clab 2776  df-cleq 2788  df-clel 2863  df-nfc 2935  df-ne 2985  df-nel 3091  df-ral 3110  df-rex 3111  df-reu 3112  df-rab 3114  df-v 3439  df-sbc 3707  df-csb 3812  df-dif 3862  df-un 3864  df-in 3866  df-ss 3874  df-pss 3876  df-nul 4212  df-if 4382  df-pw 4455  df-sn 4473  df-pr 4475  df-tp 4477  df-op 4479  df-uni 4746  df-iun 4827  df-br 4963  df-opab 5025  df-mpt 5042  df-tr 5064  df-id 5348  df-eprel 5353  df-po 5362  df-so 5363  df-fr 5402  df-we 5404  df-xp 5449  df-rel 5450  df-cnv 5451  df-co 5452  df-dm 5453  df-rn 5454  df-res 5455  df-ima 5456  df-pred 6023  df-ord 6069  df-on 6070  df-lim 6071  df-suc 6072  df-iota 6189  df-fun 6227  df-fn 6228  df-f 6229  df-f1 6230  df-fo 6231  df-f1o 6232  df-fv 6233  df-riota 6977  df-ov 7019  df-oprab 7020  df-mpo 7021  df-om 7437  df-wrecs 7798  df-recs 7860  df-rdg 7898  df-er 8139  df-en 8358  df-dom 8359  df-sdom 8360  df-pnf 10523  df-mnf 10524  df-xr 10525  df-ltxr 10526  df-le 10527  df-sub 10719  df-neg 10720  df-nn 11487  df-n0 11746  df-z 11830

This theorem is referenced by:  nn0indALT  11927  nn0indd  11928  zindd  11932  fzennn  13186  mulexp  13318  expadd  13321  expmul  13324  leexp1a  13389  bernneq  13440  modexp  13449  faccl  13493  facdiv  13497  facwordi  13499  faclbnd  13500  facubnd  13510  bccl  13532  brfi1indALT  13704  wrdind  13920  wrd2ind  13921  cshweqrep  14019  rtrclreclem4  14254  relexpindlem  14256  iseraltlem2  14873  binom  15018  climcndslem1  15037  binomfallfac  15228  demoivreALT  15387  ruclem8  15423  odd2np1lem  15522  bitsinv1  15624  sadcadd  15640  sadadd2  15642  saddisjlem  15646  smu01lem  15667  smumullem  15674  alginv  15748  prmfac1  15892  pcfac  16064  ramcl  16194  mhmmulg  18022  psgnunilem3  18355  sylow1lem1  18453  efgsrel  18587  efgsfo  18592  efgred  18601  srgmulgass  18971  srgpcomp  18972  srgbinom  18985  lmodvsmmulgdi  19359  assamulgscm  19818  mplcoe3  19934  cnfldexp  20260  expcn  23163  dvnadd  24209  dvnres  24211  dvnfre  24232  ply1divex  24413  fta1g  24444  plyco  24514  dgrco  24548  dvnply2  24559  plydivex  24569  fta1  24580  cxpmul2  24953  facgam  25325  dchrisumlem1  25747  qabvle  25883  qabvexp  25884  ostth2lem2  25892  rusgrnumwwlk  27441  eupth2  27706  ex-ind-dvds  27932  wrdt2ind  30306  subfacval2  32042  cvmliftlem7  32146  bccolsum  32579  faclim  32586  faclim2  32588  heiborlem4  34624  mzpexpmpt  38827  pell14qrexpclnn0  38948  rmxypos  39029  jm2.17a  39042  jm2.17b  39043  rmygeid  39046  jm2.19lem3  39073  hbtlem5  39213  cnsrexpcl  39250  relexpiidm  39534  fperiodmullem  41111  stoweidlem17  41844  stoweidlem19  41846  wallispilem3  41894  fmtnorec2  43187  lmodvsmdi  43910