2
$\begingroup$

I'm faced with a set of strictly increasing functions $\Bbb N\to \Bbb N$, i.e. positive integer valued sequences. The only thing I know about them is that they are pairwise eventually disjoint, by which I mean that given $U$, $V$ in this set, $U(\Bbb N)\cap V(\Bbb N)$ is finite.

Is this family countable? Uncountable? Does it depend?

Obviously the set of all positive integer sequences is uncountable, so this feels like a bit of a long shot, but I'm hoping the pairwise eventually disjoint condition might put a cap on the cardinality.

One thing I've been able to do, using a sort of diagonal argument, is to show that given such a set, if it's countable, I can find a new sequence that's eventually pairwise disjoint to every element in the set, and yet has no number assigned to it. But this new sequence won't actually be in the set, so this doesn't produce a contradiction like a diagonal argument is supposed to.

If the set is countable, then I can "decapitate" each sequence by a finite amount to obtain a set of pairwise disjoint sequences, which I'd really like to be able to do.

$\endgroup$
1
$\begingroup$

You can have as many as $2^\omega=\mathfrak{c}$ such sequences. First, we can identify strictly increasing sequences with their ranges. Two subsets of $\Bbb N$ are almost disjoint if their intersection is finite. There are families of $2^\omega$ pairwise almost disjoint infinite subsets of $\Bbb N$: see my answer to this question and the answers to the question that it duplicated for a variety of constructions.

$\endgroup$
2
$\begingroup$

For each real number $r>1$ we can define $f_r(n)=\lfloor rn\rfloor$. If $x\neq y$ then there exists natural number $N$ such that $|x-y|>1/N$, it forces $f_x(N)\neq f_y(N)$. Also, $\lfloor r(n+1)\rfloor=\lfloor rn+r \rfloor\ge \lfloor rn+1\rfloor>\lfloor rn\rfloor $ so $f_r$ is strictly increasing. Therefore $r\mapsto \lfloor rn\rfloor$ gives $\mathfrak{c}$ many strictly increasing sequences of natural numbers.

$\endgroup$
0
$\begingroup$

There is no concrete answer. If the sets are pairwise disjoint, it is easy to show that the family is countable, but it will also satisfy your requirements.

However, it is possible to find an uncountable family of sets which are pairwise eventually disjoint, or almost disjoint. The key point is to note that there is no uniform bound on when two sets become disjoint.

$\endgroup$
  • $\begingroup$ Did I misunderstand the question? $\endgroup$ – Asaf Karagila Oct 6 '13 at 0:51
  • $\begingroup$ No, your answer was spot-on, but Brian provided an explicit construction which I thought was interesting. $\endgroup$ – Jack M Oct 6 '13 at 1:08
  • $\begingroup$ No he didn't. tetori provided an example, Brian provided a link which you should have found on your own using the search box and/or Google. $\endgroup$ – Asaf Karagila Oct 6 '13 at 13:08
  • $\begingroup$ I'm sorry, I should have guessed that the technical term for what I was looking for was "almost disjoint". How exactly could I have found that question by searching, given what I knew about the problem? Don't take it personally, I just thought his answer was slightly more complete. I could only accept one. $\endgroup$ – Jack M Oct 6 '13 at 13:20

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.