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

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

Advanced Search

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

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

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




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

[Privacy Policy] [Terms of Use]

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