3
$\begingroup$

Let $A_n = \{ m \in \mathbb{N} : \exists k \in \mathbb{N} \ \ km=n$} for $n \in \mathbb{N}$. I am trying to find $$\bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty}A_n$$ In general, this not a very difficult task, however, in this case it bothers me to see $k$ both in the definition of the set with $\exists$ and in the sum index. After all, we want $k$ to exist, not to choose it.

Answer based on user suggestions $$\bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty}A_n = \left( A_0 \cup A_1 \cup \dots \right) \cap \left( A_1 \cup A_2 \cup \dots \right) \cap \left( A_2 \cup A_3 \cup \dots \right) \cap \dots $$ Since $A_n$ is a set of divisors of $n$, $A_0 = \mathbb{N}, A_1 = \{1\}, A_2 = \{1, 2\}, A_3 = \{1, 3\}$ and so on. Moreover, $a \in A_ab$ for $a,b \in \mathbb{N}$. So $\bigcup_{n=k}^{\infty}A_n = \mathbb{N}$ and we have

$$\bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty}A_n = \left( A_0 \cup A_1 \cup \dots \right) \cap \left( A_1 \cup A_2 \cup \dots \right) \cap \left( A_2 \cup A_3 \cup \dots \right) \cap \dots = \mathbb{N} \cap \mathbb{N} \cap \mathbb{N} \cap \dots = \mathbb{N}$$

The notation is ambiguous - the $k$ in the definition of $A_n$ has nothing to do with the $k$ in the indexes of the unions and intersections.

$\endgroup$
  • 1
    $\begingroup$ You are correct that the choice of notation is unfortunate. $\endgroup$ – Bolton Bailey Dec 8 '16 at 8:09
1
$\begingroup$

Hint. $A_n$ is the set of divisors of $n$ and $$S:=\bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty}A_n$$ consists of integers which belong to $A_n$ for infinitely many $n$.

$S$ is not empty because $1\in A_n$ for all $n$ (note that $A_0$ is not empty!).

Moreover if $m$ is a positive integer then $m\in A_{md}$ for all $d\geq 1$. Hence $$\bigcup_{n=k}^{\infty}A_n\supset \bigcup_{m=1}^{\infty}\bigcup_{d=k}^{\infty}A_{md}\supset \bigcup_{m=1}^{\infty} \{m\}=\mathbb{N}$$

What may we conclude?

$\endgroup$
  • 2
    $\begingroup$ Every natural number other than zero is the divisor of infinitely many natural numbers. $\endgroup$ – Bolton Bailey Dec 8 '16 at 8:11
  • $\begingroup$ So $A_0 = \mathbb{N}$, and because of the fact you mention each inner union is actually $\mathbb{N}$, so the whole intersection of unions is $\mathbb{N}$? On a side note, does the $k$ in the definition of the set have anything to do whatsoever with the $k$ in the index of the unions/intersections? $\endgroup$ – Zelazny Dec 8 '16 at 8:27
  • 1
    $\begingroup$ @Zelazny Yes for the first and No for the second $\endgroup$ – Robert Z Dec 8 '16 at 8:35
2
$\begingroup$

It is best that we rephrase the question in layman terms, and then attempt to answer it.

$A_n$, as you can observe,is the set of divisors of $n$.

Suppose that $x \in \displaystyle\bigcap_{k=0}^\infty \displaystyle\bigcup_{n \geq k} A_n$.

This means, that for all $k$, $x \in \displaystyle\bigcup_{n \geq k} A_n$.

This means, that for all $k$, there is an $n$ larger than $k$, such that $x \in A_n$.

This means that for all $k$, there is $n$ larger than $k$, such that $x$ is a divisor of $n$.

Now, having done this, you know that the above statement is true for every $x$, because given $k$, you can take the first multiple of $x$ that comes after $k$, call it $n$, then $x \in A_n$.

Therefore, what you have to attempt to prove is that $\displaystyle\bigcap_{k=0}^\infty \displaystyle\bigcup_{n \geq k} A_n = \mathbb N$ !

We will now rigorously prove this.

How would you do this? One inclusion is obvious: Of course $\displaystyle\bigcap_{k=0}^\infty \displaystyle\bigcup_{n \geq k} A_n$ can consist only of natural numbers, because $A_n$ themselves contain only natural numbers.

The other way, let $x \in \mathbb N$. Let $k \in \mathbb N$. Let $l = \lceil \frac kx \rceil$,then note that $n=xl \geq k$ and $n=xl \implies x \in A_n$. Therefore, $x\in \displaystyle\bigcap_{k=0}^\infty \displaystyle\bigcup_{n \geq k} A_n$.

That completes the argument.


Actually, it turns out that $\cap_{k=0}^\infty \cup_{n \geq k} A_n$ has a name : the limit superior of $A_n$. This quantity may also be defined for sequences, using the fact that their images are sets.

Actually, it is easy to see from this definition that an element $x$ is in the limit superior of $A_n$ if and only if $x$ belongs to infinitely many $A_n$. This translates to : $x$ is a divisor of $n$ for infinitely many $n$, since $x\in A_n$ means it is a divisor of $n$. This is true for all $x$, so the claim above follows easily.

There is another quantity, the limit inferior, which is obtained by switching the $\cap$ and $\cup$ in the limsup definition. The limit inferior of the $A_n$ can be obtained using the dual fact that $x$ is in the liminf if and only if $x \in A_n$ eventually i.e. $x \notin A_m$ for only finitely many $m$. It is not difficult to see that the liminf of these $A_n$ is the set $\{1\}$.

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