Physics Forums (http://www.physicsforums.com/index.php)
-   Linear & Abstract Algebra (http://www.physicsforums.com/forumdisplay.php?f=75)
-   -   *|*Interesting Limit Set*|* (http://www.physicsforums.com/showthread.php?t=96183)

 bomba923 Oct23-05 01:17 AM

*|*Interesting Limit Set*|*

Not homework! Just curious ! :

$$\text{Is} \; \mathop {\lim }\limits_{n \to \infty } \bigcup\limits_{i = 0}^n {\frac{i} {n}} = \mathbb{Q} \cap \left[ {0,1} \right] \; ?$$

If so, then I will:
$${\text{Prove that }}\mathop {\lim }\limits_{n \to \infty } \bigcup\limits_{i = 0}^n {\frac{i}{n}} = \mathbb{Q} \cap \left[ {0,1} \right]$$
:smile:
If not, then I will:
$${\text{Prove that }}\mathop {\lim }\limits_{n \to \infty } \bigcup\limits_{i = 0}^n {\frac{i}{n}} \ne \mathbb{Q} \cap \left[ {0,1} \right]$$
:smile:

 AKG Oct23-05 01:42 AM

By:

$$\text{Is} \; \mathop {\lim }\limits_{n \to \infty } \bigcup\limits_{i = 0}^n {\frac{i}{n}} = \mathbb{Q} \cap \left[ {0,1} \right] \; ?$$

I suppose you mean:

$$\text{Is} \; \mathop {\lim }\limits_{n \to \infty } \bigcup\limits_{i = 0}^n \left \{\frac{i}{n}\right \} = \mathbb{Q} \cap \left[ {0,1} \right] \; ?$$

Anyways, I believe the answer is "No". I'm not entirely certain on the definition of the limit of a sequence of sets, but I would suspect that if the limit were to be what you hypothesize it is, then for all q in $\mathbb{Q} \cap [0,1]$, there exists N > 0 such that q is in

$$\bigcup\limits_{i = 0}^n \left \{\frac{i}{n}\right \}$$

for all n > N.

 bomba923 Oct23-05 07:56 PM

Quote:
 Quote by AKG I'm not entirely certain on the definition of the limit of a sequence of sets ...
!Hey, are you referring to the set-theoretic limit ?

 AKG Oct24-05 02:30 AM

Yes. So unless I made an error, the answer is "No," the limit is not $\mathbb{Q} \cap [0,1]$.

 bomba923 Dec17-05 06:07 PM

Hmm...it seems we have quite a spirited debate regarding that question on http://www.intpcentral.com/forums/showthread.php?t=7954.

However, we don't use the set-theoretic limit...and thus comes the unruly debate :redface:

(just thought I'd refer this thread here :shy:)

Admittedly, most members of that site seem to be a little too..well, imprecise

 shmoe Dec18-05 04:42 PM

I only looked briefly at that other website, but replacing the "n" in the upper limit of the union to "n!" changes the limit (this is assuming you mean the usual set-theoretic limit like the one you linked to). With n! your limit will be all the rationals in [0,1], with n you will just get {0,1}.

 bomba923 Dec18-05 07:10 PM

Quote:
 Quote by shmoe I only looked briefly at that other website, but replacing the "n" in the upper limit of the union to "n!" changes the limit (this is assuming you mean the usual set-theoretic limit like the one you linked to). With n! your limit will be all the rationals in [0,1], with n you will just get {0,1}.

 shmoe Dec18-05 10:56 PM

Quote:
 Quote by bomba923 :approve: Thank you! :approve: Please sign into INTPC (that forum) and help me out!
Help what out? If you understand what's going on, it looks like you need to explain to them what a set theoretic limit is. It looks like this is where the trouble is, and without understanding what you mean by the limit there is no hope at all of understanding your question.

If you are having difficulty understanding something yourself, post here and I'll do my best.

 bomba923 Dec19-05 02:04 AM

Thanks :smile:
From my understanding of the set-theoretic limit, in order for
$$\mathop {\lim }\limits_{n \to \infty } \bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} = \mathbb{Q} \cap \left[ {0,1} \right]$$

I must show that
$$\begin{gathered} \mathop {\lim }\limits_{n \to \infty } \inf \bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} = \mathop {\lim }\limits_{n \to \infty } \sup \bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} \Rightarrow \hfill \\ \mathop {\lim }\limits_{k \to \infty } \bigcup\limits_k {\bigcap\limits_{n \geqslant k} {\bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} } } = \mathop {\lim }\limits_{k \to \infty } \sup \bigcap\limits_k {\bigcup\limits_{n \geqslant k} {\bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} } } \hfill \\ \end{gathered}$$

However,
Quote:
 Quote by Wikipedia The supremum of a sequence of sets is the smallest set containing all the sets, i.e., the countable union of the sets.
Obviously, we know that
$$\bigcup\limits_n^\infty {\bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i} {{n!}}} \right\}} } = \mathbb{Q} \cap \left[ {0,1} \right]$$

Needless to say, we can also state that:
$$\bigcup\limits_n^\infty {\bigcup\limits_{i = 0}^n {\left\{ {\frac{i} {n}} \right\}} } = \mathbb{Q} \cap \left[ {0,1} \right]$$

*For the limit supremum,
$$\begin{gathered} \because \forall k \in \mathbb{N},\;\bigcup\limits_{n \geqslant k} {\bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} } = \mathbb{Q} \cap \left[ {0,1} \right] \Rightarrow \hfill \\ \therefore \mathop {\lim }\limits_{k \to \infty } \sup \bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} = \bigcap\limits_k {\bigcup\limits_{n \geqslant k} {\bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} } } = \mathbb{Q} \cap \left[ {0,1} \right] \hfill \\ \end{gathered}$$

The trouble is with the limit infinitum; although it is indeed intuitively plausible :biggrin:, how do I show mathematically that

$$\bigcup\limits_k {\bigcap\limits_{n \geqslant k} {\bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} } } = \mathbb{Q} \cap \left[ {0,1} \right]$$

?

 AKG Dec19-05 03:09 AM

Quote:
 Quote by bomba923 Thanks :smile: From my understanding of the set-theoretic limit, in order for $$\mathop {\lim }\limits_{n \to \infty } \bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} = \mathbb{Q} \cap \left[ {0,1} \right]$$ I must show that $$\begin{gathered} \mathop {\lim }\limits_{n \to \infty } \inf \bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} = \mathop {\lim }\limits_{n \to \infty } \sup \bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} \Rightarrow \hfill \\ \mathop {\lim }\limits_{k \to \infty } \bigcup\limits_k {\bigcap\limits_{n \geqslant k} {\bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} } } = \mathop {\lim }\limits_{k \to \infty } \sup \bigcap\limits_k {\bigcup\limits_{n \geqslant k} {\bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} } } \hfill \\ \end{gathered}$$
No, you need to show that:

$$\mathop {\liminf} _{n \to \infty} \bigcup _{i=0} ^{n!} \left \{\frac{i}{n!}\right \} = \mathop {\limsup} _{n \to \infty} \bigcup _{i=0} ^{n!} \left \{ \frac{i}{n!}\right \} = \mathbb{Q} \cap [0,\, 1]$$

and to show that, you need to show:

$$\bigcup _{k = 0} ^{\infty} \bigcap _{n = k} ^{\infty} \bigcup _{i=0} ^{n!} \left \{ \frac{i}{n!}\right \} = \bigcap _{k = 0} ^{\infty} \bigcup _{n = k} ^{\infty} \bigcup _{i=0} ^{n!} \left \{ \frac{i}{n!}\right \} = \mathbb{Q} \cap [0,\, 1]$$

Alternatively, you can use the first method on the link given, by looking at what they call "indicator variables." However, I think the method you started with is easy enough.

$$\bigcup _{k = 0} ^{\infty} \bigcap _{n = k} ^{\infty} \bigcup _{i=0} ^{n!} \left \{ \frac{i}{n!}\right \} = \bigcup _{k = 0} ^{\infty} \bigcup _{i=0} ^{k!} \left \{ \frac{i}{k!}\right \} = \mathbb{Q} \cap [0,\, 1]$$

The first equality holds because if m > n, then

$$\bigcup _{i=0} ^{n!} \left \{ \frac{i}{n!}\right \} \subset \bigcup _{i=0} ^{m!} \left \{ \frac{i}{m!}\right \}[/itex] since if m > n, then 1/n! is just a multiple of 1/m!. The second equality holds because every fraction will occur, because the fraction a/b in [0, 1] will occur when k = b, since a/b is just a multiple of 1/b!, specifically a/b = [a(b-1)!] * (1/b!) and clearly [a(b-1)!] < b! otherwise a/b > 1. Also: [tex]\bigcap _{k = 0} ^{\infty} \bigcup _{n = k} ^{\infty} \bigcup _{i=0} ^{n!} \left \{ \frac{i}{n!}\right \} = \bigcap _{k = 1} ^{\infty} (\mathbb{Q} \cap [0,\, 1]) = \mathbb{Q} \cap [0,\, 1]$$

The second equality holds for obvious reasons. The first is also obvious, especially given what I said about the liminf just before this, and you can figure that out on your own.

 shmoe Dec19-05 08:16 AM

Let A(n)={0, 1/n!, 2/n!,...,n!/n!}. Then A(n) is contained in A(n+1). The limit is then simply the union of these sets. Easy enough to show this is the rationals in [0,1]

 shmoe Dec19-05 08:48 AM

Quote:
 Quote by shmoe With n! your limit will be all the rationals in [0,1], with n you will just get {0,1}.
I thought about this a little more, and with an "n" the limit doesn't exist. The page you linked to gives an incorrect definition of the limit of a sequence of sets. The one with "indicator variables" is not equivalent to the limsup/liminf version.

The liminf/limsup version is correct, the indicator variable one actually gives the liminf, which is all elements not in only a finite number of sets in your sequence. The limsup gives all elements in infinitely many of the sets in your sequence.

This doesn't change my response with "n!" as it's a nested increasing sequence. With "n", the liminf and limsup are different (can you find them?).

 AKG Dec19-05 06:42 PM

shmoe

I thought the very same thing about the indicator variable formulation (although this was a while back when I saw this definition on wikipedia) and the two definitions actually are the same. You have to pay attention to the fine print:

If the limit as i goes to infinity of xi exists for all x

You will find that:

$$\{x : \lim _{i \to \infty}x_i = 1\} = \liminf _{i \to \infty} A_i$$

and

$$\{x : \lim _{i \to \infty}x_i = 0\} = (\limsup _{i \to \infty} A_i)^C$$

So the $\lim _{i \to \infty}x_i$ is defined for all x iff limsup = liminf.

 shmoe Dec19-05 10:12 PM

Ahh, good point. I missed the bit about the limit existing for all x. The limsup of the sets is all elements whose "indicator sequence" has limsup=1 (the usual limsup of a sequence here), the liminf of the sets is all elements whose indicator sequence has liminf=1. If the limits exist for all x, then the limsup and liminf of the sets are obviously equal, and vice versa.

 bomba923 Dec31-05 03:35 AM

Hmm...
Is this correct?
$$\begin{gathered} \mathop {\lim }\limits_{n \to \infty } \bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} = \mathbb{Q} \cap \left[ {0,1} \right] \Rightarrow \hfill \\ \mathop {\lim }\limits_{n \to \infty } \inf \bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} = \mathop {\lim }\limits_{n \to \infty } \sup \bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} = \mathbb{Q} \cap \left[ {0,1} \right] \Rightarrow \hfill \\ \bigcup\limits_{k \geqslant 0} {\bigcap\limits_{n \geqslant k} {\bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} } } = \bigcap\limits_{k \geqslant 0} {\bigcup\limits_{n \geqslant k} {\bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} } } = \mathbb{Q} \cap \left[ {0,1} \right] \Rightarrow \hfill \\ \bigcup\limits_{k \geqslant 0} {\bigcup\limits_{i = 0}^{k!} {\left\{ {\frac{i}{{k!}}} \right\}} } = \bigcap\limits_{k \geqslant 0} {\left( {\mathbb{Q} \cap \left[ {0,1} \right]} \right)} = \mathbb{Q} \cap \left[ {0,1} \right] \Rightarrow \hfill \\ \mathbb{Q} \cap \left[ {0,1} \right] = \mathbb{Q} \cap \left[ {0,1} \right] = \mathbb{Q} \cap \left[ {0,1} \right]. \hfill \\ \therefore \mathop {\lim }\limits_{n \to \infty } \bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} = \mathbb{Q} \cap \left[ {0,1} \right] \hfill \\ \end{gathered}$$

 shmoe Dec31-05 09:10 AM

As you've written it, not really. You're starting by assuming what you want to prove then have a bunch of one-way implications. These are all actually two way implications, "if and only ifs", but you don't mention this. Take a look again at how AKG organized it, considering the lim inf and lim sup seperately, and his justifications for each step.

Incidently, if you can show that the lim inf is the rationals in [0,1] since you also know lim inf is contained in lim sup (which is clearly contained in the rationals in [0,1] here), you must have lim inf=lim sup.

 bomba923 Jan1-06 11:59 PM

1) For any sequence of sets where lim inf and lim sup exist, will lim inf always be a subset of lim sup ?

2) Ok...notation-wise:

*Is it:
$$\mathop {\lim }\limits_{n \to \infty } \inf A_n$$

*Or:
$$\mathop {\lim \inf }\limits_{n \to \infty } A_n$$

Which notation is correct? Where do we place the "$n \to \infty$" ?

3) Can I prove my statement otherwise, using the worded definitions of liminf and limsup, as such:

$$\begin{gathered} \forall A \subset \mathbb{Q} \cap \left[ {0,1} \right],\; \hfill \\ \exists N \in \mathbb{N}\;{\text{such that }}\forall n > N,\;A \subset \bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} , \hfill \\ {\text{and }}\forall N \in \mathbb{N},\;\exists n > N\;{\text{such that }}A \subset \bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} \hfill \\ \end{gathered}$$

 shmoe Jan2-06 12:17 AM

Quote:
 Quote by bomba923 1) For any sequence of sets where lim inf and lim sup exist, will lim inf always be a subset of lim sup ?
lim sup and lim inf always exist, and yes lim inf will be a subset of lim sup. lim inf is all elements that are excluded from a finite number of sets only, lim sup is all elements that are in infinitely many of the sets, excluded from finitely many=> included in infinitely many.

Compare with the usual lim inf and lim sup of real sequances which always exist and are finite when the sequences are bounded. Any sequence of sets is "bounded" below by the empty set and above by the union of the sets (with the containment partial ordering).

Quote:
 Quote by bomba923 2) Ok...notation-wise: *Is it: $$\mathop {\lim }\limits_{n \to \infty } \inf A_n$$ *Or: $$\mathop {\lim \inf }\limits_{n \to \infty } A_n$$ Which notation is correct? Where do we place the "$n \to \infty$" ?
The second way, under both the lim and the inf. think of "lim inf" as one symbol. It's sometimes written as $$\underline{\lim}$$ for normal sequences (of real numbers) and I'd expect for sets as well ($$\overline{\lim}$$ for lim sup).

It's maybe worth noting how latex handles it: $$\liminf _{n \to \infty}$$

Quote:
 Quote by bomba923 3) Can I prove my statement otherwise, using the worded definitions of liminf and limsup, as such: $$\begin{gathered} \forall A \subset \mathbb{Q} \cap \left[ {0,1} \right],\; \hfill \\ \exists N \in \mathbb{N}\;{\text{such that }}\forall n > N,\;A \subset \bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} , \hfill \\ {\text{and }}\forall N \in \mathbb{N},\;\exists n > N\;{\text{such that }}A \subset \bigcup\limits_{i = 0}^{n!} {\left\{ {\frac{i}{{n!}}} \right\}} \hfill \\ \end{gathered}$$
I'm not sure what you're getting at here, since this is an increasing sequence the first statement follows from the second, and the second is a little silly-why bother with the N bound? Though these are certainly false if A is not finite.

All times are GMT -5. The time now is 04:50 AM.