Cardinality of an interval as a limit

[Fermat1]

Let $I$ be an interval and $A_{n}$ be the set of $k/n$ where $k$ is an integer.

Prove that $|I|$ is the limit as $n$ tends to infinity of $\frac{1}{n}|(IA_{n})|$ where $IA_{n}$ denotes intersection.

My plan was to split it up into cases for the different type of intervals and come up with formulas for $|(IA_{n})|$, but I'm finding that very tricky.

Thanks

 

[Euge]

Let $I$ be an interval and $A_{n}$ be the set of $k/n$ where $k$ is an integer.

Prove that $|I|$ is the limit as $n$ tends to infinity of $\frac{1}{n}|(IA_{n})|$ where $IA_{n}$ denotes intersection.

My plan was to split it up into cases for the different type of intervals and come up with formulas for $|(IA_{n})|$, but I'm finding that very tricky.

Thanks

Hi Fermat,

The stated problem is a bit unclear; you used the absolute value bars to indicate both cardinality and Lebesgue measure? I'm assuming that $|I|$ is the Lebesgue measure of $I$ and $|IA_n|$ is the cardinality of $I\cap A_n$ (with the exception that |IA_n| is $\infty$ if $I\cap A_n$ is infinte). If $I$ is an unbounded interval, $|I| = \infty$ and $|I\cap A_n| = \infty$. So the equation will hold. So suppose $I$ is a bounded interval. There are four possible forms for $I$: $(a,b)$, $[a,b)$, $(a,b]$, and $[a,b]$. I'll do the case when $I = [a,b]$, as the others have similar arguments. When $I = [a,b]$, $|I \cap A_n|$ is no more than $nb - na + 1$ and no less than $nb - na - 3$. Hence, $||I \cap A_n| - (nb - na)| < C$ for some constant $C$ independent of $n$. Thus,

$$ \left|\frac{|IA_n|}{n} - |I|\right| < \frac{C}{n}.$$

Since $\frac{C}{n} \to 0$ as $n \to \infty$, we deduce that

$$ \lim_{n\to \infty} \frac{|IA_n|}{n} = |I|$$.

 

[Fermat1]

Hi Fermat,

The stated problem is a bit unclear; you used the absolute value bars to indicate both cardinality and Lebesgue measure? I'm assuming that $|I|$ is the Lebesgue measure of $I$ and $|IA_n|$ is the cardinality of $I\cap A_n$. If $I$ is an unbounded interval, $|I| = \infty$ and $|I\cap A_n| = \infty$. So the equation will hold. So suppose $I$ is a bounded interval. There are four possible forms for $I$: $(a,b)$, $[a,b)$, $(a,b]$, and $[a,b]$. I'll do the case when $I = [a,b]$, as the others have similar arguments. When $I = [a,b]$, $I \cap A_n$ has no more than $nb - na + 1$ elements and no less than $nb - na - 3$ elements. Hence, $||I \cap A_n| - (nb - na)| < C$ for some constant $C$ independent of $n$. Thus,

$$ \left|\frac{|IA_n|}{n} - |I|\right| < \frac{C}{n}.$$

Since $\frac{C}{n} \to 0$ as $n \to \infty$, we deduce that

$$ \lim_{n\to \infty} \frac{|IA_n|}{n} = |I|$$.

Thanks very much. Can I ask how you got the bounds $nb - na + 1$ and $nb - na - 3$, and how I obtain bounds for the other sorts of intervals. Thanks

 

[Euge]

Thanks very much. Can I ask how you got the bounds $nb - na + 1$ and $nb - na - 3$, and how I obtain bounds for the other sorts of intervals. Thanks

When $I = [a, b]$, $I\cap A_n$ is the set of rationals of the form $\frac{k}{n}$ which satisfy $a \le \frac{k}{n} \le b$, i.e., $na \le k \le nb$. So $|I \cap A_n|$ is the number of integers $k$ in the interval $[na,nb]$. The least integer in $[na,nb]$ is either $na$ or $\lfloor na \rfloor + 1$ (depending on whether or not $na$ is an integer) and similarly the greatest integer in $[na,nb]$ is either $nb$ or $\lfloor nb \rfloor - 1$. Hence $|I \cap A_n|$ is either $nb - na + 1$, $\lfloor nb \rfloor - na$, $nb - \lfloor na \rfloor$, or $\lfloor nb \rfloor - \lfloor na \rfloor - 2$. Each of these numbers are between $nb - na - 3$ and $nb - na + 1$ since $\lfloor nb \rfloor \in (nb - 1, nb]$ and $\lfloor na \rfloor \in (na - 1, na]$. Therefore $|I \cap A_n|$ is no more than $nb - na + 1$ than $nb - na + 3$.

The other cases are dealt with in nearly the same way.