= Solution
Write $U'=U\setminus\{y\}$ and $\mathcal F'=\{B\setminus\{y\}:B\in\mathcal F\}$. If $\mathcal A$ is a basis for the original instance, replace each member $A$ by $A\setminus\{y\}$. Deletion commutes with <unions>, so the resulting family generates every member of $\mathcal F'$ and has at most $|\mathcal A|$ members.
Conversely, take a basis $\mathcal A'$ for the reduced instance. Lift each of its members by
$$
L(A')=\begin{cases}A'\cup\{y\},&x\in A',\\A',&x\notin A'.\end{cases}
$$
If $B\setminus\{y\}$ is represented as a <union> of reduced basis <sets>, the same <union> of their lifts agrees with $B$ on $U'$. It contains $y$ exactly when one of the selected reduced basis <sets> contains $x$, namely exactly when $x\in B$. By the assumed <incidence equivalence in a set family>, this occurs exactly when $y\in B$. Thus the lifted <union> is precisely $B$, and the lifted basis has no more members.
Therefore \b[deleting $y$ preserves the yes/no answer with the same parameter $k$]. The reverse construction does not require a reduced basis <set> to be an input <set>.
Back to article page
