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

Theorem tfrcllemres 6357
Description: Lemma for tfr1on 6345. 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 276 . . . . . . . . 9 ((𝜑𝑧𝑌) → Ord 𝑋)
3 simpr 110 . . . . . . . . . 10 ((𝜑𝑧𝑌) → 𝑧𝑌)
4 tfrcllemres.yx . . . . . . . . . . 11 (𝜑𝑌𝑋)
54adantr 276 . . . . . . . . . 10 ((𝜑𝑧𝑌) → 𝑌𝑋)
63, 5jca 306 . . . . . . . . 9 ((𝜑𝑧𝑌) → (𝑧𝑌𝑌𝑋))
7 ordtr1 4385 . . . . . . . . 9 (Ord 𝑋 → ((𝑧𝑌𝑌𝑋) → 𝑧𝑋))
82, 6, 7sylc 62 . . . . . . . 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 6356 . . . . . . . 8 ((𝜑𝑧𝑋) → ∃𝑔(𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢))))
158, 14syldan 282 . . . . . . 7 ((𝜑𝑧𝑌) → ∃𝑔(𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢))))
1610ad2antrr 488 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → Fun 𝐺)
171ad2antrr 488 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → Ord 𝑋)
18113adant1r 1231 . . . . . . . . . 10 (((𝜑𝑧𝑌) ∧ 𝑥𝑋𝑓:𝑥𝑆) → (𝐺𝑓) ∈ 𝑆)
19183adant1r 1231 . . . . . . . . 9 ((((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) ∧ 𝑥𝑋𝑓:𝑥𝑆) → (𝐺𝑓) ∈ 𝑆)
204ad2antrr 488 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑌𝑋)
213adantr 276 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑧𝑌)
2213adantlr 477 . . . . . . . . . 10 (((𝜑𝑧𝑌) ∧ 𝑥 𝑋) → suc 𝑥𝑋)
2322adantlr 477 . . . . . . . . 9 ((((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) ∧ 𝑥 𝑋) → suc 𝑥𝑋)
24 simprl 529 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑔:𝑧𝑆)
25 feq2 5345 . . . . . . . . . . . . . 14 (𝑥 = 𝑧 → (𝑔:𝑥𝑆𝑔:𝑧𝑆))
26 raleq 2672 . . . . . . . . . . . . . 14 (𝑥 = 𝑧 → (∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦)) ↔ ∀𝑦𝑧 (𝑔𝑦) = (𝐺‘(𝑔𝑦))))
2725, 26anbi12d 473 . . . . . . . . . . . . 13 (𝑥 = 𝑧 → ((𝑔:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦))) ↔ (𝑔:𝑧𝑆 ∧ ∀𝑦𝑧 (𝑔𝑦) = (𝐺‘(𝑔𝑦)))))
28 fveq2 5511 . . . . . . . . . . . . . . . 16 (𝑦 = 𝑢 → (𝑔𝑦) = (𝑔𝑢))
29 reseq2 4898 . . . . . . . . . . . . . . . . 17 (𝑦 = 𝑢 → (𝑔𝑦) = (𝑔𝑢))
3029fveq2d 5515 . . . . . . . . . . . . . . . 16 (𝑦 = 𝑢 → (𝐺‘(𝑔𝑦)) = (𝐺‘(𝑔𝑢)))
3128, 30eqeq12d 2192 . . . . . . . . . . . . . . 15 (𝑦 = 𝑢 → ((𝑔𝑦) = (𝐺‘(𝑔𝑦)) ↔ (𝑔𝑢) = (𝐺‘(𝑔𝑢))))
3231cbvralv 2703 . . . . . . . . . . . . . 14 (∀𝑦𝑧 (𝑔𝑦) = (𝐺‘(𝑔𝑦)) ↔ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))
3332anbi2i 457 . . . . . . . . . . . . 13 ((𝑔:𝑧𝑆 ∧ ∀𝑦𝑧 (𝑔𝑦) = (𝐺‘(𝑔𝑦))) ↔ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢))))
3427, 33bitrdi 196 . . . . . . . . . . . 12 (𝑥 = 𝑧 → ((𝑔:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦))) ↔ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))))
3534rspcev 2841 . . . . . . . . . . 11 ((𝑧𝑋 ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ∃𝑥𝑋 (𝑔:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦))))
368, 35sylan 283 . . . . . . . . . 10 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ∃𝑥𝑋 (𝑔:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦))))
37 vex 2740 . . . . . . . . . . 11 𝑔 ∈ V
38 feq1 5344 . . . . . . . . . . . . 13 (𝑓 = 𝑔 → (𝑓:𝑥𝑆𝑔:𝑥𝑆))
39 fveq1 5510 . . . . . . . . . . . . . . 15 (𝑓 = 𝑔 → (𝑓𝑦) = (𝑔𝑦))
40 reseq1 4897 . . . . . . . . . . . . . . . 16 (𝑓 = 𝑔 → (𝑓𝑦) = (𝑔𝑦))
4140fveq2d 5515 . . . . . . . . . . . . . . 15 (𝑓 = 𝑔 → (𝐺‘(𝑓𝑦)) = (𝐺‘(𝑔𝑦)))
4239, 41eqeq12d 2192 . . . . . . . . . . . . . 14 (𝑓 = 𝑔 → ((𝑓𝑦) = (𝐺‘(𝑓𝑦)) ↔ (𝑔𝑦) = (𝐺‘(𝑔𝑦))))
4342ralbidv 2477 . . . . . . . . . . . . 13 (𝑓 = 𝑔 → (∀𝑦𝑥 (𝑓𝑦) = (𝐺‘(𝑓𝑦)) ↔ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦))))
4438, 43anbi12d 473 . . . . . . . . . . . 12 (𝑓 = 𝑔 → ((𝑓:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐺‘(𝑓𝑦))) ↔ (𝑔:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦)))))
4544rexbidv 2478 . . . . . . . . . . 11 (𝑓 = 𝑔 → (∃𝑥𝑋 (𝑓:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐺‘(𝑓𝑦))) ↔ ∃𝑥𝑋 (𝑔:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦)))))
4637, 45, 12elab2 2885 . . . . . . . . . 10 (𝑔𝐴 ↔ ∃𝑥𝑋 (𝑔:𝑥𝑆 ∧ ∀𝑦𝑥 (𝑔𝑦) = (𝐺‘(𝑔𝑦))))
4736, 46sylibr 134 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑔𝐴)
489, 16, 17, 19, 12, 20, 21, 23, 24, 47tfrcllemsucaccv 6349 . . . . . . . 8 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) ∈ 𝐴)
49 vex 2740 . . . . . . . . . . 11 𝑧 ∈ V
5025imbi1d 231 . . . . . . . . . . . . . 14 (𝑥 = 𝑧 → ((𝑔:𝑥𝑆 → (𝐺𝑔) ∈ 𝑆) ↔ (𝑔:𝑧𝑆 → (𝐺𝑔) ∈ 𝑆)))
51113expia 1205 . . . . . . . . . . . . . . . . . 18 ((𝜑𝑥𝑋) → (𝑓:𝑥𝑆 → (𝐺𝑓) ∈ 𝑆))
5251alrimiv 1874 . . . . . . . . . . . . . . . . 17 ((𝜑𝑥𝑋) → ∀𝑓(𝑓:𝑥𝑆 → (𝐺𝑓) ∈ 𝑆))
53 fveq2 5511 . . . . . . . . . . . . . . . . . . . 20 (𝑓 = 𝑔 → (𝐺𝑓) = (𝐺𝑔))
5453eleq1d 2246 . . . . . . . . . . . . . . . . . . 19 (𝑓 = 𝑔 → ((𝐺𝑓) ∈ 𝑆 ↔ (𝐺𝑔) ∈ 𝑆))
5538, 54imbi12d 234 . . . . . . . . . . . . . . . . . 18 (𝑓 = 𝑔 → ((𝑓:𝑥𝑆 → (𝐺𝑓) ∈ 𝑆) ↔ (𝑔:𝑥𝑆 → (𝐺𝑔) ∈ 𝑆)))
5655spv 1860 . . . . . . . . . . . . . . . . 17 (∀𝑓(𝑓:𝑥𝑆 → (𝐺𝑓) ∈ 𝑆) → (𝑔:𝑥𝑆 → (𝐺𝑔) ∈ 𝑆))
5752, 56syl 14 . . . . . . . . . . . . . . . 16 ((𝜑𝑥𝑋) → (𝑔:𝑥𝑆 → (𝐺𝑔) ∈ 𝑆))
5857ralrimiva 2550 . . . . . . . . . . . . . . 15 (𝜑 → ∀𝑥𝑋 (𝑔:𝑥𝑆 → (𝐺𝑔) ∈ 𝑆))
5958adantr 276 . . . . . . . . . . . . . 14 ((𝜑𝑧𝑌) → ∀𝑥𝑋 (𝑔:𝑥𝑆 → (𝐺𝑔) ∈ 𝑆))
6050, 59, 8rspcdva 2846 . . . . . . . . . . . . 13 ((𝜑𝑧𝑌) → (𝑔:𝑧𝑆 → (𝐺𝑔) ∈ 𝑆))
6160imp 124 . . . . . . . . . . . 12 (((𝜑𝑧𝑌) ∧ 𝑔:𝑧𝑆) → (𝐺𝑔) ∈ 𝑆)
6224, 61syldan 282 . . . . . . . . . . 11 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → (𝐺𝑔) ∈ 𝑆)
63 opexg 4225 . . . . . . . . . . 11 ((𝑧 ∈ V ∧ (𝐺𝑔) ∈ 𝑆) → ⟨𝑧, (𝐺𝑔)⟩ ∈ V)
6449, 62, 63sylancr 414 . . . . . . . . . 10 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ⟨𝑧, (𝐺𝑔)⟩ ∈ V)
65 snidg 3620 . . . . . . . . . 10 (⟨𝑧, (𝐺𝑔)⟩ ∈ V → ⟨𝑧, (𝐺𝑔)⟩ ∈ {⟨𝑧, (𝐺𝑔)⟩})
66 elun2 3303 . . . . . . . . . 10 (⟨𝑧, (𝐺𝑔)⟩ ∈ {⟨𝑧, (𝐺𝑔)⟩} → ⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}))
6764, 65, 663syl 17 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}))
68 opeldmg 4828 . . . . . . . . . 10 ((𝑧 ∈ V ∧ (𝐺𝑔) ∈ 𝑆) → (⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) → 𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩})))
6949, 62, 68sylancr 414 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → (⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) → 𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩})))
7067, 69mpd 13 . . . . . . . 8 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}))
71 dmeq 4823 . . . . . . . . . 10 ( = (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) → dom = dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}))
7271eleq2d 2247 . . . . . . . . 9 ( = (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) → (𝑧 ∈ dom 𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩})))
7372rspcev 2841 . . . . . . . 8 (((𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) ∈ 𝐴𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩})) → ∃𝐴 𝑧 ∈ dom )
7448, 70, 73syl2anc 411 . . . . . . 7 (((𝜑𝑧𝑌) ∧ (𝑔:𝑧𝑆 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ∃𝐴 𝑧 ∈ dom )
7515, 74exlimddv 1898 . . . . . 6 ((𝜑𝑧𝑌) → ∃𝐴 𝑧 ∈ dom )
76 eliun 3888 . . . . . 6 (𝑧 𝐴 dom ↔ ∃𝐴 𝑧 ∈ dom )
7775, 76sylibr 134 . . . . 5 ((𝜑𝑧𝑌) → 𝑧 𝐴 dom )
7877ex 115 . . . 4 (𝜑 → (𝑧𝑌𝑧 𝐴 dom ))
7978ssrdv 3161 . . 3 (𝜑𝑌 𝐴 dom )
80 dmuni 4833 . . . 4 dom 𝐴 = 𝐴 dom
8112, 1tfrcllemssrecs 6347 . . . . 5 (𝜑 𝐴 ⊆ recs(𝐺))
82 dmss 4822 . . . . 5 ( 𝐴 ⊆ recs(𝐺) → dom 𝐴 ⊆ dom recs(𝐺))
8381, 82syl 14 . . . 4 (𝜑 → dom 𝐴 ⊆ dom recs(𝐺))
8480, 83eqsstrrid 3202 . . 3 (𝜑 𝐴 dom ⊆ dom recs(𝐺))
8579, 84sstrd 3165 . 2 (𝜑𝑌 ⊆ dom recs(𝐺))
869dmeqi 4824 . 2 dom 𝐹 = dom recs(𝐺)
8785, 86sseqtrrdi 3204 1 (𝜑𝑌 ⊆ dom 𝐹)
Colors of variables: wff set class
Syntax hints:  wi 4  wa 104  w3a 978  wal 1351   = wceq 1353  wex 1492  wcel 2148  {cab 2163  wral 2455  wrex 2456  Vcvv 2737  cun 3127  wss 3129  {csn 3591  cop 3594   cuni 3807   ciun 3884  Ord word 4359  suc csuc 4362  dom cdm 4623  cres 4625  Fun wfun 5206  wf 5208  cfv 5212  recscrecs 6299
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 614  ax-in2 615  ax-io 709  ax-5 1447  ax-7 1448  ax-gen 1449  ax-ie1 1493  ax-ie2 1494  ax-8 1504  ax-10 1505  ax-11 1506  ax-i12 1507  ax-bndl 1509  ax-4 1510  ax-17 1526  ax-i9 1530  ax-ial 1534  ax-i5r 1535  ax-13 2150  ax-14 2151  ax-ext 2159  ax-coll 4115  ax-sep 4118  ax-pow 4171  ax-pr 4206  ax-un 4430  ax-setind 4533
This theorem depends on definitions:  df-bi 117  df-3an 980  df-tru 1356  df-fal 1359  df-nf 1461  df-sb 1763  df-eu 2029  df-mo 2030  df-clab 2164  df-cleq 2170  df-clel 2173  df-nfc 2308  df-ne 2348  df-ral 2460  df-rex 2461  df-reu 2462  df-rab 2464  df-v 2739  df-sbc 2963  df-csb 3058  df-dif 3131  df-un 3133  df-in 3135  df-ss 3142  df-nul 3423  df-pw 3576  df-sn 3597  df-pr 3598  df-op 3600  df-uni 3808  df-iun 3886  df-br 4001  df-opab 4062  df-mpt 4063  df-tr 4099  df-id 4290  df-iord 4363  df-on 4365  df-suc 4368  df-xp 4629  df-rel 4630  df-cnv 4631  df-co 4632  df-dm 4633  df-rn 4634  df-res 4635  df-ima 4636  df-iota 5174  df-fun 5214  df-fn 5215  df-f 5216  df-f1 5217  df-fo 5218  df-f1o 5219  df-fv 5220  df-recs 6300
This theorem is referenced by:  tfrcldm  6358
  Copyright terms: Public domain W3C validator