yourdomain.com

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

a89653841042a@yandex.ru писал(а):Source of the post Является ли совокупность слов в такой полугруппе множеством?

Да.

Sonic86 писал(а):Source of the post
a89653841042a@yandex.ru писал(а):Source of the post Является ли совокупность слов в такой полугруппе множеством?
Да.
я догадываюсь, что у Вас где-то на 5 этажей ниже сидит баг, но отвечать буду формально

Множество не может содержать одинаковых элементов. Но их невозможно исключить из совокупности ввиду алгоритмической неразрешимости. Как быть?

a89653841042a@yandex.ru писал(а):Source of the post
Множество не может содержать одинаковых элементов. Но их невозможно исключить из совокупности ввиду алгоритмической неразрешимости. Как быть?

Чего?
Вот Вам полугруппа $\Pi = \langle x_1,...,x_n|r_1=s_1,...,r_k=s_k\rangle$ . Элементами полугруппы являются классы эквивалентных символов (если нужны конкретные $$r_j,s_j$$

, я Вам из Мальцева пример выпишу). Классы по построению различны. Соответственно исключать некие неведомые одинаковые элементы из совокупности просто не нужно - их там с самого начала нет.
Или Вам нужен вывод из в рамках $$ZFC$$

, что класс классов эквивалентных слов - множество?

Sonic86 писал(а):Source of the post
a89653841042a@yandex.ru писал(а):Source of the post
Множество не может содержать одинаковых элементов. Но их невозможно исключить из совокупности ввиду алгоритмической неразрешимости. Как быть?
Чего?
Вот Вам полугруппа $\Pi = \langle x_1,...,x_n|r_1=s_1,...,r_k=s_k\rangle$ . Элементами полугруппы являются классы эквивалентных символов (если нужны конкретные , я Вам из Мальцева пример выпишу). Классы по построению различны. Соответственно исключать некие неведомые одинаковые элементы из совокупности просто не нужно - их там с самого начала нет.
Или Вам нужен вывод из в рамках , что класс классов эквивалентных слов - множество?

Лично мне тоже не очень ясно.
1. Как конструктивно построить эти классы эквивалентных символов? Если можно, продемонстрировать на примере, для которого доказана неразрешимая проблема равенства слов: порождающие $$a,b,c,d,e$$

; определяющие соотношения - $$ac=ca, ad=da, bc=cb, bd=db, eca=ce, edb=de, cca=ccae$$

2. И в рамках $$ZFC$$

тоже не очень ясно: как постулировать класс эквивалентных слов, если определяющая функция неразрешима?

IgorS писал(а):Source of the post Лично мне тоже не очень ясно.
1. Как конструктивно построить эти классы эквивалентных символов? Если можно, продемонстрировать на примере, для которого доказана неразрешимая проблема равенства слов: порождающие ; определяющие соотношения -
2. И в рамках тоже не очень ясно: как постулировать класс эквивалентных слов, если определяющая функция неразрешима?

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

Ну а что значит конструктивно строить классы? Некоторые классы в приведенном примере бесконечны (например, класс $$K$$

, содержащий эквивалентные элементы $\{cca,ccae,ccaee,ccaeee,...\}$ ), выписать любой класс простым перебором его элементов мы не можем. Значит класс надо как-то описывать. Как? Самый тривиальный способ такой: сказать, что класс $$K_w$$

- это класс, содержащий некоторое слово $$w$$

, далее, если $u\in K_w$ и $$v$$

может быть получен одним элементарным преобразованием из соотношений полугруппы из $$u$$

, то $v\in K_w$ тоже. Если, перебрав все элементарные преобразования, мы получаем одно и то же конечное множество слов, то $$K_w$$

даже конечен. Если класс бесконечен, такого не случиться. Но в любом случае $$K_w$$

таким образом задан, причем даже конструктивно. В частности, если некоторое $u\in K_w$ , то подобным перебором можно обязательно проверить этот факт и явно найди цепочку преобразований, приводящую $$w$$

к

. Если же $u\not\in K_w$ , то проверить мы так это не можем.
(Вы меня проверяйте - правильно хоть или нет).

IgorS писал(а):Source of the post 2. И в рамках тоже не очень ясно: как постулировать класс эквивалентных слов, если определяющая функция неразрешима?

Не понял, какая определяющая функция? Я в $$ZFC$$

не силен, могу вышеприведенное определение $$K_w$$

формально выписать на уровне наивной теории множеств. Надо? Никакая определяющая функция там не нужна, только соотношения эквивалентности.
$K_w=\{u:u\sim w\}$
$u\sim w\Leftrightarrow (\exists u_1,...,u_n) u=u_1, u_n=w, u_1\sim_E u_2,...,u_{n-1}\sim_E u_n$
$u\sim_E v \Leftrightarrow (\exists a,b,c,d,r,s\in\langle x_1,...,x_m\rangle )u=arb, v=csd, \{r=s\}\subseteq R$ , где $$R$$

- множество соотношений полугруппы.
Пойдет? Или в синтаксисе $$ZFC$$

такое выписать затруднительно?

Sonic86 писал(а):Source of the post
Ну а что значит конструктивно строить классы? класс надо как-то описывать. Как? Самый тривиальный способ такой: сказать, что класс - это класс, содержащий некоторое слово , далее, если $u\in K_w$ и может быть получен одним элементарным преобразованием из соотношений полугруппы из , то $v\in K_w$ тоже. Если, перебрав все элементарные преобразования, мы получаем одно и то же конечное множество слов, то даже конечен. Если класс бесконечен, такого не случиться. Но в любом случае таким образом задан, причем даже конструктивно. В частности, если некоторое $u\in K_w$ , то подобным перебором можно обязательно проверить этот факт и явно найди цепочку преобразований, приводящую к . Если же $u\not\in K_w$ , то проверить мы так это не можем.
(Вы меня проверяйте - правильно хоть или нет).

Так в этом и проблема. Совокупность всех слов, эквивалентных данному слову $$w$$

принято обозначать $$[w]$$

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

Ну это понятно все.
Как это относится к конструктивному построению классов, мне неясно.
И вопросов я не наблюдаю. И к исходным вопросам это не относится.

Sonic86 писал(а):Source of the post
Ну это понятно все.
Как это относится к конструктивному построению классов, мне неясно.
И вопросов я не наблюдаю. И к исходным вопросам это не относится.

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

IgorS писал(а):Source of the post Это означает, что таким образом построить классы невозможно.

:blink: А $\mathbb{N}$ построить можно?
Я Вам явный способ построения классов привел. Не надо путать возможность построения классов и возможность их различения.

IgorS писал(а):Source of the post Мне кажется, что первоначальный вопрос как раз и остается: Для того чтобы некая совокупность была множеством, должна быть процедура отделения элементов совокупности друг от друга. В данном случае это не так.

А множество $\mathcal{P}(N)$ всех подмножеств $\mathbb{N}$ это по-Вашему тоже не множество что-ли?

yourdomain.com

Теория множеств, теория групп.

Теория множеств, теория групп.

Теория множеств, теория групп.

Теория множеств, теория групп.

Теория множеств, теория групп.

Теория множеств, теория групп.

Теория множеств, теория групп.

Теория множеств, теория групп.

Теория множеств, теория групп.

Теория множеств, теория групп.

Теория множеств, теория групп.