equivalentierelatie

Matrixrekenen, vectorruimten, groep-en ringstructuren, (lineaire) tranformaties.
Plaats reactie
JB1997
Vast lid
Vast lid
Berichten: 42
Lid geworden op: 02 nov 2015, 18:21

equivalentierelatie

Bericht door JB1997 » 03 okt 2016, 17:35

Laat R een relatie zijn op een verzameling A. Toon aan dat er een equivalentierelatie S op A bestaat die R omvat. Toon daarna aan dat er een kleinste equivalentierelatie op A bestaat die R omvat.

Iemand tips? Ik probeerde al te stellen dat S het cartesisch product is van A met zichzelf, maar dan weet ik niet hoe ik verder moet bij het 2de deel.

arie
Moderator
Moderator
Berichten: 3910
Lid geworden op: 09 mei 2008, 09:19

Re: equivalentierelatie

Bericht door arie » 05 okt 2016, 18:10

Construeer een minimale uitbreiding van R, zodanig dat deze een equivalentierelatie S wordt.

Werk volgens de definitie van een equivalentierelatie:
- reflexiviteit: wat moet gelden voor ALLE elementen a van A?
- symmetrie: als aRb, dan moet wegens overdekking ook aSb bestaan, maar als aSb moet wegens symmetrie ook gelden: ..S..
- transitiviteit: voor alle aSb en bSc moet vervolgens gelden ..S..

Je hebt met S nu R omvat, en je weet dat S een equivalentierelatie is.
Kan je een element cSd (of een pijl van c naar d) uit deze relatie verwijderen zodanig dat
- S een equivalentierelatie blijft
EN
- S bovendien R volledig overdekt?
Wat is dus je conclusie?

JB1997
Vast lid
Vast lid
Berichten: 42
Lid geworden op: 02 nov 2015, 18:21

Re: equivalentierelatie

Bericht door JB1997 » 05 okt 2016, 19:13

de minimale equivalentie relatie S wordt dus zodanig geconstrueerd zodat ze R omvat:
1) Voor alle a die in A zitten: (a,a) zit in S.
2) Voor alle a,b in A geldt: (a,b) zit in S, dan geldt ook bSa. Wegens overdekking zitten ook alle koppels (a,b) die tot R behoren in S.
3) Voor alle a,b,c in A: als aSb en bSc, dan ook aSc.

Voor de kleinste equivalentierelatie te vinden, kan men ook alle equivalentierelaties op A beschouwen die R omvatten. De doorsnede van al die equivalentierelaties (opnieuw een equivalentierelatie) bevat dan ook R. Dit is dan de kleinste equivalentierelatie op A die R omvat.

Plaats reactie