Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Effective method of getting a one-to-one onto function from a one-to-one
function?

Replies: 4   Last Post: Sep 15, 2013 8:23 AM

 Messages: [ Previous | Next ]
 Timothy Murphy Posts: 657 Registered: 12/18/07
Re: Effective method of getting a one-to-one onto function from a one-to-one function?
Posted: Sep 13, 2013 9:27 AM

Sandy wrote:

> Suppose X is a set with aleph_0 members and f:X-->N is a one-to-one
> function. Is there an effective (maybe even "canonical") method of
> defining g:X-->N in terms of f so that g is one-to-one and onto?

This is an interesting question.
But how do you know that X has cardinality aleph_0?
In effect this means you have a bijection between N and X,
either implicitly or explicitly.

> Background: X is a set of Turing machine programs and f is a Gödel
> numbering. What I want is an invertible Gödel numbering.

Can't you tell if a number is a Godel number?
(Ie do the Godel numbers form a recursive set?)
If so, can't you just go through 0,1,2 in N,
and for each number m determine if it is a Godel number g,
and if so map the number n of matched cases to g?

--
Timothy Murphy
e-mail: gayleard /at/ eircom.net
School of Mathematics, Trinity College, Dublin 2, Ireland

Date Subject Author
9/13/13 Sandy
9/13/13 Timothy Murphy
9/13/13 Sandy
9/14/13 William Elliot
9/15/13 Sandy