Äquivalenzrelationen und Abbildungen

29.10.2011, 09:26

Newbie...

Äquivalenzrelationen und Abbildungen

Meine Frage:
Hallo,
ich stehe gerade vor einem kleinen Verständnis-Problem. Naja, eigentlich eher vor 2.
Und zwar wurde ich letzte Woche in den ersten 3 Vorlesungen mit Mengenlehre bombardiert, hab aber nie etwas davon gehört... Ich hab mir schon fleißig das meiste angelesen, die Probleme die bleiben sind eher kleiner Natur, aber ohne sie zu lösen komme ich leider bei meinen Hausaufgaben nicht weiter. Ich hoffe ihr könnt mir da ein wenig helfen. Ich nenne mal die Aufgaben:

(1) Schreiben sie für die Menge M={1} und N={a,b} alle Elemente von P((MxN) $\begin{eqnarray*} \cup \end{eqnarray*}$ (NxM)) .

(2) Seien M und N nichtleere Mengen und sei f: M => N eine Abbildung. Zeigen Sie:
{(a,b) $\begin{eqnarray*} \in \end{eqnarray*}$ MxN: f(a)=f(b)} ist eine Äquivalenzrelation auf M.
Geben sie in dem Fall M=RxR (R=reelle Zahlen) und N=R für f((x,y)):=x²+y² für alle (x,y) $\begin{eqnarray*} \in \end{eqnarray*}$ M eine geometrische Beschreibung der entsprechenden Äquivalenzklassen.

Meine Ideen:
Mein Ansatz bei (1):
Zuerst mal das karthesische Produkt:
MxN= (1,a),(1,b) und NxM= (a,1),(b,1)
Dies sind ja nun keine Mengen mehr...Aber ich habe trotzdem mal weiter überlegt:
Die Vereinigung wäre ja:
(MxN) $\begin{eqnarray*} \cup \end{eqnarray*}$ (NxM) = (1,a),(1,b),(a,1),(b,1) oder?
Und nun soll ich daraus die Potenzmenge bestimmen, so habe ich das jedenfalls verstanden (!?). Laut Regel wären das 2^n Mengen, also 16. Ich kriege:
P(P)= {leer},{(1,a)},{(1,b)},{(a,1)},{(b,1)},{(1,a),(1,b)},{(1,a),(a,1)},
{(1,a),(b,1)},{(1,b),(a,1)},{(1,b),(b,1)},{(a,1),(b,1)},
{(1,a),(1,b),(a,1)},{(1,a),(1,b),(b,1)},{(1,a),(a,1),(b,1)},{(1,b),(a,1),(b,1)},
{(1,a),(1,b),(a,1),(b,1)}
Und es sind tatsächlich 16. Nur kommt mir das ganze ein wenig merkwürdig vor, da ich binäre Tupel dabei hab und jetzt bin ich mir nicht sicher ob das so richig ist.

Ansatz zu 2:
Hier scheitere ich schon wesentlich früher. (a,b) $\begin{eqnarray*} \in \end{eqnarray*}$ MxN heißt doch das a $\begin{eqnarray*} \in \end{eqnarray*}$ M und b $\begin{eqnarray*} \in \end{eqnarray*}$ N, oder? dann wäre doch aber mein b theoretisch mein f(a), da ja f:M => N die Abbildung ist, oder? Da liegt mein Problem...

Ich hoffe ihr könnt mir ein wenig helfen
MfG,
Tobi

29.10.2011, 09:38

lgrizu

Auf diesen Beitrag antworten »

RE: Äquivalenzrelationen und Abbildungen

Zitat:

Original von Newbie...

Meine Ideen:
Mein Ansatz bei (1):
Zuerst mal das karthesische Produkt:
MxN= (1,a),(1,b) und NxM= (a,1),(b,1)
Dies sind ja nun keine Mengen mehr...

Doch das sind Menegne, es ist $\begin{eqnarray*} M \times N=\left\{(a,b): a \in M \text{ und } b \in N\right\} \end{eqnarray*}$ . Du hast eine Menge von Tupeln.

Zitat:

Die Vereinigung wäre ja:
(MxN) $\begin{eqnarray*} \cup \end{eqnarray*}$ (NxM) = (1,a),(1,b),(a,1),(b,1) oder?

Nicht vergessen, Mengenklammern zu setzen. Es ist $\begin{eqnarray*} M \times N=\left\{(1,a),(1,b) \right\} \end{eqnarray*}$ und $\begin{eqnarray*} N \times M =\left\{ (a,1), (b,1) \right\} \end{eqnarray*}$ und die Vereinigung ist dann demenstprechend $\begin{eqnarray*} \left\{(a,1),(b,1),(1,a),(1,b)\right\} \end{eqnarray*}$

Zitat:

Und nun soll ich daraus die Potenzmenge bestimmen, so habe ich das jedenfalls verstanden (!?). Laut Regel wären das 2^n Mengen, also 16. Ich kriege:
P(P)= {{leer},{(1,a)},{(1,b)},{(a,1)},{(b,1)},{(1,a),(1,b)},{(1,a),(a,1)},
{(1,a),(b,1)},{(1,b),(a,1)},{(1,b),(b,1)},{(a,1),(b,1)},
{(1,a),(1,b),(a,1)},{(1,a),(1,b),(b,1)},{(1,a),(a,1),(b,1)},{(1,b),(a,1),(b,1)},
{(1,a),(1,b),(a,1),(b,1)}}

Auch hier die Mengenklammer nicht vergessen, die Potenzmenge ist eine Menge von Mengen.

Die zweite Aufgabe hat ein Kommiltone von dir hier auch gepostet: Mengenlehre - Ansätze und Links für HA.

Allerdings wird dort das Kartesische Produkt MXM betrachtet.

29.10.2011, 10:51

Newbie...

Auf diesen Beitrag antworten »

aaah, ok. Dann war ja zumindest der Ansatz nicht ganz falsch... Danke dir für deine Antwort.
Hmm, wenn das MxM wäre dann wüsste ich glaube ich wie ich das lösen muss. Vielleicht hab ich das ja falsch abgeschrieben...

29.10.2011, 13:28

Newbie...

Auf diesen Beitrag antworten »

Soo, schon hab ich das nächste Problem mit der (zum glück...) letzten Aufgabe:

Sei U1:=1 , U2:=2 , Un=U(n-1)+U(n-2) , n=1,2,3,...
Zeigen sie, daß auf diese Weise rekursiv eine Zahlenfolge (Un)n=1,2,... definiert ist, sodass Un $\begin{eqnarray*} \leq \end{eqnarray*}$ (7/4)^n
für alle n $\begin{eqnarray*} \in \end{eqnarray*}$ N (natürliche Zahlen). Da er uns in der Vorlesung einmal kurz in 5min die vollst. Induktion an die Tafel geklatscht hat gehe ich davon aus das wir die Aufgabe damit lösen sollen (...):

Mein Ansatz:

Zuerst mal beweise ich das ganze für das kleinste element (nennt man das so?) für n, ich denke mal das ist hier 1:

U1=U(1-1)+U(1-2) <=> U1=U0+U(-1)

Dazu muss ich ja erstmal U0 und U-1 berechnen. Das hab ich so gemacht:
U2=U1+U0 , 2=1+U0 , also muss U0=1 sein (!?) und dann:
U1=U0+U(-1) , 1=1+U(-1) , also muss U(-1)=0 sein (!?).

Dann weiter mit dem Beweis für n=1:
U1 $\begin{eqnarray*} \leq \end{eqnarray*}$ (7/4)^1 , U0+U(-1) $\begin{eqnarray*} \leq \end{eqnarray*}$ (7/4) also:
1+0 $\begin{eqnarray*} \leq \end{eqnarray*}$ (7/4) (!?)
An dieser Stelle hätte ich dann das ganze für n=1 bewiesen (denke ich)

Dann folgt die Induktionsvoraussetzung:
U(n-1)+U(n-2) $\begin{eqnarray*} \leq \end{eqnarray*}$ (7/4)^n

Und meine Induktionsbehauptung:
U((n+1)-1)+U((n+1)-2) $\begin{eqnarray*} \leq \end{eqnarray*}$ (7/4)^(n+1)
Hier habe ich probiert auf der rechten Seite eine Summe zu bilden, bei der wieder etwas aus der Voraussetzung auftaucht:
Un + U(n-1) $\begin{eqnarray*} \leq \end{eqnarray*}$ (7/4)^n + (3/4)*(7/4)^n
Und jetzt habe ich probiert die linke Seite so umzuformen, das sie elemente aus der linken seite der Voraussetzung enthält:
Un+U(n-1)+U(n-2)-U(n-2) $\begin{eqnarray*} \leq \end{eqnarray*}$ (7/4)^n + (3/4)*(7/4)^n
Dann hatte ich zwei Ungleichungen:
U(n-1)+U(n-2) $\begin{eqnarray*} \leq \end{eqnarray*}$ (7/4)^n (diese ist ja wieder die Induktionsvoraussetzung, sie gilt also als wahr!?)
und:
Un-U(n-2) $\begin{eqnarray*} \leq \end{eqnarray*}$ (3/4)*(7/4)^n (diese bleibt zu beweisen. Nur weiß ich nicht wie ich jetzt weiter machen soll geschweige denn ob das bisher so richtig ist...)

29.10.2011, 18:46

lgrizu

Auf diesen Beitrag antworten »

Die Rekursionsvorschrift lautet $\begin{eqnarray*} U_{n}=U_{n-1}+U_{n-2} \end{eqnarray*}$ mit den Startwerten $\begin{eqnarray*} U_1=1 \end{eqnarray*}$ und $\begin{eqnarray*} U_2=2 \end{eqnarray*}$ ?

Dann ist $\begin{eqnarray*} U_3=3 \end{eqnarray*}$ , $\begin{eqnarray*} U_4=U_3+U_2=3+2=5 \end{eqnarray*}$ .

Das ganze wäre dann die Fibonacci Folge mit dem fehlenden ersten Glied 1.

Für n=1 ist nichts zu zeigen, denn es ist nach Startwertvorgabe $\begin{eqnarray*} U_1=1 \end{eqnarray*}$ , ebensowenig für n=2, beginnen wir also mit n=3.

Du solltest den Induktionsanfang auch für n=3 und für n=4 machen, denn du benötigst in dem Beweis auch die Vorraussetzung für n-1, du musst das ganze also für ein n und für ein zugehöriges n-1 zeigen, dann wären n=4 und n-1=3.

Deine ganze rumrechnerei erübrigt sich, wenn man die Vorraussetzung auf $\begin{eqnarray*} U_n \end{eqnarray*}$ und $\begin{eqnarray*} U_{n-1} \end{eqnarray*}$ loslassen kann.

29.10.2011, 19:23

Newbie...

Auf diesen Beitrag antworten »

Mmh, ok. Klar soweit. Aber weshalb ist hier meine Voraussetzung für n und meine Behauptung für n-1? Ich dachte man nimmt immer Un an und beweist es dann auch für U(n+1), oder ist es egal ob ich eins dazu addiere oder abziehe?

EDIT:
Irgendwie komm ich trotzdem nicht weiter (ich weiß, muss mühsam sein mit mir...):
Voraussetzung:
U(n-1)+U(n-2) $\begin{eqnarray*} \leq \end{eqnarray*}$ (7/4)^n (die bleibt ja, oder?)
Und die Behauptung mit n-1 ist dann:
U((n-1)-1)+U((n-1)-2) $\begin{eqnarray*} \leq \end{eqnarray*}$ (7/4)^(n-1)

daraus mache ich wieder:
U(n-2)+U(n-3) $\begin{eqnarray*} \leq \end{eqnarray*}$ (7/4)^n -(3/4)*(7/4)^n
und weiter:
U(n-2)+U(n-3)+U(n-1)-U(n-1) $\begin{eqnarray*} \leq \end{eqnarray*}$ (7/4)^n -(3/4)*(7/4)^n

Und dann habe ich wieder zwei Ungleichungen von denen eine die Voraussetzung ist:
U(n-1)+U(n-2) $\begin{eqnarray*} \leq \end{eqnarray*}$ (7/4)^n (Voraussetzung)
und
U(n-3)-U(n-1) $\begin{eqnarray*} \leq \end{eqnarray*}$ -(3/4)*(7/4)^n (müsst ich noch beweisen)

und nu häng ich schon wieder...

29.10.2011, 22:08

lgrizu

Auf diesen Beitrag antworten »

Du hast doch durch de Rekursionsvorschrifz folgendes gegeben:

$\begin{eqnarray*} U_{n+1}=U_n+U_{n-1} \end{eqnarray*}$ .

Nun ist nach Induktionsvorraussetzung $\begin{eqnarray*} U_n \leq \left( \frac{7}{4} \right)^n \end{eqnarray*}$ , und weil wir schlauerweise die Induktionsvorraussetzung auch für ein n-1 geprüft haben gilt ebenso nach Vorraussetzung: $\begin{eqnarray*} U_{n-1} \leq \left( \frac{7}{4} \right)^{n-1} \end{eqnarray*}$ .

Wir haben also nach Vorraussetzung:

$\begin{eqnarray*} U_{n+1}=U_{n}+U_{n-1} \leq \left( \frac{7}{4} \right)^n + \left( \frac{7}{4} \right)^{n-1} \end{eqnarray*}$ .

Nun kann man sich daran machen zu zeigen, dass gilt $\begin{eqnarray*} \left( \frac{7}{4} \right)^n + \left( \frac{7}{4} \right)^{n-1} \leq \left( \frac{7}{4} \right)^{n+1} \end{eqnarray*}$ , das ist reien Rechenarbeit.

30.10.2011, 08:57

Newbie...

Auf diesen Beitrag antworten »

Der Beweis wäre dann:
$\begin{eqnarray*} \left(\frac{7}{4} \right)^n + \left(\frac{7}{4} \right)^{n-1} \leq \left(\frac{7}{4} \right)^{n+1} \end{eqnarray*}$
$\begin{eqnarray*} \left(\frac{7}{4} \right)^n + \left(\frac{7}{4} \right)^n \cdot \left(\frac{-7}{4}\right) \leq \left(\frac{7}{4} \right)^n \cdot \left(\frac{7}{4} \right) \end{eqnarray*}$
$\begin{eqnarray*} \left(\frac{7}{4} \right)^n \cdot \left(1-\frac{7}{4}\right) \leq \left(\frac{7}{4} \right)^n \cdot \frac{7}{4} \end{eqnarray*}$
$\begin{eqnarray*} \frac{-3}{4} \cdot \left(\frac{7}{4} \right)^n \leq \frac{7}{4} \cdot \left(\frac{7}{4} \right)^n \end{eqnarray*}$
$\begin{eqnarray*} -3 \cdot \left(\frac{7}{4} \right)^n \leq 7 \cdot \left(\frac{7}{4} \right)^n \end{eqnarray*}$
Und ab dieser Stelle sehe ich ja das die rechte Seite immer größer sein wird als die linke, richtig?
Damit wäre das ja mein Beweis (?).
Ein kleines Verständnisproblem bleibt allerdings:
Weshalb kann ich:
$\begin{eqnarray*} \left(\frac{7}{4} \right)^n + \left(\frac{7}{4} \right)^{n-1} \leq \left(\frac{7}{4} \right)^{n+1} \end{eqnarray*}$
überhaupt setzen?
Es is ja: $\begin{eqnarray*} U_{n+1}=U_{n}+U_{n-1} \end{eqnarray*}$
Soweit klar, da es rekursiv ist geht das so (ich wusste nicht was rekursiv heißt, deshalb kam ich da nicht drauf...)
Und: $\begin{eqnarray*} U_{n+1}=U_{n}+U_{n-1} \leq \left(\frac{7}{4} \right)^n + \left(\frac{7}{4} \right)^{n-1} \end{eqnarray*}$ ist auch klar.
Wie aber kommt jetzt $\begin{eqnarray*} \left(\frac{7}{4} \right)^{n+1} \end{eqnarray*}$ ins Spiel? Oder gilt das wegen:
$\begin{eqnarray*} U_{n+1} \leq \left(\frac{7}{4} \right)^{n+1} \end{eqnarray*}$ ? Aber das habe ich doch gar nicht bewiesen?
Die Zusammensetzung von:
$\begin{eqnarray*} \left(\frac{7}{4} \right)^n + \left(\frac{7}{4} \right)^{n-1} \leq \left(\frac{7}{4} \right)^{n+1} \end{eqnarray*}$
ist mir noch nicht so ganz klar. Ich hoffe du lässt ein wenig nachsicht mit mir walten (...^^).

Ich danke dir auf jeden Fall schonmal ganz ordentlich, ohne deine Hilfe wär ich immer noch am grübeln wie ich überhaupt anfangen soll...

30.10.2011, 13:14

lgrizu

Auf diesen Beitrag antworten »

Also bis hierhin ist alles klar, oder?

$\begin{eqnarray*} U_{n+1}=U_{n}+U_{n-1} \leq \left( \frac{7}{4} \right)^n + \left( \frac{7}{4} \right)^{n-1} \end{eqnarray*}$ .

Nun müssen wir zeigen, dass gilt $\begin{eqnarray*} U_{n+1} \leq \left(\frac{7}{4} \right)^{n+1} \end{eqnarray*}$ .

Wir haben bereits nach Vorraussetzung:

$\begin{eqnarray*} U_{n+1} \leq \left( \frac{7}{4} \right)^n + \left( \frac{7}{4} \right)^{n-1} \end{eqnarray*}$ .

Wenn wir nun zeigen können, dass gilt $\begin{eqnarray*} \left( \frac{7}{4} \right)^n + \left( \frac{7}{4} \right)^{n-1} \leq \left(\frac{7}{4}\right)^{n+1} \end{eqnarray*}$ ist die Behauptung bewiesen.

Zitat:

Wie du auf diese Umformung kommst ist mir Unklar. Es ist $\begin{eqnarray*} \left(\frac{7}{4}\right)^{n-1} \neq \left(\frac{7}{4}\right)^{n} \cdot \left( \frac{-7}{4}\right)=(-1) \cdot \left(\frac{7}{4}\right)^{n+1} \end{eqnarray*}$ .

30.10.2011, 20:14

Newbie...

Auf diesen Beitrag antworten »

Ouh, ja. Natürlich, das ist falsch. Was für ein Denkfehler...
Ich habe jetzt als Beweis folgendes gefunden:
$\begin{eqnarray*} \left(\frac{7}{4}\right)^n + \left(\frac{7}{4}\right)^{n-1} \leq \left(\frac{7}{4}\right)^{n+1} \end{eqnarray*}$
dann:
$\begin{eqnarray*} \left(\frac{7}{4}\right)^n + \left(\frac{7}{4}\right)^n \cdot \left(\frac{7}{4}\right)^{-1} \leq \left(\frac{7}{4}\right)^n \cdot \left(\frac{7}{4}\right) \end{eqnarray*}$
dann:
$\begin{eqnarray*} \left(\frac{7}{4}\right)^n \cdot \left(1+\frac{4}{7}\right) \leq \left(\frac{7}{4}\right)^n \cdot \frac{7}{4} \end{eqnarray*}$
und daraus:
$\begin{eqnarray*} \frac{11}{7} \leq \frac{7}{4} \end{eqnarray*}$
$\begin{eqnarray*} \frac{44}{28} \leq \frac{49}{28} \end{eqnarray*}$

Stimmt das dann so? Oder hab ich wieder irgendwo so einen Schussel-Fehler...?
Ich danke dir nochmal, kann ich gar nicht oft genug sagen. Ich glaube zwar nicht das ich jetzt eine Aufgabe zur vollst. Induktion ganz allein lösen kann, aber der Weg dahin ist mir doch ein gutes Stück klarer geworden (sofern das jetzt richtig ist^^)

30.10.2011, 20:17

lgrizu

Auf diesen Beitrag antworten »

Jap, ist richtig. Nun das ganze noch sauber und richtig aufschreiben.

30.10.2011, 21:01

Newbie...

Auf diesen Beitrag antworten »

Ok, wunderbar. Danke dir nochmals!

MfG,
Tobi

Neue Frage »

Antworten »

Äquivalenzrelationen und Abbildungen

Verwandte Themen