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

[alcoholist]

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

Определения

почему во множественном числе? Я же одно дал. И жду ваши попытки доказательства приведенного (прямого) утверждения. Попробуйте, что ли, от противного.

[GlobalMiwka]

Короче. Начну со второго определения.

пусть $\forall\varphi(\exists\varphi'(\forall s (\varphi(s)=\varphi(s'))\wedge\forall e\forall e'(\varphi(ee')=\varphi(e)\varphi(e')\wedge\varphi'(ee')=\varphi'(e)\varphi'(e'))))$, тогда так как любой элемент $e$ разложим однозначно на элементы множества S, то это значит, что все элементы $e$ разные,
т.е. можно сказать $\forall e (e=ee')\Rightarrow\varphi(ee')=\varphi(e)\varphi(e')=\varphi'(e)\varphi'(e')=\varphi'(ee')$,
т.е. $\forall e\forall e'\varphi(ee')=\varphi'(ee')$ - функции $\varphi$ и $\varphi'$ совпадают.

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

Тогда все доказано. Хотя я не уверен, что любое отображение в произвольную полугруппу может быть расширенно однозначно до гомоморфизма, это надо все таки рассматривать саму функцию отображения и во что элементы отображаются, так как и то и другое может накладывать ограничения.

[GlobalMiwka]

Опечатку допустил в первом выражении , должно быть $\forall s(\varphi(s)=\varphi'(s))$

[george66]

Гомоморфизм - это отображение множества элементов одной полугруппы во множество элементов другой, переводящее произведение элементов в произведение их образов. Пусть в первой полугруппе есть элементы $a,b$. Пусть мы знаем, что они переходят в элементы второй полугруппы $\varphi(a),\varphi(b)$. То есть, задана функция (пока обычная, не гомоморфизм) $\varphi$ из множества $\{a,b\}$ во множество элементов второй полугруппы. Если каждый элемент первой полугруппы однозначно разлагается в произведение $a,b$ (множество $\{a,b\}$ является базисом), то элементы первой полугруппы выглядят так
$a,b,aa,ab,ba,bb,aaa,aab\ldots$
Тогда мы можем единственным возможным способом доопределить функцию $\varphi$, чтобы она сохраняла произведения
$\varphi(aa)=\varphi(a)\varphi(a)$
$\varphi(ab)=\varphi(a)\varphi(b)$
$\varphi(ba)=\varphi(b)\varphi(a)$
$\varphi(bb)=\varphi(b)\varphi(b)$
$\varphi(aaa)=\varphi(a)\varphi(a)\varphi(a)$
$\varphi(aab)=\varphi(a)\varphi(a)\varphi(b)$
и так далее.

[GlobalMiwka]

george66 я не совсем понял к чему это пояснение.

[george66]

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

george66 я не совсем понял к чему это пояснение.

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

[GlobalMiwka]

Ясно. Выберем любое отображение $\varphi \colon S\rightarrow E'$ и для любой пары $\varphi(s),\varphi(s')$ выберем такое $\varphi(ss')$, чтобы $\varphi(ss')=\varphi(s)\varphi(s')$, далее в силу ассоциативности полугруппы следует, что для любой последовательности $s\in S$ сохранятся гомоморфизм $\varphi \colon E\rightarrow E'$, далее исходя из а) ассциативности и б) единственности разложения следуте единственность этой функции.

[GlobalMiwka]

Теперь вернёмся к первому утверждению. Пусть $\exists s',s'' (s',s'',s's''\in S)$, так как они не являются продолжением гомоморфизма, то можно выбрать отображение $\varphi(s's'')\neq(\varphi(s')\varphi(s'')=\varphi(s's''))$, так как сказано для любого отображения $S\rightarrow E$, так как для любой тройки я могу это сделать, то $\forall s,s',s'' (s\neq s's'')$, т.е. независимы.

Возникают 2 вопроса:

1. Как доказать, что все элементы представимы через $S$
2. Есть элемент $e\notin S$ не выразимый через элементы $S$

-- 02.06.2019, 12:41 --

еще я понял, что отображение $\varphi \colon S\rightarrow E'$, не может быть гомоморфизмом, потому что элементы множества $S$ не выражаются друг через друга, т.е. нет выражения $s=s's''$, поэтому нет $\varphi(s)=\varphi(s')\varphi(s'')$, поэтому можно взять любое отображение и расширить его до гомоморфизма.

-- 02.06.2019, 12:50 --

поясню выражение $\varphi(s's'')\neq(\varphi(s')\varphi(s'')=\varphi(s's''))$

1. $s=s's''\in S$
2. так как $s',s'',s's''\in E$, а на $E$ определено гомоморфизм, то должно быть $\varphi(s's'') = \varphi(s')\varphi(s'')$
3. но так как можно выбрать такое отображение $\varphi\colon S\rightarrow E'$ $\varphi(s's'') \neq \varphi(s')\varphi(s'')$
4. получается противоречие значит $s\neq s's''$
5. $s's''\notin S$

[george66]

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

[alcoholist]

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

Выберем любое отображение $\varphi \colon S\rightarrow E'$ и для любой пары $\varphi(s),\varphi(s')$ выберем такое $\varphi(ss')$, чтобы $\varphi(ss')=\varphi(s)\varphi(s')$

По-русски это звучит так. Пусть $\varphi \colon S\rightarrow E'$ -- произвольное отображение. Определим отображение $\varphi$ на элементах-произведениях

$$s_1s_2\in SS=\{ab\in E:a,b\in S\}\subset E$$

формулой $\varphi(s_1s_2)=\varphi(s_1)\varphi(s_2)$. Действуя последовательно, мы расширим $\varphi$ до гомоморфизма всей полугруппы.
Если мы доказываем прямое утверждение:

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

Если любое отображение $f\colon S\to E'$ в произвольную полугруппу однозначно продолжается до гомоморфизма $\bar{f}\colon E\to E'$, то представление любого элемента $h\in E$ в виде произведения элементов из $S$ однозначно.

то расширение построено корректно и надо доказать единственность разложения по базису.

[george66]

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

еще я понял, что отображение $\varphi \colon S\rightarrow E'$, не может быть гомоморфизмом, потому что элементы множества $S$ не выражаются друг через друга, т.е. нет выражения $s=s's''$, поэтому нет $\varphi(s)=\varphi(s')\varphi(s'')$, поэтому можно взять любое отображение и расширить его до гомоморфизма.

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

Теперь, что мы имеем. Мы построили в явном виде свободную полугруппу с заданным базисом. Это полугруппа слов (или конечных строк), составленных из элементов базиса. Если теперь доказать, что свободная полугруппа с данным базисом по существу единственная, всё будет сделано. Предположите, что есть две свободные полугруппы с одинаковым базисом (хоть $\{a,b\}$), постройте между ними какой-нибудь гомоморфизм.

[GlobalMiwka]

Под определением свободы вы имеет ввиду следующее определение:

Полугруппа свобода, если существует подмножество $S$ в $G$, такое что каждый элемент $G$ записывается единственным образом как произведение конечного числа элементов $S$ ???

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

Предположите, что есть две свободных полугруппы с одним и тем же базисом, найдите их гомоморфизмы друг в друга (используя определение свободы)

не понял как это 2-е полугруппы с одним и тем же базисом. Они же по определению свободы совпадают. Как их может быть две?

[GlobalMiwka]

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

превое определение:

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

из этого определения следует:
1) мы не знаем, что это за множество $S$ такое, т.е. какими свойствами элементы множества обладают, например, коммутативны ли они или что еще.
2) можно выбирать все отображения $S$ в $E'$, т.е. рассматривать любое из них.
3) отображение в произвольную полугруппу $E'$
4) любое отображение $S$ в произвольную полугруппу $E'$ может быть единственным образом расширено до гомоморфизма $E$ в $E'$

1. множество $S$ - о нем ничего не известно пока. Поэтому мы можем допустить, что $\exists s,s',s'' \in S$ такие, что $s=s's''$.
а) так как 2), т.е. можно выбирать все отображения $S$ в $E'$, т.е. рассматривать любое из них и
б) так как 3), т.е. отображение в произвольную полугруппу $E'$.
Выберем такое $\varphi\colon S\rightarrow E'$ и такую произвольную полугруппу $E'$, чтобы $s\rightarrow \varphi(s)$(потому что можно выбрать произвольное отображение в любую полугруппу), чтобы $\varphi(s),\varphi(s'),\varphi(s'') \in E'$ такие, что $\varphi(s)\neq\varphi(s')\varphi(s'')$.
Но так как по условию определения над всеми элементами $e\in E$ определен гомоморфизм, то из условия существования $s=s's''$ следует $\Rrightarrow \varphi(s)=\varphi(s')\varphi(s'')$, т.е. противоречие $\varphi(s)\neq\varphi(s')\varphi(s'')$ и $\varphi(s)=\varphi(s')\varphi(s'')$.
Это значит, что никакой элементы множества $S$ не может быть выражен через другие элементы множества $S$, т.е. $\forall s,s',s''\in S(s\neq s's'')$, т.е. элементы множества $S$ независимы.

Итак мы установили первое свойство элементов множества $S$, а именно, что они независимы.

2. Замечание. В силу того, что элементы множества $S$ независимы, т.е. нет никакой тройки $\forall s,s',s'' (s=s's'')$ то мы не можем поставить знак равенства между $\varphi(s')\varphi(s'')$ и $(\varphi(s's'')=\varphi(s))$, т.е. нет никакого гомоморфизма над $S$, если можно так выразиться, поэтому $\varphi\colon S\rightarrow E'$ может быть любым отображением $S\rightarrow E'$

3. Теперь $\forall s,s',s''(s\neq s's'')\Rightarrow s's''\in E\diagdown S$. Возникает вопрос, а что со всеми сочетаниями $s_{1}s_{2}...s_{n}$, может ли получится $\exists s\in S(s=s_{1}s_{2}...s_{n})$. Снова так как 2), 3) и 4) то $\forall s_{1},s_{2},s_{3}$ можно выбрать такое отображение $\varphi\colon S\rightarrow E'$ и такую произвольную полугруппу $E'$, чтобы $s\rightarrow \varphi(s)$(потому что можно выбрать произвольное отображение в любую полугруппу) было таким, что $\varphi(s)=\varphi((s_{1}s_{2})s_{3})\neq\varphi(s_{1}s_{2})\varphi(s_{3})\wedge \varphi(s_{1}(s_{2}s_{3}))\neq\varphi(s_{1})\varphi(s_{2}s_{3})$. Отсюда ясно, что это можно сделать и для любого $n$.

4. А что если $\exists e\in E\diagdown S(e\neq s_{1}s_{2}...s_{n})$, ведь мы не знаем, что это за полугруппа $E$ и какими именно свойствами обладает множество $S$. Снова согласно ходу решения 3. $\exists s,s'\in S(s=s'e)\Rightarrow \varphi(s)\neq \varphi(s')\varphi(e)$, т.е. $e\cup S$ независимы.

5. можно ли добавить $e$ $S$, может это не столь очевидно, так как $\varphi(s)\neq \varphi(s')\varphi(e)$, то не никакого гомоморфизма над $e\cup S$, то можно отобразить $e\rightarrow \varphi(e)$ во что угодно, т.е. ничем от элементов множества $S$ не отличается.

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

7. Замечание. В задаче постулируется наличие гомоморфизма, возможность отображать $E$ как угодно и в какую угодно полугруппу, что я и делал. Интересно то, что эти требования определения вынуждают полугруппу $E$ иметь определенные свойства, но сама полугруппа так сказать "не в курсе" того, что ее там куда-то отображают.

Если решение верно, то как надо было по-вашему решать?

[alcoholist]

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

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

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

-- Пн июн 03, 2019 23:47:08 --

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

-- Пн июн 03, 2019 23:51:12 --

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

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

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

[george66]

Мы построили в явном виде НЕКОТОРУЮ свободную полугруппу с заданным базисом. Для неё всё хорошо, каждый элемент однозначно разлагается в произведение базисных. Но вдруг есть другие свободные полугруппы с тем же базисом, устроенные как-то совсем иначе? Надо доказать, что любая свободная полугруппа с данным базисом по сути совпадает с полугруппой слов (конечных строк). Проще всего доказать, что вообще любые две свободные группы с данным базисом по сути совпадают (между их элементами есть взаимно однозначное соответствие, сохраняющее произведения). Определение свободы такое: полугруппа $E$ свободная с базисом $S$ если любую функцию из $S$ в $E'$ можно единственным образом продолжить до гомоморфизма из $E$ в $E'$. Предположим, что есть две полугруппы с таким свойством, обозначим их $E_1$ и $E_2$. У них общий базис $S$. Придумайте какой-нибудь гомоморфизм из $E_1$ в $E_2$ (одну из них используйте в качестве $E$, а другую в качестве $E'$)