TheoremBase

Recursion on the Natural Numbers Starting at One

Given a set a, a starting value c in a and a map g from N × a to a, there is exactly one map f from N to a with f(1) = c and f(n + 1) = g(n, f(n)) for every natural number n.

Statement

In the setting of Class Theory NBG: the Axioms, Standing Conventions and Basic Notation, let N\mathbb{N} and 11 be as in The Set of Natural Numbers and the Number One §naturals and The Set of Natural Numbers and the Number One §one, and let ++ be the addition. Let aa be a set, let c∈ac\in a, and let g:N×a→ag:\mathbb{N}\times a\to a be a map on the Cartesian product N×a\mathbb{N}\times a; for n∈Nn\in\mathbb{N} and u∈au\in a write g(n,u)g(n,u) for the value g((n,u))g((n,u)), which exists because (n,u)∈N×a(n,u)\in\mathbb{N}\times a by Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set §membership and N×a\mathbb{N}\times a is the domain of gg by Functions, Values of a Function, and Functions from One Class to Another §map. For a map f:N→af:\mathbb{N}\to a and n∈Nn\in\mathbb{N}, the values f(1)f(1) and f(n+1)f(n+1) exist because the domain of ff is N\mathbb{N} by Functions, Values of a Function, and Functions from One Class to Another §map, 1∈N1\in\mathbb{N} by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication §one, and n+1∈Nn+1\in\mathbb{N} by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication §closed; and f(n)∈af(n)\in a because it lies in the range of ff, which is included in aa by Functions, Values of a Function, and Functions from One Class to Another §map, so g(n,f(n))g(n,f(n)) exists.

There is exactly one map f:N→af:\mathbb{N}\to a such that f(1)=cf(1)=c and f(n+1)=g(n,f(n))f(n+1)=g(n,f(n)) for every n∈Nn\in\mathbb{N}.

Proofs

Log in to submit a proof.

Loading...

Citations

Loading…

Dependencies

Loading…

Related

0 relations

Curated associations between results. These are editable and subjective — they do not replace the dependency graph, which is derived from the references in the text.

No relations recorded yet.

Comments

Log in to comment.

Loading…