![]() |
Intuitionistic Logic Explorer |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > ILE Home > Th. List > df-frec | GIF version |
Description: Define a recursive
definition generator on ω (the class of finite
ordinals) with characteristic function 𝐹 and initial value 𝐼.
This rather amazing operation allows us to define, with compact direct
definitions, functions that are usually defined in textbooks only with
indirect self-referencing recursive definitions. A recursive definition
requires advanced metalogic to justify - in particular, eliminating a
recursive definition is very difficult and often not even shown in
textbooks. On the other hand, the elimination of a direct definition is
a matter of simple mechanical substitution. The price paid is the
daunting complexity of our frec operation
(especially when df-recs 6305
that it is built on is also eliminated). But once we get past this
hurdle, definitions that would otherwise be recursive become relatively
simple; see frec0g 6397 and frecsuc 6407.
Unlike with transfinite recursion, finite recurson can readily divide definitions and proofs into zero and successor cases, because even without excluded middle we have theorems such as nn0suc 4603. The analogous situation with transfinite recursion - being able to say that an ordinal is zero, successor, or limit - is enabled by excluded middle and thus is not available to us. For the characteristic functions which satisfy the conditions given at frecrdg 6408, this definition and df-irdg 6370 restricted to ω produce the same result. Note: We introduce frec with the philosophical goal of being able to eliminate all definitions with direct mechanical substitution and to verify easily the soundness of definitions. Metamath itself has no built-in technical limitation that prevents multiple-part recursive definitions in the traditional textbook style. (Contributed by Mario Carneiro and Jim Kingdon, 10-Aug-2019.) |
Ref | Expression |
---|---|
df-frec | ⊢ frec(𝐹, 𝐼) = (recs((𝑔 ∈ V ↦ {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼))})) ↾ ω) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | cF | . . 3 class 𝐹 | |
2 | cI | . . 3 class 𝐼 | |
3 | 1, 2 | cfrec 6390 | . 2 class frec(𝐹, 𝐼) |
4 | vg | . . . . 5 setvar 𝑔 | |
5 | cvv 2737 | . . . . 5 class V | |
6 | 4 | cv 1352 | . . . . . . . . . . 11 class 𝑔 |
7 | 6 | cdm 4626 | . . . . . . . . . 10 class dom 𝑔 |
8 | vm | . . . . . . . . . . . 12 setvar 𝑚 | |
9 | 8 | cv 1352 | . . . . . . . . . . 11 class 𝑚 |
10 | 9 | csuc 4365 | . . . . . . . . . 10 class suc 𝑚 |
11 | 7, 10 | wceq 1353 | . . . . . . . . 9 wff dom 𝑔 = suc 𝑚 |
12 | vx | . . . . . . . . . . 11 setvar 𝑥 | |
13 | 12 | cv 1352 | . . . . . . . . . 10 class 𝑥 |
14 | 9, 6 | cfv 5216 | . . . . . . . . . . 11 class (𝑔‘𝑚) |
15 | 14, 1 | cfv 5216 | . . . . . . . . . 10 class (𝐹‘(𝑔‘𝑚)) |
16 | 13, 15 | wcel 2148 | . . . . . . . . 9 wff 𝑥 ∈ (𝐹‘(𝑔‘𝑚)) |
17 | 11, 16 | wa 104 | . . . . . . . 8 wff (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) |
18 | com 4589 | . . . . . . . 8 class ω | |
19 | 17, 8, 18 | wrex 2456 | . . . . . . 7 wff ∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) |
20 | c0 3422 | . . . . . . . . 9 class ∅ | |
21 | 7, 20 | wceq 1353 | . . . . . . . 8 wff dom 𝑔 = ∅ |
22 | 13, 2 | wcel 2148 | . . . . . . . 8 wff 𝑥 ∈ 𝐼 |
23 | 21, 22 | wa 104 | . . . . . . 7 wff (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼) |
24 | 19, 23 | wo 708 | . . . . . 6 wff (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼)) |
25 | 24, 12 | cab 2163 | . . . . 5 class {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼))} |
26 | 4, 5, 25 | cmpt 4064 | . . . 4 class (𝑔 ∈ V ↦ {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼))}) |
27 | 26 | crecs 6304 | . . 3 class recs((𝑔 ∈ V ↦ {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼))})) |
28 | 27, 18 | cres 4628 | . 2 class (recs((𝑔 ∈ V ↦ {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼))})) ↾ ω) |
29 | 3, 28 | wceq 1353 | 1 wff frec(𝐹, 𝐼) = (recs((𝑔 ∈ V ↦ {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼))})) ↾ ω) |
Colors of variables: wff set class |
This definition is referenced by: freceq1 6392 freceq2 6393 frecex 6394 frecfun 6395 nffrec 6396 frec0g 6397 frecfnom 6401 freccllem 6402 frecfcllem 6404 frecsuclem 6406 |
Copyright terms: Public domain | W3C validator |