MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  frrlem9 Structured version   Visualization version   GIF version

Theorem frrlem9 8350
Description: Lemma for well-founded recursion. Show that the well-founded recursive generator produces a function. Hypothesis three will be eliminated using different induction rules depending on if we use partial orders or the axiom of infinity. (Contributed by Scott Fenton, 27-Aug-2022.)
Hypotheses
Ref Expression
frrlem9.1 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}
frrlem9.2 𝐹 = frecs(𝑅, 𝐴, 𝐺)
frrlem9.3 ((𝜑 ∧ (𝑔 ∈ 𝐵 ∧ ℎ ∈ 𝐵)) → ((𝑥𝑔𝑢 ∧ 𝑥ℎ𝑣) → 𝑢 = 𝑣))
Assertion
Ref Expression
frrlem9 (𝜑 → Fun 𝐹)
Distinct variable groups:   𝐴,𝑓,𝑥,𝑦   𝑓,𝐺,𝑥,𝑦   𝑅,𝑓,𝑥,𝑦   𝐵,𝑔,ℎ   𝑥,𝐹,𝑢,𝑣   𝜑,𝑓   𝑓,𝐹   𝜑,𝑔,ℎ,𝑥,𝑢,𝑣
Allowed substitution hints:   𝜑(𝑦)   𝐴(𝑣, 𝑢, 𝑔, ℎ)   𝐵(𝑥, 𝑦, 𝑣, 𝑢, 𝑓)   𝑅(𝑣, 𝑢, 𝑔, ℎ)   𝐹(𝑦, 𝑔, ℎ)   𝐺(𝑣, 𝑢, 𝑔, ℎ)

Proof of Theorem frrlem9
StepHypRef Expression
1 eluni2 4876 . . . . . . . 8 (⟨𝑥, 𝑢⟩ ∈ ∪ 𝐵 ↔ ∃𝑔 ∈ 𝐵 ⟨𝑥, 𝑢⟩ ∈ 𝑔)
2 df-br 5109 . . . . . . . . 9 (𝑥𝐹𝑢 ↔ ⟨𝑥, 𝑢⟩ ∈ 𝐹)
3 frrlem9.1 . . . . . . . . . . 11 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}
4 frrlem9.2 . . . . . . . . . . 11 𝐹 = frecs(𝑅, 𝐴, 𝐺)
53, 4frrlem5 8346 . . . . . . . . . 10 𝐹 = ∪ 𝐵
65eleq2i 2856 . . . . . . . . 9 (⟨𝑥, 𝑢⟩ ∈ 𝐹 ↔ ⟨𝑥, 𝑢⟩ ∈ ∪ 𝐵)
72, 6bitri 278 . . . . . . . 8 (𝑥𝐹𝑢 ↔ ⟨𝑥, 𝑢⟩ ∈ ∪ 𝐵)
8 df-br 5109 . . . . . . . . 9 (𝑥𝑔𝑢 ↔ ⟨𝑥, 𝑢⟩ ∈ 𝑔)
98rexbii 3113 . . . . . . . 8 (∃𝑔 ∈ 𝐵 𝑥𝑔𝑢 ↔ ∃𝑔 ∈ 𝐵 ⟨𝑥, 𝑢⟩ ∈ 𝑔)
101, 7, 93bitr4i 306 . . . . . . 7 (𝑥𝐹𝑢 ↔ ∃𝑔 ∈ 𝐵 𝑥𝑔𝑢)
11 eluni2 4876 . . . . . . . 8 (⟨𝑥, 𝑣⟩ ∈ ∪ 𝐵 ↔ ∃ℎ ∈ 𝐵 ⟨𝑥, 𝑣⟩ ∈ ℎ)
12 df-br 5109 . . . . . . . . 9 (𝑥𝐹𝑣 ↔ ⟨𝑥, 𝑣⟩ ∈ 𝐹)
135eleq2i 2856 . . . . . . . . 9 (⟨𝑥, 𝑣⟩ ∈ 𝐹 ↔ ⟨𝑥, 𝑣⟩ ∈ ∪ 𝐵)
1412, 13bitri 278 . . . . . . . 8 (𝑥𝐹𝑣 ↔ ⟨𝑥, 𝑣⟩ ∈ ∪ 𝐵)
15 df-br 5109 . . . . . . . . 9 (𝑥ℎ𝑣 ↔ ⟨𝑥, 𝑣⟩ ∈ ℎ)
1615rexbii 3113 . . . . . . . 8 (∃ℎ ∈ 𝐵 𝑥ℎ𝑣 ↔ ∃ℎ ∈ 𝐵 ⟨𝑥, 𝑣⟩ ∈ ℎ)
1711, 14, 163bitr4i 306 . . . . . . 7 (𝑥𝐹𝑣 ↔ ∃ℎ ∈ 𝐵 𝑥ℎ𝑣)
1810, 17anbi12i 640 . . . . . 6 ((𝑥𝐹𝑢 ∧ 𝑥𝐹𝑣) ↔ (∃𝑔 ∈ 𝐵 𝑥𝑔𝑢 ∧ ∃ℎ ∈ 𝐵 𝑥ℎ𝑣))
19 reeanv 3238 . . . . . 6 (∃𝑔 ∈ 𝐵 ∃ℎ ∈ 𝐵 (𝑥𝑔𝑢 ∧ 𝑥ℎ𝑣) ↔ (∃𝑔 ∈ 𝐵 𝑥𝑔𝑢 ∧ ∃ℎ ∈ 𝐵 𝑥ℎ𝑣))
2018, 19bitr4i 281 . . . . 5 ((𝑥𝐹𝑢 ∧ 𝑥𝐹𝑣) ↔ ∃𝑔 ∈ 𝐵 ∃ℎ ∈ 𝐵 (𝑥𝑔𝑢 ∧ 𝑥ℎ𝑣))
21 frrlem9.3 . . . . . 6 ((𝜑 ∧ (𝑔 ∈ 𝐵 ∧ ℎ ∈ 𝐵)) → ((𝑥𝑔𝑢 ∧ 𝑥ℎ𝑣) → 𝑢 = 𝑣))
2221rexlimdvva 3223 . . . . 5 (𝜑 → (∃𝑔 ∈ 𝐵 ∃ℎ ∈ 𝐵 (𝑥𝑔𝑢 ∧ 𝑥ℎ𝑣) → 𝑢 = 𝑣))
2320, 22biimtrid 245 . . . 4 (𝜑 → ((𝑥𝐹𝑢 ∧ 𝑥𝐹𝑣) → 𝑢 = 𝑣))
2423alrimiv 1962 . . 3 (𝜑 → ∀𝑣((𝑥𝐹𝑢 ∧ 𝑥𝐹𝑣) → 𝑢 = 𝑣))
2524alrimivv 1963 . 2 (𝜑 → ∀𝑥∀𝑢∀𝑣((𝑥𝐹𝑢 ∧ 𝑥𝐹𝑣) → 𝑢 = 𝑣))
263, 4frrlem6 8347 . . 3 Rel 𝐹
27 dffun2 6576 . . 3 (Fun 𝐹 ↔ (Rel 𝐹 ∧ ∀𝑥∀𝑢∀𝑣((𝑥𝐹𝑢 ∧ 𝑥𝐹𝑣) → 𝑢 = 𝑣)))
2826, 27mpbiran 722 . 2 (Fun 𝐹 ↔ ∀𝑥∀𝑢∀𝑣((𝑥𝐹𝑢 ∧ 𝑥𝐹𝑣) → 𝑢 = 𝑣))
2925, 28sylibr 237 1 (𝜑 → Fun 𝐹)
Colors of variables:    wff setvar class
This proof depends on syntax axioms:   → wi 4   ∧ wa 401   ∧ w3a 1103  ∀wal 1568   = wceq 1570  ∃wex 1812   ∈ wcel 2147  {cab 2741  ∀wral 3080  ∃wrex 3090   ⊆ wss 3900  ⟨cop 4840  ∪ cuni 4872   class class class wbr 5108   ↾ cres 5660  Rel wrel 5663  Predcpred 6329  Fun wfun 6560   Fn wfn 6561  ‘cfv 6566  (class class class)co 7451  frecscfrecs 8336
This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1828  ax-4 1842  ax-5 1945  ax-6 2002  ax-7 2043  ax-8 2149  ax-9 2157  ax-11 2197  ax-12 2216  ax-ext 2735  ax-sep 5255  ax-pr 5398
This proof depends on definitions:  df-bi 210  df-an 402  df-or 862  df-3an 1105  df-tru 1573  df-fal 1583  df-ex 1813  df-sb 2102  df-clab 2742  df-cleq 2755  df-clel 2839  df-ral 3081  df-rex 3091  df-rab 3417  df-v 3456  df-ss 3901  df-dif 4050  df-in 4094  df-un 4154  df-nul 4282  df-if 4486  df-sn 4589  df-pr 4591  df-op 4841  df-uni 4873  df-iun 4958  df-br 5109  df-opab 5174  df-id 5553  df-xp 5664  df-rel 5665  df-cnv 5666  df-co 5667  df-dm 5668  df-rn 5669  df-res 5670  df-ima 5671  df-pred 6330  df-iota 6520  df-fun 6568  df-fn 6569  df-fv 6574  df-ov 7454  df-frecs 8337
This theorem is used by:  frrlem10  8351  frrlem11  8352  frrlem12  8353  frrlem13  8354  fpr1  8359  fprfung  8365  frr1  9800
  Copyright terms: Public domain W3C validator