Matematické Fórum

Qwerrr · 06. 09. 2010 00:54

Nerozumím, proč se důkaz nevede takto:

Věta: Buď G pologrupa, n>1 přirozené číslo, a1,...,an náleží G. Pak výsledek součinu prvků a1,...,an (v uvedeném pořadí) nezáleží na jejich uzávorkování.

Důkaz indukcí:
I. n=2 platí
II. Předpokládejme, že tvrzení platí pro a1,...,a(n-1). Dokazujeme pro a1,...,an.

Uvažujme libovolné uzávorkování, např. (a1,...,ar).(a(r+1),...an). Každá z těchto závorek obsahuje maximálně (n-1) prvků pro 0<r<n. Indukční předpoklad je tedy splněn a věta je tedy dokázána? Nepoužil jsem zde asociativitu, čili by to platilo i na grupoidu, což je divné.

Je problém v tom, že toto platí jen pro r<n? Čili není možné vybrat r=n, což znamená, že závorkování není zcela libovolné? /r=n je situace, kdy jsou všechny prvky v jedné závorce/

I kdyby v tomto problém byl, tak to přece "učebnicový" důkaz neřeší:
v něm se předpokládá taktéž r<n a = [a1, . . . , ar] · [ar+1, . . . , an] = krok, kde využiju asociativitu = [a1] · [a2, . . . , an], kde hranaté závorky značí, že už to nezáleží na úzávorkování.

Kdyby byl problém v tom, že indkuční předpoklad je daný přesně pro a1,...,a(n-1), tak je "učebnice taky mimo", protože tvrdí, že [a2, . . . , an] nezáleží na uzávorkování.

Stýv · 06. 09. 2010 01:52

Každá z těchto závorek obsahuje maximálně (n-1) prvků pro 0<r<n. Indukční předpoklad je tedy splněn...

indukční předpoklad snad říká něco o počtu členů v jednotlivých závorkách?

Qwerrr · 06. 09. 2010 02:13

Zkusím trochu přesněji:
V indukční předpokladu se předpokládá, že součin prvků a1,...,aj pro nějaké 0<j<n nezáleží na uzávorkování.

V tom případě nerozumím, jak je možné, že na [a2, . . . , an] zde: a = [a1, . . . , ar] · [ar+1, . . . , an] = krok, kde využiju asociativitu = [a1] · [a2, . . . , an] lze aplikovat indukční předpoklad? Vždyť [a2, . . . , an] není součin prvků a1,...,aj pro nějaké 0<j<n ?

Rumburak

↑ Qwerrr:
Pokusím se pouze napovědět.
Že (G, . ) je pologrupa znamená, že na množině G je definována binární operace x.y splňující asociativní zákon.

Ujasněme si nejprve, co znamená symbol $a_1 \cdot a_2 \cdot \,...\, \cdot a_n$ pro n > 1 celé. Tento symbol nutno nějak definovat,
a sice nějakou rekursí - nejspíše

$a_1 \cdot a_2 \cdot \,...\, \cdot a_{j+1}\, := (a_1 \cdot a_2 \cdot \,...\, \cdot a_j )\cdot a_{j+1}$ , specilně např. $a_1 \cdot a_2 \cdot a_3 \cdot a_4 \cdot a_5 \,:= (((a_1 \cdot a_2) \cdot a_3) \cdot a_4) \cdot a_5$ .

Toho nutno v důkazu využít.
Indukční předpoklad V(n) o přirozeném čísle n je potřeba zformulovat dosti obecně, shruba takto:

Pro libovolné prvky $x_1,\, x_2, \, ..., \, x_j$ pologrupy G , kde $j \,\le \, n$ přirozené, výraz $x_1 \cdot x_2 \cdot \,...\, \cdot x_j$ není závislý
na případném jeho vnitřím uzávorkování.

(Předpokládám, že je jasný obsah tohoto výroku.)

Zkoumám-li součin $a_1 \cdot a_2 \cdot \,...\, \cdot a_{n+1}$ , pak např. za $x_1,\, x_2, \, ..., \, x_n$ mohu vzít $a_1,\, a_2, \, ..., \, a_n$ nebo také $a_2,\, a_3, \, ..., \, a_{n+1}$ ,
pakliže se to v důkazu bude hodit.

Qwerrr · 06. 09. 2010 17:21 — Editoval Qwerrr (06. 09. 2010 17:27)

↑ Rumburak:

Tak jsem zvědav, jestli jsem pochopil:

Chápu správně, že "není závislý na případném jeho vnitřním uzávorkování" znamená, že výraz $x_1 \cdot x_2 \cdot \,...\, \cdot x_j$ lze vždy zapsat ve tvaru $x_1 \cdot x_2 \cdot \,...\, \cdot x_{j+1}\, := (x_1 \cdot x_2 \cdot \,...\, \cdot x_j )\cdot x_{j+1}$ ?

A teď k hlavní věci, proč jsem to psal: Myslel jsem, že nějaká úprava a asociativní zákon v důkazu nejsou potřeba. Zkusím si to zodpovědět, proč jsem neměl pravdu. Taky to přepíšu do tvaru, který používáš ty, tj. indukční předpoklad, který platí pro $n$ , a dokazování pro $(n+1)$ .
Uvažujme "poslední závorky" $(a_{1} \cdot ... \cdot a_r) \cdot (a_{r+1} \cdot ... \cdot a_{n+1})$ . Co jsou to "poslední závorky"? Tak např. ve výrazu: $a_1 \cdot a_2 \cdot a_3 \cdot a_4 \cdot a_5 \,:= (((a_1 \cdot a_2) \cdot a_3) \cdot a_4) \cdot a_5$ jsou to závorky: $a_1 \cdot a_2 \cdot a_3 \cdot a_4 \cdot a_5 \,:= (((a_1 \cdot a_2) \cdot a_3) \cdot a_4) \c$ (ty úplně vnější)
Uvnitř těchto závorek již nezáleží na uzávorkování a to proto, že vždy platí $r \,\le \, n$ , a tedy indukční předpoklad je uvnitř závorek splněn. Nyní se ale starejme o celý výraz, tj. o všech $n+1$ prvků: Pokud by bylo $r=n$ , pak máme požadovaný výše definovaný tvar "nezávislosti na uzávorkování". Toto byl speciální případ, jenže my musíme postupovat obecně, tedy zahrnout i další případy a pro $r<n$ je situace zcela jiná! Ještě nevíme, jestli výraz $(a_{1} \cdot ... \cdot a_r) \cdot (a_{r+1} \cdot ... \cdot a_{n+1})$ pro $r<n$ je nezávislý na uzávorkování, protože jsme ho nenapsali ve výše definovaném tvaru "nezávislosti na uzávorkování". Je ho tedy třeba převést na požadovaný tvar a tento "převod na požadovaný tvar" už je onen "učebnicový důkaz".

?

Rumburak

↑ Qwerrr:
Toto $x_1 \cdot x_2 \cdot \,...\, \cdot x_{j+1}\, := (x_1 \cdot x_2 \cdot \,...\, \cdot x_j )\cdot x_{j+1}$ chápu, jak jsem už napsal, jako indukční krok k definici výrazu na levé straně,
který raději zapisujme ve tvaru $\prod_{i =1}^{j +1} x_i$ . Definujeme-li před tím ještě $\prod_{i =1}^{1} x_i\,\,:=x_1$ , máme tím podle věty o konstrukci úplnou indukcí
zajištěnu definici výrazu $\prod_{i =1}^n x_i$ pro libovolné přirozené číslo n a libovolný seznam $(x_1, \,..., \,x_n)$ prvků pologrupy G. Výrokem, že
tento výraz pro n > 2 není závislý na vnitřním uzávorkování (a jehož platnost pro každé takové n chceme dokázat), míním

W(n) $\forall_k \, \[k\in\{1,2, ..., n-1\} \, \Rightarrow \, \prod_{i =1}^n x_i = $\prod_{i =1}^k x_i$ \cdot $\prod_{i =k+1}^n x_i$ \]$ .

Teď už by ten důkaz, v němž za indukční předpoklad bereme

V(n) $\forall_j \, [\j \in\{3, ..., n\} \, \Rightarrow \, W(j)]$ ,

kde platnost V(3) je dána asociativním zákonem, snad neměl být těžký. Implikaci $V(n) \, \Rightarrow \, V(n+1)$ dokazujeme indukcí dle k ve W(n+1),
takže indukce se v důkazu věty uplatní clekem dvakrát - na dvou různých logických úrovních.