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

Theorem om2uzrdg 12738
 Description: A helper lemma for the value of a recursive definition generator on upper integers (typically either ℕ or ℕ0) with characteristic function 𝐹(𝑥, 𝑦) and initial value 𝐴. Normally 𝐹 is a function on the partition, and 𝐴 is a member of the partition. See also comment in om2uz0i 12729. (Contributed by Mario Carneiro, 26-Jun-2013.) (Revised by Mario Carneiro, 18-Nov-2014.)
Hypotheses
Ref Expression
om2uz.1 𝐶 ∈ ℤ
om2uz.2 𝐺 = (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 𝐶) ↾ ω)
uzrdg.1 𝐴 ∈ V
uzrdg.2 𝑅 = (rec((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩), ⟨𝐶, 𝐴⟩) ↾ ω)
Assertion
Ref Expression
om2uzrdg (𝐵 ∈ ω → (𝑅𝐵) = ⟨(𝐺𝐵), (2nd ‘(𝑅𝐵))⟩)
Distinct variable groups:   𝑦,𝐴   𝑥,𝑦,𝐶   𝑦,𝐺   𝑥,𝐹,𝑦
Allowed substitution hints:   𝐴(𝑥)   𝐵(𝑥,𝑦)   𝑅(𝑥,𝑦)   𝐺(𝑥)

Proof of Theorem om2uzrdg
Dummy variables 𝑧 𝑤 𝑣 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 fveq2 6178 . . 3 (𝑧 = ∅ → (𝑅𝑧) = (𝑅‘∅))
2 fveq2 6178 . . . 4 (𝑧 = ∅ → (𝐺𝑧) = (𝐺‘∅))
31fveq2d 6182 . . . 4 (𝑧 = ∅ → (2nd ‘(𝑅𝑧)) = (2nd ‘(𝑅‘∅)))
42, 3opeq12d 4401 . . 3 (𝑧 = ∅ → ⟨(𝐺𝑧), (2nd ‘(𝑅𝑧))⟩ = ⟨(𝐺‘∅), (2nd ‘(𝑅‘∅))⟩)
51, 4eqeq12d 2635 . 2 (𝑧 = ∅ → ((𝑅𝑧) = ⟨(𝐺𝑧), (2nd ‘(𝑅𝑧))⟩ ↔ (𝑅‘∅) = ⟨(𝐺‘∅), (2nd ‘(𝑅‘∅))⟩))
6 fveq2 6178 . . 3 (𝑧 = 𝑣 → (𝑅𝑧) = (𝑅𝑣))
7 fveq2 6178 . . . 4 (𝑧 = 𝑣 → (𝐺𝑧) = (𝐺𝑣))
86fveq2d 6182 . . . 4 (𝑧 = 𝑣 → (2nd ‘(𝑅𝑧)) = (2nd ‘(𝑅𝑣)))
97, 8opeq12d 4401 . . 3 (𝑧 = 𝑣 → ⟨(𝐺𝑧), (2nd ‘(𝑅𝑧))⟩ = ⟨(𝐺𝑣), (2nd ‘(𝑅𝑣))⟩)
106, 9eqeq12d 2635 . 2 (𝑧 = 𝑣 → ((𝑅𝑧) = ⟨(𝐺𝑧), (2nd ‘(𝑅𝑧))⟩ ↔ (𝑅𝑣) = ⟨(𝐺𝑣), (2nd ‘(𝑅𝑣))⟩))
11 fveq2 6178 . . 3 (𝑧 = suc 𝑣 → (𝑅𝑧) = (𝑅‘suc 𝑣))
12 fveq2 6178 . . . 4 (𝑧 = suc 𝑣 → (𝐺𝑧) = (𝐺‘suc 𝑣))
1311fveq2d 6182 . . . 4 (𝑧 = suc 𝑣 → (2nd ‘(𝑅𝑧)) = (2nd ‘(𝑅‘suc 𝑣)))
1412, 13opeq12d 4401 . . 3 (𝑧 = suc 𝑣 → ⟨(𝐺𝑧), (2nd ‘(𝑅𝑧))⟩ = ⟨(𝐺‘suc 𝑣), (2nd ‘(𝑅‘suc 𝑣))⟩)
1511, 14eqeq12d 2635 . 2 (𝑧 = suc 𝑣 → ((𝑅𝑧) = ⟨(𝐺𝑧), (2nd ‘(𝑅𝑧))⟩ ↔ (𝑅‘suc 𝑣) = ⟨(𝐺‘suc 𝑣), (2nd ‘(𝑅‘suc 𝑣))⟩))
16 fveq2 6178 . . 3 (𝑧 = 𝐵 → (𝑅𝑧) = (𝑅𝐵))
17 fveq2 6178 . . . 4 (𝑧 = 𝐵 → (𝐺𝑧) = (𝐺𝐵))
1816fveq2d 6182 . . . 4 (𝑧 = 𝐵 → (2nd ‘(𝑅𝑧)) = (2nd ‘(𝑅𝐵)))
1917, 18opeq12d 4401 . . 3 (𝑧 = 𝐵 → ⟨(𝐺𝑧), (2nd ‘(𝑅𝑧))⟩ = ⟨(𝐺𝐵), (2nd ‘(𝑅𝐵))⟩)
2016, 19eqeq12d 2635 . 2 (𝑧 = 𝐵 → ((𝑅𝑧) = ⟨(𝐺𝑧), (2nd ‘(𝑅𝑧))⟩ ↔ (𝑅𝐵) = ⟨(𝐺𝐵), (2nd ‘(𝑅𝐵))⟩))
21 uzrdg.2 . . . . 5 𝑅 = (rec((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩), ⟨𝐶, 𝐴⟩) ↾ ω)
2221fveq1i 6179 . . . 4 (𝑅‘∅) = ((rec((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩), ⟨𝐶, 𝐴⟩) ↾ ω)‘∅)
23 opex 4923 . . . . 5 𝐶, 𝐴⟩ ∈ V
24 fr0g 7516 . . . . 5 (⟨𝐶, 𝐴⟩ ∈ V → ((rec((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩), ⟨𝐶, 𝐴⟩) ↾ ω)‘∅) = ⟨𝐶, 𝐴⟩)
2523, 24ax-mp 5 . . . 4 ((rec((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩), ⟨𝐶, 𝐴⟩) ↾ ω)‘∅) = ⟨𝐶, 𝐴
2622, 25eqtri 2642 . . 3 (𝑅‘∅) = ⟨𝐶, 𝐴
27 om2uz.1 . . . . 5 𝐶 ∈ ℤ
28 om2uz.2 . . . . 5 𝐺 = (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 𝐶) ↾ ω)
2927, 28om2uz0i 12729 . . . 4 (𝐺‘∅) = 𝐶
3026fveq2i 6181 . . . . 5 (2nd ‘(𝑅‘∅)) = (2nd ‘⟨𝐶, 𝐴⟩)
3127elexi 3208 . . . . . 6 𝐶 ∈ V
32 uzrdg.1 . . . . . 6 𝐴 ∈ V
3331, 32op2nd 7162 . . . . 5 (2nd ‘⟨𝐶, 𝐴⟩) = 𝐴
3430, 33eqtri 2642 . . . 4 (2nd ‘(𝑅‘∅)) = 𝐴
3529, 34opeq12i 4398 . . 3 ⟨(𝐺‘∅), (2nd ‘(𝑅‘∅))⟩ = ⟨𝐶, 𝐴
3626, 35eqtr4i 2645 . 2 (𝑅‘∅) = ⟨(𝐺‘∅), (2nd ‘(𝑅‘∅))⟩
37 frsuc 7517 . . . . . 6 (𝑣 ∈ ω → ((rec((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩), ⟨𝐶, 𝐴⟩) ↾ ω)‘suc 𝑣) = ((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩)‘((rec((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩), ⟨𝐶, 𝐴⟩) ↾ ω)‘𝑣)))
3821fveq1i 6179 . . . . . 6 (𝑅‘suc 𝑣) = ((rec((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩), ⟨𝐶, 𝐴⟩) ↾ ω)‘suc 𝑣)
3921fveq1i 6179 . . . . . . 7 (𝑅𝑣) = ((rec((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩), ⟨𝐶, 𝐴⟩) ↾ ω)‘𝑣)
4039fveq2i 6181 . . . . . 6 ((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩)‘(𝑅𝑣)) = ((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩)‘((rec((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩), ⟨𝐶, 𝐴⟩) ↾ ω)‘𝑣))
4137, 38, 403eqtr4g 2679 . . . . 5 (𝑣 ∈ ω → (𝑅‘suc 𝑣) = ((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩)‘(𝑅𝑣)))
42 fveq2 6178 . . . . . 6 ((𝑅𝑣) = ⟨(𝐺𝑣), (2nd ‘(𝑅𝑣))⟩ → ((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩)‘(𝑅𝑣)) = ((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩)‘⟨(𝐺𝑣), (2nd ‘(𝑅𝑣))⟩))
43 df-ov 6638 . . . . . . 7 ((𝐺𝑣)(𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩)(2nd ‘(𝑅𝑣))) = ((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩)‘⟨(𝐺𝑣), (2nd ‘(𝑅𝑣))⟩)
44 fvex 6188 . . . . . . . 8 (𝐺𝑣) ∈ V
45 fvex 6188 . . . . . . . 8 (2nd ‘(𝑅𝑣)) ∈ V
46 oveq1 6642 . . . . . . . . . 10 (𝑤 = (𝐺𝑣) → (𝑤 + 1) = ((𝐺𝑣) + 1))
47 oveq1 6642 . . . . . . . . . 10 (𝑤 = (𝐺𝑣) → (𝑤𝐹𝑧) = ((𝐺𝑣)𝐹𝑧))
4846, 47opeq12d 4401 . . . . . . . . 9 (𝑤 = (𝐺𝑣) → ⟨(𝑤 + 1), (𝑤𝐹𝑧)⟩ = ⟨((𝐺𝑣) + 1), ((𝐺𝑣)𝐹𝑧)⟩)
49 oveq2 6643 . . . . . . . . . 10 (𝑧 = (2nd ‘(𝑅𝑣)) → ((𝐺𝑣)𝐹𝑧) = ((𝐺𝑣)𝐹(2nd ‘(𝑅𝑣))))
5049opeq2d 4400 . . . . . . . . 9 (𝑧 = (2nd ‘(𝑅𝑣)) → ⟨((𝐺𝑣) + 1), ((𝐺𝑣)𝐹𝑧)⟩ = ⟨((𝐺𝑣) + 1), ((𝐺𝑣)𝐹(2nd ‘(𝑅𝑣)))⟩)
51 oveq1 6642 . . . . . . . . . . 11 (𝑥 = 𝑤 → (𝑥 + 1) = (𝑤 + 1))
52 oveq1 6642 . . . . . . . . . . 11 (𝑥 = 𝑤 → (𝑥𝐹𝑦) = (𝑤𝐹𝑦))
5351, 52opeq12d 4401 . . . . . . . . . 10 (𝑥 = 𝑤 → ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩ = ⟨(𝑤 + 1), (𝑤𝐹𝑦)⟩)
54 oveq2 6643 . . . . . . . . . . 11 (𝑦 = 𝑧 → (𝑤𝐹𝑦) = (𝑤𝐹𝑧))
5554opeq2d 4400 . . . . . . . . . 10 (𝑦 = 𝑧 → ⟨(𝑤 + 1), (𝑤𝐹𝑦)⟩ = ⟨(𝑤 + 1), (𝑤𝐹𝑧)⟩)
5653, 55cbvmpt2v 6720 . . . . . . . . 9 (𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩) = (𝑤 ∈ V, 𝑧 ∈ V ↦ ⟨(𝑤 + 1), (𝑤𝐹𝑧)⟩)
57 opex 4923 . . . . . . . . 9 ⟨((𝐺𝑣) + 1), ((𝐺𝑣)𝐹(2nd ‘(𝑅𝑣)))⟩ ∈ V
5848, 50, 56, 57ovmpt2 6781 . . . . . . . 8 (((𝐺𝑣) ∈ V ∧ (2nd ‘(𝑅𝑣)) ∈ V) → ((𝐺𝑣)(𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩)(2nd ‘(𝑅𝑣))) = ⟨((𝐺𝑣) + 1), ((𝐺𝑣)𝐹(2nd ‘(𝑅𝑣)))⟩)
5944, 45, 58mp2an 707 . . . . . . 7 ((𝐺𝑣)(𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩)(2nd ‘(𝑅𝑣))) = ⟨((𝐺𝑣) + 1), ((𝐺𝑣)𝐹(2nd ‘(𝑅𝑣)))⟩
6043, 59eqtr3i 2644 . . . . . 6 ((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩)‘⟨(𝐺𝑣), (2nd ‘(𝑅𝑣))⟩) = ⟨((𝐺𝑣) + 1), ((𝐺𝑣)𝐹(2nd ‘(𝑅𝑣)))⟩
6142, 60syl6eq 2670 . . . . 5 ((𝑅𝑣) = ⟨(𝐺𝑣), (2nd ‘(𝑅𝑣))⟩ → ((𝑥 ∈ V, 𝑦 ∈ V ↦ ⟨(𝑥 + 1), (𝑥𝐹𝑦)⟩)‘(𝑅𝑣)) = ⟨((𝐺𝑣) + 1), ((𝐺𝑣)𝐹(2nd ‘(𝑅𝑣)))⟩)
6241, 61sylan9eq 2674 . . . 4 ((𝑣 ∈ ω ∧ (𝑅𝑣) = ⟨(𝐺𝑣), (2nd ‘(𝑅𝑣))⟩) → (𝑅‘suc 𝑣) = ⟨((𝐺𝑣) + 1), ((𝐺𝑣)𝐹(2nd ‘(𝑅𝑣)))⟩)
6327, 28om2uzsuci 12730 . . . . . 6 (𝑣 ∈ ω → (𝐺‘suc 𝑣) = ((𝐺𝑣) + 1))
6463adantr 481 . . . . 5 ((𝑣 ∈ ω ∧ (𝑅𝑣) = ⟨(𝐺𝑣), (2nd ‘(𝑅𝑣))⟩) → (𝐺‘suc 𝑣) = ((𝐺𝑣) + 1))
6562fveq2d 6182 . . . . . 6 ((𝑣 ∈ ω ∧ (𝑅𝑣) = ⟨(𝐺𝑣), (2nd ‘(𝑅𝑣))⟩) → (2nd ‘(𝑅‘suc 𝑣)) = (2nd ‘⟨((𝐺𝑣) + 1), ((𝐺𝑣)𝐹(2nd ‘(𝑅𝑣)))⟩))
66 ovex 6663 . . . . . . 7 ((𝐺𝑣) + 1) ∈ V
67 ovex 6663 . . . . . . 7 ((𝐺𝑣)𝐹(2nd ‘(𝑅𝑣))) ∈ V
6866, 67op2nd 7162 . . . . . 6 (2nd ‘⟨((𝐺𝑣) + 1), ((𝐺𝑣)𝐹(2nd ‘(𝑅𝑣)))⟩) = ((𝐺𝑣)𝐹(2nd ‘(𝑅𝑣)))
6965, 68syl6eq 2670 . . . . 5 ((𝑣 ∈ ω ∧ (𝑅𝑣) = ⟨(𝐺𝑣), (2nd ‘(𝑅𝑣))⟩) → (2nd ‘(𝑅‘suc 𝑣)) = ((𝐺𝑣)𝐹(2nd ‘(𝑅𝑣))))
7064, 69opeq12d 4401 . . . 4 ((𝑣 ∈ ω ∧ (𝑅𝑣) = ⟨(𝐺𝑣), (2nd ‘(𝑅𝑣))⟩) → ⟨(𝐺‘suc 𝑣), (2nd ‘(𝑅‘suc 𝑣))⟩ = ⟨((𝐺𝑣) + 1), ((𝐺𝑣)𝐹(2nd ‘(𝑅𝑣)))⟩)
7162, 70eqtr4d 2657 . . 3 ((𝑣 ∈ ω ∧ (𝑅𝑣) = ⟨(𝐺𝑣), (2nd ‘(𝑅𝑣))⟩) → (𝑅‘suc 𝑣) = ⟨(𝐺‘suc 𝑣), (2nd ‘(𝑅‘suc 𝑣))⟩)
7271ex 450 . 2 (𝑣 ∈ ω → ((𝑅𝑣) = ⟨(𝐺𝑣), (2nd ‘(𝑅𝑣))⟩ → (𝑅‘suc 𝑣) = ⟨(𝐺‘suc 𝑣), (2nd ‘(𝑅‘suc 𝑣))⟩))
735, 10, 15, 20, 36, 72finds 7077 1 (𝐵 ∈ ω → (𝑅𝐵) = ⟨(𝐺𝐵), (2nd ‘(𝑅𝐵))⟩)
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ∧ wa 384   = wceq 1481   ∈ wcel 1988  Vcvv 3195  ∅c0 3907  ⟨cop 4174   ↦ cmpt 4720   ↾ cres 5106  suc csuc 5713  ‘cfv 5876  (class class class)co 6635   ↦ cmpt2 6637  ωcom 7050  2nd c2nd 7152  reccrdg 7490  1c1 9922   + caddc 9924  ℤcz 11362 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1720  ax-4 1735  ax-5 1837  ax-6 1886  ax-7 1933  ax-8 1990  ax-9 1997  ax-10 2017  ax-11 2032  ax-12 2045  ax-13 2244  ax-ext 2600  ax-sep 4772  ax-nul 4780  ax-pow 4834  ax-pr 4897  ax-un 6934 This theorem depends on definitions:  df-bi 197  df-or 385  df-an 386  df-3or 1037  df-3an 1038  df-tru 1484  df-ex 1703  df-nf 1708  df-sb 1879  df-eu 2472  df-mo 2473  df-clab 2607  df-cleq 2613  df-clel 2616  df-nfc 2751  df-ne 2792  df-ral 2914  df-rex 2915  df-reu 2916  df-rab 2918  df-v 3197  df-sbc 3430  df-csb 3527  df-dif 3570  df-un 3572  df-in 3574  df-ss 3581  df-pss 3583  df-nul 3908  df-if 4078  df-pw 4151  df-sn 4169  df-pr 4171  df-tp 4173  df-op 4175  df-uni 4428  df-iun 4513  df-br 4645  df-opab 4704  df-mpt 4721  df-tr 4744  df-id 5014  df-eprel 5019  df-po 5025  df-so 5026  df-fr 5063  df-we 5065  df-xp 5110  df-rel 5111  df-cnv 5112  df-co 5113  df-dm 5114  df-rn 5115  df-res 5116  df-ima 5117  df-pred 5668  df-ord 5714  df-on 5715  df-lim 5716  df-suc 5717  df-iota 5839  df-fun 5878  df-fn 5879  df-f 5880  df-f1 5881  df-fo 5882  df-f1o 5883  df-fv 5884  df-ov 6638  df-oprab 6639  df-mpt2 6640  df-om 7051  df-2nd 7154  df-wrecs 7392  df-recs 7453  df-rdg 7491 This theorem is referenced by:  uzrdglem  12739  uzrdgfni  12740  uzrdgsuci  12742
 Copyright terms: Public domain W3C validator