The fractional cost of an indicator is the cover cost (assisting theorem)

Notation shared by all four statements

Throughout, $E$ and $S$ are arbitrary types carrying the instance assumptions that each is a finite type ($E$, $S$ finite) and that equality is decidable on each of them ($E$ and $S$ both have decidable equality; the decidability on $S$ is what permits the constructions $\mathrm{cont}$ and $\mathbf{1}_C$ below to be written at all). Elements of $E$ are thought of as points and elements of $S$ as indices.

A family of sets is a function $A : S \to \mathcal{P}_{\mathrm{fin}}(E)$, written $s \mapsto A_s$, assigning to each index $s$ a finite subset $A_s \subseteq E$. A cost function is $c : S \to \mathbb{R}$, written $s \mapsto c_s$; its values are arbitrary real numbers unless a hypothesis restricts them.

The auxiliary notions used below are, spelled out:

• $\mathrm{cont}(e) := \{\, s \in S : e \in A_s \,\}$, the (finite) set of indices whose set contains the point $e$.
• Coverable for $A$: for every point $e \in E$ there exists an index $s \in S$ with $e \in A_s$. Equivalently, $\mathrm{cont}(e) \neq \varnothing$ for every $e$.
• NonnegCost for $c$: $c_s \ge 0$ for every $s \in S$.
• $C$ is a cover (for a finite $C \subseteq S$): for every $e \in E$ there exists $s \in C$ with $e \in A_s$.
• Cover cost: $\mathrm{coverCost}(c, C) := \sum_{s \in C} c_s$, a finite sum over the members of $C$.
• $x$ is a fractional cover (for $x : S \to \mathbb{R}$): both

• Fractional cost: $\mathrm{fracCost}(c, x) := \sum_{s \in S} c_s \, x_s$, a finite sum over all of $S$.
• Indicator: $\mathbf{1}_C : S \to \mathbb{R}$, $\mathbf{1}_C(s) = 1$ if $s \in C$ and $\mathbf{1}_C(s) = 0$ otherwise.

4. indicator_cost

Binders and hypotheses. Fix finite types $E, S$ with decidable equality on each. Explicit arguments: a cost function $c : S \to \mathbb{R}$ and a finite subset $C \subseteq S$. There are no hypotheses at all: no coverability, no nonnegativity of $c$, no assumption that $C$ is a cover, and indeed no family of sets $A$ appears in the statement — the type $E$, its finiteness and its decidable equality enter only as unused binders/instances, while the finiteness of $S$ is what makes the left-hand sum over all of $S$ meaningful.

Conclusion. The two real numbers

are equal. On the left, the sum ranges over every index of $S$, each term weighted by the indicator of $C$: indices $s \notin C$ contribute $c_s \cdot 0 = 0$ and indices $s \in C$ contribute $c_s \cdot 1 = c_s$. On the right, the sum ranges only over the members of $C$. The claim is thus that restricting the index range to $C$ and multiplying by the indicator over the full index range give the same real value.

Nonnegativity. No sign condition on $c$ is assumed or needed for the statement to be well formed: both sides are finite sums of real numbers, always defined, so this is an exact equality of reals with $c$ entirely arbitrary — individual costs may be negative, zero, or positive, and either side may be negative. No cancellation, absolute value, or ordering is involved.

Degenerate cases silently included.

• $C = \varnothing$: the right-hand side is the empty sum $0$, and every term on the left is $c_s \cdot 0 = 0$, so the asserted equality reads $0 = 0$.
• $C = S$: the left-hand side has all weights $1$ and the equality reads $\sum_{s \in S} c_s = \sum_{s \in S} c_s$.
• $S$ empty: both sides are empty sums, $0 = 0$.
• $E$ empty, or $E$ arbitrary: irrelevant to the claim, since $E$ occurs only in the binders.
• $c \equiv 0$: both sides are $0$.
• $c$ with negative values: permitted here, unlike in statements 1 and 2, since no nonnegativity hypothesis is carried.
• $C$ need not be a cover of anything, and no set family is even in scope.

What is NOT asserted. Nothing about covers, fractional covers, feasibility, or optimality; in particular this is not a claim that $\mathbf{1}_C$ is a fractional cover (that is statement 3), and not a claim about optimal values. No inequality is asserted in either direction beyond the stated equality, no claim is made about sums over index sets other than $S$ and $C$, and nothing is said about functions $x : S \to \mathbb{R}$ other than $\mathbf{1}_C$ — in particular no analogous identity for general $x$ supported on $C$.