Theorem tfis 2245

Description: Transfinite Induction Schema. If all ordinal numbers less than a given number x have a property (induction hypothesis), then all ordinal numbers have the property (conclusion). Exercise 25 of [Enderton] p. 200.

Hypothesis

Ref	Expression
tfis.1	⊢ (x ∈ On → (∀y ∈ x [y / x]φ → φ))

Assertion

Ref	Expression
tfis	⊢ (x ∈ On → φ)

Distinct variable group(s):   φ,y   x,y

Proof of Theorem tfis

Step	Hyp	Ref	Expression
1		ssrab 1556	. . . . 5 ⊢ {x ∈ On∣φ} ⊆ On
2		ax-17 925	. . . . . . . . . . 11 ⊢ (z ∈ On → ∀x z ∈ On)
3		ax-17 925	. . . . . . . . . . . . 13 ⊢ (y ∈ z → ∀x y ∈ z)
4		hbs1 986	. . . . . . . . . . . . 13 ⊢ ([y / x]φ → ∀x[y / x]φ)
5	3, 4	hbral 1236	. . . . . . . . . . . 12 ⊢ (∀y ∈ z [y / x]φ → ∀x∀y ∈ z [y / x]φ)
6		hbs1 986	. . . . . . . . . . . 12 ⊢ ([z / x]φ → ∀x[z / x]φ)
7	5, 6	hbim 702	. . . . . . . . . . 11 ⊢ ((∀y ∈ z [y / x]φ → [z / x]φ) → ∀x(∀y ∈ z [y / x]φ → [z / x]φ))
8	2, 7	hbim 702	. . . . . . . . . 10 ⊢ ((z ∈ On → (∀y ∈ z [y / x]φ → [z / x]φ)) → ∀x(z ∈ On → (∀y ∈ z [y / x]φ → [z / x]φ)))
9		eleq1 1149	. . . . . . . . . . 11 ⊢ (x = z → (x ∈ On ↔ z ∈ On))
10		raleq 1324	. . . . . . . . . . . 12 ⊢ (x = z → (∀y ∈ x [y / x]φ ↔ ∀y ∈ z [y / x]φ))
11		sbequ12 865	. . . . . . . . . . . 12 ⊢ (x = z → (φ ↔ [z / x]φ))
12	10, 11	imbi12d 474	. . . . . . . . . . 11 ⊢ (x = z → ((∀y ∈ x [y / x]φ → φ) ↔ (∀y ∈ z [y / x]φ → [z / x]φ)))
13	9, 12	imbi12d 474	. . . . . . . . . 10 ⊢ (x = z → ((x ∈ On → (∀y ∈ x [y / x]φ → φ)) ↔ (z ∈ On → (∀y ∈ z [y / x]φ → [z / x]φ))))
14		tfis.1	. . . . . . . . . 10 ⊢ (x ∈ On → (∀y ∈ x [y / x]φ → φ))
15	8, 13, 14	chv2 850	. . . . . . . . 9 ⊢ (z ∈ On → (∀y ∈ z [y / x]φ → [z / x]φ))
16		dfss3 1498	. . . . . . . . . 10 ⊢ (z ⊆ {x ∈ On∣φ} ↔ ∀y ∈ z y ∈ {x ∈ On∣φ})
17	2	elrabsf 1456	. . . . . . . . . . . 12 ⊢ (y ∈ {x ∈ On∣φ} ↔ (y ∈ On ∧ [y / x]φ))
18	17	pm3.27bd 263	. . . . . . . . . . 11 ⊢ (y ∈ {x ∈ On∣φ} → [y / x]φ)
19	18	r19.20si 1254	. . . . . . . . . 10 ⊢ (∀y ∈ z y ∈ {x ∈ On∣φ} → ∀y ∈ z [y / x]φ)
20	16, 19	sylbi 174	. . . . . . . . 9 ⊢ (z ⊆ {x ∈ On∣φ} → ∀y ∈ z [y / x]φ)
21	15, 20	syl5 22	. . . . . . . 8 ⊢ (z ∈ On → (z ⊆ {x ∈ On∣φ} → [z / x]φ))
22	21	anc2li 250	. . . . . . 7 ⊢ (z ∈ On → (z ⊆ {x ∈ On∣φ} → (z ∈ On ∧ [z / x]φ)))
23	2	elrabsf 1456	. . . . . . 7 ⊢ (z ∈ {x ∈ On∣φ} ↔ (z ∈ On ∧ [z / x]φ))
24	22, 23	syl6ibr 186	. . . . . 6 ⊢ (z ∈ On → (z ⊆ {x ∈ On∣φ} → z ∈ {x ∈ On∣φ}))
25	24	rgen 1247	. . . . 5 ⊢ ∀z ∈ On (z ⊆ {x ∈ On∣φ} → z ∈ {x ∈ On∣φ})
26		tfi 2244	. . . . 5 ⊢ (({x ∈ On∣φ} ⊆ On ∧ ∀z ∈ On (z ⊆ {x ∈ On∣φ} → z ∈ {x ∈ On∣φ})) → {x ∈ On∣φ} = On)
27	1, 25, 26	mp2an 520	. . . 4 ⊢ {x ∈ On∣φ} = On
28	27	cleqcomi 1105	. . 3 ⊢ On = {x ∈ On∣φ}
29	28	cleqrabi 1347	. 2 ⊢ (x ∈ On ↔ (x ∈ On ∧ φ))
30	29	pm3.27bd 263	1 ⊢ (x ∈ On → φ)

Syntax hints:   → wi 2   ∧ wa 196   = weq 797   ∈ wel 803  [wsb 852   = wceq 1091   ∈ wcel 1092  ∀wral 1201  {crab 1204   ⊆ wss 1487  Oncon0 2199

This theorem is referenced by:  tfis2f 2246

This theorem was proved from axioms:  ax-1 3  ax-2 4  ax-3 5  ax-mp 6  ax-4 673  ax-5 674  ax-6 675  ax-7 676  ax-gen 677  ax-8 798  ax-9 799  ax-10 800  ax-11 801  ax-12 802  ax-13 804  ax-14 805  ax-16 922  ax-17 925  ax-ext 1074  ax-rep 1075  ax-un 1076  ax-pow 1077

This theorem depends on definitions:  df-bi 128  df-or 197  df-an 198  df-3or 582  df-3an 583  df-ex 679  df-sb 853  df-clab 1093  df-cleq 1097  df-clel 1099  df-ral 1205  df-rex 1206  df-rab 1208  df-v 1349  df-sbc 1441  df-dif 1489  df-un 1490  df-in 1491  df-ss 1492  df-nul 1708  df-pw 1799  df-sn 1811  df-pr 1812  df-tp 1814  df-op 1815  df-uni 1920  df-tr 2042  df-br 2063  df-opab 2098  df-eprel 2122  df-po 2128  df-so 2138  df-fr 2169  df-we 2186  df-ord 2202  df-on 2203

metamath.org