Формальна аксіоматична теорія вважається визначеною, якщо виконані наступні умови:
1. Заданий мову теорії.
2. Визначено поняття формули в цій теорії.
116
Курс лекцій з математичної логіки
3. Виділено деякий безліч формул, які називаються аксіомами.
4. Визначено правила виведення в цій теорії.
Серед математичних теорій виділяють теорії першого порядку. Вони відрізняються від теорій вищих порядків тим, що не допускають в своєму викладі предикати, які мають в якості можливих значень своїх аргументів інші предикати і функції. Крім того, вони не допускають кванторние операції по предикатам або функцій.
Теорій першого порядку досить для виразів більшості відомих математичних теорій.
У нашому курсі математичної логіки ми обмежимося тільки математичними теоріями першого порядку, які називають іноді елементарними теоріями.
§ 1. Мова першого порядку
Визначення 1. Алфавітом А називається всяке непорожнє кінцеве безліч символів. Символи алфавіту називаються буквами.
Визначення 2. Словом в алфавіті А називається будь-яка кінцева послідовність літер алфавіту А. Порожня послідовність літер називається порожнім словом і позначається через A.
Будемо говорити, що два конкретних слова аха2. ап і Ь, Ь2. bk алфавіту А рівні і писати axar. ап = j2. bh
якщо п = k і а \ =. U2 =?> 2> ••• »ап - Іоп • При цьому число
п називають довжиною цього слова.
Нехай T деяка теорія. Позначимо через А (Т)
алфавіт цієї теорії. безліч Е
безлічі виразів Е (Т) теорії T називають мовою теорії Т.
Мови першого порядку обслуговують теорії першого порядку. В алфавіт будь-якої теорії T першого порядку входять по суті ті ж символи, які були введені
МАТЕМАТИЧНІ ТЕОРІЇ
раніше. Це символи логічних операцій , V,
символи кванторних операцій V, 3; допоміжні символи - дужки, коми; рахункове безліч «-Місцеві предикатних букв Aj (п, j> l), де верхній індекс
вказує на число місць, а нижній - номер предикатной букви; кінцеве (можливо, і пусте) або рахункове
безліч функціональних букв l), де верх-
ний індекс вказує на число змінних, що входять в функцію, а нижній - номер функціональної літери; кінцеве (можливо порожній) або рахункове безліч предметних констант af (i> l).
Зокрема, під функціональної буквою можна розуміти ланцюжок логічних операцій.
Безліч предикатних букв разом з безліччю функціональних букв і констант називається сигнатурою мови даної теорії і є його специфічною частиною.
Таким чином, в теорії T першого порядку можуть бути відсутні деякі або навіть всі функціональні букви і предметні константи, а також деякі, але не всі предикатні літери.
Різні теорії першого порядку можуть відрізнятися один від одного за складом букв в алфавіті.
§ 2. Терми і формули
Подальший опис теорії T вимагає перш за все індуктивних визначень терма і формули. терми
і формули - це два класи слів безлічі Е (Т).
Визначення терма. 1. Предметна змінна і предметна константа суть терми.
2. Якщо T1, г2. гп - терми і А - символ і-місцевої
операції, то А-1
3. Ніяких інших термів, крім визначених у п. 1 і п. 2. ст T немає.
Згідно природної інтерпретації, терм - це ім'я деякого предмета. Крім змінних і предметних
118
Курс лекцій з математичної логіки
констант, термами є ланцюжки, утворені з змінних і предметних констант за допомогою символів операцій, т. к. в неявної інтерпретації він тлумачиться як значення деякої функції.
Визначення формули. 1. Якщо А - символ «-Місцеві відносини (предикат або функція), a T1, г2. гп -
терми, то А (гі, г2. гп) - формула. Зокрема, якщо А -
предикатна буква А ", то А" (гі, г2. гп) називається елементарної формулою.
2. Якщо А і Б формули, то А В, AvB, А-> В, A-формули.
3. Якщо А - формула, а у - предметна змінна, яка входить в А вільно або не міститься в А, то
вираження VyA. Зуа - формули. При цьому А називається областю дії квантора.
4. Ніяких інших формул, крім визначених у п. 1 - 3. немає.
§ 3. Логічні та спеціальні аксіоми.
Аксіоми теорії першого порядку T розбиваються на два класи: логічні аксіоми і спеціальні (нелогічні або власні аксіоми).
Логічні аксіоми. Хоч би якими були формули А, В і С теорії Т, такі формули є логічними аксіомами теорії T.
4) VXiA (Xi) -> A (f), де A (xj) є формула теорії T і t є терм теорії Т, вільний в A (Xi). Відзначимо, що t може збігатися з х. і тоді ми приходимо до аксіоми V ^ A (Xi) А (х;);
Попередня 33 34 35 36 37 38. 51 >> Наступна