Read-backs: attainment and comparison of optimal cover values

Throughout, the following notation is used for the objects the three statements refer to. $E$ and $S$ are two types (indices for elements and for sets, respectively), each carrying a finiteness assumption. For $s \in S$ we write $A_s \subseteq E$ for the finite subset of $E$ named by the first field of the bundled argument, and $c(s) \in \mathbb{R}$ for the real number named by its second field. For $e \in E$ we write

$$\mathrm{cont}(e) \;=\; \{\, s \in S \;:\; e \in A_s \,\},$$

the (finite) set of indices whose set contains $e$.

A cover is a finite subset $C \subseteq S$ such that every $e \in E$ satisfies $e \in A_s$ for at least one $s \in C$; its cost is $\sum_{s \in C} c(s)$, each member of $C$ counted once.

A fractional cover is an arbitrary real-valued function $x : S \to \mathbb{R}$ satisfying both

$$x(s) \ge 0 \ \ \text{for every } s \in S, \qquad \sum_{s \in \mathrm{cont}(e)} x(s) \ \ge\ 1 \ \ \text{for every } e \in E;$$

its cost is $\sum_{s \in S} c(s)\, x(s)$, summed over all of $S$, not merely over the support of $x$.

---

PrimalDualOnline.SetCover.exists_optFractional

Binders, instances and the bundled argument. Identical to the previous statement: implicitly given types $E$ and $S$ in arbitrary universes; four instances ($E$ finite, $S$ finite, equality on $E$ decidable, equality on $S$ decidable — the last two being what permit $\mathrm{cont}(e)$ to be formed); and one explicit bundled set-cover instance $I$ carrying the family $A$, the cost $c$, a proof that $0 \le c(s)$ for every $s \in S$, and a proof that every $e \in E$ lies in $A_s$ for at least one $s \in S$.

The conclusion. There exists a real number $v$ which is the least element of the set of achievable fractional cover costs

$$V_{\mathrm{frac}} \;=\; \Bigl\{\, w \in \mathbb{R} \;:\; \text{some fractional cover } x \text{ satisfies } \textstyle\sum_{s \in S} c(s)\,x(s) = w \,\Bigr\}.$$

Expanded into its two component clauses, the assertion is that there is a $v \in \mathbb{R}$ with:

• (Membership / attainment.) There exists a function $x_0 : S \to \mathbb{R}$ such that $x_0(s) \ge 0$ for every $s \in S$, and $\sum_{s \in \mathrm{cont}(e)} x_0(s) \ge 1$ for every $e \in E$, and

$$\sum_{s \in S} c(s)\, x_0(s) \;=\; v .$$

• (Lower bound.) For every function $x : S \to \mathbb{R}$ with $x(s) \ge 0$ for all $s \in S$ and $\sum_{s \in \mathrm{cont}(e)} x(s) \ge 1$ for all $e \in E$,

$$v \;\le\; \sum_{s \in S} c(s)\, x(s).$$

1. Attainment vs. infimum vs. boundedness. Again attainment: a minimum, not an infimum and not mere boundedness below. The membership clause requires an actual feasible $x_0$ whose cost equals $v$ exactly; the lower-bound clause requires that no feasible $x$ costs less. Note that here the quantifier ranges over an infinite domain — all real-valued functions on $S$ satisfying the two feasibility constraints — so the attainment content is substantive in a way the finite-subset case is not. The statement does not say the minimum is the infimum of a sequence, does not say the feasible region is compact, and does not say the minimum is approached without being reached.

2. Provenance and load-bearing status of the two side conditions.

• Nonnegativity of cost is present, as field 3 of the bundled argument $I$. It bears on the lower-bound clause. Concretely, if it were dropped and some $s_0 \in S$ had $c(s_0) < 0$, then from any feasible $x$ one obtains further feasible points by increasing the single coordinate $x(s_0)$ by an arbitrary amount $t > 0$: raising a coordinate preserves $x \ge 0$ and can only increase each constrained sum $\sum_{s \in \mathrm{cont}(e)} x(s)$, so all constraints continue to hold, while the cost changes by $c(s_0)\,t \to -\infty$. Then $V_{\mathrm{frac}}$ would have no lower bound at all, and the lower-bound clause would be unsatisfiable for every real $v$ — so the existential would fail. (The membership clause would be unaffected.) This is the clause where the condition does work that it does not do in the integral statement.
• Every element lies in some set (coverability) is present, as field 4 of the bundled argument $I$. It bears on the membership clause. If it were dropped and some $e_0 \in E$ had $e_0 \notin A_s$ for every $s$, then $\mathrm{cont}(e_0) = \emptyset$ and its constraint reads $0 = \sum_{s \in \emptyset} x(s) \ge 1$, which no $x$ satisfies; there would be no feasible $x$ at all, $V_{\mathrm{frac}}$ would be empty, and the membership clause would be unsatisfiable for every $v$, while the lower-bound clause would hold vacuously for every $v$. As before, the exception is $E$ empty, where coverability is vacuous.

3. (Not applicable; this item concerns the comparison statement.)

4. Hypotheses relative to the comparison statement. Exactly the same prefix as the integral existence statement — four instances, one bundled argument — and therefore no hypothesis beyond what the comparison statement assumes; the comparison statement adds two reals and two hypotheses on top of this same prefix. In particular this statement does not assume the existence of a least integral value, and says nothing about covers, indicators or integrality.

5. Degenerate cases silently included.

• $E$ empty. The second feasibility constraint is vacuous, so every nonnegative $x$ is a fractional cover, including $x \equiv 0$, whose cost is $0$; $V_{\mathrm{frac}}$ then contains $0$ and, since every summand $c(s)x(s)$ is a product of nonnegatives, contains nothing below $0$.
• $S$ empty. As before, coverability then forces $E$ empty. There is exactly one function $S \to \mathbb{R}$, the empty function, it is feasible, and its cost is the empty sum $0$; so $V_{\mathrm{frac}} = \{0\}$.
• $c \equiv 0$. Nonnegativity holds; every feasible $x$ has cost $0$, so $V_{\mathrm{frac}} \subseteq \{0\}$ and the asserted $v$ is $0$, attained by any feasible $x$ at all.
• Individual zero-cost sets. A coordinate $s$ with $c(s) = 0$ contributes $0$ to the cost whatever the value of $x(s)$, so the attaining $x_0$ of the membership clause is not pinned down: it may place arbitrary nonnegative mass on such coordinates. No uniqueness of $x_0$ is claimed.
• Unbounded entries of a fractional cover. The feasibility conditions impose only $x(s) \ge 0$ and $\sum_{s \in \mathrm{cont}(e)} x(s) \ge 1$. There is no upper bound on any entry: no $x(s) \le 1$, no normalization, no integrality, no rationality, no bound on $\sum_s x(s)$. Entries may be arbitrarily large, so $V_{\mathrm{frac}}$ is in general unbounded above; the assertion concerns only its least element. The domain is all of $S \to \mathbb{R}$, so entries are arbitrary reals subject only to those constraints.

What is NOT asserted. No relation to the integral optimum — this statement is silent about covers and about any gap or ratio between fractional and integral values. No uniqueness: a bare existential over $v$, not unique existence, and the attaining $x_0$ is not claimed unique. No structural claim about $x_0$: it is not claimed to be $0$-$1$ valued, rational, supported on few coordinates, or extremal/vertex-like. No duality claim: nothing about dual packings, about $\sum_{e} y(e)$, or about weak or strong duality. No bound on $v$ — not $v \ge 0$, not $v \le \sum_{s} c(s)$, nothing. No claim that the feasible region is nonempty, bounded, or compact beyond what the membership clause states, and no claim that the minimum is computable or that any algorithm finds it.

---