The Math Forum

Search All of the Math Forum:

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

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

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

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: 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
  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/
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]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.