Ik heb moeite met de volgende opdracht. Zo weet ik wel waar de relatie aan moet voldoen, nl: Trans.: Alle x,y,z((xRy en yRz)$\Rightarrow$ xRz) Refl.: Alle x(xRx) (wat wordt hier eigenlijk precies mee bedoeld? Een waarde heeft toch altijd een relatie met zichzelf?) Symm.: Alle x,y (xRy $\Rightarrow$ yRx) Ik heb echter geen idee hoe ik dat in onderstaande opdracht tot elkaar moet brengen. Laat staan dat ik een bewijs kan opstellen of een tegenvoorbeeld kan geven! Ik hoop dat jullie me kunnen helpen.
Een binaire relatie R tussen willekeurige deelverzamelingen van reele getallen is gedefinieerd door: A R B $<\Rightarrow$ er bestaat een injectieve functie f: A $\to$ B.
Geef aan of deze relatie transitief, reflexief, symmetrisch is. Geef een bewijsje als het antwoord ja is en een tegenvoorbeeld als het antwoord nee is.
Judith
Student universiteit - dinsdag 1 maart 2005
Antwoord
Allereerst ga ik maar eens in op je uitspraak 'wat wordt hier eigenlijk precies mee bedoeld? Een waarde heeft toch altijd een relatie met zichzelf?' Een waarde heeft misschien wel altijd een relatie met zichzelf, maar dat hoeft niet de relatie R te zijn.
Laten we maar eens wat voorbeelden nemen om de begrippen 'relatie', 'transitief', 'reflexief' en 'symmetrisch' duidelijker te maken.
Een relatie is eigenlijk niets anders dan een uitspraak over 2 dingen. In de meeste gevallen betekent dit wel dat die 'iets' met elkaar te maken hebben, maar dat hoeft eigenlijk niet eens.
Als voorbeeld geef ik hier een aantal relaties tussen natuurlijke getallen:
xIy: x en y zijn hetzelfde getal (bijvoorbeeld 1I1 is waar (want 1=1), en 10I10 (10=10), maar 11I10 niet (want 11$ \ne $10)) xGy: x is groter dan y (bijvoorbeeld 4G2 is waar (4$>$2), en 5G4 (5$>$4), maar 2G4 en 2G2 niet (want 2$>$4 en 2$>$2 zijn niet aar)) xDy: x is een deler van y (bijvoorbeeld 3D9 is waar (3 is een deler van 9), en 4D64, maar 2D7 niet (2 is geen deler van 7)) xPy: x is te schrijven als de som van y priemgetallen (1 telt als priemgetal) (bijvoorbeeld 3P2, want 3=2+1 en 7P3, want 7=3+2+2, maar niet 11P2, want 2 priemgetallen hebben nooit als som 11)
Dit zijn allemaal mogelijke relaties. Zijn deze ook transitief, reflexief, symmetrisch? Allereerst transitiviteit: De relatie I is transitief: Als xIy en yIz, dan geldt x=y en y=z, dus x=z, dus xIz De relatie G is transitief: Als xGy en yGz, dan is x$>$y en y$>$z, dus x$>$z, dus xGz De relatie D is transitief: Als xDy en yDz, dan is x een deler van y, en y een deler van z, en dus ook x een deler van z De relatie P is niet transitief: 11P9 is waar, want 11=2+2+1+1+1+1+1+1+1, en 9P2 is waar, want 9=7+2, maar 11P2 is niet waar.
Dan reflexiviteit: I is reflexief: x=x geldt voor alle x, dus xIx G is niet reflexief: x$>$x is niet waar D is reflexief: x is altijd een deler van x P is reflexief: x is altijd te schrijven als de som van x enen.
Tenslotte symmetrie: I is symmetrisch: als x=y, dan ook y=x G is niet symmetrisch: als x$>$y, dan niet y$>$x D is niet symmetrisch: als x een deler is van y, hoeft y nog geen deler van x te zijn P is niet symmetrisch: Als x te schrijven is als de som van y priemgetallen, hoeft y nog niet te schrijven te zijn als de som van x priemgetallen.
Dan komen we nu naar jouw relatie R.
A R B $<\Rightarrow$ er bestaat een injectieve functie f: A $\to$ B
Allereerst, is deze transitief? Dat wil zeggen als A R B en B R C, geldt dan ook A R C? Als we een injectieve functie f: A $\to$ B hebben, en een injectieve functie g: B $\to$ C, dan is de functie g·f (g na f): A $\to$ C ook injectief, dus is er zo'n functie, dus de relatie is transitief.
Is deze reflexief? Dat wil zeggen, bestaat er voor elke verzameling A een injectieve functie f: A $\to$ A? Deze bestaat, namelijk de identiteit. Dus R is ook reflexief.
Ten slotte symmetrisch. Als er een injectieve functie f: A $\to$ B bestaat, bestaat er dan ook een injectieve functie g: B $\to$ A? Dit is niet het geval. Zij A de verzameling {0}, en B de gehele verzameling van reële getallen. Dan is er een injectieve functie A $\to$ B (bijvoorbeeld f(0)=0), maar geen injectieve functie B $\to$ A (er is maar een functie B $\to$ A, namelijk de constante functie f(x)=0, en deze is niet injectief).
