![]() |
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 11582 | . 2 ⊢ (𝐴 ∈ ℕ0 ↔ (𝐴 ∈ ℤ ∧ 0 ≤ 𝐴)) | |
2 | 0z 11580 | . . 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 11582 | . . . . . 6 ⊢ (𝑦 ∈ ℕ0 ↔ (𝑦 ∈ ℤ ∧ 0 ≤ 𝑦)) | |
10 | nn0ind.6 | . . . . . 6 ⊢ (𝑦 ∈ ℕ0 → (𝜒 → 𝜃)) | |
11 | 9, 10 | sylbir 225 | . . . . 5 ⊢ ((𝑦 ∈ ℤ ∧ 0 ≤ 𝑦) → (𝜒 → 𝜃)) |
12 | 11 | 3adant1 1125 | . . . 4 ⊢ ((0 ∈ ℤ ∧ 𝑦 ∈ ℤ ∧ 0 ≤ 𝑦) → (𝜒 → 𝜃)) |
13 | 3, 4, 5, 6, 8, 12 | uzind 11661 | . . 3 ⊢ ((0 ∈ ℤ ∧ 𝐴 ∈ ℤ ∧ 0 ≤ 𝐴) → 𝜏) |
14 | 2, 13 | mp3an1 1560 | . 2 ⊢ ((𝐴 ∈ ℤ ∧ 0 ≤ 𝐴) → 𝜏) |
15 | 1, 14 | sylbi 207 | 1 ⊢ (𝐴 ∈ ℕ0 → 𝜏) |
Colors of variables: wff setvar class |
Syntax hints: → wi 4 ↔ wb 196 ∧ wa 383 = wceq 1632 ∈ wcel 2139 class class class wbr 4804 (class class class)co 6813 0cc0 10128 1c1 10129 + caddc 10131 ≤ cle 10267 ℕ0cn0 11484 ℤcz 11569 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1871 ax-4 1886 ax-5 1988 ax-6 2054 ax-7 2090 ax-8 2141 ax-9 2148 ax-10 2168 ax-11 2183 ax-12 2196 ax-13 2391 ax-ext 2740 ax-sep 4933 ax-nul 4941 ax-pow 4992 ax-pr 5055 ax-un 7114 ax-resscn 10185 ax-1cn 10186 ax-icn 10187 ax-addcl 10188 ax-addrcl 10189 ax-mulcl 10190 ax-mulrcl 10191 ax-mulcom 10192 ax-addass 10193 ax-mulass 10194 ax-distr 10195 ax-i2m1 10196 ax-1ne0 10197 ax-1rid 10198 ax-rnegex 10199 ax-rrecex 10200 ax-cnre 10201 ax-pre-lttri 10202 ax-pre-lttrn 10203 ax-pre-ltadd 10204 ax-pre-mulgt0 10205 |
This theorem depends on definitions: df-bi 197 df-or 384 df-an 385 df-3or 1073 df-3an 1074 df-tru 1635 df-ex 1854 df-nf 1859 df-sb 2047 df-eu 2611 df-mo 2612 df-clab 2747 df-cleq 2753 df-clel 2756 df-nfc 2891 df-ne 2933 df-nel 3036 df-ral 3055 df-rex 3056 df-reu 3057 df-rab 3059 df-v 3342 df-sbc 3577 df-csb 3675 df-dif 3718 df-un 3720 df-in 3722 df-ss 3729 df-pss 3731 df-nul 4059 df-if 4231 df-pw 4304 df-sn 4322 df-pr 4324 df-tp 4326 df-op 4328 df-uni 4589 df-iun 4674 df-br 4805 df-opab 4865 df-mpt 4882 df-tr 4905 df-id 5174 df-eprel 5179 df-po 5187 df-so 5188 df-fr 5225 df-we 5227 df-xp 5272 df-rel 5273 df-cnv 5274 df-co 5275 df-dm 5276 df-rn 5277 df-res 5278 df-ima 5279 df-pred 5841 df-ord 5887 df-on 5888 df-lim 5889 df-suc 5890 df-iota 6012 df-fun 6051 df-fn 6052 df-f 6053 df-f1 6054 df-fo 6055 df-f1o 6056 df-fv 6057 df-riota 6774 df-ov 6816 df-oprab 6817 df-mpt2 6818 df-om 7231 df-wrecs 7576 df-recs 7637 df-rdg 7675 df-er 7911 df-en 8122 df-dom 8123 df-sdom 8124 df-pnf 10268 df-mnf 10269 df-xr 10270 df-ltxr 10271 df-le 10272 df-sub 10460 df-neg 10461 df-nn 11213 df-n0 11485 df-z 11570 |
This theorem is referenced by: nn0indALT 11665 nn0indd 11666 zindd 11670 fzennn 12961 mulexp 13093 expadd 13096 expmul 13099 leexp1a 13113 bernneq 13184 modexp 13193 faccl 13264 facdiv 13268 facwordi 13270 faclbnd 13271 faclbnd6 13280 facubnd 13281 bccl 13303 brfi1indALT 13474 wrdind 13676 wrd2ind 13677 cshweqrep 13767 rtrclreclem4 14000 relexpindlem 14002 cjexp 14089 absexp 14243 iseraltlem2 14612 binom 14761 bcxmas 14766 climcndslem1 14780 binomfallfac 14971 demoivreALT 15130 ruclem8 15165 odd2np1lem 15266 bitsinv1 15366 sadcadd 15382 sadadd2 15384 saddisjlem 15388 smu01lem 15409 smumullem 15416 alginv 15490 prmfac1 15633 pcfac 15805 ramcl 15935 mhmmulg 17784 psgnunilem3 18116 sylow1lem1 18213 efgsrel 18347 efgsfo 18352 efgred 18361 srgmulgass 18731 srgpcomp 18732 srgbinom 18745 lmodvsmmulgdi 19100 assamulgscm 19552 mplcoe3 19668 cnfldexp 19981 tmdmulg 22097 expcn 22876 dvnadd 23891 dvnres 23893 dvnfre 23914 ply1divex 24095 fta1g 24126 plyco 24196 dgrco 24230 dvnply2 24241 plydivex 24251 fta1 24262 cxpmul2 24634 facgam 24991 dchrisumlem1 25377 qabvle 25513 qabvexp 25514 ostth2lem2 25522 rusgrnumwwlk 27097 eupth2 27391 ex-ind-dvds 27629 subfacval2 31476 cvmliftlem7 31580 bccolsum 31932 faclim 31939 faclim2 31941 heiborlem4 33926 mzpexpmpt 37810 pell14qrexpclnn0 37932 rmxypos 38016 jm2.17a 38029 jm2.17b 38030 rmygeid 38033 jm2.19lem3 38060 hbtlem5 38200 cnsrexpcl 38237 relexpiidm 38498 fperiodmullem 40016 stoweidlem17 40737 stoweidlem19 40739 wallispilem3 40787 fmtnorec2 41965 lmodvsmdi 42673 |
Copyright terms: Public domain | W3C validator |