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 ]
 Sandy Posts: 51 Registered: 7/9/13
Re: Effective method of getting a one-to-one onto function from a
one-to-one function?

Posted: Sep 13, 2013 2:41 PM

Timothy Murphy wrote:
> 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.

That's a good point!

>> 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?)

Yes.

> 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?

Thank you.

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