2nn0ind - Mathbox for Stefan O'Rear

	Mathbox for Stefan O'Rear		< Previous Next > Nearby theorems
Mirrors > Home > MPE Home > Th. List > Mathboxes > 2nn0ind		Structured version Visualization version GIF version

Theorem 2nn0ind 42357

Description: Induction on nonnegative integers with two base cases, for use with Lucas-type sequences. (Contributed by Stefan O'Rear, 1-Oct-2014.)

**Hypotheses**
Ref	Expression
2nn0ind.1	⊢ 𝜓
2nn0ind.2	⊢ 𝜒
2nn0ind.3	⊢ (𝑦 ∈ ℕ → ((𝜃 ∧ 𝜏) → 𝜂))
2nn0ind.4	⊢ (𝑥 = 0 → (𝜑 ↔ 𝜓))
2nn0ind.5	⊢ (𝑥 = 1 → (𝜑 ↔ 𝜒))
2nn0ind.6	⊢ (𝑥 = (𝑦 − 1) → (𝜑 ↔ 𝜃))
2nn0ind.7	⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜏))
2nn0ind.8	⊢ (𝑥 = (𝑦 + 1) → (𝜑 ↔ 𝜂))
2nn0ind.9	⊢ (𝑥 = 𝐴 → (𝜑 ↔ 𝜌))

**Assertion**
Ref	Expression
2nn0ind	⊢ (𝐴 ∈ ℕ₀ → 𝜌)

Distinct variable groups: 𝑥,𝑦 𝑥,𝐴 𝜓,𝑥 𝜒,𝑥 𝜃,𝑥 𝜏,𝑥 𝜂,𝑥 𝜌,𝑥 𝜑,𝑦 Allowed substitution hints: 𝜑(𝑥) 𝜓(𝑦) 𝜒(𝑦) 𝜃(𝑦) 𝜏(𝑦) 𝜂(𝑦) 𝜌(𝑦) 𝐴(𝑦)

Proof of Theorem 2nn0ind Dummy variable 𝑎 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		nn0p1nn 12536	. . . 4 ⊢ (𝐴 ∈ ℕ₀ → (𝐴 + 1) ∈ ℕ)
2		oveq1 7422	. . . . . . 7 ⊢ (𝑎 = 1 → (𝑎 − 1) = (1 − 1))
3	2	sbceq1d 3780	. . . . . 6 ⊢ (𝑎 = 1 → ([(𝑎 − 1) / 𝑥]𝜑 ↔ [(1 − 1) / 𝑥]𝜑))
4		dfsbcq 3777	. . . . . 6 ⊢ (𝑎 = 1 → ([𝑎 / 𝑥]𝜑 ↔ [1 / 𝑥]𝜑))
5	3, 4	anbi12d 631	. . . . 5 ⊢ (𝑎 = 1 → (([(𝑎 − 1) / 𝑥]𝜑 ∧ [𝑎 / 𝑥]𝜑) ↔ ([(1 − 1) / 𝑥]𝜑 ∧ [1 / 𝑥]𝜑)))
6		oveq1 7422	. . . . . . 7 ⊢ (𝑎 = 𝑦 → (𝑎 − 1) = (𝑦 − 1))
7	6	sbceq1d 3780	. . . . . 6 ⊢ (𝑎 = 𝑦 → ([(𝑎 − 1) / 𝑥]𝜑 ↔ [(𝑦 − 1) / 𝑥]𝜑))
8		dfsbcq 3777	. . . . . 6 ⊢ (𝑎 = 𝑦 → ([𝑎 / 𝑥]𝜑 ↔ [𝑦 / 𝑥]𝜑))
9	7, 8	anbi12d 631	. . . . 5 ⊢ (𝑎 = 𝑦 → (([(𝑎 − 1) / 𝑥]𝜑 ∧ [𝑎 / 𝑥]𝜑) ↔ ([(𝑦 − 1) / 𝑥]𝜑 ∧ [𝑦 / 𝑥]𝜑)))
10		oveq1 7422	. . . . . . 7 ⊢ (𝑎 = (𝑦 + 1) → (𝑎 − 1) = ((𝑦 + 1) − 1))
11	10	sbceq1d 3780	. . . . . 6 ⊢ (𝑎 = (𝑦 + 1) → ([(𝑎 − 1) / 𝑥]𝜑 ↔ [((𝑦 + 1) − 1) / 𝑥]𝜑))
12		dfsbcq 3777	. . . . . 6 ⊢ (𝑎 = (𝑦 + 1) → ([𝑎 / 𝑥]𝜑 ↔ [(𝑦 + 1) / 𝑥]𝜑))
13	11, 12	anbi12d 631	. . . . 5 ⊢ (𝑎 = (𝑦 + 1) → (([(𝑎 − 1) / 𝑥]𝜑 ∧ [𝑎 / 𝑥]𝜑) ↔ ([((𝑦 + 1) − 1) / 𝑥]𝜑 ∧ [(𝑦 + 1) / 𝑥]𝜑)))
14		oveq1 7422	. . . . . . 7 ⊢ (𝑎 = (𝐴 + 1) → (𝑎 − 1) = ((𝐴 + 1) − 1))
15	14	sbceq1d 3780	. . . . . 6 ⊢ (𝑎 = (𝐴 + 1) → ([(𝑎 − 1) / 𝑥]𝜑 ↔ [((𝐴 + 1) − 1) / 𝑥]𝜑))
16		dfsbcq 3777	. . . . . 6 ⊢ (𝑎 = (𝐴 + 1) → ([𝑎 / 𝑥]𝜑 ↔ [(𝐴 + 1) / 𝑥]𝜑))
17	15, 16	anbi12d 631	. . . . 5 ⊢ (𝑎 = (𝐴 + 1) → (([(𝑎 − 1) / 𝑥]𝜑 ∧ [𝑎 / 𝑥]𝜑) ↔ ([((𝐴 + 1) − 1) / 𝑥]𝜑 ∧ [(𝐴 + 1) / 𝑥]𝜑)))
18		2nn0ind.1	. . . . . . 7 ⊢ 𝜓
19		ovex 7448	. . . . . . . 8 ⊢ (1 − 1) ∈ V
20		1m1e0 12309	. . . . . . . . . 10 ⊢ (1 − 1) = 0
21	20	eqeq2i 2741	. . . . . . . . 9 ⊢ (𝑥 = (1 − 1) ↔ 𝑥 = 0)
22		2nn0ind.4	. . . . . . . . 9 ⊢ (𝑥 = 0 → (𝜑 ↔ 𝜓))
23	21, 22	sylbi 216	. . . . . . . 8 ⊢ (𝑥 = (1 − 1) → (𝜑 ↔ 𝜓))
24	19, 23	sbcie 3818	. . . . . . 7 ⊢ ([(1 − 1) / 𝑥]𝜑 ↔ 𝜓)
25	18, 24	mpbir 230	. . . . . 6 ⊢ [(1 − 1) / 𝑥]𝜑
26		2nn0ind.2	. . . . . . 7 ⊢ 𝜒
27		1ex 11235	. . . . . . . 8 ⊢ 1 ∈ V
28		2nn0ind.5	. . . . . . . 8 ⊢ (𝑥 = 1 → (𝜑 ↔ 𝜒))
29	27, 28	sbcie 3818	. . . . . . 7 ⊢ ([1 / 𝑥]𝜑 ↔ 𝜒)
30	26, 29	mpbir 230	. . . . . 6 ⊢ [1 / 𝑥]𝜑
31	25, 30	pm3.2i 470	. . . . 5 ⊢ ([(1 − 1) / 𝑥]𝜑 ∧ [1 / 𝑥]𝜑)
32		simprr 772	. . . . . . . 8 ⊢ ((𝑦 ∈ ℕ ∧ ([(𝑦 − 1) / 𝑥]𝜑 ∧ [𝑦 / 𝑥]𝜑)) → [𝑦 / 𝑥]𝜑)
33		nncn 12245	. . . . . . . . . . 11 ⊢ (𝑦 ∈ ℕ → 𝑦 ∈ ℂ)
34		ax-1cn 11191	. . . . . . . . . . 11 ⊢ 1 ∈ ℂ
35		pncan 11491	. . . . . . . . . . 11 ⊢ ((𝑦 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝑦 + 1) − 1) = 𝑦)
36	33, 34, 35	sylancl 585	. . . . . . . . . 10 ⊢ (𝑦 ∈ ℕ → ((𝑦 + 1) − 1) = 𝑦)
37	36	adantr 480	. . . . . . . . 9 ⊢ ((𝑦 ∈ ℕ ∧ ([(𝑦 − 1) / 𝑥]𝜑 ∧ [𝑦 / 𝑥]𝜑)) → ((𝑦 + 1) − 1) = 𝑦)
38	37	sbceq1d 3780	. . . . . . . 8 ⊢ ((𝑦 ∈ ℕ ∧ ([(𝑦 − 1) / 𝑥]𝜑 ∧ [𝑦 / 𝑥]𝜑)) → ([((𝑦 + 1) − 1) / 𝑥]𝜑 ↔ [𝑦 / 𝑥]𝜑))
39	32, 38	mpbird 257	. . . . . . 7 ⊢ ((𝑦 ∈ ℕ ∧ ([(𝑦 − 1) / 𝑥]𝜑 ∧ [𝑦 / 𝑥]𝜑)) → [((𝑦 + 1) − 1) / 𝑥]𝜑)
40		2nn0ind.3	. . . . . . . . 9 ⊢ (𝑦 ∈ ℕ → ((𝜃 ∧ 𝜏) → 𝜂))
41		ovex 7448	. . . . . . . . . . 11 ⊢ (𝑦 − 1) ∈ V
42		2nn0ind.6	. . . . . . . . . . 11 ⊢ (𝑥 = (𝑦 − 1) → (𝜑 ↔ 𝜃))
43	41, 42	sbcie 3818	. . . . . . . . . 10 ⊢ ([(𝑦 − 1) / 𝑥]𝜑 ↔ 𝜃)
44		vex 3474	. . . . . . . . . . 11 ⊢ 𝑦 ∈ V
45		2nn0ind.7	. . . . . . . . . . 11 ⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜏))
46	44, 45	sbcie 3818	. . . . . . . . . 10 ⊢ ([𝑦 / 𝑥]𝜑 ↔ 𝜏)
47	43, 46	anbi12i 627	. . . . . . . . 9 ⊢ (([(𝑦 − 1) / 𝑥]𝜑 ∧ [𝑦 / 𝑥]𝜑) ↔ (𝜃 ∧ 𝜏))
48		ovex 7448	. . . . . . . . . 10 ⊢ (𝑦 + 1) ∈ V
49		2nn0ind.8	. . . . . . . . . 10 ⊢ (𝑥 = (𝑦 + 1) → (𝜑 ↔ 𝜂))
50	48, 49	sbcie 3818	. . . . . . . . 9 ⊢ ([(𝑦 + 1) / 𝑥]𝜑 ↔ 𝜂)
51	40, 47, 50	3imtr4g 296	. . . . . . . 8 ⊢ (𝑦 ∈ ℕ → (([(𝑦 − 1) / 𝑥]𝜑 ∧ [𝑦 / 𝑥]𝜑) → [(𝑦 + 1) / 𝑥]𝜑))
52	51	imp 406	. . . . . . 7 ⊢ ((𝑦 ∈ ℕ ∧ ([(𝑦 − 1) / 𝑥]𝜑 ∧ [𝑦 / 𝑥]𝜑)) → [(𝑦 + 1) / 𝑥]𝜑)
53	39, 52	jca 511	. . . . . 6 ⊢ ((𝑦 ∈ ℕ ∧ ([(𝑦 − 1) / 𝑥]𝜑 ∧ [𝑦 / 𝑥]𝜑)) → ([((𝑦 + 1) − 1) / 𝑥]𝜑 ∧ [(𝑦 + 1) / 𝑥]𝜑))
54	53	ex 412	. . . . 5 ⊢ (𝑦 ∈ ℕ → (([(𝑦 − 1) / 𝑥]𝜑 ∧ [𝑦 / 𝑥]𝜑) → ([((𝑦 + 1) − 1) / 𝑥]𝜑 ∧ [(𝑦 + 1) / 𝑥]𝜑)))
55	5, 9, 13, 17, 31, 54	nnind 12255	. . . 4 ⊢ ((𝐴 + 1) ∈ ℕ → ([((𝐴 + 1) − 1) / 𝑥]𝜑 ∧ [(𝐴 + 1) / 𝑥]𝜑))
56	1, 55	syl 17	. . 3 ⊢ (𝐴 ∈ ℕ₀ → ([((𝐴 + 1) − 1) / 𝑥]𝜑 ∧ [(𝐴 + 1) / 𝑥]𝜑))
57		nn0cn 12507	. . . . . . 7 ⊢ (𝐴 ∈ ℕ₀ → 𝐴 ∈ ℂ)
58		pncan 11491	. . . . . . 7 ⊢ ((𝐴 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝐴 + 1) − 1) = 𝐴)
59	57, 34, 58	sylancl 585	. . . . . 6 ⊢ (𝐴 ∈ ℕ₀ → ((𝐴 + 1) − 1) = 𝐴)
60	59	sbceq1d 3780	. . . . 5 ⊢ (𝐴 ∈ ℕ₀ → ([((𝐴 + 1) − 1) / 𝑥]𝜑 ↔ [𝐴 / 𝑥]𝜑))
61	60	biimpa 476	. . . 4 ⊢ ((𝐴 ∈ ℕ₀ ∧ [((𝐴 + 1) − 1) / 𝑥]𝜑) → [𝐴 / 𝑥]𝜑)
62	61	adantrr 716	. . 3 ⊢ ((𝐴 ∈ ℕ₀ ∧ ([((𝐴 + 1) − 1) / 𝑥]𝜑 ∧ [(𝐴 + 1) / 𝑥]𝜑)) → [𝐴 / 𝑥]𝜑)
63	56, 62	mpdan 686	. 2 ⊢ (𝐴 ∈ ℕ₀ → [𝐴 / 𝑥]𝜑)
64		2nn0ind.9	. . 3 ⊢ (𝑥 = 𝐴 → (𝜑 ↔ 𝜌))
65	64	sbcieg 3815	. 2 ⊢ (𝐴 ∈ ℕ₀ → ([𝐴 / 𝑥]𝜑 ↔ 𝜌))
66	63, 65	mpbid 231	1 ⊢ (𝐴 ∈ ℕ₀ → 𝜌)

Colors of variables: wff setvar class

Syntax hints: → wi 4 ↔ wb 205 ∧ wa 395 = wceq 1534 ∈ wcel 2099 [wsbc 3775 (class class class)co 7415 ℂcc 11131 0cc0 11133 1c1 11134 + caddc 11136 − cmin 11469 ℕcn 12237 ℕ₀cn0 12497

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 2167 ax-ext 2699 ax-sep 5294 ax-nul 5301 ax-pow 5360 ax-pr 5424 ax-un 7735 ax-resscn 11190 ax-1cn 11191 ax-icn 11192 ax-addcl 11193 ax-addrcl 11194 ax-mulcl 11195 ax-mulrcl 11196 ax-mulcom 11197 ax-addass 11198 ax-mulass 11199 ax-distr 11200 ax-i2m1 11201 ax-1ne0 11202 ax-1rid 11203 ax-rnegex 11204 ax-rrecex 11205 ax-cnre 11206 ax-pre-lttri 11207 ax-pre-lttrn 11208 ax-pre-ltadd 11209

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 2530 df-eu 2559 df-clab 2706 df-cleq 2720 df-clel 2806 df-nfc 2881 df-ne 2937 df-nel 3043 df-ral 3058 df-rex 3067 df-reu 3373 df-rab 3429 df-v 3472 df-sbc 3776 df-csb 3891 df-dif 3948 df-un 3950 df-in 3952 df-ss 3962 df-pss 3964 df-nul 4320 df-if 4526 df-pw 4601 df-sn 4626 df-pr 4628 df-op 4632 df-uni 4905 df-iun 4994 df-br 5144 df-opab 5206 df-mpt 5227 df-tr 5261 df-id 5571 df-eprel 5577 df-po 5585 df-so 5586 df-fr 5628 df-we 5630 df-xp 5679 df-rel 5680 df-cnv 5681 df-co 5682 df-dm 5683 df-rn 5684 df-res 5685 df-ima 5686 df-pred 6300 df-ord 6367 df-on 6368 df-lim 6369 df-suc 6370 df-iota 6495 df-fun 6545 df-fn 6546 df-f 6547 df-f1 6548 df-fo 6549 df-f1o 6550 df-fv 6551 df-riota 7371 df-ov 7418 df-oprab 7419 df-mpo 7420 df-om 7866 df-2nd 7989 df-frecs 8281 df-wrecs 8312 df-recs 8386 df-rdg 8425 df-er 8719 df-en 8959 df-dom 8960 df-sdom 8961 df-pnf 11275 df-mnf 11276 df-ltxr 11278 df-sub 11471 df-nn 12238 df-n0 12498

This theorem is referenced by: jm2.18 42400 jm2.15nn0 42415 jm2.16nn0 42416

W3C validator

	
		OSZAR »