![]() |
Metamath Proof Explorer |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > MPE Home > Th. List > nnind | Structured version Visualization version GIF version |
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 12217 for an example of its use. See nn0ind 12639 for induction on nonnegative integers and uzind 12636, uzind4 12872 for induction on an arbitrary upper set of integers. See indstr 12882 for strong induction. See also nnindALT 12213. This is an alternative for Metamath 100 proof #74. (Contributed by NM, 10-Jan-1997.) (Revised by Mario Carneiro, 16-Jun-2013.) |
Ref | Expression |
---|---|
nnind.1 | ⊢ (𝑥 = 1 → (𝜑 ↔ 𝜓)) |
nnind.2 | ⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜒)) |
nnind.3 | ⊢ (𝑥 = (𝑦 + 1) → (𝜑 ↔ 𝜃)) |
nnind.4 | ⊢ (𝑥 = 𝐴 → (𝜑 ↔ 𝜏)) |
nnind.5 | ⊢ 𝜓 |
nnind.6 | ⊢ (𝑦 ∈ ℕ → (𝜒 → 𝜃)) |
Ref | Expression |
---|---|
nnind | ⊢ (𝐴 ∈ ℕ → 𝜏) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | 1nn 12205 | . . . . . 6 ⊢ 1 ∈ ℕ | |
2 | nnind.5 | . . . . . 6 ⊢ 𝜓 | |
3 | nnind.1 | . . . . . . 7 ⊢ (𝑥 = 1 → (𝜑 ↔ 𝜓)) | |
4 | 3 | elrab 3679 | . . . . . 6 ⊢ (1 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ (1 ∈ ℕ ∧ 𝜓)) |
5 | 1, 2, 4 | mpbir2an 709 | . . . . 5 ⊢ 1 ∈ {𝑥 ∈ ℕ ∣ 𝜑} |
6 | elrabi 3673 | . . . . . . 7 ⊢ (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} → 𝑦 ∈ ℕ) | |
7 | peano2nn 12206 | . . . . . . . . . 10 ⊢ (𝑦 ∈ ℕ → (𝑦 + 1) ∈ ℕ) | |
8 | 7 | a1d 25 | . . . . . . . . 9 ⊢ (𝑦 ∈ ℕ → (𝑦 ∈ ℕ → (𝑦 + 1) ∈ ℕ)) |
9 | nnind.6 | . . . . . . . . 9 ⊢ (𝑦 ∈ ℕ → (𝜒 → 𝜃)) | |
10 | 8, 9 | anim12d 609 | . . . . . . . 8 ⊢ (𝑦 ∈ ℕ → ((𝑦 ∈ ℕ ∧ 𝜒) → ((𝑦 + 1) ∈ ℕ ∧ 𝜃))) |
11 | nnind.2 | . . . . . . . . 9 ⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜒)) | |
12 | 11 | elrab 3679 | . . . . . . . 8 ⊢ (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ (𝑦 ∈ ℕ ∧ 𝜒)) |
13 | nnind.3 | . . . . . . . . 9 ⊢ (𝑥 = (𝑦 + 1) → (𝜑 ↔ 𝜃)) | |
14 | 13 | elrab 3679 | . . . . . . . 8 ⊢ ((𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ ((𝑦 + 1) ∈ ℕ ∧ 𝜃)) |
15 | 10, 12, 14 | 3imtr4g 295 | . . . . . . 7 ⊢ (𝑦 ∈ ℕ → (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} → (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑})) |
16 | 6, 15 | mpcom 38 | . . . . . 6 ⊢ (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} → (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑}) |
17 | 16 | rgen 3062 | . . . . 5 ⊢ ∀𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑} |
18 | peano5nni 12197 | . . . . 5 ⊢ ((1 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ∧ ∀𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑}) → ℕ ⊆ {𝑥 ∈ ℕ ∣ 𝜑}) | |
19 | 5, 17, 18 | mp2an 690 | . . . 4 ⊢ ℕ ⊆ {𝑥 ∈ ℕ ∣ 𝜑} |
20 | 19 | sseli 3974 | . . 3 ⊢ (𝐴 ∈ ℕ → 𝐴 ∈ {𝑥 ∈ ℕ ∣ 𝜑}) |
21 | nnind.4 | . . . 4 ⊢ (𝑥 = 𝐴 → (𝜑 ↔ 𝜏)) | |
22 | 21 | elrab 3679 | . . 3 ⊢ (𝐴 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ (𝐴 ∈ ℕ ∧ 𝜏)) |
23 | 20, 22 | sylib 217 | . 2 ⊢ (𝐴 ∈ ℕ → (𝐴 ∈ ℕ ∧ 𝜏)) |
24 | 23 | simprd 496 | 1 ⊢ (𝐴 ∈ ℕ → 𝜏) |
Colors of variables: wff setvar class |
Syntax hints: → wi 4 ↔ wb 205 ∧ wa 396 = wceq 1541 ∈ wcel 2106 ∀wral 3060 {crab 3431 ⊆ wss 3944 (class class class)co 7393 1c1 11093 + caddc 11095 ℕcn 12194 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1797 ax-4 1811 ax-5 1913 ax-6 1971 ax-7 2011 ax-8 2108 ax-9 2116 ax-10 2137 ax-11 2154 ax-12 2171 ax-ext 2702 ax-sep 5292 ax-nul 5299 ax-pr 5420 ax-un 7708 ax-1cn 11150 |
This theorem depends on definitions: df-bi 206 df-an 397 df-or 846 df-3or 1088 df-3an 1089 df-tru 1544 df-fal 1554 df-ex 1782 df-nf 1786 df-sb 2068 df-mo 2533 df-eu 2562 df-clab 2709 df-cleq 2723 df-clel 2809 df-nfc 2884 df-ne 2940 df-ral 3061 df-rex 3070 df-reu 3376 df-rab 3432 df-v 3475 df-sbc 3774 df-csb 3890 df-dif 3947 df-un 3949 df-in 3951 df-ss 3961 df-pss 3963 df-nul 4319 df-if 4523 df-pw 4598 df-sn 4623 df-pr 4625 df-op 4629 df-uni 4902 df-iun 4992 df-br 5142 df-opab 5204 df-mpt 5225 df-tr 5259 df-id 5567 df-eprel 5573 df-po 5581 df-so 5582 df-fr 5624 df-we 5626 df-xp 5675 df-rel 5676 df-cnv 5677 df-co 5678 df-dm 5679 df-rn 5680 df-res 5681 df-ima 5682 df-pred 6289 df-ord 6356 df-on 6357 df-lim 6358 df-suc 6359 df-iota 6484 df-fun 6534 df-fn 6535 df-f 6536 df-f1 6537 df-fo 6538 df-f1o 6539 df-fv 6540 df-ov 7396 df-om 7839 df-2nd 7958 df-frecs 8248 df-wrecs 8279 df-recs 8353 df-rdg 8392 df-nn 12195 |
This theorem is referenced by: nnindALT 12213 nnindd 12214 nn1m1nn 12215 nnaddcl 12217 nnmulcl 12218 nnge1 12222 nnne0 12228 nnsub 12238 nneo 12628 peano5uzi 12633 nn0ind-raph 12644 ser1const 14006 expcllem 14020 expeq0 14040 expmordi 14114 seqcoll 14407 relexpsucnnl 14959 relexpcnv 14964 relexprelg 14967 relexpnndm 14970 relexpaddnn 14980 climcndslem2 15778 sqrt2irr 16174 rplpwr 16481 prmind2 16604 prmdvdsexp 16634 eulerthlem2 16697 pcmpt 16807 prmpwdvds 16819 vdwlem10 16905 mulgnnass 18961 imasdsf1olem 23808 ovolunlem1a 24942 ovolicc2lem3 24965 voliunlem1 24996 volsup 25002 dvexp 25399 plyco 25684 dgrcolem1 25716 vieta1 25754 emcllem6 26432 bposlem5 26718 2sqlem10 26858 dchrisum0flb 26940 iuninc 31657 ofldchr 32294 nexple 32836 esumfzf 32896 rrvsum 33282 subfacp1lem6 34005 cvmliftlem10 34114 bcprod 34536 faclimlem1 34541 incsequz 36419 bfplem1 36493 nnn1suc 40966 nnadd1com 40967 nnaddcom 40968 nnadddir 40970 nnmul1com 40971 nnmulcom 40972 2nn0ind 41453 relexpxpnnidm 42223 relexpss1d 42225 iunrelexpmin1 42228 relexpmulnn 42229 trclrelexplem 42231 iunrelexpmin2 42232 relexp0a 42236 cotrcltrcl 42245 trclimalb2 42246 cotrclrcl 42262 inductionexd 42675 fmuldfeq 44070 dvnmptconst 44428 stoweidlem20 44507 wallispilem4 44555 wallispi2lem1 44558 wallispi2lem2 44559 dirkertrigeqlem1 44585 iccelpart 45871 nn0sumshdiglem2 46954 |
Copyright terms: Public domain | W3C validator |