Relation R på mængde

En relation på to mængder A og B er blot en delmængde af det Cartesiske produkt X x Y, altså en delmængde af alle ordnede par af elementer (x,y) hvor x ligger i X og y i Y. En relation kan ses som en mængde af tilladte skridt. Hvis xRy kan man altså i løs forstand "komme" fra x til y. Bemærk at de to mængder, A og B, i almindelighed er forskellige. Er de ens taler man ofte om en homogen relation, hvilket er tilfældet her.

Jeg går ud fra, at der med skrivemåden R^x menes relationen R sammensat med sig selv x gange. Har vi givet to relationer, R på X x Y og S på Y x Z, så menes med relationskompositionen R;S (R sammensat med S) en ny relationen (delmængde af X x Z). Et ordnet par (x,z) er element i R;S hvis og kun hvis der findes et y (i Y) således at (x,y) tilhører R og (y,z) tilhører S.

Rent regnepraktisk tager man elementvist elementerne i R og ser for hvilke ordnede par i S førstekomponenten er lig andenkomponenten i elementet fra R. Disse er elementer i R;S.

Til eksempel kan vi finde R;R. Et element i R er (a,b). Vi leder dernæst efter alle elementer i R, der har b som førstekomponent. Det er (b,a). Derfor er (a,a) element i R;R fordi vi kan "komme" fra a til a ad a->b->a. Et andet element i R er (a,c). Vi leder efter alle elementer i R, der har c som første komponent. Dem er der ingen af. Sidste element i R er (b,a). Vi leder efter elementer i R med a som første komponent. Det er (a,b) og (a,c). Derfor er R;R = { (a,a), (b,b), (b,c)}.

Tilsvarende for de øvrige kompositioner i c og d idet man i spørgsmål c tager udgangspunkt i resultatet R;R ovenfor og i spørgsmål d tager udgangspunkt i resultatet fra spørgsmål c.