] >
Een bijectieve afbeelding koppelt de elementen van aan die van . Op grond daarvan kun je zeggen dat de verzamelingen en evenveel elementen hebben. In de wiskunde zegt men dat ze gelijkmachtig zijn.
3.27 Definitie. Verzamelingen en heten gelijkmachtig als er een bijectie van naar bestaat. Notatie: .
Zijn en gelijkmachtig, dan hebben ze evenveel elementen. Hoeveel elementen ze hebben, dat is een andere kwestie.
Het begrip gelijkmachtig voldoet aan eigenschappen die je ervan kunt verwachten:
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
Om aan te geven hoeveel elementen een verzameling heeft kun je hem vergelijken met een standaardverzameling. Voor ieder natuurlijk getal hebben we een standaardverzameling .
3.29 Notaties. Zij . Met geven we de verzameling aan van natuurlijke getallen met :
Ook gebruiken we de volgende notatie:
We hebben dus en voor alle : . Daarmee ligt dus ook vast. De notatie ligt vast door en . Duidelijk is dat .
Het idee is dat de standaardverzameling is met elementen. Een verzameling heeft dan elementen als . Het kan natuurlijk niet zo zijn dat en voor verschillende en . Maar waarom eigenlijk niet?
3.30 Propositie. Voor alle natuurlijke getallen en geldt: als er een injectieve afbeelding bestaat, dan .
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
Bewijs. Uit en volgt dat . Er is dus een bijectie . Zowel als is injectief. Dus en , ofwel . □
Dit gevolg rechtvaardigt de volgende definitie.
3.32 Definitie. Een verzameling heeft elementen als . Notatie: . We noemen het aantal elementen van . Is er zo’n dan heet de verzameling eindig. Een bijectieve afbeelding noemen we een nummering van .
Het begrip aantal en de notatie daarvoor gebruikten we al vaker. Het gaat om een zeer natuurlijk begrip. In deze paragraaf gaat het om de fundering ervan.
In 3.32 wordt gedefinieerd wat een eindige verzameling is. Als je het begrip eindig niet als iets vanzelfsprekends beschouwt (en er dus een definitie voor geeft), dan moet je vanzelfsprekende uitspraken zoals de volgende propositie gaan bewijzen.
Bewijs. We bewijzen eerst dat deelverzamelingen van eindig zijn. We doen dat met inductie naar . Een deelverzameling van een lege verzameling is leeg, dus voor met is het waar.
Stel dat voor een deelverzamelingen van een verzameling met elementen eindig zijn. Laat een verzameling zijn met elementen. Dan is er een nummering . Deze bepaalt een nummering en dus . Laat een deelverzameling zijn van . De deelverzameling van is eindig. Er zijn twee mogelijkheden: en . In beide gevallen volgt eenvoudig dat eindig is.
Met volledige inductie volgt dat deelverzamelingen van eindige verzamelingen eindig zijn. Zij nu een deelverzameling van met . Dan is eindig, zeg . Er zijn bijecties en . De afbeelding is injectief en dus volgt uit Propositie 3.30 dat . □
Nog een gevolg van Propositie 3.30:
3.34 Gevolg. Voor alle natuurlijke getallen en geldt: als er een surjectieve afbeelding bestaat, dan .
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □