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

Binders, instances and hypotheses. Implicitly given types $E$ and $S$ in arbitrary universes; four typeclass instances ($E$ finite, $S$ finite, equality on $E$ decidable, equality on $S$ decidable); one explicit bundled set-cover instance $I$ over $E$ and $S$, carrying the family $A : S \to$ (finite subsets of $E$), the cost $c : S \to \mathbb{R}$, 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$. Then two explicit real variables $v_f$ and $v_i$, universally quantified, and two explicit hypotheses about them, stated for the same $A$ and $c$ drawn from $I$:

• $h_f$: $v_f$ is the least element of the set of fractional cover costs, i.e. both
  • there exists $x_0 : S \to \mathbb{R}$ with $x_0(s) \ge 0$ for all $s$, with $\sum_{s \in \mathrm{cont}(e)} x_0(s) \ge 1$ for all $e \in E$, and with $\sum_{s \in S} c(s)\,x_0(s) = v_f$; and
  • for every $x : S \to \mathbb{R}$ satisfying $x(s) \ge 0$ for all $s$ and $\sum_{s \in \mathrm{cont}(e)} x(s) \ge 1$ for all $e \in E$, one has $v_f \le \sum_{s \in S} c(s)\,x(s)$.
• $h_i$: $v_i$ is the least element of the set of integral cover costs, i.e. both
  • there exists a finite $C_0 \subseteq S$ such that every $e \in E$ lies in $A_s$ for some $s \in C_0$, and $\sum_{s \in C_0} c(s) = v_i$; and
  • for every finite $C \subseteq S$ such that every $e \in E$ lies in $A_s$ for some $s \in C$, one has $v_i \le \sum_{s \in C} c(s)$.

The conclusion.

$$v_f \;\le\; v_i .$$

That is: for any two reals standing in those two least-element relations with respect to one and the same family $A$ and cost $c$, the fractional value is less than or equal to the integral value. The inequality is non-strict, in that direction: fractional on the left, integral on the right.

1. Attainment vs. infimum vs. boundedness. This statement does not itself assert that any minimum is attained; attainment appears here only inside its hypotheses. Each of $h_f$ and $h_i$ is a least-element assumption, and each accordingly contains an attainment clause (a witness $x_0$, respectively $C_0$, realizing the value) alongside a lower-bound clause. The conclusion is a plain comparison of two given reals. So the logical shape is: if both minima are attained at the values $v_f$ and $v_i$, then $v_f \le v_i$. Nothing asserts that such $v_f$ or $v_i$ exist; if for some instance no such pair existed, the statement would hold vacuously for that instance.

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

• Nonnegativity of cost is present, as field 3 of the bundled argument $I$ — not as a loose hypothesis, and not restated in $h_f$ or $h_i$. As regards the conclusion it does no work: the hypothesis $h_f$ already supplies a lower-bound clause quantified over all feasible $x$, and $h_i$ already supplies a witness cover, so the comparison follows from the hypotheses without reference to the signs of the $c(s)$. What dropping nonnegativity would change is the population of instances to which the statement applies: with some $c(s_0) < 0$ the fractional cost can be driven to $-\infty$ along increasing $x(s_0)$ (raising one coordinate preserves nonnegativity and every covering constraint), so the lower-bound clause of $h_f$ would be unsatisfiable and the hypothesis $h_f$ could hold for no $v_f$ at all. The implication would then be vacuous rather than false.
• Every element lies in some set (coverability) is present, as field 4 of the bundled argument $I$. It likewise does no work in deriving the conclusion, since the membership clauses of $h_f$ and $h_i$ already assert that a feasible $x_0$ and a cover $C_0$ exist. If it were dropped and some $e_0$ were in no $A_s$, then $\mathrm{cont}(e_0) = \emptyset$ and its constraint $0 \ge 1$ is unsatisfiable, and no finite $C$ covers $e_0$; both membership clauses would fail, so neither $h_f$ nor $h_i$ could be satisfied, and the statement would again be vacuously true rather than false. In short: in this statement both bundled conditions bear on whether the hypotheses are satisfiable, not on the conclusion.

3. Can either extremal set be empty? Two readings, both addressed.

• The two value sets. Under the hypotheses, neither can be empty. The membership clause of $h_f$ places $v_f$ in the set of fractional cover costs, and the membership clause of $h_i$ places $v_i$ in the set of integral cover costs; a set with a least element is nonempty by definition. If one of them could be empty for a given instance, the corresponding hypothesis would be unsatisfiable and the statement would carry no content for that instance — it would be vacuously true, asserting nothing about $v_f$ and $v_i$. (Coverability, as noted above, is the bundled condition that rules this out independently of the hypotheses, except in the vacuous case $E$ empty where both sets contain $0$.)
• The extremal witnesses. The minimizing cover $C_0$ furnished by $h_i$ can be the empty subset of $S$, but only when $E$ is empty: the covering condition on $C_0 = \emptyset$ requires, for each $e \in E$, some $s \in \emptyset$ with $e \in A_s$, which is impossible unless there is no $e$. Likewise the minimizing $x_0$ furnished by $h_f$ can be the zero function only when $E$ is empty, since otherwise each $e$ forces $\sum_{s \in \mathrm{cont}(e)} x_0(s) \ge 1 > 0$. In that $E$-empty case $v_i = \sum_{s \in \emptyset} c(s) = 0$ and $v_f = 0$, and the asserted inequality reads $0 \le 0$, which holds as an equality. So the empty-witness case does not contradict the conclusion; it is one of the cases in which the conclusion is an equality rather than a strict inequality. Separately, $C_0$ may be nonempty yet contain sets that contribute nothing (see item 5), since the covering condition never demands minimality.

4. Hypotheses relative to the two existence statements. All three statements share the identical prefix: the same two implicit types, the same four typeclass instances ($E$ finite, $S$ finite, equality decidable on $E$, equality decidable on $S$), and the same single explicit bundled set-cover instance $I$ with its four fields. Neither existence statement carries any hypothesis that this comparison statement lacks. This statement carries strictly more: two additional explicit real arguments $v_f, v_i$, and two additional explicit hypotheses $h_f, h_i$ asserting that each is the least element of its respective value set. It does not assume the two existence theorems as such; it takes the two least elements as given data and hypotheses. Conversely, the existence statements assume nothing about any value, about the other notion of cover, or about a relationship between them.

5. Degenerate cases silently included.

• $E$ empty. Both feasibility notions become vacuous: every finite $C \subseteq S$ is a cover and every nonnegative $x$ is a fractional cover. With nonnegative costs the least values are $v_i = 0$ (attained at $C_0 = \emptyset$) and $v_f = 0$ (attained at $x_0 \equiv 0$), and the conclusion holds with equality. Coverability is vacuously satisfiable, so such bundled instances exist for any $A$ and any nonnegative $c$.
• $S$ empty. Coverability requires some $s \in S$ for each $e \in E$, so an instance with $S$ empty forces $E$ empty. Then the only finite subset of $S$ is $\emptyset$ and the only function $S \to \mathbb{R}$ is the empty function; both value sets are $\{0\}$, so $v_f = v_i = 0$ and the conclusion is $0 \le 0$.
• $c \equiv 0$. Nonnegativity holds; every cover and every fractional cover has cost $0$, so the hypotheses force $v_f = v_i = 0$ and the asserted inequality is an equality. The statement's non-strict $\le$ admits this.
• Individual zero-cost sets. Sets $s$ with $c(s) = 0$ may be added to a minimizing cover $C_0$, or given arbitrary nonnegative mass $x_0(s)$, without changing either cost. Hence neither extremal witness is pinned down by the hypotheses, and $C_0$ need not be inclusion-minimal or of minimum cardinality. The values $v_f$ and $v_i$ are nonetheless each fixed by their hypothesis, since a subset of $\mathbb{R}$ has at most one least element — though the statement asserts only the inequality between them, not this or any uniqueness.
• Unbounded entries of a fractional cover. The lower-bound clause of $h_f$ is quantified over all nonnegative $x$ meeting the covering constraints, with no upper bound on any $x(s)$, no $x(s) \le 1$, no integrality and no rationality; entries may be arbitrarily large reals. Such $x$ are therefore included in the comparison range of $h_f$, and the set of fractional costs is in general unbounded above; this does not affect the conclusion, which concerns only the least elements. The attaining $x_0$ is likewise unconstrained in magnitude.

What is NOT asserted. The statement does not assert that $v_f$ or $v_i$ exists — only what follows if both are given. It does not assert equality, nor strictness, nor any gap or ratio bound in the other direction: there is no claim of the form $v_i \le \alpha\, v_f$ for any $\alpha$, no integrality-gap bound, no claim about $\max_e |\mathrm{cont}(e)|$ or any frequency- or logarithm-based factor. It does not claim that $v_f$ and $v_i$ are unique (that a set has at most one least element is not part of what is asserted), nor that either is nonnegative, nonzero, rational or finite in any sense beyond being real. It says nothing about the relationship between the attaining witnesses $x_0$ and $C_0$ — in particular nothing about rounding a fractional cover to a cover, nothing about indicator functions of covers, and nothing about supports. It makes no duality claim: nothing about dual packings, $\sum_e y(e)$, weak duality or complementary slackness. And it makes no algorithmic, greedy, primal-dual, online or complexity claim.