MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  tfrlem9 Structured version   Visualization version   GIF version

Theorem tfrlem9 8344
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 𝐴 = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))}
Assertion
Ref Expression
tfrlem9 (𝐵 ∈ dom recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))
Distinct variable groups:   𝑥,𝑓,𝑦,𝐵   𝑓,𝐹,𝑥,𝑦
Allowed substitution hints:   𝐴(𝑥,𝑦,𝑓)

Proof of Theorem tfrlem9
Dummy variable 𝑧 is distinct from all other variables.
StepHypRef Expression
1 eldm2g 5868 . . 3 (𝐵 ∈ dom recs(𝐹) → (𝐵 ∈ dom recs(𝐹) ↔ ∃𝑧𝐵, 𝑧⟩ ∈ recs(𝐹)))
21ibi 269 . 2 (𝐵 ∈ dom recs(𝐹) → ∃𝑧𝐵, 𝑧⟩ ∈ recs(𝐹))
3 dfrecs3 8331 . . . . . 6 recs(𝐹) = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))}
43eleq2i 2848 . . . . 5 (⟨𝐵, 𝑧⟩ ∈ recs(𝐹) ↔ ⟨𝐵, 𝑧⟩ ∈ {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))})
5 eluniab 4873 . . . . 5 (⟨𝐵, 𝑧⟩ ∈ {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))} ↔ ∃𝑓(⟨𝐵, 𝑧⟩ ∈ 𝑓 ∧ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
64, 5bitri 277 . . . 4 (⟨𝐵, 𝑧⟩ ∈ recs(𝐹) ↔ ∃𝑓(⟨𝐵, 𝑧⟩ ∈ 𝑓 ∧ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
7 fnop 6619 . . . . . . . . . . . . . 14 ((𝑓 Fn 𝑥 ∧ ⟨𝐵, 𝑧⟩ ∈ 𝑓) → 𝐵𝑥)
8 rspe 3246 . . . . . . . . . . . . . . . 16 ((𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
9 tfrlem.1 . . . . . . . . . . . . . . . . . 18 𝐴 = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))}
109eqabri 2898 . . . . . . . . . . . . . . . . 17 (𝑓𝐴 ↔ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
11 elssuni 4891 . . . . . . . . . . . . . . . . . 18 (𝑓𝐴𝑓 𝐴)
129recsfval 8339 . . . . . . . . . . . . . . . . . 18 recs(𝐹) = 𝐴
1311, 12sseqtrrdi 3972 . . . . . . . . . . . . . . . . 17 (𝑓𝐴𝑓 ⊆ recs(𝐹))
1410, 13sylbir 237 . . . . . . . . . . . . . . . 16 (∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))) → 𝑓 ⊆ recs(𝐹))
158, 14syl 17 . . . . . . . . . . . . . . 15 ((𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → 𝑓 ⊆ recs(𝐹))
16 fveq2 6856 . . . . . . . . . . . . . . . . . . . 20 (𝑦 = 𝐵 → (𝑓𝑦) = (𝑓𝐵))
17 reseq2 5953 . . . . . . . . . . . . . . . . . . . . 21 (𝑦 = 𝐵 → (𝑓𝑦) = (𝑓𝐵))
1817fveq2d 6860 . . . . . . . . . . . . . . . . . . . 20 (𝑦 = 𝐵 → (𝐹‘(𝑓𝑦)) = (𝐹‘(𝑓𝐵)))
1916, 18eqeq12d 2772 . . . . . . . . . . . . . . . . . . 19 (𝑦 = 𝐵 → ((𝑓𝑦) = (𝐹‘(𝑓𝑦)) ↔ (𝑓𝐵) = (𝐹‘(𝑓𝐵))))
2019rspcv 3572 . . . . . . . . . . . . . . . . . 18 (𝐵𝑥 → (∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)) → (𝑓𝐵) = (𝐹‘(𝑓𝐵))))
21 fndm 6613 . . . . . . . . . . . . . . . . . . . . 21 (𝑓 Fn 𝑥 → dom 𝑓 = 𝑥)
2221eleq2d 2842 . . . . . . . . . . . . . . . . . . . 20 (𝑓 Fn 𝑥 → (𝐵 ∈ dom 𝑓𝐵𝑥))
239tfrlem7 8342 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Fun recs(𝐹)
24 funssfv 6877 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ((Fun recs(𝐹) ∧ 𝑓 ⊆ recs(𝐹) ∧ 𝐵 ∈ dom 𝑓) → (recs(𝐹)‘𝐵) = (𝑓𝐵))
2523, 24mp3an1 1463 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ((𝑓 ⊆ recs(𝐹) ∧ 𝐵 ∈ dom 𝑓) → (recs(𝐹)‘𝐵) = (𝑓𝐵))
2625adantrl 724 . . . . . . . . . . . . . . . . . . . . . . . . . 26 ((𝑓 ⊆ recs(𝐹) ∧ ((𝑓 Fn 𝑥𝑥 ∈ On) ∧ 𝐵 ∈ dom 𝑓)) → (recs(𝐹)‘𝐵) = (𝑓𝐵))
2721eleq1d 2841 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 (𝑓 Fn 𝑥 → (dom 𝑓 ∈ On ↔ 𝑥 ∈ On))
28 onelss 6377 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 (dom 𝑓 ∈ On → (𝐵 ∈ dom 𝑓𝐵 ⊆ dom 𝑓))
2927, 28biimtrrdi 256 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 (𝑓 Fn 𝑥 → (𝑥 ∈ On → (𝐵 ∈ dom 𝑓𝐵 ⊆ dom 𝑓)))
3029imp31 420 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 (((𝑓 Fn 𝑥𝑥 ∈ On) ∧ 𝐵 ∈ dom 𝑓) → 𝐵 ⊆ dom 𝑓)
31 fun2ssres 6555 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ((Fun recs(𝐹) ∧ 𝑓 ⊆ recs(𝐹) ∧ 𝐵 ⊆ dom 𝑓) → (recs(𝐹) ↾ 𝐵) = (𝑓𝐵))
3231fveq2d 6860 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ((Fun recs(𝐹) ∧ 𝑓 ⊆ recs(𝐹) ∧ 𝐵 ⊆ dom 𝑓) → (𝐹‘(recs(𝐹) ↾ 𝐵)) = (𝐹‘(𝑓𝐵)))
3323, 32mp3an1 1463 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ((𝑓 ⊆ recs(𝐹) ∧ 𝐵 ⊆ dom 𝑓) → (𝐹‘(recs(𝐹) ↾ 𝐵)) = (𝐹‘(𝑓𝐵)))
3430, 33sylan2 601 . . . . . . . . . . . . . . . . . . . . . . . . . 26 ((𝑓 ⊆ recs(𝐹) ∧ ((𝑓 Fn 𝑥𝑥 ∈ On) ∧ 𝐵 ∈ dom 𝑓)) → (𝐹‘(recs(𝐹) ↾ 𝐵)) = (𝐹‘(𝑓𝐵)))
3526, 34eqeq12d 2772 . . . . . . . . . . . . . . . . . . . . . . . . 25 ((𝑓 ⊆ recs(𝐹) ∧ ((𝑓 Fn 𝑥𝑥 ∈ On) ∧ 𝐵 ∈ dom 𝑓)) → ((recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)) ↔ (𝑓𝐵) = (𝐹‘(𝑓𝐵))))
3635exbiri 818 . . . . . . . . . . . . . . . . . . . . . . . 24 (𝑓 ⊆ recs(𝐹) → (((𝑓 Fn 𝑥𝑥 ∈ On) ∧ 𝐵 ∈ dom 𝑓) → ((𝑓𝐵) = (𝐹‘(𝑓𝐵)) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))
3736com3l 89 . . . . . . . . . . . . . . . . . . . . . . 23 (((𝑓 Fn 𝑥𝑥 ∈ On) ∧ 𝐵 ∈ dom 𝑓) → ((𝑓𝐵) = (𝐹‘(𝑓𝐵)) → (𝑓 ⊆ recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))
3837exp31 422 . . . . . . . . . . . . . . . . . . . . . 22 (𝑓 Fn 𝑥 → (𝑥 ∈ On → (𝐵 ∈ dom 𝑓 → ((𝑓𝐵) = (𝐹‘(𝑓𝐵)) → (𝑓 ⊆ recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))))
3938com34 91 . . . . . . . . . . . . . . . . . . . . 21 (𝑓 Fn 𝑥 → (𝑥 ∈ On → ((𝑓𝐵) = (𝐹‘(𝑓𝐵)) → (𝐵 ∈ dom 𝑓 → (𝑓 ⊆ recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))))
4039com24 95 . . . . . . . . . . . . . . . . . . . 20 (𝑓 Fn 𝑥 → (𝐵 ∈ dom 𝑓 → ((𝑓𝐵) = (𝐹‘(𝑓𝐵)) → (𝑥 ∈ On → (𝑓 ⊆ recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))))
4122, 40sylbird 262 . . . . . . . . . . . . . . . . . . 19 (𝑓 Fn 𝑥 → (𝐵𝑥 → ((𝑓𝐵) = (𝐹‘(𝑓𝐵)) → (𝑥 ∈ On → (𝑓 ⊆ recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))))
4241com3l 89 . . . . . . . . . . . . . . . . . 18 (𝐵𝑥 → ((𝑓𝐵) = (𝐹‘(𝑓𝐵)) → (𝑓 Fn 𝑥 → (𝑥 ∈ On → (𝑓 ⊆ recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))))
4320, 42syld 47 . . . . . . . . . . . . . . . . 17 (𝐵𝑥 → (∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)) → (𝑓 Fn 𝑥 → (𝑥 ∈ On → (𝑓 ⊆ recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))))
4443com24 95 . . . . . . . . . . . . . . . 16 (𝐵𝑥 → (𝑥 ∈ On → (𝑓 Fn 𝑥 → (∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)) → (𝑓 ⊆ recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))))
4544imp4d 427 . . . . . . . . . . . . . . 15 (𝐵𝑥 → ((𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → (𝑓 ⊆ recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))
4615, 45mpdi 45 . . . . . . . . . . . . . 14 (𝐵𝑥 → ((𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵))))
477, 46syl 17 . . . . . . . . . . . . 13 ((𝑓 Fn 𝑥 ∧ ⟨𝐵, 𝑧⟩ ∈ 𝑓) → ((𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵))))
4847exp4d 436 . . . . . . . . . . . 12 ((𝑓 Fn 𝑥 ∧ ⟨𝐵, 𝑧⟩ ∈ 𝑓) → (𝑥 ∈ On → (𝑓 Fn 𝑥 → (∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵))))))
4948ex 415 . . . . . . . . . . 11 (𝑓 Fn 𝑥 → (⟨𝐵, 𝑧⟩ ∈ 𝑓 → (𝑥 ∈ On → (𝑓 Fn 𝑥 → (∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))))
5049com4r 94 . . . . . . . . . 10 (𝑓 Fn 𝑥 → (𝑓 Fn 𝑥 → (⟨𝐵, 𝑧⟩ ∈ 𝑓 → (𝑥 ∈ On → (∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))))
5150pm2.43i 52 . . . . . . . . 9 (𝑓 Fn 𝑥 → (⟨𝐵, 𝑧⟩ ∈ 𝑓 → (𝑥 ∈ On → (∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵))))))
5251com3l 89 . . . . . . . 8 (⟨𝐵, 𝑧⟩ ∈ 𝑓 → (𝑥 ∈ On → (𝑓 Fn 𝑥 → (∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵))))))
5352imp4a 425 . . . . . . 7 (⟨𝐵, 𝑧⟩ ∈ 𝑓 → (𝑥 ∈ On → ((𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))
5453rexlimdv 3155 . . . . . 6 (⟨𝐵, 𝑧⟩ ∈ 𝑓 → (∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵))))
5554imp 409 . . . . 5 ((⟨𝐵, 𝑧⟩ ∈ 𝑓 ∧ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))
5655exlimiv 1944 . . . 4 (∃𝑓(⟨𝐵, 𝑧⟩ ∈ 𝑓 ∧ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))
576, 56sylbi 219 . . 3 (⟨𝐵, 𝑧⟩ ∈ recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))
5857exlimiv 1944 . 2 (∃𝑧𝐵, 𝑧⟩ ∈ recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))
592, 58syl 17 1 (𝐵 ∈ dom recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wa 398  w3a 1095   = wceq 1554  wex 1793  wcel 2136  {cab 2734  wral 3070  wrex 3080  wss 3899  cop 4582   cuni 4859  dom cdm 5640  cres 5642  Oncon0 6335  Fun wfun 6504   Fn wfn 6505  cfv 6510  recscrecs 8329
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1809  ax-4 1823  ax-5 1924  ax-6 1981  ax-7 2022  ax-8 2138  ax-9 2146  ax-10 2169  ax-11 2185  ax-12 2206  ax-ext 2728  ax-sep 5240  ax-nul 5250  ax-pr 5384  ax-un 7707
This theorem depends on definitions:  df-bi 209  df-an 399  df-or 857  df-3or 1096  df-3an 1097  df-tru 1557  df-fal 1567  df-ex 1794  df-nf 1798  df-sb 2085  df-mo 2560  df-eu 2590  df-clab 2735  df-cleq 2748  df-clel 2831  df-nfc 2905  df-ne 2952  df-ral 3071  df-rex 3081  df-rab 3409  df-v 3450  df-sbc 3740  df-csb 3848  df-dif 3902  df-un 3904  df-in 3906  df-ss 3916  df-pss 3919  df-nul 4281  df-if 4475  df-pw 4551  df-sn 4577  df-pr 4579  df-op 4583  df-uni 4860  df-iun 4945  df-br 5095  df-opab 5157  df-mpt 5176  df-tr 5202  df-id 5535  df-eprel 5540  df-po 5548  df-so 5549  df-fr 5593  df-we 5595  df-xp 5646  df-rel 5647  df-cnv 5648  df-co 5649  df-dm 5650  df-rn 5651  df-res 5652  df-ima 5653  df-pred 6277  df-ord 6338  df-on 6339  df-iota 6466  df-fun 6512  df-fn 6513  df-f 6514  df-fo 6516  df-fv 6518  df-ov 7388  df-2nd 7960  df-frecs 8250  df-wrecs 8281  df-recs 8330
This theorem is referenced by:  tfrlem11  8347  tfr2a  8354
  Copyright terms: Public domain W3C validator