Доказательство с помощью индукции

[geniy88]

Столкнулся с одним интересным доказательством. Представьте что у нас есть свободная группа и мы должны доказать, что если два элемента этой группы коммутативны то они являются степенью какого либо элемента этой группы. То есть, если $ a,b \in G $ и $ab=ba$, то тогда существует элемент $ c \in G$ такой, что $ a=c^{k}$ $b=c^{h}$ для некоторых натуральных чисел $k$ и $h$. Так вот доказательство начинается со слов: доказательство основано на индукции построенной на $l(a)+l(b)$, где $l(a)$ и $l(b)$ длина слов $a$ и $b$. Как понять, что доказательство основано на индукции построенной на $l(a)+l(b)$?
Заранее благодарен.

[ИСН]

Про метод математической индукции слышали когда-нибудь?

[geniy88]

про метод слышал, но как он связан с суммой $l(a)+l(b)$?

[ИСН]

Так и связан: по ней индукция.

[geniy88]

я использовал индукцию следующим образом, допустим мы должны доказать равенство для всех $n$, я доказывал что если для $k$ равенство верно, то верно и для $k+1$ и потом подставлял вместо $n$ единицу и при единице равенство обычно выполнялось. А как тут?

[ИСН]

так же, только роль $n$ выполняет эта штука, $l(a)+l(b)$.

[Dan B-Yallay]

А в этом случае идея такая:
1) Покажем, что для $l(a)+l(b)=1$ утверждение верно.
2) Допустим, что для $l(a)+l(b)=n$ утв. верно. Докажем, что оно верно для $l(a)+l(b)=n+1$

-- Вт апр 10, 2012 14:42:38 --

Опоздал. Повторенье - мать мучения.

[geniy88]

они рассматривают произвольные слова $a=x_{1}...x_{l}$ и $b=y_{1}...y_{m}$ и из равенства $ab=ba$ следует, что $x_{i}=y_{i}$ для $0<i<l+1$ и поэтому $b=au$ где $l(u)=m-l<l(b)$. И потом пишут $au=b=a^{-1}ab=a^{-1}ba=a^{-1}aua=ua$
и по индукции мы видим, что $a$ и $u$ являются степенью одного элемента.

[Sonic86]

geniy88 в сообщении #558862 писал(а):

они рассматривают произвольные слова $a=x_{1}...x_{l}$ и $b=y_{1}...y_{m}$ и из равенства $ab=ba$ следует, что $x_{i}=y_{i}$ для $0<i<l+1$ и поэтому $b=au$ где $l(u)=m-l<l(b)$. И потом пишут $au=b=a^{-1}ab=a^{-1}ba=a^{-1}aua=ua$
и по индукции мы видим, что $a$ и $u$ являются степенью одного элемента.

И что неясного?
(не помню, такое же доказательство или нет, но есть какое-то доказательство в книге Линдона Шуппа Комбинаторная теория групп в самом начале)
Можно и другое доказательство придумать.

[geniy88]

Sonic86, это из книги Д.Л. Джонсон Презентации групп. Неясно, то как они строят индукцию. Если для $a$ и $u$ выполняется то выполняется и для $a$ и $b$ это ясно. Но где тут $n$ и $n+1$ ведь $l(a)+l(u)+1 \neq l(a)+l(b) $.

[Sonic86]

geniy88 в сообщении #558934 писал(а):

Д.Л. Джонсон Презентации групп.

Угу, запомню...

geniy88 в сообщении #558934 писал(а):

Но где тут $n$ и $n+1$ ведь $l(a)+l(u)+1 \neq l(a)+l(b) $.

Ну тут не совсем так: мы можем предполагать, что доказано для суммарной длины $<l(a)+l(b)$, а подстановкой $b\equiv au$ мы приходим к соотношению $au=ua$ с меньшей суммарной длиной, но не обязательно меньшей ровно на 1 символ - можно на 2, на 3, ... - для них же верен шаг индукции.

[geniy88]

аха, теперь все ясно! Спасибо большое всем за ответы! Будем двигаться дальше :)

[Sonic86]

geniy88 в сообщении #558934 писал(а):

Sonic86, это из книги Д.Л. Джонсон Презентации групп

Ммм, а нету книжки в гугле не дадите ссылку?

[arseniiv]

(О названии книги.)

А разве не представления? Как-то странно звучит презентации.

[Sonic86]

arseniiv в сообщении #559085 писал(а):

А разве не представления? Как-то странно звучит презентации.

Да, я так тоже пробовал гуглить - нету. На английском только не пробовал ... Так и есть...
Блин, а на русском нет опять?

(Оффтоп)

гыыы... скачал хотя бы на английском...