Eindige verzameling

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de verzamelingenleer, een deelgebied van de wiskunde is een eindige verzameling een verzameling met een eindig aantal elementen. De verzameling

\{2,4,6,8,10\}\,\!

is bijvoorbeeld een eindige verzameling met vijf elementen. Het aantal elementen van een eindige verzameling is een natuurlijk (niet-negatief getal) en wordt de kardinaliteit van de verzameling genoemd. Een verzameling die niet eindig is wordt oneindig genoemd. De verzameling van alle positieve gehele getallen is een voorbeeld van een oneindige verzameling:

\{1,2,3,\ldots\}. \,

Eindige verzamelingen zijn bijzonder belangrijk in de combinatoriek, de wiskundige studie van het tellen. Veel wiskundige argumenten, waar eindige verzamelingen een rol in spelen, baseren zich op het duiventilprincipe. Dit principe stelt dat er geen injectieve functie kan bestaan van een grotere eindige verzameling naar een kleinere eindige verzameling.

Definitie en terminologie[bewerken]

Formeel wordt een verzameling S eindige genoemd als er een bijectie

S = \{x_1,x_2,\ldots,x_n\}. \,

bestaat voor enig natuurlijk getal n. Het getal n wordt de kardinaliteit van de verzameling genoemd. De kardinaliteit wordt aangeduid door |S|. (Merk op dat men de lege verzameling als eindig met kardinaliteit nul beschouwt). Indien een verzameling eindig is kunnen de elementen worden geschreven als een rij:

S = \{x_1,x_2,\ldots,x_n\}. \,

In de combinatoriek wordt een eindige verzameling met n elementen soms een n-verzameling genoemd. De verzameling (5,6,7) is bijvoorbeeld een 3-verzameling, een eindige verzameling met drie elementen.

Basiseigenschappen[bewerken]

Elke strikte deelverzameling van een eindige verzameling S is eindig en heeft minder elementen dan S zelf. Als gevolg daarvan kan er geen bijectie bestaan tussen een eindige verzameling S en een strikte deelverzameling van S. Elke verzameling met deze eigenschap wordt Dedekind-eindig genoemd. Door gebruik te maken van de standaard ZFC-axioma's voor de verzamelingenleer, is iedere Dedekind-eindige verzameling ook eindig, maar dit vereist het keuzeaxioma (of ten minste het afhankelijke keuzeaxioma).

Elke injectieve functie tussen twee eindige verzamelingen met dezelfde kardinaliteit is ook een surjectieve functie, en op gelijke wijze is elke surjectie tussen twee eindige verzamelingen met dezelfde kardinaliteit ook een injectie.

De vereniging van twee eindige verzamelingen is eindig, met

|S\cup T| \le |S| + |T|.

In feite geldt:

|S\cup T| = |S| + |T| - |S\cap T|.

Meer in het algemeen is de vereniging van elk eindig aantal van eindige verzamelingen eindig. Het Cartesisch product van eindige verzamelingen is ook eindig, met

|S\times T| = |S|\times|T|. \,

Op gelijks wijze is het cartesisch product van een eindig aantal eindige verzamelingen eindig. Een eindige verzameling met n elementen heeft 2n verschillende deelverzamelingen. Dat wil zeggen dat de machtsverzameling van een eindige verzameling ook eindig is, met een kardinaliteit van 2n.

Elke deelgroep van een eindige verzameling is eindig. De verzameling van waarden van een functie, wanneer toegepast op de elementen uit een eindige verzameling, is eveneens eindig.

Alle eindige verzamelingen zijn aftelbaar, maar niet alle aftelbare verzamelingen zijn eindig. Sommige auteurs gebruik "aftelbaar" in de zin van "aftelbaar oneindig", en deze auteurs zijn dus niet noodzakelijkerwijs van mening dat eindige verzamelingen aftelbaar zijn.)

Het vrije halfrooster over een eindige verzameling is de verzameling van al haar niet-lege deelverzamelingen, waar de join operatie wordt gegeven door de vereniging van verzamelingen.