Inductiebewijs met meer dan 1 variabele

Stel dat er een implicatie is van de vorm: (P(p) en P(q)) impliceert P(r) met P(x) = x zit in een bepaalde taal L. In dit voorbeeld hebben we dat p en q strings zijn in een bepaalde taal L en r = pq (de concatenatie). Gevraagd is dus om te bewijzen dat: als p en q in L zitten, dan zit pq in de taal L. Stel dat men dit met inductie wil doen, waarom is het dan voldoende om de inductie alleen over p (of alleen over q) te doen? Ik dacht dat inductie over alle variabelen moest?

Erik J
Student universiteit - donderdag 25 november 2021

Antwoord

Dat hangt een beetje van de situatie af, maar beide mogelijkheden zouden zich voor kunnen doen.

Het zou inderdaad zo kunnen zijn dat het volgende bewijsschema werkt:

"Laat $p$ een willekeurige string zijn; we bewijzen met inductie dat voor elke $q$ ook $pq$ in de taal zit."

Maar in sommige ingewikkelder situaties zou het kunnen dat je zowel inductie naar $p$ als naar $q$ moet doen. Dan krijg je dit:

"Neem aan dat voor elke string $s$ korter dan $p$ (of iets dergelijks) geldt dat voor elke $q$ ook $sq$ in de taal zit. We bewijzen nu met inductie dat voor elke $q$ ook $pq$ in de taal zit."

In het eerste geval zal alleen $p$ een rol in het bewijs spelen; in het tweede geval kun je op kortere strings terugvallen.
Het is maar net wat werkt.

Op de vraag "Waarom is het voldoende?" is het antwoord: als het bewijs goed is is het voldoende. Het hoeft niet met inductie naar $p$ maar als inductie naar $p$ handiger is zou ik het wel mooi gebruiken.

kphart
donderdag 25 november 2021

Re: Inductiebewijs met meer dan 1 variabele

©2001-2024 WisFaq