Drexel dragonThe Math ForumDonate to the Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » sci.math.* » sci.math

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

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]

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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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


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

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2015. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.