Sinn (über REGELMENGE) induktiv definierter Menge ?

15/07/2008 - 21:44 von Ernst Baumann | Report spam
Hallo allerseits,
Gebilde wie Terme und Formeln _muss_ man als induktive Mengen (mit
Hilfe einer Regelmenge) bilden, wenn man dies korrekt machen will.
So sieht es zumindest Prof. Kindler (siehe (Kapitel über induktive
Definitionen)

http://wwwcs.uni-paderborn.de/cs/ki.../Semantik/
Auf dieser Website befindet sich u.a. das zugehörige Skript




Beispiel einer (über eine Regelmenge) induktiv definierter Menge

Die Regeln R1, R2, R3
R1:
{}

3

R2:
{}

5

R3:
r, s sind natürliche Zahlen (>=1) mit r!=s
{r , s}

r + s


D0 := {} gilt per Definition
// 3 folgt laut R1 aus {}, 5 folgt laut R2 aus {}
D1 = {3 , 5}
// 3 folgt laut R1 aus {}, 5 folgt laut R2 aus {}
// und 8 folgt laur R3 aus 5 und 3
D2 := {3 , 5 , 8}
// 3 folgt laut R1 aus {}, 5 folgt laut R2 aus {}
// und 8 folgt laut R3 aus 5 und 3
// 11 folgt laut R3 aus 8 und 3, 13 folgt laut R3 aus 8 und 5
D3 =: {3 , 5 , 8 , 11 , 13}
...

Damit hat man eine sauber definierte Menge I(R)
(Def1)
I(R) := D0 u D1 u D2 u ...
also für dieses Beispiel:
I(R) = {3 , 5 , 8 , 11 , 13, ...}

So weit, so gut, aber:
Warum wird für die Definition dieser ganze Aufwand über eine
_Regelmenge_ gemacht?

Warum macht man nicht folgendes _ohne Regelmenge_:
(e bedeutet Element von)

Es sei A eine Teilmenege von N = Menge der natürlichen Zahlen.
Dann wird definiert:

(F1):
n e A :<==> es existieren natürliche Zahlen n1, n2 mit n1!=n2
und n1>=1 und n2>=1 und
n1 e A und n2 e A, so dass gilt: n = n1 + n2
oder n = 3
oder n = 5

Dies wird nicht gemacht, weil die Menge A nicht eindeutig definiert
ist.
Denn A = {3, 4, 5, 6, 7, ...} würde neben obig definiertem I(R) auch
die Formel (F1) erfüllen

Aber man könnte folgendes definieren:
(Def2)
E = Durchschnitt aller Mengen, die Teilmenge von N sind und (F1)
erfüllen.

Fragen:
1)
Warum wird diese Definition (Def1) nicht gemacht?
Ist diese Definition nicht korrekt?
2)
Sind (Def1) und (Def2) gleichwertig?

mfg
Ernst
 

Lesen sie die antworten

#1 Marc Olschok
15/07/2008 - 22:29 | Warnen spam
Ernst Baumann wrote:
Hallo allerseits,
Gebilde wie Terme und Formeln _muss_ man als induktive Mengen (mit
Hilfe einer Regelmenge) bilden, wenn man dies korrekt machen will.
So sieht es zumindest Prof. Kindler (siehe (Kapitel über induktive
Definitionen)

http://wwwcs.uni-paderborn.de/cs/ki.../Semantik/
Auf dieser Website befindet sich u.a. das zugehörige Skript




Beispiel einer (über eine Regelmenge) induktiv definierter Menge

Die Regeln R1, R2, R3
R1:
{}

3

R2:
{}

5

R3:
r, s sind natürliche Zahlen (>=1) mit r!=s
{r , s}

r + s


D0 := {} gilt per Definition
// 3 folgt laut R1 aus {}, 5 folgt laut R2 aus {}
D1 = {3 , 5}
// 3 folgt laut R1 aus {}, 5 folgt laut R2 aus {}
// und 8 folgt laur R3 aus 5 und 3
D2 := {3 , 5 , 8}
// 3 folgt laut R1 aus {}, 5 folgt laut R2 aus {}
// und 8 folgt laut R3 aus 5 und 3
// 11 folgt laut R3 aus 8 und 3, 13 folgt laut R3 aus 8 und 5
D3 =: {3 , 5 , 8 , 11 , 13}
...

Damit hat man eine sauber definierte Menge I(R)
(Def1)
I(R) := D0 u D1 u D2 u ...
also für dieses Beispiel:
I(R) = {3 , 5 , 8 , 11 , 13, ...}

So weit, so gut, aber:
Warum wird für die Definition dieser ganze Aufwand über eine
_Regelmenge_ gemacht?



Ich vermute einmal, dass die obige Menge als einfaches Beispiel
für eine durch Regeln definierte Menge dienen soll.

Im Zusammenhang mit Termen und Formeln ist zuweilen so, dass man
Eigenschaften von Termen oder Formeln durch strukturelle Induktion
beweisen kann. Da werden die verwendeten Regeln explizit benutzt.


Warum macht man nicht folgendes _ohne Regelmenge_:
(e bedeutet Element von)

Es sei A eine Teilmenege von N = Menge der natürlichen Zahlen.
Dann wird definiert:

(F1):
n e A :<==> es existieren natürliche Zahlen n1, n2 mit n1!=n2
und n1>=1 und n2>=1 und
n1 e A und n2 e A, so dass gilt: n = n1 + n2
oder n = 3
oder n = 5

Dies wird nicht gemacht, weil die Menge A nicht eindeutig definiert
ist.
Denn A = {3, 4, 5, 6, 7, ...} würde neben obig definiertem I(R) auch
die Formel (F1) erfüllen

Aber man könnte folgendes definieren:
(Def2)
E = Durchschnitt aller Mengen, die Teilmenge von N sind und (F1)
erfüllen.

Fragen:
1)
Warum wird diese Definition (Def1) nicht gemacht?
Ist diese Definition nicht korrekt?
2)
Sind (Def1) und (Def2) gleichwertig?



Ja, falls ich mich jetzt nicht verguckt habe.
Beides definiert die Menge 3N + 5N = { 3a + 5b | a,b in N }.
Sehr viel einfacher ist natürlich auch (Def2) nicht; letztlich wurden
die einzelnen Regeln von (Def1) in (F1) eingebaut.

Marc

Ähnliche fragen