Zonder verlies van algemeenheid

In een wiskundig bewijs geeft de term zonder verlies van algemeenheid (z.v.v.a.) aan dat men een aanname maakt maar dat het bewijs nog steeds geldig is voor alle mogelijke gevallen. Voor de andere gevallen kan namelijk dezelfde redenering gebruikt worden, vaak door symmetrie. Zo kan men in een bewijs twee getallen a en b hebben waarvoor a < b of b < a geldt: het is mogelijk het bewijs te vervolgen onder de aanname dat a < b, aangezien het bewijs in het geval b < a op dezelfde manier zou verlopen — men kan de variabelen immers zo hernoemen dat de rollen van a en b worden omgewisseld.

Voorbeeld

We beschouwen de volgende situatie:

Drie objecten zijn elk rood of blauw geverfd.

De volgende stelling is te bewijzen:

Er zijn ten minste twee objecten met dezelfde kleur.

Het bewijs:

We nemen zonder verlies van algemeenheid aan dat het eerste object rood is. Als een van de twee andere objecten rood is, dan geldt de stelling.

Als de beide andere objecten blauw zijn, geldt de stelling ook.

Toelichting:

Het is toegestaan deze aanname te maken, aangezien de gevolgde redenering ook geldt als het eerste object blauw is.

Er zijn acht (2³) mogelijke permutaties:

1. RRR
2. RRB
3. RBR
4. RBB
5. BBB (inverse van 1.)
6. BBR (inverse van 2.)
7. BRB (inverse van 3.)
8. BRR (inverse van 4.)

We zien dat 1 t/m 4 dezelfde vorm hebben als 5 t/m 8, de gevallen waarbij het eerste object blauw is (men kan ze in elkaar omzetten door rood en blauw om te wisselen). Het bewijs beschouwt 1 t/m 4; de overige gevallen (5 t/m 8) zijn symmetrisch aan 1 t/m 4, waardoor de aanname zonder verlies van algemeenheid gemaakt mag worden. Het bewijs vervolgt door eerst de permutaties 1 t/m 3 te beschouwen (waarbij er een tweede rood object is naast het eerste rode). Het bewijs wordt voltooid bij de vierde permutatie (met slechts één rood object).

Externe links

• (en) Without loss of generality (WLOG), PlanetMath