1 Zum grammatischen Rahmen
Theorem 1-1. AUSL ist eine Funktion auf AUS
(i) Dom(AUSL) = AUS und
(ii) Fur alle μ ∈ AUS, k, l ∈ N: Wenn (μ, k), (μ, l) ∈ AUSL, dann k = l.
Beweis: (i) ergibt sich direkt aus Definition 1-3 und Definition 1-4. Zu (ii): Seien μ ∈
AUS, k, l ∈ N mit (μ, k), (μ, l) ∈ AUSL. Dann gibt es {μ0, ..., μk-1} ⊆ GAUS mit μ =
rμ0...μk-Γ und es gibt {μ'0, ., μ'l-1} ⊆ GAUS mit μ = rμ'0...μ'l-1^l. Nach Postulat 1-2-(i)
ist dann k = l. ■
Theorem 1-2. Ausdrucke sind Verkettungen von Grundausdrucken
Wenn μ ∈ AUS, dann gibt es {μo, ., μAUSL(μ)-ι} ⊆ GAUS, so dass μ = rμo. μAUSL(μ)-ιπ .
Beweis: Ergibt sich direkt aus Definition 1-3 und Definition 1-4. ■
Theorem 1-3. Identifizierung von Gliedern einer Ausdrucksverkettung
Wenn k ∈ N∖{0} und fur alle i < k: μi ∈ AUS, dann gilt fur alle s < ∑kkf10 AUSL(μj):
(i) s < AUSL(μ0)
oder
(ii) AUSL(μo) ≤ s und es gibt l, r, so dass
a) 0 < l < k und r < AUSL(μl) und s = (∑1f= 0 AUSL(μn))+r und
b) Fur alle l', r': Wenn 0 < l' < k und r' < AUSL(μf) und s =
(∑n,L10 AUSL(μn))+r', dann l' = l und r' = r.
Beweis: Sei k ∈ N∖{0} und gelte fur alle i < k: μi ∈ AUS. Sei nun s < ∑k 10 AUSL(μj).
Dann ist s < AUSL(μ0) oder AUSL(μ0) ≤ s. Im ersten Fall gilt die Behauptung. Sei nun
AUSL(μ0) ≤ s. Dann ist 1 < k, denn sonst ware 1 = k und somit AUSL(μ0) =
∑ 0 AUSL(μ) > s. Also gibt es wenigstens ein i, namlich 1, so dass 0 < i < k und
∑n 1 0 AUSL(μn) ≤ s. Sei nun l = max({i | 0 < i < k und ∑n 1 0 AUSL(μn) ≤ s}). Dann ist 0
< l < k und ∑]f1 0 AUSL(μn) ≤ s. Dann gibt es ein r, so dass (∑n 1 0 AUSL(μn))+r = s.
Ware nun AUSL(μl) ≤ r. Nun ist l < k-1 oder l = k-1. Angenommen l < k-1. Dann ist l+1
< k. Dann ware ∑^ = 0 ALSL(μ.) = (∑f1 0 AUSL(μn))+AUSL(μl) ≤ (∑f1 0 AUSL(μn))+r
= s, was der Maximalitat von l widerspricht. Angenommen l = k-1. Dann ware l-1 = k-2
und somit ∑k^=10 AUSL(μn) = (∑k^=20 AUSL(μn))+AUSL(μk-ι) ≤ (∑k 2() AUSL(μn))+r = s,
was der Annahme uber s widerspricht. Also fuhrt die Annahme, dass AUSL(μl) ≤ r in