] >
Bij de constructie van maakten we gebruik van een equivalentierelatie. Daarom hebben we uitvoerig naar equivalentierelaties gekeken. In en ook in hebben we de ordening . Een ordening is een reflexieve, antisymmetrische, transitieve relatie, zie Definitie 5.12. In deze paragraaf gaan we nader in op ordeningen. Voor een gegeven, maar willekeurige, ordening zullen we vaak het symbool gebruiken: het lijkt op , maar dat heeft gewoonlijk een meer specifieke betekenis. Hebben we een ordening in een verzameling dan spreken we van een geordende verzameling:
5.39 Definitie. Is een ordening van een verzameling , dan zeggen we dat een geordende verzameling is.
5.40 Voorbeelden. , , en zijn voorbeelden van geordende verzamelingen. Merk op dat ook een ordening is. Is een ordening, dan is , gedefinieerd door , ook een ordening. Is een geordende verzameling en een deelverzameling van , dan geeft door beperking tot een ordening van .
Ordeningen van niet al te grote verzamelingen kun je in een plaatje weergeven. Figuur 5.4 bijvoorbeeld bestaat uit plaatjes van een viertal ordeningen van . Kun je van naar gaan door langs verbindingen van beneden naar boven te lopen, dan . Zo’n plaatje wordt wel een Hassediagram genoemd. We zullen enkele typen van ordeningen onderscheiden.
5.41 Definitie. Een ordening van een verzameling heet totaal als voor iedere geldt: of . We zeggen dan dat een totaal geordende verzameling is.
5.42 Voorbeelden. De ordeningen en van de verzamelingen , zijn totaal. Het totaal zijn van de ordening van volgt eenvoudig uit diezelfde eigenschap van de ordening van .
5.43 Definitie. Laat een ordening zijn van een verzameling en laat een deelverzameling zijn van . Dan heet het kleinste element van (m.b.t. de ordening ) als
Is het kleinste element van , dan geven we dit aan met . Is het kleinste element van m.b.t. de ordening (waarbij ), dan heet het grootste element van , notatie .
Heeft een kleinste element, dan is dat element uniek. Dit volgt eenvoudig uit het antisymmetrisch zijn van . Het hangt van en af of een kleinste element bestaat.
De deelverzameling van heeft geen kleinste element m.b.t. .
De deelverzameling van heeft geen grootste element m.b.t. .
5.44 Definitie. Een ordening van een verzameling heet een welordening als iedere niet-lege deelverzameling van een kleinste element heeft m.b.t. . We noemen dan een welgeordende verzameling.
We gaan bewijzen dat een welgeordende verzameling is. Dat is een zo voor de hand liggende eigenschap van de verzameling der natuurlijke getallen dat je je kunt afvragen of daar een bewijs voor nodig is. Dat geldt trouwens ook voor volledige inductie, maar die eigenschap hebben we als axioma genomen. In zekere zin is de welordening van equivalent met volledige inductie. We gaan eerst een nieuwe versie van volledige inductie afleiden.
Bewijs. Met volledige inductie bewijzen we dat voor alle . Voor is dit duidelijk, want .
Stel voor een . Dan ook , en dus .
Dus voor alle . Voor iedere hebben we nu en dus . □
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
Propositie 5.45 en Stelling 5.46 zijn varianten van het principe van volledige inductie en worden vaak in bewijzen gebruikt. Propositie 5.45 levert het sterke principe van volledige inductie.
Volledige inductie (sterk)
| |
Stel is een natuurlijk getal met voor alle . | |
Dus . | |
Dus voor alle met voor alle .
| |
Met het sterke principe van volledige inductie volgt dat
| |
voor alle . | |
Bij gewone inductie is het de kunst om te bewijzen onder de aanname dat geldt. Bij deze sterke vorm van inductie gaat het erom te bewijzen onder de aanname dat geldt voor alle . Het lijkt er op dat we het geval zo vergeten. Echter voor staat er dat geldt als geldt voor alle natuurlijke getallen , maar zulke natuurlijke getallen zijn er niet. Een bewijs volgens het sterke principe verloopt gewoonlijk zo dat er gevalsonderscheidingen plaats vinden: gevallen waarin de inductieaanname wordt gebruikt en gevallen waarin hij niet wordt gebruikt.
De ordening van is geen welordening. Niet-lege deelverzamelingen hebben een kleinste element onder een extra voorwaarde.
5.47 Definitie. Zij een geordende verzameling. Een heet een ondergrens van een deelverzameling van als voor alle . De deelverzameling heet naar beneden begrensd als er voor een ondergrens is.
Een heet een bovengrens van een deelverzameling van als voor alle . De deelverzameling heet naar boven begrensd als er voor een bovengrens is.
5.48 Stelling. Naar beneden begrensde niet-lege deelverzamelingen van hebben een kleinste element. Naar boven begrensde niet-lege deelverzamelingen van hebben een grootste element.
Hebben we het over de geordende verzameling , dan bedoelen we daar mee. Een grootste element is het kleinste element m.b.t. .
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
Een totale ordening hoeft geen welordening te zijn. Het omgekeerde geldt wel.
Bewijs.
Laten elementen zijn van . Dan is een deelverzameling van . Omdat een welordening is, heeft deze verzameling een kleinste element. Als het kleinste element is, dan geldt . Is het kleinste element, dan . Dus: of .
Dus voor alle geldt: of . Ofwel: is totaal. □
Een belangrijk voorbeeld van een ordening is de relatie ‘is deelverzameling van’. Dit is een relatie in de verzameling van alle deelverzamelingen van een gegeven verzameling.
5.50 Voorbeeld. Zij een verzameling. De machtsverzameling is een geordende verzameling: . De inclusie is daarbij de ordening. De verzameling heeft elementen en Figuur 5.5 is een Hassediagram van deze geordende verzameling. Deze ordening is niet totaal en dus ook geen welordening.