![]() |
Metamath Proof Explorer |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > MPE Home > Th. List > nn0ind | Structured version Visualization version GIF version |
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.) |
Ref | Expression |
---|---|
nn0ind.1 | ⊢ (𝑥 = 0 → (𝜑 ↔ 𝜓)) |
nn0ind.2 | ⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜒)) |
nn0ind.3 | ⊢ (𝑥 = (𝑦 + 1) → (𝜑 ↔ 𝜃)) |
nn0ind.4 | ⊢ (𝑥 = 𝐴 → (𝜑 ↔ 𝜏)) |
nn0ind.5 | ⊢ 𝜓 |
nn0ind.6 | ⊢ (𝑦 ∈ ℕ0 → (𝜒 → 𝜃)) |
Ref | Expression |
---|---|
nn0ind | ⊢ (𝐴 ∈ ℕ0 → 𝜏) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | elnn0z 12568 | . 2 ⊢ (𝐴 ∈ ℕ0 ↔ (𝐴 ∈ ℤ ∧ 0 ≤ 𝐴)) | |
2 | 0z 12566 | . . 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 12568 | . . . . . 6 ⊢ (𝑦 ∈ ℕ0 ↔ (𝑦 ∈ ℤ ∧ 0 ≤ 𝑦)) | |
10 | nn0ind.6 | . . . . . 6 ⊢ (𝑦 ∈ ℕ0 → (𝜒 → 𝜃)) | |
11 | 9, 10 | sylbir 234 | . . . . 5 ⊢ ((𝑦 ∈ ℤ ∧ 0 ≤ 𝑦) → (𝜒 → 𝜃)) |
12 | 11 | 3adant1 1131 | . . . 4 ⊢ ((0 ∈ ℤ ∧ 𝑦 ∈ ℤ ∧ 0 ≤ 𝑦) → (𝜒 → 𝜃)) |
13 | 3, 4, 5, 6, 8, 12 | uzind 12651 | . . 3 ⊢ ((0 ∈ ℤ ∧ 𝐴 ∈ ℤ ∧ 0 ≤ 𝐴) → 𝜏) |
14 | 2, 13 | mp3an1 1449 | . 2 ⊢ ((𝐴 ∈ ℤ ∧ 0 ≤ 𝐴) → 𝜏) |
15 | 1, 14 | sylbi 216 | 1 ⊢ (𝐴 ∈ ℕ0 → 𝜏) |
Colors of variables: wff setvar class |
Syntax hints: → wi 4 ↔ wb 205 ∧ wa 397 = wceq 1542 ∈ wcel 2107 class class class wbr 5148 (class class class)co 7406 0cc0 11107 1c1 11108 + caddc 11110 ≤ cle 11246 ℕ0cn0 12469 ℤcz 12555 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1798 ax-4 1812 ax-5 1914 ax-6 1972 ax-7 2012 ax-8 2109 ax-9 2117 ax-10 2138 ax-11 2155 ax-12 2172 ax-ext 2704 ax-sep 5299 ax-nul 5306 ax-pow 5363 ax-pr 5427 ax-un 7722 ax-resscn 11164 ax-1cn 11165 ax-icn 11166 ax-addcl 11167 ax-addrcl 11168 ax-mulcl 11169 ax-mulrcl 11170 ax-mulcom 11171 ax-addass 11172 ax-mulass 11173 ax-distr 11174 ax-i2m1 11175 ax-1ne0 11176 ax-1rid 11177 ax-rnegex 11178 ax-rrecex 11179 ax-cnre 11180 ax-pre-lttri 11181 ax-pre-lttrn 11182 ax-pre-ltadd 11183 ax-pre-mulgt0 11184 |
This theorem depends on definitions: df-bi 206 df-an 398 df-or 847 df-3or 1089 df-3an 1090 df-tru 1545 df-fal 1555 df-ex 1783 df-nf 1787 df-sb 2069 df-mo 2535 df-eu 2564 df-clab 2711 df-cleq 2725 df-clel 2811 df-nfc 2886 df-ne 2942 df-nel 3048 df-ral 3063 df-rex 3072 df-reu 3378 df-rab 3434 df-v 3477 df-sbc 3778 df-csb 3894 df-dif 3951 df-un 3953 df-in 3955 df-ss 3965 df-pss 3967 df-nul 4323 df-if 4529 df-pw 4604 df-sn 4629 df-pr 4631 df-op 4635 df-uni 4909 df-iun 4999 df-br 5149 df-opab 5211 df-mpt 5232 df-tr 5266 df-id 5574 df-eprel 5580 df-po 5588 df-so 5589 df-fr 5631 df-we 5633 df-xp 5682 df-rel 5683 df-cnv 5684 df-co 5685 df-dm 5686 df-rn 5687 df-res 5688 df-ima 5689 df-pred 6298 df-ord 6365 df-on 6366 df-lim 6367 df-suc 6368 df-iota 6493 df-fun 6543 df-fn 6544 df-f 6545 df-f1 6546 df-fo 6547 df-f1o 6548 df-fv 6549 df-riota 7362 df-ov 7409 df-oprab 7410 df-mpo 7411 df-om 7853 df-2nd 7973 df-frecs 8263 df-wrecs 8294 df-recs 8368 df-rdg 8407 df-er 8700 df-en 8937 df-dom 8938 df-sdom 8939 df-pnf 11247 df-mnf 11248 df-xr 11249 df-ltxr 11250 df-le 11251 df-sub 11443 df-neg 11444 df-nn 12210 df-n0 12470 df-z 12556 |
This theorem is referenced by: nn0indALT 12655 nn0indd 12656 zindd 12660 fzennn 13930 mulexp 14064 expadd 14067 expmul 14070 leexp1a 14137 bernneq 14189 modexp 14198 faccl 14240 facdiv 14244 facwordi 14246 faclbnd 14247 facubnd 14257 bccl 14279 brfi1indALT 14458 wrdind 14669 wrd2ind 14670 cshweqrep 14768 rtrclreclem4 15005 relexpindlem 15007 iseraltlem2 15626 binom 15773 climcndslem1 15792 binomfallfac 15982 demoivreALT 16141 ruclem8 16177 odd2np1lem 16280 bitsinv1 16380 sadcadd 16396 sadadd2 16398 saddisjlem 16402 smu01lem 16423 smumullem 16430 alginv 16509 prmfac1 16655 pcfac 16829 ramcl 16959 mhmmulg 18990 psgnunilem3 19359 sylow1lem1 19461 efgsrel 19597 efgsfo 19602 efgred 19611 srgmulgass 20034 srgpcomp 20035 srgbinom 20048 lmodvsmmulgdi 20500 cnfldexp 20971 assamulgscm 21447 mplcoe3 21585 expcn 24380 dvnadd 25438 dvnres 25440 dvnfre 25461 ply1divex 25646 fta1g 25677 plyco 25747 dgrco 25781 dvnply2 25792 plydivex 25802 fta1 25813 cxpmul2 26189 facgam 26560 dchrisumlem1 26982 qabvle 27118 qabvexp 27119 ostth2lem2 27127 rusgrnumwwlk 29219 eupth2 29482 ex-ind-dvds 29704 wrdt2ind 32105 subfacval2 34167 cvmliftlem7 34271 bccolsum 34698 faclim 34705 faclim2 34707 gg-expcn 35153 heiborlem4 36671 sumcubes 41207 mzpexpmpt 41469 pell14qrexpclnn0 41590 rmxypos 41672 jm2.17a 41685 jm2.17b 41686 rmygeid 41689 jm2.19lem3 41716 hbtlem5 41856 cnsrexpcl 41893 relexpiidm 42441 fperiodmullem 44000 stoweidlem17 44720 stoweidlem19 44722 wallispilem3 44770 fmtnorec2 46198 lmodvsmdi 47012 itcovalt2 47317 ackendofnn0 47324 |
Copyright terms: Public domain | W3C validator |