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

Theorem tfrlem9 8314
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 5846 . . 3 (𝐵 ∈ dom recs(𝐹) → (𝐵 ∈ dom recs(𝐹) ↔ ∃𝑧𝐵, 𝑧⟩ ∈ recs(𝐹)))
21ibi 267 . 2 (𝐵 ∈ dom recs(𝐹) → ∃𝑧𝐵, 𝑧⟩ ∈ recs(𝐹))
3 dfrecs3 8302 . . . . . 6 recs(𝐹) = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))}
43eleq2i 2826 . . . . 5 (⟨𝐵, 𝑧⟩ ∈ recs(𝐹) ↔ ⟨𝐵, 𝑧⟩ ∈ {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))})
5 eluniab 4875 . . . . 5 (⟨𝐵, 𝑧⟩ ∈ {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))} ↔ ∃𝑓(⟨𝐵, 𝑧⟩ ∈ 𝑓 ∧ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
64, 5bitri 275 . . . 4 (⟨𝐵, 𝑧⟩ ∈ recs(𝐹) ↔ ∃𝑓(⟨𝐵, 𝑧⟩ ∈ 𝑓 ∧ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
7 fnop 6599 . . . . . . . . . . . . . 14 ((𝑓 Fn 𝑥 ∧ ⟨𝐵, 𝑧⟩ ∈ 𝑓) → 𝐵𝑥)
8 rspe 3224 . . . . . . . . . . . . . . . 16 ((𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
9 tfrlem.1 . . . . . . . . . . . . . . . . . 18 𝐴 = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))}
109eqabri 2876 . . . . . . . . . . . . . . . . 17 (𝑓𝐴 ↔ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
11 elssuni 4892 . . . . . . . . . . . . . . . . . 18 (𝑓𝐴𝑓 𝐴)
129recsfval 8310 . . . . . . . . . . . . . . . . . 18 recs(𝐹) = 𝐴
1311, 12sseqtrrdi 3973 . . . . . . . . . . . . . . . . 17 (𝑓𝐴𝑓 ⊆ recs(𝐹))
1410, 13sylbir 235 . . . . . . . . . . . . . . . 16 (∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))) → 𝑓 ⊆ recs(𝐹))
158, 14syl 17 . . . . . . . . . . . . . . 15 ((𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) → 𝑓 ⊆ recs(𝐹))
16 fveq2 6832 . . . . . . . . . . . . . . . . . . . 20 (𝑦 = 𝐵 → (𝑓𝑦) = (𝑓𝐵))
17 reseq2 5931 . . . . . . . . . . . . . . . . . . . . 21 (𝑦 = 𝐵 → (𝑓𝑦) = (𝑓𝐵))
1817fveq2d 6836 . . . . . . . . . . . . . . . . . . . 20 (𝑦 = 𝐵 → (𝐹‘(𝑓𝑦)) = (𝐹‘(𝑓𝐵)))
1916, 18eqeq12d 2750 . . . . . . . . . . . . . . . . . . 19 (𝑦 = 𝐵 → ((𝑓𝑦) = (𝐹‘(𝑓𝑦)) ↔ (𝑓𝐵) = (𝐹‘(𝑓𝐵))))
2019rspcv 3570 . . . . . . . . . . . . . . . . . 18 (𝐵𝑥 → (∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)) → (𝑓𝐵) = (𝐹‘(𝑓𝐵))))
21 fndm 6593 . . . . . . . . . . . . . . . . . . . . 21 (𝑓 Fn 𝑥 → dom 𝑓 = 𝑥)
2221eleq2d 2820 . . . . . . . . . . . . . . . . . . . 20 (𝑓 Fn 𝑥 → (𝐵 ∈ dom 𝑓𝐵𝑥))
239tfrlem7 8312 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Fun recs(𝐹)
24 funssfv 6853 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ((Fun recs(𝐹) ∧ 𝑓 ⊆ recs(𝐹) ∧ 𝐵 ∈ dom 𝑓) → (recs(𝐹)‘𝐵) = (𝑓𝐵))
2523, 24mp3an1 1450 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ((𝑓 ⊆ recs(𝐹) ∧ 𝐵 ∈ dom 𝑓) → (recs(𝐹)‘𝐵) = (𝑓𝐵))
2625adantrl 716 . . . . . . . . . . . . . . . . . . . . . . . . . 26 ((𝑓 ⊆ recs(𝐹) ∧ ((𝑓 Fn 𝑥𝑥 ∈ On) ∧ 𝐵 ∈ dom 𝑓)) → (recs(𝐹)‘𝐵) = (𝑓𝐵))
2721eleq1d 2819 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 (𝑓 Fn 𝑥 → (dom 𝑓 ∈ On ↔ 𝑥 ∈ On))
28 onelss 6357 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 (dom 𝑓 ∈ On → (𝐵 ∈ dom 𝑓𝐵 ⊆ dom 𝑓))
2927, 28biimtrrdi 254 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 (𝑓 Fn 𝑥 → (𝑥 ∈ On → (𝐵 ∈ dom 𝑓𝐵 ⊆ dom 𝑓)))
3029imp31 417 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 (((𝑓 Fn 𝑥𝑥 ∈ On) ∧ 𝐵 ∈ dom 𝑓) → 𝐵 ⊆ dom 𝑓)
31 fun2ssres 6535 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ((Fun recs(𝐹) ∧ 𝑓 ⊆ recs(𝐹) ∧ 𝐵 ⊆ dom 𝑓) → (recs(𝐹) ↾ 𝐵) = (𝑓𝐵))
3231fveq2d 6836 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 ((Fun recs(𝐹) ∧ 𝑓 ⊆ recs(𝐹) ∧ 𝐵 ⊆ dom 𝑓) → (𝐹‘(recs(𝐹) ↾ 𝐵)) = (𝐹‘(𝑓𝐵)))
3323, 32mp3an1 1450 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ((𝑓 ⊆ recs(𝐹) ∧ 𝐵 ⊆ dom 𝑓) → (𝐹‘(recs(𝐹) ↾ 𝐵)) = (𝐹‘(𝑓𝐵)))
3430, 33sylan2 593 . . . . . . . . . . . . . . . . . . . . . . . . . 26 ((𝑓 ⊆ recs(𝐹) ∧ ((𝑓 Fn 𝑥𝑥 ∈ On) ∧ 𝐵 ∈ dom 𝑓)) → (𝐹‘(recs(𝐹) ↾ 𝐵)) = (𝐹‘(𝑓𝐵)))
3526, 34eqeq12d 2750 . . . . . . . . . . . . . . . . . . . . . . . . 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 3133 . . . . . 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 2113  {cab 2712  wral 3049  wrex 3058  wss 3899  cop 4584   cuni 4861  dom cdm 5622  cres 5624  Oncon0 6315  Fun wfun 6484   Fn wfn 6485  cfv 6490  recscrecs 8300
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 2115  ax-9 2123  ax-10 2146  ax-11 2162  ax-12 2182  ax-ext 2706  ax-sep 5239  ax-nul 5249  ax-pr 5375  ax-un 7678
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 2537  df-eu 2567  df-clab 2713  df-cleq 2726  df-clel 2809  df-nfc 2883  df-ne 2931  df-ral 3050  df-rex 3059  df-rab 3398  df-v 3440  df-sbc 3739  df-csb 3848  df-dif 3902  df-un 3904  df-in 3906  df-ss 3916  df-pss 3919  df-nul 4284  df-if 4478  df-pw 4554  df-sn 4579  df-pr 4581  df-op 4585  df-uni 4862  df-iun 4946  df-br 5097  df-opab 5159  df-mpt 5178  df-tr 5204  df-id 5517  df-eprel 5522  df-po 5530  df-so 5531  df-fr 5575  df-we 5577  df-xp 5628  df-rel 5629  df-cnv 5630  df-co 5631  df-dm 5632  df-rn 5633  df-res 5634  df-ima 5635  df-pred 6257  df-ord 6318  df-on 6319  df-iota 6446  df-fun 6492  df-fn 6493  df-f 6494  df-fo 6496  df-fv 6498  df-ov 7359  df-2nd 7932  df-frecs 8221  df-wrecs 8252  df-recs 8301
This theorem is referenced by:  tfrlem11  8317  tfr2a  8324
  Copyright terms: Public domain W3C validator