Read-backs: certificate bounds

Throughout, the shared vocabulary is expanded as follows. A set-cover instance $I$ on two types $E$ (elements) and $S$ (set indices) is a bundle of exactly four components:

• a family $A : S \to \mathcal{P}_{\mathrm{fin}}(E)$, i.e. a finite subset $A_s \subseteq E$ for each index $s$;
• a cost function $c : S \to \mathbb{R}$;
• a proof of nonnegative cost: $\forall s \in S,\ 0 \le c_s$;
• a proof of coverability: $\forall e \in E,\ \exists s \in S,\ e \in A_s$.

Derived notions, all expanded inline in each section below:

$$N(e) \;=\; \{\, s \in S \;:\; e \in A_s \,\}, \qquad f(e) \;=\; |N(e)| \in \mathbb{N}, \qquad \Delta \;=\; \sup_{e \in E} f(e) \in \mathbb{N},$$

where $N(e)$ is formed by filtering the whole index type $S$, $f(e)$ is a cardinality in $\mathbb{N}$, and $\Delta$ is a supremum in $\mathbb{N}$ taken over all of $E$ — a supremum of an empty family, which is $0$ when $E$ is empty. Further:

$$\mathrm{coverCost}(c, \mathcal{C}) = \sum_{s \in \mathcal{C}} c_s, \qquad \mathrm{fracCost}(c, x) = \sum_{s \in S} c_s x_s, \qquad \mathrm{pack}(y) = \sum_{e \in E} y_e .$$

$\mathrm{coverCost}$ sums only over the given finite index set $\mathcal{C}$; $\mathrm{fracCost}$ sums over all of $S$; $\mathrm{pack}$ sums over all of $E$.

---

PrimalDualOnline.SetCover.packing_le_fractional

Binders and instance arguments. The statement is universally quantified over two arbitrary types $E$ and $S$ (implicit arguments), with four typeclass arguments: $E$ is a finite type, $S$ is a finite type, equality on $E$ is decidable, and equality on $S$ is decidable. Finiteness does not exclude emptiness: either type may be empty. Decidable equality on $S$ is what allows $N(e)$ to be formed by filtering $S$; decidable equality on $E$ is demanded as an instance argument, while none of the notions occurring in this statement mentions it. Three explicit arguments follow: a set-cover instance $I$ on $E, S$ (carrying $A$, $c$, the nonnegativity proof and the coverability proof), an arbitrary function $x : S \to \mathbb{R}$, and an arbitrary function $y : E \to \mathbb{R}$.

Hypotheses. Two, both about $x$ and $y$ with respect to the family and cost inside $I$:

1. $x$ is a fractional cover of $A$, which unfolds to the conjunction of

$$\forall s \in S,\ 0 \le x_s \qquad\text{and}\qquad \forall e \in E,\ \ 1 \le \sum_{s \in N(e)} x_s .$$

There is no upper bound on any $x_s$: entries are not capped at $1$ or anywhere else. 2. $y$ is a dual packing for $(A, c)$, which unfolds to the conjunction of

$$\forall e \in E,\ 0 \le y_e \qquad\text{and}\qquad \forall s \in S,\ \ \sum_{e \in A_s} y_e \le c_s .$$

The second constraint ranges over every index $s \in S$.

Conclusion.

$$\sum_{e \in E} y_e \;\;\le\;\; \sum_{s \in S} c_s\, x_s .$$

A non-strict inequality between the total dual value over all of $E$ and the cost-weighted total of $x$ over all of $S$.

1. Nonnegativity of cost; every element in some set. Nonnegativity of $c$ is not a loose hypothesis: it is a field of the bundled argument $I$ (as is coverability, $\forall e \exists s,\ e \in A_s$). Consequently the statement cannot be instantiated at a family/cost pair violating either: the argument $I$ cannot be formed without supplying both proofs, so the statement simply does not apply to such data. Neither field is mentioned in the conclusion; they travel along inside $I$.

2. Logical redundancy. Both bundled proof fields are derivable from the remaining hypotheses.

• Nonnegativity of cost follows from hypothesis 2: for each $s$, all terms of $\sum_{e \in A_s} y_e$ are nonnegative because $y \ge 0$, so $0 \le \sum_{e \in A_s} y_e \le c_s$.
• Coverability follows from hypothesis 1: if some $e$ had $N(e) = \emptyset$, then $\sum_{s \in N(e)} x_s = 0$, contradicting $1 \le 0$; hence $N(e) \ne \emptyset$, i.e. $\exists s,\ e \in A_s$.

If these two fields were dropped (the statement restated over a bare family $A$ and bare cost $c$ with no such hypotheses), the collection of situations the statement covers would not change: every $A, c, x, y$ satisfying the two remaining hypotheses already satisfies both properties. No other hypothesis is derivable: nonnegativity of $x$, the covering inequalities for $x$, nonnegativity of $y$, and the packing inequalities for $y$ are mutually independent.

3. Arbitrary or specific. The fractional cover is arbitrary: $x$ is universally quantified and constrained only by feasibility. No optimality is invoked — the notions of least fractional cost and least integral cover cost defined in the vocabulary are not used here. The dual vector $y$ is likewise arbitrary, constrained only by being a dual packing. There is no cover (no finite index set $\mathcal{C}$) in this statement at all.

4. Cast from $\mathbb{N}$ to $\mathbb{R}$. There is none: every quantity in this statement is real-valued, and no cardinality or frequency appears.

5. Degenerate cases.

• $E$ empty. Coverability is vacuous; the covering inequalities in hypothesis 1 and the nonnegativity of $y$ are vacuous; each $A_s$ is empty, so every packing constraint reads $0 \le c_s$, which holds by the bundled nonnegativity. $\mathrm{pack}(y) = 0$, and the conclusion becomes $0 \le \sum_s c_s x_s$, a sum of products of nonnegative reals.
• $S$ empty. Then $N(e) = \emptyset$ for every $e$, so hypothesis 1 would demand $1 \le 0$; thus the hypotheses are unsatisfiable unless $E$ is also empty. (Independently, the bundled coverability field already cannot be constructed with $S$ empty and $E$ nonempty.) With both empty, both sides are empty sums and the conclusion is $0 \le 0$.
• $\mathcal{C}$ empty. Not applicable: no cover appears.
• $c \equiv 0$. Nonnegativity holds. The packing constraints give $\sum_{e \in A_s} y_e \le 0$, and with $y \ge 0$ this forces $y_e = 0$ for every $e$ lying in some $A_s$ — which, by coverability, is every $e$. So $\mathrm{pack}(y) = 0$ and $\mathrm{fracCost}(c,x) = 0$: the conclusion is $0 \le 0$.
• Individual zero-cost sets. If $c_s = 0$ for a particular $s$, the packing constraint at $s$ together with $y \ge 0$ forces $y_e = 0$ for every $e \in A_s$.
• $\rho$. Not applicable: no multiplier appears.
• Unbounded entries of the fractional cover. Only $x \ge 0$ and the covering inequalities are imposed; individual $x_s$ may be arbitrarily large, and the right-hand side is correspondingly unbounded above. Coordinates $s$ with $x_s = 0$ are still summed over in $\mathrm{fracCost}$, contributing $0$.
• Empty sets $A_s = \emptyset$ are permitted; their packing constraint reads $0 \le c_s$. Distinct indices may carry equal subsets.

Not asserted. Nothing about optimality: neither $x$ nor $y$ is claimed minimal, maximal, or extremal, and no least fractional cost or least cover cost is mentioned. No claim that the inequality is tight, attained, or reversible; no strict inequality. No claim that a fractional cover or a dual packing exists — both are supplied as arguments, so the statement is silent if none exists. Nothing about integral covers, cover cost, frequency, maximum frequency, or any approximation factor. No algorithm, no ordering or online structure, and no assertion that the hypotheses are simultaneously satisfiable.

---