TheoremBase

Induction for Predicative Formulas, and the Order of ℕ below 1 and below n+1

Induction on the natural numbers for any condition expressed by a predicative formula, and two facts on the order of the natural numbers: no natural number lies below 1, and the natural numbers below n+1 are those below n together with n.

Statement

In the setting of Routine Facts Used Without Citation: Arithmetic, Maps, Predicativity and Indices, let N\mathbb{N}, 11, the sum n+1n+1 and the order ≤\le with strict order << be as in The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (ii), The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (iv) and The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (v).

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 φ(1)\varphi(1) holds, and φ(n)\varphi(n) implies φ(n+1)\varphi(n+1) for every n∈Nn\in\mathbb{N}, then φ(n)\varphi(n) holds for every n∈Nn\in\mathbb{N}.

There is no k∈Nk\in\mathbb{N} with k<1k<1.

For all k,n∈Nk,n\in\mathbb{N}: k<n+1k<n+1 if and only if k<nk<n or k=nk=n; and k≤n+1k\le n+1 if and only if k≤nk\le n or k=n+1k=n+1.

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…