Rekursion in Peano-Arithmetik

Eingedenk dieses Threads auf Stackoverflow.com schreibe ich, weil ich es grade schön finde, mal was kurzes zur Peano Arithmetik.

Die Peano-Arithmetik ist eine Theorie 1. Stufe, sie kennt als Zeichen beliebig viele Variablensymbole, die für Zahlen stehen können, Existenzquantoren, Allquantoren, alle logischen Junktoren (& und ¬ reichen aber aus), die Addition +, und die Multiplikation *, Zahlengleichheit =, Größer-relation <. Die Axiome der Peano Arithmetik schreib ich jetzt nicht hin, sie sind das, was man erwarten würde. Sie erlaubt per se keine Rekursion. Die Frage ist nun, wie drückt man aus, dass a eine Zehnerpotenz ist.

Dass a Potenz der Primzahl p ist, drückt man ganz leicht aus: Man sagt, jeder Teiler von a ist 1 oder teilbar durch p:

∀x((∃y(y*x=a & ¬(x=1))) → ∃z(p*z=x))

Aber wie drückt man aus, dass a Potenz einer beliebigen Zahl p ist, die nicht notwendig prim ist. Hier versagt dieses Verfahren.

Man kann aber etwas anderes probieren. Und zwar nutzt man den chinesischen Restsatz.

Definieren wir der Einfachheit erstmal ein paar Relationen:

D(x,y)=∃α(x*α=y) „x teilt y“
Prime(x)=¬x=1&∀α(D(α,x)→α=x|α=1) „x ist prim“
a=b mod c = ∃α a=c*α+b

Betrachten wir dann folgende Aussage:

∃y ∃k( b<k & „Es gibt ein y, sodass es ein k>b gibt, sodass…“
∀x(D(x,y)&Prime(x)→¬D(x*x,y)) & „Jede Primzahl teilt y höchstens einmal.“
∀x(D(x,y)&Prime(x)&∀z(Prime(z)&z<x→¬D(z,y))→(k=1 mod x))& „Ist x kleinster Primteiler von y, so ist k=1 mod x“
∀x∀z(D(x,y)&Prime(x)&D(z,y)&Prime(z)&z<x&∀t(z<t<x→¬(Prime(t)&D(t,y)))→ „Ist x Primteiler von y, und z nächstgrößerer Primteiler von y, dann…“
∀a<x ∀c<z ((k=a mod x)&(k=c mod z)-> a=c*10))& „…ist a<x, c<z, und k=a mod x, und k=c mod z, so ist a=c*10.“
∀x(D(x,y)&Prime(x)&∀z(Prime(z)&z>x→¬D(z,y))→(b<x & k=b mod x))) „Ist x größter Primteiler von y, so ist b<x und k=b mod x“

Wenn ich mich nicht ganz täusche, drückt das ungefähr sowas aus wie „es gibt eine Folge von Zahlen, die mit 1 beginnt, und sich in jedem Schritt verzehnfacht, und auf b endet“ – also „b ist Zehnerpotenz“.

Ok, auf diese Weise hab ich das zwar noch nie gesehen, aber so ähnliche Sachen (die meisten benutzen auch den chinesischen Restsatz, und auch eine Folge von teilerfremden Zahlen) hab ich schon öfters gesehen. Ich find sie aber immernoch schön, auch wenn ich inzwischen zu Advanced™ sein müsste.

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: