Numbers written in base B on a relation-ordered index set #
DescriptiveComplexity.binNum writes a number in base two, one bit per position. The
reduction that proves Knapsack NP-hard needs the same reading in a larger
base: the ground elements of a set system become blocks of bits, and the
number of sets covering an element becomes the digit of that block. Choosing
the base above the number of sets is what stops carries from crossing a block
boundary, and then a sum of weights equals the target exactly when every
element is covered once – which is uniqueness of base-B expansions,
DescriptiveComplexity.digitNum_inj here.
The development mirrors the binary one: a peeling lemma for the lowest block
(DescriptiveComplexity.digitNum_peel_min) and an induction on the number of blocks.
DescriptiveComplexity.binNum is the special case of base two with digits 0 and 1
(DescriptiveComplexity.binNum_eq_digitNum).
Scaling every digit scales the value. A gadget whose block totals are all even therefore weighs twice the number obtained by halving each digit, which is how a reduction can write half of a total it cannot compute.