Teil a) Definition von M'

Question

Aufgabenteil a):

Mir ist der vorletzte Abschnitt der Lösung nicht ganz klar. Warum ist die Menge M' gerade so definiert, dass sie sich von jeder Menge der Liste unterscheidet? Sie ist doch praktisch das Komplement von Mn, und das könnte doch auch in der Liste vorkommen?

Vielen Dank!

 

Answer 1

Hallo,

das M' enthält alle wj, bei denen gilt, dass Mj sie nicht enhält. Es enthält aber keines der wj, für die gilt, dass Mj sie enthält. Wichtig ist hier, zu beachten, dass nur die Diagonalelemente betrachtet werden.

Man kann sich das ganze auch so vorstellen:

Steht in Zeile 1, Spalte 1 eine 0, dann steht in M' (Eintrag 1) eine 1; steht in der Tabelle eine 1, dann steht in M' eine 0

Steht in Zeile 2, Spalte 2 eine 0, dann steht in M' (Eintrag 2) eine 1; steht in der Tabelle eine 1, dann steht in M' eine 0

Steht in Zeile 3, Spalte 3 eine 0, dann steht in M' (Eintrag 3) eine 1; steht in der Tabelle eine 1, dann steht in M' eine 0

...

Somit unterscheidet sich M' von jedem M in der Liste mindestens im Diagonalelement und kann somit nicht Teil der Liste sein.

Ich hoffe, ich konnte dir weiterhelfen.

Viele Grüße

Philippe (Tutor)