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?