2014 dxdy logo

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

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


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


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

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

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

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

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



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


07/08/06

3474
Спасибо Вам на добром слове :wink:

Тему, конечно, можно переместить или вообще удалить, чтоб не позорить честь - я разобрался.

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


23/07/05
17973
Москва
AlexDem писал(а):
По-моему, Ваш пример противоречив (с той позиции, с которой я подхожу). Запишу соответствующие ему перестановки: ...


Вы заблуждаетесь. Перестановки (подстановки) - это отображения (вообще-то, даже взаимно однозначные, чего в данном примере не наблюдается), их композиция ассоциативна. А в примере AD элементы $0$ и $1$ нельзя интерпретировать как подстановки.

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


21/12/05
5903
Новосибирск
Если неассоциативных операций не бывает, то у меня нет ни одной работы по математике.
А как вам понравится такая задачка, почерпнута из реальной статьи, на которую мне шеф ещё в студенчестве дал написать рецензию.

Определение. Группоид G назовём антиассоциативным, если равенство $x(yz)=(xy)z$ не выполняется ни для каких значений переменных.
Автор интересовался возможными порядками конечных антиассоциативных группоидов и, наконец, соорудил пример порядка где-то около 20.
Мой ответ был таков: для любого n>1. Доказательство - одна строчка. :D

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


07/08/06

3474
Нет, мне всё же кажется, что я нашёл верный ответ на свой вопрос. Возможно, определение сейчас поменялось, но у меня перед глазами кгига Сушкевича "Теория обобщенных групп", где на с.9 вводятся подстановки. У него рассматриваются случаи, когда во втором ряду элементы дублируются (а значит обратного отображения нет) - они называются конечными обобщёнными подстановками. Такие подстановки соответствуют полугруппам.

Если бы операцию нельзя было рассматривать как отображение, это означало бы, что существует такое преобразование множества $Z$ в себя, которое отсутствует в симметрической полугруппе $F$. А там по определению есть они все. Однако, никто не обещал, что суперпозиция на $F$ даст подполугруппу, изоморфную $Z$ относительно рассматриваемой операции. Но возможны и другие операции над функциями из $F$, отличные от суперпозиции (в том числе и неассоциативные) - и с такой операцией изоморфизм можно установить.

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


18/12/07
8774
Новосибирск
bot писал(а):
Определение. Группоид G назовём антиассоциативным, если равенство $x(yz)=(xy)z$ не выполняется ни для каких значений переменных.
Автор интересовался возможными порядками конечных антиассоциативных группоидов и, наконец, соорудил пример порядка где-то около 20.
Мой ответ был таков: для любого n>1. Доказательство - одна строчка. :D


Хе-хе. В $\mathbb{Z}_n$ определяем $x \ast y = x + 1$. Тогда $x \ast (y \ast z) = x + 1 \neq x + 2 = (x \ast y) \ast z$. И правда в одну строчку!

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


07/08/06

3474
Хм, а я начал было граф рисовать. По-моему, если там две операции одинаковый путь имеют, то ассоциативность нарушится - так было в примере AD и у Профессор Снэйп - та же история, все пути совпадают.

 Профиль  
                  
 
 
Сообщение07.02.2008, 18:26 
Экс-модератор


17/06/06
5004
AlexDem писал(а):
Ваш пример противоречив (с той позиции, с которой я подхожу).
Видимо, я плохо понимаю Вашу позицию, потому что противоречий быть не может, потому что в группоиде никаких аксиом на операции не налагается. :? Или в смысле что он - контрпример?

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

Профессор Снэйп писал(а):
Какого х... вся эта х.... делает в разделе "помогите решить/разобраться"?! В дискуссионные её, там ферматикам раздолье.
Если бы автор был абсолютно уверен, что доказал противоречивость математики - было бы это все там. А тут адекватный человек обнаружил, что в голове что-то не сходится, предложил остальным его разглючить.

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


07/08/06

3474
Дело в том, что в данном случае я ошибочно предположил, что раз операция представима отображением, то такой группоид обязательно должен быть изоморфен подполугруппе $<F,*>$, но упустил из виду то обстоятельство, что на множестве $F$ может быть введена не только операция суперпозиции, но и какая-нибудь другая, в том числе - неассоциативная. По крайней мере, мне так сейчас видится этот вопрос.

 Профиль  
                  
 
 
Сообщение07.02.2008, 18:41 
Экс-модератор


17/06/06
5004
Да, наверное, это оно. Только вот это не отменяет вопрос про "синтаксис" и "семантику". Вот ваш пример с операцией отрицания, которая неассоциативна, но неким естественным образом соответствует операции сложения. Может быть, формализовать этот естественное соответствие - и группоидам придёт конец (с точностью до этого соответствия)?

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


07/08/06

3474
Нет, теперь уже не выйдет :). Тем более, что Ваш пример как раз доказывает, что синтаксис тут ни при чём.

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


17/06/06
5004
Ну типа там утверждение, что "всякую бинарную операцию можно выразить через какую-нибудь ассоциативную бинарную операцию или "обратную" к ней"? Или так: "для каждого вычитания найдётся своё сложение"? По-моему, занятное занятие.

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


18/12/07
8774
Новосибирск
Тогда вот вопрос, близкий к теме.

Сколько всего существует различных ассоциативных бинарных операций на конечном множестве, состоящем из $n$ элементов?

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

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

http://www.research.att.com/~njas/sequences/A023814

Для $n = 7$ имеем $7743056064$ ассоциативных операций и $7^{7^2} = 256923577521058878088611477224235621321607$ всех операций. Неассоциативных операций получается во много-много раз больше, чем ассоциативных. Значит, далеко не каждую неассоциативную операцию можно получить из ассоциативной :)

 Профиль  
                  
 
 
Сообщение07.02.2008, 19:49 
Экс-модератор


17/06/06
5004
Профессор Снэйп писал(а):
точный ответ неизвестен даже для $n=8$.
Жесть ... :shock:
Профессор Снэйп писал(а):
Неассоциативных операций получается во много-много раз больше, чем ассоциативных.
И асимптотика, небось, не в нашу пользу ... Да, значит, надо посвободнее соответствие сочинять. Чтобы одна ассоциативная операция обслуживала очень много неассоциативных. Ну да ладно, это уже для умных.

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


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


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

Что Вас интересует? Можно ли любую бинарную операцию на произвольном множестве определить через некоторую ассоциативную операцию (или операции)? Прежде чем отвечать на этот вопрос, нужно зафиксировать формальный смысл того, что значит "одна операция определяется через другую".

Вас интересует определение бинарных операций через суперпозиции конечного числа ассоциативных бинарных операций? Или может быть вопрос о том, можно ли задать произвольную бинарную операцию через уравнение, использующее символы ассоциативных бинарных операций, как неявную функцию (типа как мы задаём разность $a-b$ через решение уравнения $a = x+b$). Или что-то третье?

Первые два вопроса --- это уже интересные задачи, над ними можно подумать. Для начала предлагаю описать класс (не обязательно бинарных) операций на $\mathbb{Z}_n$, выразимых при помощи сложения и суперпозиций (ну и ещё проекций, про них часто забывают, однако без них с формальной точки зрения далеко не уедешь).

Пусть $X$ --- произвольное множество, $g(y_1, \ldots, y_n)$ --- некоторая $n$-местная операция на $X$ (то есть отображение из $X^n$ в $X$). Пусть также $h_1(x_1, \ldots, x_k), \ldots, h_n(x_1, \ldots, x_k)$ --- $n$ штук $k$-местных операций на $X$. Мы говорим, что $k$-местная операция $f$ задаётся при помощи суперпозиции из операций $g, h_1, \ldots, h_n$, если её значение на произвольном наборе $x_1, \ldots, x_k \in X$ определяется равенством:

$$
f(x_1, \ldots, x_k) = g(h_1(x_1, \ldots, x_k), \ldots, h_n(x_1, \ldots, x_k))
$$

Пусть $X = \mathbb{Z}_n$, $f(x,y) = x + y$ и $I_n^k(x_1, \ldots, x_n) = x_k$ для всех натуральных $n \geqslant 1$ и $k$ от $1$ до $n$. Какие операции на $X$ можно построить суперпозициями, исходя из этих функций? Ясно, что далеко не все. Например, умножение этим способом не задашь. А через умножение и проекции, наоборот, нельзя выразить сложение. Можно также довольно легко придумать операцию, которую нельзя выразить через сложение, умножение и проекции? Ну и т. д., в том же духе...

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


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

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

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

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



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

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


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

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