![]() |
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 12257 for an example of its use. See nn0ind 12679 for induction on nonnegative integers and uzind 12676, uzind4 12912 for induction on an arbitrary upper set of integers. See indstr 12922 for strong induction. See also nnindALT 12253. 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 12245 | . . . . . 6 ⊢ 1 ∈ ℕ | |
2 | nnind.5 | . . . . . 6 ⊢ 𝜓 | |
3 | nnind.1 | . . . . . . 7 ⊢ (𝑥 = 1 → (𝜑 ↔ 𝜓)) | |
4 | 3 | elrab 3680 | . . . . . 6 ⊢ (1 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ (1 ∈ ℕ ∧ 𝜓)) |
5 | 1, 2, 4 | mpbir2an 710 | . . . . 5 ⊢ 1 ∈ {𝑥 ∈ ℕ ∣ 𝜑} |
6 | elrabi 3674 | . . . . . . 7 ⊢ (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} → 𝑦 ∈ ℕ) | |
7 | peano2nn 12246 | . . . . . . . . . 10 ⊢ (𝑦 ∈ ℕ → (𝑦 + 1) ∈ ℕ) | |
8 | 7 | a1d 25 | . . . . . . . . 9 ⊢ (𝑦 ∈ ℕ → (𝑦 ∈ ℕ → (𝑦 + 1) ∈ ℕ)) |
9 | nnind.6 | . . . . . . . . 9 ⊢ (𝑦 ∈ ℕ → (𝜒 → 𝜃)) | |
10 | 8, 9 | anim12d 608 | . . . . . . . 8 ⊢ (𝑦 ∈ ℕ → ((𝑦 ∈ ℕ ∧ 𝜒) → ((𝑦 + 1) ∈ ℕ ∧ 𝜃))) |
11 | nnind.2 | . . . . . . . . 9 ⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜒)) | |
12 | 11 | elrab 3680 | . . . . . . . 8 ⊢ (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ (𝑦 ∈ ℕ ∧ 𝜒)) |
13 | nnind.3 | . . . . . . . . 9 ⊢ (𝑥 = (𝑦 + 1) → (𝜑 ↔ 𝜃)) | |
14 | 13 | elrab 3680 | . . . . . . . 8 ⊢ ((𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ ((𝑦 + 1) ∈ ℕ ∧ 𝜃)) |
15 | 10, 12, 14 | 3imtr4g 296 | . . . . . . 7 ⊢ (𝑦 ∈ ℕ → (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} → (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑})) |
16 | 6, 15 | mpcom 38 | . . . . . 6 ⊢ (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} → (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑}) |
17 | 16 | rgen 3058 | . . . . 5 ⊢ ∀𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑} |
18 | peano5nni 12237 | . . . . 5 ⊢ ((1 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ∧ ∀𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑}) → ℕ ⊆ {𝑥 ∈ ℕ ∣ 𝜑}) | |
19 | 5, 17, 18 | mp2an 691 | . . . 4 ⊢ ℕ ⊆ {𝑥 ∈ ℕ ∣ 𝜑} |
20 | 19 | sseli 3974 | . . 3 ⊢ (𝐴 ∈ ℕ → 𝐴 ∈ {𝑥 ∈ ℕ ∣ 𝜑}) |
21 | nnind.4 | . . . 4 ⊢ (𝑥 = 𝐴 → (𝜑 ↔ 𝜏)) | |
22 | 21 | elrab 3680 | . . 3 ⊢ (𝐴 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ (𝐴 ∈ ℕ ∧ 𝜏)) |
23 | 20, 22 | sylib 217 | . 2 ⊢ (𝐴 ∈ ℕ → (𝐴 ∈ ℕ ∧ 𝜏)) |
24 | 23 | simprd 495 | 1 ⊢ (𝐴 ∈ ℕ → 𝜏) |
Colors of variables: wff setvar class |
Syntax hints: → wi 4 ↔ wb 205 ∧ wa 395 = wceq 1534 ∈ wcel 2099 ∀wral 3056 {crab 3427 ⊆ wss 3944 (class class class)co 7414 1c1 11131 + caddc 11133 ℕcn 12234 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1790 ax-4 1804 ax-5 1906 ax-6 1964 ax-7 2004 ax-8 2101 ax-9 2109 ax-10 2130 ax-11 2147 ax-12 2164 ax-ext 2698 ax-sep 5293 ax-nul 5300 ax-pr 5423 ax-un 7734 ax-1cn 11188 |
This theorem depends on definitions: df-bi 206 df-an 396 df-or 847 df-3or 1086 df-3an 1087 df-tru 1537 df-fal 1547 df-ex 1775 df-nf 1779 df-sb 2061 df-mo 2529 df-eu 2558 df-clab 2705 df-cleq 2719 df-clel 2805 df-nfc 2880 df-ne 2936 df-ral 3057 df-rex 3066 df-reu 3372 df-rab 3428 df-v 3471 df-sbc 3775 df-csb 3890 df-dif 3947 df-un 3949 df-in 3951 df-ss 3961 df-pss 3963 df-nul 4319 df-if 4525 df-pw 4600 df-sn 4625 df-pr 4627 df-op 4631 df-uni 4904 df-iun 4993 df-br 5143 df-opab 5205 df-mpt 5226 df-tr 5260 df-id 5570 df-eprel 5576 df-po 5584 df-so 5585 df-fr 5627 df-we 5629 df-xp 5678 df-rel 5679 df-cnv 5680 df-co 5681 df-dm 5682 df-rn 5683 df-res 5684 df-ima 5685 df-pred 6299 df-ord 6366 df-on 6367 df-lim 6368 df-suc 6369 df-iota 6494 df-fun 6544 df-fn 6545 df-f 6546 df-f1 6547 df-fo 6548 df-f1o 6549 df-fv 6550 df-ov 7417 df-om 7865 df-2nd 7988 df-frecs 8280 df-wrecs 8311 df-recs 8385 df-rdg 8424 df-nn 12235 |
This theorem is referenced by: nnindALT 12253 nnindd 12254 nn1m1nn 12255 nnaddcl 12257 nnmulcl 12258 nnge1 12262 nnne0 12268 nnsub 12278 nneo 12668 peano5uzi 12673 nn0ind-raph 12684 ser1const 14047 expcllem 14061 expeq0 14081 expmordi 14155 seqcoll 14449 relexpsucnnl 15001 relexpcnv 15006 relexprelg 15009 relexpnndm 15012 relexpaddnn 15022 climcndslem2 15820 sqrt2irr 16217 rplpwr 16524 prmind2 16647 prmdvdsexp 16677 eulerthlem2 16742 pcmpt 16852 prmpwdvds 16864 vdwlem10 16950 mulgnnass 19055 imasdsf1olem 24266 ovolunlem1a 25412 ovolicc2lem3 25435 voliunlem1 25466 volsup 25472 dvexp 25872 plyco 26162 dgrcolem1 26195 vieta1 26234 emcllem6 26920 bposlem5 27208 2sqlem10 27348 dchrisum0flb 27430 iuninc 32336 ofldchr 32969 nexple 33564 esumfzf 33624 rrvsum 34010 subfacp1lem6 34731 cvmliftlem10 34840 bcprod 35268 faclimlem1 35273 incsequz 37156 bfplem1 37230 nnn1suc 41763 nnadd1com 41764 nnaddcom 41765 nnadddir 41767 nnmul1com 41768 nnmulcom 41769 2nn0ind 42288 relexpxpnnidm 43056 relexpss1d 43058 iunrelexpmin1 43061 relexpmulnn 43062 trclrelexplem 43064 iunrelexpmin2 43065 relexp0a 43069 cotrcltrcl 43078 trclimalb2 43079 cotrclrcl 43095 inductionexd 43508 fmuldfeq 44894 dvnmptconst 45252 stoweidlem20 45331 wallispilem4 45379 wallispi2lem1 45382 wallispi2lem2 45383 dirkertrigeqlem1 45409 iccelpart 46696 nn0sumshdiglem2 47618 |
Copyright terms: Public domain | W3C validator |