WisFaq!

Re: Inductiebewijs met meer dan 1 variabele

Het is precies deze statement die mij nog niet duidelijk is die u heeft gequote:

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

U neemt aan dat p willekeurig is, dus de bewering zal voor alle p moeten gelden. Maar met inductie bewijs je ook iets voor alle q. Dus eigenlijk heb je een dubbele voor alle kwantor? Ik vind het nog raar dat je p zomaar wel mag "isoleren" en dan alleen de inductie over q doet terwijl we zeggen dat: "voor elke q ook pq in de taal zit". Waarbij nu p niet meer geïsoleerd is maar gebruikt wordt in de implicatie.

Erik Jan
25-11-2021

Antwoord

Je bewering ziet er zo uit
$$(\forall p)(\forall q)( P(p)\land P(q) \Rightarrow P(pq) )
$$Je kunt dat lezen als: voor alle $p$ en alle $q$ geldt iets en dan zou ik dat proberen te bewijzen als "Laat $p$ en $q$ willekeurige strings zijn, we bewijzen $\ldots$".
Als dat lukt ben ik klaar.

Je kunt ook (extra) haakjes zetten:
$$(\forall p)\bigl((\forall q)( P(p)\land P(q) \Rightarrow P(pq) )\bigr)
$$je krijgt een logisch equivalente bewering, maar het accent is een beetje verschoven: voor alle $p$ geldt iets (namelijk dat voor alle $q$ in combinatie met $p$ iets geldt).

Dan zou ik beginnen met "Laat $p$ een willekeurige string zijn"; in het bewijs van $(\forall q)( P(p)\land P(q) \Rightarrow P(pq) )$ zou ik kunnen zeggen "Laat $q$ een willekeurige string zijn" en dan zit ik ik het eerste bewijs.
Maar ik zou ook kunnen besluiten die bewering met inductie naar $q$ te bewijzen, en als dat lukt mag ik, omdat $p$ willekeurig was, $(\forall p)$ er weer voor zetten en ben ik klaar.

Er is overigens geen sprake van `isoleren' of zo; we gebruiken gewoon de gangbare regels: als je iets voor alle $p$ moet bewijzen dan bewijs je het voor een willekeurige $p$ die voor de duur van het bewijs vast is. Die $p$ speelt natuurlijk in dat bewijs een rol.

kphart
25-11-2021