# Proving a set-theoretic identity

Context: Measure theory.

Reason: Just curious.

Question: Given $\{A_k\}$ with $A_k$ not disjoint, $B_1=A_1$ and $B_n = A_n - \bigcup\limits_{k=1}^{n-1} A_k$ for $n \in \mathbb{N}-\{1\}$ and $k \in \mathbb{N}$, how can I show that $$\bigcup\limits_{n=2}^{\infty}A_n = \bigcup\limits_{n=2}^{\infty}B_n?$$

Attempt: $$\bigcup\limits_{n=2}^{\infty}B_n=\bigcup\limits_{n=2}^{\infty}\left(A_n \cap (\bigcup\limits_{k=1}^{n-1} A_k)^c\right)=\bigcup\limits_{n=2}^{\infty}A_n \bigcap \bigcup\limits_{n=2}^{\infty}\left(\bigcup\limits_{k=1}^{n-1} A_k\right)^c = \cdots$$

Where do I go from here?

(I'm adding this answer since it shows that the statement as written is not completely correct, because it shows a different style of proof, and because I discovered a direct connection with induction.)


The most straightforward approach for proofs like this is to start with the most complex side, and calculate the elements $\;x\;$ of that set: $$\calc x \in \langle \cup n :: A_n - \langle \cup k : k < n : A_k \rangle \rangle \calcop\equiv{expand definition of \;\cup\; twice, and of \;-\;} \langle \exists n :: x \in A_n \land \lnot \langle \exists k : k < n : x \in A_k \rangle \rangle \calcop\equiv{logic: rewrite using DeMorgan twice, and 'shunting'} \lnot \langle \forall n : \langle \forall k : k < n : x \not\in A_k \rangle : x \not\in A_n \rangle \tag{*} \endcalc$$

The last step was inspired by the shape of the formula, since the last statement reminds us of the principle of complete induction (see Wikipedia and another question): $$\tag 1 \langle \forall i : i \in V \land \langle \forall j : j \in V \land j < i : P_j \rangle : P_i \rangle \;\equiv\; \langle \forall i : i \in V : P_i \rangle$$ where $\;i,j\;$ range over the same set $\;V\;$ with an ordering $\;<\;$. (Often $\ref 1$ is presented only with the $\;\Rightarrow\;$ direction, but since the other direction is trivial, it is usually simpler to use the stronger more symmetrical version.)

However, there is a difference between $\ref *$ and $\ref 1$: in $\ref *$ the dummies do not range over the same set, since $\;n \in \mathbb N_{\ge 2}\;$ but $\;k \in \mathbb N_{\ge 1}\;$. So we cannot use $\ref 1$ directly.

Therefore, let's try to rewrite $\ref *$ so that we can use $\ref 1$: $$\calc \tag{*} \lnot \langle \forall n : \langle \forall k : k < n : x \not\in A_k \rangle : x \not\in A_n \rangle \calcop\equiv{logic: split off \;k = 1\;} \lnot \langle \forall n : x \not\in A_1 \land \langle \forall k : 2 \le k \land k < n : x \not\in A_k \rangle : x \not\in A_n \rangle \calcop\equiv{logic: DeMorgan; move \;x \not\in A_1\; out of \;\exists n\;; DeMorgan} x \not\in A_1 \land \lnot \langle \forall n : \langle \forall k : 2 \le k \land k < n : x \not\in A_k \rangle : x \not\in A_n \rangle \calcop{\tag{**} \equiv}{using induction principle \ref 1 on \;\mathbb N_{\ge 2}\; with \;P_n := x \not\in A_n\;} x \not\in A_1 \land \lnot \langle \forall n :: x \not\in A_n \rangle \calcop\equiv{logic: DeMorgan; definitions of \;\cup\; and \;-\;} x \in \langle \cup n :: A_n \rangle - A_1 \endcalc$$

By set extensionality, the above calculation proves $$\tag 2 \langle \cup n :: A_n \rangle - A_1 \;=\; \langle \cup n :: A_n - \langle \cup k : k < n : A_k \rangle \rangle$$ and the key step was $\ref{**}$ where we applied the principle of complete induction.

Finally, this implies that $\ref 0$ is not true: now that we know $\ref 2$ it is easy to find a counterexample, e.g., if $\;A_1\;$ and $\;A_2\;$ share an element, then that element is in the left hand side of $\ref 0$ but not in its right hand side.

It might be easier to show each side is a subset of the other.

$\bigcup A_n \subset \bigcup B_n$

For $x \in \bigcup A_n$, let $n$ be the smallest integer such that $x \in A_n$. Then $x \in B_n$.

$\bigcup A_n \supset \bigcup B_n$

For $x \in \bigcup B_n$, there exists a [unique] $n$ such that $x \in B_n$. Then $x \in A_n$.

Try showing the double inclusion. One side is easy as $B_i \subseteq A_i$ for all $i$. For the other side, think of $x \in \bigcup A_i$, and let $A_k$ the first $k$ such that $x \in A_k$, what can you say about $x$ and $B_k$?