Kartesisches Produkt: Beweis für eine Glg

[daria03_3ebe35]

Hallo!

Und zwar handelt es sich um folgende Gleichung:

(AxB) n (CxD) = (AnC) x (BnD)

(wobei das „n“ für geschnitten mit" stehen soll)

Meine bisherigen Überlegungen:

Allg. ist AxB = { (a,b) | a e A, b e B }

Also hab ich mal die die 4 (beliebigen) Mengen A,B,C,D jeweils
a e A,
b e B,
c e C und
d e D
„definiert“ - oder sagen wir mal so: mal hingeschrieben *g*

Wenn ich das jetzt auf die obige Gleichung anwende,
steht da:

(a,b) n (c,d) = ?? (a n c) geht doch nicht, oder etwa doch?

und bekomme ich für die linke Seite nicht die leere Menge?
Aber wo ist dann der allgemeine Beweis?

Und hab ich nicht, indem ich da z.b. a e A , b e B etc. verwende, schonmal „festgelegt“, dass die Mengen in meiner Rechnung disjunkt sind?
Wäre das dann trotzdem immer noch ein allgemeiner Beweis?
*grübel*

Bin gerade ein bisschen verwirrt und hoffe auf Ratschläge / Denkanstöße…

Danke!
Daria

[M_L_]

Auch hallo.

Und zwar handelt es sich um folgende Gleichung:

(AxB) n (CxD) = (AnC) x (BnD)

(wobei das „n“ für geschnitten mit" stehen soll)

Siehe auch http://de.wikipedia.org/wiki/Mengenlehre -> Beispiele & http://de.wikipedia.org/wiki/Kartesisches_Produkt

Meine bisherigen Überlegungen:

Allg. ist AxB = { (a,b) | a e A, b e B }

Also hab ich mal die die 4 (beliebigen) Mengen A,B,C,D jeweils
a e A,
b e B,
c e C und
d e D
„definiert“ - oder sagen wir mal so: mal hingeschrieben *g*

Also man sollte schon ein paar gute Zahlentupel anstelle der Mengen hinschreiben Siehe auch die Beispiele der Wikipedia.

Hm, also aus dem Stegreif wird das jetzt nix…
Immerhin soll der eine Satz (A1nA2)xB = … verallgemeinert (+ bewiesen) werden zu (A1nA2)x(B1nB2)=(A1xB1)n(A2xB2)

Bin gerade ein bisschen verwirrt und hoffe auf Ratschläge /
Denkanstöße…

…nicht nachts zu dieser Unzeit

HTH
mfg M.L.

[Martin]

Hallo Daria,

wieviele Möglichkeiten gibt es, einen Kuchen an vier Kinder A, B, C, D zu verfüttern? 16: Keiner bekommt was von dem Kuchen, nur A bekommt davon, C und D bekommen davon (aber nicht A und B), alle bekommen was davon… das waren jetzt ein paar Beispiele. Alle 16 Möglichkeiten kannst Du in einer Tabelle wie folgt darstellen:

D C B A 
=============
- - - - 0 
- - - x 1
- - x - 2
- - x x 3
- x - - 4
- x - x 5
- x x - 6
- x x x 7
x - - - 8
x - - x 9
x - x - 10
x - x x 11
x x - - 12
x x - x 13
x x x - 14
x x x x 15

Ein „x“ bedeutet: Derjenige bekommt was von dem Kuchen; und ein „-“ bedeutet, daß er hungrig bleiben muss. Mit den Zahlen rechts habe ich die 16 Möglichkeiten durchnummeriert. Wie Du siehst, bildet das Schema aus den „x“ und „-“ zeilenweise gerade die Dualdarstellung der rechts stehenden Zahlen.

Aber wozu soll das jetzt gut sein? Warte, gleich wird es Dir klar! Du erkennst nämlich , daß es clever ist, folgende Mengen zu definieren:

A := {1, 3, 5, 7, 9, 11, 13, 15}
B := {2, 3, 6, 7, 10, 11, 14, 15}
C := {4, 5 ... (selbst komplettieren)
D := {8, 9 ...

Verstehst Du, wie sich diese Mengen aus der obigen Tabelle ergeben, und welcher Sinn dahintersteckt? Jede der Zahlen 1 bis 15 repräsentiert genau eine Schnittmenge, wobei alle überhaupt möglichen Kombinationen von A, B, C, D garantiert erfasst sind, d. h. es gibt keine „Schlupflöcher“. Beispiele: 1 = A, 3 = AnB, 10 = BnD, 13 = AnCnD, 15 = AnBnCnD. Das ist der Clou an der Sache.

Was nun zu tun ist, ist klar: AxB und CxD bilden! Dazu malst Du zwei Tabellen. Die AxB-Tabelle sieht einfach so aus:

 | 1 3 5 7 9 11 13 15
---+-------------------------
 2 | 
 3 |
 6 |
 7 |
10 |
11 |
14 |
15 |

Jede der 8² = 64 Tabellenzellen steht für ein Element von AxB.

Die CxD-Tabelle überlegst Du Dir bitteschön selbst. Sobald Du beide Tabellen auf dem Papier stehen hast, guckst Du, welche Zellen in beiden auftauchen. Markiere alle mit einem ‚x‘. Am Schluß solltest Du genau 16 'x’e in jeder der beiden Tabellen stehen haben. Sie kennzeichnen die Elemente von (AxB)n(CxD).

So, und den Rest überlasse ich Dir! Übrig bleibt noch festzustellen, welche Elemente sich in AnC und BnD befinden (es sind je vier Stück), und diese beiden Schnittmengen in Zusammenhang mit dem ‚x‘-Muster in den Tabellen zu bringen. In dem Moment, in dem Dir ein Licht aufgeht, hast Du die Aufgabe dann auch schon gelöst, und zwar mathematisch einwandfrei!

Viel Spaß!

Mit freundlichem Gruß
Martin

[daria03_3ebe35]

Wow, das hat mir echt weitergeholfen! Genial! Danke schön!
Du bist nicht zufällig Autor eines Lehrbuches? *zwinker*

Zwar hab ich in den beiden Tabellen genau erkannt, dass die von mir zu beweisende Gleichung stimmt - aber ehrlich gesagt ist mir noch immer nicht klar, *wieso* diese gilt.

Kann man sie auch noch anders - ohne explizite Mengen wie z.b. A = {1, 2, …} anzugeben - herleiten?
Mit Rechenregeln für das Vektorprodukt vielleicht? Wobei - jene müssten auch erstmal „bewiesen“ werden.
*grübel*

LG
Daria

[Martin]

Nochmals hallo, Daria,

Du bist nicht zufällig Autor eines Lehrbuches?

nein, aber was nicht ist, kann ja noch werden…

Zwar hab ich in den beiden Tabellen genau erkannt, dass die
von mir zu beweisende Gleichung stimmt - aber ehrlich gesagt
ist mir noch immer nicht klar, *wieso* diese gilt.

Nun, zunächst gilt sie einfach deshalb, weil Du ihre Gültigkeit bewiesen hast. Aber ich denke, Du meinst eigentlich etwas anderes, nämlich ob man sich über den doch etwas „spröden“ Beweis hinausgehend irgendwie auch eine anschauliche Vorstellung davon machen kann, was diese komische Gleichung „eigentlich“ besagt.

Angenommen, Du bist die Betreiberin von zwei Internet-Kontaktbörsen namens „FunFlirt“ und „ChatAndMore“, über die männliche Teilnehmer Kontakte zu weiblichen herstellen können, und umgekehrt (die Kombinationen „Mann sucht Mann“ und „Frau sucht Frau“ sollen ausgeschlossen bleiben).

Wie muß das Bild in Deinem Chefzimmer, das Dein Business repräsentiert, aussehen? Na, so:

http://mitglied.lycos.de/sabinchenm/ABCD/ABCD.jpg

Der linke, rote Kreis steht für FunFlirt, der rechte, schwarze für ChatAndMore. Die grauen oberen Hälften sind die Mengen der männlichen Teilnehmer, die unteren Hälften die der weiblichen. Im gelben Überlappbereich befinden sich die Teilnehmer, die in Kontaktbörsen Mitglied sind.

Jetzt definieren wir die Mengen A, B, C, D wie folgt:

A := männliche FunFlirt-Teilnehmer
B := weibliche "
C := männliche ChatAndMore-Teilnehmer
D := weibliche "

Dann sind

AxB = die Menge aller möglichen Paare, die sich über FunFlirt kennenlernen können
CxD = die Menge aller möglichen Paare, die sich über ChatAndMore kennenlernen können

sowie

G := (AxB)n(CxD) = die Menge aller möglichen Paare, die sich sowohl über FunFlirt als auch über ChatAndMore kennenlernen können

Da beide Kontaktbörsen gut laufen, sind A, B, C, und D große Mengen, und entsprechend sind AxB und CxD verflucht groß. Wenn A 5000 Frauen enthält und B 6000 Männer, dann enthält AxB stolze 5000 * 6000 = 30 Millionen Elemente!

Nun passiert folgendes: Du interessierst Dich aus irgendeinem (z. B. marketingtechnischen) Grund für den „gelben Bereich“, genauer: Du willst alle überhaupt möglichen „gelben Paare“ (= die Elemente der Menge G) aufgelistet haben! Dann hast Du zwei Möglichkeiten. Erstens: Du läßt Dir von der Datenbank alle 30 Millionen überhaupt möglichen AxB-Paare, sowie alle 25 Millionen überhaupt möglichen CxD-Paare ausspucken, und checkst anschließend ab, welche Paare davon identisch sind (= Bildung von (AxB)n(CxD)) – dies sind die „gelben“ G-Paare. Es könnten z. B. 900 Stück sein.

Diese Vorgehensweise würde aber wegen der beiden gigantisch großen Paarlisten einen hohen Rechenaufwand erfordern, wäre also „teuer“. Geht es besser? Ja! Zweite Möglichkeit: Du läßt Dir zuerst von der Datenbank AnC sowie BnD ausgeben, also alle „Beide-Börsen“-Männer und alle „Beide-Börsen“-Frauen. Das geht fix, denn diese beiden Mengen sind relativ „klein“; sie haben jeweils nur 30 Elemente. Anschließend brauchst Du beide bloß noch zu (AnC)x(BnD) verkartesisieren, und schwupps hast Du ebenfalls die 30 * 30 = 900 Paare umfassende G-Menge!

Es leuchtet sofort ein, dass beide Methoden zum selben Ergebnis – der Menge G aller überhaupt möglichen „gelben“ Paare – führen. Und damit hast Du Dir gerade den zu beweisenden Satz vor Augen geführt! Seine „Weisheit“ ist also eigentlich banal; der Satz besagt quasi, daß beide oben erläuterten Möglichkeiten äquivalent sind: Du mußt G nicht „teuer“ gemäß G = (AxB)n(CxD) berechnen, sondern darfst es Dir gemäß G = (AnC)x(BnD) leicht machen, weil das Ergebnis garantiert dasselbe ist.

Mit freundlichem Gruß
Martin

[daria03_3ebe35]

Auch von mir ein erneutes Hallo!
(Ich hoffe, dieser Beitrag verschwindet nicht in der Versenkung, da das Thema schon so weit nach unten durchgerutscht ist…)

Nun, zunächst gilt sie einfach deshalb, weil Du ihre
Gültigkeit bewiesen hast.

Hat man die Gültigkeit der Gleichung wirklich ganz allgemein und formal bewiesen? Wenn man sich konkrete Mengen definiert, also mit Elementen wie „1“, „2“, … ? „Darf“ man das in einem formalen Beweis? Könnte man nicht dagegen einwenden: für andere Zahlen / Beispiele könnte es nicht gelten…
Was ich damit sagen will, ist: Inwiefern ist dies ein mathematisch korrekter Beweis?
Müssen Beweise nicht „unabhängig von Beispielen“ sein? (Mit Beispiel meine ich die in diesem Fall konkret definierten Elemente, auch wenn sie nach einem ausgeklügelten System definiert wurden.)
Ich dachte immer, man müsste sehr allgemein mit a e A usw. „rechnen“.
Kann das gerade nicht ganz so deutlich ausdrücken und hoffe, du weißt was ich zu sagen versuche

Dann sind

AxB = die Menge aller möglichen Paare, die sich über FunFlirt
kennenlernen können
CxD = die Menge aller möglichen Paare, die sich über
ChatAndMore kennenlernen können

Danke für dieses super-anschauliche Beispiel! )
Sich die Paare, die aus AxB hervorgehen, mal als richtig konkrete „Menschenpaare“ vorzustellen, das finde ich eine echt gute Idee und vielleicht wird mir diese nicht ganz so abstrakte Vorstellung (die ich ab jetzt im Hinterkopf haben werde) bei weiteren, ähnlichen Aufgaben mit dem kartesichen Produkt helfen.
Wirklich klasse! *lob lob lob*

Lg
Daria

[Martin]

Grüß Dich ,

(Ich hoffe, dieser Beitrag verschwindet nicht in der
Versenkung, da das Thema schon so weit nach unten
durchgerutscht ist…)

keine Sorge, bis dahin dauert es noch etwas.

Hat man die Gültigkeit der Gleichung wirklich ganz
allgemein und formal bewiesen? Wenn man sich konkrete
Mengen definiert, also mit Elementen wie „1“, „2“, … ?
„Darf“ man das in einem formalen Beweis? Könnte man nicht
dagegen einwenden: für andere Zahlen / Beispiele könnte es
nicht gelten…

Nein, der Einwand wäre nicht berechtigt, weil die Zahlen eben ganz bestimmte Schnittmengen „codieren“; präziser: weil jede der 15 Zahlen genau eine der 15 überhaupt möglichen Schnittmengen zwischen A, B, C, D „codiert“. Jede Zahl steht also für eine Menge (z. B. ist „13“ also als Menge M₁₃ zu verstehen), für ein Flächenstück des „Kleeblattes“, das die vier ineinandergeschobenen A-, B-, C-, D-Mengenkreise bilden.

Was ich damit sagen will, ist: Inwiefern ist dies ein
mathematisch korrekter Beweis?

Der Beweis ist korrekt, aber – wie ich mittlerweile auch erkannt habe – sperriger als nötig. Man kann es besser machen (s. u.).

Müssen Beweise nicht „unabhängig von Beispielen“ sein? (Mit
Beispiel meine ich die in diesem Fall konkret definierten
Elemente, auch wenn sie nach einem ausgeklügelten System
definiert wurden.)

Der Beweis sieht „beispielabhängig“ aus, aber er ist es in Wirklichkeit nicht, aus dem oben genannten Grund (die Zahlen sind als „Codes“ für Mengen zu verstehen).

Hier eine andere Variante, die uns beiden besser gefällt/gefallen wird :

Allgemein gilt (M, X beliebige Mengen, „“ = „ohne“):

M = (M\X) u (MnX)

Also darf man in schreiben:

A = (A\C) u (AnC)
B = (B\D) u (BnD)
C = (C\A) u (CnA)
D = (D\B) u (DnB)

Daraus folgt:

AxB =
(A\C) x (B\D)
u
(A\C) x (BnD)
u
(AnC) x (B\D)
u
(AnC) x (BnD)
u

sowie

CxD =
(C\A) x (D\B)
u
(C\A) x (DnB)
u
(CnA) x (D\B)
u
(CnA) x (DnB)
u

(fettmarkiert sind die identischen Teile!)

und daraus resultiert die Schnittmenge zu

(AxB) n (CxD) = (AnC) x (BnD)

Fertig! Klein, fein und genauso richtig.

Sich die Paare, die aus AxB hervorgehen, mal als richtig
konkrete „Menschenpaare“ vorzustellen,

Ja, da fühlen sich die Damen in ihrem Element… *lächel*.

Mit freundlichem Gruß
Martin

[daria03_3ebe35]

Danke! (und noch eine Frage…)
Hallo Martin,
ich wollte mich nochmals bei dir dafür bedanken, dass du mir so geduldig Rede und Antwort stehst - großes Lob!

Gestern ist bei mir eine weitere Frage aufgetaucht (soll ich die in diesem „Thread“ stellen oder lieber ein eigenes Thema dafür eröffnen? Hmm, es hat ja mit dem kartesischen Produkt zu tun, geht aber darüber hinaus.)

Und zwar handelt es sich um die Relation zwischen zwei Mengen.
(Hab ich das soweit richtig verstanden, dass sie binär heißt, wenn es sich um eine Relation zwischen zwei Mengen handelt und n-äre Relation, wenn es sich um n Mengen handelt?
Soweit - so gut, ich glaube auch verstanden zu haben, was es mit der Relation auf sich hat, dass sie eine Teilmenge ist (des kartesischen Produkts jener Mengen?).

Das ist also der Stand der Dinge, was ich bisher verinnerlicht hab
Nun meine Frage:

Wie kann man sich die Komposition zweier Relationen vorstellen?
Hast du dafür zufällig auch eine Veranschaulichung parat?
Und was ist, wenn man gleich mehrere Relationen verkettet (heißt das so?) ?

Denn ich denke, erst wenn ich wirklich verstanden habe, was überhaupt diese Komposition ist, dann kann ich weitermachen mit „invers“, „asymmetrisch“ etc…

LG
Daria