WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«А. Е. ПЕНТУС Московский государственный университет им. М. В. Ломоносова e-mail: apentus М. Р. ПЕНТУС Московский государственный университет им. М. В. Ломоносова, ...»

Атомарная теория деления и пересечения

двусторонних идеалов полуколец

А. Е. ПЕНТУС

Московский государственный университет

им. М. В. Ломоносова

e-mail: apentus@mech.math.msu.su

М. Р. ПЕНТУС

Московский государственный университет

им. М. В. Ломоносова,

Российский государственный гуманитарный университет,

Московский педагогический государственный университет,

Математический институт им. В. А. Стеклова РАН

УДК 512+510.64

Ключевые слова: идеал полукольца, исчисление Ламбека .

Аннотация В статье рассматриваются двусторонние идеалы полуколец. Изучается теория двусторонних идеалов в сигнатуре, состоящей из предикатного символа и трёх функциональных символов, обозначающих пересечение, правое деление и левое деление идеалов. Доказывается, что множество атомарных формул этой сигнатуры, истинных на всех полукольцах при всех оценках, разрешимо .

Abstract A. E. Pentus, M. R. Pentus, The atomic theory of division and intersection of semiring ideals, Fundamentalnaya i prikladnaya matematika, vol. 21 (2016), no. 1, pp. 181—191 .

We consider two-sided ideals of semirings. More precisely, we study the theory of two-sided ideals in the signature consisting of the predicate symbol and three function symbols that denote the intersection, right division, and left division of ideals. We prove the decidability of the set of those atomic formulas in this signature that are valid for all semirings and all valuations .



Введение На множестве всех двусторонних идеалов произвольного полукольца S можно определить операцию правого деления (I/J = {c S | c · J I}), операцию левого деления (J\I = {c S | J · c I}) и операцию пересечения. Цель данной статьи — найти эффективный способ проверки тождественной истинности Работа выполнена при частичной поддержке РФФИ (проекты 14-01-00127а, 15-01-09218а, 16-01-00615а, НШ-1423.2014.1) .

Фундаментальная и прикладная математика, 2016, том 21, № 1, с. 181—191 .

c 2016 Национальный Открытый Университет «ИНТУИТ»

182 А. Е. Пентус, М. Р. Пентус соотношений, формулируемых в терминах пересечения, правого деления, левого деления и отношения. Та же задача для случая без пересечения была решена в [4] .

В разделе 1 даются определения, касающиеся полуколец и их двусторонних идеалов. В разделе 2 вводится исчисление LM(\, /, ) — исчисление Ламбека с двумя делениями и пересечением и добавленным правилом монотонности .

В разделе 3 приводится доказательство корректности исчисления LM(\, /, ) относительно интерпретации на множестве идеалов полукольца. В разделе 4 доказывается, что в исчислении LM(\, /, ) выводятся все тождественно истинные свойства двусторонних идеалов полуколец, записываемые в указанной сигнатуре как атомарные формулы. (Доказательство основано на том, что невыводимые в LM(\, /, ) свойства опровергаются в конкретной универсальной модели.) Так как множество выводимых секвенций исчисления LM(\, /, ) разрешимо, установлена разрешимость атомарной теории деления и пересечения двусторонних идеалов .

1. Полукольца Определение 1.1. В этой статье полукольцом называется алгебра S, +, ·, 0 с выделенным элементом 0 и бинарными операциями + и ·, удовлетворяющими следующим аксиомам (где a, b, c — произвольные элементы множества S):

1) a + b = b + a,

2) a + 0 = a, 3) (a + b) + c = a + (b + c), 4) (a · b) · c = a · (b · c),

5) a · (b + c) = a · b + a · c, 6) (b + c) · a = b · a + c · a,



7) a · 0 = 0, 8) 0 · a = 0 .

Пример 1.2 .

Через N обозначим множество всех натуральных чисел (ноль считаем натуральным числом). Множество N с обычными операциями сложения и умножения и нулём образует полукольцо .

Пример 1.3 .

Определим на множестве {0, 1, 2, 3, 4} две бинарные операции и следующим образом:

4 4 4 4 4 4, 4 0 4 4 4 4 .

Тогда {0, 1, 2, 3, 4},,, 0 — полукольцо .

Атомарная теория деления и пересечения двусторонних идеалов полуколец

–  –  –

3. Модели Определение 3.1. Оценкой на полукольце называется произвольная функция v, ставящая в соответствие примитивным типам p1, p2,... некоторые двусторонние идеалы этого полукольца. Естественное продолжение оценки v на множество всех типов будем тоже обозначать через v. Оно задаётся следующими соотношениями:

1) v(A B) = v(A) v(B), 186 А. Е. Пентус, М. Р. Пентус

–  –  –

6) p1 (p1 /p2 ) = p1, 7) (p1 /p3 ) (p2 /p3 ) = (p1 p2 )/p3 .

Теорема 3.9 .

Исчисление LM(\, /, ) корректно относительно моделей на полукольцах (т. е. каждая выводимая в исчислении LM(\, /, ) секвенция истинна на всех полукольцах при всех оценках ) .

Доказательство. Пусть даны полукольцо S, +, ·, 0 и оценка v .

Нетрудно доказать, что для любых двусторонних идеалов I, J, K выполняются следующие соотношения:

1) (I · J) · K = I · (J · K),

2) I · J K тогда и только тогда, когда I K/J,

3) I · J K тогда и только тогда, когда J I\K,

4) I · J I,

5) I · J J .

Из них выводятся соотношения

6) если I J, то I · K J · K и K · I K · J, 7) (I/J) · J I,

8) J · (J\I) I .

Используя приведённые соотношения, можно индукцией по длине вывода доказать, что если LM(\, /, ) A1... An B, то v(A1 ) ·... · v(An ) v(B) .

Основная цель данной статьи — доказать обратную теорему (см. следствие 4.2) .

–  –  –

Теперь можно доказать, что каждая невыводимая в исчислении LM(\, /, ) секвенция ложна на построенном полукольце при указанной оценке v. Пусть LM(\, /, ) A1... An B, где Ai Tp(\, /, ) (для всех i) и B Tp(\, /, ). Из соотношения (1) видно, что Ai v(Ai ) (для всех i) и A1... An v(B). Следовательно, / v(A1 ) ·... · v(An ) v(B), и ложность невыводимой секвенции A1... An B доказана .

Следствие 4.2. Исчисление LM(\, /, ) полно относительно моделей на полукольцах (т. е. для каждой секвенции из истинности на всех полукольцах при всех оценках следует выводимость в исчислении LM(\, /, )) .

Доказательство. Если некоторая секвенция истинна во всех моделях на полукольцах, то она истинна в модели, построенной в теореме 4.1, а поэтому выводима в исчислении LM(\, /, ) .

Следствие 4.3. Рассмотрим множество секвенций вида A B, где A Tp(\, /, ) и B Tp(\, /, ). Выделим среди них множество тех секвенций, которые истинны во всех моделях на полукольцах. Это множество разрешимо .





Доказательство. Согласно теореме 3.9 и следствию 4.2 множество секвенций вида A B, истинных во всех моделях на полукольцах, совпадает с множеством выводимых в исчислении LM(\, /, ) секвенций вида A B (здесь A Tp(\, /, ) и B Tp(\, /, )). Осталось проверить, что множество выводимых в LM(\, /, ) секвенций разрешимо .

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

Следствие 4.4. Рассмотрим множество равенств вида A = B, где A Tp(\, /, ) и B Tp(\, /, ). Выделим среди них множество тех равенств, которые истинны во всех моделях на полукольцах. Это множество разрешимо .

Доказательство. Пусть A Tp(\, /, ) и B Tp(\, /, ). Равенство A = B истинно во всех моделях на полукольцах тогда и только тогда, когда секвенции A B и B A истинны во всех моделях на полукольцах .

Литература [1] Бушковский В. Синтаксическое исчисление Ламбека и его семантика // Логические исследования. Вып. 1. — М.: Наука, 1993. — С. 77—96 .

[2] Ламбек И. Математическое исследование структуры предложения // Математическая лингвистика: Сб. переводов / Под ред. Ю. А. Шрейдера и др. — М.: Мир, 1964. — С. 47—68 .

Атомарная теория деления и пересечения двусторонних идеалов полуколец [3] Ламбек И. Кольца и модули. — М.: Мир, 1971 .

[4] Пентус А. Е., Пентус М. Р. Атомарная теория деления двусторонних идеалов полуколец // Фундамент. и прикл. матем. — 2006. — Т. 12, вып. 2. — С. 201—208 .

[5] Фукс Л. Частично упорядоченные алгебраические системы. — М.: Мир, 1965 .

[6] Buszkowski W. Completeness results for Lambek syntactic calculus // Z. Math. Logik Grundlag. Math. — 1986. — Vol. 32. — P. 13—28 .

[7] Buszkowski W. Type logics in grammar // Trends in Logic: 50 Years of Studia Logica / V. F. Hendricks, J. Malinowski, eds. — Kluwer Academic, 2003. — P. 337—382 .

[8] Van Benthem J. Language in Action. Categories, Lambdas and Dynamic Logic. — Amsterdam: North-Holland, 1991. — (Stud. Logic Foundations Math.; Vol. 130) .






Похожие работы:

«Внеклассное мероприятие: "А.Д.Сахаров в эпохе времени" У судьбы не требуя уступок, Не винюсь ни в чем перед судьбой. Главное на свете есть поступок. Действие, рожденное тобой. Не пустопорожнее гаданье, Не словесный дождичек во мгле. Главное на свете есть деяние. Вот...»

«Приложение к приказуУМВД России по г. Сургутуy^ojjJfe^imp^T Mo-K^cf 2018№Название МДОУАдрес МДОУСлужбаЗакреплен1Муниципальное бюджетное дошкольное образовательное учреждение детский сад № 3 "Эрудит"ул. Чехова, 2 34-88-48 32-17-77РЭОЧерепанов О.В. телефон: 76-10-70; телефон...»

«© Коллектив авторов, 2010 М.В. Коновалова1, А.Ю. Вашура1, Е.З. Година2, Д.В. Николаев3, С.Г. Руднев4, А.В. Третьяк2, И.А. Хомякова2, Г.Я. Цейтлин1 ОСОБЕННОСТИ КОМПОНЕНТНОГО СОСТАВА ТЕЛА У ДЕТЕЙ И ПОДРОСТКОВ С ОСТРЫМ ЛИМФОБЛАСТНЫМ ЛЕЙКОЗОМ В...»

«Муниципальное бюджетное дошкольное образовательное учреждение Центр развития ребенка – "Детский сад №28" Проект программы оздоровления детей МБДОУ ЦРР – "Детский сад №28" совместно с кафедрой стоматологии детского возраста, ЛОР болезней и физиотерапии ЧГМА "Влияние функциональных нарушений ЛОР органов и патологий челюстно-лицево...»

«Министерство образования и науки Российской Федерации ФГБОУ ВО "Уральский государственный педагогический университет" Институт менеджмента и права Кафедра философии и акмеологии Разработка программы а...»

«ПУБЛИЧНЫЙ ДОКЛАД О СОСТОЯНИИ И РЕЗУЛЬТАТАХ ДЕЯТЕЛЬНОСТИ МБОУ СОШ №10 с углубленным изучением отдельных предметов в 2017-2018 учебном году Муниципальное бюджетное общеобразовательное учреждение средняя общеобразовательная школа №10 с углубленным изучением отдельных предметов города Сургута Приветственное сло...»

«Урок литературы в 9 классе "Стану буйства я жизни живым отголоском." (основные мотивы и особенности лирики А. Фета) Учитель русского языка и литературы МБОУ "СОШ №29 с углубленным изучением отдельных предметов" г. Курска СОЛОДКОВА И. Н.Цели уро...»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.