[DW] Bewijs maximum - maximale element

Forum van 1ste Bachelor Informatica.

Moderator: Praesidium

User avatar
Flipper
Posts: 193

[DW] Bewijs maximum - maximale element

Post#1 » Sat Oct 13, 2012 2:22 pm

Ik probeer, voor zover mijn ochtendhumeur het toelaat, verzamelingenleer te snappen. Tot nog toe ben ik met alles mee, maar ik begrijp de redeneringen in het volgende bewijs niet zo goed:

Eigenschap: Als a = maximum voor Y, dan is a ook de maximale element (, bovendien is dat maximum uniek).

Bewijs: Stel dat a = maximum voor de verzameling (Y, ) (Voor is de partiële orde relatie)

//Hier ben ik mee, want dat is de definitie van de maximum

Neem is willekeurig zodat

//Waar komt dat vandaan???

Omdat POR is anti-symmetrisch //Dit snap ik dan weer wel, definitie van anti-symetrie


Er is nog iets wat ik niet zo goed begrijp: op het einde van de les hadden we het over de HASSE-diagram om POR voor te stellen en waaruit je eventueel kunt afleiden wat het minimaal en maximaal element is (en minima en maximum). Er werd dan zo gegeven de verzameling Y = {1, 2, 3, 4, 5, 6} en hun onderlinge relatie in HASSE-diagram

1 -> 2 -> 4 en 6
1 -> 3 -> 6
1 -> 5

Nu zegt ie dat 1 het minimaal element is en ook het minimum, dat snap ik, want elk element in die verzameling. Maar nu: 4, 5 en 6 zijn de maximale elementen, akkoord, want ze bevinden zich helemaal onderaan de diagram, maar waarom 6 dan geen maximum is??? Per definitie is toch elk element ? Of moet ik die dingen als relaties zien; 6 is geen maximum omdat niet alle "wegen" op 6 uitkomen (In dit voorbeeld: 1 -> 5 komt niet op 6 uit)?

Wat is dan de relatie trouwens? Ik heb in mijn notitie een klein, onnozele opmerking die me in de war stuurt: er staat daar dat als de relatie R = "... is deler van ..." zou zijn, dat 6 dan wél het maximum is.

Any help, wiskundigen? :)
They call him Flipper, Flipper, faster than lightning,
No-one you see, is smarter than he,
And we know Flipper, lives in a world full of wonder,
Flying there-under, under the sea!

timvdm
Posts: 47

Re: [DW] Bewijs maximum - maximale element

Post#2 » Sat Oct 13, 2012 4:25 pm

Code: Select all

//Waar komt dat vandaan???
Voor zover ik weet komt dit niet meteen ergens vandaan. Het is gewoon een trukje om het bewijs te voeren.

Code: Select all

Nu zegt ie dat 1 het minimaal element is en ook het minimum, dat snap ik, want elk element in die verzameling. Maar nu: 4, 5 en 6 zijn de maximale elementen, akkoord, want ze bevinden zich helemaal onderaan de diagram, maar waarom 6 dan geen maximum is??? Per definitie is toch elk element ? Of moet ik die dingen als relaties zien; 6 is geen maximum omdat niet alle "wegen" op 6 uitkomen (In dit voorbeeld: 1 -> 5 komt niet op 6 uit)?
Je moet die <= idd zien als een orderelatie. Er zijn 3 maxima (4, 5 en 6) en er kan dus geen maiximaal element zijn vermits er slechts 1 kan zijn. Als 6 een miximaal element zou zijn, moet je vanuit 6 ook alle andere elementen kunnen bereiken via een pad in 1 richting (naar beneden).

Normaal gaan de pijlen omhoog, maar je zegt dat 4, 5 en 6 onderaan staan? Er zijn 2 mogelijkheden:
a) "... is deelbaar door ..."
b) "... is deler van ..."
Bij (a) zouden 4, 5 en 6 maximaal zijn en minimaal bij (b). Zowel bij (a) als (b) kan 6 geen maximaal/minimaal element zijn volgens mij (niet alle elementen zijn bereikbaar vanout 6).

User avatar
Flipper
Posts: 193

Re: [DW] Bewijs maximum - maximale element

Post#3 » Sat Oct 13, 2012 5:49 pm

timvdm wrote:Voor zover ik weet komt dit niet meteen ergens vandaan. Het is gewoon een trukje om het bewijs te voeren.
Mmh, ik zal het woensdag toch maar eens gaan navragen aan Symens.
timvdm wrote:Je moet die <= idd zien als een orderelatie. Er zijn 3 maxima (4, 5 en 6) en er kan dus geen maiximaal element zijn vermits er slechts 1 kan zijn. Als 6 een miximaal element zou zijn, moet je vanuit 6 ook alle andere elementen kunnen bereiken via een pad in 1 richting (naar beneden).

Normaal gaan de pijlen omhoog, maar je zegt dat 4, 5 en 6 onderaan staan? Er zijn 2 mogelijkheden:
a) "... is deelbaar door ..."
b) "... is deler van ..."
Bij (a) zouden 4, 5 en 6 maximaal zijn en minimaal bij (b). Zowel bij (a) als (b) kan 6 geen maximaal/minimaal element zijn volgens mij (niet alle elementen zijn bereikbaar vanout 6).
Haal je niet die dingen door elkaar? Een verzameling kan toch meerdere maximale elementen hebben en hooguit 1 maximum? Maar dat je zegt dat ik die dingen als (P)OR moet zien, maakt wel veel duidelijk :D
Voorbeeld: X = 2 ^{1, 2, 3} en Y = { {LEEG}, {1}, {3}, {1, 3}, {2, 3} }
{1, 3} en {2, 3} = maximale elementen: er zijn geen verzamelingen waar deze verzamelingen er deel van maken.
{2, 3} kan geen maximum zijn, want het element {2} zit niet in Y (en dat moet, volgens de definitie van de maximum)
Bij ons heeft Symens toch alleszins van boven naar beneden gewerkt, want hij zette bij een andere voorbeeld de lege verzameling helemaal vanboven. Eigenlijk maakt dat niet zo heel erg veel uit, het punt is dat je dan ziet welk element tot welke in directe relatie staan.

Wat betreft die kleine opmerking; ik heb even eroverheen gelezen, als de verzameling Y = {1, 2, 3, 6} (dus zonder de 4 en 5), dan zou 6 inderdaad het maximum zijn indien de relatie R = "... is deler van ..." geldt. :D
They call him Flipper, Flipper, faster than lightning,
No-one you see, is smarter than he,
And we know Flipper, lives in a world full of wonder,
Flying there-under, under the sea!

timvdm
Posts: 47

Re: [DW] Bewijs maximum - maximale element

Post#4 » Sat Oct 13, 2012 7:18 pm

Edit: Ja, er kunnen meerdere maximale elementen zijn en slechts 1 maximum...

User avatar
Math Wolf
Posts: 4053
Contact:

Re: [DW] Bewijs maximum - maximale element

Post#5 » Sun Oct 14, 2012 8:39 pm

waar komt dat vandaag: stel er bestaat een z zodat z groter of gelijk is dan a (vorige regel). Maar ook, aangezien a het maximum is, is a nog altijd groter of gelijk aan z (want z is een element van de verzameling en a is groter of gelijk aan elk element in de verzameling).
Gevolg, elk element z dat groter of gelijk is aan a, is eigenlijk gelijk aan a en dus is a het unieke maximum.
2014: Jan16, Feb15, Mar16, Apr15, May14, Jun13, Jul12, Aug10, Sep9, Oct8, Nov6, Dec6
2015: Jan5, Feb5, Mar5, Apr4, May4, Jun2, Jul2, Jul31, Aug29, Sep28, Oct27, Nov25, Dec25

User avatar
Flipper
Posts: 193

Re: [DW] Bewijs maximum - maximale element

Post#6 » Sun Oct 14, 2012 9:24 pm

Math Wolf wrote:waar komt dat vandaan: stel er bestaat een z zodat z groter of gelijk is dan a (vorige regel). Maar ook, aangezien a het maximum is, is a nog altijd groter of gelijk aan z (want z is een element van de verzameling en a is groter of gelijk aan elk element in de verzameling).
Gevolg, elk element z dat groter of gelijk is aan a, is eigenlijk gelijk aan a en dus is a het unieke maximum.
I just saw the light! :bow: :D

De volgende keer moet ik eens minder verder kijken dan mijne neus lang is :roll:
They call him Flipper, Flipper, faster than lightning,
No-one you see, is smarter than he,
And we know Flipper, lives in a world full of wonder,
Flying there-under, under the sea!

Return to “1ste Bachelor”

Who is online

Users browsing this forum: No registered users and 2 guests

cron