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

Theorem tfr1onlemres 6347
Description: Lemma for tfr1on 6348. 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 4387 . . . . . . . . 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 6346 . . . . . . . 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 5304 . . . . . . . . . . . . 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 6335 . . . . . . . . . . 11 (𝑔 ∈ V → (𝑔𝐴 ↔ ∃𝑤𝑋 (𝑔 Fn 𝑤 ∧ ∀𝑢𝑤 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))))
3230, 31ax-mp 5 . . . . . . . . . 10 (𝑔𝐴 ↔ ∃𝑤𝑋 (𝑔 Fn 𝑤 ∧ ∀𝑢𝑤 (𝑔𝑢) = (𝐺‘(𝑔𝑢))))
3329, 32sylibr 134 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑔𝐴)
349, 16, 17, 19, 12, 20, 21, 23, 24, 33tfr1onlemsucaccv 6339 . . . . . . . 8 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) ∈ 𝐴)
35 vex 2740 . . . . . . . . . . 11 𝑧 ∈ V
36 fneq2 5304 . . . . . . . . . . . . . . 15 (𝑥 = 𝑧 → (𝑔 Fn 𝑥𝑔 Fn 𝑧))
3736imbi1d 231 . . . . . . . . . . . . . 14 (𝑥 = 𝑧 → ((𝑔 Fn 𝑥 → (𝐺𝑔) ∈ V) ↔ (𝑔 Fn 𝑧 → (𝐺𝑔) ∈ V)))
38113expia 1205 . . . . . . . . . . . . . . . . . 18 ((𝜑𝑥𝑋) → (𝑓 Fn 𝑥 → (𝐺𝑓) ∈ V))
3938alrimiv 1874 . . . . . . . . . . . . . . . . 17 ((𝜑𝑥𝑋) → ∀𝑓(𝑓 Fn 𝑥 → (𝐺𝑓) ∈ V))
40 fneq1 5303 . . . . . . . . . . . . . . . . . . 19 (𝑓 = 𝑔 → (𝑓 Fn 𝑥𝑔 Fn 𝑥))
41 fveq2 5514 . . . . . . . . . . . . . . . . . . . 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 4227 . . . . . . . . . . 11 ((𝑧 ∈ V ∧ (𝐺𝑔) ∈ V) → ⟨𝑧, (𝐺𝑔)⟩ ∈ V)
5235, 50, 51sylancr 414 . . . . . . . . . 10 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ⟨𝑧, (𝐺𝑔)⟩ ∈ V)
53 snidg 3621 . . . . . . . . . 10 (⟨𝑧, (𝐺𝑔)⟩ ∈ V → ⟨𝑧, (𝐺𝑔)⟩ ∈ {⟨𝑧, (𝐺𝑔)⟩})
54 elun2 3303 . . . . . . . . . 10 (⟨𝑧, (𝐺𝑔)⟩ ∈ {⟨𝑧, (𝐺𝑔)⟩} → ⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}))
5552, 53, 543syl 17 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → ⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}))
56 opeldmg 4831 . . . . . . . . . 10 ((𝑧 ∈ V ∧ (𝐺𝑔) ∈ V) → (⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) → 𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩})))
5735, 50, 56sylancr 414 . . . . . . . . 9 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → (⟨𝑧, (𝐺𝑔)⟩ ∈ (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}) → 𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩})))
5855, 57mpd 13 . . . . . . . 8 (((𝜑𝑧𝑌) ∧ (𝑔 Fn 𝑧 ∧ ∀𝑢𝑧 (𝑔𝑢) = (𝐺‘(𝑔𝑢)))) → 𝑧 ∈ dom (𝑔 ∪ {⟨𝑧, (𝐺𝑔)⟩}))
59 dmeq 4826 . . . . . . . . . 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 3890 . . . . . 6 (𝑧 𝐴 dom ↔ ∃𝐴 𝑧 ∈ dom )
6563, 64sylibr 134 . . . . 5 ((𝜑𝑧𝑌) → 𝑧 𝐴 dom )
6665ex 115 . . . 4 (𝜑 → (𝑧𝑌𝑧 𝐴 dom ))
6766ssrdv 3161 . . 3 (𝜑𝑌 𝐴 dom )
68 dmuni 4836 . . . 4 dom 𝐴 = 𝐴 dom
6912, 1tfr1onlemssrecs 6337 . . . . 5 (𝜑 𝐴 ⊆ recs(𝐺))
70 dmss 4825 . . . . 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 4827 . 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 3592  cop 3595   cuni 3809   ciun 3886  Ord word 4361  suc csuc 4364  dom cdm 4625  cres 4627  Fun wfun 5209   Fn wfn 5210  cfv 5215  recscrecs 6302
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 4117  ax-sep 4120  ax-pow 4173  ax-pr 4208  ax-un 4432  ax-setind 4535
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 3577  df-sn 3598  df-pr 3599  df-op 3601  df-uni 3810  df-iun 3888  df-br 4003  df-opab 4064  df-mpt 4065  df-tr 4101  df-id 4292  df-iord 4365  df-on 4367  df-suc 4370  df-xp 4631  df-rel 4632  df-cnv 4633  df-co 4634  df-dm 4635  df-rn 4636  df-res 4637  df-ima 4638  df-iota 5177  df-fun 5217  df-fn 5218  df-f 5219  df-f1 5220  df-fo 5221  df-f1o 5222  df-fv 5223  df-recs 6303
This theorem is referenced by:  tfr1on  6348
  Copyright terms: Public domain W3C validator