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

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

Proof of Theorem fprlem1
Dummy variable 𝑎 is distinct from all other variables.
StepHypRef Expression
1 vex 3443 . . . . 5 𝑥 ∈ V
2 vex 3443 . . . . 5 𝑢 ∈ V
31, 2breldm 5670 . . . 4 (𝑥𝑔𝑢𝑥 ∈ dom 𝑔)
4 vex 3443 . . . . 5 𝑣 ∈ V
51, 4breldm 5670 . . . 4 (𝑥𝑣𝑥 ∈ dom )
6 elin 4096 . . . . 5 (𝑥 ∈ (dom 𝑔 ∩ dom ) ↔ (𝑥 ∈ dom 𝑔𝑥 ∈ dom ))
76biimpri 229 . . . 4 ((𝑥 ∈ dom 𝑔𝑥 ∈ dom ) → 𝑥 ∈ (dom 𝑔 ∩ dom ))
83, 5, 7syl2an 595 . . 3 ((𝑥𝑔𝑢𝑥𝑣) → 𝑥 ∈ (dom 𝑔 ∩ dom ))
9 id 22 . . 3 ((𝑥𝑔𝑢𝑥𝑣) → (𝑥𝑔𝑢𝑥𝑣))
102brresi 5750 . . . . 5 (𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢 ↔ (𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥𝑔𝑢))
114brresi 5750 . . . . 5 (𝑥( ↾ (dom 𝑔 ∩ dom ))𝑣 ↔ (𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥𝑣))
1210, 11anbi12i 626 . . . 4 ((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥( ↾ (dom 𝑔 ∩ dom ))𝑣) ↔ ((𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥𝑔𝑢) ∧ (𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥𝑣)))
13 an4 652 . . . 4 (((𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥𝑔𝑢) ∧ (𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥𝑣)) ↔ ((𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥 ∈ (dom 𝑔 ∩ dom )) ∧ (𝑥𝑔𝑢𝑥𝑣)))
1412, 13bitri 276 . . 3 ((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥( ↾ (dom 𝑔 ∩ dom ))𝑣) ↔ ((𝑥 ∈ (dom 𝑔 ∩ dom ) ∧ 𝑥 ∈ (dom 𝑔 ∩ dom )) ∧ (𝑥𝑔𝑢𝑥𝑣)))
158, 8, 9, 14syl21anbrc 1337 . 2 ((𝑥𝑔𝑢𝑥𝑣) → (𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥( ↾ (dom 𝑔 ∩ dom ))𝑣))
16 inss2 4132 . . . . . . . . . 10 (dom 𝑔 ∩ dom ) ⊆ dom
17 fprlem.1 . . . . . . . . . . 11 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥𝐴 ∧ ∀𝑦𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}
1817frrlem3 32736 . . . . . . . . . 10 (𝐵 → dom 𝐴)
1916, 18sstrid 3906 . . . . . . . . 9 (𝐵 → (dom 𝑔 ∩ dom ) ⊆ 𝐴)
2019adantl 482 . . . . . . . 8 ((𝑔𝐵𝐵) → (dom 𝑔 ∩ dom ) ⊆ 𝐴)
2120adantl 482 . . . . . . 7 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → (dom 𝑔 ∩ dom ) ⊆ 𝐴)
22 simpl1 1184 . . . . . . 7 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → 𝑅 Fr 𝐴)
23 frss 5417 . . . . . . 7 ((dom 𝑔 ∩ dom ) ⊆ 𝐴 → (𝑅 Fr 𝐴𝑅 Fr (dom 𝑔 ∩ dom )))
2421, 22, 23sylc 65 . . . . . 6 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → 𝑅 Fr (dom 𝑔 ∩ dom ))
25 simpl2 1185 . . . . . . 7 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → 𝑅 Po 𝐴)
26 poss 5371 . . . . . . 7 ((dom 𝑔 ∩ dom ) ⊆ 𝐴 → (𝑅 Po 𝐴𝑅 Po (dom 𝑔 ∩ dom )))
2721, 25, 26sylc 65 . . . . . 6 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → 𝑅 Po (dom 𝑔 ∩ dom ))
28 simpl3 1186 . . . . . . 7 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → 𝑅 Se 𝐴)
29 sess2 5419 . . . . . . 7 ((dom 𝑔 ∩ dom ) ⊆ 𝐴 → (𝑅 Se 𝐴𝑅 Se (dom 𝑔 ∩ dom )))
3021, 28, 29sylc 65 . . . . . 6 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → 𝑅 Se (dom 𝑔 ∩ dom ))
3117frrlem4 32737 . . . . . . 7 ((𝑔𝐵𝐵) → ((𝑔 ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ∧ ∀𝑎 ∈ (dom 𝑔 ∩ dom )((𝑔 ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺((𝑔 ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎)))))
3231adantl 482 . . . . . 6 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → ((𝑔 ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ∧ ∀𝑎 ∈ (dom 𝑔 ∩ dom )((𝑔 ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺((𝑔 ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎)))))
3317frrlem4 32737 . . . . . . . . 9 ((𝐵𝑔𝐵) → (( ↾ (dom ∩ dom 𝑔)) Fn (dom ∩ dom 𝑔) ∧ ∀𝑎 ∈ (dom ∩ dom 𝑔)(( ↾ (dom ∩ dom 𝑔))‘𝑎) = (𝑎𝐺(( ↾ (dom ∩ dom 𝑔)) ↾ Pred(𝑅, (dom ∩ dom 𝑔), 𝑎)))))
34 incom 4105 . . . . . . . . . . . 12 (dom 𝑔 ∩ dom ) = (dom ∩ dom 𝑔)
3534reseq2i 5738 . . . . . . . . . . 11 ( ↾ (dom 𝑔 ∩ dom )) = ( ↾ (dom ∩ dom 𝑔))
36 fneq12 6326 . . . . . . . . . . 11 ((( ↾ (dom 𝑔 ∩ dom )) = ( ↾ (dom ∩ dom 𝑔)) ∧ (dom 𝑔 ∩ dom ) = (dom ∩ dom 𝑔)) → (( ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ↔ ( ↾ (dom ∩ dom 𝑔)) Fn (dom ∩ dom 𝑔)))
3735, 34, 36mp2an 688 . . . . . . . . . 10 (( ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ↔ ( ↾ (dom ∩ dom 𝑔)) Fn (dom ∩ dom 𝑔))
3835fveq1i 6546 . . . . . . . . . . . 12 (( ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (( ↾ (dom ∩ dom 𝑔))‘𝑎)
39 predeq2 6033 . . . . . . . . . . . . . . 15 ((dom 𝑔 ∩ dom ) = (dom ∩ dom 𝑔) → Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎) = Pred(𝑅, (dom ∩ dom 𝑔), 𝑎))
4034, 39ax-mp 5 . . . . . . . . . . . . . 14 Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎) = Pred(𝑅, (dom ∩ dom 𝑔), 𝑎)
4135, 40reseq12i 5739 . . . . . . . . . . . . 13 (( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎)) = (( ↾ (dom ∩ dom 𝑔)) ↾ Pred(𝑅, (dom ∩ dom 𝑔), 𝑎))
4241oveq2i 7034 . . . . . . . . . . . 12 (𝑎𝐺(( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎))) = (𝑎𝐺(( ↾ (dom ∩ dom 𝑔)) ↾ Pred(𝑅, (dom ∩ dom 𝑔), 𝑎)))
4338, 42eqeq12i 2811 . . . . . . . . . . 11 ((( ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺(( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎))) ↔ (( ↾ (dom ∩ dom 𝑔))‘𝑎) = (𝑎𝐺(( ↾ (dom ∩ dom 𝑔)) ↾ Pred(𝑅, (dom ∩ dom 𝑔), 𝑎))))
4434, 43raleqbii 3200 . . . . . . . . . 10 (∀𝑎 ∈ (dom 𝑔 ∩ dom )(( ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺(( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎))) ↔ ∀𝑎 ∈ (dom ∩ dom 𝑔)(( ↾ (dom ∩ dom 𝑔))‘𝑎) = (𝑎𝐺(( ↾ (dom ∩ dom 𝑔)) ↾ Pred(𝑅, (dom ∩ dom 𝑔), 𝑎))))
4537, 44anbi12i 626 . . . . . . . . 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 𝑔), 𝑎)))))
4633, 45sylibr 235 . . . . . . . 8 ((𝐵𝑔𝐵) → (( ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ∧ ∀𝑎 ∈ (dom 𝑔 ∩ dom )(( ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺(( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎)))))
4746ancoms 459 . . . . . . 7 ((𝑔𝐵𝐵) → (( ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ∧ ∀𝑎 ∈ (dom 𝑔 ∩ dom )(( ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺(( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎)))))
4847adantl 482 . . . . . 6 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → (( ↾ (dom 𝑔 ∩ dom )) Fn (dom 𝑔 ∩ dom ) ∧ ∀𝑎 ∈ (dom 𝑔 ∩ dom )(( ↾ (dom 𝑔 ∩ dom ))‘𝑎) = (𝑎𝐺(( ↾ (dom 𝑔 ∩ dom )) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ), 𝑎)))))
49 fpr3g 32733 . . . . . 6 (((𝑅 Fr (dom 𝑔 ∩ dom ) ∧ 𝑅 Po (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 )))
5024, 27, 30, 32, 48, 49syl311anc 1377 . . . . 5 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → (𝑔 ↾ (dom 𝑔 ∩ dom )) = ( ↾ (dom 𝑔 ∩ dom )))
5150breqd 4979 . . . 4 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → (𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣𝑥( ↾ (dom 𝑔 ∩ dom ))𝑣))
5251biimprd 249 . . 3 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → (𝑥( ↾ (dom 𝑔 ∩ dom ))𝑣𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣))
5317frrlem2 32735 . . . . 5 (𝑔𝐵 → Fun 𝑔)
5453ad2antrl 724 . . . 4 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → Fun 𝑔)
55 funres 6274 . . . 4 (Fun 𝑔 → Fun (𝑔 ↾ (dom 𝑔 ∩ dom )))
56 dffun2 6242 . . . . 5 (Fun (𝑔 ↾ (dom 𝑔 ∩ dom )) ↔ (Rel (𝑔 ↾ (dom 𝑔 ∩ dom )) ∧ ∀𝑥𝑢𝑣((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣)))
57 2sp 2151 . . . . . 6 (∀𝑢𝑣((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣) → ((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣))
5857sps 2150 . . . . 5 (∀𝑥𝑢𝑣((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣) → ((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣))
5956, 58simplbiim 505 . . . 4 (Fun (𝑔 ↾ (dom 𝑔 ∩ dom )) → ((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣))
6054, 55, 593syl 18 . . 3 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → ((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣))
6152, 60sylan2d 604 . 2 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → ((𝑥(𝑔 ↾ (dom 𝑔 ∩ dom ))𝑢𝑥( ↾ (dom 𝑔 ∩ dom ))𝑣) → 𝑢 = 𝑣))
6215, 61syl5 34 1 (((𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴) ∧ (𝑔𝐵𝐵)) → ((𝑥𝑔𝑢𝑥𝑣) → 𝑢 = 𝑣))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 207  wa 396  w3a 1080  wal 1523   = wceq 1525  wex 1765  wcel 2083  {cab 2777  wral 3107  cin 3864  wss 3865   class class class wbr 4968   Po wpo 5367   Fr wfr 5406   Se wse 5407  dom cdm 5450  cres 5452  Rel wrel 5455  Predcpred 6029  Fun wfun 6226   Fn wfn 6227  cfv 6232  (class class class)co 7023  frecscfrecs 32728
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1781  ax-4 1795  ax-5 1892  ax-6 1951  ax-7 1996  ax-8 2085  ax-9 2093  ax-10 2114  ax-11 2128  ax-12 2143  ax-13 2346  ax-ext 2771  ax-sep 5101  ax-nul 5108  ax-pow 5164  ax-pr 5228
This theorem depends on definitions:  df-bi 208  df-an 397  df-or 843  df-3an 1082  df-tru 1528  df-ex 1766  df-nf 1770  df-sb 2045  df-mo 2578  df-eu 2614  df-clab 2778  df-cleq 2790  df-clel 2865  df-nfc 2937  df-ne 2987  df-ral 3112  df-rex 3113  df-rab 3116  df-v 3442  df-sbc 3712  df-csb 3818  df-dif 3868  df-un 3870  df-in 3872  df-ss 3880  df-nul 4218  df-if 4388  df-sn 4479  df-pr 4481  df-op 4485  df-uni 4752  df-br 4969  df-opab 5031  df-mpt 5048  df-id 5355  df-po 5369  df-fr 5409  df-se 5410  df-xp 5456  df-rel 5457  df-cnv 5458  df-co 5459  df-dm 5460  df-rn 5461  df-res 5462  df-ima 5463  df-pred 6030  df-iota 6196  df-fun 6234  df-fn 6235  df-fv 6240  df-ov 7026
This theorem is referenced by:  fpr1  32750  fpr2  32751
  Copyright terms: Public domain W3C validator