Äquivalenzrelation: Gleichmächtigkeit und Äquivalenz beweisen

Question

Hallo :)

ich studiere Mathematik im 1. Semester und habe eine Frage zu folgender Aufgabe:

Aufgabe: Beweisen Sie, dass

a) die Relation „äquivalent“ auf der Menge aller Terme

b) die Relation „Gleichmächtigkeit“ auf der Menge aller Mengen

eine Äquivalenzrelation darstellt.

Problem/Ansatz:

Wir haben vor kurzem Äquivalenzklassen und die Äquivalenzrelation besprochen, und ich habe das soweit auch verstanden, aber mir fällt leider nicht ein, wie ich beides beweisen soll.

Mir ist klar, dass 3 Eigenschaften gegeben sein müssen, um die Relation als eine Äquivalenzrelation zu bestimmen:

1. Reflexivität

2. Symmetrie

3. Transitivität

Wie aber kann ich beides beweisen?

Ich wäre sehr dankbar über etwas Hilfe :)

Answer 1

Mal zu b) "gleichmächtig" bedeutet "hat gleich viele Elemente".

1. Reflexivität

Jede Menge M ist gleich mächtig wie sie selbst.

| M | = | M | 

2. Symmetrie

Wenn Menge A gleichmächtig ist, wie Menge B, dann ist auch Menge B gleichmächtig wie Menge A.

|A| = |B| ==> |B| = |A| 

3. Transitivität

Wenn Menge A gleichmächtig ist, wie Menge B und Menge B gleichmächtig wie Menge C, so ist A gleichmächtig, wie Menge C.

|A| = |B| und |B| = |C| ==> |A| = |C|

Sobald ihr etwas Theorie gemacht habt, kannst du auch mit "Klassen von gleichmächtigen Mengen" argumentieren und brauchst nicht mehr unbedingt auf die Definition zurückzugreifen.

Comments

Vielen Dank :)

Wie kann die Argumentation denn dann für a) lauten?

---

Mach mal ein paar Beispiele von Termen.

Welche sind "äquivalent"?

---

Zwei Terme sind genau dann über einer Grundmenge äquivalent, wenn sie für alle Einsetzungen aus der Grundmenge die gleichen Werte ergeben.

Damit kannst du analog zur Argumentation von lul in der Antwort zu b) argumentieren.

---

Äquivalent sind alle Terme, die die gleiche Definitionsmenge haben und für alle einsetzbaren Zahlen den gleichen Wert annehmen.

Also z.B. T(a) = 6x + 2 und T(b) = 2x + 4x + 1*2

---

Gut. Wie Wolfgang erwähnt hat. Genau wie oben vorgehen.

1. Jeder Term ist "äquivalent" zu sich selbst.

usw.

---

Vielen Dank, Wolfgang. Aber wie genau soll ich das aufschreiben?

Wenn ich das so aufschreibe, habe ich ja zugleich nicht bewiesen, dass es sich so verhält:

1. Jeder Term a ist zu sich selbst äquivalent [T(a) = T(a)]

2. Wenn der Term a zu einem Term b äquivalent ist, dann ist auch Term b zu dem Term a äquivalent.

3. Ist der Term a zu einem Term b äquivalent und dieser zu einem Term c, so ist Term a auch zu einem Term c äquivalent.

---

Ich brauche ja irgendeinen Beweis dafür, dass es so ist.

---

1. Weil T(a) die gleiche Definitionsmenge hat wie T(a) und für alle einsetzbaren Zahlen den gleichen Wert annimmt.

usw.

---

Ein Frage habe ich noch: Reicht die Argumentation von oben für b) als kompletter Beweis bzw. muss ich nicht noch Begründungen hinzufügen?

Genügt es wirklich, zu sagen, dass bei einer Gleichmächtigkeit zwischen A und B und B und C auch eine Gleichmächtigkeit zwischen A und C vorliegt?

---

@Mengen: Fallunterscheidung

Endliche Mengen: Wenn Menge A na Elemente hat und Menge B nb Elemente und gilt na = nb , so gilt wegen der Regeln zur Gleichheit von natürlichen Zahlen, dass nb = na.

usw. D.h. du könntest es auf Eigenschaften der Gleichheit von "natürlichen Zahlen" zurückführen und angeben, dass das vorausgesetzt wird.

Unendliche Mengen: Mächtigkeit mit Hilfe von bijektiven Abbildungen betrachten.

Allerdings werden die natürlichen Zahlen in der Logik gern auf Mengen aufgebaut. D.h. schau da genau, ob du wirklich noch mehr machen musst. Du solltest besser nichts verwenden, das erst später eingeführt wird. D.h. vielleicht auch bei endlichen Mengen mit bijektiven Abbildungen argumentieren.

---

Alles klar, vielen Dank!