1

A sequence of objects in a set $S$ is, by definition, a function $f$ from the set of natural numbers $\mathbb{N}=\{1,2,\ldots\}$ to $S$.

I wanted to see whether the following function makes sense to say that we have defined a sequence of prime numbers.

Let $f:\mathbb{N}\rightarrow \mathbb{N}$, $f(n)$ is $n$-th prime number. Here prime numbers are taken from $2$, and written in increasing order, and then enumerated as first, second, etc.

Does it make sense to say that this is a sequence of prime numbers? If yes, can we assert that $f(n)$ can not be expressed by any formula in $n$? (As we know there are infinitely many primes, but we do not an algebraic expression in $n$ which expresses the $n$-th prime number, am I right?)

Beginner
  • 10,836
  • 1
    You are right, this is a well-defined sequence, but indeed it has no closed form. – TheSilverDoe Sep 02 '20 at 10:20
  • May I get to know what it closed form? – Beginner Sep 02 '20 at 10:22
  • I mean that, as you said, you cannot express the $n-$th term in terms of $n$. – TheSilverDoe Sep 02 '20 at 10:23
  • Can you precise what a formula in $n$ is? Enumerating the primes is primitive recursive. – mathcounterexamples.net Sep 02 '20 at 10:27
  • I mean, since currently exact values of primes are known up to a certain limit, but beyond it, we do not know the prime number; we know only that it exists. This is because, there is no expression in terms of $n$ and other known integers, real numbers, which give $n$-th prime number. – Beginner Sep 02 '20 at 10:31
  • Related: https://math.stackexchange.com/questions/3797362/is-list-of-prime-numbers-a-sequence – Martin R Sep 02 '20 at 10:48
  • @TheSilverDoe What do you mean by ...you cannot express* the $n$−th term in terms of $n$.*? – mathcounterexamples.net Sep 02 '20 at 11:31
  • @mathcounterexamples.net I mean that there is no "formula", in the (intuitive) sense that there is no elementary function (which can be expressed with usual operations and functions) who takes $n$ as an argument and gives the $n-$th prime number. I know this is not a rigourous definition of "formula", but I think this is what the OP wants to know. – TheSilverDoe Sep 02 '20 at 11:33
  • @TheSilverDoe I understand. But I think that it is dangerous to go in that direction. In particular, because understanding that a formula is a fuzzy concept is interesting in itself. In particular, a closed form expression is probably what you mean by a formula. Right? Then this article provides links between primitive recursion function (that $p(n)$ is) and closed form expressions. – mathcounterexamples.net Sep 02 '20 at 11:40

1 Answers1

1

Does it make sense to say that this is a sequence of prime numbers?

Yes, such a sequence makes perfect sense.

If yes, can we assert that $f(n)$ can not be expressed by any formula in $n$?

This all depends on what you call a formula. For example you can find a primitive recursive function that enumerates the primes. See this article for details.

mathcounterexamples.net
  • 70,018