P. 80 of Theorem List - Metamath Proof Explorer

Theorem List for Metamath Proof Explorer - 7901-8000   *Has distinct variable group(s)

Type	Label	Description
Statement
Theorem	tposf1o2 7901	Condition of a bijective transposition. (Contributed by NM, 10-Sep-2015.)
⊢ (Rel 𝐴 → (𝐹:𝐴–1-1-onto→𝐵 → tpos 𝐹:◡𝐴–1-1-onto→𝐵))
Theorem	tposfo 7902	The domain and range of a transposition. (Contributed by NM, 10-Sep-2015.)
⊢ (𝐹:(𝐴 × 𝐵)–onto→𝐶 → tpos 𝐹:(𝐵 × 𝐴)–onto→𝐶)
Theorem	tposf 7903	The domain and range of a transposition. (Contributed by NM, 10-Sep-2015.)
⊢ (𝐹:(𝐴 × 𝐵)⟶𝐶 → tpos 𝐹:(𝐵 × 𝐴)⟶𝐶)
Theorem	tposfn 7904	Functionality of a transposition. (Contributed by Mario Carneiro, 4-Oct-2015.)
⊢ (𝐹 Fn (𝐴 × 𝐵) → tpos 𝐹 Fn (𝐵 × 𝐴))
Theorem	tpos0 7905	Transposition of the empty set. (Contributed by NM, 10-Sep-2015.)
⊢ tpos ∅ = ∅
Theorem	tposco 7906	Transposition of a composition. (Contributed by Mario Carneiro, 4-Oct-2015.)
⊢ tpos (𝐹 ∘ 𝐺) = (𝐹 ∘ tpos 𝐺)
Theorem	tpossym 7907*	Two ways to say a function is symmetric. (Contributed by Mario Carneiro, 4-Oct-2015.)
⊢ (𝐹 Fn (𝐴 × 𝐴) → (tpos 𝐹 = 𝐹 ↔ ∀𝑥 ∈ 𝐴 ∀𝑦 ∈ 𝐴 (𝑥𝐹𝑦) = (𝑦𝐹𝑥)))
Theorem	tposeqi 7908	Equality theorem for transposition. (Contributed by Mario Carneiro, 10-Sep-2015.)
⊢ 𝐹 = 𝐺    ⇒   ⊢ tpos 𝐹 = tpos 𝐺
Theorem	tposex 7909	A transposition is a set. (Contributed by Mario Carneiro, 10-Sep-2015.)
⊢ 𝐹 ∈ V    ⇒   ⊢ tpos 𝐹 ∈ V
Theorem	nftpos 7910	Hypothesis builder for transposition. (Contributed by Mario Carneiro, 10-Sep-2015.)
⊢ Ⅎ𝑥𝐹    ⇒   ⊢ Ⅎ𝑥tpos 𝐹
Theorem	tposoprab 7911*	Transposition of a class of ordered triples. (Contributed by Mario Carneiro, 10-Sep-2015.)
⊢ 𝐹 = {⟨⟨𝑥, 𝑦⟩, 𝑧⟩ ∣ 𝜑}    ⇒   ⊢ tpos 𝐹 = {⟨⟨𝑦, 𝑥⟩, 𝑧⟩ ∣ 𝜑}
Theorem	tposmpo 7912*	Transposition of a two-argument mapping. (Contributed by Mario Carneiro, 10-Sep-2015.)
⊢ 𝐹 = (𝑥 ∈ 𝐴, 𝑦 ∈ 𝐵 ↦ 𝐶)    ⇒   ⊢ tpos 𝐹 = (𝑦 ∈ 𝐵, 𝑥 ∈ 𝐴 ↦ 𝐶)
Theorem	tposconst 7913	The transposition of a constant operation using the relation representation. (Contributed by SO, 11-Jul-2018.)
⊢ tpos ((𝐴 × 𝐵) × {𝐶}) = ((𝐵 × 𝐴) × {𝐶})
2.4.12  Curry and uncurry
Syntax	ccur 7914	Extend class notation to include the currying function.
class curry 𝐴
Syntax	cunc 7915	Extend class notation to include the uncurrying function.
class uncurry 𝐴
Definition	df-cur 7916*	Define the currying of 𝐹, which splits a function of two arguments into a function of the first argument, producing a function over the second argument. (Contributed by Mario Carneiro, 7-Jan-2017.)
⊢ curry 𝐹 = (𝑥 ∈ dom dom 𝐹 ↦ {⟨𝑦, 𝑧⟩ ∣ ⟨𝑥, 𝑦⟩𝐹𝑧})
Definition	df-unc 7917*	Define the uncurrying of 𝐹, which takes a function producing functions, and transforms it into a two-argument function. (Contributed by Mario Carneiro, 7-Jan-2017.)
⊢ uncurry 𝐹 = {⟨⟨𝑥, 𝑦⟩, 𝑧⟩ ∣ 𝑦(𝐹‘𝑥)𝑧}
Theorem	mpocurryd 7918*	The currying of an operation given in maps-to notation, splitting the operation (function of two arguments) into a function of the first argument, producing a function over the second argument. (Contributed by AV, 27-Oct-2019.)
⊢ 𝐹 = (𝑥 ∈ 𝑋, 𝑦 ∈ 𝑌 ↦ 𝐶)    &   ⊢ (𝜑 → ∀𝑥 ∈ 𝑋 ∀𝑦 ∈ 𝑌 𝐶 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑌 ≠ ∅)    ⇒   ⊢ (𝜑 → curry 𝐹 = (𝑥 ∈ 𝑋 ↦ (𝑦 ∈ 𝑌 ↦ 𝐶)))
Theorem	mpocurryvald 7919*	The value of a curried operation given in maps-to notation is a function over the second argument of the original operation. (Contributed by AV, 27-Oct-2019.)
⊢ 𝐹 = (𝑥 ∈ 𝑋, 𝑦 ∈ 𝑌 ↦ 𝐶)    &   ⊢ (𝜑 → ∀𝑥 ∈ 𝑋 ∀𝑦 ∈ 𝑌 𝐶 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑌 ≠ ∅)    &   ⊢ (𝜑 → 𝑌 ∈ 𝑊)    &   ⊢ (𝜑 → 𝐴 ∈ 𝑋)    ⇒   ⊢ (𝜑 → (curry 𝐹‘𝐴) = (𝑦 ∈ 𝑌 ↦ ⦋𝐴 / 𝑥⦌𝐶))
Theorem	fvmpocurryd 7920*	The value of the value of a curried operation given in maps-to notation is the operation value of the original operation. (Contributed by AV, 27-Oct-2019.)
⊢ 𝐹 = (𝑥 ∈ 𝑋, 𝑦 ∈ 𝑌 ↦ 𝐶)    &   ⊢ (𝜑 → ∀𝑥 ∈ 𝑋 ∀𝑦 ∈ 𝑌 𝐶 ∈ 𝑉)    &   ⊢ (𝜑 → 𝑌 ∈ 𝑊)    &   ⊢ (𝜑 → 𝐴 ∈ 𝑋)    &   ⊢ (𝜑 → 𝐵 ∈ 𝑌)    ⇒   ⊢ (𝜑 → ((curry 𝐹‘𝐴)‘𝐵) = (𝐴𝐹𝐵))
2.4.13  Undefined values
Syntax	cund 7921	Extend class notation with undefined value function.
class Undef
Definition	df-undef 7922	Define the undefined value function, whose value at set 𝑠 is guaranteed not to be a member of 𝑠 (see pwuninel 7924). (Contributed by NM, 15-Sep-2011.)
⊢ Undef = (𝑠 ∈ V ↦ 𝒫 ∪ 𝑠)
Theorem	pwuninel2 7923	Direct proof of pwuninel 7924 avoiding functions and thus several ZF axioms. (Contributed by Stefan O'Rear, 22-Feb-2015.)
⊢ (∪ 𝐴 ∈ 𝑉 → ¬ 𝒫 ∪ 𝐴 ∈ 𝐴)
Theorem	pwuninel 7924	The power set of the union of a set does not belong to the set. This theorem provides a way of constructing a new set that doesn't belong to a given set. See also pwuninel2 7923. (Contributed by NM, 27-Jun-2008.) (Proof shortened by Mario Carneiro, 23-Dec-2016.)
⊢ ¬ 𝒫 ∪ 𝐴 ∈ 𝐴
Theorem	undefval 7925	Value of the undefined value function. Normally we will not reference the explicit value but will use undefnel 7927 instead. (Contributed by NM, 15-Sep-2011.) (Revised by Mario Carneiro, 24-Dec-2016.)
⊢ (𝑆 ∈ 𝑉 → (Undef‘𝑆) = 𝒫 ∪ 𝑆)
Theorem	undefnel2 7926	The undefined value generated from a set is not a member of the set. (Contributed by NM, 15-Sep-2011.)
⊢ (𝑆 ∈ 𝑉 → ¬ (Undef‘𝑆) ∈ 𝑆)
Theorem	undefnel 7927	The undefined value generated from a set is not a member of the set. (Contributed by NM, 15-Sep-2011.)
⊢ (𝑆 ∈ 𝑉 → (Undef‘𝑆) ∉ 𝑆)
Theorem	undefne0 7928	The undefined value generated from a set is not empty. (Contributed by NM, 3-Sep-2018.)
⊢ (𝑆 ∈ 𝑉 → (Undef‘𝑆) ≠ ∅)
2.4.14  Well-founded recursion
Syntax	cwrecs 7929	Declare syntax for the well-founded recursive function generator.
class wrecs(𝑅, 𝐴, 𝐹)
Definition	df-wrecs 7930*	Here we define the well-founded recursive function generator. This function takes the usual expressions from recursion theorems and forms a unified definition. Specifically, given a function 𝐹, a relationship 𝑅, and a base set 𝐴, this definition generates a function 𝐺 = wrecs(𝑅, 𝐴, 𝐹) that has property that, at any point 𝑥 ∈ 𝐴, (𝐺‘𝑥) = (𝐹‘(𝐺 ↾ Pred(𝑅, 𝐴, 𝑥))). See wfr1 7956, wfr2 7957, and wfr3 7958. (Contributed by Scott Fenton, 7-Jun-2018.) (New usage is discouraged.)
⊢ wrecs(𝑅, 𝐴, 𝐹) = ∪ {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐹‘(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}
Theorem	wrecseq123 7931	General equality theorem for the well-founded recursive function generator. (Contributed by Scott Fenton, 7-Jun-2018.)
⊢ ((𝑅 = 𝑆 ∧ 𝐴 = 𝐵 ∧ 𝐹 = 𝐺) → wrecs(𝑅, 𝐴, 𝐹) = wrecs(𝑆, 𝐵, 𝐺))
Theorem	nfwrecs 7932	Bound-variable hypothesis builder for the well-founded recursive function generator. (Contributed by Scott Fenton, 9-Jun-2018.)
⊢ Ⅎ𝑥𝑅    &   ⊢ Ⅎ𝑥𝐴    &   ⊢ Ⅎ𝑥𝐹    ⇒   ⊢ Ⅎ𝑥wrecs(𝑅, 𝐴, 𝐹)
Theorem	wrecseq1 7933	Equality theorem for the well-founded recursive function generator. (Contributed by Scott Fenton, 7-Jun-2018.)
⊢ (𝑅 = 𝑆 → wrecs(𝑅, 𝐴, 𝐹) = wrecs(𝑆, 𝐴, 𝐹))
Theorem	wrecseq2 7934	Equality theorem for the well-founded recursive function generator. (Contributed by Scott Fenton, 7-Jun-2018.)
⊢ (𝐴 = 𝐵 → wrecs(𝑅, 𝐴, 𝐹) = wrecs(𝑅, 𝐵, 𝐹))
Theorem	wrecseq3 7935	Equality theorem for the well-founded recursive function generator. (Contributed by Scott Fenton, 7-Jun-2018.)
⊢ (𝐹 = 𝐺 → wrecs(𝑅, 𝐴, 𝐹) = wrecs(𝑅, 𝐴, 𝐺))
Theorem	wfr3g 7936*	Functions defined by well-founded recursion are identical up to relation, domain, and characteristic function. (Contributed by Scott Fenton, 11-Feb-2011.)
⊢ (((𝑅 We 𝐴 ∧ 𝑅 Se 𝐴) ∧ (𝐹 Fn 𝐴 ∧ ∀𝑦 ∈ 𝐴 (𝐹‘𝑦) = (𝐻‘(𝐹 ↾ Pred(𝑅, 𝐴, 𝑦)))) ∧ (𝐺 Fn 𝐴 ∧ ∀𝑦 ∈ 𝐴 (𝐺‘𝑦) = (𝐻‘(𝐺 ↾ Pred(𝑅, 𝐴, 𝑦))))) → 𝐹 = 𝐺)
Theorem	wfrlem1 7937*	Lemma for well-founded recursion. The final item we are interested in is the union of acceptable functions 𝐵. This lemma just changes bound variables for later use. (Contributed by Scott Fenton, 21-Apr-2011.)
⊢ 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐹‘(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}    ⇒   ⊢ 𝐵 = {𝑔 ∣ ∃𝑧(𝑔 Fn 𝑧 ∧ (𝑧 ⊆ 𝐴 ∧ ∀𝑤 ∈ 𝑧 Pred(𝑅, 𝐴, 𝑤) ⊆ 𝑧) ∧ ∀𝑤 ∈ 𝑧 (𝑔‘𝑤) = (𝐹‘(𝑔 ↾ Pred(𝑅, 𝐴, 𝑤))))}
Theorem	wfrlem2 7938*	Lemma for well-founded recursion. An acceptable function is a function. (Contributed by Scott Fenton, 21-Apr-2011.)
⊢ 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐹‘(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}    ⇒   ⊢ (𝑔 ∈ 𝐵 → Fun 𝑔)
Theorem	wfrlem3 7939*	Lemma for well-founded recursion. An acceptable function's domain is a subset of 𝐴. (Contributed by Scott Fenton, 21-Apr-2011.)
⊢ 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐹‘(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}    ⇒   ⊢ (𝑔 ∈ 𝐵 → dom 𝑔 ⊆ 𝐴)
Theorem	wfrlem3a 7940*	Lemma for well-founded recursion. Show membership in the class of acceptable functions. (Contributed by Scott Fenton, 31-Jul-2020.)
⊢ 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐹‘(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}    &   ⊢ 𝐺 ∈ V    ⇒   ⊢ (𝐺 ∈ 𝐵 ↔ ∃𝑧(𝐺 Fn 𝑧 ∧ (𝑧 ⊆ 𝐴 ∧ ∀𝑤 ∈ 𝑧 Pred(𝑅, 𝐴, 𝑤) ⊆ 𝑧) ∧ ∀𝑤 ∈ 𝑧 (𝐺‘𝑤) = (𝐹‘(𝐺 ↾ Pred(𝑅, 𝐴, 𝑤)))))
Theorem	wfrlem4 7941*	Lemma for well-founded recursion. Properties of the restriction of an acceptable function to the domain of another one. (Contributed by Scott Fenton, 21-Apr-2011.) (Revised by AV, 18-Jul-2022.)
⊢ 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐹‘(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}    ⇒   ⊢ ((𝑔 ∈ 𝐵 ∧ ℎ ∈ 𝐵) → ((𝑔 ↾ (dom 𝑔 ∩ dom ℎ)) Fn (dom 𝑔 ∩ dom ℎ) ∧ ∀𝑎 ∈ (dom 𝑔 ∩ dom ℎ)((𝑔 ↾ (dom 𝑔 ∩ dom ℎ))‘𝑎) = (𝐹‘((𝑔 ↾ (dom 𝑔 ∩ dom ℎ)) ↾ Pred(𝑅, (dom 𝑔 ∩ dom ℎ), 𝑎)))))
Theorem	wfrlem5 7942*	Lemma for well-founded recursion. The values of two acceptable functions agree within their domains. (Contributed by Scott Fenton, 21-Apr-2011.) (Revised by Mario Carneiro, 26-Jun-2015.)
⊢ 𝑅 We 𝐴    &   ⊢ 𝑅 Se 𝐴    &   ⊢ 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐹‘(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}    ⇒   ⊢ ((𝑔 ∈ 𝐵 ∧ ℎ ∈ 𝐵) → ((𝑥𝑔𝑢 ∧ 𝑥ℎ𝑣) → 𝑢 = 𝑣))
Theorem	wfrrel 7943	The well-founded recursion generator generates a relationship. (Contributed by Scott Fenton, 8-Jun-2018.)
⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    ⇒   ⊢ Rel 𝐹
Theorem	wfrdmss 7944	The domain of the well-founded recursion generator is a subclass of 𝐴. (Contributed by Scott Fenton, 21-Apr-2011.)
⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    ⇒   ⊢ dom 𝐹 ⊆ 𝐴
Theorem	wfrlem8 7945	Lemma for well-founded recursion. Compute the prececessor class for an 𝑅 minimal element of (𝐴 ∖ dom 𝐹). (Contributed by Scott Fenton, 21-Apr-2011.)
⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    ⇒   ⊢ (Pred(𝑅, (𝐴 ∖ dom 𝐹), 𝑋) = ∅ ↔ Pred(𝑅, 𝐴, 𝑋) = Pred(𝑅, dom 𝐹, 𝑋))
Theorem	wfrdmcl 7946	Given 𝐹 = wrecs(𝑅, 𝐴, 𝑋) ∧ 𝑋 ∈ dom 𝐹, then its predecessor class is a subset of dom 𝐹. (Contributed by Scott Fenton, 21-Apr-2011.)
⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    ⇒   ⊢ (𝑋 ∈ dom 𝐹 → Pred(𝑅, 𝐴, 𝑋) ⊆ dom 𝐹)
Theorem	wfrlem10 7947*	Lemma for well-founded recursion. When 𝑧 is an 𝑅 minimal element of (𝐴 ∖ dom 𝐹), then its predecessor class is equal to dom 𝐹. (Contributed by Scott Fenton, 21-Apr-2011.)
⊢ 𝑅 We 𝐴    &   ⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    ⇒   ⊢ ((𝑧 ∈ (𝐴 ∖ dom 𝐹) ∧ Pred(𝑅, (𝐴 ∖ dom 𝐹), 𝑧) = ∅) → Pred(𝑅, 𝐴, 𝑧) = dom 𝐹)
Theorem	wfrfun 7948	The well-founded function generator generates a function. (Contributed by Scott Fenton, 21-Apr-2011.) (Revised by Mario Carneiro, 26-Jun-2015.)
⊢ 𝑅 We 𝐴    &   ⊢ 𝑅 Se 𝐴    &   ⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    ⇒   ⊢ Fun 𝐹
Theorem	wfrlem12 7949*	Lemma for well-founded recursion. Here, we compute the value of the recursive definition generator. (Contributed by Scott Fenton, 21-Apr-2011.) (Revised by Mario Carneiro, 26-Jun-2015.)
⊢ 𝑅 We 𝐴    &   ⊢ 𝑅 Se 𝐴    &   ⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    ⇒   ⊢ (𝑦 ∈ dom 𝐹 → (𝐹‘𝑦) = (𝐺‘(𝐹 ↾ Pred(𝑅, 𝐴, 𝑦))))
Theorem	wfrlem13 7950*	Lemma for well-founded recursion. From here through wfrlem16 7953, we aim to prove that dom 𝐹 = 𝐴. We do this by supposing that there is an element 𝑧 of 𝐴 that is not in dom 𝐹. We then define 𝐶 by extending dom 𝐹 with the appropriate value at 𝑧. We then show that 𝑧 cannot be an 𝑅 minimal element of (𝐴 ∖ dom 𝐹), meaning that (𝐴 ∖ dom 𝐹) must be empty, so dom 𝐹 = 𝐴. Here, we show that 𝐶 is a function extending the domain of 𝐹 by one. (Contributed by Scott Fenton, 21-Apr-2011.) (Revised by Mario Carneiro, 26-Jun-2015.)
⊢ 𝑅 We 𝐴    &   ⊢ 𝑅 Se 𝐴    &   ⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    &   ⊢ 𝐶 = (𝐹 ∪ {⟨𝑧, (𝐺‘(𝐹 ↾ Pred(𝑅, 𝐴, 𝑧)))⟩})    ⇒   ⊢ (𝑧 ∈ (𝐴 ∖ dom 𝐹) → 𝐶 Fn (dom 𝐹 ∪ {𝑧}))
Theorem	wfrlem14 7951*	Lemma for well-founded recursion. Compute the value of 𝐶. (Contributed by Scott Fenton, 21-Apr-2011.)
⊢ 𝑅 We 𝐴    &   ⊢ 𝑅 Se 𝐴    &   ⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    &   ⊢ 𝐶 = (𝐹 ∪ {⟨𝑧, (𝐺‘(𝐹 ↾ Pred(𝑅, 𝐴, 𝑧)))⟩})    ⇒   ⊢ (𝑧 ∈ (𝐴 ∖ dom 𝐹) → (𝑦 ∈ (dom 𝐹 ∪ {𝑧}) → (𝐶‘𝑦) = (𝐺‘(𝐶 ↾ Pred(𝑅, 𝐴, 𝑦)))))
Theorem	wfrlem15 7952*	Lemma for well-founded recursion. When 𝑧 is 𝑅 minimal, 𝐶 is an acceptable function. This step is where the Axiom of Replacement becomes required. (Contributed by Scott Fenton, 21-Apr-2011.)
⊢ 𝑅 We 𝐴    &   ⊢ 𝑅 Se 𝐴    &   ⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    &   ⊢ 𝐶 = (𝐹 ∪ {⟨𝑧, (𝐺‘(𝐹 ↾ Pred(𝑅, 𝐴, 𝑧)))⟩})    ⇒   ⊢ ((𝑧 ∈ (𝐴 ∖ dom 𝐹) ∧ Pred(𝑅, (𝐴 ∖ dom 𝐹), 𝑧) = ∅) → 𝐶 ∈ {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐺‘(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))})
Theorem	wfrlem16 7953*	Lemma for well-founded recursion. If 𝑧 is 𝑅 minimal in (𝐴 ∖ dom 𝐹), then 𝐶 is acceptable and thus a subset of 𝐹, but dom 𝐶 is bigger than dom 𝐹. Thus, 𝑧 cannot be minimal, so (𝐴 ∖ dom 𝐹) must be empty, and (due to wfrdmss 7944), dom 𝐹 = 𝐴. (Contributed by Scott Fenton, 21-Apr-2011.)
⊢ 𝑅 We 𝐴    &   ⊢ 𝑅 Se 𝐴    &   ⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    &   ⊢ 𝐶 = (𝐹 ∪ {⟨𝑧, (𝐺‘(𝐹 ↾ Pred(𝑅, 𝐴, 𝑧)))⟩})    ⇒   ⊢ dom 𝐹 = 𝐴
Theorem	wfrlem17 7954	Without using ax-rep 5154, show that all restrictions of wrecs are sets. (Contributed by Scott Fenton, 31-Jul-2020.)
⊢ 𝑅 We 𝐴    &   ⊢ 𝑅 Se 𝐴    &   ⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    ⇒   ⊢ (𝑋 ∈ dom 𝐹 → (𝐹 ↾ Pred(𝑅, 𝐴, 𝑋)) ∈ V)
Theorem	wfr2a 7955	A weak version of wfr2 7957 which is useful for proofs that avoid the Axiom of Replacement. (Contributed by Scott Fenton, 30-Jul-2020.)
⊢ 𝑅 We 𝐴    &   ⊢ 𝑅 Se 𝐴    &   ⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    ⇒   ⊢ (𝑋 ∈ dom 𝐹 → (𝐹‘𝑋) = (𝐺‘(𝐹 ↾ Pred(𝑅, 𝐴, 𝑋))))
Theorem	wfr1 7956	The Principle of Well-Founded Recursion, part 1 of 3. We start with an arbitrary function 𝐺. Then, using a base class 𝐴 and a well-ordering 𝑅 of 𝐴, we define a function 𝐹. This function is said to be defined by "well-founded recursion." The purpose of these three theorems is to demonstrate the properties of 𝐹. We begin by showing that 𝐹 is a function over 𝐴. (Contributed by Scott Fenton, 22-Apr-2011.) (Revised by Mario Carneiro, 26-Jun-2015.)
⊢ 𝑅 We 𝐴    &   ⊢ 𝑅 Se 𝐴    &   ⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    ⇒   ⊢ 𝐹 Fn 𝐴
Theorem	wfr2 7957	The Principle of Well-Founded Recursion, part 2 of 3. Next, we show that the value of 𝐹 at any 𝑋 ∈ 𝐴 is 𝐺 recursively applied to all "previous" values of 𝐹. (Contributed by Scott Fenton, 18-Apr-2011.) (Revised by Mario Carneiro, 26-Jun-2015.)
⊢ 𝑅 We 𝐴    &   ⊢ 𝑅 Se 𝐴    &   ⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    ⇒   ⊢ (𝑋 ∈ 𝐴 → (𝐹‘𝑋) = (𝐺‘(𝐹 ↾ Pred(𝑅, 𝐴, 𝑋))))
Theorem	wfr3 7958*	The principle of Well-Founded Recursion, part 3 of 3. Finally, we show that 𝐹 is unique. We do this by showing that any function 𝐻 with the same properties we proved of 𝐹 in wfr1 7956 and wfr2 7957 is identical to 𝐹. (Contributed by Scott Fenton, 18-Apr-2011.) (Revised by Mario Carneiro, 26-Jun-2015.)
⊢ 𝑅 We 𝐴    &   ⊢ 𝑅 Se 𝐴    &   ⊢ 𝐹 = wrecs(𝑅, 𝐴, 𝐺)    ⇒   ⊢ ((𝐻 Fn 𝐴 ∧ ∀𝑧 ∈ 𝐴 (𝐻‘𝑧) = (𝐺‘(𝐻 ↾ Pred(𝑅, 𝐴, 𝑧)))) → 𝐹 = 𝐻)
2.4.15  Functions on ordinals; strictly monotone ordinal functions
Theorem	iunon 7959*	The indexed union of a set of ordinal numbers 𝐵(𝑥) is an ordinal number. (Contributed by NM, 13-Oct-2003.) (Revised by Mario Carneiro, 5-Dec-2016.)
⊢ ((𝐴 ∈ 𝑉 ∧ ∀𝑥 ∈ 𝐴 𝐵 ∈ On) → ∪ 𝑥 ∈ 𝐴 𝐵 ∈ On)
Theorem	iinon 7960*	The nonempty indexed intersection of a class of ordinal numbers 𝐵(𝑥) is an ordinal number. (Contributed by NM, 13-Oct-2003.) (Proof shortened by Mario Carneiro, 5-Dec-2016.)
⊢ ((∀𝑥 ∈ 𝐴 𝐵 ∈ On ∧ 𝐴 ≠ ∅) → ∩ 𝑥 ∈ 𝐴 𝐵 ∈ On)
Theorem	onfununi 7961*	A property of functions on ordinal numbers. Generalization of Theorem Schema 8E of [Enderton] p. 218. (Contributed by Eric Schmidt, 26-May-2009.)
⊢ (Lim 𝑦 → (𝐹‘𝑦) = ∪ 𝑥 ∈ 𝑦 (𝐹‘𝑥))    &   ⊢ ((𝑥 ∈ On ∧ 𝑦 ∈ On ∧ 𝑥 ⊆ 𝑦) → (𝐹‘𝑥) ⊆ (𝐹‘𝑦))    ⇒   ⊢ ((𝑆 ∈ 𝑇 ∧ 𝑆 ⊆ On ∧ 𝑆 ≠ ∅) → (𝐹‘∪ 𝑆) = ∪ 𝑥 ∈ 𝑆 (𝐹‘𝑥))
Theorem	onovuni 7962*	A variant of onfununi 7961 for operations. (Contributed by Eric Schmidt, 26-May-2009.) (Revised by Mario Carneiro, 11-Sep-2015.)
⊢ (Lim 𝑦 → (𝐴𝐹𝑦) = ∪ 𝑥 ∈ 𝑦 (𝐴𝐹𝑥))    &   ⊢ ((𝑥 ∈ On ∧ 𝑦 ∈ On ∧ 𝑥 ⊆ 𝑦) → (𝐴𝐹𝑥) ⊆ (𝐴𝐹𝑦))    ⇒   ⊢ ((𝑆 ∈ 𝑇 ∧ 𝑆 ⊆ On ∧ 𝑆 ≠ ∅) → (𝐴𝐹∪ 𝑆) = ∪ 𝑥 ∈ 𝑆 (𝐴𝐹𝑥))
Theorem	onoviun 7963*	A variant of onovuni 7962 with indexed unions. (Contributed by Eric Schmidt, 26-May-2009.) (Proof shortened by Mario Carneiro, 5-Dec-2016.)
⊢ (Lim 𝑦 → (𝐴𝐹𝑦) = ∪ 𝑥 ∈ 𝑦 (𝐴𝐹𝑥))    &   ⊢ ((𝑥 ∈ On ∧ 𝑦 ∈ On ∧ 𝑥 ⊆ 𝑦) → (𝐴𝐹𝑥) ⊆ (𝐴𝐹𝑦))    ⇒   ⊢ ((𝐾 ∈ 𝑇 ∧ ∀𝑧 ∈ 𝐾 𝐿 ∈ On ∧ 𝐾 ≠ ∅) → (𝐴𝐹∪ 𝑧 ∈ 𝐾 𝐿) = ∪ 𝑧 ∈ 𝐾 (𝐴𝐹𝐿))
Theorem	onnseq 7964*	There are no length ω decreasing sequences in the ordinals. See also noinfep 9107 for a stronger version assuming Regularity. (Contributed by Mario Carneiro, 19-May-2015.)
⊢ ((𝐹‘∅) ∈ On → ∃𝑥 ∈ ω ¬ (𝐹‘suc 𝑥) ∈ (𝐹‘𝑥))
Syntax	wsmo 7965	Introduce the strictly monotone ordinal function. A strictly monotone function is one that is constantly increasing across the ordinals.
wff Smo 𝐴
Definition	df-smo 7966*	Definition of a strictly monotone ordinal function. Definition 7.46 in [TakeutiZaring] p. 50. (Contributed by Andrew Salmon, 15-Nov-2011.)
⊢ (Smo 𝐴 ↔ (𝐴:dom 𝐴⟶On ∧ Ord dom 𝐴 ∧ ∀𝑥 ∈ dom 𝐴∀𝑦 ∈ dom 𝐴(𝑥 ∈ 𝑦 → (𝐴‘𝑥) ∈ (𝐴‘𝑦))))
Theorem	dfsmo2 7967*	Alternate definition of a strictly monotone ordinal function. (Contributed by Mario Carneiro, 4-Mar-2013.)
⊢ (Smo 𝐹 ↔ (𝐹:dom 𝐹⟶On ∧ Ord dom 𝐹 ∧ ∀𝑥 ∈ dom 𝐹∀𝑦 ∈ 𝑥 (𝐹‘𝑦) ∈ (𝐹‘𝑥)))
Theorem	issmo 7968*	Conditions for which 𝐴 is a strictly monotone ordinal function. (Contributed by Andrew Salmon, 15-Nov-2011.) Avoid ax-13 2379. (Revised by Gino Giotto, 19-May-2023.)
⊢ 𝐴:𝐵⟶On    &   ⊢ Ord 𝐵    &   ⊢ ((𝑥 ∈ 𝐵 ∧ 𝑦 ∈ 𝐵) → (𝑥 ∈ 𝑦 → (𝐴‘𝑥) ∈ (𝐴‘𝑦)))    &   ⊢ dom 𝐴 = 𝐵    ⇒   ⊢ Smo 𝐴
Theorem	issmo2 7969*	Alternate definition of a strictly monotone ordinal function. (Contributed by Mario Carneiro, 12-Mar-2013.)
⊢ (𝐹:𝐴⟶𝐵 → ((𝐵 ⊆ On ∧ Ord 𝐴 ∧ ∀𝑥 ∈ 𝐴 ∀𝑦 ∈ 𝑥 (𝐹‘𝑦) ∈ (𝐹‘𝑥)) → Smo 𝐹))
Theorem	smoeq 7970	Equality theorem for strictly monotone functions. (Contributed by Andrew Salmon, 16-Nov-2011.)
⊢ (𝐴 = 𝐵 → (Smo 𝐴 ↔ Smo 𝐵))
Theorem	smodm 7971	The domain of a strictly monotone function is an ordinal. (Contributed by Andrew Salmon, 16-Nov-2011.)
⊢ (Smo 𝐴 → Ord dom 𝐴)
Theorem	smores 7972	A strictly monotone function restricted to an ordinal remains strictly monotone. (Contributed by Andrew Salmon, 16-Nov-2011.) (Proof shortened by Mario Carneiro, 5-Dec-2016.)
⊢ ((Smo 𝐴 ∧ 𝐵 ∈ dom 𝐴) → Smo (𝐴 ↾ 𝐵))
Theorem	smores3 7973	A strictly monotone function restricted to an ordinal remains strictly monotone. (Contributed by Andrew Salmon, 19-Nov-2011.)
⊢ ((Smo (𝐴 ↾ 𝐵) ∧ 𝐶 ∈ (dom 𝐴 ∩ 𝐵) ∧ Ord 𝐵) → Smo (𝐴 ↾ 𝐶))
Theorem	smores2 7974	A strictly monotone ordinal function restricted to an ordinal is still monotone. (Contributed by Mario Carneiro, 15-Mar-2013.)
⊢ ((Smo 𝐹 ∧ Ord 𝐴) → Smo (𝐹 ↾ 𝐴))
Theorem	smodm2 7975	The domain of a strictly monotone ordinal function is an ordinal. (Contributed by Mario Carneiro, 12-Mar-2013.)
⊢ ((𝐹 Fn 𝐴 ∧ Smo 𝐹) → Ord 𝐴)
Theorem	smofvon2 7976	The function values of a strictly monotone ordinal function are ordinals. (Contributed by Mario Carneiro, 12-Mar-2013.)
⊢ (Smo 𝐹 → (𝐹‘𝐵) ∈ On)
Theorem	iordsmo 7977	The identity relation restricted to the ordinals is a strictly monotone function. (Contributed by Andrew Salmon, 16-Nov-2011.)
⊢ Ord 𝐴    ⇒   ⊢ Smo ( I ↾ 𝐴)
Theorem	smo0 7978	The null set is a strictly monotone ordinal function. (Contributed by Andrew Salmon, 20-Nov-2011.)
⊢ Smo ∅
Theorem	smofvon 7979	If 𝐵 is a strictly monotone ordinal function, and 𝐴 is in the domain of 𝐵, then the value of the function at 𝐴 is an ordinal. (Contributed by Andrew Salmon, 20-Nov-2011.)
⊢ ((Smo 𝐵 ∧ 𝐴 ∈ dom 𝐵) → (𝐵‘𝐴) ∈ On)
Theorem	smoel 7980	If 𝑥 is less than 𝑦 then a strictly monotone function's value will be strictly less at 𝑥 than at 𝑦. (Contributed by Andrew Salmon, 22-Nov-2011.)
⊢ ((Smo 𝐵 ∧ 𝐴 ∈ dom 𝐵 ∧ 𝐶 ∈ 𝐴) → (𝐵‘𝐶) ∈ (𝐵‘𝐴))
Theorem	smoiun 7981*	The value of a strictly monotone ordinal function contains its indexed union. (Contributed by Andrew Salmon, 22-Nov-2011.)
⊢ ((Smo 𝐵 ∧ 𝐴 ∈ dom 𝐵) → ∪ 𝑥 ∈ 𝐴 (𝐵‘𝑥) ⊆ (𝐵‘𝐴))
Theorem	smoiso 7982	If 𝐹 is an isomorphism from an ordinal 𝐴 onto 𝐵, which is a subset of the ordinals, then 𝐹 is a strictly monotonic function. Exercise 3 in [TakeutiZaring] p. 50. (Contributed by Andrew Salmon, 24-Nov-2011.)
⊢ ((𝐹 Isom E , E (𝐴, 𝐵) ∧ Ord 𝐴 ∧ 𝐵 ⊆ On) → Smo 𝐹)
Theorem	smoel2 7983	A strictly monotone ordinal function preserves the membership relation. (Contributed by Mario Carneiro, 12-Mar-2013.)
⊢ (((𝐹 Fn 𝐴 ∧ Smo 𝐹) ∧ (𝐵 ∈ 𝐴 ∧ 𝐶 ∈ 𝐵)) → (𝐹‘𝐶) ∈ (𝐹‘𝐵))
Theorem	smo11 7984	A strictly monotone ordinal function is one-to-one. (Contributed by Mario Carneiro, 28-Feb-2013.)
⊢ ((𝐹:𝐴⟶𝐵 ∧ Smo 𝐹) → 𝐹:𝐴–1-1→𝐵)
Theorem	smoord 7985	A strictly monotone ordinal function preserves strict ordering. (Contributed by Mario Carneiro, 4-Mar-2013.)
⊢ (((𝐹 Fn 𝐴 ∧ Smo 𝐹) ∧ (𝐶 ∈ 𝐴 ∧ 𝐷 ∈ 𝐴)) → (𝐶 ∈ 𝐷 ↔ (𝐹‘𝐶) ∈ (𝐹‘𝐷)))
Theorem	smoword 7986	A strictly monotone ordinal function preserves weak ordering. (Contributed by Mario Carneiro, 4-Mar-2013.)
⊢ (((𝐹 Fn 𝐴 ∧ Smo 𝐹) ∧ (𝐶 ∈ 𝐴 ∧ 𝐷 ∈ 𝐴)) → (𝐶 ⊆ 𝐷 ↔ (𝐹‘𝐶) ⊆ (𝐹‘𝐷)))
Theorem	smogt 7987	A strictly monotone ordinal function is greater than or equal to its argument. Exercise 1 in [TakeutiZaring] p. 50. (Contributed by Andrew Salmon, 23-Nov-2011.) (Revised by Mario Carneiro, 28-Feb-2013.)
⊢ ((𝐹 Fn 𝐴 ∧ Smo 𝐹 ∧ 𝐶 ∈ 𝐴) → 𝐶 ⊆ (𝐹‘𝐶))
Theorem	smorndom 7988	The range of a strictly monotone ordinal function dominates the domain. (Contributed by Mario Carneiro, 13-Mar-2013.)
⊢ ((𝐹:𝐴⟶𝐵 ∧ Smo 𝐹 ∧ Ord 𝐵) → 𝐴 ⊆ 𝐵)
Theorem	smoiso2 7989	The strictly monotone ordinal functions are also isomorphisms of subclasses of On equipped with the membership relation. (Contributed by Mario Carneiro, 20-Mar-2013.)
⊢ ((Ord 𝐴 ∧ 𝐵 ⊆ On) → ((𝐹:𝐴–onto→𝐵 ∧ Smo 𝐹) ↔ 𝐹 Isom E , E (𝐴, 𝐵)))
2.4.16  "Strong" transfinite recursion
Syntax	crecs 7990	Notation for a function defined by strong transfinite recursion.
class recs(𝐹)
Definition	df-recs 7991	Define a function recs(𝐹) on On, the class of ordinal numbers, by transfinite recursion given a rule 𝐹 which sets the next value given all values so far. See df-rdg 8029 for more details on why this definition is desirable. Unlike df-rdg 8029 which restricts the update rule to use only the previous value, this version allows the update rule to use all previous values, which is why it is described as "strong", although it is actually more primitive. See recsfnon 8022 and recsval 8023 for the primary contract of this definition. (Contributed by Stefan O'Rear, 18-Jan-2015.) (Revised by Scott Fenton, 3-Aug-2020.)
⊢ recs(𝐹) = wrecs( E , On, 𝐹)
Theorem	dfrecs3 7992*	The old definition of transfinite recursion. This version is preferred for development, as it demonstrates the properties of transfinite recursion without relying on well-founded recursion. (Contributed by Scott Fenton, 3-Aug-2020.)
⊢ recs(𝐹) = ∪ {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐹‘(𝑓 ↾ 𝑦)))}
Theorem	recseq 7993	Equality theorem for recs. (Contributed by Stefan O'Rear, 18-Jan-2015.)
⊢ (𝐹 = 𝐺 → recs(𝐹) = recs(𝐺))
Theorem	nfrecs 7994	Bound-variable hypothesis builder for recs. (Contributed by Stefan O'Rear, 18-Jan-2015.)
⊢ Ⅎ𝑥𝐹    ⇒   ⊢ Ⅎ𝑥recs(𝐹)
Theorem	tfrlem1 7995*	A technical lemma for transfinite recursion. Compare Lemma 1 of [TakeutiZaring] p. 47. (Contributed by NM, 23-Mar-1995.) (Revised by Mario Carneiro, 24-May-2019.)
⊢ (𝜑 → 𝐴 ∈ On)    &   ⊢ (𝜑 → (Fun 𝐹 ∧ 𝐴 ⊆ dom 𝐹))    &   ⊢ (𝜑 → (Fun 𝐺 ∧ 𝐴 ⊆ dom 𝐺))    &   ⊢ (𝜑 → ∀𝑥 ∈ 𝐴 (𝐹‘𝑥) = (𝐵‘(𝐹 ↾ 𝑥)))    &   ⊢ (𝜑 → ∀𝑥 ∈ 𝐴 (𝐺‘𝑥) = (𝐵‘(𝐺 ↾ 𝑥)))    ⇒   ⊢ (𝜑 → ∀𝑥 ∈ 𝐴 (𝐹‘𝑥) = (𝐺‘𝑥))
Theorem	tfrlem3a 7996*	Lemma for transfinite recursion. Let 𝐴 be the class of "acceptable" functions. The final thing we're interested in is the union of all these acceptable functions. This lemma just changes some bound variables in 𝐴 for later use. (Contributed by NM, 9-Apr-1995.)
⊢ 𝐴 = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐹‘(𝑓 ↾ 𝑦)))}    &   ⊢ 𝐺 ∈ V    ⇒   ⊢ (𝐺 ∈ 𝐴 ↔ ∃𝑧 ∈ On (𝐺 Fn 𝑧 ∧ ∀𝑤 ∈ 𝑧 (𝐺‘𝑤) = (𝐹‘(𝐺 ↾ 𝑤))))
Theorem	tfrlem3 7997*	Lemma for transfinite recursion. Let 𝐴 be the class of "acceptable" functions. The final thing we're interested in is the union of all these acceptable functions. This lemma just changes some bound variables in 𝐴 for later use. (Contributed by NM, 9-Apr-1995.)
⊢ 𝐴 = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐹‘(𝑓 ↾ 𝑦)))}    ⇒   ⊢ 𝐴 = {𝑔 ∣ ∃𝑧 ∈ On (𝑔 Fn 𝑧 ∧ ∀𝑤 ∈ 𝑧 (𝑔‘𝑤) = (𝐹‘(𝑔 ↾ 𝑤)))}
Theorem	tfrlem4 7998*	Lemma for transfinite recursion. 𝐴 is the class of all "acceptable" functions, and 𝐹 is their union. First we show that an acceptable function is in fact a function. (Contributed by NM, 9-Apr-1995.)
⊢ 𝐴 = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐹‘(𝑓 ↾ 𝑦)))}    ⇒   ⊢ (𝑔 ∈ 𝐴 → Fun 𝑔)
Theorem	tfrlem5 7999*	Lemma for transfinite recursion. The values of two acceptable functions are the same within their domains. (Contributed by NM, 9-Apr-1995.) (Revised by Mario Carneiro, 24-May-2019.)
⊢ 𝐴 = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐹‘(𝑓 ↾ 𝑦)))}    ⇒   ⊢ ((𝑔 ∈ 𝐴 ∧ ℎ ∈ 𝐴) → ((𝑥𝑔𝑢 ∧ 𝑥ℎ𝑣) → 𝑢 = 𝑣))
Theorem	recsfval 8000*	Lemma for transfinite recursion. The definition recs is the union of all acceptable functions. (Contributed by Mario Carneiro, 9-May-2015.)
⊢ 𝐴 = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐹‘(𝑓 ↾ 𝑦)))}    ⇒   ⊢ recs(𝐹) = ∪ 𝐴