Induktives Definieren

09.01.2014, 19:11

GroovyChuc

Induktives Definieren

Meine Frage:
Zuerstmal eine Definition aus meinem Skript zur näheren Definiion:
$\begin{eqnarray*} \textit{Es sei f: A$^n$ $\rightarrow$ A eine n-stellige Funktion(Operation). Dann sind die Abbildungen $\Gamma_f$ :$\mathcal{P}$(A) $\rightarrow$ $\mathcal{P}$(A) sowie $\Gamma^k_f$:$\mathcal{P}$(A)$\rightarrow$ $\mathcal{P}$(A) für alle k $\in$ $\mathbb{N}$ wie folgt definiert (für B $\subseteq$ A):} \end{eqnarray*}$
$\begin{eqnarray*} \Gamma^0_f(B)=_{def} B \end{eqnarray*}$
$\begin{eqnarray*} \Gamma^k_f(B)=_{def} \Gamma^{k-1}_f(B) ~\cup~ \{ f(a_1,\dots,a_n)~|~ a_1,\dots,a_n \in \Gamma^k_f(B)\} \end{eqnarray*}$
$\begin{eqnarray*} \textit{Die Menge $\Gamma_f$(B) heisst Abschluss von B unter f.} \end{eqnarray*}$

Jetzt gibt es dazu auch Beispiele:
Wenn wir die Operation inc : $\begin{eqnarray*} \mathbb{N} \rightarrow \mathbb{N} : n \rightarrow n + 1 \end{eqnarray*}$ betrachten, so gilt:
$\begin{eqnarray*} \Gamma^0_{inc}(\{0\}) = \{0\} \end{eqnarray*}$ Ist klar da so definiert.
$\begin{eqnarray*} \Gamma^1_{inc}(\{0\}) = \{0\} \cup \{1\} = \{0,1\} \end{eqnarray*}$ Diesen Schritt verstehe ich nicht mehr. Klar die $\begin{eqnarray*} \{0\} \end{eqnarray*}$ kommt durch $\begin{eqnarray*} \Gamma^{k-1}_f(B) \end{eqnarray*}$ , aber laut Definition(wenn ich das richtig verstanden habe) ist der Teil nach der $\begin{eqnarray*} \cup \end{eqnarray*}$ doch die Menge der Funktionen, so dass die Funktionswerte Element vom Vorgänger( $\begin{eqnarray*} \Gamma^{k-1}_f(B) \end{eqnarray*}$ ) sind. Aber da ist immer nur die $\begin{eqnarray*} \{0\} \end{eqnarray*}$ ein Element.
Beim Rest gilt das selbe. Den Teil vor der $\begin{eqnarray*} \cup \end{eqnarray*}$ verstehe ich, den danach nicht.
$\begin{eqnarray*} \Gamma^2_{inc}(\{0\}) = \{0,1\} \cup \{1,2\} = \{0,1,2\} \end{eqnarray*}$
$\begin{eqnarray*} \Gamma^3_{inc}(\{0\}) = \{0,1,2\} \cup \{1,2,3\} = \{0,1,2,3\}<br /> \vdots \end{eqnarray*}$
$\begin{eqnarray*} \Gamma^k_{inc}(\{0\}) = \{0,1,\dots,k\} \end{eqnarray*}$

Danke für jede Hilfe

Meine Ideen:
siehe oben $\begin{eqnarray*} \uparrow \end{eqnarray*}$

09.01.2014, 23:11

dastrian

Auf diesen Beitrag antworten »

RE: Induktives Definieren
Hallo Groovy!
Das ist ein bisschen kompliziert, aber nach ein paar Minuten nachdenken glaube ich, es schaut komplizierter aus, als es ist! smile

Zunächst mal: Diese Definition stimmt glaub ich so nicht:
$\begin{eqnarray*} \Gamma^k_f(B)=_{def} \Gamma^{k-1}_f(B) \cup \{ f(a_1,\dots,a_n) | a_1,\dots,a_n \in \Gamma^k_f(B)\} \end{eqnarray*}$
denn da wird $\begin{eqnarray*} \Gamma^k_f(B) \end{eqnarray*}$ durch etwas definiert, wo wieder am Ende $\begin{eqnarray*} \Gamma^k_f(B) \end{eqnarray*}$ vorkommt - das wäre schon fies. Gemeint ist wahrscheinlich
$\begin{eqnarray*} \Gamma^k_f(B)=_{def} \Gamma^{k-1}_f(B) \cup \{ f(a_1,\dots,a_n) | a_1,\dots, a_n \in \Gamma^{k-1}_f(B)\} \end{eqnarray*}$
Kann das sein?

Weiter wurde wohl vergessen, $\begin{eqnarray*} \Gamma_f \end{eqnarray*}$ zu definieren; Ich gehe mal von $\begin{eqnarray*} \Gamma_f = \bigcup_{k \in \mathbb{N}} \Gamma_f^{k} \end{eqnarray*}$ aus - stimmt's oder hab ich Recht? Big Laugh

Wenn das nun stimmt, dann täuschst du dich an folgender Stelle:

Zitat:

Wenn wir die Operation inc : $\begin{eqnarray*} \mathbb{N} \rightarrow \mathbb{N} : n \rightarrow n + 1 \end{eqnarray*}$ betrachten, so gilt:
$\begin{eqnarray*} \Gamma^0_{inc}(\{0\}) = \{0\} \end{eqnarray*}$ Ist klar da so definiert.
$\begin{eqnarray*} \Gamma^1_{inc}(\{0\}) = \{0\} \cup \{1\} = \{0,1\} \end{eqnarray*}$ Diesen Schritt verstehe ich nicht mehr. Klar die $\begin{eqnarray*} \{0\} \end{eqnarray*}$ kommt durch $\begin{eqnarray*} \Gamma^{k-1}_f(B) \end{eqnarray*}$ , aber laut Definition(wenn ich das richtig verstanden habe) ist der Teil nach der $\begin{eqnarray*} \cup \end{eqnarray*}$ doch die Menge der Funktionen, so dass die Funktionswerte Element vom Vorgänger( $\begin{eqnarray*} \Gamma^{k-1}_f(B) \end{eqnarray*}$ ) sind.

Der Teil hinter $\begin{eqnarray*} \cup \end{eqnarray*}$ sind die Funktionswerte aller (Tupel von) Elementen aus $\begin{eqnarray*} \Gamma^{k-1}_f(B) \end{eqnarray*}$ , also im Fall von $\begin{eqnarray*} k=1 \end{eqnarray*}$ wie hier betrachtet man $\begin{eqnarray*} \Gamma^{k-1}_f(B) = \Gamma^0_f(B) = \{ 0 \} \end{eqnarray*}$ und davon die fFunktionswerte, hier also $\begin{eqnarray*} f(0) = 1 \end{eqnarray*}$
Machen wir das gleiche am selben Beispiel für $\begin{eqnarray*} k=2 \end{eqnarray*}$ :

Zitat:

$\begin{eqnarray*} \Gamma^2_{inc}(\{0\}) = \{0,1\} \cup \{1,2\} = \{0,1,2\} \end{eqnarray*}$

Für den Teil hinter dem $\begin{eqnarray*} \cup \end{eqnarray*}$ betrachte wieder $\begin{eqnarray*} \Gamma^{k-1}_f(B) = \Gamma^1_f(B) = \{ 0, 1 \} \end{eqnarray*}$ und davon die Funktionswerte, also $\begin{eqnarray*} f(0) = 1 \end{eqnarray*}$ und $\begin{eqnarray*} f(1) = 2 \end{eqnarray*}$ .

Hoffe, es ist alles etwas klarer geworden! Die Masterfrage wäre dann noch, warum man $\begin{eqnarray*} \Gamma_f(B) \end{eqnarray*}$ den "Abschluss" von $\begin{eqnarray*} B \end{eqnarray*}$ unter $\begin{eqnarray*} f \end{eqnarray*}$ nennt. Augenzwinkern

10.01.2014, 14:28

GroovyChuc

Auf diesen Beitrag antworten »

Ok die Definition hat tatsächlich nicht gestimmt bzw. war nicht vollständig smile

War ein bisschen genervt zu dem Zeitpunkt.

Konnte es auf jeden Fall nachvollziehen und es ist auch logisch.

Wieso es Abschluss B unter $\begin{eqnarray*} f \end{eqnarray*}$ heisst?
Vielleicht, weil alle möglichen Werte für $\begin{eqnarray*} f \end{eqnarray*}$ berechnet werden und $\begin{eqnarray*} f \end{eqnarray*}$ sozusagen abgeschlossen ist?

Auf jeden Fall danke für deine Hilfe smile

11.01.2014, 07:16

dastrian

Auf diesen Beitrag antworten »

Hi! Freut mich, dass ich helfen konnte! Beim Abschluss weiß ich nicht, ob du das richtige meinst. Man könnte es anschaulich so erklären:
Für eine Teilmenge $\begin{eqnarray*} B \subset A \end{eqnarray*}$ ist $\begin{eqnarray*} \Gamma_f(B) \end{eqnarray*}$ die kleinste Menge, die $\begin{eqnarray*} B \end{eqnarray*}$ enthält und von $\begin{eqnarray*} f \end{eqnarray*}$ auf sich selbst abgebildet wird.

Dieses "kleinste" soll heißen, dass $\begin{eqnarray*} \Gamma_f(B) \end{eqnarray*}$ der Schnitt aller Mengen mit diesen beiden Eigenschaften ist, formal sei also
$\begin{eqnarray*} \Lambda_f(B) = \{ C \subset A : B \subset C \wedge f(c_1, \ldots, c_n) \in C ~ \forall c_k \in C \} \end{eqnarray*}$
die Menge aller Teilmengen $\begin{eqnarray*} C \end{eqnarray*}$ von $\begin{eqnarray*} A \end{eqnarray*}$ , die die folgenden beiden Eigenschaften haben:
1. $\begin{eqnarray*} B \end{eqnarray*}$ ist eine Teilmenge von $\begin{eqnarray*} C \end{eqnarray*}$ und
2. Jedes Tupel aus Elementen von $\begin{eqnarray*} C \end{eqnarray*}$ wird von $\begin{eqnarray*} f \end{eqnarray*}$ auf ein Element abgebildet, welches ebenfalls in $\begin{eqnarray*} C \end{eqnarray*}$ liegt

Dann ist $\begin{eqnarray*} \Gamma_f(B) = \bigcap_{C \in \Lambda_f(B)} C \end{eqnarray*}$

Man kann sich das mit folgender Überlegung ganz gut klarmachen: Falls $\begin{eqnarray*} B \end{eqnarray*}$ selbst die Eigenschaften hat, dass jedes Tupel aus Elementen in $\begin{eqnarray*} B \end{eqnarray*}$ von $\begin{eqnarray*} f \end{eqnarray*}$ wieder auf ein Element von $\begin{eqnarray*} B \end{eqnarray*}$ abgebildet wird (also $\begin{eqnarray*} f(b_1, \ldots, b_n) \in B \end{eqnarray*}$ für $\begin{eqnarray*} b_k \in B \end{eqnarray*}$ ), dann ist nach Konstruktion
$\begin{eqnarray*} \Gamma_f^0(B) = \Gamma_f^1(B) = \Gamma_f^2(B) = \ldots = B \end{eqnarray*}$ und damit auch $\begin{eqnarray*} \Gamma_f(B) = B \end{eqnarray*}$
Falls aber $\begin{eqnarray*} B \end{eqnarray*}$ Elemente hat, deren Tupel nicht auf $\begin{eqnarray*} B \end{eqnarray*}$ ebgebildet werden, dann gewinnt man $\begin{eqnarray*} \Gamma_f^1(B) \end{eqnarray*}$ aus $\begin{eqnarray*} \Gamma_f^0(B) \end{eqnarray*}$ , indem man diese Bildelemente ergänzt. Das gleiche wird nun wieder auf $\begin{eqnarray*} \Gamma_f^1(B) \end{eqnarray*}$ angewandt, und so weiter unendlich lange, "bis" am Ende eine Menge herauskommt, deren Elementtupel auf Elemente der gleichen Menge abgebildet werden.

Neue Frage »

Antworten »

Induktives Definieren

Verwandte Themen