Exercise I.2.7 in Elstrodt I am trying to solve exercise I.2.7 in the book by Elstrodt..

Let $A_1,...,A_n \subset X$ and
$U_k := \bigcup \limits_{1 \leq i_1 < ... < i_k \leq n} A_{i_1} \cap ... \cap A_{i_k}$, $V_k := \bigcap \limits_{1 \leq i_1 < ... < i_k \leq n} A_{i_1} \cup ... \cup A_{i_k}$.
Show that: For every $k = 1,...,n$, $U_k = V_{n-k+1}$.

One inclusion seems straightforward:
Let $x \in U_k$, then $x \in A_{i_1} \cap ... \cap A_{i_k}$ for some choice of indices $1 \leq i_1 < ... < i_k \leq n$. If we pick $n-k+1$ sets $A_j$, then at least one of the sets $A_j$ must correspond to one of the $A_{i_1}, ... A_{i_k}$. Hence, $x \in V_{n-k+1}$.
However, I am struggling to prove the other inclusion.
Can anyone help me out? Maybe there is also a better way to prove the claim that does not involve showing both inclusions.
Thank you!
 A: Given
\begin{align*}
U_k:=\bigcup_{1\leq i_1<\cdots <i_k\leq n}\bigcap_{j=1}^k A_{i_j}\qquad\text{and}\qquad
V_k:=\bigcap_{1\leq i_1<\cdots <i_k\leq n}\bigcup_{j=1}^k A_{i_j}\qquad (1\leq k\leq n)
\end{align*}
we want to show the other inclusion
\begin{align*}
\color{blue}{V_{n-k+1}\subseteq U_k\qquad\qquad(1\leq k\leq n)}\tag{1}
\end{align*}
equivalently
\begin{align*}
x\in V_{n-k+1}\qquad\Longrightarrow\qquad x\in U_k
\end{align*}
equivalently
\begin{align*}
x\not \in U_{k}\qquad\Longrightarrow\qquad x\not\in V_{n-k+1}
\end{align*}

*

*The left-hand side $x\not\in U_k$ means for each choice of indices $1\leq i_1<\cdots<i_k\leq n$ we have
\begin{align*}
x\not\in \bigcap_{j=1}^k A_{i_j}
\end{align*}

*This implies $x$ is element of at most $k-1$ pairwise different sets $A_{j_1},\ldots,A_{j_{k-1}}$, $1\leq j_1<\cdots<j_{k-1}\leq n$. We can therefore select $n-k+1$ indices
\begin{align*}
1\leq q_1<\cdots<q_{n-k+1}\leq n\qquad\text{with}\qquad
\{q_1,\ldots,q_{n-k+1}\}\subseteq [n]\setminus\{j_1,\ldots j_{k-1}\}
\end{align*}
so, that
\begin{align*}
x\not\in A_{q_1}\cup\cdots\cup A_{q_{n-k-1}}
\end{align*}

*which implies
\begin{align*}
\color{blue}{x\not\in \bigcap_{1\leq i_1<\cdots <i_{n-k+1}\leq n}\bigcup_{j=1}^{n-k+1}A_{i_j}=V_{n-k+1}}
\end{align*}
and the claim (1) follows.

