Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

Предложение 4. Пусть ? (X1,…,Xn, Y1,…, Ym) – формула, переменные которой берутся лишь из числа X1,…,Xn, Y1,…, Ym . Назовём такую формулу предикативной, если в ней связными являются только переменные для множеств
(т.е. если она может быть приведена к такому виду с помощью принятых сокращений). Для всякой предикативной формулы ? (X1,…,Xn, Y1,…, Ym)
[pic] [pic]Z[pic]x1 …[pic]xn ([pic][pic] Z [pic] ? (x1,…,xn, Y1,…, Ym)).

Доказательство. Мы можем ограничиться рассмотрением только таких формул ?, которые не содержат подформул вида Yi [pic] W, так как всякая такая подформула может быть заменена на [pic]x (x = Yi & x [pic] W), что в свою очередь эквивалентно формуле [pic]x ([pic]z (z [pic] x [pic] z [pic]
Yi) & x [pic] W). Можно также предполагать, что в ? не содержатся подформулы вида X[pic]X, которые могут быть заменены на [pic]u (u = X & u
[pic] X), последнее же эквивалентно [pic]u ([pic]z (z [pic] u [pic] z
[pic] X) & u [pic] X). Доказательство проведем теперь индукцией по числу k логических связок и кванторов, входящих в формулу ? (записанную с ограниченными переменными для множеств).

1. Пусть k = 0. Формула ? имеет вид xi [pic] xj, или xj [pic] xi, или xi [pic] Yi, где 1 ? i < j ? n. В первом случае, по аксиоме В1, существует некоторый класс W1 такой, что

[pic]xi[pic]xj ([pic][pic]W1 [pic] xi [pic] xj).
Во втором случае, по той же аксиоме, существует класс W2 такой, что

[pic]xi[pic]xj ([pic][pic]W2 [pic] xj [pic] xi), и тогда, в силу

[pic] [pic]X[pic]Z [pic]u [pic]v ([pic][pic] Z [pic] [pic] [pic] X), существует класс W3 такой, что

[pic]xi[pic]xj ([pic][pic]W3 [pic] xj [pic] xi).
Итак, в любом из первых двух случаев существует класс W3 такой, что

[pic]xi[pic]xj ([pic][pic]W [pic] ? (x1,…,xn, Y1,…, Ym)).
Тогда, заменив в
[pic] [pic]X[pic]Z [pic]v1…[pic]vk[pic]u[pic]w ([pic] [pic] Z [pic] [pic]

[pic] X)
X на W, получим, что существует некоторый класс Z1 такой, что

[pic]x1… [pic]xi-1[pic]xi[pic]xj ([pic][pic]Z1 [pic] ? (x1,…,xn, Y1,…,

Ym)).
Далее, на основании

[pic] [pic]X[pic]Z [pic]v1…[pic]vm[pic]x1…[pic]xn ([pic] [pic]

[pic] Z[pic][pic][pic]X) там же при Z1 = X, заключаем, что существует класс Z2 такой, что

[pic]x1 … [pic]xi [pic]xi+1 … [pic]xj ([pic] [pic] Z2 [pic] ? (x1,…,xn,

Y1,…, Ym)).
Наконец, применяя

[pic] [pic]X[pic]Z [pic]v1…[pic]vm[pic]x1…[pic]xn ([pic][pic] Z

[pic][pic][pic]X)

(1) там же при Z2 = Х, получаем, что существует класс Z такой, что

[pic]x1…[pic]xn ([pic] [pic] Z [pic] ? (x1,…,xn, Y1,…, Ym)).
Для остающегося случая xi [pic] Yi теорема следует из (1) и
[pic] [pic]X[pic]Z [pic]x[pic] v1…[pic]vm ([pic] [pic] Z [pic] x [pic] X).

2. Предположим, что теорема доказана для любого k < s и что ? содержит s логических связок и кванторов.

(a) ? есть [pic] ?. По индуктивному предположению, существует класс W такой, что

[pic]x1…[pic]xn ([pic] [pic] W [pic] ? (x1,…,xn, Y1,…, Ym)).

Теперь остается положить Z = [pic].

(b) ? есть ? [pic]?. По индуктивному предположению, существуют классы
Z1 и Z2 такие, что

[pic]x1…[pic]xn ([pic] [pic] Z1 [pic] ? (x1,…,xn, Y1,…, Ym)) и

Рекомендуем скачать другие рефераты по теме: реферат на тему право, реферат орган.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата