1
$\begingroup$

I have a set-theory equation in my book that I don't understand how to prove.

I have a disjoint collection of sets $A_1, A_2,\cdots\ , A_n$ and a disjoint collection $A_1\star, A_2\star, ..., A_n\star$ is constructed with the property that $(A_1\star)\cup(A_2\star)\cup(A_3\star)\cdots = (A_1)\cup(A_2)\cup(A_3)\cdots$

$A_i\star$ is defined by $$A_1\star = A_1,\quad A_i\star = A_i \diagdown [(A_1)\cup(A_2)\cup\cdots(A_{i-1})]$$ where $$A_i \diagdown [(A_1)\cup(A_2)\cup\cdots(A_{i-1})] = A_i\cap\overline{[(A_1)\cup(A_2)\cup...(A_{i-1})]}$$.

The book says it "should be easy to see that" $$(A_1\star)\cup(A_2\star)\cup(A_3\star)\cup... = (A_1)\cup(A_2)\cup(A_3)\cup\cdots$$

Should I use induction, and if so how?

Thanks.

$\endgroup$
1
  • 4
    $\begingroup$ I don't think the first collection of sets are disjoint.The result would be a triviality in that case $\endgroup$ – Vishesh Jul 26 '13 at 13:52
0
$\begingroup$

Use induction as below

For $n=1$, the definition tells that the statement $A_1\star=A_1$ holds.

Let this be true for $n=k$.

Now, for $n=k+1$

$$\bigcup_{j=1}^{k+1}A_{j}\star=\left(\bigcup_{j=1}^{k}A_{j}\star\right)\bigcup A_{k+1}\star\\ =\left(\bigcup_{j=1}^{k}A_{j}\right)\bigcup \left(A_{k+1}\bigcap\overline{\bigcup_{j=1}^k A_j}\right)\\ =\left(\bigcup_{j=1}^{k+1}A_{j}\right)\bigcap\left(\bigcup_{j=1}^{k}A_{j}\bigcup\overline{\bigcup_{j=1}^k A_j}\right)\\ =\left(\bigcup_{j=1}^{k+1}A_{j}\right)\bigcap \Omega=\bigcup_{j=1}^{k+1}A_{j}$$ where $\Omega $ is the universal set. Hence the statement is true for all $n\in \mathbb{N}$.

$\endgroup$
3
  • $\begingroup$ Your argument looks good. Thanks. I was just wondering if the number of sets is infinite, do I just extend the natural numbers to infinity and then extend induction like that? $\endgroup$ – user85362 Jul 26 '13 at 14:33
  • $\begingroup$ Yes, that's the way to do, because infinity never really means infinity, it means up to some natural number which can be arbitrarily large, actually infinity is not defined in $\mathbb{N}$ $\endgroup$ – Samrat Mukhopadhyay Jul 26 '13 at 14:35
  • $\begingroup$ using induction here is indeed rather inept, as brian m. scott said. I just thought it would make the intuition of how the disjoint star sets are created clearer. Warning: if you want to show that the limit of a sequence is a rational number it doesn't suffice to show that all elements in the sequence are rational. Or, to show that the union of sets is finite, it doesn't suffice to show that each finite union is finite. Or, to show that an infinite cartesian product of sets is countable, it doesn't suffice that each finite cartesian product is countable. $\endgroup$ – Bananach Jul 26 '13 at 16:18
2
$\begingroup$

If we look at the union step for step, in each step $i$, $A_i^*$ differs from $A_i$ in that it has been taken away the elements from $A_{i-1}, A_{i-2},\dots,A_1$. But these elements are already in your union up to this step, hence it doesnt matter (this is an argument of induction; what I wrote actually proves, that for each $i\in\mathbb{N}$ the two different unions up to this point are the same).

Thus, you know that all of the finite unions are the same. Now, every element that is in an infinite union, already belongs to a finite sub-union. Therefore, if $a$ is in the non-star union, you can find a finite sub-union that contains $a$, but this sub-union is equal to the star sub-union, hence the infinite star-union contains $a$ as well.

$\endgroup$
1
$\begingroup$

You don’t really need induction. It’s obvious that $\bigcup_{k\in\Bbb Z^+}A_k^*\subseteq\bigcup_{k\in\Bbb Z^+}A_k$. Now suppose that $x\in\bigcup_{k\in\Bbb Z^+}A_k$, and let $m=\min\{k\in\Bbb Z^+:x\in A_k\}$; clearly $x\in A_m^*$, and it follows immediately that $\bigcup_{k\in\Bbb Z^+}A_k\subseteq\bigcup_{k\in\Bbb Z^+}A_k^*$ and hence that $\bigcup_{k\in\Bbb Z^+}A_k^*=\bigcup_{k\in\Bbb Z^+}A_k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy