Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Доказательство. Действительно, множество теорем P любой дедуктики перечислимо, а потому не может совпадать с неперечислимым множеством истин T. чтдИтак, ответ на основной вопрос получен — если множество истин можно задать алгоритмом, то адекватная дедуктика может быть построена и всё в порядке: всё истинное доказуемо и всё доказуемое истинно. Если же множество истин невозможно задать алгоритмически, то и нет надежды на построение адекватной дедуктики (системы доказательств). Но, может быть, всё не так плохо и неалгоритмические множества истин нам просто не понадобятся на практике? Увы, ответ отрицательный — неалгоритмические множества истин нам совершенно необходимы. 4.4 ¢ .8. Множество истин арифметики Сначала установим важный факт, относящийся к числовым множествам. Говорят, что множество натуральных чисел N ÍN выразимо с помощью множества истин T, если существует такая вычислимая функция F: N® U *, что n Î N тогда и только тогда, когда F (n)Î T. Теорема. Множество истин T выражает хотя бы одно неперечислимое множество натуральных чисел N тогда и только тогда, когда не существует дедуктики < D, D > адекватной T. Доказательство. [Þ] Пусть множество N неперечислимо и выразимо множеством истин T с помощью вычислимой функции F: N® U *. Имеем N = F –1 (Im F Ç T). Но множество значений Im F вычислимой функции натурального ряда перечислимо по лемме 4. Значит множество T неперечислимо, иначе множество Im F Ç T было бы перечислимо и множество N было бы перечислимо по лемме 5. Для неперечислимого множества истин адекватной дедуктики не существует. [Ü] Пусть для множества истин T адекватной дедуктики не существует. Тогда множество Т неперечислимо. Но множество U * перечислимо, пусть оно перечисляется вычислимой функцией F: N® U *. Имеем T = F (F –1(T)). Положим N:= F –1(T). Заключаем по лемме 5, что множество N неперечислимо и выразимо множеством истин T. чтд Данный факт сводит несуществование адекватной дедуктики к выразимости неперечислимых числовых множеств. Но, может быть, ещё не всё потеряно и такие множества истин нам просто не нужны, и про них можно забыть? К сожалению, это не так. Неприятные случаи совсем рядом. Рассмотрим в качестве примера множество истин арифметики. Арифметика — понятие натуральных чисел, операции сложения, умножения, отношения между натуральными числами — это такой элемент общей культуры (не только раздел математики), без которого существование современного человечества трудно себе представить. Как и ранее, обсуждение вопросов о том, является ли арифметика откровением, данным Богом, или же это итог развития науки, является ли способность к счёту врожденной или благоприобретённой, уведут нас далеко от рассматриваемого предмета: дискретная математика для программистов.
Зафиксируем язык арифметики, определённый в п.4.4.7. В этом языке используются: цифры для записи натуральных чисел, буквы для записи переменных, операции сложения + и умножения ×, отношение =, логические связки Ø, ® и кванторы ", $. Далее из этих символов в языке арифметики допускается строить следующие конструкции. 1. Термы. Все числа и переменные суть термы. Выражения вида (t + u) и (t × u), где t и u суть термы, также суть термы. Все переменные в терме являются его параметрами. Терм без параметров называется константой. 2. Атомы. Выражения вида (t = u), где t и u суть термы, называются атомами, или элементарными формулами. Параметрами атомов являются объединение параметров термов. 3. Формулы. Если A и B суть формулы, а x — переменная, то Ø А, А ® B, $ x A, " x A тоже формулы. Кванторы исключают свои переменные из числа параметров подкванторной формулы. Далее формулам без параметров (суждениям) сопоставляются истинностные значения T и F по правилам п. 4.4.2. Все суждения арифметики, имеющие истинностное значение T, образуют множество истин арифметики T. Охарактеризуем класс арифметических множеств. Рассмотрим класс формул языка арифметики не более чем с одним параметром. Будем обозначать такие формулы a(x). Тогда для любого конкретного x ÎN формула a(x) — суждение, и имеет истинностное значение. Множество М:= { x ÎN | a(x) = T} называется сопряженным с формулой a(x). Арифметические множества обладают рядом полезных свойств. Свойство 1. Дополнение к арифметическому множеству есть арифметическое множество.
|