
Re: Effective method of getting a onetoone onto function from a onetoone 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 onetoone > function. Is there an effective (maybe even "canonical") method of > defining g:X>N in terms of f so that g is onetoone 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 email: gayleard /at/ eircom.net School of Mathematics, Trinity College, Dublin 2, Ireland

