Müssen Relationen zwischen Elementen der selben Menge sein?

Nein. Eine Relation ist allgemein möglich als Teilmenge aller (a element A, b element B).

Ein Beispiel ist die Relation über die Menge aller Studenten S und die Menge aller Professoren P, wobei die Relation (s element S, p element P) aussagt, dass Student s eine Vorlesung bei Professor p hört. Studenten und Professoren sind hier unterschiedliche Mengen.

Ein anderes Beispiel ist fast jede beliebige relationale Datenbank. Die meisten davon enthalten Relationen zwischen den Einträgen verschiedener Tabellen (also verschiedener Mengen), aber dass eine Tabelle ihre eigenen Datensätze referenziert (d.h. es Relationen innerhalb derselben Menge gibt), ist nicht immer gegeben.

Dass eine Relation sich nur innerhalb einer Menge abspielt, ist also lediglich der Spezialfall A=B. Beispiel: Menge M=Menschen, Relation R:(m1 element M, m2 element M) mit der Bedeutung, dass m1 m2 kennt. Das muss nicht reflexiv sein, z.B. kennen viele Leute wichtige Politiker, aber umgekehrt kennt kaum ein Politiker jeden seiner Wähler.