Seien n transitive Relationen R1 , R2, ..., Rn gegeben. Beh: Durchschnitt aller Ri ist transitiv.
Bei n=1 ist nichts zu zeigen, der Durchschnitt ist R1.
Gelte die Beh. für ein gewisses n aus IN.
und seien nun n+1 transitive Relationen R1 , R2, ..., Rn Rn+1 gegeben.
und der Durchschnitt der ersten n Relationen sei R. Dann ist R transitiv
gemäß Ind. annahme.
Und der Durchschnitt aller R1 , R2, ..., Rn, Rn+1 ist = R ∩ Rn+1
wenn nun R ∩ Rn+1 leer ist, dann ist nichts zu zeigen, die leere Relation ist transitiv.
ist R ∩ Rn+1 nicht leer, und gibt es Paare (a,b) und (b,c) aus R ∩ Rn+1
dann ist (a,b) und (b,c) aus R und es ist (a,b) und (b,c) aus Rn+1
Dann ist (a,c) aus R wegen der Transitivität von R
und es t (a,c) aus Rn+1 wegen der Transitivität von Rn+1
also (a,c) auch aus R ∩ Rn+1 q.e.d.
