The indicator of a cover is a fractional cover (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

$$x_s \ge 0 \quad \text{for every } s \in S, \qquad \text{and} \qquad \sum_{s \in \mathrm{cont}(e)} x_s \ \ge\ 1 \quad \text{for every } e \in E .$$

• 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.

---

3. indicator_isFractionalCover

Binders and hypotheses. Fix finite types $E, S$ with decidable equality on each (decidability on $S$ is needed both to form $\mathrm{cont}(e)$ and to define the indicator). Explicit arguments: a family $A : S \to \mathcal{P}_{\mathrm{fin}}(E)$ and a finite subset $C \subseteq S$. The only hypothesis is:

• $C$ is a cover: for every $e \in E$ there exists $s \in C$ with $e \in A_s$.

There is no cost function among the arguments, and consequently no nonnegativity-of-cost hypothesis. There is no coverability hypothesis on $A$ either (coverability is not assumed; the cover hypothesis on $C$ is a separate, stronger-looking condition on the given $C$).

Conclusion. The real-valued function $\mathbf{1}_C$ given by

$$\mathbf{1}_C(s) = \begin{cases} 1 & s \in C \\ 0 & s \notin C\end{cases}$$

is a fractional cover, i.e. both of the following hold:

1. $\mathbf{1}_C(s) \ge 0$ for every $s \in S$;
2. for every $e \in E$,

$$\sum_{s \in \mathrm{cont}(e)} \mathbf{1}_C(s) \ \ge\ 1,$$

that is, the number of indices $s$ that simultaneously lie in $C$ and satisfy $e \in A_s$ — the cardinality $|C \cap \mathrm{cont}(e)|$, viewed as a real number — is at least $1$.

Degenerate cases silently included.

• If $E$ is empty, the cover hypothesis is vacuously true for every finite $C \subseteq S$, including $C = \varnothing$; the second conclusion clause is then also vacuous, and only the nonnegativity clause carries content. In particular the statement is asserted for $C = \varnothing$ in that case.
• If $E$ is nonempty, the cover hypothesis forces $C$ to be nonempty and forces $\mathrm{cont}(e) \cap C \neq \varnothing$ for each $e$.
• If $S$ is empty, then $C = \varnothing$, and the hypothesis is satisfiable only when $E$ is empty as well.
• $C$ may contain redundant indices, indices with $A_s = \varnothing$, or all of $S$; the conclusion is asserted for every such $C$ satisfying the hypothesis.

What is NOT asserted. The inequality in clause 2 is only $\ge 1$: it is not claimed that the sum equals $1$, nor that a point is covered by exactly one member of $C$, nor any upper bound on $|C \cap \mathrm{cont}(e)|$. Nothing is said about cost: no comparison of $\mathrm{fracCost}(c,\mathbf{1}_C)$ with anything, no optimality or near-optimality of $\mathbf{1}_C$ among fractional covers, no relation to the optimal values of statements 1 and 2. No converse is asserted — it is not claimed that a $\{0,1\}$-valued fractional cover arises from a cover, nor that $\mathbf{1}_C$ being a fractional cover implies $C$ is a cover. No minimality of $C$ and no existence of any cover is asserted; the given $C$ is supplied by the caller.

---