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

Theorem frrlem15 9734
Description: Lemma for general well-founded recursion. Two acceptable functions are compatible. (Contributed by Scott Fenton, 11-Sep-2023.)
Hypotheses
Ref Expression
frrlem15.1 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥𝐴 ∧ ∀𝑦𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}
frrlem15.2 𝐹 = frecs(𝑅, 𝐴, 𝐺)
Assertion
Ref Expression
frrlem15 (((𝑅 Fr 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → ((𝑥𝑔𝑢𝑥𝑣) → 𝑢 = 𝑣))
Distinct variable groups:   𝐴,𝑓,𝑥,𝑦,𝑔,,𝑢,𝑣   𝑅,𝑓,𝑥,𝑦,𝑔,,𝑢,𝑣   𝑓,𝐺,𝑥,𝑦,𝑔,,𝑢,𝑣
Allowed substitution hints:   𝐵(𝑥,𝑦,𝑣,𝑢,𝑓,𝑔,)   𝐹(𝑥,𝑦,𝑣,𝑢,𝑓,𝑔,)

Proof of Theorem frrlem15
Dummy variable 𝑎 is distinct from all other variables.
StepHypRef Expression
1 vex 3477 . . . . . 6 𝑥 ∈ V
2 vex 3477 . . . . . 6 𝑢 ∈ V
31, 2breldm 5900 . . . . 5 (𝑥𝑔𝑢𝑥 ∈ dom 𝑔)
43adantr 481 . . . 4 ((𝑥𝑔𝑢𝑥𝑣) → 𝑥 ∈ dom 𝑔)
5 vex 3477 . . . . . 6 𝑣 ∈ V
61, 5breldm 5900 . . . . 5 (𝑥𝑣𝑥 ∈ dom )
76adantl 482 . . . 4 ((𝑥𝑔𝑢𝑥𝑣) → 𝑥 ∈ dom )
84, 7elind 4190 . . 3 ((𝑥𝑔𝑢𝑥𝑣) → 𝑥 ∈ (dom 𝑔 ∩ dom ))
9 id 22 . . 3 ((𝑥𝑔𝑢𝑥𝑣) → (𝑥𝑔𝑢𝑥𝑣))
102brresi 5982 . . . . 5 (𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢 ↔ (𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥𝑔𝑢))
115brresi 5982 . . . . 5 (𝑥( ↾ (dom 𝑔 ∩ dom ))𝑣 ↔ (𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥𝑣))
1210, 11anbi12i 627 . . . 4 ((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥( ↾ (dom 𝑔 ∩ dom ))𝑣) ↔ ((𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥𝑔𝑢) ∧ (𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥𝑣)))
13 an4 654 . . . 4 (((𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥𝑔𝑢) ∧ (𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥𝑣)) ↔ ((𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥 ∈ (dom 𝑔 ∩ dom )) ∧ (𝑥𝑔𝑢𝑥𝑣)))
1412, 13bitri 274 . . 3 ((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥( ↾ (dom 𝑔 ∩ dom ))𝑣) ↔ ((𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥 ∈ (dom 𝑔 ∩ dom )) ∧ (𝑥𝑔𝑢𝑥𝑣)))
158, 8, 9, 14syl21anbrc 1344 . 2 ((𝑥𝑔𝑢𝑥𝑣) → (𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥( ↾ (dom 𝑔 ∩ dom ))𝑣))
16 inss1 4224 . . . . . . . . 9 (dom 𝑔 ∩ dom ) ⊆ dom 𝑔
17 frrlem15.1 . . . . . . . . . 10 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥𝐴 ∧ ∀𝑦𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}
1817frrlem3 8255 . . . . . . . . 9 (𝑔𝐵 → dom 𝑔𝐴)
1916, 18sstrid 3989 . . . . . . . 8 (𝑔𝐵 → (dom 𝑔 ∩ dom ) ⊆ 𝐴)
2019ad2antrl 726 . . . . . . 7 (((𝑅 Fr 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → (dom 𝑔 ∩ dom ) ⊆ 𝐴)
21 simpll 765 . . . . . . 7 (((𝑅 Fr 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → 𝑅 Fr 𝐴)
22 frss 5636 . . . . . . 7 ((dom 𝑔 ∩ dom ) ⊆ 𝐴 → (𝑅 Fr 𝐴𝑅 Fr (dom 𝑔 ∩ dom )))
2320, 21, 22sylc 65 . . . . . 6 (((𝑅 Fr 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → 𝑅 Fr (dom 𝑔 ∩ dom ))
24 simplr 767 . . . . . . 7 (((𝑅 Fr 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → 𝑅 Se 𝐴)
25 sess2 5638 . . . . . . 7 ((dom 𝑔 ∩ dom ) ⊆ 𝐴 → (𝑅 Se 𝐴𝑅 Se (dom 𝑔 ∩ dom )))
2620, 24, 25sylc 65 . . . . . 6 (((𝑅 Fr 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → 𝑅 Se (dom 𝑔 ∩ dom ))
2717frrlem4 8256 . . . . . . 7 ((𝑔𝐵𝐵) → ((𝑔 ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ∧ ∀𝑎 ∈ (dom 𝑔 ∩ dom )((𝑔 ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺((𝑔 ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎)))))
2827adantl 482 . . . . . 6 (((𝑅 Fr 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → ((𝑔 ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ∧ ∀𝑎 ∈ (dom 𝑔 ∩ dom )((𝑔 ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺((𝑔 ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎)))))
2917frrlem4 8256 . . . . . . . . 9 ((𝐵𝑔𝐵) → (( ↾ (dom ∩ dom 𝑔)) Fn (dom ∩ dom 𝑔) ∧ ∀𝑎 ∈ (dom ∩ dom 𝑔)(( ↾ (dom ∩ dom 𝑔))‘𝑎) = (𝑎𝐺(( ↾ (dom ∩ dom 𝑔)) ↾ Pred(𝑅, (dom ∩ dom 𝑔), 𝑎)))))
30 incom 4197 . . . . . . . . . . . 12 (dom 𝑔 ∩ dom ) = (dom ∩ dom 𝑔)
3130reseq2i 5970 . . . . . . . . . . 11 ( ↾ (dom 𝑔 ∩ dom )) = ( ↾ (dom ∩ dom 𝑔))
32 fneq12 6634 . . . . . . . . . . 11 ((( ↾ (dom 𝑔 ∩ dom )) = ( ↾ (dom ∩ dom 𝑔)) ∧ (dom 𝑔 ∩ dom ) = (dom ∩ dom 𝑔)) → (( ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ↔ ( ↾ (dom ∩ dom 𝑔)) Fn (dom ∩ dom 𝑔)))
3331, 30, 32mp2an 690 . . . . . . . . . 10 (( ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ↔ ( ↾ (dom ∩ dom 𝑔)) Fn (dom ∩ dom 𝑔))
3431fveq1i 6879 . . . . . . . . . . . 12 (( ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (( ↾ (dom ∩ dom 𝑔))‘𝑎)
35 predeq2 6292 . . . . . . . . . . . . . . 15 ((dom 𝑔 ∩ dom ) = (dom ∩ dom 𝑔) → Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎) = Pred(𝑅, (dom ∩ dom 𝑔), 𝑎))
3630, 35ax-mp 5 . . . . . . . . . . . . . 14 Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎) = Pred(𝑅, (dom ∩ dom 𝑔), 𝑎)
3731, 36reseq12i 5971 . . . . . . . . . . . . 13 (( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎)) = (( ↾ (dom ∩ dom 𝑔)) ↾ Pred(𝑅, (dom ∩ dom 𝑔), 𝑎))
3837oveq2i 7404 . . . . . . . . . . . 12 (𝑎𝐺(( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎))) = (𝑎𝐺(( ↾ (dom ∩ dom 𝑔)) ↾ Pred(𝑅, (dom ∩ dom 𝑔), 𝑎)))
3934, 38eqeq12i 2749 . . . . . . . . . . 11 ((( ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺(( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎))) ↔ (( ↾ (dom ∩ dom 𝑔))‘𝑎) = (𝑎𝐺(( ↾ (dom ∩ dom 𝑔)) ↾ Pred(𝑅, (dom ∩ dom 𝑔), 𝑎))))
4030, 39raleqbii 3337 . . . . . . . . . 10 (∀𝑎 ∈ (dom 𝑔 ∩ dom )(( ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺(( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎))) ↔ ∀𝑎 ∈ (dom ∩ dom 𝑔)(( ↾ (dom ∩ dom 𝑔))‘𝑎) = (𝑎𝐺(( ↾ (dom ∩ dom 𝑔)) ↾ Pred(𝑅, (dom ∩ dom 𝑔), 𝑎))))
4133, 40anbi12i 627 . . . . . . . . 9 ((( ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ∧ ∀𝑎 ∈ (dom 𝑔 ∩ dom )(( ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺(( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎)))) ↔ (( ↾ (dom ∩ dom 𝑔)) Fn (dom ∩ dom 𝑔) ∧ ∀𝑎 ∈ (dom ∩ dom 𝑔)(( ↾ (dom ∩ dom 𝑔))‘𝑎) = (𝑎𝐺(( ↾ (dom ∩ dom 𝑔)) ↾ Pred(𝑅, (dom ∩ dom 𝑔), 𝑎)))))
4229, 41sylibr 233 . . . . . . . 8 ((𝐵𝑔𝐵) → (( ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ∧ ∀𝑎 ∈ (dom 𝑔 ∩ dom )(( ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺(( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎)))))
4342ancoms 459 . . . . . . 7 ((𝑔𝐵𝐵) → (( ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ∧ ∀𝑎 ∈ (dom 𝑔 ∩ dom )(( ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺(( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎)))))
4443adantl 482 . . . . . 6 (((𝑅 Fr 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → (( ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ∧ ∀𝑎 ∈ (dom 𝑔 ∩ dom )(( ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺(( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎)))))
45 frr3g 9733 . . . . . 6 (((𝑅 Fr (dom 𝑔 ∩ dom ) ∧ 𝑅 Se (dom 𝑔 ∩ dom )) ∧ ((𝑔 ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ∧ ∀𝑎 ∈ (dom 𝑔 ∩ dom )((𝑔 ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺((𝑔 ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎)))) ∧ (( ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ∧ ∀𝑎 ∈ (dom 𝑔 ∩ dom )(( ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺(( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎))))) → (𝑔 ↾ (dom 𝑔 ∩ dom )) = ( ↾ (dom 𝑔 ∩ dom )))
4623, 26, 28, 44, 45syl211anc 1376 . . . . 5 (((𝑅 Fr 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → (𝑔 ↾ (dom 𝑔 ∩ dom )) = ( ↾ (dom 𝑔 ∩ dom )))
4746breqd 5152 . . . 4 (((𝑅 Fr 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → (𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣𝑥( ↾ (dom 𝑔 ∩ dom ))𝑣))
4847biimprd 247 . . 3 (((𝑅 Fr 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → (𝑥( ↾ (dom 𝑔 ∩ dom ))𝑣𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣))
4917frrlem2 8254 . . . . . 6 (𝑔𝐵 → Fun 𝑔)
5049funresd 6580 . . . . 5 (𝑔𝐵 → Fun (𝑔 ↾ (dom 𝑔 ∩ dom )))
5150ad2antrl 726 . . . 4 (((𝑅 Fr 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → Fun (𝑔 ↾ (dom 𝑔 ∩ dom )))
52 dffun2 6542 . . . . 5 (Fun (𝑔 ↾ (dom 𝑔 ∩ dom )) ↔ (Rel (𝑔 ↾ (dom 𝑔 ∩ dom )) ∧ ∀𝑥𝑢𝑣((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣)))
53 2sp 2179 . . . . . 6 (∀𝑢𝑣((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣) → ((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣))
5453sps 2178 . . . . 5 (∀𝑥𝑢𝑣((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣) → ((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣))
5552, 54simplbiim 505 . . . 4 (Fun (𝑔 ↾ (dom 𝑔 ∩ dom )) → ((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣))
5651, 55syl 17 . . 3 (((𝑅 Fr 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → ((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣))
5748, 56sylan2d 605 . 2 (((𝑅 Fr 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → ((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥( ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣))
5815, 57syl5 34 1 (((𝑅 Fr 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → ((𝑥𝑔𝑢𝑥𝑣) → 𝑢 = 𝑣))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 205  wa 396  w3a 1087  wal 1539   = wceq 1541  wex 1781  wcel 2106  {cab 2708  wral 3060  cin 3943  wss 3944   class class class wbr 5141   Fr wfr 5621   Se wse 5622  dom cdm 5669  cres 5671  Rel wrel 5674  Predcpred 6288  Fun wfun 6526   Fn wfn 6527  cfv 6532  (class class class)co 7393  frecscfrecs 8247
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1913  ax-6 1971  ax-7 2011  ax-8 2108  ax-9 2116  ax-10 2137  ax-11 2154  ax-12 2171  ax-ext 2702  ax-rep 5278  ax-sep 5292  ax-nul 5299  ax-pr 5420  ax-un 7708  ax-inf2 9618
This theorem depends on definitions:  df-bi 206  df-an 397  df-or 846  df-3or 1088  df-3an 1089  df-tru 1544  df-fal 1554  df-ex 1782  df-nf 1786  df-sb 2068  df-mo 2533  df-eu 2562  df-clab 2709  df-cleq 2723  df-clel 2809  df-nfc 2884  df-ne 2940  df-ral 3061  df-rex 3070  df-rmo 3375  df-reu 3376  df-rab 3432  df-v 3475  df-sbc 3774  df-csb 3890  df-dif 3947  df-un 3949  df-in 3951  df-ss 3961  df-pss 3963  df-nul 4319  df-if 4523  df-pw 4598  df-sn 4623  df-pr 4625  df-op 4629  df-uni 4902  df-int 4944  df-iun 4992  df-br 5142  df-opab 5204  df-mpt 5225  df-tr 5259  df-id 5567  df-eprel 5573  df-po 5581  df-so 5582  df-fr 5624  df-se 5625  df-we 5626  df-xp 5675  df-rel 5676  df-cnv 5677  df-co 5678  df-dm 5679  df-rn 5680  df-res 5681  df-ima 5682  df-pred 6289  df-ord 6356  df-on 6357  df-lim 6358  df-suc 6359  df-iota 6484  df-fun 6534  df-fn 6535  df-f 6536  df-f1 6537  df-fo 6538  df-f1o 6539  df-fv 6540  df-riota 7349  df-ov 7396  df-oprab 7397  df-mpo 7398  df-om 7839  df-2nd 7958  df-frecs 8248  df-wrecs 8279  df-recs 8353  df-rdg 8392  df-1o 8448  df-oadd 8452  df-ttrcl 9685
This theorem is referenced by:  frr1  9736  frr2  9737
  Copyright terms: Public domain W3C validator