F ⊆ P(X) sei ein Clutter, wobei X eine endliche Menge. Zeige Ungleichung für die Mächtigkeit von F

Question

Sei X eine endliche Menge mit n := |X|. Wir nennen eine Menge F ⊆ P(X) ein Clutter, wenn für alle A, B ∈ F gilt: Wenn A ⊆ B, dann A = B.

Sei F ⊆ P(X) ein Clutter. Zeigen Sie
 $$|F| ≤\begin{pmatrix} n\\ [\frac{n}{2}] \end{pmatrix}$$

EDIT: Gemeint sind "Floor - Klammern".

Comments

sorry es gibt kleiner Fehler bei den unteren klammarn sie sind keine normale geschweifte Klammern sondern wie es auf dem Bild zu sehen.

---

Hinweis: die Mengen in i) sind F = { {1,2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4} } => |F| = 6. Man erkennt, dass für zwei ungleiche Mengen jede Menge ein Element enthält, das in der anderen Menge nicht enthalten ist. Auf wie viele Arten lassen sich solche Mengen bilden?

---

P für Potenzmenge (?)

In der Aufgabe wird Clutter definiert.

Wie ist Clutter normalerweise definiert bei https://de.wikipedia.org/wiki/Clutter_(Bibliothek) ? Ich vermute mal theoretische Informatik. In welchem Fach macht ihr das?

---

 Sei X eine endliche Menge mit n := |X|. Wir nennen eine Menge F ⊆ P(X) ein Clutter, wenn für alle
A, B ∈ F gilt: Wenn A ⊆ B, dann A = B.

und ja P steht für Potenzmenge.

in theoretische Informatik.

---

@JohnTanner: in (i) hat man F für n = 4 aufgezählt und |F| = 6 gezählt.

Somit hätte man schon eine Art Verankerung. Nämlich

Fall n=4: |F| = 6 und (4 tief 2) = 4! (2! * 2!) = (4*3*2*1)/((2*1*2*1) = 6 . Stimmt.

Warum hast du bei (i) zweielementige Teilmengen von {1,2,3,4} gewählt?

Wäre F = {{1}, {2}, {3}, {4}} kein Clutter?

---

leute könnt ihr bei (ii) helfen weil (i) mich nicht interessiert

---

Ohne (i) ist (ii) wohl nicht zu machen. V.a. falls da vollständige Induktion benutzt werden soll.

Auch wenn du kombinatorisch argumentieren sollst, geht das an einem komkreten Beispiel erst mal besser. Die Verallgemeinerung ist dann in der Regel einfach.

Hier muss man vielleicht noch unterscheiden, ob n gerade oder ungerade ist. Kann auch sein, dass sich das erübrigt, weil man irgendwann einfach sagen, kann dass die Mächtigkeit eines Clutters den grössten Binomialkoeffizienten (n tief ...) nicht übertreffen kann.

---

@Lu: ich denke, dass die Aufgabe eigentlich mit das maximale Clutter formuliert sein müsste. Die leere Menge wäre auch schon eins und hat Mächtigkeit 0

Zur Argumentation: Induktion könnte schwer werden. Ich würde zeigen, dass ein solches Clutter existiert und ein größeres zum Widerspruch führen

Answer 1

zu ii) Es genügt zu zeigen, dass das maximale Clutter n über n/2 Elemente hat. Im maximalen Clutter (mC) hat jede Menge o.B.d.A. gleich viele Elemente, denn:

a) hätte eine mehr Elemente würde mindesten eine andere herausfallen (wir haben ein mC); an i): wäre {1, 2, 3} in F, so würden {1, 2}, {1, 3} und {2, 3} herausfallen - würde keine herausfallen wäre es kein mC

b) hätte eine weniger Elemente, so würde mindesten eine Menge existieren, von der diese Teilmenge ist (wir haben ein mC); an i): wäre {1} in F, so würden {1, 2}, {1, 3} und {1, 4} herausfallen

Jetzt sind die Möglichkeiten Teilmengen mit k Elementen einer Mengen mit n Elementen zu bilden genau n über k. Der Binomialkoeffizient hat aber sein Maximum genau in der Mitte, also max{n über k; k in {0, ..., n}} = n/2.

Damit hat ein mC genau n über n/2 Elemente und somit gilt die Ungleichung.

Bemerkung: ob man für ungerade Fälle nach oben oder unten rundet ist nach Rechenregeln des Binomialkoeffizienten egal, z.B.: {{1},  {2}, {3}} und {{1, 2}, {1, 3}, {2, 3}} sind beide mC von {1, 2, 3}

Sorry für die Formatierung, es ist spät ;)

Comments

@JohnTanner vielen dank für die Antwort ich hätte noch einen Wünsch und zwar wurde angekündigt,dass wir die Aufgabe in meiner Frage mit Hilfe von der obige angehängte Aufgabe lösen sollen.

also wir dürfen annehmen dass die obige Aufgabe schon bewiesen wurde und deren Beweis verwenden(wir haben die obige Aufgabe im tutorium gemacht deswegen dürfen wir verwenden),soweit ich verstanden habe als Unterschied zwischen beiden Aufgabe ist dass bei der obigen Aufgabe die länge von Clutter sich auf n/2 beschränkt jedoch in der frage wurde nicht bestimmt also wie wäre dann der Beweis.

vielen dank im voraus für deine Hilfe.

---

Jetzt sind die Möglichkeiten Teilmengen mit k Elementen einer Mengen mit n Elementen zu bilden genau n über k. Der Binomialkoeffizient hat aber sein Maximum genau in der Mitte, also max{n über k; k in {0, ..., n}} = n/2.

Das ist im Wesentlichen die Aussage die in Aufgabe 2 steckt