(erledigt)[Logik] KST Graph G_0 ~ Äquivalenzklassen von E_0

17.02.2013, 11:46	Grouser	Auf diesen Beitrag antworten »
(erledigt)[Logik] KST Graph G_0 ~ Äquivalenzklassen von E_0 Betrachte auf $\begin{eqnarray} 2^{\mathbb N} \end{eqnarray}$ die Äquivalenzrelation $\begin{eqnarray} x \mathbb E_0 y \Leftrightarrow \exists m \forall n \ge m: x(n) = y(n) \end{eqnarray}$ und fixiere eine Sequenz $\begin{eqnarray} \{s_n \in 2^{< \mathbb N} \| n \in \mathbb N\} \end{eqnarray}$ , so dass für alle $\begin{eqnarray} t \in 2^{< \mathbb N} \end{eqnarray}$ ein $\begin{eqnarray} n \in \mathbb N \end{eqnarray}$ existiert mit $\begin{eqnarray} s_n \restriction rng(t) = t \end{eqnarray}$ . Definiere schließlich den azyklischen Graphen $\begin{eqnarray} G_0 \end{eqnarray}$ durch $\begin{eqnarray} G_0 = \{ (s_n ^\frown (i) ^\frown x, s_n ^\frown (1-i) ^\frown x) \| n \in \mathbb N, i \in \{0,1\}, x \in 2^{\mathbb N} \} \end{eqnarray}$ . Nun ist die Behauptung, dass die Zusammenhangskomponenten von $\begin{eqnarray} G_0 \end{eqnarray}$ genau die Äquivalenzklassen von $\begin{eqnarray} \mathbb E_0 \end{eqnarray}$ sind. Klar ist, dass aus $\begin{eqnarray} x G_0 x_1, x_1 G_0 x_2, \ldots, x_n G_0 y \end{eqnarray}$ bereits $\begin{eqnarray} x \mathbb E_0 y \end{eqnarray}$ folgt. Umgekehrt allerdings scheine ich von völlig falscher Seite auf das Problem zu blicken. Beispielsweise weiß ich nicht, wie ich zeigen kann, dass $\begin{eqnarray} (0) ^\frown x \end{eqnarray}$ und $\begin{eqnarray} (1) ^\frown x \end{eqnarray}$ in einer Zusammenhangskomponente von $\begin{eqnarray} G_0 \end{eqnarray}$ liegen. Dieses Problem besteht allgemeiner, falls kein $\begin{eqnarray} s_n \end{eqnarray}$ das exakte Anfangsstück von $\begin{eqnarray} x \end{eqnarray}$ bis vor der letzten verschiedenwertigen Stelle zu $\begin{eqnarray} y \end{eqnarray}$ ist.
19.02.2013, 11:21	Grouser	Auf diesen Beitrag antworten »
Die Frage hat sich geklärt. Ich habe schlicht überlesen, dass zusätzlich $\begin{eqnarray} s_n \in 2^n \end{eqnarray}$ gefordert wird.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »