Приведенные Декартовы произведения.

Комбинируя операцию образования декартова произведения с операцией образования классов абстракций, получаем новую операцию, которая нашла применение в матлогике.

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

Пусть - идеал в . Определим отношение  в  формулой

Tеорема 1. Отношение  является отношением эквивалентности в .

1) Рефлексивность отношения  следует из того, что , 2) симметричность очевидна, a 3) транзитивность следует из того, что произвольных

.

Теорема 2. Декартово произведение  функции  согласовано с отношением .

Д о к а з а т е л ь с т в о.  Необходимо показать, что если , то .

Пусть . Из определения  следует, что .

Поэтому , откуда .

Из теорем 1, 2 и следствий, приведенных в § 5 главе III, вытекает, что существует множество  классов абстракций отношения  в  и что в этом множестве определена операция  , индуцированная из  с помощью отношения . Определим отношение  в  формулой , где ,  - классы абстракций , содержащие соответственно  и .

Множество  называется декартовым произведением множеств , приведенным по модулю (короче, приведенным mod ). Аналогично функция (отношение ) называется декартовым произведением функция (отношение ), приведенным mod .

Пусть - произвольная высказывательная функция. Главную проблему в теории приведенных произведений можно сформулировать так:

Зная множества , определить, когда множество , функция  и отношение  удовлетворяют высказывательной функции .

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

Докажем, что справедливы утверждения (I) – (IV).

I. .

Действительно,  и поэтому ((II), §5, глава I) , откуда по закону де Моргана получим (I).

II. Если - высказывательная функция вида ( ) , то .

В самом деле, пусть .

Для  существует элемент , удовлетворяющий .

Обозначим множество этих элементов  через  и положим  для . Пусть  - функция выбора для семейства, состоящего из всех множеств .

Тогда  и для всех  

            (1) ,

откуда . Следовательно, .

Обратно, если , то (1) выполняется для всех . Тогда для этих , откуда . Поэтому  и .

Идеал  называется простым, если для произвольного  либо , либо .

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

(III). Если идеал  простой и - отрицание , то .

Действительно, .

(IV). Если идеал  простой, то  если, кроме того, обозначит , то . Это утверждение следует из первых трех.

Доказанные утверждения дают следующее решение поставленной выше проблемы.

Назовем высказывательную функцию  элементарной, если она получается из высказывательных функций :

a)

b)

c)

С помощью операций исчисления высказываний и кванторов .

°Теорема 3. Если - простой идеал,  - элементарная высказывательная функция,  - произвольные элементы из , то      (2).

Д о к а з а т е л ь с т в о.  Если - одна из функций вида a), b), c), то (2) в этом случае верно. Действительно,

в случае a) левая часть (2) эквивалентна ,

в случае b) левая часть (2) эквивалентна ,

в случае c) левая часть (2) эквивалентна .

Правая часть (2) эквивалентна

в случае a)

 в случае b)

 в случае c)

из определения множеств , функции , отношения  и простого идеала следует, что левая и правая части в (2) эквивалентны.

В силу утверждений (I)-(IV), если формула (2) справедлива для высказывательных функций  и , то она справедлива для высказывательных функций, получающихся из и с помощью операций исчисления высказываний и кванторов . Таким образом, теорема 3 доказана.

°Следствие 4. Если высказывательная функция - элементарная, то . Это следует из теоремы 3 , если высказывательная функция не содержит переменных .

Пример 2. Если  - тело с операцией сложения  и операцией умножения , то множества  - тело с операциями  и , где  и - декартовы произведения  и  соответственно.

Аналогично, если каждое из множеств  - упорядоченное тело с операциями  и  и отношениями порядка , то  - упорядоченное тело с операциями  и  и отношениями порядка .

Эти утверждения получаются из следствия 5, если высказывательные функции « - тело с операциями  и » и « - упорядоченное тело с операциями  и  и отношениями порядка » записать в виде элементарных высказывательных функций  и  соответственно.

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