Binary recursion on Nat
#
This file defines binary recursion on Nat
.
Main results #
Nat.binaryRec
: A recursion principle forbit
representations of natural numbers.Nat.binaryRec'
: The same asbinaryRec
, but the induction step can assume that ifn=0
, the bit being appended istrue
.Nat.binaryRecFromOne
: The same asbinaryRec
, but special casing both 0 and 1 as base cases.
@[inline]
def
Nat.bitCasesOn
{motive : Nat → Sort u}
(n : Nat)
(h : (b : Bool) → (n : Nat) → motive (bit b n))
:
motive n
For a predicate motive : Nat → Sort u
, if instances can be
constructed for natural numbers of the form bit b n
,
they can be constructed for any given natural number.
Equations
Instances For
@[irreducible, specialize #[]]
def
Nat.binaryRec
{motive : Nat → Sort u}
(z : motive 0)
(f : (b : Bool) → (n : Nat) → motive n → motive (bit b n))
(n : Nat)
:
motive n
A recursion principle for bit
representations of natural numbers.
For a predicate motive : Nat → Sort u
, if instances can be
constructed for natural numbers of the form bit b n
,
they can be constructed for all natural numbers.