# Find $\bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty}A_n$

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.

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

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?

• Every natural number other than zero is the divisor of infinitely many natural numbers. – Bolton Bailey Dec 8 '16 at 8:11
• 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? – Zelazny Dec 8 '16 at 8:27
• @Zelazny Yes for the first and No for the second – Robert Z Dec 8 '16 at 8:35

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