НОУ ІНТУІТ, Лекція, Діаграми
Теорія напівгруп
Наш другий приклад - теорія напівгруп. Її сигнатура складається з рівності та єдиного двомісного функціонального символу, що називається множенням; результат множення і ми будемо позначати.
Теорія складається з аксіом рівності (включаючи коректність множення: ; ми опускаємо зовнішні квантори загальності) і аксіоми асоціативності
Нормальні моделі цієї теорії називають напівгрупами.
Теорема 69. Безліч теорем теорії напівгруп (множина замкнутих формул зазначеної сигнатури, істинних у всіх напівгрупах) не можна розв'язати.
Нам знадобиться конкретний спосіб завдання напівгруп за допомогою утворюючих та співвідношень. Нехай фіксована деяка кінцева множина, звана алфавітом. Елементи його називають літерами, а кінцеві послідовності літер - словами (даного алфавіту). На словах визначено операцію з'єднання (приписування), щодо якої вони утворюють напівгрупу, яка називається вільною напівгрупою. Ця напівгрупа має нейтральний елемент - порожнє слово, приписування якого до будь-якого слова не змінює останнього.
Нехай фіксується алфавіт, а також кінцева кількість пар слів цього алфавіту. Два слова алфавіту назвемо еквівалентними, якщо одне можна перетворити на інше, багаторазово роблячи заміни підслів вигляду. Легко перевірити, що виходить відношення еквівалентності та що операція приписування коректно визначена на класах еквівалентності та асоціативна. Виходить напівгрупа. Її називають напівгрупою з утворюючими з і співвідношеннями.
141. Скільки елементів у напівгрупі з утворюючими та співвідношеннями , , (через ми позначаємо порожнє слово)? (Відповідь: ; це група.)
Відомо, що існують такі утворюючі та співвідношення, за яких проблема рівності слів (з'ясувати,чи належать два дані слова одному класу еквівалентності) є алгоритмічно нерозв'язною (докладніше див [5]). Ми зараз покажемо, що це питання можна звести до питання про виведення деякої формули в теорії напівгруп, так що якби вона була вирішуваною, то вийшло б протиріччя.
Побудова такої формули відбувається дуже природним чином; ми пояснимо його з прикладу. Нехай ми хочемо дізнатися, чи будуть слова і рівні в напівгрупі з утворюючими і співвідношеннями і . (Іншими словами, ми хочемо дізнатися, чи можна зі слова отримати слово за допомогою замін підслів та .) Як сформулювати це питання у термінах формул? Напишемо таку формулу:
Навпаки, якщо слово не виходить із заміною, то існує напівгрупа , в якій ця формула не істинна: треба взяти якраз напівгрупу з утворюючими та і співвідношеннями і значенням змінної вважати клас слова , а значенням змінної вважати клас слова . Тоді значенням терму буде клас слова , рівний класу слова з побудови напівгрупи. Аналогічним чином за такої оцінки буде істинно і рівність. А рівність нічого очікувати істинно, оскільки значення терма є клас слова , значення терма є клас слова , а ці класи різні за припущенням.
Таким чином, будь-який алгоритм, що перевіряє істинність формул у класі всіх напівгруп, можна було б використовувати для перевірки рівності двох слів у напівгрупі, заданої утворюючими та співвідношеннями. А серед таких напівгруп є нерозв'язні.
Теорія груп (у якій, крім асоціативності, є ще аксіоми існування одиниці і зворотного), також нерозв'язна, але підтвердження цього складніше, ніж напівгруп . Це й не дивно, оскільки з нерозв'язності теорії груп формально виводиться нерозв'язність теорії напівгруп, як показуєнаступне завдання.
142. Нехай теорія можна розв'язати, а теорія тієї ж сигнатури виходить з додаванням кінцевого числа аксіом. Тоді теорія можна розв'язати. (Вказівка: додаткові аксіоми з'єднуємо кон'юнкціями та поміщаємо у посилку імплікації.)
Додавання аксіом може зробити нерозв'язну теорію. Наприклад, як ми згадували, це відбувається з теорією груп при додаванні аксіоми комутативності.