ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  tfrcllemres GIF version

Theorem tfrcllemres 6031
Description: Lemma for tfr1on 6019. Recursion is defined on an ordinal if the characteristic function is defined up to a suitable point. (Contributed by Jim Kingdon, 18-Mar-2022.)
Hypotheses
Ref Expression
tfrcl.f 𝐹 = recs(𝐺)
tfrcl.g (𝜑 → Fun 𝐺)
tfrcl.x (𝜑 → Ord 𝑋)
tfrcl.ex ((𝜑𝑥𝑋𝑓:𝑥𝑆) → (𝐺𝑓) ∈ 𝑆)
tfrcllemsucfn.1 𝐴 = {𝑓 ∣ ∃𝑥𝑋 (𝑓:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐺‘(𝑓𝑦)))}
tfrcllemres.u ((𝜑𝑥 𝑋) → suc 𝑥𝑋)
tfrcllemres.yx (𝜑𝑌𝑋)
Assertion
Ref Expression
tfrcllemres (𝜑𝑌 ⊆ dom 𝐹)
Distinct variable groups:   𝑥,𝐴,𝑦   𝑓,𝐺,𝑥,𝑦   𝑆,𝑓,𝑥,𝑦   𝑓,𝑋,𝑥,𝑦   𝑓,𝑌,𝑥,𝑦   𝜑,𝑓,𝑥,𝑦
Allowed substitution hints:   𝐴(𝑓)   𝐹(𝑥,𝑦,𝑓)

Proof of Theorem tfrcllemres
Dummy variables 𝑔 𝑧 𝑢 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 tfrcl.x . . . . . . . . . 10 (𝜑 → Ord 𝑋)
21adantr 270 . . . . . . . . 9 ((𝜑𝑧𝑌) → Ord 𝑋)
3 simpr 108 . . . . . . . . . 10 ((𝜑𝑧𝑌) → 𝑧𝑌)
4 tfrcllemres.yx . . . . . . . . . . 11 (𝜑𝑌𝑋)
54adantr 270 . . . . . . . . . 10 ((𝜑𝑧𝑌) → 𝑌𝑋)
63, 5jca 300 . . . . . . . . 9 ((𝜑𝑧𝑌) → (𝑧𝑌𝑌𝑋))
7 ordtr1 4171 . . . . . . . . 9 (Ord 𝑋 → ((𝑧𝑌𝑌𝑋) → 𝑧𝑋))
82, 6, 7sylc 61 . . . . . . . 8 ((𝜑𝑧𝑌) → 𝑧𝑋)
9 tfrcl.f . . . . . . . . 9 𝐹 = recs(𝐺)
10 tfrcl.g . . . . . . . . 9 (𝜑 → Fun 𝐺)
11 tfrcl.ex . . . . . . . . 9 ((𝜑𝑥𝑋𝑓:𝑥𝑆) → (𝐺𝑓) ∈ 𝑆)
12 tfrcllemsucfn.1 . . . . . . . . 9 𝐴 = {𝑓 ∣ ∃𝑥𝑋 (𝑓:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐺‘(𝑓𝑦)))}
13 tfrcllemres.u . . . . . . . . 9 ((𝜑𝑥 𝑋) → suc 𝑥𝑋)
149, 10, 1, 11, 12, 13tfrcllemaccex 6030 . . . . . . . 8 ((𝜑𝑧𝑋) → ∃𝑔(𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢))))
158, 14syldan 276 . . . . . . 7 ((𝜑𝑧𝑌) → ∃𝑔(𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢))))
1610ad2antrr 472 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → Fun 𝐺)
171ad2antrr 472 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → Ord 𝑋)
18113adant1r 1163 . . . . . . . . . 10 (((𝜑𝑧𝑌) ∧ 𝑥𝑋𝑓:𝑥𝑆) → (𝐺𝑓) ∈ 𝑆)
19183adant1r 1163 . . . . . . . . 9 ((((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) ∧ 𝑥𝑋𝑓:𝑥𝑆) → (𝐺𝑓) ∈ 𝑆)
204ad2antrr 472 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑌𝑋)
213adantr 270 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑧𝑌)
2213adantlr 461 . . . . . . . . . 10 (((𝜑𝑧𝑌) ∧ 𝑥 𝑋) → suc 𝑥𝑋)
2322adantlr 461 . . . . . . . . 9 ((((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) ∧ 𝑥 𝑋) → suc 𝑥𝑋)
24 simprl 498 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑔:𝑧𝑆)
25 feq2 5082 . . . . . . . . . . . . . 14 (𝑥 = 𝑧 → (𝑔:𝑥𝑆𝑔:𝑧𝑆))
26 raleq 2554 . . . . . . . . . . . . . 14 (𝑥 = 𝑧 → (∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦)) ↔ ∀𝑦𝑧 (𝑔𝑦) = (𝐺‘(𝑔𝑦))))
2725, 26anbi12d 457 . . . . . . . . . . . . 13 (𝑥 = 𝑧 → ((𝑔:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦))) ↔ (𝑔:𝑧𝑆 ∧ ∀𝑦𝑧 (𝑔𝑦) = (𝐺‘(𝑔𝑦)))))
28 fveq2 5229 . . . . . . . . . . . . . . . 16 (𝑦 = 𝑢 → (𝑔𝑦) = (𝑔𝑢))
29 reseq2 4655 . . . . . . . . . . . . . . . . 17 (𝑦 = 𝑢 → (𝑔𝑦) = (𝑔𝑢))
3029fveq2d 5233 . . . . . . . . . . . . . . . 16 (𝑦 = 𝑢 → (𝐺‘(𝑔𝑦)) = (𝐺‘(𝑔𝑢)))
3128, 30eqeq12d 2097 . . . . . . . . . . . . . . 15 (𝑦 = 𝑢 → ((𝑔𝑦) = (𝐺‘(𝑔𝑦)) ↔ (𝑔𝑢) = (𝐺‘(𝑔𝑢))))
3231cbvralv 2582 . . . . . . . . . . . . . 14 (∀𝑦𝑧 (𝑔𝑦) = (𝐺‘(𝑔𝑦)) ↔ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))
3332anbi2i 445 . . . . . . . . . . . . 13 ((𝑔:𝑧𝑆 ∧ ∀𝑦𝑧 (𝑔𝑦) = (𝐺‘(𝑔𝑦))) ↔ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢))))
3427, 33syl6bb 194 . . . . . . . . . . . 12 (𝑥 = 𝑧 → ((𝑔:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦))) ↔ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))))
3534rspcev 2710 . . . . . . . . . . 11 ((𝑧𝑋 ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ∃𝑥𝑋 (𝑔:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦))))
368, 35sylan 277 . . . . . . . . . 10 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ∃𝑥𝑋 (𝑔:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦))))
37 vex 2613 . . . . . . . . . . 11 𝑔 ∈ V
38 feq1 5081 . . . . . . . . . . . . 13 (𝑓 = 𝑔 → (𝑓:𝑥𝑆𝑔:𝑥𝑆))
39 fveq1 5228 . . . . . . . . . . . . . . 15 (𝑓 = 𝑔 → (𝑓𝑦) = (𝑔𝑦))
40 reseq1 4654 . . . . . . . . . . . . . . . 16 (𝑓 = 𝑔 → (𝑓𝑦) = (𝑔𝑦))
4140fveq2d 5233 . . . . . . . . . . . . . . 15 (𝑓 = 𝑔 → (𝐺‘(𝑓𝑦)) = (𝐺‘(𝑔𝑦)))
4239, 41eqeq12d 2097 . . . . . . . . . . . . . 14 (𝑓 = 𝑔 → ((𝑓𝑦) = (𝐺‘(𝑓𝑦)) ↔ (𝑔𝑦) = (𝐺‘(𝑔𝑦))))
4342ralbidv 2373 . . . . . . . . . . . . 13 (𝑓 = 𝑔 → (∀𝑦𝑥 (𝑓𝑦) = (𝐺‘(𝑓𝑦)) ↔ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦))))
4438, 43anbi12d 457 . . . . . . . . . . . 12 (𝑓 = 𝑔 → ((𝑓:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐺‘(𝑓𝑦))) ↔ (𝑔:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦)))))
4544rexbidv 2374 . . . . . . . . . . 11 (𝑓 = 𝑔 → (∃𝑥𝑋 (𝑓:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐺‘(𝑓𝑦))) ↔ ∃𝑥𝑋 (𝑔:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦)))))
4637, 45, 12elab2 2749 . . . . . . . . . 10 (𝑔𝐴 ↔ ∃𝑥𝑋 (𝑔:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦))))
4736, 46sylibr 132 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑔𝐴)
489, 16, 17, 19, 12, 20, 21, 23, 24, 47tfrcllemsucaccv 6023 . . . . . . . 8 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) ∈ 𝐴)
49 vex 2613 . . . . . . . . . . 11 𝑧 ∈ V
5025imbi1d 229 . . . . . . . . . . . . . 14 (𝑥 = 𝑧 → ((𝑔:𝑥𝑆 → (𝐺𝑔) ∈ 𝑆) ↔ (𝑔:𝑧𝑆 → (𝐺𝑔) ∈ 𝑆)))
51113expia 1141 . . . . . . . . . . . . . . . . . 18 ((𝜑𝑥𝑋) → (𝑓:𝑥𝑆 → (𝐺𝑓) ∈ 𝑆))
5251alrimiv 1797 . . . . . . . . . . . . . . . . 17 ((𝜑𝑥𝑋) → ∀𝑓(𝑓:𝑥𝑆 → (𝐺𝑓) ∈ 𝑆))
53 fveq2 5229 . . . . . . . . . . . . . . . . . . . 20 (𝑓 = 𝑔 → (𝐺𝑓) = (𝐺𝑔))
5453eleq1d 2151 . . . . . . . . . . . . . . . . . . 19 (𝑓 = 𝑔 → ((𝐺𝑓) ∈ 𝑆 ↔ (𝐺𝑔) ∈ 𝑆))
5538, 54imbi12d 232 . . . . . . . . . . . . . . . . . 18 (𝑓 = 𝑔 → ((𝑓:𝑥𝑆 → (𝐺𝑓) ∈ 𝑆) ↔ (𝑔:𝑥𝑆 → (𝐺𝑔) ∈ 𝑆)))
5655spv 1783 . . . . . . . . . . . . . . . . 17 (∀𝑓(𝑓:𝑥𝑆 → (𝐺𝑓) ∈ 𝑆) → (𝑔:𝑥𝑆 → (𝐺𝑔) ∈ 𝑆))
5752, 56syl 14 . . . . . . . . . . . . . . . 16 ((𝜑𝑥𝑋) → (𝑔:𝑥𝑆 → (𝐺𝑔) ∈ 𝑆))
5857ralrimiva 2439 . . . . . . . . . . . . . . 15 (𝜑 → ∀𝑥𝑋 (𝑔:𝑥𝑆 → (𝐺𝑔) ∈ 𝑆))
5958adantr 270 . . . . . . . . . . . . . 14 ((𝜑𝑧𝑌) → ∀𝑥𝑋 (𝑔:𝑥𝑆 → (𝐺𝑔) ∈ 𝑆))
6050, 59, 8rspcdva 2715 . . . . . . . . . . . . 13 ((𝜑𝑧𝑌) → (𝑔:𝑧𝑆 → (𝐺𝑔) ∈ 𝑆))
6160imp 122 . . . . . . . . . . . 12 (((𝜑𝑧𝑌) ∧ 𝑔:𝑧𝑆) → (𝐺𝑔) ∈ 𝑆)
6224, 61syldan 276 . . . . . . . . . . 11 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → (𝐺𝑔) ∈ 𝑆)
63 opexg 4011 . . . . . . . . . . 11 ((𝑧 ∈ V ∧ (𝐺𝑔) ∈ 𝑆) → ⟨𝑧, (𝐺𝑔)⟩ ∈ V)
6449, 62, 63sylancr 405 . . . . . . . . . 10 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ⟨𝑧, (𝐺𝑔)⟩ ∈ V)
65 snidg 3441 . . . . . . . . . 10 (⟨𝑧, (𝐺𝑔)⟩ ∈ V → ⟨𝑧, (𝐺𝑔)⟩ ∈ {⟨𝑧, (𝐺𝑔)⟩})
66 elun2 3150 . . . . . . . . . 10 (⟨𝑧, (𝐺𝑔)⟩ ∈ {⟨𝑧, (𝐺𝑔)⟩} → ⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}))
6764, 65, 663syl 17 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}))
68 opeldmg 4588 . . . . . . . . . 10 ((𝑧 ∈ V ∧ (𝐺𝑔) ∈ 𝑆) → (⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) → 𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩})))
6949, 62, 68sylancr 405 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → (⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) → 𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩})))
7067, 69mpd 13 . . . . . . . 8 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}))
71 dmeq 4583 . . . . . . . . . 10 ( = (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) → dom = dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}))
7271eleq2d 2152 . . . . . . . . 9 ( = (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) → (𝑧 ∈ dom 𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩})))
7372rspcev 2710 . . . . . . . 8 (((𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) ∈ 𝐴𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩})) → ∃𝐴 𝑧 ∈ dom )
7448, 70, 73syl2anc 403 . . . . . . 7 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ∃𝐴 𝑧 ∈ dom )
7515, 74exlimddv 1821 . . . . . 6 ((𝜑𝑧𝑌) → ∃𝐴 𝑧 ∈ dom )
76 eliun 3702 . . . . . 6 (𝑧 𝐴 dom ↔ ∃𝐴 𝑧 ∈ dom )
7775, 76sylibr 132 . . . . 5 ((𝜑𝑧𝑌) → 𝑧 𝐴 dom )
7877ex 113 . . . 4 (𝜑 → (𝑧𝑌𝑧 𝐴 dom ))
7978ssrdv 3014 . . 3 (𝜑𝑌 𝐴 dom )
80 dmuni 4593 . . . 4 dom 𝐴 = 𝐴 dom
8112, 1tfrcllemssrecs 6021 . . . . 5 (𝜑 𝐴 ⊆ recs(𝐺))
82 dmss 4582 . . . . 5 ( 𝐴 ⊆ recs(𝐺) → dom 𝐴 ⊆ dom recs(𝐺))
8381, 82syl 14 . . . 4 (𝜑 → dom 𝐴 ⊆ dom recs(𝐺))
8480, 83syl5eqssr 3053 . . 3 (𝜑 𝐴 dom ⊆ dom recs(𝐺))
8579, 84sstrd 3018 . 2 (𝜑𝑌 ⊆ dom recs(𝐺))
869dmeqi 4584 . 2 dom 𝐹 = dom recs(𝐺)
8785, 86syl6sseqr 3055 1 (𝜑𝑌 ⊆ dom 𝐹)
Colors of variables: wff set class
Syntax hints:  wi 4  wa 102  w3a 920  wal 1283   = wceq 1285  wex 1422  wcel 1434  {cab 2069  wral 2353  wrex 2354  Vcvv 2610  cun 2980  wss 2982  {csn 3416  cop 3419   cuni 3621   ciun 3698  Ord word 4145  suc csuc 4148  dom cdm 4391  cres 4393  Fun wfun 4946  wf 4948  cfv 4952  recscrecs 5973
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 104  ax-ia2 105  ax-ia3 106  ax-in1 577  ax-in2 578  ax-io 663  ax-5 1377  ax-7 1378  ax-gen 1379  ax-ie1 1423  ax-ie2 1424  ax-8 1436  ax-10 1437  ax-11 1438  ax-i12 1439  ax-bndl 1440  ax-4 1441  ax-13 1445  ax-14 1446  ax-17 1460  ax-i9 1464  ax-ial 1468  ax-i5r 1469  ax-ext 2065  ax-coll 3913  ax-sep 3916  ax-pow 3968  ax-pr 3992  ax-un 4216  ax-setind 4308
This theorem depends on definitions:  df-bi 115  df-3an 922  df-tru 1288  df-fal 1291  df-nf 1391  df-sb 1688  df-eu 1946  df-mo 1947  df-clab 2070  df-cleq 2076  df-clel 2079  df-nfc 2212  df-ne 2250  df-ral 2358  df-rex 2359  df-reu 2360  df-rab 2362  df-v 2612  df-sbc 2825  df-csb 2918  df-dif 2984  df-un 2986  df-in 2988  df-ss 2995  df-nul 3268  df-pw 3402  df-sn 3422  df-pr 3423  df-op 3425  df-uni 3622  df-iun 3700  df-br 3806  df-opab 3860  df-mpt 3861  df-tr 3896  df-id 4076  df-iord 4149  df-on 4151  df-suc 4154  df-xp 4397  df-rel 4398  df-cnv 4399  df-co 4400  df-dm 4401  df-rn 4402  df-res 4403  df-ima 4404  df-iota 4917  df-fun 4954  df-fn 4955  df-f 4956  df-f1 4957  df-fo 4958  df-f1o 4959  df-fv 4960  df-recs 5974
This theorem is referenced by:  tfrcldm  6032
  Copyright terms: Public domain W3C validator