Metamath Proof Explorer


Theorem fprlem1

Description: Lemma for well-founded recursion with a partial order. Two acceptable functions are compatible. (Contributed by Scott Fenton, 11-Sep-2023)

Ref Expression
Hypotheses fprlem.1 𝐵 = { 𝑓 ∣ ∃ 𝑥 ( 𝑓 Fn 𝑥 ∧ ( 𝑥𝐴 ∧ ∀ 𝑦𝑥 Pred ( 𝑅 , 𝐴 , 𝑦 ) ⊆ 𝑥 ) ∧ ∀ 𝑦𝑥 ( 𝑓𝑦 ) = ( 𝑦 𝐺 ( 𝑓 ↾ Pred ( 𝑅 , 𝐴 , 𝑦 ) ) ) ) }
fprlem.2 𝐹 = frecs ( 𝑅 , 𝐴 , 𝐺 )
Assertion fprlem1 ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → ( ( 𝑥 𝑔 𝑢𝑥 𝑣 ) → 𝑢 = 𝑣 ) )

Proof

Step Hyp Ref Expression
1 fprlem.1 𝐵 = { 𝑓 ∣ ∃ 𝑥 ( 𝑓 Fn 𝑥 ∧ ( 𝑥𝐴 ∧ ∀ 𝑦𝑥 Pred ( 𝑅 , 𝐴 , 𝑦 ) ⊆ 𝑥 ) ∧ ∀ 𝑦𝑥 ( 𝑓𝑦 ) = ( 𝑦 𝐺 ( 𝑓 ↾ Pred ( 𝑅 , 𝐴 , 𝑦 ) ) ) ) }
2 fprlem.2 𝐹 = frecs ( 𝑅 , 𝐴 , 𝐺 )
3 vex 𝑥 ∈ V
4 vex 𝑢 ∈ V
5 3 4 breldm ( 𝑥 𝑔 𝑢𝑥 ∈ dom 𝑔 )
6 vex 𝑣 ∈ V
7 3 6 breldm ( 𝑥 𝑣𝑥 ∈ dom )
8 elin ( 𝑥 ∈ ( dom 𝑔 ∩ dom ) ↔ ( 𝑥 ∈ dom 𝑔𝑥 ∈ dom ) )
9 8 biimpri ( ( 𝑥 ∈ dom 𝑔𝑥 ∈ dom ) → 𝑥 ∈ ( dom 𝑔 ∩ dom ) )
10 5 7 9 syl2an ( ( 𝑥 𝑔 𝑢𝑥 𝑣 ) → 𝑥 ∈ ( dom 𝑔 ∩ dom ) )
11 id ( ( 𝑥 𝑔 𝑢𝑥 𝑣 ) → ( 𝑥 𝑔 𝑢𝑥 𝑣 ) )
12 4 brresi ( 𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑢 ↔ ( 𝑥 ∈ ( dom 𝑔 ∩ dom ) ∧ 𝑥 𝑔 𝑢 ) )
13 6 brresi ( 𝑥 ( ↾ ( dom 𝑔 ∩ dom ) ) 𝑣 ↔ ( 𝑥 ∈ ( dom 𝑔 ∩ dom ) ∧ 𝑥 𝑣 ) )
14 12 13 anbi12i ( ( 𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑢𝑥 ( ↾ ( dom 𝑔 ∩ dom ) ) 𝑣 ) ↔ ( ( 𝑥 ∈ ( dom 𝑔 ∩ dom ) ∧ 𝑥 𝑔 𝑢 ) ∧ ( 𝑥 ∈ ( dom 𝑔 ∩ dom ) ∧ 𝑥 𝑣 ) ) )
15 an4 ( ( ( 𝑥 ∈ ( dom 𝑔 ∩ dom ) ∧ 𝑥 𝑔 𝑢 ) ∧ ( 𝑥 ∈ ( dom 𝑔 ∩ dom ) ∧ 𝑥 𝑣 ) ) ↔ ( ( 𝑥 ∈ ( dom 𝑔 ∩ dom ) ∧ 𝑥 ∈ ( dom 𝑔 ∩ dom ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) )
16 14 15 bitri ( ( 𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑢𝑥 ( ↾ ( dom 𝑔 ∩ dom ) ) 𝑣 ) ↔ ( ( 𝑥 ∈ ( dom 𝑔 ∩ dom ) ∧ 𝑥 ∈ ( dom 𝑔 ∩ dom ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) )
17 10 10 11 16 syl21anbrc ( ( 𝑥 𝑔 𝑢𝑥 𝑣 ) → ( 𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑢𝑥 ( ↾ ( dom 𝑔 ∩ dom ) ) 𝑣 ) )
18 inss2 ( dom 𝑔 ∩ dom ) ⊆ dom
19 1 frrlem3 ( 𝐵 → dom 𝐴 )
20 18 19 sstrid ( 𝐵 → ( dom 𝑔 ∩ dom ) ⊆ 𝐴 )
21 20 adantl ( ( 𝑔𝐵𝐵 ) → ( dom 𝑔 ∩ dom ) ⊆ 𝐴 )
22 21 adantl ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → ( dom 𝑔 ∩ dom ) ⊆ 𝐴 )
23 simpl1 ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → 𝑅 Fr 𝐴 )
24 frss ( ( dom 𝑔 ∩ dom ) ⊆ 𝐴 → ( 𝑅 Fr 𝐴𝑅 Fr ( dom 𝑔 ∩ dom ) ) )
25 22 23 24 sylc ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → 𝑅 Fr ( dom 𝑔 ∩ dom ) )
26 simpl2 ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → 𝑅 Po 𝐴 )
27 poss ( ( dom 𝑔 ∩ dom ) ⊆ 𝐴 → ( 𝑅 Po 𝐴𝑅 Po ( dom 𝑔 ∩ dom ) ) )
28 22 26 27 sylc ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → 𝑅 Po ( dom 𝑔 ∩ dom ) )
29 simpl3 ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → 𝑅 Se 𝐴 )
30 sess2 ( ( dom 𝑔 ∩ dom ) ⊆ 𝐴 → ( 𝑅 Se 𝐴𝑅 Se ( dom 𝑔 ∩ dom ) ) )
31 22 29 30 sylc ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → 𝑅 Se ( dom 𝑔 ∩ dom ) )
32 1 frrlem4 ( ( 𝑔𝐵𝐵 ) → ( ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) Fn ( dom 𝑔 ∩ dom ) ∧ ∀ 𝑎 ∈ ( dom 𝑔 ∩ dom ) ( ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) ‘ 𝑎 ) = ( 𝑎 𝐺 ( ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) ↾ Pred ( 𝑅 , ( dom 𝑔 ∩ dom ) , 𝑎 ) ) ) ) )
33 32 adantl ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → ( ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) Fn ( dom 𝑔 ∩ dom ) ∧ ∀ 𝑎 ∈ ( dom 𝑔 ∩ dom ) ( ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) ‘ 𝑎 ) = ( 𝑎 𝐺 ( ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) ↾ Pred ( 𝑅 , ( dom 𝑔 ∩ dom ) , 𝑎 ) ) ) ) )
34 1 frrlem4 ( ( 𝐵𝑔𝐵 ) → ( ( ↾ ( dom ∩ dom 𝑔 ) ) Fn ( dom ∩ dom 𝑔 ) ∧ ∀ 𝑎 ∈ ( dom ∩ dom 𝑔 ) ( ( ↾ ( dom ∩ dom 𝑔 ) ) ‘ 𝑎 ) = ( 𝑎 𝐺 ( ( ↾ ( dom ∩ dom 𝑔 ) ) ↾ Pred ( 𝑅 , ( dom ∩ dom 𝑔 ) , 𝑎 ) ) ) ) )
35 incom ( dom 𝑔 ∩ dom ) = ( dom ∩ dom 𝑔 )
36 35 reseq2i ( ↾ ( dom 𝑔 ∩ dom ) ) = ( ↾ ( dom ∩ dom 𝑔 ) )
37 fneq12 ( ( ( ↾ ( dom 𝑔 ∩ dom ) ) = ( ↾ ( dom ∩ dom 𝑔 ) ) ∧ ( dom 𝑔 ∩ dom ) = ( dom ∩ dom 𝑔 ) ) → ( ( ↾ ( dom 𝑔 ∩ dom ) ) Fn ( dom 𝑔 ∩ dom ) ↔ ( ↾ ( dom ∩ dom 𝑔 ) ) Fn ( dom ∩ dom 𝑔 ) ) )
38 36 35 37 mp2an ( ( ↾ ( dom 𝑔 ∩ dom ) ) Fn ( dom 𝑔 ∩ dom ) ↔ ( ↾ ( dom ∩ dom 𝑔 ) ) Fn ( dom ∩ dom 𝑔 ) )
39 36 fveq1i ( ( ↾ ( dom 𝑔 ∩ dom ) ) ‘ 𝑎 ) = ( ( ↾ ( dom ∩ dom 𝑔 ) ) ‘ 𝑎 )
40 predeq2 ( ( dom 𝑔 ∩ dom ) = ( dom ∩ dom 𝑔 ) → Pred ( 𝑅 , ( dom 𝑔 ∩ dom ) , 𝑎 ) = Pred ( 𝑅 , ( dom ∩ dom 𝑔 ) , 𝑎 ) )
41 35 40 ax-mp Pred ( 𝑅 , ( dom 𝑔 ∩ dom ) , 𝑎 ) = Pred ( 𝑅 , ( dom ∩ dom 𝑔 ) , 𝑎 )
42 36 41 reseq12i ( ( ↾ ( dom 𝑔 ∩ dom ) ) ↾ Pred ( 𝑅 , ( dom 𝑔 ∩ dom ) , 𝑎 ) ) = ( ( ↾ ( dom ∩ dom 𝑔 ) ) ↾ Pred ( 𝑅 , ( dom ∩ dom 𝑔 ) , 𝑎 ) )
43 42 oveq2i ( 𝑎 𝐺 ( ( ↾ ( dom 𝑔 ∩ dom ) ) ↾ Pred ( 𝑅 , ( dom 𝑔 ∩ dom ) , 𝑎 ) ) ) = ( 𝑎 𝐺 ( ( ↾ ( dom ∩ dom 𝑔 ) ) ↾ Pred ( 𝑅 , ( dom ∩ dom 𝑔 ) , 𝑎 ) ) )
44 39 43 eqeq12i ( ( ( ↾ ( dom 𝑔 ∩ dom ) ) ‘ 𝑎 ) = ( 𝑎 𝐺 ( ( ↾ ( dom 𝑔 ∩ dom ) ) ↾ Pred ( 𝑅 , ( dom 𝑔 ∩ dom ) , 𝑎 ) ) ) ↔ ( ( ↾ ( dom ∩ dom 𝑔 ) ) ‘ 𝑎 ) = ( 𝑎 𝐺 ( ( ↾ ( dom ∩ dom 𝑔 ) ) ↾ Pred ( 𝑅 , ( dom ∩ dom 𝑔 ) , 𝑎 ) ) ) )
45 35 44 raleqbii ( ∀ 𝑎 ∈ ( dom 𝑔 ∩ dom ) ( ( ↾ ( dom 𝑔 ∩ dom ) ) ‘ 𝑎 ) = ( 𝑎 𝐺 ( ( ↾ ( dom 𝑔 ∩ dom ) ) ↾ Pred ( 𝑅 , ( dom 𝑔 ∩ dom ) , 𝑎 ) ) ) ↔ ∀ 𝑎 ∈ ( dom ∩ dom 𝑔 ) ( ( ↾ ( dom ∩ dom 𝑔 ) ) ‘ 𝑎 ) = ( 𝑎 𝐺 ( ( ↾ ( dom ∩ dom 𝑔 ) ) ↾ Pred ( 𝑅 , ( dom ∩ dom 𝑔 ) , 𝑎 ) ) ) )
46 38 45 anbi12i ( ( ( ↾ ( 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 𝑔 ) , 𝑎 ) ) ) ) )
47 34 46 sylibr ( ( 𝐵𝑔𝐵 ) → ( ( ↾ ( dom 𝑔 ∩ dom ) ) Fn ( dom 𝑔 ∩ dom ) ∧ ∀ 𝑎 ∈ ( dom 𝑔 ∩ dom ) ( ( ↾ ( dom 𝑔 ∩ dom ) ) ‘ 𝑎 ) = ( 𝑎 𝐺 ( ( ↾ ( dom 𝑔 ∩ dom ) ) ↾ Pred ( 𝑅 , ( dom 𝑔 ∩ dom ) , 𝑎 ) ) ) ) )
48 47 ancoms ( ( 𝑔𝐵𝐵 ) → ( ( ↾ ( dom 𝑔 ∩ dom ) ) Fn ( dom 𝑔 ∩ dom ) ∧ ∀ 𝑎 ∈ ( dom 𝑔 ∩ dom ) ( ( ↾ ( dom 𝑔 ∩ dom ) ) ‘ 𝑎 ) = ( 𝑎 𝐺 ( ( ↾ ( dom 𝑔 ∩ dom ) ) ↾ Pred ( 𝑅 , ( dom 𝑔 ∩ dom ) , 𝑎 ) ) ) ) )
49 48 adantl ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → ( ( ↾ ( dom 𝑔 ∩ dom ) ) Fn ( dom 𝑔 ∩ dom ) ∧ ∀ 𝑎 ∈ ( dom 𝑔 ∩ dom ) ( ( ↾ ( dom 𝑔 ∩ dom ) ) ‘ 𝑎 ) = ( 𝑎 𝐺 ( ( ↾ ( dom 𝑔 ∩ dom ) ) ↾ Pred ( 𝑅 , ( dom 𝑔 ∩ dom ) , 𝑎 ) ) ) ) )
50 fpr3g ( ( ( 𝑅 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 ) ) )
51 25 28 31 33 49 50 syl311anc ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) = ( ↾ ( dom 𝑔 ∩ dom ) ) )
52 51 breqd ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → ( 𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑣𝑥 ( ↾ ( dom 𝑔 ∩ dom ) ) 𝑣 ) )
53 52 biimprd ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → ( 𝑥 ( ↾ ( dom 𝑔 ∩ dom ) ) 𝑣𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑣 ) )
54 1 frrlem2 ( 𝑔𝐵 → Fun 𝑔 )
55 54 ad2antrl ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → Fun 𝑔 )
56 funres ( Fun 𝑔 → Fun ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) )
57 dffun2 ( Fun ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) ↔ ( Rel ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) ∧ ∀ 𝑥𝑢𝑣 ( ( 𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑢𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑣 ) → 𝑢 = 𝑣 ) ) )
58 2sp ( ∀ 𝑢𝑣 ( ( 𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑢𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑣 ) → 𝑢 = 𝑣 ) → ( ( 𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑢𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑣 ) → 𝑢 = 𝑣 ) )
59 58 sps ( ∀ 𝑥𝑢𝑣 ( ( 𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑢𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑣 ) → 𝑢 = 𝑣 ) → ( ( 𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑢𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑣 ) → 𝑢 = 𝑣 ) )
60 57 59 simplbiim ( Fun ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) → ( ( 𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑢𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑣 ) → 𝑢 = 𝑣 ) )
61 55 56 60 3syl ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → ( ( 𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑢𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑣 ) → 𝑢 = 𝑣 ) )
62 53 61 sylan2d ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → ( ( 𝑥 ( 𝑔 ↾ ( dom 𝑔 ∩ dom ) ) 𝑢𝑥 ( ↾ ( dom 𝑔 ∩ dom ) ) 𝑣 ) → 𝑢 = 𝑣 ) )
63 17 62 syl5 ( ( ( 𝑅 Fr 𝐴𝑅 Po 𝐴𝑅 Se 𝐴 ) ∧ ( 𝑔𝐵𝐵 ) ) → ( ( 𝑥 𝑔 𝑢𝑥 𝑣 ) → 𝑢 = 𝑣 ) )