Парадокс Эпименида
Рассмотрим следующий пример:
- Пусть P – это предикат «Отсутствует истинная инстанциация предиката P». Предположим, что P является допустимым предикатом (я проанализирую это предположение в следующем разделе); тогда в действительности это не только предикат, но и высказывание, поскольку в нем отсутствуют параметры.
- Пусть r – это отношение, соответствующее P (т.е. отношение, в теле которого содержаться те и только те кортежи, которые представляют истинные инстанциации P). Поскольку у P отсутствуют параметры, у r отсутствуют атрибуты (т.е. это отношение степени ноль), и, следовательно, оно должно быть либо TABLE_DEE, либо TABLE_DUM. Напомню, что TABLE_DEE – это единственное отношение без атрибутов и с ровно одним кортежем (0-кортежем), а TABLE_DUM – это единственное отношение без атрибутов и без кортежей [5].
- Предположим, что r – это TABLE_DEE. Тогда интерпретация (наличие в r единственного кортежа) состоит в том, что P является истинным – что, по определению, означает отсутствие истинных инстанциаций P, и, следовательно, r не должно содержать никаких кортежей (т.е. должно быть TABLE_DUM).
- Наоборот, предположим, что r – это TABLE_ DUM. Тогда интерпретация (того факта, что в r нет ни одного кортежа) состоит в том, что P является ложным – что, по определению, означает наличие хотя бы одной (на самом деле, ровно одной) истинной инстанциации P, и, следовательно, r должно содержать хотя бы один (на самом деле, ровно один) кортеж (т.е. должно быть TABLE_ DEE).
Вероятно, вы уже поняли, что этот пример воспроизводит в реляционной форме известный парадокс Эпименида. И конечно, корнем проблемы является ссылка на самого себя: предикат P ссылается сам на себя.
На тот случай, если вам неудобно полагаться на аргументы, основанные на специальных отношениях TABLE_DEE и TABLE_DUM, позвольте привести другой пример, иллюстрирующий тот же случай. Этот пример представляет собой существенно упрощенный вариант примера, приведенного Дэвидом Макговерном (David McGoveran) и опубликованного мной в колонке журнала DBP&D [2]. Пусть r – это отношение с единственным атрибутом N типа INTEGER, и пусть предикатом для r является «Мощность r есть N». Если r пусто, то мощность r равна нулю, и, следовательно, в r должен входить кортеж t = TUPLE {N 0}, и поэтому r не должно быть пусто. Но если кортеж t = TUPLE {N 0} действительно входит в r, то r не является пустым, и, следовательно, кортеж t не должен входить в r. То есть снова имеется некоторая разновидность того же парадокса.