2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 
Сообщение08.02.2008, 01:17 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
AD писал(а):
Ну я и говорю: точное фиксирование проблемы - это уже для умных. :) Чтобы они так прикинули, при каком способе выражения операций через другие всё может получиться, чтобы ушли от тривиальностей и дальше уже пытались что-то доказать.

Не могу сказать, что интересует что-то конкретное, но вопросы мне показались любопытными. То есть я над этим вряд ли буду серьезно думать. В слова "для умных" вкладывался именно этот смысл.


Не помню, кто сказал

Цитата:
Плох тот солдат, который не мечтает стать генералом

 Профиль  
                  
 
 
Сообщение08.02.2008, 12:39 
Экс-модератор


17/06/06
5004
:oops: Это да. Только постепенно, хорошо? :) Я просто пока немного не из этой области, мне бы первую в жизни курсовую сочинить сначала ... :roll:

Кстати, что-то в Куроше было по поводу вездесущности ассоциативности. Там под конец доказывалось, что любое множество с любой системой операций можно построить внутри некой полугруппы, в которой n-арные операции $f(x_1,\ldots,x_n)$ из нашей системы представляются в виде $\tilde{f}*x_1*\ldots*x_n$, где $\tilde f$ - некоторый элемент полугруппы, поставленный в соответствие операции $f$, а $*$ - умножение в этой полугруппе (это всё называлось "специальное точное представление").

 Профиль  
                  
 
 
Сообщение08.02.2008, 13:10 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Так. Если мы берём полугруппу $\langle S, \ast \rangle$ с $n$-элементным носителем $S$, то существует ровно $n$ унарных операций вида $f(x) = \tilde{f} \ast x$, а всего унарных операций на $S$ ровно $n^n$. Значит, далеко не любая операция на $S$ представима в указанном виде.

Но, возможно, здесь имелось в виду что-то вроде следующего. Пусть $\langle X, f_1, \ldots, f_n \rangle$ --- произвольная алгебраическая стстема с $n$ операциями (произвольной арности каждая). Тогда существует полугруппа $\langle S, \ast \rangle$, в ней подполугруппа (или даже просто подмножество) $H \subseteq S$ и элементы $\tilde{f}_1, \ldots, \tilde{f}_n \in S$, такие что

1) для произвольных $i \in [1,n]$ и $x_1, \ldots, x_{m_i} \in H$ имеет место $\tilde{f}_i \ast x_1 \ast \ldots \ast x_{m_i} \in H$;

2) Если для всех $i \in [1,n]$ и $x_1, \ldots, x_{m_i} \in H$ положить $g_i(x_1, \ldots, x_{m_i}) = \tilde{f}_i \ast x_1 \ast \ldots \ast x_{m_i}$, то алгебраические системы $\langle X, f_1, \ldots, f_n \rangle$ и $\langle H, g_1, \ldots, g_n \rangle$ изоморфны.

Если это правда, то, это, наверное, нетривиальный результат. Надо помыслить :)

 Профиль  
                  
 
 
Сообщение08.02.2008, 13:16 
Экс-модератор


17/06/06
5004
Да, примерно так вроде бы. Ясно, что "вкладывается", а не "равна". Даже вроде бы конечность числа операций не требуется.

 Профиль  
                  
 
 
Сообщение08.02.2008, 14:42 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
Профессор Снэйп писал(а):
Хе-хе. В $\mathbb{Z}_n$ определяем $x \ast y = x + 1$. Тогда $x \ast (y \ast z) = x + 1 \neq x + 2 = (x \ast y) \ast z$. И правда в одну строчку!

По сути оно и есть - правда пришёл тогда к этому окольным путём: класс антиассоциативных группоидов, дополненный единичным группоидом, является квазимногообразием, определяемым квазитождеством $x\cdot yz=xy\cdot z \rightarrow u=v$. Отсюда ясно, что это квазимногообразие замкнуто относительно взятия гомоморфных прообразов. Эти прообразы легко построить "раздвоением" одного элемента. Такисм образом достаточно построить антиассоциативный двухэлементный группоид. Построил (он же одномоментно строится), глянул на него, и вуаля:
Берём любое отображение $x \rightarrow x'$ с условием $\forall x (x''\ne x')$ и полагаем $xy=x'$. В итоге, множество значений искомой операции можно выбрать даже двухэлементным.

Цитата:
Хм... Насколько я понял, точный ответ неизвестен даже для n=8

Какие-то циферки там кривые - сразу в глаза бросается при n=2 одна, это же бред, что кроме группы нет других полугрупп? Конечно есть - с нулевым умножением, к примеру. Видимо это что-то другое. Что такое "labeled semigroup"?
В своё время сам на БЭСМ-6 считал их до 5-го порядка, четырёхэлементных - 126, а 5-элементных 1160, вроде так помнится - с точностью до изоморфизмов и антиизоморфизмов.
Потом, когда мне уж и не надо было, мне прислали американскый список до 6-го порядка (или до 7-го? - надо глянуть) - до 5-го порядка не было расхождений, если несчитать, что у них элементы - буковки, а у меня циферки, даже порядок перечисления совпал, стало быть лексикографикой одинаковой пользовались. :D
Если с 70-х в этом вопросе нет никаких продвижений, то он никому не нужен, да и гробовой он. Уж очень там мощности классов разбиения по изо(анти)изоморфизму вариабельны.

 Профиль  
                  
 
 
Сообщение08.02.2008, 17:57 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
bot писал(а):
Какие-то циферки там кривые - сразу в глаза бросается при n=2 одна, это же бред, что кроме группы нет других полугрупп? Конечно есть - с нулевым умножением, к примеру. Видимо это что-то другое. Что такое "labeled semigroup"?


"Там", Александр Дмитриевич, "циферки" абсолютно правильные. Просто нормальные люди начинают считать с нуля. Имеется 1 способ задать ассоциативную бинарную операцию на пустом множестве, 1 способ на одноэлементном, 8 способов на двухэлементном, 113 способов на трёхэлементном и т. д. :)

"Labeled semigroup" --- это "размеченная" полугруппа. Другими словами, каждый элемент выделяют уникальным унарным предикатом ("меткой") и смотрят уже количество таких структур с точностью до изоморфизма. Это то же самое, что считать различные операции, которые на фиксированном $n$-элементном множестве задают полугруппу. Причём если операции разные, то и считать их надо за разные, даже если полугруппы получаются изоморфными. То есть не количество $n$-элементных полугрупп с точностью до изоморфизма считаем, а просто количество полугрупп с фиксированным $n$-элементным носителем.

Добавлено спустя 3 минуты 8 секунд:

bot писал(а):
В своё время сам на БЭСМ-6 считал их до 5-го порядка, четырёхэлементных - 126, а 5-элементных 1160, вроде так помнится - с точностью до изоморфизмов и антиизоморфизмов.
Потом, когда мне уж и не надо было, мне прислали американскый список до 6-го порядка (или до 7-го? - надо глянуть) - до 5-го порядка не было расхождений, если несчитать, что у них элементы - буковки, а у меня циферки, даже порядок перечисления совпал, стало быть лексикографикой одинаковой пользовались. :D
Если с 70-х в этом вопросе нет никаких продвижений, то он никому не нужен, да и гробовой он. Уж очень там мощности классов разбиения по изо(анти)изоморфизму вариабельны.


А вот то, что Вы тогда считали: http://www.research.att.com/~njas/sequences/A001423

В настоящий момент известны значения вплоть до восьмого порядка :)

Добавлено спустя 18 минут 55 секунд:

AD писал(а):
Да, примерно так вроде бы. Ясно, что "вкладывается", а не "равна". Даже вроде бы конечность числа операций не требуется.


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

Пусть $X$ --- произвольное множество. Пусть $S$ --- это множество всех унарных операций на $X$. Тогда $S$ образует полугруппу относительно композиции.

Для $x \in X$ через $f_x$ обозначим унарную операцию на $X$, отображающую каждый элемент $X$ в $x$.

Соответствие $x \mapsto f_x$ вкладывает $X$ в $S$ и можно отождествлять $X$ с образом этого соотвествия.

Теперь для произвольного $s \in S$ имеем $s \circ f_x = f_{s(x)}$. И всё, похоже :)

У-у-у, как всё просто! И общий случай, по моему, нисколько не сложнее!! :) Да, не нужен нам Курош, мы и сами с усами!!! :D

 Профиль  
                  
 
 
Сообщение08.02.2008, 19:18 
Заблокирован
Аватара пользователя


07/08/06

3474
Профессор Снэйп писал(а):
И всё, похоже

Нет, похоже, не всё. В противном случае мы могли бы установить изоморфизм любого группоида с симметрической подполугруппой - с чего и начиналась тема. То есть $S$ заведомо не может быть множеством всех отображений носителя с операцией суперпозиции. Или я не совсем понял доказательство?..

 Профиль  
                  
 
 
Сообщение09.02.2008, 07:16 
Заблокирован
Аватара пользователя


07/08/06

3474
Разобрался вчера по дороге в чём было дело... Там в последнем равенстве порядок множителей обратный $s \circ f_x$, я внимания не обратил и поэтому при проверке на бинарных операциях на автомате перепутал правый с левым нулём, так что любое выражение равнялось первому множителю.

 Профиль  
                  
 
 
Сообщение09.02.2008, 10:05 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
AlexDem писал(а):
Разобрался вчера по дороге в чём было дело...


Ну раз разобрались, то и отвечать на вопрос, думаю, не требуется.

AlexDem писал(а):
Там в последнем равенстве порядок множителей обратный $s \circ f_x$, я внимания не обратил и поэтому при проверке на бинарных операциях на автомате перепутал правый с левым нулём, так что любое выражение равнялось первому множителю.


Насколько я знаю, общепринятого соглашения относительно порядка множителей при композиции вообще нет. Допустим, $f$ --- это функция из $A$ в $B$, а $g$ --- функция из $B$ в $C$. Их композиция --- это функция из $A$ в $C$. Иногда эту композицию записывают как $f \circ g$, а иногда --- как $g \circ f$, в разных книгах я встречал по разному. Первая запись удобна тем, что порядок функций в композиции совпадает с порядком стрелок и при работе с диаграммами не надо ничего "переворачивать". Вторая удобна тем, что не нужно ничего "переворачивать" при записи значений функций на аргументах: например, $(g \circ f)(a) = g(f(a))$ для $a \in A$.

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

 Профиль  
                  
 
 
Сообщение09.02.2008, 10:14 
Экс-модератор


17/06/06
5004
Профессор Снэйп писал(а):
У-у-у, как всё просто! И общий случай, по моему, нисколько не сложнее!! :) Да, не нужен нам Курош, мы и сами с усами!!! :D
Ну, в-общем, там, конечно, не сложное рассуждение, странички полторы, но все-таки немного похитрее. Вот, почитал - там всё вкладывается в симметрическую полугруппу на множестве конечных непустых строк, состоящих из элементов структуры и значков операций, и построенных по понятным правилам (как бы "выражения, состоящие из элементов и операций"; "формулы, в которые подставлены значения"). В-общем, да, идея достаточно понятная.

 Профиль  
                  
 
 
Сообщение11.02.2008, 17:18 
Заблокирован
Аватара пользователя


07/08/06

3474
Профессор Снэйп писал(а):
Насколько я знаю, общепринятого соглашения относительно порядка множителей при композиции вообще нет.

Ага. Было бы, наверно, удобно функцию записывать в виде $y = (x)f$ вместо $y = f(x)$, тогда бы прямой порядок был естественным :).

А вот по ходу - во что можно вложить подобным образом (через $\tilde f * x * y$) симметрическую полугруппу кроме другой полугруппы? В группу явно нельзя из-за сокращений, в некоторый неассоциативный группоид - можно: добавляем к исходной полугруппе новый элемент $x$ и на данном элементе модифицируем операцию (бывшую суперпозицией) таким образом, чтобы $xy = x +1$, тогда в качестве $\tilde f$ достаточно взять бывшую единицу. Так?

 Профиль  
                  
 
 
Сообщение11.02.2008, 22:37 
Заслуженный участник
Аватара пользователя


28/09/05
287
AlexDem писал(а):
Было бы, наверно, удобно функцию записывать в виде $y = (x)f$ вместо $y = f(x)$, тогда бы прямой порядок был естественным :).

Так иногда и поступают.

 Профиль  
                  
 
 
Сообщение12.02.2008, 07:25 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
AlexDem писал(а):
А вот по ходу - во что можно вложить подобным образом (через $\tilde f * x * y$) симметрическую полугруппу кроме другой полугруппы? В группу явно нельзя из-за сокращений, в некоторый неассоциативный группоид - можно: добавляем к исходной полугруппе новый элемент $x$ и на данном элементе модифицируем операцию (бывшую суперпозицией) таким образом, чтобы $xy = x +1$, тогда в качестве $\tilde f$ достаточно взять бывшую единицу. Так?


Ну да. Если я всё правильно понял, то вроде все рассуждения корректны.

Единственное что --- непонятно, откуда плюс и единица возьмутся, их надо дополнительно определять. А затем кроме $xy=x+1$ надо будет ещё доопределить, чему равно $yx$. Но все эти трудности, безусловно, преодолимы. То, что любую полугруппу (в нашем случае даже моноид) можно вложить в качестве подмодели в неассоциативный группоид (при необходимости даже с сохранением единицы) не подлежит сомнению.

К чему Вы хотите прийти?

 Профиль  
                  
 
 
Сообщение12.02.2008, 14:07 
Заблокирован
Аватара пользователя


07/08/06

3474
Профессор Снэйп писал(а):
Единственное что

Согласен с Вами. В принципе, здесь эта "+1" определяет просто некоторый "следующий за $x$ элемент" - можно выбрать любой из исходной полугруппы. Значения $yx$ тоже можно выбрать произвольно.

Профессор Снэйп писал(а):
К чему Вы хотите прийти?

Это по поводу вездесущности ассоциативности, о которой говорил AD. Получается, что точно также можно говорить и о вездесущности неассоциативности :).

 Профиль  
                  
 
 Re: Неассоциативность операции
Сообщение29.04.2014, 11:05 
Заблокирован
Аватара пользователя


07/08/06

3474
AD в сообщении #100356 писал(а):
Кстати, что-то в Куроше было по поводу вездесущности ассоциативности. Там под конец доказывалось, что любое множество с любой системой операций можно построить внутри некой полугруппы, в которой n-арные операции $f(x_1,\ldots,x_n)$ из нашей системы представляются в виде $\tilde{f}*x_1*\ldots*x_n$, где $\tilde f$ - некоторый элемент полугруппы, поставленный в соответствие операции $f$, а $*$ - умножение в этой полугруппе (это всё называлось "специальное точное представление").


Объясните, пожалуйста. Пытаюсь указанным выше образом представить умножение $a \cdot b \cdot c$ некоторого группоида с единицей. Пишу: $$a \cdot b = \tilde f * a * b,$$ но в то же время: $$a \cdot b \cdot e = \tilde f * (\tilde f * a * b) * e = \tilde f^2  * a * b.$$
Откуда $\tilde f^2 = \tilde f$. Что я делаю не так? В Куроше примеров нет, а в приводимом доказательстве есть пара неясных моментов, которые мешают разобраться.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 45 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group