Группы перестановок

[Профессор Снэйп]

Пусть $X$ --- произвольное множество (конечное либо бесконечное) и $\langle \mathrm{Perm}(X), \circ \rangle$ --- группа всех перестановок множества $X$. Написать формулу языка первого порядка групповой сигнатуры, выделяющую в этой группе множество транспозиций (то есть перестановок, переставляющих два элемента и оставляющих другие элементы на месте).

Для тех, кто слабо знаком с матлогикой и не знает, что такое формула первого порядка. Это формула, в которой можно использовать операцию композиции, кванторы $\forall$ и $\exists$ по элементам группы, равенство и логические операции $\mathop{\&}$, $\vee$, $\neg$, $\rightarrow$. В качестве примера приведу формулу, выделяющую единичный элемент группы:

$$ \Phi(x) = \forall y (x \circ y = y) $$

[neo66]

Так правильно? ($e$ - единичный элемент группы)

$\Phi(a) = \neg \exists b,c (a \circ a = e,b \circ b = e,c \circ c = e,a \neg=e,b \neg=e,c \neg=e,a = b\circ c )$

[Профессор Снэйп]

neo66 в сообщении #328393 писал(а):

Так правильно? ($e$ - единичный элемент группы)

$\Phi(a) = \neg \exists b,c (a \circ a = e,b \circ b = e,c \circ c = e,a \neg=e,b \neg=e,c \neg=e,a = b\circ c )$

Следуя синтаксису исчисления предикатов, формула записывается так:

$$ \Phi(a) = \neg \exists b \exists c ((a \circ a = e) \mathop{\&} (b \circ b = e) \mathop{\&} (c \circ c = e) \mathop{\&} \neg(a = e) \mathop{\&} \neg(b = e) \mathop{\&} \neg(c = e) \mathop{\&} (a = b \circ c)) $$

Если Вам не трудно, пишите, пожалуйста, коньюнкции вместо запятых.

Что до сути, то это неправильная формула, которая не выполняется на транспозициях. Рассмотрите, например $a = (0,1)$, $b = (0,1)(2,3)$ и $c = (2,3)$.

[neo66]

А так?

$\Phi_1(a) = \neg \exists b \exists c ((a \circ a = e) \mathop{\&} (a \circ b \circ a \circ {b^{-1} } = c \circ a \circ {c^{-1}}) ) $

$ \Phi_2(a) = \neg \exists d \exists p \exists q ( (a \circ d \circ a \circ {d^{-1} } = p \circ q )\mathop{\&}(p \circ p \circ p= e) \mathop{\&} (q \circ q \circ q= e)) $

$ \Phi(a) = \Phi_1(a) \mathop{\&} \Phi_2(a) $

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

Вероятно, это не самая остроумная идея, но уж какая есть.

[Профессор Снэйп]

neo66 в сообщении #328599 писал(а):

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

Это неверно. $\Phi_1(a)$ истинно для $a = (0,1)(2,3)(4,5)(6,7)\ldots$ (имеется в виду перестановка натурального ряда).

[neo66]

Профессор Снэйп в сообщении #328649 писал(а):

Это неверно. $\Phi_1(a)$ истинно для $a = (0,1)(2,3)(4,5)(6,7)\ldots$ (имеется в виду перестановка натурального ряда).

Нет, $\Phi_1(a)$ ложно для этого $a$. Такие $b$ и $c$, что $(a \circ b \circ a \circ {b^{-1} } = c \circ a \circ {c^{-1}})$ существуют.

[Профессор Снэйп]

neo66 в сообщении #328761 писал(а):

Нет, $\Phi_1(a)$ ложно для этого $a$. Такие $b$ и $c$, что $(a \circ b \circ a \circ {b^{-1} } = c \circ a \circ {c^{-1}})$ существуют.

В студию эти $b$ и $c$, в студию Пока не предъявите --- не поверю.

-- Пн июн 07, 2010 22:13:07 --

Надеюсь, Вы обратили внимание на многоточие. Перестановка $a$ меняет местами числа $2n$ и $2n+1$ для любого $n \in \mathbb{N}$.

[neo66]

О.К. Разобьем нашу перестановку на пары из двух транспозиций - $(0,1)(2,3)$, ну и так далее. Тогда для такой пары $b_1=(0,1,2),c_1=(0,1,3,2)$. Ну, а для остальных, аналогично. Для $i$-ой пары выписываем $b_i$ и $c_i$.

$b$ и $c$ - произведения всех таких $b_i$ и $c_i$.

[Профессор Снэйп]

Да, согласен с Вами. Есть такие $b$ и $c$

-- Пн июн 07, 2010 22:42:44 --

Вторую формулу надо подкорректировать, чтобы нельзя было взять $d=p=q=e$. А так, похоже, правильно.

Классическое решение такое:

$$ \Phi(x) = \neg (x = e) \mathop{\&} (x^2 = e) \mathop{\&} \forall y([x,y]^6 = e), $$

где $[x,y] = xyx^{-1}y^{-1}$ --- коммутатор элементов $x$ и $y$.

[Профессор Снэйп]

Существует ли в группе перестановок натурального ряда подгруппа конечного индекса (см. соседнюю тему)?