Ist die Relation R Teilmenge der Relation S, dann ist der Index von R größer oder gleich dem Index von S?

Question

ich habe eine Frage bezüglich einer allgemeinen Eigenschaft von Äquivalenzrelation. Diese laute: Ist die Relation R Teilmenge der Relation S, dann ist der Index von R größer oder gleich dem Index von S.

Ich bin auf diesen Satz beim Durchgehen der Inhalte zu Minimalautomaten/DEA/Satz von Nerode gestoßen.

Meines Wissens beschreibt der Index einer Äquivalenzrelation die Anzahl der möglichen Äquivalenzklassen. Wieso sollte dieser Index aber bei einer Teilmenge der Relation S größer oder gleich dem von S sein??

Vielleicht könnte auch jemand ein Beispiel bringen. Bei den Automaten sehe ich leider noch nicht so ganz durch...

Vielen Dank im Voraus!

Answer 1

Ist die Relation R Teilmenge der Relation S

Dann ist jedes Element, das bezüglich R zu einem gegebenen x äquivalent ist, auch bezüglich S äquivalent zu x.

Es könnte aber sein, dass es x, y gibt, die bezüglich S äquivalent sind, bezüglich R aber nicht. Die Äquivalenzklasse von x bezüglich R ist deshalb höchstens so groß wie die bezüglich S.

Wenn die Äquivalenzklassen kleiner werden, dann muss es mehr Äquivalenzklassen geben.

Vielleicht könnte auch jemand ein Beispiel bringen.

\(R = \{(a,b)\in \mathbb{Z}\times\mathbb{Z} |\ a = b\}\)

\(S = \{(a,b)\in \mathbb{Z}\times\mathbb{Z} |\ a \equiv b\mod 7\}\)

Es gilt

        \(a=b\implies a \equiv b\mod 7\qquad \forall a,b\in \mathbb{Z}\),

also ist \(R\subseteq S\).