Aus Bäumen kann man Holztüren herstellen... und Mengen

Question

Bäume spielen eine außerordentlich wichtige Rolle in der Informatik . . . da sie die Grundlage zur Herstellung jeglicher Form von Holztüren darstellen. Auf Grund der im vergangenen Jahr stark gestiegenen Nachfrage an Holztüren ist die Leitung der Türenmanufaktur IKC 2001 am aktuellen Bestand an Bäumen interessiert. Die Preisklasse einer Holztür wird natürlich maßgeblich von der Qualität des verwendeten Baums beeinflusst.

Die Bäume B_k der Qualitätsstufe k (für k ∈ ℕ0) sind wie folgt definiert:

B₀: Es gibt nur einen Baum der Qualitätsstufe 0, nämlich das leere Tupel (), d.h.: B₀ := {()}.

B_k+1: Sind t₀; t₁ Bäume der Qualitätsstufe höchstens k, so ist t := (t_0, t₁) genau dann ein Baum der Qualitätsstufe k+1, wenn t nicht bereits ein Baum der Qualitätsstufe höchstens k ist.

Hinweis : Die Bäume der Qualitätsstufe höchstens k sind gerade durch B_≤k :=U^k_j=0 B_j gegeben.

(a) Geben Sie explizit alle Elemente der Mengen B1 und B2 an.

(b) Formalisieren Sie die umgangssprachliche Definition von B_k+1, indem Sie B_k+1 durch einen Mengenausdruck definieren.

(c) Bestimmen Sie die Mächtigkeit von B₄ und B₅. Leiten Sie hierfür aus der Definition von B_k+1 eine Formel her, mit der aus den bereits bestimmten Werten für |B₀|, ..., |B_k| der Wert |B_k+1| berechnet werden kann. Begründen Sie Ihre Formel kurz.

So das ist die Aufgabe, und ich versteh garnix :D
Lösungen sind mir egal, bin mehr daran interessiert das zu verstehen

1. Frage: Was ist mit t:= (t₀, t₁) gemeint? Soll damit nur ausgedrückt werden, dass t auch ein Baum ist, oder steckt da noch mehr dahinter? Ist damit eventuell gemeint, dass die Struktur hinter der Ordnung ein Binärbaum ist, also man einfach immer mit 2ⁿ rechnen kann?

2. Frage: Wie kann ich denn explizit die Elemente angeben, wenn ich doch nur weiß, dass die Bäume bis höchstens k die Vereinigung aller Elemente von B₀ bis B_k ist? Kann man da was genaues rauslesen? Ich nehme mal an ja, sonst wäre das nicht die Aufgabe.

Weitere Fragen kann ich ja noch später als Kommentar etc stellen, ich denke, dass sich alle fragen kläre, wenn es klick gemacht hat und ich es verstanden habe

Danke für die Antworten im Voraus :)

Answer 1

1.) t:= (t₀, t₁) definiert einen Baum als Tupel zweier anderer Bäume, letztendlich kann man das als Binärbaum interpretieren. Alle Bäume habe diese Form, mit Ausnahme des einen Baumes der Qualitätsstufe 0, der der durch das leere Tupel dargestellt wird. Zu beachten ist, dass t₀=t₁ sein kann.

2.)  Du weißt nicht nur was die Bäume bis höchsten k sind, sonder auch was B_k+1 ist, nämlich alle möglichen Tupel zusammengesetzt aus Bäumen geringerer Qualitätstufen.

Da B₀={()} nur den leeren Tupel enthält gibt es nur einen möglichen Baum für die erste Qualitätstufe:

B₁={((),())}

Für B₂ solltest du drei mögliche Bäume finden (denk dran das Tupel normalerweise geordnet sind).
Ich hatte die Lösung für B₂ schon hier https://www.mathelounge.de/387982/mengenausdruck-mit-baumen?show=388010#a388010 gepostet. Kannst du deine Lösung dann ja vergleichen und vielleicht findest du dort ja auch einen Kommilitonen, mit dem du die Aufgaben gemeinsam lösen kannst :)