Definition df-frec 6535

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 6449 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 6541 and frecsuc 6551.

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 4695. 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 6552, this definition and df-irdg 6514 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.)

Assertion

Ref	Expression
df-frec	⊢ frec(𝐹, 𝐼) = (recs((𝑔 ∈ V ↦ {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼))})) ↾ ω)

Distinct variable groups:   𝑥,𝑔,𝑚,𝐹   𝑥,𝐼,𝑔,𝑚

Detailed syntax breakdown of Definition df-frec

Step	Hyp	Ref	Expression
1		cF	. . 3 class 𝐹
2		cI	. . 3 class 𝐼
3	1, 2	cfrec 6534	. 2 class frec(𝐹, 𝐼)
4		vg	. . . . 5 setvar 𝑔
5		cvv 2799	. . . . 5 class V
6	4	cv 1394	. . . . . . . . . . 11 class 𝑔
7	6	cdm 4718	. . . . . . . . . 10 class dom 𝑔
8		vm	. . . . . . . . . . . 12 setvar 𝑚
9	8	cv 1394	. . . . . . . . . . 11 class 𝑚
10	9	csuc 4455	. . . . . . . . . 10 class suc 𝑚
11	7, 10	wceq 1395	. . . . . . . . 9 wff dom 𝑔 = suc 𝑚
12		vx	. . . . . . . . . . 11 setvar 𝑥
13	12	cv 1394	. . . . . . . . . 10 class 𝑥
14	9, 6	cfv 5317	. . . . . . . . . . 11 class (𝑔‘𝑚)
15	14, 1	cfv 5317	. . . . . . . . . 10 class (𝐹‘(𝑔‘𝑚))
16	13, 15	wcel 2200	. . . . . . . . 9 wff 𝑥 ∈ (𝐹‘(𝑔‘𝑚))
17	11, 16	wa 104	. . . . . . . 8 wff (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚)))
18		com 4681	. . . . . . . 8 class ω
19	17, 8, 18	wrex 2509	. . . . . . 7 wff ∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚)))
20		c0 3491	. . . . . . . . 9 class ∅
21	7, 20	wceq 1395	. . . . . . . 8 wff dom 𝑔 = ∅
22	13, 2	wcel 2200	. . . . . . . 8 wff 𝑥 ∈ 𝐼
23	21, 22	wa 104	. . . . . . 7 wff (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼)
24	19, 23	wo 713	. . . . . 6 wff (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼))
25	24, 12	cab 2215	. . . . 5 class {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼))}
26	4, 5, 25	cmpt 4144	. . . 4 class (𝑔 ∈ V ↦ {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼))})
27	26	crecs 6448	. . 3 class recs((𝑔 ∈ V ↦ {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼))}))
28	27, 18	cres 4720	. 2 class (recs((𝑔 ∈ V ↦ {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼))})) ↾ ω)
29	3, 28	wceq 1395	1 wff frec(𝐹, 𝐼) = (recs((𝑔 ∈ V ↦ {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚 ∧ 𝑥 ∈ (𝐹‘(𝑔‘𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥 ∈ 𝐼))})) ↾ ω)

This definition is referenced by:  freceq1  6536  freceq2  6537  frecex  6538  frecfun  6539  nffrec  6540  frec0g  6541  frecfnom  6545  freccllem  6546  frecfcllem  6548  frecsuclem  6550