Equivalentie- en orderelaties - theorie PDF

Preview

Summary

Download Equivalentie- en orderelaties - theorie PDF

Description

4

RELATIES

4.2

Relaties in een verzameling

4.2.2

Equivalentierelatie De begrippen reflexiviteit, symmetrisch en transitiviteit zijn heel belangrijk. Bestudeer deze begrippen goed. Probeer, na het bestuderen van deze drie begrippen, te bepalen of onderstaande relatievoorschriften een relatie voorstellen die reflexief, symmetrisch en/of transitief is. Vul het nummer van het voorbeeld in, in de juiste categorieën in onderstaande tabel. Controleer bij de oplossingen van dit hoofdstuk of je al dan niet correct bent. 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12)

… is een veelvoud van … … is kleiner dan … … is de moeder van … … is gelijk aan … … is langer geleden … … is even dik als … … is even oud als … In … kan evenveel water als in ….

…=… …|… … is de 10-logaritme van … … is een vierkantswortel uit …

Reflexief

Symmetrisch

Transitief

1, 4, 6, 7, 8 , 9 , 10

4,6,7, 8 , 9

1, 2, 4, 5, 6 ,7, 8, 9 , 10

Welke voorbeelden zijn voorbeelden van een equivalentierelatie? ………………… Opmerking: na het maken van deze oefening lijkt het alsof elke reflexieve relatie ook symmetrisch is. Toch is het mogelijk om een symmetrische relatie te bedenken die niet ‘ …is zusvan … ’ reflexief is. Denk maar aan de relatie of ’. ‘ …is verschillend van … Je kan namelijk geen zus van jezelf zijn. Alsook is een getal nooit verschillend van zichzelf. Voorbeelden equivalentierelatie Voorbeeld 1

A= { a , b , c , d , f , g } a , a ),(b , b ),(c , c ),(d , d ),( f , f ) ,(g , g ) ,(a , b) , r= ( ( b , a ) ,( c , d ) ,( c , f ) , ( d , f ) , ( d , c ) , ( f , c ) , ( f , d )

{

Digitale begeleiding voor afstandsstudenten Een leerpad voor wiskunde VS1

1

} Arteveldehogeschool

Om te controleren of dit een voorbeeld is van een equivalentierelatie moeten we controleren of bovenstaande relatie zowel reflexief, transitief als symmetrisch is. Controle reflexief: controleer of alle identieke koppels aanwezig zijn. In orde. Alle identieke koppels horen tot de relatie. De identieke koppels zijn:

( a , a ) , ( b , b ) , ( c ,c ) , ( d , d) , ( f , f ) , ( g , g ) Controle symmetrisch: controleer bij elk koppel (a , b) ook tot de relatie behoort. In orde.

of het inverse koppel

(b , a)

Controle transitief: indien twee opeenvolgende koppels tot een relatie behoren, dan moet het samengestelde koppel ook tot de relatie behoren. In orde. Conclusie: bovenstaande relatie is een equivalentierelatie. Enkel wanneer alle drie de voorwaarden voldaan zijn, kunnen we met zekerheid zeggen dat de relatie een equivalentierelatie is. 4.5.1

Ordenen Symmetrisch, niet-symmetrisch en anti-symmetrisch

r is symmetrisch∈A ⇔∀a , b ∈ A : ( a ,b ) ∈ r ⇒( b ,a ) ∈ r r isniet −symmetrisch ∈ A ⇔∃a , b ∈ A :( a ,b ) ∈ r ∧ ( b , a) ∉ r r is anti−symmetrisch∈ A ⇔∀a , b ∈ A : ( ( a ,b )∈ r ∧ ( b , a ) ∈ r ) ⇒a=b Symmetrisch en anti-symmetrisch kan je zien als twee gevallen die heel veeleisend zijn, als twee uitersten. Zo is een relatie slechts symmetrisch indien voor ELK koppel ook het inverse koppel tot de relatie behoort. Iets analoogs geldt voor anti-symmetrisch, hier mag GEEN ENKEL koppel en zijn inverse koppel tot de relatie behoren. Het enige geval waar dit wel mag is indien het koppel een identiek koppel is, bijvoorbeeld (5,5). Niet-symmetrische relaties zijn relaties die zowel niet symmetrisch zijn als niet antisymmetrisch zijn. Reflexief, niet-reflexief, anti-reflexief

r isreflexief ∈A ⇔∀a ∈ A : ( a , a ) ∈ r r isniet −reflexief ∈ A ⇔∃a ∈ A : ( a , a) ∉r r is anti−reflexief ∈ A ⇔∀a ∈ A :( a , a )∉ r Een relatie is reflexief indien voor elk element uit de verzameling het identiek koppel behoort tot de relatie. Anti-reflexief eist dan weer dat er geen enkel identiek koppel aanwezig is. Een relatie die niet reflexief en niet anti-reflexief is, noemen we niet-reflexief. Deze relatie bevat enkele identieke koppels, maar niet allemaal. Transitief, niet-transitief

r istransitief ∈ A ⇔∀a , b , c , ∈ a : (( a , b ) ∈ r ∧( b , c ) ∈r ) ⇒( a , c ) ∈ r r isniet −transitief ∈A ⇔∃a , b , c ,∈ a :( a , b ) ∈ r ∧ ( b , c ) ∈ r ∧ ( a , c ) ∉ r

Digitale begeleiding voor afstandsstudenten Een leerpad voor wiskunde VS1

2

Arteveldehogeschool

Een relatie is transitief indien voor elke twee opeenvolgende koppels, het samengestelde koppel ook tot de relatie behoort. Indien dit in een relatie niet het geval is, noemen we deze relatie niet-transitief. Voorbeeld:

d

a b

e

c

r is anti−reflexief ∀x ∈ A : ( x , x ) ∉r r isniet −symmetrisch want (b , c)∈r , maar (c , b ) ∉ r r isniet −transitief .

  

Om deze begrippen verder in te oefenen, vind je hier extra oefeningen. Merk op dat er niet bij alle oefeningen juist één oplossing bestaat. Bij elke oefening bieden we je steeds één oplossing aan. Probeer bij elke oefening ook zelf een andere oplossing te bedenken! Oefening 1: Maak een relatie r   

in B die aan volgende voorwaarden voldoet:

r is anti-reflexief r is anti-symmetrisch r is transitief

Beschouw verzameling

B : ab

cd

Mogelijke oplossing:

ab

cd

Oefening 2: Maak een relatie r  

in C

die aan volgende voorwaarden voldoet:

r is niet-reflexief r is symmetrisch

Digitale begeleiding voor afstandsstudenten Een leerpad voor wiskunde VS1

3

Arteveldehogeschool

Beschouw verzameling

C :

ab c

Mogelijke oplossing:

ab c

Oefening 3: Is volgende relatie in D

D

transitief, ja of nee? Verklaar je antwoord.

ab cd

Antwoord: Ja deze relatie is transitief. Beschouw de definitie van transitiviteit

r istransitief ∈ A ⇔∀a , b , c , ∈ a : (( a , b ) ∈ r ∧( b , c ) ∈r ) ⇒( a , c ) ∈ r Als we de definitie bekijken van transitiviteit, dan merken we een implicatiepijl op. We zien dat de eerste voorwaarde, twee opeenvolgende koppels horen tot de relatie, niet voldaan is in bovenstaande relatie. ( ( a , b )∈ r ∧ ( b , c ) ∈r ) vinden we met andere woorden niet terug in onze verzameling. We hebben gezien in hoofdstuk 1, dat als aan de eerste uitspraak niet voldaan is bij een implicatie, de implicatie altijd waar is. We kunnen dus besluiten dat deze relatie een correct voorbeeld is van een transitieve relatie. 4.5.2

Orderelatie Extra oefeningen op het opstellen van een Hassediagram Maak van volgende opgaves zowel de pijlenvoorstelling alsook het Hassediagram. Controleer daarna je antwoord met de oplossingen. Deze oplossingen zijn te vinden bij de oplossingen van de oefeningen in dit hoofdstuk.

Digitale begeleiding voor afstandsstudenten Een leerpad voor wiskunde VS1

4

Arteveldehogeschool

Merk op: Bij elke opgave is er, in tegenstelling tot de vorige extra oefeningen, altijd maar één mogelijke pijlenvoorstelling alsook maar één mogelijk Hassediagram. Vergelijk je antwoord met de oplossing. Oefening 1: A= { 2,3,6,7,10,20 } met relatie is deler van Geef de pijlenvoorstelling alsook het Hassediagram. Oefening 2: A= { ∅, {2,8 }, { 3 , π } , N } met relatie is deelverzameling van Geef de pijlenvoorstelling alsook het Hassediagram. Oefening 3: A= { k ,l , m, n , r } met de orderelatie bepaald door onderstaand

Hasse−diagram .Geef de pijlenvoorstelling k

l m n

r

Bewijsoefening In de cursus op p 72, vind je een bewijsoefening terug. Deze oefening is de volgende: Bewijs dat ‘ r is AS∈A ’ kan geschreven worden als Mogelijkheid 1: ∀a , b ∈ A : ( ( a , b) ∈r en a ≠ b ) ⇒( b , a ) ∉r Mogelijkheid 2: ∀a , b ∈ A : a≠ b ⇒( ( a ,b ) ∉ r of ( b , a ) ∉r ) Bewijs:

r is anti−symmetrisch∈ A ⇔∀a , b∈ A : ( ( a , b ) ∈ r ∧( b , a )∈ r ) ⇒a=b (p ⇒q ⇔ p ∨ q) ⇔∀a , b∈ A : ( ( a , b ) ∈ r ∧ (b , a ) ∈ r ) ∨( a=b ) ∼( p ∧ q ) ⇔(∼ p∨ ∼q) ⇔∀a , b∈ A : ( a , b ) ∉ r ∨ (b , a ) ∉ r ∨ ( a=b ) ( p ⇒q ⇔ p ∨ q ) Mogelijkheid 1:

⇔∀a , b∈ A :( a , b ) ∉ r ∨ (a=b ) ∨( b , a ) ∉r ⇔∀a , b∈ A : ( ( a , b) ∈ r ∧ ( a ≠b ))∨ ( b , a) ∉ r ⇔∀a , b∈ A : ( ( a , b ) ∈ r ∧a ≠ b ) ⇒(b , a ) ∉r

∼( p ∧ q)⇔(∼ p ∨ ∼q) ( p ⇒q ⇔ p ∨ q )

Mogelijkheid 2:

⇔∀a , b∈ A : ( a=b ) ∨( a , b) ∉r ∨ ( b , a ) ∉r p ⇔∼(∼ p) ⇔∀a , b∈ A : ( a ≠ b ) ∨( a ,b) ∉ r ∨ ( b , a ) ∉ r associativiteit van ∨ ⇔∀a , b∈ A : ( a ≠ b ) ∨( ( a , b) ∉r ∨ ( b , a ) ∉r ) (p ⇒q ⇔ p ∨ q) ⇔∀a , b∈ A :a ≠ b ⇒( ( a , b )∉ r of ( b , a ) ∉ r )

4.5.3

Strikte orde Bij elke orderelatie hoort een strikte orderelatie: Digitale begeleiding voor afstandsstudenten Een leerpad voor wiskunde VS1

5

Arteveldehogeschool

Orderelatie

Strikte orderelatie

¿ ⊂ ≺

≤ ⊆ ≼

Opmerking Hassediagram: in een Hassediagram kan je het verschil tussen een orderelatie en een strikte orderelatie niet merken! Als je een Hassediagram krijgt, mag je uitgaan van een gewone orderelatie, tenzij anders vermeld. 4.5.4

Geordende verzamelingen In de cursus vind je terug wat een totaal geordende relatie is en wat een partieel geordende relatie is. Hier vind je nog extra voorbeelden van totaal en partieel geordende relaties. 

  

,...