23
$\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$

2 Answers 2

27
$\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 notation 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$
6
  • $\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$ Commented Sep 3, 2013 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$ Commented Sep 3, 2013 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$ Commented Sep 3, 2013 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$
    – omars
    Commented Sep 7, 2013 at 16:27
  • $\begingroup$ @OmarA.Shaban: Yes. $\endgroup$ Commented Sep 7, 2013 at 16:37
3
$\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$

You must log in to answer this question.

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