Свободная полугруппа

[GlobalMiwka]

alcoholist в сообщении #1397596 писал(а):

GlobalMiwka в сообщении #1397537 писал(а):

Полугруппа $E$ называется свободной, если она имеет базис $S$, т. е. такое подмножество $S$, что любое отображение $S$ в произвольную полугруппу $E'$ может быть единственным образом расширено до гомоморфизма $E$ в $E'$."

Неправда. Найдите определение базиса. Базис есть у любой полугруппы.

Я это определение не выдумывал, оно дано в условии задачи.

alcoholist в сообщении #1397596 писал(а):

Вот правильное,
Полугруппа $E$ называется свободной, если она имеет такой базис $S$, что любое отображение $S$ в произвольную полугруппу $E'$ может быть единственным образом расширено до гомоморфизма $E$ в $E'$.
Чувствуете разницу?

Я вот сколько искал не находил такого определения, в какой книге это дано? Что-то похожее было для свободных алгебр.
У вас написано:

alcoholist в сообщении #1397596 писал(а):

Вот правильное,
такой базис $S$, что любое отображение $S$ в произвольную полугруппу $E'$ может быть единственным образом расширено до гомоморфизма $E$ в $E'$.

Вы сами написали "любое отображение" как же тогда, "Не любое отображение из такого базиса допускает расширение до гомоморфизма даже для свободной полугруппы!" ???

alcoholist в сообщении #1397596 писал(а):

Этот базис не минимален, а нам годятся только минимальные (вот тот, который в определении "существует", он заведомо минимальный, то есть никакой его элемент не выражается через остальные элементы)

А мы еще не знаем, что "никакой его элемент не выражается через остальные элементы", это еще не доказано из определения.

alcoholist в сообщении #1397596 писал(а):

GlobalMiwka в сообщении #1397537 писал(а):

Поэтому мы можем допустить, что $\exists s,s',s'' \in S$ такие, что $s=s's''$.

не можем! Не любое отображение из такого базиса допускает расширение до гомоморфизма даже для свободной полугруппы! Этот базис не минимален, а нам годятся только минимальные (вот тот, который в определении "существует", он заведомо минимальный, то есть никакой его элемент не выражается через остальные элементы)

Мы рассматриваем это случай, потому что ничего не знаем о множестве $S$, делается допущение и смотрится следствие из этого предположения имеет ли оно право на существование, т.е. не противоречит ли оно определению данному.

george66 в сообщении #1397610 писал(а):

Мы построили в явном виде НЕКОТОРУЮ свободную полугруппу с заданным базисом. Для неё всё хорошо, каждый элемент однозначно разлагается в произведение базисных.

Мы еще не знаем каждый ли элемент и однозначно ли разлагается на базисные элементы. Это еще не доказано. Об этом еще не известно из определения. Как я могу использовать этот факт, если я его еще не доказал? Или вы имеет ввиду, что приведенное доказательство и является этой самой некоторой полугруппой и надо рассмотреть совпадение с полугруппой слов (конечных строк), но нет кикакого упоминания о полугруппе слов?

[george66]

Давайте содержательно. Пусть дано некоторое множество (базис). Оно само ещё не является полугруппой, его элементы умножать нельзя (или мы не знаем как). Для примера возьмём множество из двух элементов $\{a,b\}$. Рассмотрим всевозможные слова (конечные строки), составленные из символов $a,b$:
$a,b,aa,ab,ba,bb,aaa,aab\ldots$
Это множество строк является полугруппой, если умножение понимать как приписывание одной строки к другой, например
$ab\cdot aab=abaab$
Это понятно?

[GlobalMiwka]

Давайте. Базис не является подполугруппой вы хотели сказать и никогда не будет. Элементы его принадлежат полугруппе, стало быть для них выполняется закон ассоциативности и любой паре элементов соответствует элемент полугруппы, т.е. элементы можно перемножать, ведь предолагаеться, что полугруппа замкнута относительно свой операции умножения.

Я понял касательно полугруппы слов, как это выглядит. В условии задачи дано лишь, то что мы имеем дело с полугруппой и все, т.е. лишь определение полугруппы, т.е. больше ничего не известно, все остальное надо узнать.

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

[george66]

Дальше, полугруппа слов (назовём её $E_1$) является свободной полугруппой с базисом $\{a,b\}$. Любую функцию (обычную) из множества $\{a,b\}$ в какую-нибудь полугруппу $E'$ можно единственным способом продолжить до гомоморфизма из $E_1$ в $E'$. Это понятно?
Теперь вопрос: является ли эта полугруппа ($E_1$) единственной свободной полугруппой с базисом $\{a,b\}$? Может ли быть другая полугруппа (назовём её $E_2$), тоже содержащая элементы $a,b$ и такая, что любую функцию из множества $\{a,b\}$ в какую-нибудь полугруппу $E'$ можно единственным способом продолжить до гомоморфизма из $E_2$ в $E'$? Понятен ли вопрос?
Сейчас я спать ложусь, у меня ночь.

[GlobalMiwka]

Дано:
1. свободная полугруппа $E_{1}$ порожденная базисом $S$ и бинарной операцией $\cdot$
2. свободная полугруппа $E_{2}$ порожденная тем же базисом $S$, но другой бинарной операцией $+$

Пусть существуют гомоморфизмы $\varphi\colon E_{1}\rightarrow E'$ и $\varphi'\colon E_{2}\rightarrow E'$ согласно условию.
Рассмотрим биекцию $f$ между множеством $f\colon S\subset E_{1}\rightarrow S\subset E_{2}$
Пусть теперь $\forall s\in S\subset E_{1}(\varphi(s)=\varphi'(f(s)))$
Теперь $\forall s,s'\in S\subset E_{1}(\varphi(ss')=\varphi(s)\varphi(s')=\varphi'(f(s))\varphi'(f(s'))=\varphi(f(s)f(s')))$, т.е.$\varphi(ss')=\varphi(f(s)f(s'))$

так как в свободной полугруппе каждый элемент однозначно разложим на элементы базиса, то существует биекция между элементами полугруппы $E_{1}$ и $E_{2}$ в силу биекции $f$.

А это означает, что $\forall e\in E_{1},e'\in E_{2}(\varphi=\varphi')$, т.е. функции гомоморфизма $\varphi\colon E_{1}\rightarrow E'$ и $\varphi'\colon E_{2}\rightarrow E'$ совпадают, что означает, что расширенная биекция $f\colon E_{1}\rightarrow E_{2}$ является изоморфизмом в силу бекции $f$ и гомоморфизма $\varphi(ss')=\varphi(s)\varphi(s')=\varphi(f(s)f(s'))=\varphi(f(s)f(s'))$.

Верно ?

[george66]

Идея с биекцией правильная, поздравляю, но доказываете не то. Вот у нас есть свободная полугруппа
$a,b,aa,ab,ba,bb,aaa,aab\ldots$
Можно построить другую свободную полугруппу с тем же базисом $\{a,b\}$, просто как-нибудь переименовав элементы, например
$a,b,00,01,10,11,000,001\ldots$
Соответственно определяется умножение в новой полугруппе
$a\cdot a=00$

$a\cdot b=01$

$b\cdot a=10$

$b\cdot b=11$

$a\cdot 00=000$

$b\cdot 00=100$
и так далее. Формально, это другая полугруппа, у неё другие элементы. Но ясно, что эти две полугруппы "устроены одинаково". Это значит, что есть взаимно однозначное соответствие между элементами первой и второй полугрупп, причём произведению элементов в первой полугруппе соответствует произведение во второй и наоборот. Теперь определите гомоморфизмы между этими полугруппами (туда и сюда). Функцию, определённую на базисе, можно продолжить до гомоморфизма!

[GlobalMiwka]

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

Сперва исправлю опечатки, должно быть $\forall s,s'\in S\subset E_{1}(\varphi(ss')=\varphi(s)\varphi(s')=\varphi'(f(s))\varphi'(f(s'))=\varphi'(f(s)f(s')))$, т.е.$\varphi(ss')=\varphi'(f(s)f(s'))$

В решении гомоморфизм функции $\varphi\colon E_{1}\rightarrow E'$ строится через биективное отображение $f\colon E_{1}\rightarrow E_{2}$, все рано получили гомоморфную функцию, потому что получается $\varphi(ss')=\varphi(s)\varphi(s')$

Далее то, во что отображаются элементы $s\rightarrow f(s)$ полугруппы $E_{2}$, тоже получаются гомоморфизмами, потому что для них выполняется гомоморфизм $\varphi'(f(s)f(s'))=\varphi'(f(s))\varphi'(f(s'))$, т.е. мы получили гомоморфизм $f\colon E_{1}\rightarrow E_{2}$, а учитывая то, что это отображение биективное и то, что ее обратная функция $f^{-1}$ имеет те же качества, то мы получили изоморфизм в обе стороны.

Теперь у меня есть претензия к такому доказательству.

Согласно условию в первой части эквивалентного утверждения, согласно которому длинноватое доказательство которого я приводил, мы имеем следующий набор утверждений:

1. полугруппа - множество замкнутое относительно ассоциативной операции умножения.

2. базис, который
2.1 можно отображать как угодно
2.2 отображать в произвольную полугруппу
2.3 отображение, которое может быть однозначно расширено до гомоморфизма всей полугруппы

3. в условии нет свойства базиса
3.1 быть независимыми
3.2 однозначно представлять все элементы полугруппы

так как условия 3. нет в исходном условии я не могу воспользоваться тем доказательством, которое вы хотели, 2-е которое я привел, так как 3.1 и 3.2 надо доказать, на которое опирается 2-е доказательство.

У меня вопрос: что неверно в том длинноватом доказательстве?

[george66]

Извините, разбираться в чужом длинном (и скорее всего, неверном) доказательстве вообще мало удовольствия. Посмотрите статью про свободные группы
[url]https://ru.wikipedia.org/wiki/Свободная_группа[/url]
там начинают с определения через однозначную разложимость, а затем (под заголовком "Универсальное свойство") дают определение через продолжимость гоморфизмов. Равносильность определений, правда, не доказывают.

[GlobalMiwka]

Ясно. Спасибо.

[george66]

Если есть серьёзное желание разобраться, почитайте мой учебник теории категорий
https://github.com/George66/Textbook
он рассчитан на программистов, программистам нравится. Там на первых страницах определение изоморфизма и что-то про полугруппы. Определение свободных полугрупп, правда, только в двенадцатой главе (про сопряжённость), но тема объективно трудная.

[GlobalMiwka]

Спасибо, постараюсь прочитать все.