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

Theorem tfrlem9 8304
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 5838 . . 3 (𝐵 ∈ dom recs(𝐹) → (𝐵 ∈ dom recs(𝐹) ↔ ∃𝑧𝐵, 𝑧⟩ ∈ recs(𝐹)))
21ibi 267 . 2 (𝐵 ∈ dom recs(𝐹) → ∃𝑧𝐵, 𝑧⟩ ∈ recs(𝐹))
3 dfrecs3 8292 . . . . . 6 recs(𝐹) = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))}
43eleq2i 2823 . . . . 5 (⟨𝐵, 𝑧⟩ ∈ recs(𝐹) ↔ ⟨𝐵, 𝑧⟩ ∈ {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))})
5 eluniab 4870 . . . . 5 (⟨𝐵, 𝑧⟩ ∈ {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))} ↔ ∃𝑓(⟨𝐵, 𝑧⟩ ∈ 𝑓 ∧ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
64, 5bitri 275 . . . 4 (⟨𝐵, 𝑧⟩ ∈ recs(𝐹) ↔ ∃𝑓(⟨𝐵, 𝑧⟩ ∈ 𝑓 ∧ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
7 fnop 6590 . . . . . . . . . . . . . 14 ((𝑓 Fn 𝑥 ∧ ⟨𝐵, 𝑧⟩ ∈ 𝑓) → 𝐵𝑥)
8 rspe 3222 . . . . . . . . . . . . . . . 16 ((𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
9 tfrlem.1 . . . . . . . . . . . . . . . . . 18 𝐴 = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))}
109eqabri 2874 . . . . . . . . . . . . . . . . 17 (𝑓𝐴 ↔ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
11 elssuni 4887 . . . . . . . . . . . . . . . . . 18 (𝑓𝐴𝑓 𝐴)
129recsfval 8300 . . . . . . . . . . . . . . . . . 18 recs(𝐹) = 𝐴
1311, 12sseqtrrdi 3971 . . . . . . . . . . . . . . . . 17 (𝑓𝐴𝑓 ⊆ recs(𝐹))
1410, 13sylbir 235 . . . . . . . . . . . . . . . 16 (∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))) → 𝑓 ⊆ recs(𝐹))
158, 14syl 17 . . . . . . . . . . . . . . 15 ((𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → 𝑓 ⊆ recs(𝐹))
16 fveq2 6822 . . . . . . . . . . . . . . . . . . . 20 (𝑦 = 𝐵 → (𝑓𝑦) = (𝑓𝐵))
17 reseq2 5922 . . . . . . . . . . . . . . . . . . . . 21 (𝑦 = 𝐵 → (𝑓𝑦) = (𝑓𝐵))
1817fveq2d 6826 . . . . . . . . . . . . . . . . . . . 20 (𝑦 = 𝐵 → (𝐹‘(𝑓𝑦)) = (𝐹‘(𝑓𝐵)))
1916, 18eqeq12d 2747 . . . . . . . . . . . . . . . . . . 19 (𝑦 = 𝐵 → ((𝑓𝑦) = (𝐹‘(𝑓𝑦)) ↔ (𝑓𝐵) = (𝐹‘(𝑓𝐵))))
2019rspcv 3568 . . . . . . . . . . . . . . . . . 18 (𝐵𝑥 → (∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)) → (𝑓𝐵) = (𝐹‘(𝑓𝐵))))
21 fndm 6584 . . . . . . . . . . . . . . . . . . . . 21 (𝑓 Fn 𝑥 → dom 𝑓 = 𝑥)
2221eleq2d 2817 . . . . . . . . . . . . . . . . . . . 20 (𝑓 Fn 𝑥 → (𝐵 ∈ dom 𝑓𝐵𝑥))
239tfrlem7 8302 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Fun recs(𝐹)
24 funssfv 6843 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ((Fun recs(𝐹) ∧ 𝑓 ⊆ recs(𝐹) ∧ 𝐵 ∈ dom 𝑓) → (recs(𝐹)‘𝐵) = (𝑓𝐵))
2523, 24mp3an1 1450 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ((𝑓 ⊆ recs(𝐹) ∧ 𝐵 ∈ dom 𝑓) → (recs(𝐹)‘𝐵) = (𝑓𝐵))
2625adantrl 716 . . . . . . . . . . . . . . . . . . . . . . . . . 26 ((𝑓 ⊆ recs(𝐹) ∧ ((𝑓 Fn 𝑥𝑥 ∈ On) ∧ 𝐵 ∈ dom 𝑓)) → (recs(𝐹)‘𝐵) = (𝑓𝐵))
2721eleq1d 2816 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 (𝑓 Fn 𝑥 → (dom 𝑓 ∈ On ↔ 𝑥 ∈ On))
28 onelss 6348 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 (dom 𝑓 ∈ On → (𝐵 ∈ dom 𝑓𝐵 ⊆ dom 𝑓))
2927, 28biimtrrdi 254 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 (𝑓 Fn 𝑥 → (𝑥 ∈ On → (𝐵 ∈ dom 𝑓𝐵 ⊆ dom 𝑓)))
3029imp31 417 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 (((𝑓 Fn 𝑥𝑥 ∈ On) ∧ 𝐵 ∈ dom 𝑓) → 𝐵 ⊆ dom 𝑓)
31 fun2ssres 6526 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ((Fun recs(𝐹) ∧ 𝑓 ⊆ recs(𝐹) ∧ 𝐵 ⊆ dom 𝑓) → (recs(𝐹) ↾ 𝐵) = (𝑓𝐵))
3231fveq2d 6826 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ((Fun recs(𝐹) ∧ 𝑓 ⊆ recs(𝐹) ∧ 𝐵 ⊆ dom 𝑓) → (𝐹‘(recs(𝐹) ↾ 𝐵)) = (𝐹‘(𝑓𝐵)))
3323, 32mp3an1 1450 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ((𝑓 ⊆ recs(𝐹) ∧ 𝐵 ⊆ dom 𝑓) → (𝐹‘(recs(𝐹) ↾ 𝐵)) = (𝐹‘(𝑓𝐵)))
3430, 33sylan2 593 . . . . . . . . . . . . . . . . . . . . . . . . . 26 ((𝑓 ⊆ recs(𝐹) ∧ ((𝑓 Fn 𝑥𝑥 ∈ On) ∧ 𝐵 ∈ dom 𝑓)) → (𝐹‘(recs(𝐹) ↾ 𝐵)) = (𝐹‘(𝑓𝐵)))
3526, 34eqeq12d 2747 . . . . . . . . . . . . . . . . . . . . . . . . 25 ((𝑓 ⊆ recs(𝐹) ∧ ((𝑓 Fn 𝑥𝑥 ∈ On) ∧ 𝐵 ∈ dom 𝑓)) → ((recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)) ↔ (𝑓𝐵) = (𝐹‘(𝑓𝐵))))
3635exbiri 810 . . . . . . . . . . . . . . . . . . . . . . . 24 (𝑓 ⊆ recs(𝐹) → (((𝑓 Fn 𝑥𝑥 ∈ On) ∧ 𝐵 ∈ dom 𝑓) → ((𝑓𝐵) = (𝐹‘(𝑓𝐵)) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))
3736com3l 89 . . . . . . . . . . . . . . . . . . . . . . 23 (((𝑓 Fn 𝑥𝑥 ∈ On) ∧ 𝐵 ∈ dom 𝑓) → ((𝑓𝐵) = (𝐹‘(𝑓𝐵)) → (𝑓 ⊆ recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))
3837exp31 419 . . . . . . . . . . . . . . . . . . . . . 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 260 . . . . . . . . . . . . . . . . . . 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 424 . . . . . . . . . . . . . . 15 (𝐵𝑥 → ((𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → (𝑓 ⊆ recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))
4615, 45mpdi 45 . . . . . . . . . . . . . 14 (𝐵𝑥 → ((𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵))))
477, 46syl 17 . . . . . . . . . . . . 13 ((𝑓 Fn 𝑥 ∧ ⟨𝐵, 𝑧⟩ ∈ 𝑓) → ((𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵))))
4847exp4d 433 . . . . . . . . . . . 12 ((𝑓 Fn 𝑥 ∧ ⟨𝐵, 𝑧⟩ ∈ 𝑓) → (𝑥 ∈ On → (𝑓 Fn 𝑥 → (∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵))))))
4948ex 412 . . . . . . . . . . 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 422 . . . . . . 7 (⟨𝐵, 𝑧⟩ ∈ 𝑓 → (𝑥 ∈ On → ((𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))))
5453rexlimdv 3131 . . . . . 6 (⟨𝐵, 𝑧⟩ ∈ 𝑓 → (∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵))))
5554imp 406 . . . . 5 ((⟨𝐵, 𝑧⟩ ∈ 𝑓 ∧ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))
5655exlimiv 1931 . . . 4 (∃𝑓(⟨𝐵, 𝑧⟩ ∈ 𝑓 ∧ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))
576, 56sylbi 217 . . 3 (⟨𝐵, 𝑧⟩ ∈ recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))
5857exlimiv 1931 . 2 (∃𝑧𝐵, 𝑧⟩ ∈ recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))
592, 58syl 17 1 (𝐵 ∈ dom recs(𝐹) → (recs(𝐹)‘𝐵) = (𝐹‘(recs(𝐹) ↾ 𝐵)))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wa 395  w3a 1086   = wceq 1541  wex 1780  wcel 2111  {cab 2709  wral 3047  wrex 3056  wss 3897  cop 4579   cuni 4856  dom cdm 5614  cres 5616  Oncon0 6306  Fun wfun 6475   Fn wfn 6476  cfv 6481  recscrecs 8290
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1796  ax-4 1810  ax-5 1911  ax-6 1968  ax-7 2009  ax-8 2113  ax-9 2121  ax-10 2144  ax-11 2160  ax-12 2180  ax-ext 2703  ax-sep 5232  ax-nul 5242  ax-pr 5368  ax-un 7668
This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-3or 1087  df-3an 1088  df-tru 1544  df-fal 1554  df-ex 1781  df-nf 1785  df-sb 2068  df-mo 2535  df-eu 2564  df-clab 2710  df-cleq 2723  df-clel 2806  df-nfc 2881  df-ne 2929  df-ral 3048  df-rex 3057  df-rab 3396  df-v 3438  df-sbc 3737  df-csb 3846  df-dif 3900  df-un 3902  df-in 3904  df-ss 3914  df-pss 3917  df-nul 4281  df-if 4473  df-pw 4549  df-sn 4574  df-pr 4576  df-op 4580  df-uni 4857  df-iun 4941  df-br 5090  df-opab 5152  df-mpt 5171  df-tr 5197  df-id 5509  df-eprel 5514  df-po 5522  df-so 5523  df-fr 5567  df-we 5569  df-xp 5620  df-rel 5621  df-cnv 5622  df-co 5623  df-dm 5624  df-rn 5625  df-res 5626  df-ima 5627  df-pred 6248  df-ord 6309  df-on 6310  df-iota 6437  df-fun 6483  df-fn 6484  df-f 6485  df-fo 6487  df-fv 6489  df-ov 7349  df-2nd 7922  df-frecs 8211  df-wrecs 8242  df-recs 8291
This theorem is referenced by:  tfrlem11  8307  tfr2a  8314
  Copyright terms: Public domain W3C validator