Äquivalenzrelation beweisen < naiv < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:44 Do 15.04.2010 | | Autor: | angelnc |
| Aufgabe | Seien f, g : [mm] \IN \to \IN [/mm] Funktionen. Wir sagen "f ist in [mm] \partial(g)" [/mm] (kurz "f [mm] \in \partial(g)"), [/mm] falls es Konstanten K, [mm] n_{0} [/mm] gibt, so dass
f(n) [mm] \le [/mm] K * g(n) für alle n [mm] \ge n_{0}.
[/mm]
Wir schreiben f [mm] \sim [/mm] g, falls f [mm] \in \partial(g) [/mm] und g [mm] \in \partial(f). [/mm] f [mm] \sim [/mm] g besagt, dass f und g dieselbe Wachstumsrate haben.
Zeigen Sie, dass f [mm] \sim [/mm] g eine Äquivalenzrelation auf der Menge aller Funktionen [mm] \IN \to \IN [/mm] ist. |
Hallo!
Ich habe die Aufgabe jetzt zehn mal gelesen und verstehe leider kein Wort.
Ich habe auch schon Komilitonen gefragt und Studenten aus höheren Semestern...keiner konnte mir helfen.
Mein Professor kann überhaupt nicht erklären, deshalb wäre ich froh, wenn mir jemand erklären könnte worum es in der Aufgabe geht, was verlangt wird und wie ich auf einen Lösungsansatz komme.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Danke für Eure Hilfe.
Gruß
angelnc
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:11 Do 15.04.2010 | | Autor: | M.Rex |
Hallo
Hier sollst du prüfen, ob die drei Bedingungen einer ![[]](/images/popup.gif) Äquivalenzrelation erfollt sind.
Also:
1. $ f [mm] \sim [/mm] f $ (reflexiv)
2. $ f [mm] \sim [/mm] g [mm] \gdw [/mm] g [mm] \sim [/mm] f $ (Symmetrie)
3 $ f [mm] \sim [/mm] g, g [mm] \sim [/mm] h [mm] \Rightarrow [/mm] f [mm] \sim [/mm] h $ (Transsitivität)
Nehmen wir mal Teil 2.
Es gilt:
f [mm] \sim [/mm] g
Also gilt nach Definition
[mm] f\in\partial(g) [/mm] und [mm] g\in\partial(f).
[/mm]
Also auch
[mm] g\in\partial(f) [/mm] und [mm] f\in\partial(g) [/mm] , da die Und-Verknüpfung kommutativ ist.
Und das besagt nun....
Marius
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:45 Do 15.04.2010 | | Autor: | angelnc |
| Aufgabe | da f=f gilt: f [mm] \sim [/mm] f
da f [mm] \in \partial [/mm] (g) [mm] \wedge [/mm] g [mm] \in \partial [/mm] (f) gilt: f [mm] \sim [/mm] g
wenn h(n) = k*g(n) dann gilt: [mm] h\in \partial [/mm] (g) [mm] \wedge [/mm] g [mm] \in \partial [/mm] (h)
=> h [mm] \sim [/mm] g [mm] \wedge [/mm] g [mm] \sim [/mm] f => h [mm] \sim [/mm] f
|
Das ist jetzt das, was meine Komilitonen und ich erarbeitet haben.
Geht das in die richtige Richtung?
Gruß
angelnc
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:12 Do 15.04.2010 | | Autor: | felixf |
Hallo!
> da f=f gilt: f [mm]\sim[/mm] f
![[ok]](/images/smileys/ok.gif "[ok]")
> da f [mm]\in \partial[/mm] (g) [mm]\wedge[/mm] g [mm]\in \partial[/mm] (f) gilt: f
> [mm]\sim[/mm] g
Das ist ziemlich fuerchterlich aufgeschrieben. So solltest du das auf keinen Fall abgeben.
Und du willst vermutlich eher sagen, dass aus $f [mm] \sim [/mm] g$ folgt dass $g [mm] \sim [/mm] f$ ist?
> wenn h(n) = k*g(n)
Wie kommst du dadrauf? Wo steht irgenwas mit Gleichheit?
> dann gilt: [mm]h\in \partial[/mm] (g) [mm]\wedge[/mm] g
> [mm]\in \partial[/mm] (h)
> => h [mm]\sim[/mm] g [mm]\wedge[/mm] g [mm]\sim[/mm] f => h [mm]\sim[/mm] f
Du hast im wesentlichen nur hingeschrieben, was du zeigen sollst. Mehr nicht.
LG Felix
|
|
|
| |
|
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
Das, was Du schreibst, ist wahrhaft furchtbar, und ich will Dir mal zeigen, wie man das machen könnte,
denn wahrscheinlich hast Du gerade mit dem Studium begonnen.
Zunächst einmal ist es wichtig, daß man sich selbst ganz genau klarmacht, was zu zeigen ist.
Man sollte das auch aufschreiben. Die Korrektoren wollen das sehen - aber vor allem ist es für einen selbst wichtig.
Es ist auch eine Hilfe, wenn man sich als nächstes nochmal separat die Voraussetzung hinschreibt, denn das ist das Material, mit dem man arbeiten kann.
Anschließend notiert man, was man daraus folgern möchte, und das, was man dazu nachweisen muß.
Du möchtest nun also die Symmetrie der Relation [mm] \sim [/mm] zeigen.
Zu beweisende Behauptung:
Für [mm] f,g:\IN \to \IN [/mm] mit [mm] f\sim [/mm] g gilt: [mm] g\sim [/mm] f.
Voraussetzung:
[mm] f,g:\IN \to \IN [/mm] mit [mm] f\sim [/mm] g.
Nach Definition bedeutet dies, daß es Konstanten K und [mm] n_0 [/mm] gibt, so daß für alle natürlichen Zahlen n mit [mm] n\ge n_0 [/mm] gilt:
[mm] f(n)\le [/mm] K*g(n),
und daß es Konstanten L und [mm] m_0 [/mm] gibt, so daß für alle natürlichen Zahlen n mit [mm] m\ge m_0 [/mm] gilt:
[mm] g(m)\le [/mm] L*f(m).
zu zeigen:
Es ist [mm] g\sim [/mm] f.
Man muß also zeigen, daß Konstanten K' und [mm] n_0' [/mm] gibt, so daß für alle natürlichen Zahlen n mit [mm] n\ge n_0' [/mm] gilt:
[mm] g(n)\le [/mm] K'*f(n),
und daß es Konstanten L' und [mm] m_0' [/mm] gibt, so daß für alle natürlichen Zahlen n mit [mm] m\ge m_0' [/mm] gilt:
[mm] f(n)\le [/mm] L'f(n).
Beweis:
Es seien [mm] f,g:\IN \to \IN [/mm] mit [mm] f\sim [/mm] g.
Nach Definition bedeutet dies, daß es Konstanten K und [mm] n_0 [/mm] gibt, so daß für alle natürlichen Zahlen n mit [mm] n\ge n_0 [/mm] gilt:
[mm] f(n)\le [/mm] K*g(n),
und daß es Konstanten L und [mm] m_0 [/mm] gibt, so daß für alle natürlichen Zahlen n mit [mm] m\ge m_0 [/mm] gilt:
[mm] g(m)\le [/mm] L*f(m).
[So, und nun mußt Du irgendwie sagen, wie Du die ganzen gesuchten Konstanten bekommen kannst:]
Mit K':=L, [mm] n_0':= [/mm] ... usw.
gilt ...,
also ist nach Definition [mm] g\sim [/mm] f.
Fazit:
Man hat gezeigt, daß aus [mm] f\sim [/mm] g folgt [mm] g\sim [/mm] f, also ist die Relation [mm] \sim [/mm] symmetrisch.
Ich habe das jetzt bewußt überausführlich gemacht.
Gerade am Anfang vermeidet man so aber viele Fehler.
Du solltest merken, daß nichts Schwieriges dabei war. Schwierig ist es, solche Dinge zu Papier zu bringen.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:09 Do 15.04.2010 | | Autor: | felixf |
Hallo!
> Seien f, g : [mm]\IN \to \IN[/mm] Funktionen. Wir sagen "f ist in
> [mm]\partial(g)"[/mm] (kurz "f [mm]\in \partial(g)"),[/mm] falls es
> Konstanten K, [mm]n_{0}[/mm] gibt, so dass
> f(n) [mm]\le[/mm] K * g(n) für alle n [mm]\ge n_{0}.[/mm]
> Wir schreiben f
> [mm]\sim[/mm] g, falls f [mm]\in \partial(g)[/mm] und g [mm]\in \partial(f).[/mm] f
> [mm]\sim[/mm] g besagt, dass f und g dieselbe Wachstumsrate haben.
Es gilt uebrigens $f [mm] \sim [/mm] g$ genau dann, wenn $f = [mm] \Theta(g)$ [/mm] ist; dabei ist [mm] $\Theta$ [/mm] eins der Landau-Symbole.
Hilft dir vielleicht, Literatur zu finden wo das ganze besser erklaert ist.
LG Felix
|
|
|
|
