Theorem nnind 8998

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 9002 for an example of its use. This is an alternative for Metamath 100 proof #74. (Contributed by NM, 10-Jan-1997.) (Revised by Mario Carneiro, 16-Jun-2013.)

Hypotheses

Ref	Expression
nnind.1	⊢ (𝑥 = 1 → (𝜑 ↔ 𝜓))
nnind.2	⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜒))
nnind.3	⊢ (𝑥 = (𝑦 + 1) → (𝜑 ↔ 𝜃))
nnind.4	⊢ (𝑥 = 𝐴 → (𝜑 ↔ 𝜏))
nnind.5	⊢ 𝜓
nnind.6	⊢ (𝑦 ∈ ℕ → (𝜒 → 𝜃))

Assertion

Ref	Expression
nnind	⊢ (𝐴 ∈ ℕ → 𝜏)

Distinct variable groups:   𝑥,𝑦   𝑥,𝐴   𝜓,𝑥   𝜒,𝑥   𝜃,𝑥   𝜏,𝑥   𝜑,𝑦

Allowed substitution hints:   𝜑(𝑥)   𝜓(𝑦)   𝜒(𝑦)   𝜃(𝑦)   𝜏(𝑦)   𝐴(𝑦)

Proof of Theorem nnind

Step	Hyp	Ref	Expression
1		1nn 8993	. . . . . 6 ⊢ 1 ∈ ℕ
2		nnind.5	. . . . . 6 ⊢ 𝜓
3		nnind.1	. . . . . . 7 ⊢ (𝑥 = 1 → (𝜑 ↔ 𝜓))
4	3	elrab 2916	. . . . . 6 ⊢ (1 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ (1 ∈ ℕ ∧ 𝜓))
5	1, 2, 4	mpbir2an 944	. . . . 5 ⊢ 1 ∈ {𝑥 ∈ ℕ ∣ 𝜑}
6		elrabi 2913	. . . . . . 7 ⊢ (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} → 𝑦 ∈ ℕ)
7		peano2nn 8994	. . . . . . . . . 10 ⊢ (𝑦 ∈ ℕ → (𝑦 + 1) ∈ ℕ)
8	7	a1d 22	. . . . . . . . 9 ⊢ (𝑦 ∈ ℕ → (𝑦 ∈ ℕ → (𝑦 + 1) ∈ ℕ))
9		nnind.6	. . . . . . . . 9 ⊢ (𝑦 ∈ ℕ → (𝜒 → 𝜃))
10	8, 9	anim12d 335	. . . . . . . 8 ⊢ (𝑦 ∈ ℕ → ((𝑦 ∈ ℕ ∧ 𝜒) → ((𝑦 + 1) ∈ ℕ ∧ 𝜃)))
11		nnind.2	. . . . . . . . 9 ⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜒))
12	11	elrab 2916	. . . . . . . 8 ⊢ (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ (𝑦 ∈ ℕ ∧ 𝜒))
13		nnind.3	. . . . . . . . 9 ⊢ (𝑥 = (𝑦 + 1) → (𝜑 ↔ 𝜃))
14	13	elrab 2916	. . . . . . . 8 ⊢ ((𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ ((𝑦 + 1) ∈ ℕ ∧ 𝜃))
15	10, 12, 14	3imtr4g 205	. . . . . . 7 ⊢ (𝑦 ∈ ℕ → (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} → (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑}))
16	6, 15	mpcom 36	. . . . . 6 ⊢ (𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} → (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑})
17	16	rgen 2547	. . . . 5 ⊢ ∀𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑}
18		peano5nni 8985	. . . . 5 ⊢ ((1 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ∧ ∀𝑦 ∈ {𝑥 ∈ ℕ ∣ 𝜑} (𝑦 + 1) ∈ {𝑥 ∈ ℕ ∣ 𝜑}) → ℕ ⊆ {𝑥 ∈ ℕ ∣ 𝜑})
19	5, 17, 18	mp2an 426	. . . 4 ⊢ ℕ ⊆ {𝑥 ∈ ℕ ∣ 𝜑}
20	19	sseli 3175	. . 3 ⊢ (𝐴 ∈ ℕ → 𝐴 ∈ {𝑥 ∈ ℕ ∣ 𝜑})
21		nnind.4	. . . 4 ⊢ (𝑥 = 𝐴 → (𝜑 ↔ 𝜏))
22	21	elrab 2916	. . 3 ⊢ (𝐴 ∈ {𝑥 ∈ ℕ ∣ 𝜑} ↔ (𝐴 ∈ ℕ ∧ 𝜏))
23	20, 22	sylib 122	. 2 ⊢ (𝐴 ∈ ℕ → (𝐴 ∈ ℕ ∧ 𝜏))
24	23	simprd 114	1 ⊢ (𝐴 ∈ ℕ → 𝜏)

Syntax hints:   → wi 4   ∧ wa 104   ↔ wb 105   = wceq 1364   ∈ wcel 2164  ∀wral 2472  {crab 2476   ⊆ wss 3153  (class class class)co 5918  1c1 7873   + caddc 7875  ℕcn 8982

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-io 710  ax-5 1458  ax-7 1459  ax-gen 1460  ax-ie1 1504  ax-ie2 1505  ax-8 1515  ax-10 1516  ax-11 1517  ax-i12 1518  ax-bndl 1520  ax-4 1521  ax-17 1537  ax-i9 1541  ax-ial 1545  ax-i5r 1546  ax-ext 2175  ax-sep 4147  ax-cnex 7963  ax-resscn 7964  ax-1re 7966  ax-addrcl 7969

This theorem depends on definitions:  df-bi 117  df-3an 982  df-tru 1367  df-nf 1472  df-sb 1774  df-clab 2180  df-cleq 2186  df-clel 2189  df-nfc 2325  df-ral 2477  df-rex 2478  df-rab 2481  df-v 2762  df-un 3157  df-in 3159  df-ss 3166  df-sn 3624  df-pr 3625  df-op 3627  df-uni 3836  df-int 3871  df-br 4030  df-iota 5215  df-fv 5262  df-ov 5921  df-inn 8983

This theorem is referenced by:  nnindALT  8999  nn1m1nn  9000  nnaddcl  9002  nnmulcl  9003  nnge1  9005  nn1gt1  9016  nnsub  9021  zaddcllempos  9354  zaddcllemneg  9356  nneoor  9419  peano5uzti  9425  nn0ind-raph  9434  indstr  9658  exbtwnzlemshrink  10317  exp3vallem  10611  expcllem  10621  expap0  10640  apexp1  10789  seq3coll  10913  resqrexlemover  11154  resqrexlemlo  11157  resqrexlemcalc3  11160  gcdmultiple  12157  rplpwr  12164  prmind2  12258  prmdvdsexp  12286  sqrt2irr  12300  pw2dvdslemn  12303  pcmpt  12481  prmpwdvds  12493  mulgnnass  13227  dvexp  14860  2sqlem10  15212