Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Wie kann ich folgende Aussagen beweisen?

Wie kann ich folgende Aussagen beweisen?

Universität / Fachhochschule

Funktionen

Tags: Äquivalenz, Aussagenlogik, Funktion

FarrahFowler aktiv_icon

12:57 Uhr, 01.05.2014

Meine Frage:
Seien

X

und

Y

Mengen und

f : X \to Y

eine Funktion. Zeigen Sie, dass folgende Aussagen äquivalent sind:

(i)

f

ist injektiv

(ii) Für alle Teilmengen

A \subset X

gilt

f^{- 1} (f (A)) = A

(iii) Für alle Teilmengen

A, B \subset X

gilt

f (A \cap B) = f (A) \cap f (B)

(iv)

f (A) \cap f (B) = \emptyset

gilt für alle Teilmengen

A, B \subset X

mit

A \cap B = \emptyset

.

Meine Ideen:
Wenn ich zeigen soll, dass die Aussagen äquivalent sind, muss ich ja einen Ringschluss durchführen.
Für (i)

\Rightarrow

(ii) habe ich schon eine hoffentlich richtige Formulierung gefunden (per Widerspruchsbeweis):

Angenommen

f^{- 1} (f (A)) \neq A

Dann gibt es ein

x 1 \in A

und

x 2 \notin A

mit

f (x 1) = f (x 2)

und

x 1 \neq x 2

.

Dies ist ein Widerspruch zur Injektivität von

f

und somit eine falsche Aussage.

Okay und bei den nächsten Schritten kommme ich schon nicht weiter..

: (

Kann mir bitte jemand helfen??

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:
Funktion (Mathematischer Grundbegriff)

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Einführung Funktionen

DrBoogie aktiv_icon

13:16 Uhr, 01.05.2014

"Für (i) ⇒ (ii) habe ich schon eine hoffentlich richtige Formulierung gefunden (per Widerspruchsbeweis)"

Deine Argumentation ist zu knapp, um urteilen zu können, ob sie richtig ist. Die Idee des Widerspruchsbeweises ist an sich gut.

Ich will nicht sofort alles aufschreiben, aber z.B. (iv)=>(i) geht so:
Sei

x_{1} \neq x_{2}

. Definieren

A = {x_{1}}

B = {x_{2}}

(also einelementige Teilmengen). Es gilt klar

A \cap B = \emptyset

. (iv) sagt uns, dass

f (A) \cap f (B) = \emptyset

, aber da

f (A) = {f (x_{1})}

und

f (B) = {f (x_{2}}

, bedeutet das einfach, dass

f (x_{1}) \neq f (x_{2})

. Also,

f

ist injektiv.

FarrahFowler aktiv_icon

13:33 Uhr, 01.05.2014

Ups, wie ich sehe, habe ich vergessen aufzuschreiben, dass es noch eine Aussage

(v)

gibt.

Also nach (iv) gibt es noch

(v)

Sind

A, B

Teilmengen von

X

mit

B \subset A,

so gilt

f (A \ B) = f (A) \ f (B)

.

Hmm nachvollziehen kann ich deine Lösung zwar, aber es fällt mir immer sehr schwer, selbst einen Ansatz zu finden. Also zB von (ii) nach (iii). Uns wurde der Tipp gegeben, erst zu zeigen, dass

f (A \cap B) \subset f (A) \cap f (B)

ist und andersrum und dabei sollen wir das

f^{- 1} (f (A)) = A

mit einbringen?? Da komme ich gar nicht klar. Sitze davor, versuche etwas aufzuschreiben, aber es kommt nichts sinnvolles bei raus.

FarrahFowler aktiv_icon

14:34 Uhr, 01.05.2014

Hmm kann mir vielleicht irgendwer einen Tipp geben, wie ich bei den einzelnen Aussagen anfangen kann?
Wäre euch sehr dankbar.

DrBoogie aktiv_icon

18:08 Uhr, 01.05.2014

Bei dieser Aufgabe ist es leider praktisch unmöglich, irgendwelche Tipps zu geben, denn in den Beweisen gibt's keine Tricks, nicht mal irgendeine originelle Ideen, es läuft alles auf relativ stumpfe Anwendung von Definitionen.
Aber da es um abstrakte mathematische Beweise geht, muss man einfach gewisse Erfahrung damit haben, sonst ist es wirklich schwierig. Man braucht wirklich Zeit und nicht wenig Übung, um sich an die Kultur eines abstrakten mathematischen Beweises zu gewöhnen. Und da diese Kultur an der Schule kaum beigebracht wird, tun viele Leute sich damit im Studium schwer. Da hilft leider nur viele Beweise lesen und analysieren.

Ich schreibe trotzdem alle Beweise für Dich, das ist leider alles, was ich machen kann. :-)

i) => ii)
Indirekter Beweis. Nehmen wir an, dass i) gilt, aber ii) nicht, dass also eine Teilmenge

A

existiert, so dass

f^{- 1} (f (A)) \neq A

. Da offensichtlich

A \subset f^{- 1} (f (A))

(denn für jedes

x

aus

A

gilt

x = f^{- 1} (f (x))

, ist

f^{- 1} (f (A)) \neq A

nur dann möglich, wenn ein

y

aus

f^{- 1} (f (A))

existiert, das nicht in

A

liegt. Aus

y \in f^{- 1} (f (A))

folgt aber

f (y) \in f (A)

und daher gibt es ein

z

aus

A

, so dass

f (y) = f (z)

. Aber

y \neq z

, weil

z

A

liegt und

y

nicht. Damit ist

f

nicht Injektiv. Das ist ein Widerspruch zu i), damit haben wir bewiesen, dass aus i) tatsächlich ii) folgt.

ii) => iii)
Es gilt allgemein:

f^{- 1} (C \cap D) = f^{- 1} (C) \cap f^{- 1} (D)

. Das zeigt man so:
1)

x \in f^{- 1} (C \cap D)

< = > f (x) \in (C \cap D)

< = > f (x) \in C

und

f (x) \in D

< = > x \in f^{- 1} (C)

und

x \in f^{- 1} (C)

< = > x \in f^{- 1} (C) \cap f^{- 1} (D)

Jetzt zeigen wir, dass aus ii) tatsächlich iii) folgt.
Es gilt:

f^{- 1} (f (A) \cap f (B)) = f^{- 1} (f (A)) \cap f^{- 1} (f (B)) = A \cap B

, wobei die erste Gleichung aus der gerade bewiesenen Aussage folgt und die zweite aus ii).
Wenden jetzt

f

auf beide Seiten und bekommen

f (A) \cap f (B) = f (A \cap B)

. Damit ist iii) bewiesen.

Fortsetzung folgt... :-)

FarrahFowler aktiv_icon

18:29 Uhr, 01.05.2014

Vielen vielen Dank!!

Es fällt mir zurzeit echt noch sehr schwer, solche Beweise selbst zu formulieren, da ich erst in der dritten Woche des Studiums bin und doch alles sehr sehr viel Stoff ist, den ich mir selbst erstmal verständlich machen muss. Da fallen mir die Hausaufgaben momentan nicht leicht. Ich hoffe, dass ich das irgendwann so kann, ohne dass ich Fragen dazu stellen muss und bleibe auf jeden Fall am Ball! Also danke dir :-)

DrBoogie aktiv_icon

18:44 Uhr, 01.05.2014

iii) =>iv)

Das ist schon einfacher.
Wenn

A \cap B = \emptyset

, dann ist klar auch

f (A \cap B) = \emptyset

.
Und nach iii) gilt

f (A \cap B) = f (A) \cap f (B)

.
Also haben

f (A) \cap f (B) = \emptyset

.

iv) => v)

Zuerst mal gilt immer

A \ B \subset A

und deshalb auch immer

f (A \ B) \subset f (A)

, genauso gilt wegen

B \subset A

dann

f (B) \subset f (A)

. Und zusammen bekommen wir

f (A \ B) \cup f (B) \subset f (A)

. Andererseits, muss auch

f (A) \subset f (A \ B) \cup f (B)

gelten, denn jedes

x

aus

A

liegt entweder in

B

oder in

A \ B

, damit liegt

f (x)

entweder in

f (B)

oder in

f (A \ B)

.
Insgesamt haben also die Gleichung

f (A) = f (A \ B) \cup f (B)

(sie ist allgemein gültig, unabhängig von iv)).

Außerdem gilt immer

(A \ B) \cap B = \emptyset

. Deshalb können wir iv) anwenden und bekommen

f (A \ B) \cap f (B) = \emptyset

.
Also, haben

f (A \ B) \cup f (B) = f (A)

und

f (A \ B) \cap f (B) = \emptyset

. Daraus folgt sofort

f (A \ B) = f (A) \ f (B)

.

v) =>i)
Machen es wieder indirekt. Sei also

f

nicht Injektiv. Dann gibt's

x_{1}

und

x_{2}

mit

x_{1} \neq x_{2}

, aber

f (x_{1}) = f (x_{2})

. Definieren

B = {x_{1}}

und

A = {x_{1}, x_{2}}

.
Für diese

A

und

B

gilt

A \ B

{x_{2}}

und

f (A) = {f (x_{1})}

, weil

f (x_{1}) = f (x_{2})

, außerdem

f (B) = {f (x_{1})}

f (A \ B) = {f (x_{2})} = {f (x_{1})} = f (B) = f (A)

.
Also,

f (A \ B) \neq \emptyset

, aber

f (A) \ f (B) = \emptyset

, was der Annahme v) widerspricht. Also, muss

f

Injektiv sein, wenn v) gilt.

So, damit ist die Sache fertig. :-)

FarrahFowler aktiv_icon

19:10 Uhr, 01.05.2014

Super, danke für die Mühe!
Nur noch kurz eine Verständnisfrage zu (i)

- \to

(ii)

Da steht es muss ein

y \in f^{- 1} (f (A))

existieren, mit

y \notin A

. Das ist soweit klar. Aus

y \in f^{- 1} (f (A))

folgt, dass

f (y) \in f (A)

(auch klar) und daher existiert ein

z \in A,

sodass

f (y) = f (z)

. Das verstehe ich nicht ganz. Warum existiert dieses

z \in A

tommy40629 aktiv_icon

19:27 Uhr, 01.05.2014

Zitat:
Hmm kann mir vielleicht irgendwer einen Tipp geben, wie ich bei den einzelnen Aussagen anfangen kann?
Wäre euch sehr dankbar.

Als ich in den "Ferien" LA1 wiederholt habe, hatte ich eine ähnliche Aufgabe.
Ich habe sie durch das "Reduzieren" der Definitionen in die Aussagenlogik lösen können.

Es wird leider, auch von Profs, geleugnet das Aussagenlogik und Prädikatenlogik 1. Stufe der Schlüssel zu solchen Beweisen sind.

Aber Logik ist das Fundament der Mathematik!
Es fängt mit logischen und, oder an und wird dann langsam komplexer, das kann man jetzt nicht in 4 Sätzen erklären.

Wir haben einen Studenten bei uns, der hat uns solche ähnlichen Beweise, wie Du sie hier hast bewiesen, ohne die Hintergründe richtig verstanden zu haben, es ist aber sehr fit in Aussagenlogik und Prädikatenlogik 1. Stufe. Er hat auch gesagt, dass das das Werkzeug für solche Beweise ist.

Er hat dazu ein Buch aus den USA durchgearbeitet. Ich frage ihn mal, wie es heißt, dann nenne ich Dir den Titel.

FarrahFowler aktiv_icon

19:36 Uhr, 01.05.2014

Hallo Tommy,
ich würde mir auch gern in den Semesterferien, wenn ich dann mehr Zeit habe, viele Bücher dazu durchlesen. Aber jetzt mal im Ernst - diese Aufgabe ist doch schon ziemlich komplex, oder? Ist das normal, dass man so eine Hausaufgabe schon nach der zweiten Woche Mathematik Studium aufbekommt?

: O

Ist ja nur der erste Teil der kompletten HA und der Rest wird auch nicht leichter. Ganz schön heftig, finde ich. Aber ich bleib dran! :-)

tommy40629 aktiv_icon

19:51 Uhr, 01.05.2014

Es gibt 2 Möglichkeiten diese Aufgaben zu lösen.
1. Du hast das Thema perfekt verstanden und kannst es im Schlaf.
2. Man wendet die Logik an.

Ich habe in LA1 vom Prof Deitmar aus Tübingen, ist nicht mein Prof, solche Aufgaben, wie Du sie hier hast zeigen können, nur weil ich die Logik angewendet habe.

Ich wußte zwar nicht was ich da gerade Beweise, aber ich konnte die Definitionen zerstückeln umformen und wieder zusammensetzen. So was lernt man bei keinem Prof.

Ein Paradebeispiel ist das Distributivgesetz für die Schnittmenge und Vereinigungsmenge, das ist ein Beweis, der einzig und allein auf die Grundlagen der Gesetze von "und" und "oder" aufbaut. So ist das bei vielen dieser Mengenbeweise.

Später kommt dann die Tautologie, Kontradiktion... hinzu. Und das zu lernen ist wirklich nicht schwer. Kostet aber Zeit, die man im Semester nicht hat. Außer man belegt nur ein oder zwei Fächer.

Zur Aussgenlogik kannst Du hier etwas lernen:
www.youtube.com/watch?v=fDHippqDhVE
www.youtube.com/watch?v=-7ecaD19Ixo
www.youtube.com/watch?v=cj0pmLs1c6Y

Tautologie und Kontradiktion:
http//mediathek.mt.haw-hamburg.de/video/M1-2013-10-09-08-Tautologien-Kontradiktionen-Erfuellbarkeit/24c79cb51279e423ba4e1f6ef32d1f59

Prädikatenlogik:
http//mediathek.mt.haw-hamburg.de/search/title/pr%C3%A4dikatenlogik/description/pr%C3%A4dikatenlogik/tags/pr%C3%A4dikatenlogik/type/all/categoriesopt/0/channelsopt/0

www.youtube.com/watch?v=lVSWLrC83zw

Bei Prof Spannagel findest Du zur Logik sehr viel. Er rechnet auch auf youtube viel vor.

DrBoogie aktiv_icon

07:46 Uhr, 02.05.2014

"dass

f (y) \in f (A)

(auch klar) und daher existiert ein

z \in A

, sodass

f (y) = f (z)

. Das verstehe ich nicht ganz. Warum existiert dieses

z \in A

"

Die Aussage "

w \in f (A)

" bedeutet in Wirklichkeit "es existiert ein

z

aus

A

, so dass

w = f (z)

". Jetzt nimm

f (y)

anstelle von "

w

DrBoogie aktiv_icon

07:50 Uhr, 02.05.2014

"Es wird leider, auch von Profs, geleugnet das Aussagenlogik und Prädikatenlogik 1. Stufe der Schlüssel zu solchen Beweisen sind."

Das Problem ist, dass formale Aussagenlogik noch eine Stufe höher liegt in Richtung Abstraktion als die Beweise, wie ich sie hier geschrieben habe. Und die Erfahrung zeigt, dass die meisten Menschen deshalb mit der Aussagelogik noch größere Probleme haben. Ausnahmen gibt's bestimmt, aber nur wenige. Das ist auch der Grund, warum die volle Formalisierung der Mathematik a-la Bourbaki nicht wirklich weit vorgeschritten ist, nicht mal in Frankreich und nicht mal auf dem allerhöchsten Niveau der mathematischen Forschung (kannst Du einfach eine beliebige mathematische Zeitschrift aufmachen und sehen, dass immer noch viel mit Worten argumentiert wird).

tommy40629 aktiv_icon

14:10 Uhr, 02.05.2014

Moment Aussagenlogik schwer??

Also das ist bisher das Einfachste, was ich mir bezüglich Mathestudium angeeignet habe.

Was ich bestätigen kann ist, dass wenn man Aussagenlogik mit deutschen Lehrbüchern lernt, dann ist es echt schwer. In einem Anfängerbuch wird man sofort mit einem undurchdringlichen Formalismus erschlagen.

Die Bücher der Amerikaner dagegen sind super zu lesen.

Man darf die Aussagenlogik nur nicht mit der Logik aus dem täglichen Leben mischen.

DrBoogie aktiv_icon

14:18 Uhr, 02.05.2014

"Also das ist bisher das Einfachste, was ich mir bezüglich Mathestudium angeeignet habe."

Dann bist Du die besagte Ausnahme.
Ich habe über 15 Jahre Erfahrung - als Student, Doktorand und Wissenschaftlicher Mitarbeiter, also habe meine Statistik. :-) Und nicht nur aus Deutschland.

1161956

1161668

	Status: nicht eingeloggt	Noch nicht registriert?