Das "Heiratsproblem"

19.10.2008, 19:48

DarthVader

Das "Heiratsproblem"

nabend zusammen,

so nun haben wir folgendes problem bezüglich des sog. "heiratsproblem"

Seien $\begin{eqnarray*} X, Y \end{eqnarray*}$ endliche Mengen, für jedes Element $\begin{eqnarray*} x \in X \end{eqnarray*}$ sei weiter eine Teilmenge $\begin{eqnarray*} Y_x \subset Y \end{eqnarray*}$ gegeben, so dass folgende Bedingung erfüllt ist:

Für jede Teilmenge $\begin{eqnarray*} X' \subset X \end{eqnarray*}$ gilt:

$\begin{eqnarray*} \mid X' \mid \leq \mid \bigcup_{x \in X'} Y_x \mid \end{eqnarray*}$

Dann gibt es eine injektive Abbildung $\begin{eqnarray*} f:X \rightarrow Y \end{eqnarray*}$ mit $\begin{eqnarray*} f(x) \in Y_x \end{eqnarray*}$ für alle $\begin{eqnarray*} x \in X \end{eqnarray*}$

wir haben so eine ahnung davon zu zeigen, dass es eine eindeutige zuweisung für jedes x element X auf ein individuelles y geben muss, damit die bedingung erfüllt ist. daraus müsste folgen, dass eine injektive abbildung existiert. unser problem besteht nun darin dies formal auszudrücken.

19.10.2008, 20:41

mYthos

Auf diesen Beitrag antworten »

Leider auch dort "XY-ungelöst" ..

mY+

19.10.2008, 20:47

DarthVader

Auf diesen Beitrag antworten »

ja entschuldigt, wir hatten das erst später gesehen......aber irgendwie hat ja keiner nen kleinen tipp

20.10.2008, 12:59

Jacques

Auf diesen Beitrag antworten »

Hallo,

Ich bin mir nicht sicher, ob er weiterführt, aber mein Ansatz wäre folgender:

M. E. muss man die Abbildung f wirklich „konstruieren“ und kann nicht etwa zeigen, dass jede Funktion dieser Art injektiv ist oder umgekehrt jede injektive Funktion ein x auf ein y aus Yx abbildet.

Ich würde bei der Forderung anfangen, dass f(x) in Yx liegt, und dann versuchen die Injektivität herzustellen:

Eine Funktion g, die jedem Yx einen „Repräsentanten“ aus Yx zuordnet, existiert nach dem Auswahlaxiom. [alle Yx müssen nichtleer sein, ansonsten ist die vorgegebene Mächtigkeitsbeziehung nicht erfüllt]

Wenn man diese Funktion dann mit der Funktion h

$\begin{eqnarray*} h \colon \, X \mapsto \{Y_x \,|\, x \in X \}\quad x \mapsto Y_x \end{eqnarray*}$

verkettet, dann erhält man schon eine Funktion, die jedem x aus X ein f(x) aus Yx zuordnet. Wobei die Funktion nicht zwangsläufig injektiv ist, weil die Mengen Yx nicht disjunkt zu sein brauchen und g dann denselben „Repräsentanten“ mehrfach auswählen kann.

Man müsste g so verändern, dass die Repräsentantenwahl eindeutig ist. Evtl. kann man einmal „benutzte“ Repräsentanten ausschließen -- und dann die Eigenschaft

$\begin{eqnarray*} |X^{\prime}| \leq \left| \bigcup_{x \in X^{\prime}} Y_x \right| \end{eqnarray*}$

benutzen, um zu zeigen, dass für jedes Yx immer noch ein Repräsentant übrig ist.

Denn es gilt anscheinend: Zu zwei Elementen x1 und x2 aus X kann man ein y1 aus Yx1 und ein y2 aus Yx2 finden, sodass y1 und y2 nicht übereinstimmen.

Yx1 und Yx2 müssen disjunkte Einermengen sein, oder aber mindestens eine der beiden Mengen muss mehr als ein Element haben. In jedem Fall stehen genügend „Kandidaten“ zur Verfügung, damit y1 und y2 nicht identisch sind.

Diese Eigenschaft gilt dann IMHO nicht nur für je zwei Mengen, sondern man kann sie ausweiten, sodass auch beim Ausschließen der „benutzten“ Repräsenanten immer noch genügend davon übrig bleiben, um jedem Yx einen solchen zuzuweisen.

Aber mir fehlt leider noch die Idee, wie man die „Konstruktion“ der injektiven Repräsentantenfunktion h machen kann...

20.10.2008, 13:54

papahuhn

Auf diesen Beitrag antworten »

RE: Das "Heiratsproblem"
Mit dem Auswahlaxiom an endliche Mengen heranzugehen ist wohl etwas hart.
Das Heiratsproblem habe ich in der Graphentheorie kennengelernt. Die Lösung ist eine Induktion nach $\begin{eqnarray*} |X'| \end{eqnarray*}$ in zwei Fällen:

1. $\begin{eqnarray*} \mid X' \mid = \mid \bigcup_{x \in X'} Y_x \mid \end{eqnarray*}$

2. $\begin{eqnarray*} \mid X' \mid < \mid \bigcup_{x \in X'} Y_x \mid \end{eqnarray*}$

20.10.2008, 22:35

Urza

Auf diesen Beitrag antworten »

Die Formulierung des Satzes kann meiner Meinung nach zunächst etwas verwirren, jedenfalls habe ich mich beim ersten Ansehen gefragt, was die Rolle der Menge X eigentlich genau ist. Man kann ihn auch so (offenbar äquivalent) formulieren:

$\begin{eqnarray*} \text{Sei } Y \text{ eine endliche Menge und es seien } n\in\mathbb{N} \text{ Teilmengen } Y_i \subset Y \left( 1\leq i \leq n \right) \text{definiert,} \end{eqnarray*}$ $\begin{eqnarray*} \text{sodass für alle } 1\leq i \leq n \text{ jeweils } i \text{ davon zusammengenommen mindestens } i \text{ Elemente haben.} \end{eqnarray*}$ $\begin{eqnarray*} \text{Dann lassen sich } n \text{ paarweise verschiedene Elemente } x_1,...,x_n\in Y \text{ finden, sodass } x_i\in Y_i \text{ für alle } 1\leq i \leq n \end{eqnarray*}$

So ist es doch schon mal wesentlich angenehmer zum Lesen. Finde ich jedenfalls.

20.10.2008, 22:49

papahuhn

Auf diesen Beitrag antworten »

Zitat:

Original von Urza
Die Formulierung des Satzes kann meiner Meinung nach zunächst etwas verwirren, jedenfalls habe ich mich beim ersten Ansehen gefragt, was die Rolle der Menge X eigentlich genau ist.

$\begin{eqnarray*} X \end{eqnarray*}$ sind Frauen, $\begin{eqnarray*} Y \end{eqnarray*}$ sind Männer. Für $\begin{eqnarray*} x \in X \end{eqnarray*}$ ist $\begin{eqnarray*} Y_x \end{eqnarray*}$ die Menge der männlichen Freunde von $\begin{eqnarray*} x \end{eqnarray*}$ . Ziel ist es, jede Frau mit einem ihrer Freunde zu verheiraten.

20.10.2008, 23:03

DarthVader

Auf diesen Beitrag antworten »

erst mal vielen vielen dank an euch alle für die antworten. mein kommilitone meinte, dass induktion wohl das richtige stichwort sei.

bei 1.) haben wir überlegt dies durch einen widerspruch zu erreichen, bei 2.) halt durch einen induktionsbeweis.

wir werden uns morgen abend zusammensetzen und anschließend unsere vorgehensweise hier posten

20.10.2008, 23:06

papahuhn

Auf diesen Beitrag antworten »

Ich hab das unklar ausgedrückt. Die Fallunterscheidung ist in jedem Schritt der Induktion zu machen.

Neue Frage »

Antworten »

Das "Heiratsproblem"

Verwandte Themen