Sign in to follow this  
ReubenESTD

Gödelization - help needed.

Recommended Posts

ReubenESTD    96
Formula:
[code]
n x?i x?1 x?2 x?n
? p = p p ... p
i=1 i 1 2 n[/code]

[size="2"][i]Where:

n = the nth number in a sequence

x = a number in the sequence

p = a prime number[/i][/size]



G[font="arial, sans-serif"][size="2"][i]ö[/i][/size][/font]delization (as far as I understand) states that if you pick any natural number (x) then there is exactly one sequence of prime numbers (p) whose product (of (n) prime numbers) = x. If there are (n) numbers in the sequence, let every number be denoted by (x?1 x?2 ... x?n).

[b]I am having trouble fully grasping this and I think it would help if someone could give me an example calculation using this formula. [/b][b]
[/b]

Share this post


Link to post
Share on other sites
I've not heard of [color=#1C2837][size=2]G[font=arial, sans-serif][size=2][i]ö[/i][/size][/font]delization, but that just looks to be the prime factorisation of an integer for which it is quite easy to prove that a) it exists, and b) that it is unique.[/size][/color]
[color=#1C2837][size=2]
[/size][/color]
[color=#1C2837][size=2]An intuitive proof for existance would be:

let N be a number, either N is prime or it is not prime.
If it is not prime then there must exist a prime P and a possibly non-prime M (otherwise N would be prime).[/size][/color]
[color=#1C2837][size=2]In the same way, repeat with M instead, and eventually you either get a prime number, or 1.

from which it is easy to construct a formal inductive proof.[/size][/color]
[color=#1C2837][size=2]
[/size][/color]
[color=#1C2837][size=2]Proof of uniqueness is a little bit harder, a sketch proof would be:

Let N be the smallest integer expressible as the product of two minimal; non-identical sets of primes s1,s2..sn q1,q1...qm[/size][/color]
[color=#1C2837][size=2]as N is the smallest such number, then s1, and s2...sn, must have unique factorisations as they are smaller than N.[/size][/color]
[color=#1C2837][size=2]p1 then, must either divide s1, or s2...sn (or both, not important) and as all are prime, si = qj for some i,j. By removing si,qj from the two non-equal factorisations we get two smaller, equal numbers. as they are smaller than N, by assumption they have unique factorisations and so the two factorisations cannot be different.[/size][/color]

Share this post


Link to post
Share on other sites
quasar3d    814
You probably know (and as luca-deltadesco explained) that any integer can be factored into a unique prime factorization, and G[font="sans-serif"][size="2"]ö[/size][/font]delization is a trick that uses this fact to encode a whole sequence of numbers into a single integer by taking the product of the first prime raised to the power of the first element of your sequence, the second prime raised to the power of the second element, and so on. This gives you a single integer that encodes your whole sequence.

for example, the sequence of the first 4 squares (1,4,9,16) can be encoded as

2^1 * 3^4 * 5^9 * 7^16 = 10515106938037816406250

Share this post


Link to post
Share on other sites
ReubenESTD    96
[quote name='luca-deltodesco' timestamp='1306759889' post='4817483']
I've not heard of [color="#1C2837"][size="2"]G[font="arial, sans-serif"][size="2"][i]ö[/i][/size][/font]delization, but that just looks to be the prime factorisation of an integer for which it is quite easy to prove that a) it exists, and b) that it is unique.[/size][/color]
[color="#1C2837"] [/color]
[color="#1C2837"][size="2"]An intuitive proof for existance would be:

let N be a number, either N is prime or it is not prime.
If it is not prime then there must exist a prime P and a possibly non-prime M (otherwise N would be prime).[/size][/color]
[color="#1C2837"][size="2"]In the same way, repeat with M instead, and eventually you either get a prime number, or 1.

from which it is easy to construct a formal inductive proof.[/size][/color]
[color="#1C2837"] [/color]
[color="#1C2837"][size="2"]Proof of uniqueness is a little bit harder, a sketch proof would be:

Let N be the smallest integer expressible as the product of two minimal; non-identical sets of primes s1,s2..sn q1,q1...qm[/size][/color]
[color="#1C2837"][size="2"]as N is the smallest such number, then s1, and s2...sn, must have unique factorisations as they are smaller than N.[/size][/color]
[color="#1C2837"][size="2"]p1 then, must either divide s1, or s2...sn (or both, not important) and as all are prime, si = qj for some i,j. By removing si,qj from the two non-equal factorisations we get two smaller, equal numbers. as they are smaller than N, by assumption they have unique factorisations and so the two factorisations cannot be different.[/size][/color]
[/quote]


[quote name='quasar3d' timestamp='1306787930' post='4817652']
You probably know (and as luca-deltadesco explained) that any integer can be factored into a unique prime factorization, and G[font="sans-serif"][size="2"]ö[/size][/font]delization is a trick that uses this fact to encode a whole sequence of numbers into a single integer by taking the product of the first prime raised to the power of the first element of your sequence, the second prime raised to the power of the second element, and so on. This gives you a single integer that encodes your whole sequence.

for example, the sequence of the first 4 squares (1,4,9,16) can be encoded as

2^1 * 3^4 * 5^9 * 7^16 = 10515106938037816406250
[/quote]


Thanks both of you I understand perfectly now, big numbers though! I think I was just a little put off by all that complex-looking formula.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this