17
$\begingroup$

In some cases, we will have to consider the union or the intersection of several, even infinitely many sets, defined in the obvious way. For example, if for every positive integer $n$, we are given a set $S_n$, then $$\bbox[border:1px solid red]{\bigcup_{n=1}^\infty S_n}=S_1\cup S_2\cup\cdots=\{x\mid x\in S_n\text{ for some }n\},$$ and $$\bigcap_{n=1}^\infty S_n=S_1\cap S_2\cap\cdots=\{x\mid x\in S_n\text{ for all }n\}.$$ Two sets are said to be disjoint if their intersection is empty. More generally, several sets are said to be disjoint if no two of them have a common element. A collection of sets is said to be a partition of a set $S$ if the sets in the collection are disjoint and their union is $S$.

Normally what I know is that you can make a union or an intersection between only two sets. In this expression, there is a big union of sets. I'm asking about the meaning of this expression – what does it mean? What does the infinity sign do at the top?

Things are even more complicated with De Morgan's laws, which use the same expression:

Two particularly useful properties are given by De Morgan's laws which state that $$\left(\bigcup_nS_n\right)^c=\bigcap_nS_n^c,\quad\quad\quad\quad\left(\bigcap_nS_n\right)^c=\bigcup_nS_n^c.$$

Anyone who can explain to me the expression or De Morgan's laws would be much appreciated.

$\endgroup$
17
$\begingroup$

The equation where you've enclosed the first part in red is the definition of the $\bigcup_{n=1}^{\infty} S_n$ notation.

It works just like sum nontation does: $$ \sum_{n=a}^{b} f(n) \quad\text{means}\quad f(a)+f(a+1)+\cdots+f(b-1)+f(b) $$ and $$ \bigcup_{n=a}^{b} f(n) \quad\text{means}\quad f(a)\cup f(a+1)\cup\cdots\cup f(b-1)\cup f(b) $$ $$ \bigcap_{n=a}^{b} f(n) \quad\text{means}\quad f(a)\cap f(a+1)\cap\cdots\cap f(b-1)\cap f(b) $$

When the upper limit is $\infty$ it means a union of infinitely many sets: $$ \bigcup_{n=a}^{\infty} f(n) \quad\text{means}\quad f(a)\cup f(a+1)\cup\cdots $$ whose precise meaning is defined in the explanation you quote.

$\endgroup$
  • $\begingroup$ Think of the infinity sign on the top as playing the same role here as it does in a sum $\displaystyle\sum_{n=1}^\infty x_n$. $\endgroup$ – Harald Hanche-Olsen Sep 3 '13 at 13:32
  • 1
    $\begingroup$ One important difference with the $\sum_{n=1}^\infty f(n)$ notation is that $\bigcup_{n=1}^\infty S_n$ is always defined (provided the sets $S_n$ are), without any requirement of "convergence" as is the case for infinite sums. $\endgroup$ – Marc van Leeuwen Sep 3 '13 at 13:44
  • $\begingroup$ @MarcvanLeeuwen Sure. But even the sum is always defined (though possibly infinite) when the items being summed are all nonnegative. $\endgroup$ – Harald Hanche-Olsen Sep 3 '13 at 15:05
  • $\begingroup$ Please excuse me since I haven't used math or statistics for a very very long time. So What I understood from your example using summation(sigma) sign. That the upper part is the boundary of the range or the end condition and the lower part (n=1) is the start of the collection. So $\sum_{n=1}^\infty f(n)$ means that the summation of outputs for each parameter passed to f in this case n where n starts with one and ends with $\infty$. An example would be $\sum_{n=1}^3 f(n) = f(1) + f(2) + f(3)$, is that correct? $\endgroup$ – Omar S. Sep 7 '13 at 16:27
  • $\begingroup$ @OmarA.Shaban: Yes. $\endgroup$ – Henning Makholm Sep 7 '13 at 16:37
2
$\begingroup$

Considering de Morgan's laws, they become basic principles of handling negation in the presence of quantifiers in logic. Let's first state more formally $$ x\in\bigcup_{i\in\Bbb N}S_n \iff \exists n\in\Bbb N: x\in S_n \qquad\text{and}\qquad x\in\bigcap_{i\in\Bbb N}S_n \iff \forall n\in\Bbb N: x\in S_n. $$ Now the law $\left(\bigcup_{i\in\Bbb N}S_n\right)^c=\bigcap_{i\in\Bbb N}{S_n}^c$ becomes, remembering that set equality just means one is member of the left hand side if and only if one is member of the right hand side, $$ \lnot(\exists n\in\Bbb N: x\in S_n)\iff \forall n\in\Bbb N: \lnot(x\in S_n). $$ Similarly $\left(\bigcap_{i\in\Bbb N}S_n\right)^c=\bigcup_{i\in\Bbb N}{S_n}^c$ becomes $$ \lnot(\forall n\in\Bbb N: x\in S_n)\iff \exists n\in\Bbb N: \lnot(x\in S_n). $$ These are nothing more or less than the rules for handling negation of existentially or universally quantified phrases (in the particular case of quantification over$~\Bbb N$, but one could replace it by any set).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.