Metamath Proof Explorer


Theorem tfrlem5

Description: Lemma for transfinite recursion. The values of two acceptable functions are the same within their domains. (Contributed by NM, 9-Apr-1995) (Revised by Mario Carneiro, 24-May-2019)

Ref Expression
Hypothesis tfrlem.1 𝐴 = { 𝑓 ∣ ∃ 𝑥 ∈ On ( 𝑓 Fn 𝑥 ∧ ∀ 𝑦𝑥 ( 𝑓𝑦 ) = ( 𝐹 ‘ ( 𝑓𝑦 ) ) ) }
Assertion tfrlem5 ( ( 𝑔𝐴𝐴 ) → ( ( 𝑥 𝑔 𝑢𝑥 𝑣 ) → 𝑢 = 𝑣 ) )

Proof

Step Hyp Ref Expression
1 tfrlem.1 𝐴 = { 𝑓 ∣ ∃ 𝑥 ∈ On ( 𝑓 Fn 𝑥 ∧ ∀ 𝑦𝑥 ( 𝑓𝑦 ) = ( 𝐹 ‘ ( 𝑓𝑦 ) ) ) }
2 vex 𝑔 ∈ V
3 1 2 tfrlem3a ( 𝑔𝐴 ↔ ∃ 𝑧 ∈ On ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) )
4 vex ∈ V
5 1 4 tfrlem3a ( 𝐴 ↔ ∃ 𝑤 ∈ On ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) )
6 reeanv ( ∃ 𝑧 ∈ On ∃ 𝑤 ∈ On ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ↔ ( ∃ 𝑧 ∈ On ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ∃ 𝑤 ∈ On ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) )
7 fveq2 ( 𝑎 = 𝑥 → ( 𝑔𝑎 ) = ( 𝑔𝑥 ) )
8 fveq2 ( 𝑎 = 𝑥 → ( 𝑎 ) = ( 𝑥 ) )
9 7 8 eqeq12d ( 𝑎 = 𝑥 → ( ( 𝑔𝑎 ) = ( 𝑎 ) ↔ ( 𝑔𝑥 ) = ( 𝑥 ) ) )
10 onin ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) → ( 𝑧𝑤 ) ∈ On )
11 10 3ad2ant1 ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → ( 𝑧𝑤 ) ∈ On )
12 simp2ll ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → 𝑔 Fn 𝑧 )
13 fnfun ( 𝑔 Fn 𝑧 → Fun 𝑔 )
14 12 13 syl ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → Fun 𝑔 )
15 inss1 ( 𝑧𝑤 ) ⊆ 𝑧
16 fndm ( 𝑔 Fn 𝑧 → dom 𝑔 = 𝑧 )
17 12 16 syl ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → dom 𝑔 = 𝑧 )
18 15 17 sseqtrrid ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → ( 𝑧𝑤 ) ⊆ dom 𝑔 )
19 14 18 jca ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → ( Fun 𝑔 ∧ ( 𝑧𝑤 ) ⊆ dom 𝑔 ) )
20 simp2rl ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → Fn 𝑤 )
21 fnfun ( Fn 𝑤 → Fun )
22 20 21 syl ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → Fun )
23 inss2 ( 𝑧𝑤 ) ⊆ 𝑤
24 fndm ( Fn 𝑤 → dom = 𝑤 )
25 20 24 syl ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → dom = 𝑤 )
26 23 25 sseqtrrid ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → ( 𝑧𝑤 ) ⊆ dom )
27 22 26 jca ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → ( Fun ∧ ( 𝑧𝑤 ) ⊆ dom ) )
28 simp2lr ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) )
29 ssralv ( ( 𝑧𝑤 ) ⊆ 𝑧 → ( ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) → ∀ 𝑎 ∈ ( 𝑧𝑤 ) ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) )
30 15 28 29 mpsyl ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → ∀ 𝑎 ∈ ( 𝑧𝑤 ) ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) )
31 simp2rr ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) )
32 ssralv ( ( 𝑧𝑤 ) ⊆ 𝑤 → ( ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) → ∀ 𝑎 ∈ ( 𝑧𝑤 ) ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) )
33 23 31 32 mpsyl ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → ∀ 𝑎 ∈ ( 𝑧𝑤 ) ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) )
34 11 19 27 30 33 tfrlem1 ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → ∀ 𝑎 ∈ ( 𝑧𝑤 ) ( 𝑔𝑎 ) = ( 𝑎 ) )
35 simp3l ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → 𝑥 𝑔 𝑢 )
36 fnbr ( ( 𝑔 Fn 𝑧𝑥 𝑔 𝑢 ) → 𝑥𝑧 )
37 12 35 36 syl2anc ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → 𝑥𝑧 )
38 simp3r ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → 𝑥 𝑣 )
39 fnbr ( ( Fn 𝑤𝑥 𝑣 ) → 𝑥𝑤 )
40 20 38 39 syl2anc ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → 𝑥𝑤 )
41 37 40 elind ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → 𝑥 ∈ ( 𝑧𝑤 ) )
42 9 34 41 rspcdva ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → ( 𝑔𝑥 ) = ( 𝑥 ) )
43 funbrfv ( Fun 𝑔 → ( 𝑥 𝑔 𝑢 → ( 𝑔𝑥 ) = 𝑢 ) )
44 14 35 43 sylc ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → ( 𝑔𝑥 ) = 𝑢 )
45 funbrfv ( Fun → ( 𝑥 𝑣 → ( 𝑥 ) = 𝑣 ) )
46 22 38 45 sylc ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → ( 𝑥 ) = 𝑣 )
47 42 44 46 3eqtr3d ( ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) ∧ ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) ∧ ( 𝑥 𝑔 𝑢𝑥 𝑣 ) ) → 𝑢 = 𝑣 )
48 47 3exp ( ( 𝑧 ∈ On ∧ 𝑤 ∈ On ) → ( ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) → ( ( 𝑥 𝑔 𝑢𝑥 𝑣 ) → 𝑢 = 𝑣 ) ) )
49 48 rexlimivv ( ∃ 𝑧 ∈ On ∃ 𝑤 ∈ On ( ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) → ( ( 𝑥 𝑔 𝑢𝑥 𝑣 ) → 𝑢 = 𝑣 ) )
50 6 49 sylbir ( ( ∃ 𝑧 ∈ On ( 𝑔 Fn 𝑧 ∧ ∀ 𝑎𝑧 ( 𝑔𝑎 ) = ( 𝐹 ‘ ( 𝑔𝑎 ) ) ) ∧ ∃ 𝑤 ∈ On ( Fn 𝑤 ∧ ∀ 𝑎𝑤 ( 𝑎 ) = ( 𝐹 ‘ ( 𝑎 ) ) ) ) → ( ( 𝑥 𝑔 𝑢𝑥 𝑣 ) → 𝑢 = 𝑣 ) )
51 3 5 50 syl2anb ( ( 𝑔𝐴𝐴 ) → ( ( 𝑥 𝑔 𝑢𝑥 𝑣 ) → 𝑢 = 𝑣 ) )