Ассоциативность произвольного числа сомножителей

[Утундрий]

Пусть для некоторого "умножения" доказана ассоциативность произведения трех элементов (троек)

$$(ab)c = a(bc)=:abc \qquad (1)$$

Тогда для четверок имеется всего три различных способа расставить скобки

$$\begin{gathered} (abc)d \hfill \\ (ab)(cd) \hfill \\ a(bcd) \hfill \\ \end{gathered} \qquad \qquad (2)$$

Разобьём тройку на два сомножителя; воспользуемся $(1)$ и перекомпонуем множители как указано ниже

$$\begin{gathered} {\color{red}(abc)d} = \left( {(ab)c} \right)d = (ab)cd = \hfill \\ {\color{red}(ab)(cd)} = ab(cd) = a\left( {b(cd)} \right) = \hfill \\ {\color{red}a(bcd)} \hfill \\ \end{gathered} $$

Тем самым доказана ассоциативность четвёрок

$$(abc)d = (ab)(cd) = a(bcd) =: abcd \qquad (1')$$

Дальше - аналогично

$$\begin{gathered} (abcd)e \hfill \\ (abc)(de) \hfill \\ (ab)(cde) \hfill \\ a(bcde) \hfill \\ \end{gathered} \qquad \qquad (2')$$

$$\begin{gathered} {\color{red}(abcd)e} = \left( {(abc)d} \right)e = (abc)de = \hfill \\ {\color{red}(abc)(de)} = \left( {(ab)c} \right)(de) = (ab)c(de) = (ab)\left( {c(de)} \right) = \hfill \\ {\color{red}(ab)(cde)} = ab(cde) = a\left( {b(cde)} \right) = \hfill \\ {\color{red}a(bcde)} \hfill \\ \end{gathered} $$

$$(abcd)e = (abc)(de) = (ab)(cde) = a(bcde) =: abcde \qquad \qquad (1'')$$

И так далее и так далее...

Собственно, вопрос. Как бы немногословно обосновать серию $(2)$?

[arseniiv]

Надо расставить там все скобки до конца, тогда мы просто переходим ассоциативностью от одной расстановки к нескольким другим, и такие переходы дают связный граф, а какой именно, надо глядеть у чисел Каталана, я уже забыл, не циклический ли он там вообще.

-- Пн авг 26, 2019 00:24:10 --

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

Надо расставить там все скобки до конца

Не очень понял, почему это избегается.

[Утундрий]

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

Не очень понял, почему это избегается

Наверное потому, что число вариантов растёт как факториал.

[arseniiv]

Ну можно какие-то сокращения выдумать, так-то вроде задача удобнее, если все скобки расставлены(?)

[mihaild]

А зачем расписывать варианты? Докажем, что любой способ расставить скобки равносилен некоторому, при котором последним делается умножение на последний элемент. Доказывается элементарно: пусть есть какой-то способ, в котором результат получается другим. Возьмем из всех таких способов тот, где последнее умножение как можно правее. Тогда наша схема имеет вид $a \cdot (b \cdot c)$, где $b$ и $c$ - компоненты последнего произведения справа. Тогда наш способ дает тот же результат, что и $(a \cdot b) \cdot c$, у которого последнее умножение правее.
Ну и значит можно считать, что последнее умножение идет на последний элемент. Далее по индукции по числу сомножителей.

[Утундрий]

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

[Connector]

Утундрий в сообщении #1412022 писал(а):

А что если так?

Ассоциативность «умножения» для произвольного числа $n$ сомножителей доказывается едва ли не в любом учебнике по теории групп; как правило доказательство проводят индукцией по $n$, сразу разбивая сомножители на две группы.

[Утундрий]

Connector
Ваше заявление крайне малоинформативно.

[Connector]

Утундрий

Извиняюсь.
Вот, например, как это делает Калужнин во «Введении в общую алгебру» (с. 161), доказывая, что любое произведение $n$ множителей можно привести к стандартному виду $((...((g_1g_2)g_3)...)g_n)$ (нечто предельно близкое к тому, что требуется доказать в стартовом сообщении, если я правильно его понял).
Для $n=3$ утверждение совпадает с аксиомой ассоциативности;
Пусть доказано для $n$; группу (последовательность) из $n+1$ элементов разобьем на две (по последнему применению операции); каждая из этих двух смежных имеют длину не большую чем $n$, и по предположению индукции в рамках каждой из них порядок можно изменить произвольно. Во второй группе сомножителей изменим порядок, приведя её к виду $((...)g_{n+1})$, где порядок применения операции в пределах $(...)$ несуществен; сгруппируем (по ассоциативности) первую группу и $(...)$ и ещё раз используем индуктивное предположение.

(Предоставим слово Л. А. Калужнину)

Похожее доказательство есть у П. С. Александрова во «Введении в теорию групп».

[upgrade]

Утундрий в сообщении #1412010 писал(а):

Как бы немногословно обосновать серию $(2)$?

Так?:
$cd=e$
$abcd=abe$
...

[Утундрий]

Ну вот он просто говорит

Л.А. Калужнин писал(а):

Во всяком случае, произведение является произведение каких-то двух произведений...

И далее, что всевозможные скобки внутри обрамляющей с уже обработанной длиной - "слипаются". То есть, Калужнину это очевидно. Мне это тоже уже очевидно (а до того как стало очевидно, я не пожалел бумаги и проверил в лоб до шести сомножителей). Что же, на том и порешим.

Ну а после установления $(2)$ - голая техника слияния-разделения.

P.S. Зачем тут "стандартная форма" я так и не понял. Можно просто пройтись по всем парным разбиениям, как показано выше.

upgrade
Не уловил.

[upgrade]

Пусть ассоциативность $abc$ доказана (1)
доказываем $abcd$
пусть можно представить $cd=e$ (тут, видимо в тяжелых случаях надо доказывать, что такое произведение существует)
$abe$ доказано выше (1)
теперь пусть $bc=e$
$aed$ доказано выше (1)
теперь пусть $ab=e$
$ecd$ доказано выше (1)
ну и так далее

[Утундрий]

upgrade
Теперь понятно, но это не доказательство.

[ewert]

mihaild в сообщении #1412020 писал(а):

Докажем, что любой способ расставить скобки равносилен некоторому, при котором последним делается умножение на последний элемент.

Это вполне разумная идея (наиболее разумная, на мой вкус). Только, во-первых, в дальнейшее я не особо врубился. А во-вторых -- оформил бы всё иначе.

Прежде всего: расставить скобки в произведении -- это то же самое, что приписать каждому значку умножения определённый уровень вложенности. Чем меньше уровень, тем позднее производится умножение. Операции же с одним и тем же уровнем могут выполняться в любом порядке, т.к. выполняются они независимо друг от дружки. Например, произведению 4-х чисел в естественном порядке, т.е. слева направо -- $(((a\cdot b)\cdot c)\cdot d)$ -- соответствует последовательность уровней $3,2,1$. А расстановке скобок $((a\cdot b)\cdot(c\cdot d))$ -- последовательность уровней $2,1,2$.

При этом распределение уровней подчиняется некоторым естественным требованиям.
1 (необязательно). Встречаются все уровни от первого до последнего. Если это не так, то просто в записи присутствуют избыточные скобки, которые можно безнаказанно удалить. Ничего страшного, просто слов больше понадобится.
2. Между любыми двумя умножениями одного и того же уровня должно присутствовать хоть одно умножение уровня более низкого (т.е. выполняемое заведомо позже).
3. Как следствие: значок умножения первого уровня может быть только один.

Теперь доказательство выстраивается в некоторую естественную логическую цепочку (от конца к началу).

1. Достаточно доказать, что любая расстановка скобок/уровней равносильна перемножению слева направо, т.е. когда все уровни в этом направлении строго убывают.
2. Для этого достаточно доказать (индукция по количеству сомножителей), что любая расстановка равносильна такой, при которой на первом уровне находится самое правое из умножений.
3. Для этого, в свою очередь, достаточно доказать: если в некоторой расстановке умножение первого уровня -- не самое правое, то его можно передвинуть вправо. Т.е. можно переставить скобки так, что умножение первого уровня окажется правее.

А вот последнее действительно вполне очевидно. Если умножение первого уровня не в самом конце, то всё произведение имеет вид $(A\cdot(B\cdot C))$, где первый явно выписанный знак умножения относится к первому уровню, второй -- ко второму; все умножения, содержащиеся в $A$ (если они есть), относятся к уровню не ниже второго, содержащиеся в $B$ или в $C$ -- к уровню не ниже третьего.

Теперь по базовому определению ассоциативности такое произведение равно $((A\cdot B)\cdot C)$. Первый значок стал умножением второго уровня, второй -- первого, ч.т.д.
(уровни умножений из $A$ при этом, естественно, на единицу повысились, из $C$ -- понизились,но это уже не важно; это так, для пущей внятности)

---------------------------------------

Конечно, тоже занудство. Но, во-первых, всё-таки без никакого перебора. А во-вторых, совсем без занудства не обойтись: надо ведь чётко сформулировать, что в точности понимается под расстановкой скобок.

[Утундрий]

ewert в сообщении #1412166 писал(а):

надо ведь чётко сформулировать, что в точности понимается под расстановкой скобок

Пусть это будет просто порядок выполнения умножений.