1

An infinite sequence of sets $S_2,S_3,S_4,\ldots$ is called a cumulative sequence if the following condition holds:
$$\exists m\geq 2 \quad \forall n>m \quad S_n\subseteq S_2\cup S_3\cup S_4\cup \ldots \cup S_m. $$ Prove that the sequence $S_2,S_3,\ldots$ where $$S_n=\{\text{multiples of} \ n\} $$ is not a cumulative sequence.

This is what I tried, can someone please see if my line of thinking and answer is correct?
The negation is
$$\forall m\geq 2 \quad \exists n > m \quad S_n \nsubseteq S_2\cup S_3 \cup \ldots S_m.$$

So what I thought was: since we deal with $\forall m\geq 2$, what happens when $m$ gets big?
So the union $$\bigcup_{i=2}^\infty S_i \rightarrow \mathbb{Z}. $$ So for any finite $m$, I just have to pick a set containing integers which are not multiples of the previous $m-1$ integers.
So I thought of $m!$, which is $m(m-1)\ldots(2)$ which has every integer before it as a factor. So then just pick $n> m!+1$ since $1$ is not divisible by any of the $m-1$ factors.
Is this a valid choice of $n$ and is there a simpler way to think about this?

Natash1
  • 1,379

1 Answers1

1

Close enough, but you should make it more specific. To satisfy "$\exists n>m$" (from the negated statement), you don't need to find lots of values of $n$ — finding just one will be good enough. In your solution everything was good until you said

just pick $n>m!+1$

because not any such $n$ would work. For example, $n=2\cdot m!$ satisfies $n>m!+1$, but it doesn't work for your purposes because all its factors are contained in $2,\ldots,m-1,m$.

So, as I said, be specific: what one specific value of $n$ satisfies what you want: $n>m$ and it doesn't have any factors from the list $2,\ldots,m-1,m$? Hint: you already mentioned it in your solution!

zipirovich
  • 14,670
  • 1
  • 26
  • 35
  • Ah I see what you are saying, so maybe a better way is to say: since $m!+1>m$, then whenever $n \textbf{=} m!+1$, then the negation condition holds?
    Also, what this also makes me think is could I have just let $n = m+1$ as well?     – Natash1 Nov 10 '17 at 02:00
  • @Natash1: Yes, exactly, letting $n=m!+1$ will work. But $n=m+1$ does not necessarily work. The reason is that you're trying to satisfy two conditions: that $n>m$ and that $n$ doesn't have any factors from the list $2,\ldots,m−1,m$. Obviously, $n=m+1$ satisfies the first condition, but not necessarily the second. Counterexample: if $m=9$, then $n=m+1=10=2\cdot5$ has all its factors among $2,\ldots,m-1,m$. In fact, it's definitely not going to work unless $m+1$ is a prime. But we need something that works for all $m$. – zipirovich Nov 10 '17 at 02:15
  • Thank you, I think I am quite lucky then to have guessed $n=m!+1$ initially then. – Natash1 Nov 10 '17 at 02:22
  • 1
    @Natash1: Another idea that I had when I read your question was to pick any prime $p>m$. Fortunately, there are infinitely many of those out there! – zipirovich Nov 10 '17 at 02:23