Eindige verzameling


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

\({\displaystyle \{2,4,6,8,10\}}\)

is bijvoorbeeld een verzameling met vijf elementen.

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.

Inhoud

Definitie en terminologie


Een verzameling \({\displaystyle F}\) heet eindig als er een natuurlijk getal \({\displaystyle n}\) en een bijectie

\({\displaystyle f:\{1,2,...,n\}\to F}\)

bestaan. Deze definitie is equivalent met dat de kardinaliteit \({\displaystyle |F|}\) van de verzameling \({\displaystyle F}\) een natuurlijk getal is, en \({\displaystyle |F|=n}\). Van een eindige verzameling kunnen de elementen geschreven worden als een rij:

\({\displaystyle F=\{x_{1},x_{2},...,x_{n}\}}\).

De lege verzameling \({\displaystyle \emptyset }\) is eindig en een kardinaliteit is \({\displaystyle |\emptyset |=0}\).

Een verzameling die niet eindig is wordt oneindig genoemd.

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.

Omdat elke eindige verzameling in bijectie is met een verzameling \({\displaystyle \{1,2,...,n\}}\), en de verzameling \({\displaystyle \{1,2,...,n\}}\) te welordenen is, is elke eindige verzameling te welordenen.

Voorbeelden


De verzameling van gehele getallen groter of gelijk aan 0 en kleiner dan 5 is eindig, aangezien de verzameling vijf elementen heeft: 0, 1, 2, 3 en 4: de kardinaliteit is vijf. Bovendien is er een bijectie tussen deze verzameling en de verzameling {1, 2, 3, 4, 5}, namelijk:

\({\displaystyle \,x\mapsto x+1}\).

De verzameling reële getallen tussen 0 en 5 (genoteerd als het interval [0, 5]) is echter niet eindig. De kardinaliteit van [0, 5] gelijk is aan \({\displaystyle \aleph _{1}}\).

Alternatieve definities


Naast de hierboven gegeven definitie van eindig bestaan er alternatieve definities van eindig.

Een verzameling \({\displaystyle F}\) heet:

\({\displaystyle X\subseteq F,f[X]\subseteq X\Rightarrow X=\emptyset {\text{ of }}X=F}\),

In de Zermelo-Fraenkel-verzamelingenleer, zonder gebruik te maken van het keuzeaxioma, verhouden de definities van eindig zich als volgt:

\({\displaystyle {\text{S-eindig}}\Leftarrow {\text{Eindig}}\Leftrightarrow {\text{T-eindig}}\Leftrightarrow {\text{D}}_{2}{\text{-eindig}}\Rightarrow {\text{D-eindig}}}\)

en

\({\displaystyle {\text{S-eindig}}\Rightarrow {\text{D-eindig}}}\).

Bij aanname van het keuzeaxioma is ook elke D-eindige verzameling eindig en zijn dus alle definities van eindig equivalent.

Basiseigenschappen


Elke strikte deelverzameling van een eindige verzameling \({\displaystyle F}\) is eindig en heeft minder elementen dan \({\displaystyle F}\) zelf. Als gevolg daarvan kan er geen bijectie bestaan tussen een eindige verzameling \({\displaystyle F}\) en een strikte deelverzameling van \({\displaystyle F}\). Dat impliceert dat elke injectie \({\displaystyle f:F\to F}\) ook surjectief is, dus \({\displaystyle F}\) is Dedekind-eindig (Zie het kopje Alternatieve definities).

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

\({\displaystyle |S\cup T|\leq |S|+|T|.}\)

In feite geldt:

\({\displaystyle |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

\({\displaystyle |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.

De klasse van eindige verzamelingen


De klasse van eindige verzamelingen is een echte klasse, want de verzameling van alle eindige verzamelingen bestaat niet. Als namelijk

\({\displaystyle E=\{X:X{\text{ is eindig}}\}}\)

Dan bestaat ook de verzameling

\({\displaystyle E_{1}=\{X\in E:\exists Y,X=\{Y\}{\text{ en }}Y{\text{ is een verzameling}}\}}\)

en dan bestaat ook een verzameling \({\displaystyle V}\) zodanig dat

\({\displaystyle (\forall X\in E_{1})(\exists Y\in V):X=\{Y\}}\)

en dus bevat \({\displaystyle V}\) alle verzamelingen, maar er bestaat geen verzameling die alle verzamelingen bevat.

Zie ook











Categorieën: Verzamelingenleer




Staat van informatie: 28.09.2021 07:40:51 CEST

oorsprong: Wikipedia (Auteurs [Geschiedenis])    Licentie: CC-BY-SA-3.0

Veranderingen: Alle afbeeldingen en de meeste ontwerpelementen die daarmee verband houden, zijn verwijderd. Sommige pictogrammen werden vervangen door FontAwesome-Icons. Sommige sjablonen zijn verwijderd (zoals 'artikel heeft uitbreiding nodig') of toegewezen (zoals 'hatnotes'). CSS-klassen zijn verwijderd of geharmoniseerd.
Specifieke Wikipedia-links die niet naar een artikel of categorie leiden (zoals 'Redlinks', 'links naar de bewerkpagina', 'links naar portals') zijn verwijderd. Elke externe link heeft een extra FontAwesome-Icon. Naast enkele kleine wijzigingen in het ontwerp, werden mediacontainer, kaarten, navigatiedozen, gesproken versies en Geo-microformats verwijderd.

Belangrijke opmerking Omdat de gegeven inhoud op het gegeven moment automatisch van Wikipedia wordt gehaald, was en is een handmatige verificatie niet mogelijk. Daarom garandeert LinkFang.org niet de juistheid en actualiteit van de verkregen inhoud. Als er informatie is die momenteel verkeerd is of een onjuiste weergave heeft, aarzel dan niet om Neem contact op: E-mail.
Zie ook: Afdruk & Privacy policy.