Моноид - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:38:03Z

rollbackEdits.php mass rollback

23.128.248.38 в 03:46, 1 сентября 2022

2022-09-01T03:46:49Z

188.162.65.35: /* Примеры */ добавлено, что натуральные числа с нейтральным нулём -- не моноид

2015-09-28T16:33:21Z

‎Примеры: добавлено, что натуральные числа с нейтральным нулём -- не моноид

Lis: Про натуральные числа с умножением написана неправда: они _являются_ моноидом

2015-09-28T13:09:12Z

Про натуральные числа с умножением написана неправда: они _являются_ моноидом

Shersh: /* Источники информации */ добавлена ссылка на интересную статью про моноиды

2015-04-08T12:50:14Z

‎Источники информации: добавлена ссылка на интересную статью про моноиды

Shersh: /* Моноид с порождающими соотношениями */

2014-09-01T13:38:08Z

‎Моноид с порождающими соотношениями

Shersh: /* Ссылки */

2014-09-01T13:34:48Z

‎Ссылки

Shersh в 10:43, 18 ноября 2013

2013-11-18T10:43:10Z

Shersh в 10:33, 18 ноября 2013

2013-11-18T10:33:15Z

Shersh в 22:54, 17 ноября 2013

2013-11-17T22:54:16Z

← Предыдущая		Версия 16:38, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|definition=		\|definition=

← Предыдущая		Версия 03:46, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|definition=		\|definition=

@@ Строка 13: / Строка 13: @@
 * множество натуральных чисел <tex> \mathbb{N} </tex> с операцией сложения является моноидом <tex>\langle \mathbb{N}, +, 0 \rangle</tex>
 * множество положительных целых <tex> \mathbb{Z}_+ </tex> с операцией умножения является моноидом <tex>\langle\mathbb{Z}_+, \cdot, 1 \rangle</tex>
-* множество натуральных числел с операцией умножения является моноидом <tex>\langle \mathbb{N}, \cdot, 1 \rangle</tex> с нейтральным элементом <tex>1</tex> (наличие нуля не мешает этой структуре быть моноидом: <tex>1 \cdot 0 = 0</tex>, как того и требует аксиома нейтрального элемента).
+* множество натуральных числел с операцией умножения является моноидом <tex>\langle \mathbb{N}, \cdot, 1 \rangle</tex> с нейтральным элементом <tex>1</tex> (наличие нуля не мешает этой структуре быть моноидом: <tex>1 \cdot 0 = 0</tex>, как того и требует аксиома нейтрального элемента), но тройка <tex>\langle \mathbb{N}, \cdot, 0 \rangle</tex> моноидом уже не является.
 == Свойства ==

@@ Строка 13: / Строка 13: @@
 * множество натуральных чисел <tex> \mathbb{N} </tex> с операцией сложения является моноидом <tex>\langle \mathbb{N}, +, 0 \rangle</tex>
 * множество положительных целых <tex> \mathbb{Z}_+ </tex> с операцией умножения является моноидом <tex>\langle\mathbb{Z}_+, \cdot, 1 \rangle</tex>
-* множество натуральных числел '''не''' является моноидом по умножению с нейтральным элементом <tex>1</tex>, так как <tex>1 \cdot 0 = 0</tex>, а не <tex>1</tex>, как того требует аксиома нейтрального элемента.
+* множество натуральных числел с операцией умножения является моноидом <tex>\langle \mathbb{N}, \cdot, 1 \rangle</tex> с нейтральным элементом <tex>1</tex> (наличие нуля не мешает этой структуре быть моноидом: <tex>1 \cdot 0 = 0</tex>, как того и требует аксиома нейтрального элемента).
 == Свойства ==

@@ Строка 110: / Строка 110: @@
 * [http://ncatlab.org/nlab/show/free+monoid nLab {{---}} Free Monoid]
 * [http://www.proofwiki.org/wiki/Definition:Free_Monoid Proof Wiki {{---}} Free monoid]
 [[Категория:Теория групп]]

@@ Строка 79: / Строка 79: @@
 <tex> f(ba) = f(b) ~\texttt{++}~ f(a) </tex>
-Следовательно, так как <tex> ab = ba </tex> и отображение <tex> f </tex> является изоморфизмом, то <tex> f(ab) = f(a) ~\texttt{++}~ f(b) = f(b) ~\texttt{++}~ f(a) = f(ba) </tex>. Пусть <tex> |f(a)| = m, |f(b)| = n </tex>. Равенство этих последовательностей означает, что у последовательности <tex> f(a) ~\texttt{++}~ f(b) </tex> есть два [[Период и бордер, их связь | бордера]] длин <tex> m </tex> и <tex> n </tex> соответственно, значит, она периодическая и имеет период равный НОД<tex>(n, m)</tex>.
+Следовательно, так как <tex> ab = ba </tex> и отображение <tex> f </tex> является изоморфизмом, то <tex> f(ab) = f(a) ~\texttt{++}~ f(b) = f(b) ~\texttt{++}~ f(a) = f(ba) </tex>. Пусть <tex> |f(a)| = m, |f(b)| = n </tex>. Равенство этих последовательностей означает, что у последовательности <tex> f(a) ~\texttt{++}~ f(b) </tex> есть два [[Период и бордер, их связь | бордера]] длин <tex> m </tex> и <tex> n </tex> соответственно, значит, она периодическая и имеет период равный <tex>\gcd(n, m)</tex>.
 [[File:FreeMonoidConcatExample.png|300px]]
-Из этого следует, что последовательности <tex> f(a) </tex> и <tex> f(b) </tex> можно представить в виде конечного объединения некоторой подпоследовательности <tex> s </tex>, являющейся периодом и имеющей длину НОД<tex>(n, m)</tex>.
+Из этого следует, что последовательности <tex> f(a) </tex> и <tex> f(b) </tex> можно представить в виде конечного объединения некоторой подпоследовательности <tex> s </tex>, являющейся периодом и имеющей длину <tex>\gcd(n, m)</tex>.
 <tex> f(a) = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{p} </tex>
@@ Строка 89: / Строка 89: @@
 <tex> f(b) = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{q} , s \in M_S </tex>
-Пусть НОК<tex>(p, q) = l</tex>, тогда
+Пусть <tex>\mathrm{lcm}(p, q) = l</tex>, тогда
 <tex dpi> \overbrace{f(a) ~\texttt{++}~ f(a) ~\texttt{++}~ ... ~\texttt{++}~ f(a)}^{l / p} = \overbrace{s ~\texttt{++}~ s ~\texttt{++}~ ... ~\texttt{++}~ s}^{l} </tex>

@@ Строка 104: / Строка 104: @@
 * [[Изоморфизм групп]]
-== Ссылки ==
+== Источники информации ==
 * [[wikipedia:Monoid | Wikipedia {{---}} Monoid ]]
 * [[wikipedia:ru:Моноид | Википедия {{---}} Моноид ]]

@@ Строка 73: / Строка 73: @@
 '''Замечание''': конкатенация двух последовательностей <tex> a^i b^j </tex> и <tex> a^k b^t </tex> аналогична операции конкатенации строк, только после её применения строку надо привести к виду <tex> a^{i + k} b^{j + t} </tex>, поэтому результат операции равен не конкретной строке, а целому [[Отношение эквивалентности#Классы эквивалентности | классу эквивалентности]].
-Предположим, что данный моноид свободный. Это значит, что он изоморфен какому-то свободному моноиду над множество <tex> M_S </tex>, то есть существует биективное отображение <tex> f \colon G \to M_S </tex>. Оно сохраняет ассоциативность операций, поэтому
+Предположим, что данный моноид свободный. Это значит, что он изоморфен какому-то свободному моноиду над множеством <tex> M_S </tex>, то есть существует биективное отображение <tex> f \colon G \to M_S </tex>. Оно сохраняет ассоциативность операций, поэтому
 <tex> f(ab) = f(a) ~\texttt{++}~ f(b) </tex>

@@ Строка 69: / Строка 69: @@
 |statement= Моноид <tex dpi = 130> G = \Sigma^{*}_{/ab = ba} </tex> не является свободным
 |proof=
-Для начала покажем, что каждый элемент такого моноида можно представить в виде <tex> a^i b^j, i \geqslant 0, j \geqslant 0 </tex>. Докажем это конструктивно. Возьмём произвольную строку и будем в ней заменять все подстроки вида <tex> ba </tex> на подстроки <tex> ab </tex>. Если таких подстрок нет, то наша строка имеет вид <tex> a^i b^j </tex>, а если есть, то строка за конечное число шагов приведётся к указанному виду, потому что операцию замены <tex> ba </tex> на <tex> ab </tex> можно рассматривать, как уменьшения числа инверсий в последовательности, а их точно конечное число, так как все последовательности имеют конечную длину.
+Для начала покажем, что каждый элемент такого моноида можно представить в виде <tex> a^i b^j, i \geqslant 0, j \geqslant 0 </tex>. Докажем это конструктивно. Возьмём произвольную строку и будем в ней заменять все подстроки вида <tex> ba </tex> на подстроки <tex> ab </tex>. Если таких подстрок нет, то наша строка имеет вид <tex> a^i b^j </tex>, а если есть, то строка за конечное число шагов приведётся к указанному виду.
 '''Замечание''': конкатенация двух последовательностей <tex> a^i b^j </tex> и <tex> a^k b^t </tex> аналогична операции конкатенации строк, только после её применения строку надо привести к виду <tex> a^{i + k} b^{j + t} </tex>, поэтому результат операции равен не конкретной строке, а целому [[Отношение эквивалентности#Классы эквивалентности | классу эквивалентности]].

@@ Строка 62: / Строка 62: @@
 {{Определение
 |definition=
-'''Моноидом с порождающими отношениями''' (англ. ''equational presentation of monoid'') называется моноид, на котором введены дополнительные правила (то есть бинарные отношения на строках), отождествляющие некоторые элементы моноида.
+'''Моноидом с порождающими соотношениями''' (англ. ''equational presentation of monoid'') называется моноид, на котором введены дополнительные правила (то есть бинарные отношения на строках), отождествляющие некоторые элементы моноида.
 }}
 Примером такого моноида является множество <tex> G </tex> всевозможных строк над алфавитом <tex> \Sigma = \{a, b\} </tex>, <tex dpi = 130> G = \Sigma^{*}_{/ab = ba} </tex>, что обозначает равенство строк <tex> ab </tex> и <tex> ba </tex> в моноиде. И хотя такой моноид образован всевозможными последовательностями, он не является свободным. Покажем это.