# Equation with infinite set difference and intersection

Given $$\dots A_2\subseteq A_1\subseteq A_0 = U$$ and $$\bigcup_{n=0}^\infty (A_n \backslash A_{n+1})\cup\left(\bigcap_{n=0}^\infty A_n\right) = U$$ when $U$ is the universal set, prove that $$(A_1 \backslash A_2)\cup(A_3 \backslash A_4)\cup \dots \cup\left(\bigcap_{n=0}^\infty A_n \right) = U\backslash \left( (A_0 \backslash A_1)\cup(A_2 \backslash A_3)\cup \dots \right)$$

My try:

I am almost sure that this problem can be solved with simple induction. The problem is i can't write the induction assumption like so:

$$(A_1 \backslash A_2)\cup(A_3 \backslash A_4)\cup \dots \cup (A_{k-2} \backslash A_{k-1})\cup \left(\bigcap_{n=0}^k A_n \right) = U\backslash \left( (A_0 \backslash A_1)\cup(A_2 \backslash A_3)\cup \dots \cup (A_{k-1} \backslash A_k)\right)$$

because:

1. I don't know if k is even or odd.
2. There are two cases. for example: $$k=2 \to (A_1 \backslash A_2)\cup (A_0 \cap A_1 \cap A_2) = U \backslash (A_0 \backslash A_1)$$

$$k=3 \to (A_1 \backslash A_2)\cup (A_0 \cap A_1 \cap A_2 \cap A_3) = U \backslash ((A_0 \backslash A_1) \cup (A_2 \backslash A_3))$$

hence $$k=2 \to (A_1 \backslash A_2)\cup A_2 = U \backslash (A_0 \backslash A_1)$$

$$k=3 \to (A_1 \backslash A_2)\cup A_3 = U \backslash ((A_0 \backslash A_1) \cup (A_2 \backslash A_3))$$

so by looking at the left term, the index of the intersection has changed but the set difference is still the same.

Can you please help me find the right way to induce this proof, or is there a better and simpler way i just can't see?

## 2 Answers

HINT: For convenience let $D_n=A_n\setminus A_{n+1}$ for $n\in\Bbb N$, and let $C=\bigcap_{n\in\Bbb N}A_n$. Use the hypotheses to show that $\mathscr{P}=\{C\}\cup\{D_n:n\in\Bbb N\}$ is a family of pairwise disjoint sets whose union is $U$. (In other words, they form a partition of $U$ except that some may be empty.) A generalization of the desired result can then be proved by element-chasing: if $\mathscr{A}\subseteq\mathscr{P}$, then for each $x\in U$ we have $x\in\bigcup\mathscr{A}$ if and only if $x\notin\bigcup(\mathscr{P}\setminus\mathscr{A})$.

Induction isn’t appropriate here: you’re not trying to prove a family of statements, one for each $k\in\Bbb N$. Rather, you’re trying to prove a single statement that just happens to mention all $k\in\Bbb N$.

I think you only need to prove $A_i \backslash A_{i+1}$ and $A_j \backslash A_{j+1}$ are disjoint for $i<j$. This follows from for $i+1\leq j$, we have $A_{j}\subset A_{i+1}$.

Then the statement holds by intersects $\Big(\bigcup_{n=0}^\infty (A_{2n} \backslash A_{2n+1})\Big)^c$ on both sides of your assumption 2.