i
i
main”—2013/4/10—15:19—page201—#213
i
i
i
i
i
i
Presburger-Arithmetik 201
Beweis des Krohn-Rhodes-Theorems 7.30. Sei D
M
die kleinst e Menge von endlichen
Monoiden, welche
U
2
und alle einfachen Gruppendivisoren von M enthält, und w el-
che abgeschlossen ist unter Divisoren und Kranzprodukten. Nach Lemma 7.26 und
Lemma 7.29 genügt es,
M ∈D
M
zu zeigen. Sei k(M) die Anzahl der konventionel-
len Elemente von
M. Der B eweis ist mit Induktion nach k(M).Wennk(M) = 0 ist,
dann können wir
M nach Satz 7.32 in ein Kranzprodukt von U
n
und einer Gruppe G
zerlegen. Nach Satz 7.27 und Lemma 7.28 ist U
n
ein Divisor eines Kranzprodukts von
Monoiden
U
2
, und nach Satz 7.31 ist G ein Divisor von Kranzprodukten einfacher Un-
tergruppen (wir können
G immer weiter zerlegen, bis keine der auftretenden Gruppen
einen nichttrivialen Normalteiler besitzt). Also gilt
U
n
,G ∈D
M
und damit M ∈D
M
.
Wir nehmen nun an, dass
M mindestens ein konventionelles Element besitzt. Sei
A eine minimale Erzeugermenge von M. Dann gibt es einen konventionellen Erzeuger
c A.SeiN das von A \{c} erzeugte Untermonoid von M. Aus der Minimalität von
A folgt c ∈ N. Nach Lemma 7.33 gilt k(N
#
) = k(N) < k(M). Aus Lemma 7.36 folgt
mit Induktion
N
#
∈D
N
⊆D
M
. Lemma 7.35 zeigt k(M
c
)<k(M),worausM
c
D
M
c
⊆D
M
mit Induktion folgt. Schließlich folgt M ∈D
M
a u s S a t z 7. 3 7, L e m m a 7. 2 8
und Satz 7.27. Man beachte, dass
U
1
U
2
gilt.
7.6 Presburger-Arithmetik
Der Gödel’sche Unvollständigkeitssatz sagt, dass es für gegebene arithmetische F or-
meln über den natürlichen Zahlen im Allgemeinen unentscheidbar ist, ob sie wahr
sind. In diesem Abschnitt wollen wir zeigen, dass man von jeder arithmetischen For-
mel über
N, in der nur Additionen und keine Multiplikationen vorkommen, entschei-
den kann, ob sie wahr ist. Etwas genauer handelt es sich bei der Presburger-Arithmetik
nach Moj˙zesz Presburger (1904–1943) um die wahren Aussagen, welche mit Logik ers-
ter Stufe (engl. fir st-order logic
FO) über d en natürlichen Zahlen mit der Addition aus-
gedrückt werden können [69].
Die Syntax der hier betrachteten Logik
FO[N, +] ist induktiv wie folgt definiert:
–FürVariablen
x,y, z und Konstanten n N gehören die Formeln x = n und
x +y = z zu FO[N, +].
–Wenn
ϕ und ψ in FO[N, +] sind, dann gehören auch ϕψ und ¬ϕ zu FO[N, +].
–Wenn
ϕ in FO[N, +] ist, dann gehört auch zu FO[N, +].
Wie üblich verwenden wir die abkürzenden Schreibweisen
ϕ ψ für ¬(¬ϕ ∨¬ψ)
sowie für ¬∃x ¬ϕ. Eine Variable x ist frei in ϕ, wenn sie nicht im Gültigkeits-
bereich eines Quantors steht; um später unnötige Fallunterscheidungen zu vermei-
den, fordern wir hier nicht, dass
x in ϕ vorkommt . Wir schreiben ϕ(x
1
,...,x
n
),
um anzudeuten, dass
x
1
,...,x
n
die freien Variablen von ϕ sind. Ein Satz ist eine
Formel, in der keine freien Variablen vork ommen. Der Wahrheitsw ert eines Satzes ist
eindeutig bestimmt. Die Menge der wahren Sätze aus
FO[N, +] bildet die Presburger-

Get Diskrete algebraische Methoden now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.