| 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 12289 for an example of its use. See nn0ind 12713 for induction on nonnegative integers and uzind 12710, uzind4 12948 for induction on an arbitrary upper set of integers. See indstr 12958 for strong induction. See also nnindALT 12285. 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 12277 | . . . . . 6 ⊢ 1 ∈ ℕ | |
| 2 | nnind.5 | . . . . . 6 ⊢ 𝜓 | |
| 3 | nnind.1 | . . . . . . 7 ⊢ (𝑥 = 1 → (𝜑 ↔ 𝜓)) | |
| 4 | 3 | elrab 3692 | . . . . . 6 ⊢ (1 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ (1 ∈ ℕ ∧ 𝜓)) |
| 5 | 1, 2, 4 | mpbir2an 711 | . . . . 5 ⊢ 1 ∈ {𝑥 ∈ ℕ ∣ 𝜑} |
| 6 | elrabi 3687 | . . . . . . 7 ⊢ (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} → 𝑦 ∈ ℕ) | |
| 7 | peano2nn 12278 | . . . . . . . . . 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 3692 | . . . . . . . 8 ⊢ (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ (𝑦 ∈ ℕ ∧ 𝜒)) |
| 13 | nnind.3 | . . . . . . . . 9 ⊢ (𝑥 = (𝑦 + 1) → (𝜑 ↔ 𝜃)) | |
| 14 | 13 | elrab 3692 | . . . . . . . 8 ⊢ ((𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ ((𝑦 + 1) ∈ ℕ ∧ 𝜃)) |
| 15 | 10, 12, 14 | 3imtr4g 296 | . . . . . . 7 ⊢ (𝑦 ∈ ℕ → (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} → (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑})) |
| 16 | 6, 15 | mpcom 38 | . . . . . 6 ⊢ (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} → (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑}) |
| 17 | 16 | rgen 3063 | . . . . 5 ⊢ ∀𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑} |
| 18 | peano5nni 12269 | . . . . 5 ⊢ ((1 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ∧ ∀𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑}) → ℕ ⊆ {𝑥 ∈ ℕ ∣ 𝜑}) | |
| 19 | 5, 17, 18 | mp2an 692 | . . . 4 ⊢ ℕ ⊆ {𝑥 ∈ ℕ ∣ 𝜑} |
| 20 | 19 | sseli 3979 | . . 3 ⊢ (𝐴 ∈ ℕ → 𝐴 ∈ {𝑥 ∈ ℕ ∣ 𝜑}) |
| 21 | nnind.4 | . . . 4 ⊢ (𝑥 = 𝐴 → (𝜑 ↔ 𝜏)) | |
| 22 | 21 | elrab 3692 | . . 3 ⊢ (𝐴 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ (𝐴 ∈ ℕ ∧ 𝜏)) |
| 23 | 20, 22 | sylib 218 | . 2 ⊢ (𝐴 ∈ ℕ → (𝐴 ∈ ℕ ∧ 𝜏)) |
| 24 | 23 | simprd 495 | 1 ⊢ (𝐴 ∈ ℕ → 𝜏) |
| Colors of variables: wff setvar class |
| Syntax hints: → wi 4 ↔ wb 206 ∧ wa 395 = wceq 1540 ∈ wcel 2108 ∀wral 3061 {crab 3436 ⊆ wss 3951 (class class class)co 7431 1c1 11156 + caddc 11158 ℕcn 12266 |
| This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1795 ax-4 1809 ax-5 1910 ax-6 1967 ax-7 2007 ax-8 2110 ax-9 2118 ax-10 2141 ax-11 2157 ax-12 2177 ax-ext 2708 ax-sep 5296 ax-nul 5306 ax-pr 5432 ax-un 7755 ax-1cn 11213 |
| This theorem depends on definitions: df-bi 207 df-an 396 df-or 849 df-3or 1088 df-3an 1089 df-tru 1543 df-fal 1553 df-ex 1780 df-nf 1784 df-sb 2065 df-mo 2540 df-eu 2569 df-clab 2715 df-cleq 2729 df-clel 2816 df-nfc 2892 df-ne 2941 df-ral 3062 df-rex 3071 df-reu 3381 df-rab 3437 df-v 3482 df-sbc 3789 df-csb 3900 df-dif 3954 df-un 3956 df-in 3958 df-ss 3968 df-pss 3971 df-nul 4334 df-if 4526 df-pw 4602 df-sn 4627 df-pr 4629 df-op 4633 df-uni 4908 df-iun 4993 df-br 5144 df-opab 5206 df-mpt 5226 df-tr 5260 df-id 5578 df-eprel 5584 df-po 5592 df-so 5593 df-fr 5637 df-we 5639 df-xp 5691 df-rel 5692 df-cnv 5693 df-co 5694 df-dm 5695 df-rn 5696 df-res 5697 df-ima 5698 df-pred 6321 df-ord 6387 df-on 6388 df-lim 6389 df-suc 6390 df-iota 6514 df-fun 6563 df-fn 6564 df-f 6565 df-f1 6566 df-fo 6567 df-f1o 6568 df-fv 6569 df-ov 7434 df-om 7888 df-2nd 8015 df-frecs 8306 df-wrecs 8337 df-recs 8411 df-rdg 8450 df-nn 12267 |
| This theorem is referenced by: nnindALT 12285 nnindd 12286 nn1m1nn 12287 nnaddcl 12289 nnmulcl 12290 nnge1 12294 nnne0 12300 nnsub 12310 nneo 12702 peano5uzi 12707 nn0ind-raph 12718 ser1const 14099 expcllem 14113 expeq0 14133 expmordi 14207 seqcoll 14503 relexpsucnnl 15069 relexpcnv 15074 relexprelg 15077 relexpnndm 15080 relexpaddnn 15090 climcndslem2 15886 sqrt2irr 16285 rplpwr 16595 prmind2 16722 prmdvdsexp 16752 eulerthlem2 16819 pcmpt 16930 prmpwdvds 16942 vdwlem10 17028 mulgnnass 19127 imasdsf1olem 24383 ovolunlem1a 25531 ovolicc2lem3 25554 voliunlem1 25585 volsup 25591 dvexp 25991 plyco 26280 dgrcolem1 26313 vieta1 26354 emcllem6 27044 bposlem5 27332 2sqlem10 27472 dchrisum0flb 27554 iuninc 32573 nexple 32833 ofldchr 33344 esumfzf 34070 rrvsum 34456 subfacp1lem6 35190 cvmliftlem10 35299 bcprod 35738 faclimlem1 35743 incsequz 37755 bfplem1 37829 nnn1suc 42301 nnadd1com 42302 nnaddcom 42303 nnadddir 42305 nnmul1com 42306 nnmulcom 42307 2nn0ind 42957 relexpxpnnidm 43716 relexpss1d 43718 iunrelexpmin1 43721 relexpmulnn 43722 trclrelexplem 43724 iunrelexpmin2 43725 relexp0a 43729 cotrcltrcl 43738 trclimalb2 43739 cotrclrcl 43755 inductionexd 44168 fmuldfeq 45598 dvnmptconst 45956 stoweidlem20 46035 wallispilem4 46083 wallispi2lem1 46086 wallispi2lem2 46087 dirkertrigeqlem1 46113 iccelpart 47420 nn0sumshdiglem2 48543 |
| Copyright terms: Public domain | W3C validator |