2
$\begingroup$

I was wondering what the potential cardinality of the set of entries in the Online Encyclopedia of Integer Sequences (oeis.org) may be.

After all, if we consider the text box with its "Search" button, we're seeing a map from sequence IDs to sequence specifications. From this vantage the set of entries is not limited by physical storage. There could be a mathematical space of entries that are only materialized in storage upon request.

I've seen that the site has a policy to include interesting sequences, not uninteresting sequences. But I haven't seen a specification of what is "interesting" or "uninteresting". I'm not sure that the cardinality of the entry set is constrained by the "interestingness" criterion.

Now, are entries in OEIS required to be computable?

I mean, must there exist for each entry a finite-sized algorithm that would, given sufficient and perhaps infinite time, generate all of the sequence's elements? In that case we're limited to aleph-null entries, aren't we?

Do we know of any other constraints?

Is it OK if on math.se we discuss the specifics of OEIS in practice? I mean, if my question oversteps the bounds of propriety, please feel free to restrict answers to proper seriousness and relevance.

$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

The size of the encyclopaedia at any time will be finite. This is determined by the finite storage capacity available (amongst other constraints).

Only countably many sequences will ever be described since we have a finite language with finite strings. If the universe is finite, storage capacity will always be finite.

There are uncountably many possible sequences. Therefore, for example, there are integer sequences which ultimately grow faster than any formula we can construct.

$\endgroup$
4
  • 3
    $\begingroup$ You say “There are uncountably many possible sequences. Therefore, for example, there are integer sequences which ultimately grow faster than any formula we can construct.” There are indeed uncountably many integer sequences, but that doesn’t imply there are fast-growing ones. For example, there are uncountably many sequences consisting only of zeroes and ones, and none of them grow fast. $\endgroup$
    – Steve Kass
    Apr 20, 2014 at 22:32
  • $\begingroup$ @SteveKass Indeed that is true, and having done my going to bed routine, I thought that the comment was loosely expressed. Too tired to amend it tonight, but thanks for pointing it out, and for the nice counterexample. Also the finite sequences are countable, only the infinite ones are uncountable.. $\endgroup$
    – Mark Bennet
    Apr 20, 2014 at 22:40
  • $\begingroup$ So, the sequences that exist have the cardinality of the continuum, the sequences that we can ever describe have the cardinality of the integers, and the sequences that we ever have described have finite cardinality? Aleph-two and beth-two for example are entirely out of the question, I think? I'm not 100% clear on uncountables. $\endgroup$
    – minopret
    Apr 20, 2014 at 22:44
  • 1
    $\begingroup$ @minopret: Yes to your first sentence. $\beth_2$ is out of the question because there are only $\beth_1$ integer sequences. However, it is possible that $\aleph_2<\beth_1$, so perhaps there are at least $\aleph_2$ different sequences. They can't all be describable, however, because $\aleph_2$ is by definition larger than $\aleph_0$. $\endgroup$
    – hmakholm left over Monica
    Apr 20, 2014 at 22:57

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.