Теория упорядоченных множеств

Теория отношения эквивалентности

Это теория структур с одним универсумом и одним бинарным отношением R, удовлетворяющим аксиомам

1) " x R (x, x),

2) " x " y [ R (x, y) → R (y, x)],

3) " x " y " z [ R (x, y) & R (y, z) → R (x, z)].

Структура (A, =, <), где инфикс '<' обозначает бинарное отношение, удовлетворяющее аксиомам

1) " x Ø (x < x),

2) " x " y " z [(x < y) & (y < z) → (x < z)],

3) " x " y [(x < y) Ú (x = y) Ú (y < x)],

называется упорядоченным множеством. Примером такой структуры может быть множество вещественных чисел с обычным отношением '<'.

В процессе изучения теории часто полезным оказывается ее расширение или сужение. Теория T' = (σ', Γ') называется расширением теории T = (σ, Γ), если σ Í σ' и [ Γ ] Í [ Γ' ]. Расширение T' называется консервативным, если [ Γ' ] Ç Form (σ) = [ Γ ].

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

Теория T заданной сигнатуры σ называется полной, если для любого предложения A Î Sent (σ) либо A либо Ø A принадлежит теории T.

Если рассматриваемая теория T является теорией Th (S) некоторой σ -структуры S, то T полна, так как любое σ -предложение либо истинно либо ложно в структуре S.

Если же теория задана аксиоматически, то ее полнота не гарантирована. Например, теория групп не полна, так как предложение, выражающее коммутативность группы, и его отрицание не являются следствием групповых аксиом, поскольку в математике имеются как примеры коммутативных, так и некоммутативных групп.

Теория T Í Sent (σ) называется алгоритмически разрешимой, если существует алгоритм, который по любому предложению A Î Sent (σ) отвечает на вопрос, принадлежит ли оно теории T.

Для доказательства разрешимости многих теорий применим так называемый метод элиминации кванторов. Этот метод применим к теориям, для которых может быть выполнен элементарный шаг элиминации, то есть для любой формулы A вида $ x [ A ₁(x) & A ₂(x) &... & A_n (x)], где A_i (x) - атомарная формула или отрицание атомарной формулы, может быть построена бескванторная формула B такая, что A «B истинна в рассматриваемой теории.

Если это условие выполнено, то к каждому предложению A Î Sent (σ), где σ - сигнатура рассматриваемой теории, применима следующая процедура.

1) Превратить с помощью правил де Моргана самые внутренние кванторы в кванторы существования, если они не являются таковыми.

2) Привести область действия каждого из этих кванторов к ДНФ.

3) Распределить кванторы существования по дизъюнктивным членам.

4) Элиминировать их с помощью элементарных шагов элиминации.

5) Если результат все еще не является бескванторным, то повторить описанные шаги, в противном случае рассматриваемое выражение превратилось в истину или ложь.

Если исходная формула A не является предложением, то результатом элиминации будет формула, выражающая предикат, от свободных переменных исходной формулы A.

Дата добавления: 2015-08-31