TheoremBase

Induction on ℕ₀ from 0 for a Condition Expressed by a Predicative Formula

Induction from 0 on the natural numbers with zero for any condition expressed by a predicative formula, with the induction step stated either for the successor S(k) or for the sum n+1.

Statement

In the setting of Routine Facts Used Without Citation: Arithmetic, Maps, Predicativity and Indices, let N0\mathbb{N}_{0}, 00, 11 and the sum n+1n+1 be as in The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (ii) and The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (iv). Let xx be a set variable, and let φ\varphi be a condition on xx that is expressed by a predicative formula, its parameters having their fixed values as in Conditions Expressed by a Predicative Formula, and Guards (i). For a set aa, φ(a)\varphi(a) means that φ\varphi holds when aa is assigned to xx.

If φ(0)\varphi(0) holds, and φ(k)\varphi(k) implies φ(S(k))\varphi(S(k)) for every k∈N0k\in\mathbb{N}_{0}, where S(k)S(k) is the successor of the set kk, then φ(k)\varphi(k) holds for every k∈N0k\in\mathbb{N}_{0}.

If φ(0)\varphi(0) holds, and φ(n)\varphi(n) implies φ(n+1)\varphi(n+1) for every n∈N0n\in\mathbb{N}_{0}, then φ(n)\varphi(n) holds for every n∈N0n\in\mathbb{N}_{0}.

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…