Łączność działania- niepotrzebne nawiasy, prościej

[Jakub Gurak]

Napisze jeszcze raz, bo udało mi się uzyskać prostszy dowód
Temat ma trafić do kompendium ciekawostek

Będę chciał uzasadnić że jeśli działanie jest łączne, to nie jest potrzebne dawanie nawiasów

Dokładniej, jeśli mamy działanie mnożenia, które jest łączne oraz ciąg elementów \(\displaystyle{ a _{1}a _{2}\ldots a_{n}}\) to wynik mnożenia \(\displaystyle{ a _{1}a _{2}\ldots a_{n}}\) nie zależy od ustawienia nawiasów

Istota jest dla \(\displaystyle{ n \ge 4}\)

Dowód
Łączność oznacza że mamy prawo \(\displaystyle{ a \left( bc\right)=\left( ab\right) c}\)

Dowód korzysta z indukcji porządkowej- przez indukcję ze względu na długość ciągu (ilość zmiennych w ciągu )
Dla \(\displaystyle{ n=1}\) i \(\displaystyle{ n=2}\) Wynik \(\displaystyle{ a_{1}}\) i odpowiednio \(\displaystyle{ a_{1}a_{2}}\) oczywiście nie zależy od ustawienia nawiasów
Niech \(\displaystyle{ n=3}\)
Wynik mnożenia \(\displaystyle{ a_{1}a_{2}a_{3}}\) nie zależy od ustawienia nawiasów na mocy prawa łączności \(\displaystyle{ \left( a_{1}a_{2}\right) a_{3}=a_{1}\left( a_{2}a_{3}\right)}\)

Niech \(\displaystyle{ n \ge 4}\) i załóżmy że dla każdego \(\displaystyle{ m}\) naturalnego dodatniego ale mniejszego od \(\displaystyle{ n}\) oraz dowolnego ciągu \(\displaystyle{ a _{1}a _{2}\ldots a_{m}}\) wynik mnożenia \(\displaystyle{ a _{1}a _{2}\ldots a_{m}}\) nie zależy od ustawienia nawiasów
Weźmy dowolny ciąg \(\displaystyle{ a _{1}a _{2}\ldots a_{n}}\)
Niech \(\displaystyle{ P=\left( \left( \left( \left( a _{1} a _{2}\right) a _{3}\right)a _{4}\right)\ldots a _{n} \right)}\) (*)
Pokażemy że każde ustawienie nawiasów w \(\displaystyle{ a _{1}a _{2}\ldots a_{n}}\) wyznacza iloczyn równy \(\displaystyle{ P}\)
Aby to udowodnić zauważmy że przy jakimkolwiek ustawieniu nawiasów, któreś mnożenie wykonujemy na końcu, wobec czego \(\displaystyle{ a _{1}a _{2}\ldots a_{n}}\) jest iloczynem dwóch ciągów o długościach silnie krótszych od \(\displaystyle{ n}\)
\(\displaystyle{ a _{1}a _{2}\ldots a_{n}=\Bigl (a_{1}\ldots a_{l} \Bigr ) \Bigl ( a_{l+1}\ldots a_{n}\ \Bigr )}\)
Zanotujmy jeszcze jedną postać:
\(\displaystyle{ \left (a_{m} \left ( a_{m+1}\left( \ldots \left( a_{n-2} \left ( a_{n-1}a_{n}\right )\right)\right)\right)\right)}\) (**)
Ponieważ \(\displaystyle{ a _{1}a _{2}\ldots a_{n}}\) jest iloczynem dwóch ciągów o długościach silnie krótszych od \(\displaystyle{ n}\) więc na mocy założenia indukcyjnego możemy dowolnie ustawić nawiasy dla tych ciągów
Sprowadźmy pierwsze wyrażenie tego iloczynu do postaci (*), a drugie do postaci (**)
Tzn.
\(\displaystyle{ \Bigl (a_{1}\ldots a_{l} \Bigr ) \Bigl ( a_{l+1}\ldots a_{n}\ \Bigr )=\Bigl( \left( \left( \left( a _{1} a _{2}\right) a _{3}\right)a _{4}\right)\ldots a _{l} \Bigr) \Bigl (a_{l+1} \bigl ( a_{l+2}\bigl( \ldots \bigl ( a_{n-2} \bigl ( a_{n-1}a_{n}\bigr )\bigr )\Bigr)=}\)
\(\displaystyle{ =\Bigl( \bigl( \left( \left( a _{1} a _{2}\right) a _{3}\right)\ldots a _{l}\bigr) a _{l+1}\Bigr) \Bigl(a_{l+2} \bigl( a_{l+3}\bigl( \ldots \bigl( a_{n-2} \bigl( a_{n-1}a_{n}\bigr)\bigr)\bigr)\bigr)\Bigr)=}\) Skorzystaliśmy z łączności, kontynuując
\(\displaystyle{ =\Bigl( \bigl( \left( \left( a _{1} a _{2}\right) a _{3}\right)\ldots a _{l+1}\bigr) a _{l+2}\Bigr) \Bigl(a_{l+3} \bigl( a_{l+4}\bigl( \ldots \bigl( a_{n-2} \bigl( a_{n-1}a_{n}\bigr)\bigr)\bigr)\bigr)\Bigr)=\ldots}\)
\(\displaystyle{ =\Bigl ( \left( \left( a _{1} a _{2}\right) a _{3}\right) \ldots a _{n-2}\Bigr)
\Bigl( a_{n-1}a_{n}\Bigr )=\Bigl ( \bigl (\left( \left( a _{1} a _{2}\right) a _{3}\right) \ldots a _{n-2}\bigr )a_{n-1} \Bigr) a_{n}=P}\) Korzystaliśmy z łączności
Zatem dowolne ustawienie nawiasów wyznacza tą samą wartość \(\displaystyle{ P}\) i krok indukcyjny został dowiedziony
Na mocy indukcji porządkowej twierdzenie jest prawdziwe dla ciągów dowolnej długości

Jedno mnie niepokoi
W końcówce dowodu, robiąc rachunek, w pewnym momencie napisałem \(\displaystyle{ =\ldots}\)
i zakończyłem rachunek. Niby widać że tak można zawsze przesunąć nawiasy, ale robiąc dowód
chyba nie powinienem tak pisać Czy komuś to będzie przeszkadzać??

Temat ma trafić do kompendium ciekawostek

[M Maciejewski]

Drobna uwaga: jest problem z nawiasami. W drugim czynniku (w kilku miejscach) masz więcej otwierających nawiasów, niż zamykających. Jeśli chcesz to dopracować, aby gdzieś umieścić, warto to poprawić.
Jeśli chodzi o mnie, wielokropek mi nie przeszkadza. Wielokropek tłumaczę tak: ,,To można udowodnić prostą indukcją. Jest ona na tyle prosta, że pozwolę sobie zrobić krok indukcyjny jedynie dla pierwszego i ostatniego przejścia."