Theorem tfindsg 7569

Description: Transfinite Induction (inference schema), using implicit substitutions. The first four hypotheses establish the substitutions we need. The last three are the basis, the induction step for successors, and the induction step for limit ordinals. The basis of this version is an arbitrary ordinal 𝐵 instead of zero. Remark in [TakeutiZaring] p. 57. (Contributed by NM, 5-Mar-2004.)

Hypotheses

Ref	Expression
tfindsg.1	⊢ (𝑥 = 𝐵 → (𝜑 ↔ 𝜓))
tfindsg.2	⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜒))
tfindsg.3	⊢ (𝑥 = suc 𝑦 → (𝜑 ↔ 𝜃))
tfindsg.4	⊢ (𝑥 = 𝐴 → (𝜑 ↔ 𝜏))
tfindsg.5	⊢ (𝐵 ∈ On → 𝜓)
tfindsg.6	⊢ (((𝑦 ∈ On ∧ 𝐵 ∈ On) ∧ 𝐵 ⊆ 𝑦) → (𝜒 → 𝜃))
tfindsg.7	⊢ (((Lim 𝑥 ∧ 𝐵 ∈ On) ∧ 𝐵 ⊆ 𝑥) → (∀𝑦 ∈ 𝑥 (𝐵 ⊆ 𝑦 → 𝜒) → 𝜑))

Assertion

Ref	Expression
tfindsg	⊢ (((𝐴 ∈ On ∧ 𝐵 ∈ On) ∧ 𝐵 ⊆ 𝐴) → 𝜏)

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

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

Proof of Theorem tfindsg

Step	Hyp	Ref	Expression
1		sseq2 3992	. . . . . . 7 ⊢ (𝑥 = ∅ → (𝐵 ⊆ 𝑥 ↔ 𝐵 ⊆ ∅))
2	1	adantl 484	. . . . . 6 ⊢ ((𝐵 = ∅ ∧ 𝑥 = ∅) → (𝐵 ⊆ 𝑥 ↔ 𝐵 ⊆ ∅))
3		eqeq2 2833	. . . . . . . 8 ⊢ (𝐵 = ∅ → (𝑥 = 𝐵 ↔ 𝑥 = ∅))
4		tfindsg.1	. . . . . . . 8 ⊢ (𝑥 = 𝐵 → (𝜑 ↔ 𝜓))
5	3, 4	syl6bir 256	. . . . . . 7 ⊢ (𝐵 = ∅ → (𝑥 = ∅ → (𝜑 ↔ 𝜓)))
6	5	imp 409	. . . . . 6 ⊢ ((𝐵 = ∅ ∧ 𝑥 = ∅) → (𝜑 ↔ 𝜓))
7	2, 6	imbi12d 347	. . . . 5 ⊢ ((𝐵 = ∅ ∧ 𝑥 = ∅) → ((𝐵 ⊆ 𝑥 → 𝜑) ↔ (𝐵 ⊆ ∅ → 𝜓)))
8	1	imbi1d 344	. . . . . 6 ⊢ (𝑥 = ∅ → ((𝐵 ⊆ 𝑥 → 𝜑) ↔ (𝐵 ⊆ ∅ → 𝜑)))
9		ss0 4351	. . . . . . . . 9 ⊢ (𝐵 ⊆ ∅ → 𝐵 = ∅)
10	9	con3i 157	. . . . . . . 8 ⊢ (¬ 𝐵 = ∅ → ¬ 𝐵 ⊆ ∅)
11	10	pm2.21d 121	. . . . . . 7 ⊢ (¬ 𝐵 = ∅ → (𝐵 ⊆ ∅ → (𝜑 ↔ 𝜓)))
12	11	pm5.74d 275	. . . . . 6 ⊢ (¬ 𝐵 = ∅ → ((𝐵 ⊆ ∅ → 𝜑) ↔ (𝐵 ⊆ ∅ → 𝜓)))
13	8, 12	sylan9bbr 513	. . . . 5 ⊢ ((¬ 𝐵 = ∅ ∧ 𝑥 = ∅) → ((𝐵 ⊆ 𝑥 → 𝜑) ↔ (𝐵 ⊆ ∅ → 𝜓)))
14	7, 13	pm2.61ian 810	. . . 4 ⊢ (𝑥 = ∅ → ((𝐵 ⊆ 𝑥 → 𝜑) ↔ (𝐵 ⊆ ∅ → 𝜓)))
15	14	imbi2d 343	. . 3 ⊢ (𝑥 = ∅ → ((𝐵 ∈ On → (𝐵 ⊆ 𝑥 → 𝜑)) ↔ (𝐵 ∈ On → (𝐵 ⊆ ∅ → 𝜓))))
16		sseq2 3992	. . . . 5 ⊢ (𝑥 = 𝑦 → (𝐵 ⊆ 𝑥 ↔ 𝐵 ⊆ 𝑦))
17		tfindsg.2	. . . . 5 ⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜒))
18	16, 17	imbi12d 347	. . . 4 ⊢ (𝑥 = 𝑦 → ((𝐵 ⊆ 𝑥 → 𝜑) ↔ (𝐵 ⊆ 𝑦 → 𝜒)))
19	18	imbi2d 343	. . 3 ⊢ (𝑥 = 𝑦 → ((𝐵 ∈ On → (𝐵 ⊆ 𝑥 → 𝜑)) ↔ (𝐵 ∈ On → (𝐵 ⊆ 𝑦 → 𝜒))))
20		sseq2 3992	. . . . 5 ⊢ (𝑥 = suc 𝑦 → (𝐵 ⊆ 𝑥 ↔ 𝐵 ⊆ suc 𝑦))
21		tfindsg.3	. . . . 5 ⊢ (𝑥 = suc 𝑦 → (𝜑 ↔ 𝜃))
22	20, 21	imbi12d 347	. . . 4 ⊢ (𝑥 = suc 𝑦 → ((𝐵 ⊆ 𝑥 → 𝜑) ↔ (𝐵 ⊆ suc 𝑦 → 𝜃)))
23	22	imbi2d 343	. . 3 ⊢ (𝑥 = suc 𝑦 → ((𝐵 ∈ On → (𝐵 ⊆ 𝑥 → 𝜑)) ↔ (𝐵 ∈ On → (𝐵 ⊆ suc 𝑦 → 𝜃))))
24		sseq2 3992	. . . . 5 ⊢ (𝑥 = 𝐴 → (𝐵 ⊆ 𝑥 ↔ 𝐵 ⊆ 𝐴))
25		tfindsg.4	. . . . 5 ⊢ (𝑥 = 𝐴 → (𝜑 ↔ 𝜏))
26	24, 25	imbi12d 347	. . . 4 ⊢ (𝑥 = 𝐴 → ((𝐵 ⊆ 𝑥 → 𝜑) ↔ (𝐵 ⊆ 𝐴 → 𝜏)))
27	26	imbi2d 343	. . 3 ⊢ (𝑥 = 𝐴 → ((𝐵 ∈ On → (𝐵 ⊆ 𝑥 → 𝜑)) ↔ (𝐵 ∈ On → (𝐵 ⊆ 𝐴 → 𝜏))))
28		tfindsg.5	. . . 4 ⊢ (𝐵 ∈ On → 𝜓)
29	28	a1d 25	. . 3 ⊢ (𝐵 ∈ On → (𝐵 ⊆ ∅ → 𝜓))
30		vex 3497	. . . . . . . . . . . . . 14 ⊢ 𝑦 ∈ V
31	30	sucex 7520	. . . . . . . . . . . . 13 ⊢ suc 𝑦 ∈ V
32	31	eqvinc 3641	. . . . . . . . . . . 12 ⊢ (suc 𝑦 = 𝐵 ↔ ∃𝑥(𝑥 = suc 𝑦 ∧ 𝑥 = 𝐵))
33	28, 4	syl5ibr 248	. . . . . . . . . . . . . 14 ⊢ (𝑥 = 𝐵 → (𝐵 ∈ On → 𝜑))
34	21	biimpd 231	. . . . . . . . . . . . . 14 ⊢ (𝑥 = suc 𝑦 → (𝜑 → 𝜃))
35	33, 34	sylan9r 511	. . . . . . . . . . . . 13 ⊢ ((𝑥 = suc 𝑦 ∧ 𝑥 = 𝐵) → (𝐵 ∈ On → 𝜃))
36	35	exlimiv 1927	. . . . . . . . . . . 12 ⊢ (∃𝑥(𝑥 = suc 𝑦 ∧ 𝑥 = 𝐵) → (𝐵 ∈ On → 𝜃))
37	32, 36	sylbi 219	. . . . . . . . . . 11 ⊢ (suc 𝑦 = 𝐵 → (𝐵 ∈ On → 𝜃))
38	37	eqcoms 2829	. . . . . . . . . 10 ⊢ (𝐵 = suc 𝑦 → (𝐵 ∈ On → 𝜃))
39	38	imim2i 16	. . . . . . . . 9 ⊢ ((𝐵 ⊆ suc 𝑦 → 𝐵 = suc 𝑦) → (𝐵 ⊆ suc 𝑦 → (𝐵 ∈ On → 𝜃)))
40	39	a1d 25	. . . . . . . 8 ⊢ ((𝐵 ⊆ suc 𝑦 → 𝐵 = suc 𝑦) → ((𝐵 ⊆ 𝑦 → 𝜒) → (𝐵 ⊆ suc 𝑦 → (𝐵 ∈ On → 𝜃))))
41	40	com4r 94	. . . . . . 7 ⊢ (𝐵 ∈ On → ((𝐵 ⊆ suc 𝑦 → 𝐵 = suc 𝑦) → ((𝐵 ⊆ 𝑦 → 𝜒) → (𝐵 ⊆ suc 𝑦 → 𝜃))))
42	41	adantl 484	. . . . . 6 ⊢ ((𝑦 ∈ On ∧ 𝐵 ∈ On) → ((𝐵 ⊆ suc 𝑦 → 𝐵 = suc 𝑦) → ((𝐵 ⊆ 𝑦 → 𝜒) → (𝐵 ⊆ suc 𝑦 → 𝜃))))
43		df-ne 3017	. . . . . . . . 9 ⊢ (𝐵 ≠ suc 𝑦 ↔ ¬ 𝐵 = suc 𝑦)
44	43	anbi2i 624	. . . . . . . 8 ⊢ ((𝐵 ⊆ suc 𝑦 ∧ 𝐵 ≠ suc 𝑦) ↔ (𝐵 ⊆ suc 𝑦 ∧ ¬ 𝐵 = suc 𝑦))
45		annim 406	. . . . . . . 8 ⊢ ((𝐵 ⊆ suc 𝑦 ∧ ¬ 𝐵 = suc 𝑦) ↔ ¬ (𝐵 ⊆ suc 𝑦 → 𝐵 = suc 𝑦))
46	44, 45	bitri 277	. . . . . . 7 ⊢ ((𝐵 ⊆ suc 𝑦 ∧ 𝐵 ≠ suc 𝑦) ↔ ¬ (𝐵 ⊆ suc 𝑦 → 𝐵 = suc 𝑦))
47		onsssuc 6272	. . . . . . . . . 10 ⊢ ((𝐵 ∈ On ∧ 𝑦 ∈ On) → (𝐵 ⊆ 𝑦 ↔ 𝐵 ∈ suc 𝑦))
48		suceloni 7522	. . . . . . . . . . 11 ⊢ (𝑦 ∈ On → suc 𝑦 ∈ On)
49		onelpss 6225	. . . . . . . . . . 11 ⊢ ((𝐵 ∈ On ∧ suc 𝑦 ∈ On) → (𝐵 ∈ suc 𝑦 ↔ (𝐵 ⊆ suc 𝑦 ∧ 𝐵 ≠ suc 𝑦)))
50	48, 49	sylan2 594	. . . . . . . . . 10 ⊢ ((𝐵 ∈ On ∧ 𝑦 ∈ On) → (𝐵 ∈ suc 𝑦 ↔ (𝐵 ⊆ suc 𝑦 ∧ 𝐵 ≠ suc 𝑦)))
51	47, 50	bitrd 281	. . . . . . . . 9 ⊢ ((𝐵 ∈ On ∧ 𝑦 ∈ On) → (𝐵 ⊆ 𝑦 ↔ (𝐵 ⊆ suc 𝑦 ∧ 𝐵 ≠ suc 𝑦)))
52	51	ancoms 461	. . . . . . . 8 ⊢ ((𝑦 ∈ On ∧ 𝐵 ∈ On) → (𝐵 ⊆ 𝑦 ↔ (𝐵 ⊆ suc 𝑦 ∧ 𝐵 ≠ suc 𝑦)))
53		tfindsg.6	. . . . . . . . . . . 12 ⊢ (((𝑦 ∈ On ∧ 𝐵 ∈ On) ∧ 𝐵 ⊆ 𝑦) → (𝜒 → 𝜃))
54	53	ex 415	. . . . . . . . . . 11 ⊢ ((𝑦 ∈ On ∧ 𝐵 ∈ On) → (𝐵 ⊆ 𝑦 → (𝜒 → 𝜃)))
55	54	a1ddd 80	. . . . . . . . . 10 ⊢ ((𝑦 ∈ On ∧ 𝐵 ∈ On) → (𝐵 ⊆ 𝑦 → (𝜒 → (𝐵 ⊆ suc 𝑦 → 𝜃))))
56	55	a2d 29	. . . . . . . . 9 ⊢ ((𝑦 ∈ On ∧ 𝐵 ∈ On) → ((𝐵 ⊆ 𝑦 → 𝜒) → (𝐵 ⊆ 𝑦 → (𝐵 ⊆ suc 𝑦 → 𝜃))))
57	56	com23 86	. . . . . . . 8 ⊢ ((𝑦 ∈ On ∧ 𝐵 ∈ On) → (𝐵 ⊆ 𝑦 → ((𝐵 ⊆ 𝑦 → 𝜒) → (𝐵 ⊆ suc 𝑦 → 𝜃))))
58	52, 57	sylbird 262	. . . . . . 7 ⊢ ((𝑦 ∈ On ∧ 𝐵 ∈ On) → ((𝐵 ⊆ suc 𝑦 ∧ 𝐵 ≠ suc 𝑦) → ((𝐵 ⊆ 𝑦 → 𝜒) → (𝐵 ⊆ suc 𝑦 → 𝜃))))
59	46, 58	syl5bir 245	. . . . . 6 ⊢ ((𝑦 ∈ On ∧ 𝐵 ∈ On) → (¬ (𝐵 ⊆ suc 𝑦 → 𝐵 = suc 𝑦) → ((𝐵 ⊆ 𝑦 → 𝜒) → (𝐵 ⊆ suc 𝑦 → 𝜃))))
60	42, 59	pm2.61d 181	. . . . 5 ⊢ ((𝑦 ∈ On ∧ 𝐵 ∈ On) → ((𝐵 ⊆ 𝑦 → 𝜒) → (𝐵 ⊆ suc 𝑦 → 𝜃)))
61	60	ex 415	. . . 4 ⊢ (𝑦 ∈ On → (𝐵 ∈ On → ((𝐵 ⊆ 𝑦 → 𝜒) → (𝐵 ⊆ suc 𝑦 → 𝜃))))
62	61	a2d 29	. . 3 ⊢ (𝑦 ∈ On → ((𝐵 ∈ On → (𝐵 ⊆ 𝑦 → 𝜒)) → (𝐵 ∈ On → (𝐵 ⊆ suc 𝑦 → 𝜃))))
63		pm2.27 42	. . . . . . . . 9 ⊢ (𝐵 ∈ On → ((𝐵 ∈ On → (𝐵 ⊆ 𝑦 → 𝜒)) → (𝐵 ⊆ 𝑦 → 𝜒)))
64	63	ralimdv 3178	. . . . . . . 8 ⊢ (𝐵 ∈ On → (∀𝑦 ∈ 𝑥 (𝐵 ∈ On → (𝐵 ⊆ 𝑦 → 𝜒)) → ∀𝑦 ∈ 𝑥 (𝐵 ⊆ 𝑦 → 𝜒)))
65	64	ad2antlr 725	. . . . . . 7 ⊢ (((Lim 𝑥 ∧ 𝐵 ∈ On) ∧ 𝐵 ⊆ 𝑥) → (∀𝑦 ∈ 𝑥 (𝐵 ∈ On → (𝐵 ⊆ 𝑦 → 𝜒)) → ∀𝑦 ∈ 𝑥 (𝐵 ⊆ 𝑦 → 𝜒)))
66		tfindsg.7	. . . . . . 7 ⊢ (((Lim 𝑥 ∧ 𝐵 ∈ On) ∧ 𝐵 ⊆ 𝑥) → (∀𝑦 ∈ 𝑥 (𝐵 ⊆ 𝑦 → 𝜒) → 𝜑))
67	65, 66	syld 47	. . . . . 6 ⊢ (((Lim 𝑥 ∧ 𝐵 ∈ On) ∧ 𝐵 ⊆ 𝑥) → (∀𝑦 ∈ 𝑥 (𝐵 ∈ On → (𝐵 ⊆ 𝑦 → 𝜒)) → 𝜑))
68	67	exp31 422	. . . . 5 ⊢ (Lim 𝑥 → (𝐵 ∈ On → (𝐵 ⊆ 𝑥 → (∀𝑦 ∈ 𝑥 (𝐵 ∈ On → (𝐵 ⊆ 𝑦 → 𝜒)) → 𝜑))))
69	68	com3l 89	. . . 4 ⊢ (𝐵 ∈ On → (𝐵 ⊆ 𝑥 → (Lim 𝑥 → (∀𝑦 ∈ 𝑥 (𝐵 ∈ On → (𝐵 ⊆ 𝑦 → 𝜒)) → 𝜑))))
70	69	com4t 93	. . 3 ⊢ (Lim 𝑥 → (∀𝑦 ∈ 𝑥 (𝐵 ∈ On → (𝐵 ⊆ 𝑦 → 𝜒)) → (𝐵 ∈ On → (𝐵 ⊆ 𝑥 → 𝜑))))
71	15, 19, 23, 27, 29, 62, 70	tfinds 7568	. 2 ⊢ (𝐴 ∈ On → (𝐵 ∈ On → (𝐵 ⊆ 𝐴 → 𝜏)))
72	71	imp31 420	1 ⊢ (((𝐴 ∈ On ∧ 𝐵 ∈ On) ∧ 𝐵 ⊆ 𝐴) → 𝜏)

Syntax hints:  ¬ wn 3   → wi 4   ↔ wb 208   ∧ wa 398   = wceq 1533  ∃wex 1776   ∈ wcel 2110   ≠ wne 3016  ∀wral 3138   ⊆ wss 3935  ∅c0 4290  Oncon0 6185  Lim wlim 6186  suc csuc 6187

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1792  ax-4 1806  ax-5 1907  ax-6 1966  ax-7 2011  ax-8 2112  ax-9 2120  ax-10 2141  ax-11 2157  ax-12 2173  ax-ext 2793  ax-sep 5195  ax-nul 5202  ax-pr 5321  ax-un 7455

This theorem depends on definitions:  df-bi 209  df-an 399  df-or 844  df-3or 1084  df-3an 1085  df-tru 1536  df-ex 1777  df-nf 1781  df-sb 2066  df-mo 2618  df-eu 2650  df-clab 2800  df-cleq 2814  df-clel 2893  df-nfc 2963  df-ne 3017  df-ral 3143  df-rex 3144  df-rab 3147  df-v 3496  df-sbc 3772  df-dif 3938  df-un 3940  df-in 3942  df-ss 3951  df-pss 3953  df-nul 4291  df-if 4467  df-pw 4540  df-sn 4561  df-pr 4563  df-tp 4565  df-op 4567  df-uni 4832  df-br 5059  df-opab 5121  df-tr 5165  df-eprel 5459  df-po 5468  df-so 5469  df-fr 5508  df-we 5510  df-ord 6188  df-on 6189  df-lim 6190  df-suc 6191

This theorem is referenced by:  tfindsg2  7570  oaordi  8166  infensuc  8689  r1ordg  9201