Bestimme alle (und nicht nur einige) Partitionen der folgenden Teilmengen {1}, {1, 2} und {1, 2, 3}

Question

Aufgabe:

Bestimme alle (und nicht nur einige) Partitionen der folgenden Teilmengen von \(\mathbb{N}\): {1}, {1, 2} und {1, 2, 3}. Gib auch alle Äquivalenzrelationen auf diesen Mengen an.

Problem/Ansatz:

Zuerst habe ich mir nochmal überlegt, was eine Partition Q überhaupt ist.

* \(Q \subseteq Potenzmenge\:P(\mathbb{N})\)

wenn folgende Bedingungen gelten:

(1) Jedes Elemente von \(\mathbb{N}\) ist in einem Element von Q enthalten.

(2) Zwei Elemente von Q sind entweder gleich oder disjunkt

(3) Jedes Element von Q ist nichtleer

Um mir die P(\(\mathbb{N}\)) leichter aufbauen zu können, habe ich festgelegt {1} = a, {1, 2} = b und {1, 2, 3} = c. Also:

P(\(\mathbb{N}\)) = {{}, a, b, c, {a, b}, {b, c}, {a, c}, {a, b, c}}

! Mir ist aber daraufhin aufgefallen, dass egal welches Q ich probiere zu bilden, (2) wird immer verletzt werden, da die Vereinigung zweiter Elemente von Q nie {} sein wird.

Übersehe ich etwas?

Answer 1

Um mir die P(N) leichter aufbauen zu können, habe ich festgelegt {1} = a, {1, 2} = b und {1, 2, 3} = c. Also:

P(N) = {{}, a, b, c, {a, b}, {b, c}, {a, c}, {a, b, c}}

Das ist falsch.
{a, b} ist nach deiner Definition {{1}, {2}}, aber das ist offensichtlich keine Teilmenge von N. Du meinst bestimmt {1,2}, das wäre aber (a ∪ b).
---
Du suchst alle Partitionen der Menge {1}, die Partitionen sind Teilmengen der Potenzmenge. Bestimme diese also zunächst:
$$ \mathcal{P}(\{1\}) = \{ \emptyset, \{1\}\} $$
Aus dieser Menge musst du nun die nichtleeren Teilmenge auswählen, die die Partitionseigenschaften erfüllt sind:

\( \{ \emptyset \} \) erfüllt diese nicht, denn (1) und (3) ist verletzt.

\( \{ \emptyset, \{1\} \} \) erfüllt diese auch nicht, denn (3) ist verletzt.

Die einzige Partition ist hier also \( \{ \{ 1 \} \} \). Die Mengen in dieser Menge decken alle Elemente von \( \{ 1 \} \) ab, sind sicherlich paarweise disjunkt oder identisch und eine leere Menge ist auch nicht enthalten.
---
Dann für die Menge \( \{1,2 \} \). Die Potenzmenge:$$ \mathcal{P}(\{1,2\}) = \{ \emptyset, \{1\}, \{2\}, \{1,2\}\} $$Wieder suchst du alle nichtleeren Teilmengen dieser Potenzmenge, die die Partitionseigenschaften erfüllen.

Alle Teilmengen, die die leere Menge enthalten fallen wegen (3) raus, z.B. \( \{ \emptyset, \{1\} \} \).

Die Teilmengen \( \{\{1\} \} \) und \( \{ \{2\} \} \) sind wegen (1) keine Partitionen.

\( \{ \{1\}, \{2\} \} \) und \( \{ \{1, 2\} \} \) sind Partitionen, alle Elemente von {1,2} werden abgedeckt, die enthaltenen Mengen sind paarweise disjunkt oder identsich, und die leere Menge ist nicht dabei.

Die Teilmengen \( \{ \{1\}, \{2\}, \{1, 2\} \} \), \( \{ \{1\}, \{1, 2\} \} \) und \( \{ \{2\}, \{1, 2\} \} \) sind wiederum keine Partionen, hier sind die Mengen nicht paarweise disjunkt, d.h (2) ist verletzt.

---

Versuche so mal alle Partionen von {1, 2, 3} zu finden. Den Zusammenhang zwischen Partitionen und Äquivalenzrelationen kennst du?

Comments

Okay, das ganze Beispiel macht auf jeden Fall jetzt mehr Sinn für mich. Jetzt verstehe ich auch von was ich die Potenzmenge nehmen muss.

\(Q \subseteq P(\{1, 2, 3\})\)

\(\{\{1\}, \{2\}, \{3\}\}, \{\{1, 2\}, \{3\}\}, \{\{1\}, \{2, 3\}\}, \{\{2\}, \{1, 3\}\}, \{\{1, 2, 3\}\}\) sind, so weit ich finden konnte, alle Paritionen von \( P(\{1, 2, 3\})\).

Ich bin mir aber nicht ganz sicher, ob ich den Zusammenhang zwischen Partitionen und Äquivalenzrelationen richtig anwenden kann, aber mal sehen.

Für \(Q \subseteq P(\{1\})\) habe ich die Äquivalenzrelation \(R= \{(1, 1)\}\).

Für \(Q \subseteq P(\{1, 2\})\) habe ich \(R= \{(1, 1), (2, 2), (1, 2), (2, 1)\}\).

Für \(Q \subseteq P(\{1, 2, 3\})\) habe ich \(R= \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (3, 2), (1, 3), (3, 1)\}\).

Ist das richtig?

Ich hätte noch eine kleine weitere Frage: wie kann man hier auf Mathelounge am besten { In LaTeX eingeben weil bei sieht das dann so aus "\{\{1\}, \{2\}, \{3\}\}, \{\{1, 2\}, \{3\}\}, \{\{1\}, \{2, 3\}\}, \{\{2\}, \{1, 3\}\}, \{\{1, 2, 3\}\}".

Danke auf jeden Fall für die Hilfe!

---

Die Partitionen hast du richtig bestimmt, sehr gut!

---

Latex: Inline Code wird mit

\( \frac{1}{a} \)

erzeugt. Beispiel: \( \frac{1}{a} \), diese Formel steht im Fließtext. Mit

$$ \int_a^b f(x) \,\textrm{d}x $$

erzeugt man eine eigene Zeile in der die Formel angezeigt wird:
$$ \int_a^b f(x) \,\textrm{d}x $$
---

Das mit den Äq.rel stimmt so nicht ganz.

Jeder Partition ist eindeutig ein Äq.rel zugeordet. Man kann also sagen, es existiert eine Bijektion

{Partitionen von M} <-> {Äquivalenzrelationen auf M}

Wie du sicherlich weißt, zerlegt eine Äquivalenzrelation die Menge in sogenannte Äquivalenzklassen. Die Menge der Äquivalenzklassen ("Faktormenge" o.Ä.) bildet dann eine Partition unserer Menge.

Umgekehrt kann man aus einer gegeben Partition eine Äquivalenzrelation basteln, indem man die Elemente der Partition als Äquivalenzklassen auffasst. Ich erläutere dir das mal an einem Beispiel:

Betrachte die Menge {1,2,3} und die Partition { {1}, {2, 3} }

Die Äquivalenzklassen sind also {1} und {2, 3}. Alle Elemente einer Äquivalenzklasse sind äquivalent zueinander, Elemente unterschiedlicher Klassen sind nicht äquivalent.

Hier wäre also 1 ~ 1, (~ heißt "ist äquivalent zu"), 2 ~ 2, 2 ~ 3, 3 ~ 2 und 3 ~ 3. Als Menge geschrieben wäre das:

R = { (1,1), (2,2), (2,3), (3,2), (3,3) }

Zweites Beispiel: Menge {1, 2} und die Partition { {1}, {2} }.
Hier gilt 1 ~ 1 und 2 ~ 2, mehr nicht. Als Menge geschrieben:

R = { (1,1), (2,2) }

Ich hoffe das ist jetzt etwas klarer. Versuch mal zu den übrigen Partitionen die entsprechende Relation anzugeben.

---

Es ist für mich auf jeden Fall schon klarer, aber eine Sache läuchtet mir noch nicht ganz ein. Die Transitivität ist ja definiert durch:

\((Tra) \: \forall x, y, z \in M : ((x, y) \in R \land (y, z) \in R) \implies (x, z) \in R \)

Angenommen ich nehme die Menge \(\mathbb{N} := \{1, 2\}\), die Partition \(Q := \{\{1\}, \{2\}\}\) und die dazugehörige Äquivalenzrelation \(R:=\{(1, 1), (2, 2)\}\) (wie aus Ihrem Beispiel). Wie kann R eine Äquivalenzrelation sein? Verletzt das nicht die Transitivität? Wenn ich \(x = 1, y = 2, z = 1\) aus \(\mathbb{N}\) nehme, ist \((1, 2) \notin R \land (2, 1) \notin R\). Was genau verstehe ich nicht richtig?

---

Oh. Mir ist während dem Schreiben aufgefallen, warum die Transitivität nicht verletzt ist. Die Conclusio der Implikation \((1, 1) \in R\) ist wahr, und deshalb ist die ganze Aussage richtig. Auch ist es nicht möglich, eine wahre Prämisse und eine falsche Conclusio zu bauen - die einzige Möglichkeit wie die Implikation falsch sein könnte.

---

Für \(Q = \{\{1\}\}\) habe ich weiterhin die \(R=\{(1,1)\}\).

\(Q = \{ \{1\}, \{2\} \} \: R = \{(1, 1), (2, 2)\}\)

\(Q = \{\{1, 2\} \} \: R = \{(1, 1), (1, 2), (2, 1), (2, 2)\}\)

\(Q = \{ \{1\}, \{2\}, \{3\} \} \: R = \{(1, 1), (2, 2), (3, 3)\}\)

\(Q = \{ \{1, 2\}, \{3\} \} \: R = \{(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)\}\)

\(Q = \{\{1\}, \{2, 3\}\} \: R = \{(1, 1), (2, 2), (2, 3), (3, 2), (3, 3)\}\)

\(Q = \{\{2\}, \{1, 3\}\} \: R = \{(1, 1), (1, 3), (3, 1), (3, 3), (2, 2)\}\)

\(Q = \{\{1, 2, 3\}\} \: R = \{(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)\}\)

Passt das? Ich hoffe, es haben sich keine Fehler eingeschlichen und ich habe nichts übersehen!

---

Ja, genau. Das mit der Transitivität hast du dann noch richtig erkannt.

Die Relationen sehen gut aus!

---

Ich verstehe das Thema schon deutlich besser :D.