Теория множеств, теория групп.
- a89653841042a@yandex.ru
- Сообщений: 90
- Зарегистрирован: 10 сен 2013, 21:00
Теория множеств, теория групп.
Известно что проблема тождества слов в полугруппах алгоритмически неразрешима. Является ли совокупность слов в такой полугруппе множеством?
Последний раз редактировалось a89653841042a@yandex.ru 28 ноя 2019, 06:50, всего редактировалось 1 раз.
Причина: test
Причина: test
Теория множеств, теория групп.
Да.a89653841042a@yandex.ru писал(а):Source of the post Является ли совокупность слов в такой полугруппе множеством?
Последний раз редактировалось Sonic86 28 ноя 2019, 06:50, всего редактировалось 1 раз.
Причина: test
Причина: test
- a89653841042a@yandex.ru
- Сообщений: 90
- Зарегистрирован: 10 сен 2013, 21:00
Теория множеств, теория групп.
Sonic86 писал(а):Source of the postДа.a89653841042a@yandex.ru писал(а):Source of the post Является ли совокупность слов в такой полугруппе множеством?
Множество не может содержать одинаковых элементов. Но их невозможно исключить из совокупности ввиду алгоритмической неразрешимости. Как быть?
Последний раз редактировалось a89653841042a@yandex.ru 28 ноя 2019, 06:50, всего редактировалось 1 раз.
Причина: test
Причина: test
Теория множеств, теория групп.
Чего?a89653841042a@yandex.ru писал(а):Source of the post
Множество не может содержать одинаковых элементов. Но их невозможно исключить из совокупности ввиду алгоритмической неразрешимости. Как быть?
Вот Вам полугруппа . Элементами полугруппы являются классы эквивалентных символов (если нужны конкретные , я Вам из Мальцева пример выпишу). Классы по построению различны. Соответственно исключать некие неведомые одинаковые элементы из совокупности просто не нужно - их там с самого начала нет.
Или Вам нужен вывод из в рамках , что класс классов эквивалентных слов - множество?
Последний раз редактировалось Sonic86 28 ноя 2019, 06:50, всего редактировалось 1 раз.
Причина: test
Причина: test
Теория множеств, теория групп.
Sonic86 писал(а):Source of the postЧего?a89653841042a@yandex.ru писал(а):Source of the post
Множество не может содержать одинаковых элементов. Но их невозможно исключить из совокупности ввиду алгоритмической неразрешимости. Как быть?
Вот Вам полугруппа . Элементами полугруппы являются классы эквивалентных символов (если нужны конкретные , я Вам из Мальцева пример выпишу). Классы по построению различны. Соответственно исключать некие неведомые одинаковые элементы из совокупности просто не нужно - их там с самого начала нет.
Или Вам нужен вывод из в рамках , что класс классов эквивалентных слов - множество?
Лично мне тоже не очень ясно.
1. Как конструктивно построить эти классы эквивалентных символов? Если можно, продемонстрировать на примере, для которого доказана неразрешимая проблема равенства слов: порождающие ; определяющие соотношения -
2. И в рамках тоже не очень ясно: как постулировать класс эквивалентных слов, если определяющая функция неразрешима?
Последний раз редактировалось IgorS 28 ноя 2019, 06:50, всего редактировалось 1 раз.
Причина: test
Причина: test
Теория множеств, теория групп.
Так, я не очень правильно выразился - надо "классы эквивалентных слов" вместо "классы эквивалентных символов".IgorS писал(а):Source of the post Лично мне тоже не очень ясно.
1. Как конструктивно построить эти классы эквивалентных символов? Если можно, продемонстрировать на примере, для которого доказана неразрешимая проблема равенства слов: порождающие ; определяющие соотношения -
2. И в рамках тоже не очень ясно: как постулировать класс эквивалентных слов, если определяющая функция неразрешима?
Ну а что значит конструктивно строить классы? Некоторые классы в приведенном примере бесконечны (например, класс , содержащий эквивалентные элементы ), выписать любой класс простым перебором его элементов мы не можем. Значит класс надо как-то описывать. Как? Самый тривиальный способ такой: сказать, что класс - это класс, содержащий некоторое слово , далее, если и может быть получен одним элементарным преобразованием из соотношений полугруппы из , то тоже. Если, перебрав все элементарные преобразования, мы получаем одно и то же конечное множество слов, то даже конечен. Если класс бесконечен, такого не случиться. Но в любом случае таким образом задан, причем даже конструктивно. В частности, если некоторое , то подобным перебором можно обязательно проверить этот факт и явно найди цепочку преобразований, приводящую к . Если же , то проверить мы так это не можем.
(Вы меня проверяйте - правильно хоть или нет).
Не понял, какая определяющая функция? Я в не силен, могу вышеприведенное определение формально выписать на уровне наивной теории множеств. Надо? Никакая определяющая функция там не нужна, только соотношения эквивалентности.IgorS писал(а):Source of the post 2. И в рамках тоже не очень ясно: как постулировать класс эквивалентных слов, если определяющая функция неразрешима?
, где - множество соотношений полугруппы.
Пойдет? Или в синтаксисе такое выписать затруднительно?
Последний раз редактировалось Sonic86 28 ноя 2019, 06:50, всего редактировалось 1 раз.
Причина: test
Причина: test
Теория множеств, теория групп.
Sonic86 писал(а):Source of the post
Ну а что значит конструктивно строить классы? класс надо как-то описывать. Как? Самый тривиальный способ такой: сказать, что класс - это класс, содержащий некоторое слово , далее, если и может быть получен одним элементарным преобразованием из соотношений полугруппы из , то тоже. Если, перебрав все элементарные преобразования, мы получаем одно и то же конечное множество слов, то даже конечен. Если класс бесконечен, такого не случиться. Но в любом случае таким образом задан, причем даже конструктивно. В частности, если некоторое , то подобным перебором можно обязательно проверить этот факт и явно найди цепочку преобразований, приводящую к . Если же , то проверить мы так это не можем.
(Вы меня проверяйте - правильно хоть или нет).
Так в этом и проблема. Совокупность всех слов, эквивалентных данному слову принято обозначать и называть смежным классом. Легко показать что все определяющие соотношения выполняются и для смежных классов. И мы получаем полугруппу, построенную на смежных классах.
Т.к. основной способ задать смежный класс - это задать его представителя, то поэтому и возникла проблема равенства для ассоциативных исчислений: указать алгоритм, посредством которого для любых двух слов, можно было бы сказать, принадлежат ли они одному смежному классу. (для любителей точных формулировок: для заданного ассоциативного исчисления является ли рекурсивной совокупность всех пар слов, эквивалентных в данном исчислении)
Ответ оказался отрицательным. Значит, в приведенном выше примере есть, по крайней мере, хотя бы пара эффективно неотделимых смежных классов.
Последний раз редактировалось IgorS 28 ноя 2019, 06:50, всего редактировалось 1 раз.
Причина: test
Причина: test
Теория множеств, теория групп.
Ну это понятно все.
Как это относится к конструктивному построению классов, мне неясно.
И вопросов я не наблюдаю. И к исходным вопросам это не относится.
Как это относится к конструктивному построению классов, мне неясно.
И вопросов я не наблюдаю. И к исходным вопросам это не относится.
Последний раз редактировалось Sonic86 28 ноя 2019, 06:50, всего редактировалось 1 раз.
Причина: test
Причина: test
Теория множеств, теория групп.
Sonic86 писал(а):Source of the post
Ну это понятно все.
Как это относится к конструктивному построению классов, мне неясно.
И вопросов я не наблюдаю. И к исходным вопросам это не относится.
Это означает, что таким образом построить классы невозможно.
Мне кажется, что первоначальный вопрос как раз и остается: Для того чтобы некая совокупность была множеством, должна быть процедура отделения элементов совокупности друг от друга. В данном случае это не так.
Последний раз редактировалось IgorS 28 ноя 2019, 06:50, всего редактировалось 1 раз.
Причина: test
Причина: test
Теория множеств, теория групп.
:blink: А построить можно?IgorS писал(а):Source of the post Это означает, что таким образом построить классы невозможно.
Я Вам явный способ построения классов привел. Не надо путать возможность построения классов и возможность их различения.
А множество всех подмножеств это по-Вашему тоже не множество что-ли?IgorS писал(а):Source of the post Мне кажется, что первоначальный вопрос как раз и остается: Для того чтобы некая совокупность была множеством, должна быть процедура отделения элементов совокупности друг от друга. В данном случае это не так.
Последний раз редактировалось Sonic86 28 ноя 2019, 06:50, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 1 гость