Beispiel diophantischer und rekursiv aufzählbar Menge

29.06.2016, 22:53

forbin

Beispiel diophantischer und rekursiv aufzählbar Menge

Hallo Leute,

ich lese mich gerade in rekursive Mengen ein bzw. das gehört zu unserem Thema.
Ich habe zwar die Definition verstanden, aber kann mir kein pasendes Beispiel bereitlegen.
Auch im Internet bin ich nicht fündig geworden.

Sei $\begin{eqnarray*} B=\{1,2,4,8\} \end{eqnarray*}$ .
Nun sei $\begin{eqnarray*} c_{1} = 2^{n},n\in\mathbb N^{0} \end{eqnarray*}$ die charakteristische Funktion.
Diese würde mir ja alle Elemente der Menge liefern, damit ist die Menge rekursiv.
Stimmt das?

30.06.2016, 09:41

HAL 9000

Auf diesen Beitrag antworten »

Offenbar haben wir verschiedene Vorstellungen, was unter der charakteristischen Funktion einer Menge zu verstehen ist. Nach meinem Verständnis ist das

$\begin{align*} 1_B(x) = \begin{cases} 1 &\;\mbox{für}\;x\in B\\ 0 &\;\mbox{für}\;x\not\in B\end{cases} \end{align*}$ ,

bisweilen auch Indikatorfunktion genannt.

Du meinst es wohl eher so, dass dein $\begin{align*} c_1(n) \end{align*}$ für $\begin{align*} n\in\mathbb{N}_0 \end{align*}$ die Elemente von $\begin{align*} B \end{align*}$ liefert, also $\begin{align*} B = c_1\left(\mathbb{N}_0\right) = \left\{ c_1(n) \bigm| n\in\mathbb{N}_0 \right\} \end{align*}$ ? In dem Fall hast du wohl bei der Angabe von $\begin{align*} B \end{align*}$ die "Pünktchen" vergessen, d.h., es soll wohl $\begin{align*} B = \{1, 2, 4, 8, \ldots \} \end{align*}$ sein statt der von dir angegebenen nur vierelementigen Menge? verwirrt

Was den Begriff einer rekursiven Menge betrifft, der sagt mir nichts. Eine kurze Recherche ergibt, dass es sowas wie rekursiv aufzählbare Mengen gibt, womöglich meinst du das?

01.07.2016, 11:53

forbin

Auf diesen Beitrag antworten »

Hm, ja es ist leider so, dass ich aus dem Skript ohne Beispiel nicht schlau werde. Rekursiv aufzählbar ist sicherlich richtig.
Aber lass uns vielleicht (nach Skript) einen Schritt zurückgehen zur diophantischen Menge.
Eine Menge A ist diophantisch <=> $\begin{eqnarray*} A=\{n\in\mathbb N^{0} | \exists x_{1}...x_{r} \in\mathbb N^{0}: f(x_{1}...x_{r},n)=0\} \end{eqnarray*}$

Nun suche ich ein Beispiel.
Sei $\begin{eqnarray*} A=\{1,2\} \end{eqnarray*}$ . Dazu finde ich ja ganz leicht $\begin{eqnarray*} (x-1)(x-2)=0 \end{eqnarray*}$
Nach meinem Verständnis ist A damit diophantisch?

01.07.2016, 13:27

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von forbin
Eine Menge A ist diophantisch <=> $\begin{eqnarray*} A=\{n\in\mathbb N^{0} | \exists x_{1}...x_{r} \in\mathbb N^{0}: f(x_{1}...x_{r},n)=0\} \end{eqnarray*}$

Wenn ich das richtig nachrecherchiert habe (da ich den Begriff "diophantische Menge" bisher nicht kannte), fehlt bei dir oben noch die wichtige Information, dass $\begin{align*} f \end{align*}$ ein Polynom mit ganzzahligen Koeffizienten sein muss.

Zitat:

Original von forbin
Sei $\begin{eqnarray*} A=\{1,2\} \end{eqnarray*}$ . Dazu finde ich ja ganz leicht $\begin{eqnarray*} (x-1)(x-2)=0 \end{eqnarray*}$
Nach meinem Verständnis ist A damit diophantisch?

Ja. Ähnlich klappt es bei allen endlichen Teilmengen $\begin{align*} A \end{align*}$ von $\begin{align*} \mathbb{N}_0 \end{align*}$ , interessant wird es also erst bei unendlichen $\begin{align*} A \end{align*}$ .

01.07.2016, 20:10

forbin

Auf diesen Beitrag antworten »

Edit: meine Antwort hier war Unsinn.

Sagen wir, A sei die Menge aller Potenzen von 2.
Ist diese diophantisch?
Ich meine, $\begin{eqnarray*} 2^{x} \end{eqnarray*}$ ist ja kein polynom.

01.07.2016, 21:25

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von forbin
Ist diese diophantisch?
Ich meine, $\begin{eqnarray*} 2^{x} \end{eqnarray*}$ ist ja kein polynom.

Richtig, aber das allein ist keine Begründung für die Nicht-Diophantizität dieser Menge. Z.B. ist die Komplementmenge davon durchaus diophantisch, wie man an folgender Darstellung sieht:

$\begin{align*} \mathbb{N}_0\setminus \left\{ 2^k \bigm| k\in \mathbb{N}_0\right\} = \left\{ n\in \mathbb{N}_0 \bigm| \exists r,s\in \mathbb{N}_0:\; n=(2r+3)s \right\} \end{align*}$ .

Neue Frage »

Antworten »

Beispiel diophantischer und rekursiv aufzählbar Menge

Verwandte Themen