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

Theorem tfr1onlemres 6344
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
tfr1on.f 𝐹 = recs(𝐺)
tfr1on.g (𝜑 → Fun 𝐺)
tfr1on.x (𝜑 → Ord 𝑋)
tfr1on.ex ((𝜑𝑥𝑋𝑓 Fn 𝑥) → (𝐺𝑓) ∈ V)
tfr1onlemsucfn.1 𝐴 = {𝑓 ∣ ∃𝑥𝑋 (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐺‘(𝑓𝑦)))}
tfr1onlemres.u ((𝜑𝑥 𝑋) → suc 𝑥𝑋)
tfr1onlemres.yx (𝜑𝑌𝑋)
Assertion
Ref Expression
tfr1onlemres (𝜑𝑌 ⊆ dom 𝐹)
Distinct variable groups:   𝑥,𝐴   𝑓,𝐺,𝑥,𝑦   𝑓,𝑋,𝑥   𝑓,𝑌,𝑥   𝜑,𝑓,𝑥
Allowed substitution hints:   𝜑(𝑦)   𝐴(𝑦,𝑓)   𝐹(𝑥,𝑦,𝑓)   𝑋(𝑦)   𝑌(𝑦)

Proof of Theorem tfr1onlemres
Dummy variables 𝑔 𝑧 𝑢 𝑤 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 tfr1on.x . . . . . . . . . 10 (𝜑 → Ord 𝑋)
21adantr 276 . . . . . . . . 9 ((𝜑𝑧𝑌) → Ord 𝑋)
3 simpr 110 . . . . . . . . . 10 ((𝜑𝑧𝑌) → 𝑧𝑌)
4 tfr1onlemres.yx . . . . . . . . . . 11 (𝜑𝑌𝑋)
54adantr 276 . . . . . . . . . 10 ((𝜑𝑧𝑌) → 𝑌𝑋)
63, 5jca 306 . . . . . . . . 9 ((𝜑𝑧𝑌) → (𝑧𝑌𝑌𝑋))
7 ordtr1 4385 . . . . . . . . 9 (Ord 𝑋 → ((𝑧𝑌𝑌𝑋) → 𝑧𝑋))
82, 6, 7sylc 62 . . . . . . . 8 ((𝜑𝑧𝑌) → 𝑧𝑋)
9 tfr1on.f . . . . . . . . 9 𝐹 = recs(𝐺)
10 tfr1on.g . . . . . . . . 9 (𝜑 → Fun 𝐺)
11 tfr1on.ex . . . . . . . . 9 ((𝜑𝑥𝑋𝑓 Fn 𝑥) → (𝐺𝑓) ∈ V)
12 tfr1onlemsucfn.1 . . . . . . . . 9 𝐴 = {𝑓 ∣ ∃𝑥𝑋 (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐺‘(𝑓𝑦)))}
13 tfr1onlemres.u . . . . . . . . 9 ((𝜑𝑥 𝑋) → suc 𝑥𝑋)
149, 10, 1, 11, 12, 13tfr1onlemaccex 6343 . . . . . . . 8 ((𝜑𝑧𝑋) → ∃𝑔(𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢))))
158, 14syldan 282 . . . . . . 7 ((𝜑𝑧𝑌) → ∃𝑔(𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢))))
1610ad2antrr 488 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → Fun 𝐺)
171ad2antrr 488 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → Ord 𝑋)
18113adant1r 1231 . . . . . . . . . 10 (((𝜑𝑧𝑌) ∧ 𝑥𝑋𝑓 Fn 𝑥) → (𝐺𝑓) ∈ V)
19183adant1r 1231 . . . . . . . . 9 ((((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) ∧ 𝑥𝑋𝑓 Fn 𝑥) → (𝐺𝑓) ∈ V)
204ad2antrr 488 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑌𝑋)
213adantr 276 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑧𝑌)
2213adantlr 477 . . . . . . . . . 10 (((𝜑𝑧𝑌) ∧ 𝑥 𝑋) → suc 𝑥𝑋)
2322adantlr 477 . . . . . . . . 9 ((((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) ∧ 𝑥 𝑋) → suc 𝑥𝑋)
24 simprl 529 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑔 Fn 𝑧)
25 fneq2 5301 . . . . . . . . . . . . 13 (𝑤 = 𝑧 → (𝑔 Fn 𝑤𝑔 Fn 𝑧))
26 raleq 2672 . . . . . . . . . . . . 13 (𝑤 = 𝑧 → (∀𝑢𝑤 (𝑔𝑢) = (𝐺‘(𝑔𝑢)) ↔ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢))))
2725, 26anbi12d 473 . . . . . . . . . . . 12 (𝑤 = 𝑧 → ((𝑔 Fn 𝑤 ∧ ∀𝑢𝑤 (𝑔𝑢) = (𝐺‘(𝑔𝑢))) ↔ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))))
2827rspcev 2841 . . . . . . . . . . 11 ((𝑧𝑋 ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ∃𝑤𝑋 (𝑔 Fn 𝑤 ∧ ∀𝑢𝑤 (𝑔𝑢) = (𝐺‘(𝑔𝑢))))
298, 28sylan 283 . . . . . . . . . 10 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ∃𝑤𝑋 (𝑔 Fn 𝑤 ∧ ∀𝑢𝑤 (𝑔𝑢) = (𝐺‘(𝑔𝑢))))
30 vex 2740 . . . . . . . . . . 11 𝑔 ∈ V
3112tfr1onlem3ag 6332 . . . . . . . . . . 11 (𝑔 ∈ V → (𝑔𝐴 ↔ ∃𝑤𝑋 (𝑔 Fn 𝑤 ∧ ∀𝑢𝑤 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))))
3230, 31ax-mp 5 . . . . . . . . . 10 (𝑔𝐴 ↔ ∃𝑤𝑋 (𝑔 Fn 𝑤 ∧ ∀𝑢𝑤 (𝑔𝑢) = (𝐺‘(𝑔𝑢))))
3329, 32sylibr 134 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑔𝐴)
349, 16, 17, 19, 12, 20, 21, 23, 24, 33tfr1onlemsucaccv 6336 . . . . . . . 8 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) ∈ 𝐴)
35 vex 2740 . . . . . . . . . . 11 𝑧 ∈ V
36 fneq2 5301 . . . . . . . . . . . . . . 15 (𝑥 = 𝑧 → (𝑔 Fn 𝑥𝑔 Fn 𝑧))
3736imbi1d 231 . . . . . . . . . . . . . 14 (𝑥 = 𝑧 → ((𝑔 Fn 𝑥 → (𝐺𝑔) ∈ V) ↔ (𝑔 Fn 𝑧 → (𝐺𝑔) ∈ V)))
38113expia 1205 . . . . . . . . . . . . . . . . . 18 ((𝜑𝑥𝑋) → (𝑓 Fn 𝑥 → (𝐺𝑓) ∈ V))
3938alrimiv 1874 . . . . . . . . . . . . . . . . 17 ((𝜑𝑥𝑋) → ∀𝑓(𝑓 Fn 𝑥 → (𝐺𝑓) ∈ V))
40 fneq1 5300 . . . . . . . . . . . . . . . . . . 19 (𝑓 = 𝑔 → (𝑓 Fn 𝑥𝑔 Fn 𝑥))
41 fveq2 5511 . . . . . . . . . . . . . . . . . . . 20 (𝑓 = 𝑔 → (𝐺𝑓) = (𝐺𝑔))
4241eleq1d 2246 . . . . . . . . . . . . . . . . . . 19 (𝑓 = 𝑔 → ((𝐺𝑓) ∈ V ↔ (𝐺𝑔) ∈ V))
4340, 42imbi12d 234 . . . . . . . . . . . . . . . . . 18 (𝑓 = 𝑔 → ((𝑓 Fn 𝑥 → (𝐺𝑓) ∈ V) ↔ (𝑔 Fn 𝑥 → (𝐺𝑔) ∈ V)))
4443spv 1860 . . . . . . . . . . . . . . . . 17 (∀𝑓(𝑓 Fn 𝑥 → (𝐺𝑓) ∈ V) → (𝑔 Fn 𝑥 → (𝐺𝑔) ∈ V))
4539, 44syl 14 . . . . . . . . . . . . . . . 16 ((𝜑𝑥𝑋) → (𝑔 Fn 𝑥 → (𝐺𝑔) ∈ V))
4645ralrimiva 2550 . . . . . . . . . . . . . . 15 (𝜑 → ∀𝑥𝑋 (𝑔 Fn 𝑥 → (𝐺𝑔) ∈ V))
4746adantr 276 . . . . . . . . . . . . . 14 ((𝜑𝑧𝑌) → ∀𝑥𝑋 (𝑔 Fn 𝑥 → (𝐺𝑔) ∈ V))
4837, 47, 8rspcdva 2846 . . . . . . . . . . . . 13 ((𝜑𝑧𝑌) → (𝑔 Fn 𝑧 → (𝐺𝑔) ∈ V))
4948imp 124 . . . . . . . . . . . 12 (((𝜑𝑧𝑌) ∧ 𝑔 Fn 𝑧) → (𝐺𝑔) ∈ V)
5024, 49syldan 282 . . . . . . . . . . 11 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → (𝐺𝑔) ∈ V)
51 opexg 4225 . . . . . . . . . . 11 ((𝑧 ∈ V ∧ (𝐺𝑔) ∈ V) → ⟨𝑧, (𝐺𝑔)⟩ ∈ V)
5235, 50, 51sylancr 414 . . . . . . . . . 10 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ⟨𝑧, (𝐺𝑔)⟩ ∈ V)
53 snidg 3620 . . . . . . . . . 10 (⟨𝑧, (𝐺𝑔)⟩ ∈ V → ⟨𝑧, (𝐺𝑔)⟩ ∈ {⟨𝑧, (𝐺𝑔)⟩})
54 elun2 3303 . . . . . . . . . 10 (⟨𝑧, (𝐺𝑔)⟩ ∈ {⟨𝑧, (𝐺𝑔)⟩} → ⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}))
5552, 53, 543syl 17 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}))
56 opeldmg 4828 . . . . . . . . . 10 ((𝑧 ∈ V ∧ (𝐺𝑔) ∈ V) → (⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) → 𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩})))
5735, 50, 56sylancr 414 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → (⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) → 𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩})))
5855, 57mpd 13 . . . . . . . 8 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}))
59 dmeq 4823 . . . . . . . . . 10 ( = (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) → dom = dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}))
6059eleq2d 2247 . . . . . . . . 9 ( = (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) → (𝑧 ∈ dom 𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩})))
6160rspcev 2841 . . . . . . . 8 (((𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) ∈ 𝐴𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩})) → ∃𝐴 𝑧 ∈ dom )
6234, 58, 61syl2anc 411 . . . . . . 7 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ∃𝐴 𝑧 ∈ dom )
6315, 62exlimddv 1898 . . . . . 6 ((𝜑𝑧𝑌) → ∃𝐴 𝑧 ∈ dom )
64 eliun 3888 . . . . . 6 (𝑧 𝐴 dom ↔ ∃𝐴 𝑧 ∈ dom )
6563, 64sylibr 134 . . . . 5 ((𝜑𝑧𝑌) → 𝑧 𝐴 dom )
6665ex 115 . . . 4 (𝜑 → (𝑧𝑌𝑧 𝐴 dom ))
6766ssrdv 3161 . . 3 (𝜑𝑌 𝐴 dom )
68 dmuni 4833 . . . 4 dom 𝐴 = 𝐴 dom
6912, 1tfr1onlemssrecs 6334 . . . . 5 (𝜑 𝐴 ⊆ recs(𝐺))
70 dmss 4822 . . . . 5 ( 𝐴 ⊆ recs(𝐺) → dom 𝐴 ⊆ dom recs(𝐺))
7169, 70syl 14 . . . 4 (𝜑 → dom 𝐴 ⊆ dom recs(𝐺))
7268, 71eqsstrrid 3202 . . 3 (𝜑 𝐴 dom ⊆ dom recs(𝐺))
7367, 72sstrd 3165 . 2 (𝜑𝑌 ⊆ dom recs(𝐺))
749dmeqi 4824 . 2 dom 𝐹 = dom recs(𝐺)
7573, 74sseqtrrdi 3204 1 (𝜑𝑌 ⊆ dom 𝐹)
Colors of variables: wff set class
Syntax hints:  wi 4  wa 104  wb 105  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   Fn wfn 5207  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:  tfr1on  6345
  Copyright terms: Public domain W3C validator