7

Let $f:\mathbb{N}\to\mathbb{R}$ such that $f(n)=p$ (where $p$ is the $n$th prime number). My doubt is whether this is a function and hence a sequence. I got this doubt because we don't know all the primes, right? So after a certain stage, we don't know what is the output of the function.

Andrés E. Caicedo
  • 79,201
Shash
  • 99
  • 4
    Nevertheless, it is a sequence since it is clearly defined. And we can always find the next prime (in principle). But even a sequence of uncomputable (but well-defined) entries would be a sequence. For example, the busy-beaver values from a sequence. – Peter Aug 20 '20 at 10:59
  • 1
    It is possible to generate primes one by one without limit, given enough time. So technically we do know how to get the output. It is just a matter of time. – justadzr Aug 20 '20 at 11:05
  • 4
    Is $\pi$ a number if we don't know all of its digits? – Ennar Aug 20 '20 at 11:05
  • 1
    @Yourong'DZR'Zang And with unlimited space because the numbers get bigger and bigger. But this is usually assumed anyway in decision problems. – Peter Aug 20 '20 at 11:07
  • 1
    There are sequences for which we know only the first two terms, eg the Ackermann function $A(4,n)$, but it's still well-defined. – Chrystomath Aug 20 '20 at 11:07
  • 1
    @Chrystomath But here we are only limited because of the magnitude, in principle we can calculate those numbers. Therefore I mentioned the busy beaver sequence where we cannot do this. – Peter Aug 20 '20 at 11:09
  • 1
    @Ennar A very good point, this already applies to the algebraic number $\sqrt{2}$ – Peter Aug 20 '20 at 11:13
  • 1
    @Peter, yes, sure. I was just thinking of any irrational number, but using algebraic number probably makes even stronger point. – Ennar Aug 20 '20 at 11:15
  • 1
    It might be worth taking a look at https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016-01556-4/S0273-0979-2016-01556-4.pdf , in particular section 3 ("Bargaining"). – Barry Cipra Aug 20 '20 at 11:28

2 Answers2

8

The fact that we humans don't know all the elements of a sequence doesn't stop a sequence from being a sequence. Yes, the sequence of prime numbers is a sequence, as well-defined as any.

Arthur
  • 199,419
2

Similarly, $(a_n)_{n\in\mathbb N}$ defined as $a_n = n,$ that is an identity function on the set of natural numbers $a:\mathbb N \to \mathbb N$ defined with $a: n \mapsto n$, would be a non-sequence, because we do not know all the natural numbers. Right?

The fact we do not know apriori some / many / almost all of the terms does not invalidate the definition. As long as each term is well defined, the sequence is defined.
The natural numbers are well-ordered, so their subset of prime numbers are well-ordered, too. Hence 'the next prime number' is well defined at each step, and so is the whole sequence. No matter how hard it might be to find the actual value of the 'next term'.

CiaPan
  • 13,049