Is there a bijection from natural numbers to set of prime numbers?

[Lax Clarke]

Hi,

I was wondering about proving that there is a bijection from natural numbers to set of prime numbers. It is "obvious" that there is an n-th prime number, but is that sufficient to prove that prime number set can be considered in bijection with natural numbers? Or do we need to "construct" this process (or closed for formula) of getting the n-th prime number?

Essentially, under what conditions can we say "such a function exists" even when we do not have closed form formula for the function?

[Arturo Magidin]

Under any conditions that logically guarantee the existence of such a function.

In this case, you can use something called the Recursion Theorem, which states:

Recursion Theorem: Suppose that X is a set, a is an element of X, and f:X->X is a function. Then there exists a unique function F:N->X (where N is the set of natural numbers, including 0) such that: (i) F(0)=a; and (ii) F(n+1) = f(F(n)).


Here, you can let X be the set of all natural numbers, a=2, and f:N->N
be the function that sends x to the smallest prime that is strictly larger than x. This function is in fact computable (there is a Turing machine that will compute the value of f given any input; this was used by Goedel's in his theorem, and the idea is that all you have to do is start searching starting at n+1, until you "hit" a prime; and you know that there will be one at most at n!+1).

Then the Recursion Theorem guarantees that there is a function F with the property that F(0)=2, and F(n+1) = the smallest prime larger than F(n).

It is now easy to verify that F is one-to-one, and that it is onto the set of primes, guaranteeing the existence of a bijection.

The fact that f is computable tells you that the bijection is in fact computable; but the existence of a bijection for any infinite subset of the natural numbers (whether or not it is computable) is guarantees by the Recursion Theorem.

--
Arturo Magidin

[Arturo Magidin]

On Sunday, September 18, 2016 at 4:18:07 PM UTC-5, Lax Clarke wrote:

> Essentially, under what conditions can we say "such a function exists" even when we do not have closed form formula for the function?

Also: note that the definition of "function" does NOT require a closed form formula; it just requires that for each valid input there be one and only one output. In fact, the number of functions form the natural numbers to the natural numbers far exceeds the number of closed form formulas (there are as many functions as there are real numbers, but there are only as many closed formulas using a finite, or even countable, alphabet as there are natural numbers).

If you want to stick to formulas for which there is, if not a closed form formula, at least a "finitistic definition" (that is, you can program a Turing machine to give you the output, given any input, at least in principle provided you have enough time), then you get what are called the "Computable functions". It is perfectly logically consistent to work in a universe in which *everything* is computable (this is Goedel's "Constructible universe"); that still does not mean you can actually *find* a formula for a given function: just that one exists. But mathematical statements are not about my particular failures, but about logical existence.

In any case, a bijection from the natural numbers to the primes is definitely computable: there is an algorithm for finding the value of f(n) for any natural number n.

--
Arturo Magidin

[Ross A. Finlayson]

Yeah, it's pretty clear that such functions
exist, where if you actually provide some
closed formula for the n'th prime, you
get a Clay Prize.

[Peter Percival]

Arturo Magidin wrote:
> On Sunday, September 18, 2016 at 4:18:07 PM UTC-5, Lax Clarke wrote:
>
>> Essentially, under what conditions can we say "such a function
>> exists" even when we do not have closed form formula for the
>> function?
>
> Also: note that the definition of "function" does NOT require a
> closed form formula; it just requires that for each valid input there
> be one and only one output. In fact, the number of functions form the
> natural numbers to the natural numbers far exceeds the number of
> closed form formulas (there are as many functions as there are real
> numbers, but there are only as many closed formulas using a finite,
> or even countable, alphabet as there are natural numbers).
>
> If you want to stick to formulas for which there is, if not a closed
> form formula, at least a "finitistic definition" (that is, you can
> program a Turing machine to give you the output, given any input, at
> least in principle provided you have enough time), then you get what
> are called the "Computable functions". It is perfectly logically
> consistent to work in a universe in which *everything* is computable
> (this is Goedel's "Constructible universe"

Could you say why a univese in which everything is Turing computable is
the same as Gödel's constructible universe?

> ); that still does not mean
> you can actually *find* a formula for a given function: just that one
> exists. But mathematical statements are not about my particular
> failures, but about logical existence.
>
> In any case, a bijection from the natural numbers to the primes is
> definitely computable: there is an algorithm for finding the value of
> f(n) for any natural number n.
>


--

Do, as a concession to my poor wits, Lord Darlington, just explain
to me what you really mean.
I think I had better not, Duchess. Nowadays to be intelligible is
to be found out. -- Oscar Wilde, Lady Windermere's Fan

[Arturo Magidin]

On Monday, September 19, 2016 at 6:18:28 AM UTC-5, Peter Percival wrote:
> Arturo Magidin wrote:
> > On Sunday, September 18, 2016 at 4:18:07 PM UTC-5, Lax Clarke wrote:
> >
> >> Essentially, under what conditions can we say "such a function
> >> exists" even when we do not have closed form formula for the
> >> function?
> >
> > Also: note that the definition of "function" does NOT require a
> > closed form formula; it just requires that for each valid input there
> > be one and only one output. In fact, the number of functions form the
> > natural numbers to the natural numbers far exceeds the number of
> > closed form formulas (there are as many functions as there are real
> > numbers, but there are only as many closed formulas using a finite,
> > or even countable, alphabet as there are natural numbers).
> >
> > If you want to stick to formulas for which there is, if not a closed
> > form formula, at least a "finitistic definition" (that is, you can
> > program a Turing machine to give you the output, given any input, at
> > least in principle provided you have enough time), then you get what
> > are called the "Computable functions". It is perfectly logically
> > consistent to work in a universe in which *everything* is computable
> > (this is Goedel's "Constructible universe"
>
> Could you say why a univese in which everything is Turing computable is
> the same as Gödel's constructible universe?

My understanding may be incorrect, but my understanding is that Goedel's constructible universe is based on his notion of generalized recursive functions as being those that are "constructible", and it's known that "Turing-computable" is equivalent to "definable via generalized recursive function" is equivalent to "lambda definable".

But V=C is not something I've ever studied, so I guess I could be wrong.

--
Arturo Magidin

[mitch]

I believe that the assumption of consistency
makes the constructible universe and inner
model.

One of the Goedel functions constructs a
membership relation relative to two given
sets. This definable membership relation
takes one argument from the first set and
takes the second argument from the second
set and admits it into the defined relation
if the first argument is an element of the
second argument relative to the assumed
consistency assumption.

Would this not then suggest that the
assumed model would have to have a Turing
computable membership function in order
for the defined membership relations to
be Turing computable?

mitch

[Dick]

> > Could you say why a univese in which everything is Turing computable is
> > the same as Gödel's constructible universe?
>
> My understanding may be incorrect, but my understanding is that Goedel's constructible universe is based on his notion of generalized recursive functions as being those that are "constructible", and it's known that "Turing-computable" is equivalent to "definable via generalized recursive function" is equivalent to "lambda definable".
>
> But V=C is not something I've ever studied, so I guess I could be wrong.
>
> --
> Arturo Magidin

"Turing computable" suggests "computable by a simple Turing Machine". Goedel's Constructable Universe is far more than this. It includes everything computable by any Turing Machine, simple or not. This includes (I believe) all logical functions.
A theorem of Lowenstein states that any system of first order logic statements has a countable model (if it has a model are all). The axioms of set theory are all first order, so set theory has a countable model, I believe that Gödel's constructable universe is an example of such a model. As such, it includes everything in conventional set theory, including uncountable set (Skolem's Paradox) and Proper Classes. It is surprising that a countable set can include a Proper Class!
Dick

[Vinicius Claudino Ferraz]

There is a bijection.
It is obvious.
We don't need to construct the infinity.
No need for draw down infinitely many lines.
How can we just say?
for all natural n, exists is a prime p(n).
for all prime p, exists a natural n(p).

suppose on the contrary
<<
exists a natural n, forall f, f(n) is not prime.
exists a prime p, forall g, g(p) is not natural.
>>

Did everybody laugh at the contradictions?

Vinicius
twitter.com/mathspiritual

[Vinicius Claudino Ferraz]

f, g \in P^N = {h : N --> P}
f o g = g o f = Id
Yes. There are f, g. I believe in infinity.

O infinito é realmente
Um dos deuses mais lindos

https://www.letras.mus.br/legiao-urbana/46972/

[Chris Jacobs]

Vinicius Claudino Ferraz <borala...@gmail.com> writes:

>There is a bijection.
>It is obvious.
>We don't need to construct the infinity.
>No need for draw down infinitely many lines.
>How can we just say?
>for all natural n, exists is a prime p(n).
>for all prime p, exists a natural n(p).

If you just say that I will just say:
e.g. for all natural n, p(n) := 2
e.g. for all prime p, n(p) := 2

evidently you miss something.

>suppose on the contrary
><<
>exists a natural n, forall f, f(n) is not prime.
>exists a prime p, forall g, g(p) is not natural.
>>>

What is f? What is g?

>Did everybody laugh at the contradictions?

hihihi

>Vinicius
>twitter.com/mathspiritual=20

>Em domingo, 18 de setembro de 2016 18:18:07 UTC-3, Lax Clarke escreveu:

>> Hi,=20
>>=20
>> I was wondering about proving that there is a bijection from natural numb=
>ers to set of prime numbers. It is "obvious" that there is an n-th prime =
>number, but is that sufficient to prove that prime number set can be consid=
>ered in bijection with natural numbers? Or do we need to "construct" this =
>process (or closed for formula) of getting the n-th prime number? =20
>>=20
>> Essentially, under what conditions can we say "such a function exists" ev=

[Vinicius Claudino Ferraz]

errata: f \in P^N
g \in N^P

[mitch]

There is no reason to think that the constructible
universe is countable.

It is true that the definable power set of an
infinite set has the same cardinality as the
given infinite set when the axiom of choice
holds. This is in Kunen. But, the constructible
universe is formulated in relation to a given
model which represents the consistency assumption.
So, if two sets of the given model are such that
an uncountable infinity of membership relations
hold between respective pairs of their elements,
the definable membership relation obtained
from the pertinent Goedel function would be
uncountable. Hence, the constructible universe
would be uncountable.

That the constructible universe depends upon a
given model may be seen, for example, from Hamkins'
work in the links,

http://jdh.hamkins.org/every-model-embeds-into-own-constructible-universe/

http://arxiv.org/pdf/1207.0963v3.pdf

To the extent that the constructible universe is
"singular", the given model would be the one
"true model". But, one may only know that there
is a "true model" if set theory is consistent.
So, before you can talk about the countability
of *the* constructible universe you must know
which model is the actual V.

[Ross A. Finlayson]

The quadratic y=x^2 has always seemed of
note, because the lines connecting integer
points of the curve, through integer points
of the axis, are composites (in y), the other
integer points of the axis: primes.

[Vinicius Claudino Ferraz]

Hell.Oh, Jacobs

Theorem:

\exists f \in P^N, \exists g \in N^P, such that f o g = Id and f, g are bijections.

f is surjective: \forall p \in P, \exists n \in N ; f(n) = p
g is surjective: \forall n \in N, \exists p \in P ; g(p) = n
f is injective: f(n_1) = f(n_2) ==> n_1 = n_2
g is injective: g(p_1) = g(p_2) ==> p_1 = p_2

NOT-Theorem:

\forall f \in P^N, \forall g \in N^P, IF f o g = Id THEN (1) OR (2) OR (3) OR (4).

(1) f isn't surjective: \exists p \in P, \forall n \in N ; f(n) <> p
(2) g isn't surjective: \exists n \in N, \forall p \in P ; g(p) <> n
(3) f isn't injective: f(n_1) = f(n_2) and n_1 <> n_2
(4) g isnt' injective: g(p_1) = g(p_2) and p_1 <> p_2

Como queríamos afirmar ontem.

It has appeared Chomsky's languages at my "fundamentos de teoria de computação".
Every language comes from God. Everything speaks divine language Lambda.

Vinicius
twitter.com/mathspiritual

1

[Pubkeybreaker]

Since the primes form an infinite subset of the integers, they form a countably
infinite set. Now, the Cantor-Bernstein thm shows that they are in 1-1
correspondence with Z (all countably infinite sets can be placed in 1-1
correspondence with each other)