2
$\begingroup$

Given a family of sets $A_i$, with i $\in\{1,2,...,n\}$, we need to prove the formula: \begin{equation} \bigcup_{i=1}^n A_i =(A_1\setminus A_2)\cup (A_2\setminus A_3) \cup \cdots\cup (A_{n-1}\setminus A_n)\cup (A_n\setminus A_1)\cup \bigcap_{i=1}^n A_i \end{equation}

So now I post what I have done, and I don't know if it is correct. Therefore I ask for suggestions for correcting the mistakes I made and for alternative approaches.
In order to solve this problem, it is given to us a simpler formula: \begin{equation} \bigcup_{i=1}^n A_i=A_1\cup(A_2\setminus S_1)\cup \cdots \cup (A_n\setminus S_{n-1}) \end{equation} with $S_k=\bigcup_{i=1}^kA_i$ for any generic $k$. So what I have thought is to modify the notation of the original formula, substituting $A_i$ with $B_{n-i+1}$. Thus $A_1 $ with $B_n$, $A_2 $ with $B_{n-1},\cdots, A_n $ with $B_1$, reaching the following formula. \begin{align*} \bigcup_{i=1}^nA_i=\bigcup_{i=1}^n B_i&=(B_n\setminus B_{n-1})\cup (B_{n-1}\setminus B_{n-2})\cup \cdots \cup (B_2\setminus B_1)\cup(B_1\setminus B _n)\cup \bigcap_{i=1}^nB_i\\ &=(B_1\setminus B_n) \cup (B_2\setminus B_1) \cup \cdots \cup (B_{n-1}\setminus B_{n-2})\cup (B_n\setminus B_{n-1}) \cup \bigcap_{i=1}^nB_i \end{align*}

Observation 1: define $Z_k=\bigcup_{i=1}^kB_k$, and we notice that $B_i\setminus B_{i-1}\supset B_i\setminus Z_{i-1}$.
Observation 2: $A\cup B=A\cup B\cup B = A\cup A \cup B$ for the property of the union. So the repeating of the union is the same.
Observation 3: if $B\subset C$, then $A\cup B \cup C=A\cup C$.
Observation 4: if $(B_1\setminus B_n)$ was $B_1$, the formula will be a supset of the simpler formula written above, and given that $\forall i,(B_i\setminus B_{i-1})\subset \bigcup_{i=1}^nB_i$ we have that the formula will be exactly $\bigcup_{i=1}^nB_i$.

So I was focusing on if we can reach $B_1$ from the formula doing the union of $(B_1\setminus B_n)$ with the other terms. Therefore $(B_1\setminus B_n)\cup (B_n\setminus B_{n-1})$ we get the set $(B_1 \setminus (B_n\cap B_{n-1})) $. With union of another term: $(B_1\setminus B_n)\cup (B_n\setminus B_{n-1})\cup (B_{n-1}\setminus B_{n-2})$ we have $(B_1 \setminus (B_n\cap B_{n-1}\cap B_{n-2}))$ and etc. [What I have written you can just check graphically with the Venn diagrams drawing a set called $B_1$ and a set $B_1\cap B_n$) in $B_1$].
We can then extend this result using induction.
At the end of the day: \begin{align*} &(A_1\setminus A_2)\cup (A_2\setminus A_3) \cup \cdots\cup (A_{n-1}\setminus A_n)\cup (A_n\setminus A_1)\cup \bigcap_{i=1}^n A_i\\ =& [(B_1\setminus B_n) \cup (B_n\setminus B_{n-1})\cup \cdots \cup (B_{2}\setminus B_{1})] \cup \\ &(B_2\setminus B_1) \cup \cdots \cup (B_{n-1}\setminus B_{n-2})\cup (B_n\setminus B_{n-1}) \cup \bigcap_{i=1}^nB_i\\ =&(B_1\setminus \bigcap_{i=1}^nB_i) \cup (B_2\setminus B_1) \cup \cdots \cup (B_{n-1}\setminus B_{n-2})\cup (B_n\setminus B_{n-1}) \cup \bigcap_{i=1}^nB_i \\ \supset &B_1 \cup (B_2\setminus B_1) \cup \cdots \cup (B_n\setminus B_{n-1}) \setminus \bigcap_{i=1}^nB_i \cup \bigcap_{i=1}^nB_i \\ \supset &B_1 \cup (B_2\setminus Z_1) \cup \cdots \cup (B_n\setminus Z_{n-1}) \setminus \bigcap_{i=1}^nB_i \cup \bigcap_{i=1}^nB_i \\ = &\bigcup_{i=1}^nB_i =\bigcup_{i=1}^nA_i \end{align*}

Again, I don't know if this solution is correct, and I gently ask you for feedbak and suggestions pls!

$\endgroup$
1
  • 3
    $\begingroup$ You can show inclusion in both ways. One way is trivial. For the other way, look at an element in the union. Either it's in all sets, or there's a set such that it's in it but not in the following set. $\endgroup$ Sep 17, 2023 at 7:01

1 Answer 1

2
$\begingroup$

Personally I find juggling unions and intersections and complements like you're doing both hard to read and hard to think about. It's simpler to just show that the two sets have the same elements.

By definition an element of $\bigcup_i A_i$ is an element of $A_i$ for some $i$. That's easy enough. An element of the RHS, on the other hand, is either an element of $A_i$ not in $A_{i+1}$ for some $i$ (with cyclic indices), or an element of all the $A_i$. The RHS is clearly a subset of the LHS. To prove the other inclusion, let $a \in \bigcup_i A_i$ be an element of the union. Then either $a \in \bigcap_i A_i$ is in the intersection, or there is some index $j$ such that $a \not \in A_j$. What we need to show is that we can choose $j$ such that $a \in A_{j-1}$ (with cyclic indices).

Why can we do this? Well, suppose otherwise; then $a \not \in A_{j-1}$, and either $a \in A_{j-2}$, which means we can choose $j-1$ as our new suitable index, or $a \not \in A_{j-2}$, and then either $a \in A_{j-3}$, or... (again, all indices are cyclic) Continuing in this way, and cycling around the indices if necessary, we must find a suitable $j$ because $a \in \bigcup_i A_i$ by hypothesis.

$\endgroup$
2
  • $\begingroup$ Wow, thank you! It's mind-blowing how easy was this question using your approach, so is this "element-based analysis" the main approach of thinking about sets, when you meet those monster formulas? $\endgroup$ Sep 18, 2023 at 8:29
  • $\begingroup$ @Alessandro: yeah, in my experience. Typically you show that two sets are equal by showing that an element of one is an element of the other and vice versa, and usually one direction is easy and one direction is interesting. $\endgroup$ Sep 18, 2023 at 14:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .