Documentation

Complexity.Computability.GenericRAM.Signed.Fits

Signed fits from magnitude envelopes #

A representable nonnegative envelope covers every integer whose absolute value is at most it. The envelope itself must fit: the asymmetric signed range still excludes its positive endpoint.

Main results #

This elementary bound is original.

theorem Cslib.GenericRAM.Signed.Fits.of_natAbs_le {w B : ℕ} (hfit : Fits w ↑B) {z : ℤ} (hz : z.natAbs ≤ B) :
Fits w z

A signed fit for a nonnegative envelope also covers every integer bounded by it.