Users' Mathboxes Mathbox for Scott Fenton < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  frrlem6 Structured version   Visualization version   GIF version

Theorem frrlem6 32066
Description: Lemma for founded recursion. The union of all acceptable functions is a relationship. (Contributed by Paul Chapman, 21-Apr-2012.) (Revised by Scott Fenton, 23-Dec-2021.)
Hypotheses
Ref Expression
frrlem6.1 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥𝐴 ∧ ∀𝑦𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}
frrlem6.2 𝐹 = frecs(𝑅, 𝐴, 𝐺)
Assertion
Ref Expression
frrlem6 Rel 𝐹
Distinct variable groups:   𝐴,𝑓,𝑥,𝑦   𝑓,𝐺,𝑥,𝑦   𝑅,𝑓,𝑥,𝑦
Allowed substitution hints:   𝐵(𝑥,𝑦,𝑓)   𝐹(𝑥,𝑦,𝑓)

Proof of Theorem frrlem6
Dummy variable 𝑔 is distinct from all other variables.
StepHypRef Expression
1 reluni 5385 . . 3 (Rel 𝐵 ↔ ∀𝑔𝐵 Rel 𝑔)
2 frrlem6.1 . . . . 5 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥𝐴 ∧ ∀𝑦𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}
32frrlem2 32058 . . . 4 (𝑔𝐵 → Fun 𝑔)
4 funrel 6054 . . . 4 (Fun 𝑔 → Rel 𝑔)
53, 4syl 17 . . 3 (𝑔𝐵 → Rel 𝑔)
61, 5mprgbir 3053 . 2 Rel 𝐵
7 frrlem6.2 . . . . 5 𝐹 = frecs(𝑅, 𝐴, 𝐺)
8 df-frecs 32053 . . . . 5 frecs(𝑅, 𝐴, 𝐺) = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥𝐴 ∧ ∀𝑦𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}
97, 8eqtri 2770 . . . 4 𝐹 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥𝐴 ∧ ∀𝑦𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}
102unieqi 4585 . . . 4 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥𝐴 ∧ ∀𝑦𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}
119, 10eqtr4i 2773 . . 3 𝐹 = 𝐵
1211releqi 5347 . 2 (Rel 𝐹 ↔ Rel 𝐵)
136, 12mpbir 221 1 Rel 𝐹
Colors of variables: wff setvar class
Syntax hints:  wa 383  w3a 1072   = wceq 1620  wex 1841  wcel 2127  {cab 2734  wral 3038  wss 3703   cuni 4576  cres 5256  Rel wrel 5259  Predcpred 5828  Fun wfun 6031   Fn wfn 6032  cfv 6037  (class class class)co 6801  frecscfrecs 32052
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1859  ax-4 1874  ax-5 1976  ax-6 2042  ax-7 2078  ax-9 2136  ax-10 2156  ax-11 2171  ax-12 2184  ax-13 2379  ax-ext 2728
This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-3an 1074  df-tru 1623  df-ex 1842  df-nf 1847  df-sb 2035  df-clab 2735  df-cleq 2741  df-clel 2744  df-nfc 2879  df-ral 3043  df-rex 3044  df-rab 3047  df-v 3330  df-dif 3706  df-un 3708  df-in 3710  df-ss 3717  df-nul 4047  df-if 4219  df-sn 4310  df-pr 4312  df-op 4316  df-uni 4577  df-iun 4662  df-br 4793  df-opab 4853  df-xp 5260  df-rel 5261  df-cnv 5262  df-co 5263  df-dm 5264  df-rn 5265  df-res 5266  df-ima 5267  df-pred 5829  df-iota 6000  df-fun 6039  df-fn 6040  df-fv 6045  df-ov 6804  df-frecs 32053
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator