Folgen

04.11.2021, 20:04

Thomas007

Folgen

Hallo zusammen

Ich habe eine simple Frage: Können Folgen immer rekursiv ODER explizit definiert werden?
(Ich weiss, dass Folgen nicht immer explizit UND rekursiv definiert werden können.)

Danke für die Auskunft. smile

04.11.2021, 20:40

Steffen Bühler

Auf diesen Beitrag antworten »

RE: Folgen
Nein. Für die Folge der Primzahlen zum Beispiel geht beides nicht. Mehr auf Wiki.

Viele Grüße
Steffen

04.11.2021, 20:56

IfindU

Auf diesen Beitrag antworten »

RE: Folgen
@Steffen Ich würde das etwas relativieren. Zwischen man kann eine "einfache" Darstellung angeben und "es gibt eine explizite Darstellung" würde ich unterscheiden.

Die Folge der Primzahlen kann man z.B. rekursiv definieren über
$\begin{eqnarray*} a_1 = 2 \end{eqnarray*}$ und $\begin{eqnarray*} a_{n+1} = \min \{ p \in \mathbb P | p > a_n \} \end{eqnarray*}$ , wobei $\begin{eqnarray*} \mathbb P \end{eqnarray*}$ die Menge der Primzahlen ist.

So ist außerdem jede Folge explizit über Angabe ihrer Werte definiert, d.h. die Abbildung $\begin{eqnarray*} a \colon \mathbb N \to \mathbb P \end{eqnarray*}$ mit $\begin{eqnarray*} a_1 = 2; \; a_2 = 3\; \cdots \end{eqnarray*}$ . Die Folge ist explzit angebbar über $\begin{eqnarray*} a_n = \text{n-te Primzahl} \end{eqnarray*}$ und damit nicht rekursiv definiert. Wie schwer es nun ist die $\begin{eqnarray*} n \end{eqnarray*}$ -te Primzahl zu bestimmen, würde ich als irrelevant betrachten.

04.11.2021, 21:08

HAL 9000

Auf diesen Beitrag antworten »

RE: Folgen

Zitat:

Original von Steffen Bühler
Für die Folge der Primzahlen zum Beispiel geht beides nicht.

Da kann man auch anderer Ansicht sein: $\begin{eqnarray*} p_1:=2 \end{eqnarray*}$ und

$\begin{eqnarray*} p_n = \min\left\{ m\in\mathbb{N} \mid m>p_{n-1}~\wedge \forall t\in\mathbb{N}: \left(t\mid m\Rightarrow t=1\vee t=m\right)\right\} \end{eqnarray*}$

wäre eine passende rekursive Definition. Augenzwinkern

Deswegen ist die Frage von Thomas007 alles andere als simpel.

04.11.2021, 21:10

Steffen Bühler

Auf diesen Beitrag antworten »

RE: Folgen
Ich bin natürlich der Letzte, der Euch widerspricht. Doch halte ich es für eigenartig, das Bildungsgesetz der Primzahlfolge über die Primzahlmenge bzw. die Primzahldefinition zu definieren. Geht das mathematisch tatsächlich ohne Zirkelschluss?

04.11.2021, 21:20

IfindU

Auf diesen Beitrag antworten »

RE: Folgen
Man kann die Menge der Primzahl definieren, wie es HAL gemacht hat:

$\begin{eqnarray*} \mathbb P = \{ p \in \mathbb N : \forall n \in \mathbb N \text{ mit } n | p \implies n \in \{1,p\}\} \end{eqnarray*}$ .

Die Menge ist vollkommen unabhängig von irgendeiner Folge, und definiert eine Teilmenge der natürlichen Zahlen. Die natürlichen Zahlen sind eine wohlgeordnete Menge und damit die Menge der Primzahl als Teilmenge davon ist ebenfalls wohlgeordnet. D.h. jede Teilmenge von hat ein kleinstes Element.

Bis hier hin habe ich noch kein Wort über Folgen verloren. Und an der Stelle definiert man sich geeignete Teilmengen und nimmt genau das kleinste, um eine rekursive Folge zu definieren.

Für die explizite Darstellung nimmt man die kanonische Ordnung auf $\begin{eqnarray*} \mathbb P \end{eqnarray*}$ (die von $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ geerbte, d.h. $\begin{eqnarray*} 2 < 3 < 5 < 7 < 11 < \ldots) \end{eqnarray*}$ und definiert die Folge eben als genau das $\begin{eqnarray*} n \end{eqnarray*}$ -te Glied der Kette.

Inwiefern eine "abstrake" Ordnung eine explizite Folgendarstellung ergibt, ist eine gute Frage. Überlasse ich den Philosphen und den axiomnahen Mathematikern Big Laugh

Als letzte Bemerkung: Da man jede explizite Folge $\begin{eqnarray*} a_n = f(n) \end{eqnarray*}$ aufschreiben kann als $\begin{eqnarray*} a_{n+1} = f(n+1) + 0 \cdot a_n \end{eqnarray*}$ ist jede explizite Folge auch eine rekursive Folge. Damit ist mit dem finden einer expliziten Darstellung auch eine (triviale) rekursive Darstellung gefunden.

04.11.2021, 22:27

Thomas007

Auf diesen Beitrag antworten »

RE: Folgen
Also dann ist im Grunde auch diese Aussage falsch? "Folgen können nicht immer explizit UND rekursiv definiert werden."

04.11.2021, 22:32

Thomas007

Auf diesen Beitrag antworten »

RE: Folgen
Dann hätte ich gleich noch ne Frage, die in diese Richtung geht: Eine Folge muss nicht zwingend unendlich viele Glieder haben, oder?

04.11.2021, 22:36

Leopold

Auf diesen Beitrag antworten »

Hier geht es wohl, wie schon IfindU bemerkt hat, in die Philosophie der Mathematik hinein. Bei konkreten Beispielen hat der praktizierende Mathematiker das richtige Gefühl, ob eine explizite oder rekursive Definition vorliegt. Wenn man aber einmal sauber definieren müßte, was rekursiv und explizit wirklich bedeuten, kommt man bald in Schwierigkeiten. Ist zum Beispiel $\begin{align*} a_n = 2^n \end{align*}$ eine explizit definierte Folge? Das könnte man so annehmen, denn man hat einen Formelausdruck für das $\begin{align*} n \end{align*}$ -te Folgenglied. Auf der anderen Seite steckt in der Definition der Potenz genuin das Rekursive drin: $\begin{align*} 2^n = 2^{n-1} \cdot 2 \end{align*}$ . Die Rekursion ist daher durch eine Definition in einem expliziten Ausdruck versteckt worden. Man könnte sogar den extremen Standpunkt einnehmen, daß die gesamte konstruktiv berechenbare Mathematik letztlich rekursiv aufgebaut ist.

Zur neuen Frage von Thomas007: Folgen in der Analysis sind Abbildungen der natürlichen Zahlen in die Menge der reellen Zahlen, haben also immer unendlich viele Glieder. Es mag andere Bereiche der Mathematik geben, wo man das etwas lässiger sieht.

04.11.2021, 23:51

Finn_

Auf diesen Beitrag antworten »

Folgen sind ein wenig einschränkend. Die verfügbaren Mittel würde ich gerne erweitern um

rekursiv definierte Funktionen mit mehreren Argumenten,
den Aufruf von bereits definierten Funktionen,
Fallunterscheidungen,
Vergleiche.

Eine rekursive Definition der Folge der Primzahlen erhält nun mit dem folgenden Algorithmus:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

def count_divisors(k, n, c):
    if k == n + 1:
        return c
    else:
        return count_divisors(k + 1, n, c + (1 if n%k == 0 else 0))

def is_prime(n):
    return count_divisors(1, n, 0) == 2

def next_prime(n):
    return n + 1 if is_prime(n + 1) else next_prime(n + 1)

def p(n):
    return 2 if n == 0 else next_prime(p(n - 1))

print([p(n) for n in range(10)])

Neue Frage »

Antworten »

Folgen

Verwandte Themen