def digit_lt

bend-collections-laws-math@1.0.0.0 · proofs/lib/arith.bend:64

import Base
import bend-collections-laws-math@1.0.0.0/proofs/lib/lemmas/spec/numeric.bend as S
import bend-collections-laws-math@1.0.0.0/proofs/lib/nat.bend as N
import bend-collections-laws-math@1.0.0.0/proofs/lib/logic.bend as L
import bend-collections-laws-math@1.0.0.0/proofs/lib/u32alg.bend as A

64# a digit x below 2^k after y < b scaled by 2^k stays below b scaled
65def digit_lt(+k: Nat, +one: Nat, +h1: {one == 1n : Nat}, +x: Nat, +y: Nat, +b: Nat, +hx: {Nat.is_lt(x, sc(k, one)) == True{} : Bool}, +hy: {Nat.is_lt(y, b) == True{} : Bool}) -> {Nat.is_lt(Nat.add(sc(k, y), x), sc(k, b)) == True{} : Bool}:
66  +hx1 = L.subst(Nat, o => {Nat.is_lt(x, S.scale_binary(k, o)) == True{} : Bool}, one, 1n, h1, hx)
67  +l1 = N.lt_add_left(x, sc(k, 1n), sc(k, y), hx1)
68  +e1 = Equal.trans(Nat, Nat.add(sc(k, y), sc(k, 1n)), sc(k, Nat.add(y, 1n)), sc(k, 1n+y), A.sc_add(k, y, 1n), Equal.cong(Nat, Nat, z => sc(k, z), Nat.add(y, 1n), 1n+y, N.add_comm(y, 1n)))
69  +l2 = L.subst(Nat, z => {Nat.is_lt(Nat.add(sc(k, y), x), z) == True{} : Bool}, Nat.add(sc(k, y), sc(k, 1n)), sc(k, 1n+y), e1, l1)
70  N.lt_le_trans(Nat.add(sc(k, y), x), sc(k, 1n+y), sc(k, b), l2, sc_le(k, 1n+y, b, N.lt_succ_le_succ(y, b, hy)))