Theorem tfrlem9 5873

Description: Lemma for transfinite recursion. Here we compute the value of recs (the union of all acceptable functions). (Contributed by NM, 17-Aug-1994.)

Hypothesis

Ref	Expression
tfrlem.1	⊢ A = {f ∣ ∃x ∈ On (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)))}

Assertion

Ref	Expression
tfrlem9	⊢ (B ∈ dom recs(𝐹) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))

Distinct variable groups:   x,f,y,B   f,𝐹,x,y

Allowed substitution hints:   A(x,y,f)

Proof of Theorem tfrlem9

Dummy variable z is distinct from all other variables.

Step	Hyp	Ref	Expression
1		eldm2g 4473	. . 3 ⊢ (B ∈ dom recs(𝐹) → (B ∈ dom recs(𝐹) ↔ ∃z⟨B, z⟩ ∈ recs(𝐹)))
2	1	ibi 165	. 2 ⊢ (B ∈ dom recs(𝐹) → ∃z⟨B, z⟩ ∈ recs(𝐹))
3		df-recs 5858	. . . . . 6 ⊢ recs(𝐹) = ∪ {f ∣ ∃x ∈ On (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)))}
4	3	eleq2i 2101	. . . . 5 ⊢ (⟨B, z⟩ ∈ recs(𝐹) ↔ ⟨B, z⟩ ∈ ∪ {f ∣ ∃x ∈ On (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)))})
5		eluniab 3582	. . . . 5 ⊢ (⟨B, z⟩ ∈ ∪ {f ∣ ∃x ∈ On (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)))} ↔ ∃f(⟨B, z⟩ ∈ f ∧ ∃x ∈ On (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)))))
6	4, 5	bitri 173	. . . 4 ⊢ (⟨B, z⟩ ∈ recs(𝐹) ↔ ∃f(⟨B, z⟩ ∈ f ∧ ∃x ∈ On (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)))))
7		fnop 4943	. . . . . . . . . . . . . 14 ⊢ ((f Fn x ∧ ⟨B, z⟩ ∈ f) → B ∈ x)
8		rspe 2364	. . . . . . . . . . . . . . . 16 ⊢ ((x ∈ On ∧ (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)))) → ∃x ∈ On (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y))))
9		tfrlem.1	. . . . . . . . . . . . . . . . . 18 ⊢ A = {f ∣ ∃x ∈ On (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)))}
10	9	abeq2i 2145	. . . . . . . . . . . . . . . . 17 ⊢ (f ∈ A ↔ ∃x ∈ On (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y))))
11		elssuni 3598	. . . . . . . . . . . . . . . . . 18 ⊢ (f ∈ A → f ⊆ ∪ A)
12	9	recsfval 5869	. . . . . . . . . . . . . . . . . 18 ⊢ recs(𝐹) = ∪ A
13	11, 12	syl6sseqr 2986	. . . . . . . . . . . . . . . . 17 ⊢ (f ∈ A → f ⊆ recs(𝐹))
14	10, 13	sylbir 125	. . . . . . . . . . . . . . . 16 ⊢ (∃x ∈ On (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y))) → f ⊆ recs(𝐹))
15	8, 14	syl 14	. . . . . . . . . . . . . . 15 ⊢ ((x ∈ On ∧ (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)))) → f ⊆ recs(𝐹))
16		fveq2 5119	. . . . . . . . . . . . . . . . . . . 20 ⊢ (y = B → (f‘y) = (f‘B))
17		reseq2 4549	. . . . . . . . . . . . . . . . . . . . 21 ⊢ (y = B → (f ↾ y) = (f ↾ B))
18	17	fveq2d 5123	. . . . . . . . . . . . . . . . . . . 20 ⊢ (y = B → (𝐹‘(f ↾ y)) = (𝐹‘(f ↾ B)))
19	16, 18	eqeq12d 2051	. . . . . . . . . . . . . . . . . . 19 ⊢ (y = B → ((f‘y) = (𝐹‘(f ↾ y)) ↔ (f‘B) = (𝐹‘(f ↾ B))))
20	19	rspcv 2646	. . . . . . . . . . . . . . . . . 18 ⊢ (B ∈ x → (∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)) → (f‘B) = (𝐹‘(f ↾ B))))
21		fndm 4939	. . . . . . . . . . . . . . . . . . . . 21 ⊢ (f Fn x → dom f = x)
22	21	eleq2d 2104	. . . . . . . . . . . . . . . . . . . 20 ⊢ (f Fn x → (B ∈ dom f ↔ B ∈ x))
23	9	tfrlem7 5871	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ⊢ Fun recs(𝐹)
24		funssfv 5140	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ⊢ ((Fun recs(𝐹) ∧ f ⊆ recs(𝐹) ∧ B ∈ dom f) → (recs(𝐹)‘B) = (f‘B))
25	23, 24	mp3an1 1218	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 ⊢ ((f ⊆ recs(𝐹) ∧ B ∈ dom f) → (recs(𝐹)‘B) = (f‘B))
26	25	adantrl 447	. . . . . . . . . . . . . . . . . . . . . . . . . 26 ⊢ ((f ⊆ recs(𝐹) ∧ ((f Fn x ∧ x ∈ On) ∧ B ∈ dom f)) → (recs(𝐹)‘B) = (f‘B))
27	21	eleq1d 2103	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ (f Fn x → (dom f ∈ On ↔ x ∈ On))
28		onelss 4089	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ (dom f ∈ On → (B ∈ dom f → B ⊆ dom f))
29	27, 28	syl6bir 153	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ⊢ (f Fn x → (x ∈ On → (B ∈ dom f → B ⊆ dom f)))
30	29	imp31 243	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 ⊢ (((f Fn x ∧ x ∈ On) ∧ B ∈ dom f) → B ⊆ dom f)
31		fun2ssres 4884	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ⊢ ((Fun recs(𝐹) ∧ f ⊆ recs(𝐹) ∧ B ⊆ dom f) → (recs(𝐹) ↾ B) = (f ↾ B))
32	31	fveq2d 5123	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ⊢ ((Fun recs(𝐹) ∧ f ⊆ recs(𝐹) ∧ B ⊆ dom f) → (𝐹‘(recs(𝐹) ↾ B)) = (𝐹‘(f ↾ B)))
33	23, 32	mp3an1 1218	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 ⊢ ((f ⊆ recs(𝐹) ∧ B ⊆ dom f) → (𝐹‘(recs(𝐹) ↾ B)) = (𝐹‘(f ↾ B)))
34	30, 33	sylan2 270	. . . . . . . . . . . . . . . . . . . . . . . . . 26 ⊢ ((f ⊆ recs(𝐹) ∧ ((f Fn x ∧ x ∈ On) ∧ B ∈ dom f)) → (𝐹‘(recs(𝐹) ↾ B)) = (𝐹‘(f ↾ B)))
35	26, 34	eqeq12d 2051	. . . . . . . . . . . . . . . . . . . . . . . . 25 ⊢ ((f ⊆ recs(𝐹) ∧ ((f Fn x ∧ x ∈ On) ∧ B ∈ dom f)) → ((recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)) ↔ (f‘B) = (𝐹‘(f ↾ B))))
36	35	exbiri 364	. . . . . . . . . . . . . . . . . . . . . . . 24 ⊢ (f ⊆ recs(𝐹) → (((f Fn x ∧ x ∈ On) ∧ B ∈ dom f) → ((f‘B) = (𝐹‘(f ↾ B)) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))))
37	36	com3l 75	. . . . . . . . . . . . . . . . . . . . . . 23 ⊢ (((f Fn x ∧ x ∈ On) ∧ B ∈ dom f) → ((f‘B) = (𝐹‘(f ↾ B)) → (f ⊆ recs(𝐹) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))))
38	37	exp31 346	. . . . . . . . . . . . . . . . . . . . . 22 ⊢ (f Fn x → (x ∈ On → (B ∈ dom f → ((f‘B) = (𝐹‘(f ↾ B)) → (f ⊆ recs(𝐹) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))))))
39	38	com34 77	. . . . . . . . . . . . . . . . . . . . 21 ⊢ (f Fn x → (x ∈ On → ((f‘B) = (𝐹‘(f ↾ B)) → (B ∈ dom f → (f ⊆ recs(𝐹) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))))))
40	39	com24 81	. . . . . . . . . . . . . . . . . . . 20 ⊢ (f Fn x → (B ∈ dom f → ((f‘B) = (𝐹‘(f ↾ B)) → (x ∈ On → (f ⊆ recs(𝐹) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))))))
41	22, 40	sylbird 159	. . . . . . . . . . . . . . . . . . 19 ⊢ (f Fn x → (B ∈ x → ((f‘B) = (𝐹‘(f ↾ B)) → (x ∈ On → (f ⊆ recs(𝐹) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))))))
42	41	com3l 75	. . . . . . . . . . . . . . . . . 18 ⊢ (B ∈ x → ((f‘B) = (𝐹‘(f ↾ B)) → (f Fn x → (x ∈ On → (f ⊆ recs(𝐹) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))))))
43	20, 42	syld 40	. . . . . . . . . . . . . . . . 17 ⊢ (B ∈ x → (∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)) → (f Fn x → (x ∈ On → (f ⊆ recs(𝐹) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))))))
44	43	com24 81	. . . . . . . . . . . . . . . 16 ⊢ (B ∈ x → (x ∈ On → (f Fn x → (∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)) → (f ⊆ recs(𝐹) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))))))
45	44	imp4d 334	. . . . . . . . . . . . . . 15 ⊢ (B ∈ x → ((x ∈ On ∧ (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)))) → (f ⊆ recs(𝐹) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))))
46	15, 45	mpdi 38	. . . . . . . . . . . . . 14 ⊢ (B ∈ x → ((x ∈ On ∧ (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)))) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B))))
47	7, 46	syl 14	. . . . . . . . . . . . 13 ⊢ ((f Fn x ∧ ⟨B, z⟩ ∈ f) → ((x ∈ On ∧ (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)))) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B))))
48	47	exp4d 351	. . . . . . . . . . . 12 ⊢ ((f Fn x ∧ ⟨B, z⟩ ∈ f) → (x ∈ On → (f Fn x → (∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B))))))
49	48	ex 108	. . . . . . . . . . 11 ⊢ (f Fn x → (⟨B, z⟩ ∈ f → (x ∈ On → (f Fn x → (∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))))))
50	49	com4r 80	. . . . . . . . . 10 ⊢ (f Fn x → (f Fn x → (⟨B, z⟩ ∈ f → (x ∈ On → (∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))))))
51	50	pm2.43i 43	. . . . . . . . 9 ⊢ (f Fn x → (⟨B, z⟩ ∈ f → (x ∈ On → (∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B))))))
52	51	com3l 75	. . . . . . . 8 ⊢ (⟨B, z⟩ ∈ f → (x ∈ On → (f Fn x → (∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B))))))
53	52	imp4a 331	. . . . . . 7 ⊢ (⟨B, z⟩ ∈ f → (x ∈ On → ((f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y))) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))))
54	53	rexlimdv 2426	. . . . . 6 ⊢ (⟨B, z⟩ ∈ f → (∃x ∈ On (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y))) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B))))
55	54	imp 115	. . . . 5 ⊢ ((⟨B, z⟩ ∈ f ∧ ∃x ∈ On (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)))) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))
56	55	exlimiv 1486	. . . 4 ⊢ (∃f(⟨B, z⟩ ∈ f ∧ ∃x ∈ On (f Fn x ∧ ∀y ∈ x (f‘y) = (𝐹‘(f ↾ y)))) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))
57	6, 56	sylbi 114	. . 3 ⊢ (⟨B, z⟩ ∈ recs(𝐹) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))
58	57	exlimiv 1486	. 2 ⊢ (∃z⟨B, z⟩ ∈ recs(𝐹) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))
59	2, 58	syl 14	1 ⊢ (B ∈ dom recs(𝐹) → (recs(𝐹)‘B) = (𝐹‘(recs(𝐹) ↾ B)))

Syntax hints:   → wi 4   ∧ wa 97   ∧ w3a 884   = wceq 1242  ∃wex 1378   ∈ wcel 1390  {cab 2023  ∀wral 2300  ∃wrex 2301   ⊆ wss 2911  ⟨cop 3369  ∪ cuni 3570  Oncon0 4065  dom cdm 4287   ↾ cres 4289  Fun wfun 4838   Fn wfn 4839  ‘cfv 4844  recscrecs 5857

This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 99  ax-ia2 100  ax-ia3 101  ax-io 629  ax-5 1333  ax-7 1334  ax-gen 1335  ax-ie1 1379  ax-ie2 1380  ax-8 1392  ax-10 1393  ax-11 1394  ax-i12 1395  ax-bnd 1396  ax-4 1397  ax-14 1402  ax-17 1416  ax-i9 1420  ax-ial 1424  ax-i5r 1425  ax-ext 2019  ax-sep 3865  ax-pow 3917  ax-pr 3934  ax-setind 4219

This theorem depends on definitions:  df-bi 110  df-3an 886  df-tru 1245  df-nf 1347  df-sb 1643  df-eu 1900  df-mo 1901  df-clab 2024  df-cleq 2030  df-clel 2033  df-nfc 2164  df-ral 2305  df-rex 2306  df-rab 2309  df-v 2553  df-sbc 2759  df-csb 2847  df-un 2916  df-in 2918  df-ss 2925  df-pw 3352  df-sn 3372  df-pr 3373  df-op 3375  df-uni 3571  df-iun 3649  df-br 3755  df-opab 3809  df-mpt 3810  df-tr 3845  df-id 4020  df-iord 4068  df-on 4070  df-xp 4293  df-rel 4294  df-cnv 4295  df-co 4296  df-dm 4297  df-res 4299  df-iota 4809  df-fun 4846  df-fn 4847  df-fv 4852  df-recs 5858

This theorem is referenced by:  tfr2a  5874  tfrlemiubacc  5882