Matematyka.pl

Chciałbym udowodnić uogólnioną łączność czyli inaczej mówiąc możliwość dowolności nawiasów w zapisie \(\displaystyle{ a_1 + a_2 + ... + a_n}\). Dochodzę do wniosku, że to wcale nie jest takie trywialne jak mi się na początku wydawało. Być może mylnie.

Jedyne co mi przychodzi do głowy to dowód "algorytmowo-indukcyjny". Nie wiem na ile jest poprawny, dlatego poniżej moja próba.

Weźmy dowolne \(\displaystyle{ n}\) i załóżmy, że dla wszystkich \(\displaystyle{ k<n}\) łączność została udowodniona. Musimy pokazać, że łączność zachodzi dla \(\displaystyle{ n}\). Musimy zatem pokazać, że dla \(\displaystyle{ n}\), dla dowolnego ułożenia nawiasów otrzymamy standardowy układ nawiasów, który zapisujemy po prostu bez nawiasów.

Wiemy, że w naszym dowolnym ułożeniu występuje bezspośrednio \(\displaystyle{ b:=(a_{i_1} + a_{i_2})}\). Do \(\displaystyle{ b}\) dodawany jest z kolei element. Mamy tutaj dwie możliwośc:
1) Element ma postać \(\displaystyle{ a_{i}}\), wtedy korzystamy z założenia i otrzymujemy \(\displaystyle{ (a_{i_1} + a_{i_2} + a_{i_3})}\).
2) Element ma postać \(\displaystyle{ c:= (a_{i_3} + ... + a_{i_p})}\), gdzie \(\displaystyle{ p<n}\). Wtedy powołujemy się na założenie i usuwamy wszystkie nawiasy w \(\displaystyle{ c}\). Następnie dodajemy \(\displaystyle{ b}\) i \(\displaystyle{ c}\) korzystając z założenia idukcyjnego.

Następnie postępujemy analogicznie, aż znikną wszystkie nawiasy.

Tak nie do końca mi się podoba ten dowód, bo mam wrażenie, że jest dość opisowy. Pierw myślałem, żeby może zdefiniować taką łącznośc rekurencyjne, ale tutaj też mam pewne problemy.

-- 21 kwi 2016, o 01:00 --

Chyba jednak przekombinowałem, bo teraz dochodzą do wniosku, że:
Mam sumę z pewnymi nawiasami dla \(\displaystyle{ n}\), \(\displaystyle{ a_1 + ... +a_n}\). Wybieram \(\displaystyle{ b_j = a_j a_{j+1}}\). Mam więc sumę z pewnymi nawiasami \(\displaystyle{ a_1 + ... + a_{j-1} + b_k + a_{j+2} + ... + a_n}\). Teraz korzystam z założenia indukcyjnego, więc mogę sobie dowolnie ustawić nawiasy. Więc ustawiam (w sumie nawet nie muszę jakoś specjalnie ustawiać tylko korzystam z podstawowych nawiasów) \(\displaystyle{ (...(a_1 + a_2)+a_3)...)+a_{j-1})(a_{j} + a_{j+1})) + a_{j+2})...)+ a_n}\). I teraz z podstawowego prawa łączności przestawiam sobie nawiasy tak, że otrzymuje podstawową formę. Koniec dowodu.

Przekombinowałeś.

W definicji:

• Działanie \(\displaystyle{ \circ}\) jest łączne w zbiorze \(\displaystyle{ X}\) gdy:
  
  • \(\displaystyle{ \forall_{a, b, c\in X}\quad a\circ b\circ c=(a\circ b)\circ c=a\circ(b\circ c)}\)

\(\displaystyle{ a}\), \(\displaystyle{ b}\) i \(\displaystyle{ c}\) mogą być wyrażeniami typu \(\displaystyle{ (p\circ q)}\) (zawierające nawiasy). Innymi słowy, nie muszą to być „atomy” zbioru \(\displaystyle{ X}\).

A gdzieś pisalem, ze to muszą być "atomy"? Nie wiem jak ta odpowiedź odnosi się do mojego posta.

Moim zdaniem to, co chcesz udowodnić, bezpośrednio wynika z definicji własności łączności działań i mój post właśnie tego dotyczył.

SlotaWoj pisze:Moim zdaniem to, co chcesz udowodnić, bezpośrednio wynika z definicji własności łączności działań i mój post właśnie tego dotyczył.

Nie mogę się tutaj zgodzić. Przecież z góry założyłeś prawdziwość tych wyrażeń złożonych czego robić nie wolno. Z definicji wynika, owszem, to co napisałeś tylko Ty operaujsz na tych samych złożonych wyrażeniach po dwóch stronach, a ja mówię, że wcale nie wiem czy są takie same - to trzeba pierw udowodnić co też zrobiłem w pierwszym poście pod koniec.

Definicja własności łączności działań jest niejawnie indukcyjna. Wynik działania o tej własności jest niezależny od jakiejkolwiek możliwej kolejności jego wykonania, wyznaczoną przez dowolnie rozbudowaną, w tym zagnieżdżoną strukturę nawiasów.

Wynik działania o tej własności jest niezależny od jakiejkolwiek możliwej kolejności jego wykonania, wyznaczoną przez dowolnie rozbudowaną, w tym zagnieżdżoną strukturę nawiasów.

Gdzie definicja o tym mówi?
Definicja mówi jedynie jak zachowywać się w przypadku trzech elementów (nieważne jak bardzo skomplikowanych). Natomiast, żeby mówić o równośc muszę wiedzieć, że są równe, a do tego muszę zbadać ich strukturę. Twoja podejście jest na zasadzie "muszą być równe, bo definicja tak mówi", jednak ja w deifnicji nic takiego nie odnajduję. Być może ja czegoś tu nie rozumiem...

novicjusz pisze: Tak nie do końca mi się podoba ten dowód, bo mam wrażenie, że jest dość opisowy.

Dowód opisowy, to nie problem ogólnie rzecz biorąc. Mi też ten dowód się nie podoba, a to dlatego że nie wyrażasz się zbyt jasno.

novicjusz pisze: Chyba jednak przekombinowałem, bo teraz dochodzą do wniosku, że:
Mam sumę z pewnymi nawiasami dla \(\displaystyle{ n}\), \(\displaystyle{ a_1 + ... +a_n}\). Wybieram \(\displaystyle{ b_j = a_j a_{j+1}}\). Mam więc sumę z pewnymi nawiasami \(\displaystyle{ a_1 + ... + a_{j-1} + b_k + a_{j+2} + ... + a_n}\). Teraz korzystam z założenia indukcyjnego, więc mogę sobie dowolnie ustawić nawiasy. Więc ustawiam (w sumie nawet nie muszę jakoś specjalnie ustawiać tylko korzystam z podstawowych nawiasów) \(\displaystyle{ (...(a_1 + a_2)+a_3)...)+a_{j-1})(a_{j} + a_{j+1})) + a_{j+2})...)+ a_n}\). I teraz z podstawowego prawa łączności przestawiam sobie nawiasy tak, że otrzymuje podstawową formę. Koniec dowodu.

Ten dowód też nie jest do końca jasny

SlotaWoj pisze:Moim zdaniem to, co chcesz udowodnić, bezpośrednio wynika z definicji własności łączności działań i mój post właśnie tego dotyczył.

Też się nie zgodzę
Dla trzech elementów sprawę załatwia łączność działania, ale dla \(\displaystyle{ n}\)
Potrzebny jest dowód

novicjusz pisze:

Wynik działania o tej własności jest niezależny od jakiejkolwiek możliwej kolejności jego wykonania, wyznaczoną przez dowolnie rozbudowaną, w tym zagnieżdżoną strukturę nawiasów.

Gdzie definicja o tym mówi?
Definicja mówi jedynie jak zachowywać się w przypadku trzech elementów (nieważne jak bardzo skomplikowanych).

Właśnie dla trzech elementów sprawę załatwia łączność, a dla \(\displaystyle{ n}\) to też prawda, ale wymaga dowodu
Może przedstawie ten dowód, ale nie teraz, bo teraz czuje się zmęczony

A co w tym dowodzie jest nie tak? Mogę rozpisać.

Udowodnijmy, że każdy wyraz (z daną konstelacją nawiasów) dla \(\displaystyle{ n \ge 3}\) można zapisać w formie \(\displaystyle{ (...(a_1 + a_2) + a_3)...) + a_n}\).

Początek indukcyjny:
\(\displaystyle{ n=3}\): Wynika wprost z definicji.

\(\displaystyle{ n \rightarrow n+1}\):
Załóżmy, że dla \(\displaystyle{ n}\) wszystkie wyrazy można zapisać w powyższej formie. Weźmy teraz wyraz dla \(\displaystyle{ n+1}\) i musimy pokazać, że można go sprowadzić do powyższej postaci. W tym wyrazie musi występować \(\displaystyle{ (a_j + a_{j+1})}\) (co jest oczywiste), a więc zdefiniujmy \(\displaystyle{ b:= (a_j + a_{j+1})}\). Zatem wyrażenie możemy zapisać w postaci \(\displaystyle{ n}\) wyrazowej. Korzystając z założenia indukcyjnego mamy \(\displaystyle{ (...(a_1 + a_2) + a_3)...)+b})... + a_{n+1}}\), a więc mamy standardowy układ nawiasów dla \(\displaystyle{ n}\) wyrazów, a to jest równe \(\displaystyle{ (...(a_1 + a_2) + a_3)...)+(a_j+a_{j+1}))... + a_{n+1}}\). Następnie wystarczy skorzystać tylko z prawa łączności i otrzymujemy standardowe ułożenia dla \(\displaystyle{ n+1}\) co mieliśmy pokazać.

novicjusz pisze: W tym wyrazie musi występować \(\displaystyle{ (a_j + a_{j+1})}\) (co jest oczywiste)

Dla mnie nie jest to oczywiste, choć może to prawda, trudno mi powiedzieć

Możesz bowiem mieć \(\displaystyle{ a _{1}+\left( a _{2}+\left( a _{3}+\left( a _{4}+\left( a _{5}+a _{6}\right) \right) \right) \right)}\)

Czytając od lewa do prawej dopiero na końcu masz \(\displaystyle{ a _{5}+a _{6}}\) sumę dwóch elementów, w samym środku
Istnieje bowiem całe bogactwo możliwości ustawiania nawiasów

novicjusz pisze: W tym wyrazie musi występować \(\displaystyle{ (a_j + a_{j+1})}\) (co jest oczywiste)

Jak mówiłem, trudno mi to jest rozstrzygnąć, z powyższych względów, ale przyjmijmy że tak jest, idźmy dalej
Ale dalej też nie dobrze

\(\displaystyle{ (...(a_1 + a_2) + a_3)...)+b})... + a_{n+1}}\)

Piszesz że \(\displaystyle{ b}\) po prostu jest dodawane do sumy z lewej strony, a następnie po prostu jest dodawana suma z prawej strony
A możesz mieć np.
\(\displaystyle{ a_1 +\left( a _{2}+\left( a _{3}+\left( a _{4}+ a _{5}\right) \right)\right)}\)
Wyróżnijmy \(\displaystyle{ a _{4}+a _{5}}\)
Nie jest dodawane suma z lewej strony, tylko z lewej strony jest dodawany element \(\displaystyle{ a _{3}}\), do nowej sumy z lewej strony nie jest dodawana suma, lecz element \(\displaystyle{ a _{2}}\)
i do powstałej sumy na koniec \(\displaystyle{ a _{1}}\)
Twój dowód nie uwzględnia wszystkich możliwości ustawiania nawiasów A jest to bardzo bogata
rodzina

Jakub Gurak pisze:Dla mnie nie jest to oczywiste, choć może to prawda, trudno mi powiedzieć

Wynika to z samej istoty używania nawiasów. Nawiasy służą temu, abyśmy znali kolejność wykonywania operacji. Możemy je usunąć tylko wtedy, gdy wiemy, że kolejność nie ma znaczenia. A w chwili obecnej wiemy jedynie, że kolejność nie ma znaczenia da \(\displaystyle{ n}\) (założenie). Dla \(\displaystyle{ n+1}\) musimy to dopiero udowodnić, dlatego wyrażenie \(\displaystyle{ (a_j + a_{j+1})}\) musi występować.

Jakub Gurak pisze: Możesz bowiem mieć \(\displaystyle{ a _{1}+\left( a _{2}+\left( a _{3}+\left( a _{4}+\left( a _{5}+a _{6}\right) \right) \right) \right)}\)

Czytając od lewa do prawej dopiero na końcu masz \(\displaystyle{ a _{5}+a _{6}}\) sumę dwóch elementów, w samym środku
Istnieje bowiem całe bogactwo możliwości ustawiania nawiasów.

W moim dowodzie kolejność jest nieistotna. Dowód nie bazuje na tym, że wyraz \(\displaystyle{ (a_j + a_{j+1})}\) jest w jakimś konkrentym miejscu. I jak sam widzisz u Ciebie również występuje \(\displaystyle{ (a_5 + a_6)}\) czyli w Twoim wyrażeniu jest postać \(\displaystyle{ (a_j + a_{j+1})}\).

Jakub Gurak pisze: Piszesz że \(\displaystyle{ b}\) po prostu jest dodawane do sumy z lewej strony, a następnie po prostu jest dodawana suma z prawej strony
A możesz mieć np.
\(\displaystyle{ a_1 +\left( a _{2}+\left( a _{3}+\left( a _{4}+ a _{5}\right) \right)\right)}\)
Wyróżnijmy \(\displaystyle{ a _{4}+a _{5}}\)
Nie jest dodawane suma z lewej strony, tylko z lewej strony jest dodawany element \(\displaystyle{ a _{3}}\), do nowej sumy z lewej strony nie jest dodawana suma, lecz element \(\displaystyle{ a _{2}}\)
i do powstałej sumy na koniec \(\displaystyle{ a _{1}}\)
Twój dowód nie uwzględnia wszystkich możliwości ustawiania nawiasów A jest to bardzo bogata
rodzina

Tego w ogóle nie rozumiem - w moim odczuciu te Twoje rozważania są zupełnie zbędne. Dzięki \(\displaystyle{ b}\) mam wyraz \(\displaystyle{ n}\) elementowy, a co za tym idzie mogę skorzystać z założenia i dowolnie przestawić sobie nawiasy. Po przestawianiu rozpisuje \(\displaystyle{ b}\) i korzystam z prawa łączności i dostaję standardowe ułożenie nawiasów co kończy dowód.

novicjusz pisze:

SlotaWoj pisze:Definicja własności łączności działań jest niejawnie indukcyjna. Wynik działania o tej własności jest niezależny od jakiejkolwiek możliwej kolejności jego wykonania, wyznaczoną przez dowolnie rozbudowaną, w tym zagnieżdżoną strukturę nawiasów.

Gdzie definicja o tym mówi?
Definicja mówi jedynie jak zachowywać się w przypadku trzech elementów (nieważne jak bardzo skomplikowanych). ...

Ograniczmy się do własności łączności dodawania w (nieograniczonych) zbiorach liczb \(\displaystyle{ X}\):

• \(\displaystyle{ \forall_{a, b, c\in X}\quad a+b+c=(a+b)+c=a+(b+c)}\)

Każdą liczbę można przedstawić jako sumę dwóch innych liczb i niech \(\displaystyle{ a=d+e}\). Z definicji mamy wtedy:

• \(\displaystyle{ \forall_{d, e, b, c\in X}\quad d+e+b+c=(d+e)+b+c=((d+e)+b)+c=(d+e)+(b+c)=...}\)

ale też:

• \(\displaystyle{ ...=d+e+(b+c)=d+(e+(b+c))=...}\)

oraz także:

• \(\displaystyle{ ...=d+(e+b)+c=(d+e+b)+c=d+(e+b+c)}\)

Dla czterech składników (przy ustalonej ich kolejności, co musimy założyć, bo działanie nie musi być przemienne) to co napisałem wyczerpuje wszystkie możliwe struktury nawiasowe: bez nawiasów, tylko nawiasy 1-go poziomu, nawiasy 1-go i 2-go poziomu.

To co przedstawiłem powyżej ilustruje, co rozumiem jako niejawną indukcyjność definicji.

Definicja używa jedynie trzech składników i dzięki temu jest zwięzła, ale to nie oznacza, że wprowadzenie do niej dodatkowych składników zmienia jej istotę i trzeba czegoś dowodzić.

Trochę to koresponduje z definicją składnika, którą posługują się analizatory składni wyrażeń:

• składnik : czynnik
  • lub
  składnik : składnik + czynnik

Gdy działanie „+” nie jest przemienne, jest jeszcze:

• składnik : czynnik + składnik

Tutaj składnik jest zdefiniowany przez czynnik, operator sumy i rekurencję.

Niestety mam dalej z tym problem. Pokazałeś coś dla trzech składników, następnie dla czterech i piszesz, że dalej nie trzeba, bo tak przecież jest. Przynajmniej ja tak to widzę. Nie pokazałeś w ogóle czy łącznośc jest prawdziwa dla 20 czy 50 składników. Zawsze możemy argumentować na zasadzie, że coś działa dla określonych wartości to dla reszty też będzie działało i nawet gdy to jest fakt, to z formalnego punktu widzenia nic nie zostało pokazane.

Bo właśnie na tym polega „indukcyjność” definicji (w wielu źródłach nazywana także rekurencyjnością, tzn. odwołującą się do samej siebie). Przecież z definicją indukcyjną ciągu arytmetycznego:

• \(\displaystyle{ a_{n+1}=a_n+r}\)

nie ma żadnych problemów.

Problem jest tylko w tym, że w przypadku definicji własności łączności działań jej indukcyjność nie jest to wyrażona wprost, ale trzeba się jej domyślać, bo (w przypadku liczb) każdą liczbę można przedstawić jako sumę dwóch innych liczb. W przypadku innych obiektów, na których są wykonywane działania łączne będzie się to wyrażało inaczej, ale idea jest podobna lub wręcz taka sama.

Edit:
Oczywiście, z tym (w przypadku dodawania liczb): każdą liczbę można przedstawić jako sumę dwóch innych liczb trzeba trochę uważać, bo w zbiorze liczb naturalnych \(\displaystyle{ \NN=\{1,\,2,\,3,\,...\}}\) jest kłopot z jedynką, ale wystarczy ów zbiór rozszerzyć o \(\displaystyle{ \{0\}}\) i przyjąć: ... dwóch innych, niekoniecznie różnych od siebie i od sumy, i po problemie.
Oczywiście „puryści” matematyczni mogą uważać, że w związku z tym w klasycznym zbiorze liczb naturalnych (bez zera) to moje uzasadnienie niejawnej indukcyjności definicji własności łączności dodawania liczb nie jest wystarczające.

Niech działanie \(\displaystyle{ *}\) na zbiorze \(\displaystyle{ X}\) będzie łączne, to znaczy dla dowolnych \(\displaystyle{ a, b, c \in X}\) zachodzi \(\displaystyle{ a*(b*c) = (a*b)*c}\). Wtedy dowolne rozmieszczenie nawiasów w wyrażeniu \(\displaystyle{ a_1 * a_2 * \ldots * a_n}\) nie zmienia wartości wyrażenia.

Dowód. Skorzystamy z pewnego wariantu indukcji: jeżeli teza jest spełniona dla wszystkich \(\displaystyle{ m < n}\), to możemy ją udowodnić takżde dla \(\displaystyle{ n}\). Dla \(\displaystyle{ n = 1, 2}\) nie za bardzo jest co sprawdzać, dla \(\displaystyle{ n = 3}\) to jest po prostu zwykła łączność.

Pokażemy, że zawsze można nawiasy przesunąć w lewo, do postaci \(\displaystyle{ ((\ldots((a_1 * a_2) * a_3 ) * \ldots)*a_n)}\) (\(\displaystyle{ \star}\)).

Ustalmy \(\displaystyle{ n > 3}\) i załóżmy, że dla \(\displaystyle{ m < n}\) teza rzeczywiście jest spełniona. Nieważne jak rozstawimy nawiasy w \(\displaystyle{ a_1 * \ldots * a_n}\), któreś mnożenie wykonujemy na końcu. Mamy więc do czynienia z \(\displaystyle{ A * B}\), gdzie \(\displaystyle{ A = a_1 * \ldots * a_m}\) oraz \(\displaystyle{ B = a_{m+1} * \ldots * a_n}\) (gdzie \(\displaystyle{ 0 < m < n}\)). Z założenia indukcyjnego możemy uporządkować nawiasy w \(\displaystyle{ A}\) i \(\displaystyle{ B}\) do postaci \(\displaystyle{ \star}\).

Zauważmy, że skoro \(\displaystyle{ B = C * a_n}\), to \(\displaystyle{ A * (C * a_n) = (A*C) * a_n}\) i tu właściwie dowód się kończy: to jest to samo, co w Twoim pierwszym poście, tylko sformalizowane, bo w skończenie wielu krokach powyciągamy tak wszystkie "ostatnie" czynniki.