def sum_fits

bend-collections-laws-crypto@1.0.0.0 · proofs/math/typed/w64m128.bend:35

import Base
import bend-collections-laws-crypto@1.0.0.0/spec/lib/common.bend as C
import bend-collections-laws-crypto@1.0.0.0/proofs/lib/nat.bend as N
import bend-collections-laws-crypto@1.0.0.0/proofs/lib/logic.bend as L
import bend-collections-laws-crypto@1.0.0.0/proofs/lib/lemmas/proofs/nat_algebra.bend as NA
import bend-collections-laws-crypto@1.0.0.0/proofs/math/typed/width.bend as WW

35# x, y fit k bits: x + y fits 1 + k bits
36def sum_fits(+k: Nat, +x: Nat, +y: Nat, +hx: {C.fits(k, x) == True{} : Bool}, +hy: {C.fits(k, y) == True{} : Bool}) -> {C.fits(1n+k, Nat.add(x, y)) == True{} : Bool}:
37  +P = C.pow2(k)
38  +h1 = N.lt_le_trans(Nat.add(x, y), Nat.add(P, y), Nat.add(P, P), N.lt_add_r2(x, P, y, WW.lt_of_fits(k, x, hx)), N.le_add_left(y, P, P, N.lt_le(y, P, WW.lt_of_fits(k, y, hy))))
39  WW.fits_of_lt(1n+k, Nat.add(x, y), L.subst(Nat, z => {Nat.is_lt(Nat.add(x, y), z) == True{} : Bool}, Nat.add(P, P), Nat.double(P), Equal.sym(Nat, Nat.double(P), Nat.add(P, P), NA.double_self(P)), h1))