Theorem tfindes 6766

Description: Transfinite Induction with explicit substitution. The first hypothesis is the basis, the second is the induction step for successors, and the third is the induction step for limit ordinals. Theorem Schema 4 of [Suppes] p. 197. (Contributed by NM, 5-Mar-2004.)

Hypotheses

Ref	Expression
tfindes.1	⊢ [∅ / 𝑥]𝜑
tfindes.2	⊢ (𝑥 ∈ On → (𝜑 → [suc 𝑥 / 𝑥]𝜑))
tfindes.3	⊢ (Lim 𝑦 → (∀𝑥 ∈ 𝑦 𝜑 → [𝑦 / 𝑥]𝜑))

Assertion

Ref	Expression
tfindes	⊢ (𝑥 ∈ On → 𝜑)

Distinct variable groups:   𝑥,𝑦   𝜑,𝑦

Allowed substitution hint:   𝜑(𝑥)

Proof of Theorem tfindes

Dummy variable 𝑧 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		dfsbcq 3293	. 2 ⊢ (𝑦 = ∅ → ([𝑦 / 𝑥]𝜑 ↔ [∅ / 𝑥]𝜑))
2		dfsbcq 3293	. 2 ⊢ (𝑦 = 𝑧 → ([𝑦 / 𝑥]𝜑 ↔ [𝑧 / 𝑥]𝜑))
3		dfsbcq 3293	. 2 ⊢ (𝑦 = suc 𝑧 → ([𝑦 / 𝑥]𝜑 ↔ [suc 𝑧 / 𝑥]𝜑))
4		sbceq2a 3303	. 2 ⊢ (𝑦 = 𝑥 → ([𝑦 / 𝑥]𝜑 ↔ 𝜑))
5		tfindes.1	. 2 ⊢ [∅ / 𝑥]𝜑
6		nfv 1792	. . . 4 ⊢ Ⅎ𝑥 𝑧 ∈ On
7		nfsbc1v 3311	. . . . 5 ⊢ Ⅎ𝑥[𝑧 / 𝑥]𝜑
8		nfsbc1v 3311	. . . . 5 ⊢ Ⅎ𝑥[suc 𝑧 / 𝑥]𝜑
9	7, 8	nfim 2056	. . . 4 ⊢ Ⅎ𝑥([𝑧 / 𝑥]𝜑 → [suc 𝑧 / 𝑥]𝜑)
10	6, 9	nfim 2056	. . 3 ⊢ Ⅎ𝑥(𝑧 ∈ On → ([𝑧 / 𝑥]𝜑 → [suc 𝑧 / 𝑥]𝜑))
11		eleq1 2571	. . . 4 ⊢ (𝑥 = 𝑧 → (𝑥 ∈ On ↔ 𝑧 ∈ On))
12		sbceq1a 3302	. . . . 5 ⊢ (𝑥 = 𝑧 → (𝜑 ↔ [𝑧 / 𝑥]𝜑))
13		suceq 5539	. . . . . 6 ⊢ (𝑥 = 𝑧 → suc 𝑥 = suc 𝑧)
14	13	sbceq1d 3296	. . . . 5 ⊢ (𝑥 = 𝑧 → ([suc 𝑥 / 𝑥]𝜑 ↔ [suc 𝑧 / 𝑥]𝜑))
15	12, 14	imbi12d 329	. . . 4 ⊢ (𝑥 = 𝑧 → ((𝜑 → [suc 𝑥 / 𝑥]𝜑) ↔ ([𝑧 / 𝑥]𝜑 → [suc 𝑧 / 𝑥]𝜑)))
16	11, 15	imbi12d 329	. . 3 ⊢ (𝑥 = 𝑧 → ((𝑥 ∈ On → (𝜑 → [suc 𝑥 / 𝑥]𝜑)) ↔ (𝑧 ∈ On → ([𝑧 / 𝑥]𝜑 → [suc 𝑧 / 𝑥]𝜑))))
17		tfindes.2	. . 3 ⊢ (𝑥 ∈ On → (𝜑 → [suc 𝑥 / 𝑥]𝜑))
18	10, 16, 17	chvar 2153	. 2 ⊢ (𝑧 ∈ On → ([𝑧 / 𝑥]𝜑 → [suc 𝑧 / 𝑥]𝜑))
19		cbvralsv 3051	. . . 4 ⊢ (∀𝑥 ∈ 𝑦 𝜑 ↔ ∀𝑧 ∈ 𝑦 [𝑧 / 𝑥]𝜑)
20		sbsbc 3295	. . . . 5 ⊢ ([𝑧 / 𝑥]𝜑 ↔ [𝑧 / 𝑥]𝜑)
21	20	ralbii 2858	. . . 4 ⊢ (∀𝑧 ∈ 𝑦 [𝑧 / 𝑥]𝜑 ↔ ∀𝑧 ∈ 𝑦 [𝑧 / 𝑥]𝜑)
22	19, 21	bitri 259	. . 3 ⊢ (∀𝑥 ∈ 𝑦 𝜑 ↔ ∀𝑧 ∈ 𝑦 [𝑧 / 𝑥]𝜑)
23		tfindes.3	. . 3 ⊢ (Lim 𝑦 → (∀𝑥 ∈ 𝑦 𝜑 → [𝑦 / 𝑥]𝜑))
24	22, 23	syl5bir 228	. 2 ⊢ (Lim 𝑦 → (∀𝑧 ∈ 𝑦 [𝑧 / 𝑥]𝜑 → [𝑦 / 𝑥]𝜑))
25	1, 2, 3, 4, 5, 18, 24	tfinds 6763	1 ⊢ (𝑥 ∈ On → 𝜑)

Syntax hints:   → wi 4  [wsb 1828   ∈ wcel 1937  ∀wral 2791  [wsbc 3291  ∅c0 3757  Oncon0 5474  Lim wlim 5475  suc csuc 5476

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1698  ax-4 1711  ax-5 1789  ax-6 1836  ax-7 1883  ax-8 1939  ax-9 1946  ax-10 1965  ax-11 1970  ax-12 1983  ax-13 2137  ax-ext 2485  ax-sep 4558  ax-nul 4567  ax-pr 4680  ax-un 6659

This theorem depends on definitions:  df-bi 192  df-or 379  df-an 380  df-3or 1022  df-3an 1023  df-tru 1471  df-ex 1693  df-nf 1697  df-sb 1829  df-eu 2357  df-mo 2358  df-clab 2492  df-cleq 2498  df-clel 2501  df-nfc 2635  df-ne 2677  df-ral 2796  df-rex 2797  df-rab 2800  df-v 3068  df-sbc 3292  df-dif 3429  df-un 3431  df-in 3433  df-ss 3440  df-pss 3442  df-nul 3758  df-if 3909  df-pw 3980  df-sn 3996  df-pr 3998  df-tp 4000  df-op 4002  df-uni 4229  df-br 4435  df-opab 4494  df-tr 4531  df-eprel 4791  df-po 4801  df-so 4802  df-fr 4839  df-we 4841  df-ord 5477  df-on 5478  df-lim 5479  df-suc 5480

This theorem is referenced by:  tfinds2  6767