First, this is not the same question as(adsbygoogle = window.adsbygoogle || []).push({});

https://www.physicsforums.com/threads/goedel-numbering-decoding.484898/

It concerns a different encoding procedure, hence a different decoding one.

My question concerns the argument in http://en.wikipedia.org/wiki/Gödel_numbering_for_sequences

for the existence of an effective decoding function β corresponding to the effective coding π for the Gödel number for sequences as given in that article : that is, given this procedure for generating the Gödel number from a sequence, and given the Godel number G of an unknown sequence (k_{1},...k_{n}), to prove the existence of β such that for all for all 0<i<n, β(G,i) =k_{i}.

Wikipedia leaves the " for all 0<i<n " implicit, so I will follow that abuse of notation as well:

If I understand that argument correctly:

First, we assume that we can choose m_{i}such that

[*] m_{i}>a_{i}

[**] all m_{i}are coprime to one another.

(This can even be done constructively.)

Then since we know that (k_{1},...k_{n}) exists, we know that a least solution x to the congruences

x ≡ a_{i}mod m_{i}

exists. Call it X.

We can construct a recursive function rem(a,b) so that rem(a,b)=(a mod b), so since we know X exists, we know that a procedure rem(X,m_{i}) = a_{i}exists.

OK, something rankles. Apparently I am not laying down the outline correctly , because it sounds slightly circular to me. Can anyone tell me what is wrong in my summary?

(It would be nice if there were a constructive proof.....)

(Also: the construction of the m_{i}so as to fulfill [*] and [**] would seem to require rather huge numbers: if [*] is fulfilled, then one just takes m = lcm(1,..., n-1) and m_{i}= (i+1)*m + 1. But the only way I can see to make sure that [*] is fulfilled is to set m = lcm(1,...n-1, G), where G is the given Gödel number of the sequence; this ends up with rather large m_{i}, so would it still be effective?)

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Gödel numbering for sequences

Loading...

Similar Threads - Gödel numbering sequences | Date |
---|---|

I An easy proof of Gödel's first incompleteness theorem? | Mar 6, 2018 |

I What is a sufficient piece of arithmetic for Gödel's first incompleteness theorem | Jun 1, 2016 |

Gödel’s theorem: larger than proof? | Oct 6, 2014 |

About Gödel incompleteness theorem | Aug 25, 2014 |

Is Gödel numbering a first or second order function? | May 10, 2014 |

**Physics Forums - The Fusion of Science and Community**