Heiratsproblem < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:21 Di 21.10.2008 | | Autor: | Conker |
| Aufgabe | Seien X, Y endliche Mengen, für jedes Element x [mm] \in [/mm] X sei weiter eine Teilmenge [mm] Y_{x} \subseteq [/mm] Y gegeben, so dass folgende Bedingung erfüllt ist:
Für jede Teilmenge X' [mm] \subseteq [/mm] X gilt:
|X'| [mm] \le [/mm] | [mm] \bigcup_{x \in X'}^{} Y_{x} [/mm] |.
Dann gibt es eine injektive abbildung f : X [mm] \to [/mm] Y mit f(x) [mm] \in Y_{x} [/mm] für alle x [mm] \in [/mm] X. |
Irgendwelche Vorschläge?
Ich weiß aus einer vorherigen Aufgabe, dass für eine m-elementige Teilmenge X' einer n-elementigen Menge X gilt: |X'| = [mm] \vektor{n \\ m}, [/mm] falls das irgendwie weiterhilft.
Ich scheitere allerdings daran, mir die Vereinigung von [mm] Y_{x} [/mm] vorzustellen. Kann mir das jemand anschaulich erklären? Wie mir das wiederum weiterhelfen soll, weiß ich allerdings auch nicht.
Wie soll ich hier vorgehen? Verstehe momentan noch nicht einmal die Aufgabe so richtig.
In einer weiteren Teilaufgabe heißt es: Wieso heißt diese Aufgabe auch "das Heiratsproblem"? Interpretieren Sie [mm] Y_{x} [/mm] als die "zu x befreundeten y [mm] \in [/mm] Y". - ???
Unter Heiratsproblem habe etwas im Netz gefunden, allerdings nichts, was auf diese Aufgabe passt.
Für Hilfe wäre ich sehr dankbar.
/Conker
PS: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Seien X, Y endliche Mengen, für jedes Element x [mm]\in[/mm] X sei
> weiter eine Teilmenge [mm]Y_{x} \subseteq[/mm] Y gegeben, so dass
> folgende Bedingung erfüllt ist:
>
> Für jede Teilmenge X' [mm]\subseteq[/mm] X gilt:
>
> |X'| [mm]\le[/mm] | [mm]\bigcup_{x \in X'}^{} Y_{x}[/mm] |.
>
> Dann gibt es eine injektive abbildung f : X [mm]\to[/mm] Y mit f(x)
> [mm]\in Y_{x}[/mm] für alle x [mm]\in[/mm] X.
> Irgendwelche Vorschläge?
> Ich scheitere allerdings daran, mir die Vereinigung von
> [mm]Y_{x}[/mm] vorzustellen.
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
die Menge X ist endlich, also etwa [mm] X=\{x_1, x_2, ..., x_n\}.
[/mm]
Zu jedem der [mm] x_i \in [/mm] X gehört eine Teilmenge [mm] Y_{x_i} [/mm] von Y.
Also
zu [mm] x_1 [/mm] gehört [mm] Y_{x_1}
[/mm]
zu [mm] x_2 [/mm] gehört [mm] Y_{x_2}
[/mm]
[mm] \vdots
[/mm]
zu [mm] x_n [/mm] gehört [mm] Y_{x_n}.
[/mm]
Um gleich mal auf die Sache mit dem Heiraten zu sprechen zu kommen:
Du kannst es Dir so vorstellen, daß in der Menge X n heiratslustige Freundinnen versammelt sind, und in der Menge Y irgendeine Anzahl von heiratsfähigen Männern.
Die Frauen suchen sich Männer aus, die ihnen gefallen.
In der Menge [mm] Y_{x_i} [/mm] sind nun alle Männer versammelt, die für die Frau [mm] x_i [/mm] zum Heiraten infrage kämen.
Die Konstellation ist nun so, daß, wenn sich irgendwelche k der n Frauen zusammentun und die Männer, die für eine von ihnen infrage kommen würde, auflisten würden, die Liste mindestens k Namen enthalten würde.
Beispiel: [mm] x_3, x_4 [/mm] und [mm] x_7 [/mm] betrachten die Menge [mm] Y_{x_3}\cup Y_{x_4} \cup Y_{x_7}. [/mm] Sie stellen fest, daß [mm] Y_{x_3}\cup Y_{x_4} \cup Y_{x_7} [/mm] 3 oder mehr als 3 Männer enthält.
Das freut sie, denn andernfalls könnt's ja gar nicht klappen, daß jede einen Mann heiratet, der ihr auch gefällt, und es würde Streit und Tränen bei den Frauen geben, So besteht immerhin Hoffnung.
Das gilt nun für alle möglichen Mengen X' von Frauen, die man aus der Menge X zusammenstellen kann.
Jetzt zur injektiven Funktion f mit den gegebenen Bedingungen.
Zeigen sollst Du, daß es unter den gegebenen Umständen einzurichten ist, daß alle Frauen glücklich zu verheiraten sind:
man bekommt es so hin, daß jede einen Mann heiratet, der ihr auch gefällt, keine zwei Freundinnen müssen sich einen Mann teilen (das wäre rein rechtlich ja auch gar nciht möglich), so daß am Ende zumindest die Frauen zufrieden sind.
Einen Beweis hab ich im Moment nicht in der Tasche.
Ich bin mir aber in höchstem Maße sicher, daß das per vollständige Induktion über dieDabei kommt man ja oft auf Ideen, wie#s allgemein zu bewerkstelligen ist.
Gruß . Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:41 Di 21.10.2008 | | Autor: | Conker |
Danke für die ausführliche Veranschaulichung, ich denke, jetzt habe ich die Fragestellung gut verstanden.
Aus der Bedingungen entnehme ich nun, dass |X| [mm] \le [/mm] |Y|, da die Bedingung für jede Teilmenge X' [mm] \subseteq [/mm] X, also auch für X' = X selbst gilt: |X| [mm] \le [/mm] $ [mm] \bigcup_{x \in X}^{} Y_{x} [/mm] $ [mm] \le [/mm] |Y|, da [mm] Y_{x} \subseteq [/mm] Y. Das ist zumindest eine notwendige Bedingung für eine injektive Abbildung f : X [mm] \to [/mm] Y. Als Alternativaufgabe ist gefordert zumindest zu zeigen, dass die gegebene Bedingung notwendig für die Existenz einer solchen Abbildung ist. Das wäre damit denke ich getan, oder?
Nun ist noch zu zeigen, dass |X| [mm] \le |Y_{x}|, [/mm] denn dann gibt es auch eine Abbildung in der jedes x [mm] \in [/mm] X auch ein f(x) [mm] \in Y_{x} [/mm] findet, richtig?
Nur wie zeige ich das?
Vielleicht hat ja jemand einen Ansatz bzw. kann mir schon mal bestätigen, dass ich zumindest auf dem richtigen Weg bin.
/Conker
|
|
|
| |
|
> Danke für die ausführliche Veranschaulichung, ich denke,
> jetzt habe ich die Fragestellung gut verstanden.
>
> Aus der Bedingungen entnehme ich nun, dass |X| [mm]\le[/mm] |Y|, da
> die Bedingung für jede Teilmenge X' [mm]\subseteq[/mm] X, also auch
> für X' = X selbst gilt: |X| [mm]\le[/mm] [mm]\bigcup_{x \in X}^{} Y_{x}[/mm]
> [mm]\le[/mm] |Y|, da [mm]Y_{x} \subseteq[/mm] Y. Das ist zumindest eine ,
> notwendige Bedingung für eine injektive Abbildung f : X [mm]\to[/mm]
> Y. Als Alternativaufgabe ist gefordert zumindest zu zeigen,
> dass die gegebene Bedingung notwendig für die Existenz
> einer solchen Abbildung ist. Das wäre damit denke ich
> getan, oder?
Hallo,
ja.
>
> Nun ist noch zu zeigen, dass |X| [mm]\le |Y_{x}|,[/mm]
Das wird Dir nicht gelingen, denke ich:
nehmen wir [mm] X:=\{A, S}, Y=\{J, G, F, T\}, Y_A=\{J\}, Y_G=\{G\}
[/mm]
Die erfüllen die in der Aufgabe an die Mengen gestellte Bedingung.
Es ist aber |X| > [mm] |Y_A| [/mm] und |X| > [mm] |Y_B| [/mm]
Gruß v. Angela
Ich meine wie bereits erwähnt, daß Du [mm] \ne [/mm] Induktion machen mußt.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:36 Di 21.10.2008 | | Autor: | Conker |
Ja, das mein Ansatz irgendwie Murks ist, ist mir auch gerade aufgefallen.
Man verzeihe mir die vielleicht naive Frage, aber ich bin Erstsemester und das ist der erste Übungszettel und ich... naja, wie mache das mit der Induktion?
|
|
|
| |
|
> Man verzeihe mir die vielleicht naive Frage, aber ich bin
> Erstsemester und das ist der erste Übungszettel und ich...
> naja, wie mache das mit der Induktion?
Hallo,
bezieht sich Deine Frage darauf, wie  vollständige Induktion allgemein geht?
das kannst Du in obigem Link oder recht schön auch bei der Wikipedia nachlesen.
Im speziellen Fall: wie gesagt habe ich noch keine Lösung in der Tasche.
Erstmal würde man auf jeden Fall zeigen, daß die Sache stimmt, wenn X nur ein Element enthält.
Dann nimmt man an, die Behauptung sein gezeigt für Mengen X mit k Elementen.
Unter dieser Voraussetzung versucht anschließend zu zeigen, daß sie dann auch gilt, wenn X k+1 Elemente enthält.
Mal 'ne Idee (es ist nur eine Idee, ich weiß nicht, ob man damit zum Ziel kommt)
X enthalte die Elemente [mm] x_1, [/mm] ..., [mm] x_k, x_{k+1} [/mm] und die Voraussetzungen gelten.
Dann finde ich eine injektive Abbildung f von X \ [mm] \{ x_{k+1}\} [/mm] in der geforderten Art und Weise. (Das sichert die Induktionsvoraussetzung)
Schauen wir nun die Menge [mm] Y_{x_{k+1}} [/mm] an. Wenn [mm] Y_{x_{k+1}} [/mm] \ [mm] \{f(x_1),...,f(x_k)\} [/mm] nicht leer ist, brauch ich ja einfach bloß [mm] x_{k+1} [/mm] eins der verbleibenden Elemente als "Ehemann" zuzuweisen, und schon ist die auf ganz X erweiterte injektive Abbildung fertig.
Wenn nun aber [mm] Y_{x_{k+1}} [/mm] \ [mm] \{f(x_1),...,f(x_k)\} [/mm] leer ist, muß man überlegen, wie man sich aus der Affäre ziehen kann.
Man müßte dann zeigen können, daß in irgendeiner der Mengen [mm] Y_x [/mm] noch ein "Mann" übrig ist, den man einer der Frauen [mm] x_1, ...,x_k [/mm] geben kann, so daß der "freiwerdende" für [mm] x_{k+1} [/mm] zur Verfügung steht.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 22:54 Di 21.10.2008 | | Autor: | Conker |
Ha!
Ich glaube, ich habe eine genial Lösung gefunden (ich hoffe mal, da ist nicht irgendwo ein Stolperstein versteckt und es sieht mir so verzwickt aus, als könnte da tatsächlich einer sein. Also wenn jemand noch Zeit hat, sich das anzuschauen, ich wäre sehr sehr sehr sehr dankbar, dafür, weil ich das bis morgen haben muss).
Aaaaaalso:
Ich bezeichne die Menge [mm] Y_{x_{n}} [/mm] als Liste der potentiellen Ehemänner für [mm] x_{n}
[/mm]
Vereinfachen wir die Bedingung, sodass wir nun annehmen: |X'| = | $ [mm] \bigcup_{x \in X'}^{} Y_{x} [/mm] $ |.
Das bedeutet, dass die Listen einer beliebigen Menge von Frauen X' genau soviele Kandidaten aufweisen, wie es Frauen in X' gibt. Daraus folgt dann, dass jede Frau nur einen Kanditaten auf Ihrer Liste hat und es folgt auch, dass die Anzahl der Frauen in X der Anzahl der Kandidaten dieser Frauen entspricht.
Da nun jede Frau nur einen Kandidaten auf der Liste hat und es für alle Frauen zusammen genausoviele Kandidaten gibt wie Frauen, folgt daraus, dass jede Frau einen anderen Kandidaten hat.
Eine injektive Abbildung ist unter diesen Voraussetzungen natürlich möglich.
Nehmen wir nun an, eine beliebige Frau [mm] x_{i} [/mm] hätte einen Kanditen mehr als alle anderen (in diesem Fall 2). So ist für jede Teilmenge X'' von X' für die gilt: [mm] x_{i} \not\in [/mm] X'', die oben angenommene Bedingung identisch.
Für alle x [mm] \in [/mm] X'' gibt es damit für diesen Fall ebenfalls eine injektive Abbildung. Insbesondere bleibt festzuhalten, dass alle Frauen bis auf [mm] x_{i} [/mm] immer noch unterschiedliche Kandidaten haben.
Für die Teilmengen X'' von X' für die dagegen gilt: [mm] x_{i} \in [/mm] X'' verändert sich die oben angenommene Bedingung zu:
|X'| + 1 = | $ [mm] \bigcup_{x \in X'}^{} Y_{x} [/mm] $ |,
da diese Teilmenge aus irgendeiner Anzahl von Frauen besteht (die alle nur einen Mann auf der Liste haben) und eben jener Frau, die Zwei Männer auf der Liste hat. Nun folgt aus der Tatsache, dass einerseits aus jeder Teilmenge X' genau ein Kandidat mehr hervorgeht und dass andererseits alle Frauen mit Ausnahme von [mm] x_{i} [/mm] mit Sicherheit unterschiedliche Kandidaten haben, dass "der eine Mehr" in jeder Konstellation der ist, der auf der Liste von [mm] x_{i} [/mm] steht, somit [mm] x_{i} [/mm] auf jeden Fall auch einen Kandidaten abbekommt, somit eine injektive Abbildung wiederum möglich ist.
Bleibt festzuhalten:
A) Für jede Teilmenge X'' von X' für die gilt: [mm] x_{i} \not\in [/mm] X'', gilt: |X'| = | $ [mm] \bigcup_{x \in X'}^{} Y_{x} [/mm] $ |.
[mm] \Rightarrow [/mm] es gibt eine injektive Abbildung.
B) Für jede Telmenge X'' von X' für die gilt: [mm] x_{i} \in [/mm] X'', gilt: |X'| + 1 = | $ [mm] \bigcup_{x \in X'}^{} Y_{x} [/mm] $ |.
[mm] \Rightarrow [/mm] es gibt eine injektive Abbildung.
Nun könnten wir weiter so verfahren und einer beliebigen Frau erneut einen weiteren Kandidaten auf die Liste schreiben.
Die beiden angegebenen Fälle A) und B) werden dann wieder in jeweils zwei Fallunterscheidungen einbezogen, bei denen dann bei A) in einem Fall +1 auf die linke Seite der Gleichung hinzuaddiert wird und in dem anderen Fall nicht. Genauso wird bei B) in einem fall +1 auf die linke Seite der Gleichung hinzuaddiert wird und in dem anderen Fall nicht.
Jedesmal geht daraus dann hervor, dass es eine injektive Abbildung gibt.
Und wir sehen also, dass sich die Bedingung entweder nicht verändert, oder aber sich die linke Seite der Gleichung um +1 erhöht. Es ist also die linke Seite der Gleichung entweder gleich der Rechten, oder man muss sie mit +1 addieren, um gleich der rechten Seite zu sein, ist also ohne Addition um 1 kleiner (!!!). Nach mehrmaligem Durchführen ist sie für einen beliebig gewählte Menge X' also entweder immer noch gleich oder aber um eine beliebige natürliche Zahl kleiner und stets folgt die Injektivität.
Schreiben wir also diesen Sachverhalt, aus dem stets die Injektivität folgt als:
|X'| [mm] \le [/mm] | $ [mm] \bigcup_{x \in X'}^{} Y_{x} [/mm] $ |.
q.e.d.
|
|
|
| |
|
Hallo,
ich bin mir nicht sicher, ob ich heute soviel Zeit am Stück haben werde, daß ich Deinen Beweis studieren kann. Wahrscheinlich eher nicht.
Ich habe aber gesehen, daß man ![[]](/images/popup.gif) hier einen Induktionsbeweis findet, welchen ich Dir nicht vorenthalten möchte. (An einer Stelle enthält er einen Druckfehler, es muß dort n-k heißen - Du merkst dann schon, wo das ist.)
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:29 Mi 22.10.2008 | | Autor: | Conker |
Ich denke, das entspricht in etwa dem, was ich jetzt aufgeschrieben habe (glaube ich zumindest, habs nur kurz überflogen). Wenn nicht, ist es jetzt sowieso zu spät.
Was mir noch aufgefallen ist: In dem von dir zitierten Fall ist als Voraussetzung gegeben, dass |X| = |Y|, das war in meiner Aufgabe nicht gegeben.
Danke auf jeden Fall für die Hilfe. :)
/Conker
|
|
|
| |
|
> Was mir noch aufgefallen ist: In dem von dir zitierten Fall
> ist als Voraussetzung gegeben, dass |X| = |Y|, das war in
> meiner Aufgabe nicht gegeben.
Hallo,
ich sehe das nicht. Da steht doch oben auf S.12, daß [mm] |\mathcal{A}'| \le |\mathcal{B}'| [/mm] gelten soll.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:53 Mi 22.10.2008 | | Autor: | Conker |
Also das sehe ich wiederum nicht *g*
Da steht doch:
Sind zwei Mengen a = [mm] \{A_{1}, ... , A_{n},\} [/mm] und b = [mm] \{B_{1}, ... , B_{n},\} [/mm] von je n Elementen gegen [...].
Hast du mir vielleicht nen falschen Link gegeben?
/Conker
|
|
|
| |
|
> Also das sehe ich wiederum nicht *g*
Aber dafür seh' ich jetzt Deins...
(Meins ist 'nen paar Zeilen tiefer).
Du hast also recht. Der Unterschied dürfte aber keine Rolle spielen, denn in dem Buch wird dann ja sogar eine schärfere Aussage bewiesen.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:11 Mi 22.10.2008 | | Autor: | Conker |
... woraus ja aber nicht unmittelbar folgt, dass die schwächere Aussage automatisch auch gilt.
Biespiel hierzu:
Behauptung1: aus a+1=x und b+1=x folgt: a=b -trivial-
Behauptung 2: aus a+1=x und b+1=y folgt: a=b -falsch-
/Conkerchen
|
|
|
| |
|
> ... woraus ja aber nicht unmittelbar folgt, dass die
> schwächere Aussage automatisch auch gilt.
Wenn die starke Aussage gilt, gilt die schwächere automatisch. (Falsche Aussagen kann man natürlich nicht beweisen, und bei 2. wäre ...==> a=b ja falsch.)
So auch hier, was man sieht, wenn man die Voraussetzungen und die Folgen richtig aufschreibt.
Aussage 1:
Seien a,b Zahlen derart, daß es eine Zahl x gibt mit a+1=x und b+1=x.
Dann gilt: a=b.
Aussage 2:
Seien a,b Zahlen derart, daß es Zahlen x,y gibt mit a+1=x und b+1=y.
Dann gilt: a=b oder [mm] a\not=b
[/mm]
Mithilfe von 1. kann ich 2. zeigen:
Es sei also 1. bewiesen,
und es seien a,b Zahlen derart, daß es Zahlen x,y gibt mit a+1=x und b+1=y.
Fall A: x=y
Aus Aussage 1. folgt a=b
Fall B: [mm] x\not [/mm] y ==> [mm] x-1\not=y-1 [/mm] ==> [mm] a\not=b.
[/mm]
Insgesamt erhält man also, daß a=b oder [mm] a\not=b [/mm] folgt. (Wozu man natürlich in Wahrheit keinerlei Beweis benötigt hätte.)
Beim Heiratsproblem: wenn das für eine sehr begrenzte Anzahl Männer (wie im Buch) klappt, klappt es ja erst recht, wenn die Auswahl größer ist.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Mi 22.10.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Aufgabe | Auf der Suche nach einem Beispiel für ein Wissenschaftstheoretisches Seminar bin ich auf das "Heiratsproblem" gestoßen.
Wenn in der Wissenschaft Behauptungen über Gegenstandsbereiche aufgestellt werden sollen...also z.B. über die Menge aller Studierenden, die Menge aller Sprachen usw. werden dazu Aussagesätze formuliert.
Solche Aussagesätze bestehen aus Ausdrücken, aus singulären und generellen Namen für Dinge, über die etwas Wahres und Informatives ausgesagt werden soll.
Ich habe nun gehört, dass in der Mathematik dazu Formulierungen und Behauptungen über den Gegenstandsbereich durchnummeriert werden um sie nicht mit anderen Sätzen der gleichen Abhandlung zu verwechseln.
Satz 1
Satz 2
Satz 3
|
Da ich mit in der Mathematik gar nicht auskenne, wollte ich fragen, ob mir jemand so ein Beispiel nennen kann?
Herzlichen Dank im Voraus,
Ingrid
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:19 Mo 24.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
