О порядке на кольце свободного моноида

[Nartu]

Пусть $A$ есть конечный алфавит, $A^{\ast}$ его словарь и по совместительству свободный моноид с базисом $A$. Построим множество всех конечных сумм на его элементах с целыми коэффициентами $\mathbb{Z}[A^{\ast}]$.

Так вот, если А упорядочено, то этот порядок порождает порядок на словаре $A^{\ast}$ , это лексический порядок. А можно ли продолжить и как-то задать порядок на $\mathbb{Z}[A^{\ast}]$ ?

Я предлагаю вот такие свойства -

$\forall w, w_1, w_2, \tilde{w} \in A^{\ast} $

$1)\;w>0\,;$

$2)\;w+\tilde{w}>w\,;$

$3)\;w-\tilde{w}<w\,;$

$4)\;\forall k \in \mathbb{Z}\, \colon k>0\,,\,w_1>w_2 \Rightarrow kw_1>kw_2\,;$

$5)\;\forall k \in \mathbb{Z}\, \colon k<0\,,\,w_1>w_2 \Rightarrow kw_1<kw_2\,;$

$6)\;w_1>w_2 \Rightarrow w_1-w_2>0$

Не без белых пятен, на пример что делать с пустым словом $\lambda$ ?

У меня как-то полностью не получается, возникают непонятные ситуации, где нельзя точно сказать...
Мой лучший результат - это просто приводить суммы к полностью положительным слагаемым и смотреть - у кого самое лексически бОльшее слово.
То есть, как-бы, аналог меры Жордана? Когда множества сравниваются по максимальному элементу.
Вот типа так: $A=\left\lbrace{a,b \right\rbrace}\,, a>b \Rightarrow ab+b>ba+a\,,$ ибо $ab$ лексически больше всех справа.

Однако это работает если нет коэффициентов отличных от 1. Я не знаю, как быть с иными суммами.

Только что появилась идея, что можно порядок на словах брать за главного, а в остальных случаях сравнивать просто множители, они же целые числа. Но тут получается какая-то "сингулярность" :
если $a>b$ тогда они должны удовлетворять условию $a>kb\,,\;\forall k \in \mathbb{Z}\;-$ напоминает бесконечно-малые разных порядков, или инфинитезимали из нестандартного анализа(не уверен, ибо мало читал о нём).

Ну и так как это кольцо, наверное, конкатенация слов дистрибутивна над сложением. Она не меняет лексический порядок слов( $u|| w_1>u||w_2$ тут префиксы выпадают, а тут $w_1|| u>w_2|| u$ дополнительный суффикс не играет роли.)
Отсюда - конкатенация должна сохранять порядок и на элементах кольца, которое я рассматриваю: $w_1+w_2>w_3+w_4 \Rightarrow u||(w_1+w_2)>u||(w_3+w_4)$ так же и справа.
Если брать мой вариант типа Жордана, то последнее предложение сохраняет его, и всё хорошо. На счёт конкатенации $w_1\parallel kw_2\,,$ то там по дистрибутивности k можно выкинуть наперёд.

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

[dgwuqtj]

Самый простой способ - это записать два элемента $\mathbb Z[A^*]$ в виде $\sum_{w \in A^*} n_w w$ и сравнить наборы чисел $(n_w)_w$ лексикографически. Тогда все свойства выполняются, $\mathbb Z[A^*]$ даже будет упорядоченной абелевой группой.

[Nartu]

Я не совсем понял эту запись.. Вы хотите разложить в сумму всех элементов словаря? Тогда это будут бесконечные слова из чисел..
А что означает $(n_w)_w$ ?

А эта упор. аб. группа она будет как $\mathbb{Z}$ ? Странное чувство. Вроде как порядок тоже лексический, а значит он частичен.

Ааа.. подождите, это же как создать слова из коэффициентов пары элементов того кольца! Но порядок важен, а сумма предполагает независимость от порядка слагаемых. Есть вариант, что вы смотрите "канонический" вариант - когда слова в каждой сумме выстраиваются в естественном порядке согласно своему словарю. И тогда будет токо один кортеж коэффициентов.
Но снова, я могу выстроить в порядке убывания и получить второй вариант.

Пример нужен. Вот с двумя буквами: $2a$ и $8b$ . Кто больше, если $a>b$ ?

[dgwuqtj]

У вас $\mathbb Z[A^*]$ - это свободная абелева группа с базисом $A^*$, все её элементы можно представить как суммы слов с целыми коэффициентами, почти все коэффициенты нулевые. Так как $A^*$ бесконечно, это не очень осмысленно рассматривать как обычную сумму типа $a + \ldots + z$ (хотя можно, если выкинуть слагаемые с нулевыми коэффициентами, а оставшиеся упорядочить по возрастанию $w$). Но само отображение $n \colon A^* \to \mathbb Z$ корректно определено для любого элемента $\mathbb Z[A^*]$ и не зависит ни от каких порядков. Лексикографическое сравнение таких функций предполагает линейные порядки на $A^*$ и $\mathbb Z$, вот мы как раз и берём стандартные. Конечно, вместо обычного лексикографического порядка на $A^*$ можно взять обратный лексикографический или какой-нибудь ещё, их довольно много даже с хорошими свойствами.

Лексикографический порядок как раз обычно полный (то есть линейный). Отображение $n \colon A^* \to \mathbb Z$ меньше отображения $m$, если найдётся $w$ такое, что $n_w < m_w$ и для всех $w' < w$ выполнено $n_{w'} = m_{w'}$.

[Nartu]

dgwuqtj в сообщении #1617637 писал(а):

Но само отображение $n \colon A^* \to \mathbb{Z}$ корректно определено для любого элемента $\mathbb{Z}[A^*]$

Это вы коэффициент возвращаете? Или сумму коэффициентов слов из элемента кольца и выходит $\mathbb{Z}[A^*] \to \mathbb Z$ такой себе гомоморфизм.

dgwuqtj в сообщении #1617637 писал(а):

Отображение $n \colon A^* \to \mathbb Z$ меньше отображения $m$, если найдётся $w$ такое, что $n_w < m_w$ и для всех $w' < w$ выполнено $n_{w'} = m_{w'}$.

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

И появляется вопрос - а это вычислимо? Ну, мне пока кажется, что это будет непросто. Для предложеного мной примера просто на буквах алфавита.. я не могу развидеть какой итог..
А хотя, в принципе получается, $8b>2a$ из-за того, что $b$ раньше $a$ при возрастании, а числа сравниваются обычно.
всё верно?

dgwuqtj в сообщении #1617637 писал(а):

Лексикографический порядок как раз обычно полный (то есть линейный).

я когда-то попытался выстроить лексически в 1 ряд все двоичные слова... в общем, не вышло.. залез в трансфиниты, а там проблемы сразу. Может я понимаю линейный порядок слишком буквально?

[dgwuqtj]

Nartu в сообщении #1617646 писал(а):

Это вы коэффициент возвращаете?

Да, это коэффициент.

Nartu в сообщении #1617646 писал(а):

Наверное здесь индекс $w$ значит значение на этом элементе. - Тогда как-то не похоже на составление кортежей коэффициентов... видимо демонстрация линейности порядка.

Это определение (одного из кучи возможных) порядка на $\mathbb Z[A^*]$. А так да, сравниваются "последовательности" из чисел. Разве что они не последовательности, $A^*$ не изоморфно $\mathbb N$ как упорядоченное множество при $|A| > 1$.

Nartu в сообщении #1617646 писал(а):

Может я понимаю линейный порядок слишком буквально?

Линейный - это когда любые два элемента сравнимы. Для $A = \{a, b\}$ порядок на $A^*$ устроен примерно так: $\lambda, a, aa, ..., ab, ..., b, ba, ...$

Nartu в сообщении #1617646 писал(а):

И появляется вопрос - а это вычислимо?

Конечно, если алфавит сам является разрешимым множеством. Элементы $\mathbb Z[A^*]$ можно представлять как списки пар $(w, n_w)$ (отсортированных по первым компонентам) для тех слов, где коэффициент ненулевой.

[Nartu]

dgwuqtj в сообщении #1617780 писал(а):

Разве что они не последовательности, $A^*$ не изоморфно $\mathbb N$ как упорядоченное множество при $|A| > 1$.

Почему-то я вспомнил о p-адике. Это часом не та же структура?

Меня немного тревожил тот факт, что коммутативные суммы превращаются в кортежи, где есть $\mathbb{Z}$ множители. Просто для каждой суммы будет один такой. Так что можно даже из их множества сразу и начинать:

$(\mathbb{Z}\times A^{\ast})\times(\mathbb{Z}\times A^{\ast})\times \dots \times(\mathbb{Z}\times A^{\ast})\times \dots$

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

dgwuqtj в сообщении #1617637 писал(а):

Конечно, вместо обычного лексикографического порядка на $A^{\ast}$ можно взять обратный лексикографический или какой-нибудь ещё, их довольно много даже с хорошими свойствами.

Хотелось бы посмотреть в литературе о других вот этих "с хорошими свойствами". Можете что-то посоветовать? Может, при сравнении мне больше подойдёт другой, хотя и этот неплох.

[dgwuqtj]

Почитайте что-то про линейные порядки на абелевых группах (особенно на свободных). В частности, про мономиальные порядки. К p-адическим числам это не относится.