youproof.orgDeep Math. Human Access.

Bizonyítás

Először az átzárójelezhetőséget fogjuk igazolni. Nevezzük a * műveletet "szorzásnak", és alkalmazzunk a "tényezők" számára – azaz n-re – vonatkozó teljes indukciót. Indukciós feltételként tegyük fel, hogy az állítás igaz bármely legfeljebb n-1 tényezős szorzatra, vagyis hogy ezekre az átzárójelezés akárhogyan elvégezhető. Azt kell megmutatnunk, hogy ekkor egy tetszőleges n tényezős szorzatot is akárhogyan tudunk zárójelezni. Legyen például P egy ilyen tetszőlegesen zárójelezett n tényezős szorzat. Ekkor P a zárójelezése alapján legutolsóként elvégzendő szorzás művelete mentén két részre bontható:

P = L * R

Itt L és R egy-egy olyan kifejezés, amelyben a tényezők száma legfeljebb n-1. Az indukciós feltétel miatt tehát őket akárhogyan zárójelezhetjük, ezért az általánosság megsértése nélkül feltételezhetjük, hogy ezek a zárójelezések balra vannak rendezve, azaz valamilyen 1 \leq k < n esetén:

P = \underbrace{( \dots ((a_1 * a_2) * a_3) * \dots ) * a_k}_{=L} * \underbrace{( \dots ((a_{k+1} * a_{k+2}) * a_{k+3}) * \dots ) * a_n}_{=R}

Ám ekkor a * művelet asszociativitását k-szor alkalmazva a P kifejezést át tudjuk zárójelezni úgy, hogy az szintén egy balra rendezett zárójelezés legyen, azaz:

P = (\dots ((L * a_{k+1}) * a_{k+2}) * \dots ) * a_n
Az átzárójelezés technikai részletei

Jelöljük R_i-vel azt a balra rendezett zárójelezésű kifejezést, amelyet az R kifejezés első i darab tényezőjéből kapunk, azaz:

\begin{aligned} R_1 &= a_{k+1} \\ R_2 &= a_{k+1} * a_{k+2} \\ R_3 &= (a_{k+1} * a_{k+2}) * a_{k+3} \\ &\vdots \\ R_i &= (\dots ((a_{k+1} * a_{k+2}) * a_{k+3}) * \dots ) * a_{k+i} \\ &\vdots \end{aligned}

Először megmutatjuk, hogy bármely i index és az S halmaz tetszőleges x eleme esetén az x tényező bevihető az R_i kifejezés legbelső zárójelén belülre, azaz teljesül az alábbi:

x * R_i = (\dots (((x * a_{k+1}) * a_{k+2}) * a_{k+3}) * \dots ) * a_{k+i}

Ezt i-re vonatkozó teljes indukcióval igazoljuk. Tegyük fel indukciós feltételként, hogy az állítás igaz i-1-re, azaz:

x * R_{i-1} = (\dots (((x * a_{k+1}) * a_{k+2}) * a_{k+3}) * \dots ) * a_{k+i-1}

Most indukciós lépésként megmutatjuk, hogy ekkor ugyanez igaz lesz i-re is. Vegyük észre, hogy az R_i kifejezések fenti definíciója miatt tetszőleges i index esetén R_i = R_{i-1} * a_{k+i}. Emiatt az x * R_i kifejezést így is írhatjuk:

x * R_i = x * (\underbrace{R_{i-1} * a_{k+i}}_{=R_i}) = \dots

A * művelet asszociativitása miatt:

\dots = (x * R_{i-1}) * a_{k+i} = \dots

Végül az indukciós feltétel miatt:

\dots = (\dots (((x * a_{k+1}) * a_{k+2}) * a_{k+3}) * \dots ) * a_{k+i}

Felállítottuk a dominósort, most döntsük is le. Az i=1 esetén nincs mit bizonyítani, hiszen x * R_1 = x * a_{k+1} csak egyféleképpen zárójelezhető. Az i=2 esetén pedig a * művelet asszociativitása miatt nyilván x * R_2 = x * (a_{k+1} * a_{k+2}) = (x * a_{k+1}) * a_{k+2}.

Ezzel igazoltuk tehát az alábbi összefüggést:

x * R_i = (\dots (((x * a_{k+1}) * a_{k+2}) * a_{k+3}) * \dots ) * a_{k+i}

Ezt felhasználva az eredeti P kifejezést fogjuk lépésenként átzárójelezni úgy, hogy az egy balra rendezett zárójelezés legyen. Ehhez az R_i-hez hasonlóan vezessük be az L_j jelölést is, amely tehát jelölje azt a kifejezést, amelyet az L kifejezés első j darab tényezőjéből kapunk, azaz:

\begin{aligned} L_1 &= a_{1} \\ L_2 &= a_{1} * a_{2} \\ L_3 &= (a_{1} * a_{2}) * a_{3} \\ &\vdots \\ L_j &= (\dots ((a_{1} * a_{2}) * a_{3}) * \dots ) * a_{j} \\ &\vdots \end{aligned}

Vegyük észre, hogy ez alapján tetszőleges j index esetén L_j = L_{j-1} * a_j, így az eredeti P kifejezés átzárójelezésének első lépése így néz ki:

\begin{aligned} P &= \underbrace{( \dots ((a_1 * a_2) * a_3) * \dots ) * a_k}_{=L=L_k=L_{k-1} * a_k} * \underbrace{( \dots ((a_{k+1} * a_{k+2}) * a_{k+3}) * \dots ) * a_n}_{=R=R_{n-k}} = \\ &= (L_{k-1} * a_k) * R_{n-k} = L_{k-1} * (a_k * R_{n-k}) = \\ &= L_{k-1} * (\dots (((a_k * a_{k+1}) * a_{k+2}) * a_{k+3}) * \dots ) * a_n) = \dots \end{aligned}

A baloldali L=L_k kifejezés utolsó a_k tényezőjét tehát sikerült átvinni a jobboldali R kifejezés legbelső zárójelén belülre. Most ugyanezt a lépést végezzük el az eggyel rövidebb L_{k-1} kifejezésre is:

\dots = L_{k-2} * (\dots (((a_{k-1} * a_{k}) * a_{k+1}) * a_{k+2}) * \dots ) * a_n) = \dots

Látható, hogy ez az eljárás mindaddig folytatható, amíg a baloldali kifejezés el nem fogy. Ezen a ponton a P kifejezés valóban egy balra rendezett zárójelezésű kifejezés lesz:

\dots = (\dots (((a_1 * a_2) * a_3) * \dots ) * a_n)

Vagyis azt kaptuk, hogy amennyiben tetszőleges, legfeljebb n-1 tényezős szorzat átzárójelezhető, akkor ez igaz lesz az n tényezős szorzatokra is. Felállítottuk tehát a dominósort, és beláttuk, hogy bármely dominó felborítása esetén a soron következő dominó is fel fog borulni. Az első dominó felborítása ebben az esetben triviális, hiszen n=1 és n=2 esetén nincs mit bizonyítani, a legfeljebb egy vagy két tényezős szorzatok ugyanis csak egyféleképpen zárójelezhetők, n=3 esetén pedig a * művelet asszociativitása miatt nyilván (a_1 * a_2) * a_3 = a_1 * (a_2 * a_3).

Most igazoljuk a tetszőleges sorrendezhetőséget is. Vegyük észre, hogy a tényezők bármely sorrendje előáll egymás utáni szomszédos cserékből, tehát elég egyetlen ilyen cserére megmutatni, hogy az nem változtatja meg a szorzat értékét. Vegyük például az a_i és az a_{i+1} szomszédos elemeket. Ekkor a zárójelezés már bizonyított szabadsága miatt a teljes szorzatot így írhatjuk:

(\text{baloldali rész}) * (a_i * a_{i+1}) * (\text{jobboldali rész}) = \dots

Ám a kommutativitás miatt a_i * a_{i+1} = a_{i+1} * a_i, és így:

\dots = (\text{baloldali rész}) * (a_{i+1} * a_i) * (\text{jobboldali rész})

∎