Diskretka5

Замкнутые классы функций

Свойства замыкания

Предложение 2. Для каждого C F имеет место C [C]:

Доказательство. Пусть f (x1; x2; : : : ; xn) 2 C. Но x1; x2; : : : ; xnформулы над C.

Замкнутые классы функций

Свойства замыкания

Предложение 2. Для каждого C F имеет место C [C]:

Доказательство. Пусть f (x1; x2; : : : ; xn) 2 C. Но x1; x2; : : : ; xnформулы над C. Значит f (x1; x2; : : : ; xn) формула над C, то есть f (x1; x2; : : : ; xn) 2 [C].

Замкнутые классы функций

Свойства замыкания

Предложение 3. Если C D, то [C] [D].

Замкнутые классы функций

Свойства замыкания

Предложение 3. Если C D, то [C] [D].

Доказательство. Индукция по индуктивному определению.

Замкнутые классы функций

Свойства замыкания

Предложение 3. Если C D, то [C] [D].

Доказательство. Индукция по индуктивному определению.

I Каждая переменная есть формула над C и над D.

Замкнутые классы функций

Свойства замыкания

Предложение 3. Если C D, то [C] [D].

Доказательство. Индукция по индуктивному определению.

IКаждая переменная есть формула над C и над D.

IПусть f 2 C D и A1; A2; : : : ; An формулы над C. Делаем индукционное предположение о том, что A1; A2; : : : ; An формулы над D.

Замкнутые классы функций

Свойства замыкания

Предложение 3. Если C D, то [C] [D].

Доказательство. Индукция по индуктивному определению.

IКаждая переменная есть формула над C и над D.

IПусть f 2 C D и A1; A2; : : : ; An формулы над C. Делаем индукционное предположение о том, что

A1; A2; : : : ; An формулы над D. Так как f 2 D, то новая формула f (A1; A2; : : : ; An) над C будет также формулой и над D.

Замкнутые классы функций

Свойства замыкания

Предложение 3. Если C D, то [C] [D].

Доказательство. Индукция по индуктивному определению.

IКаждая переменная есть формула над C и над D.

IПусть f 2 C D и A1; A2; : : : ; An формулы над C. Делаем индукционное предположение о том, что

A1; A2; : : : ; An формулы над D. Так как f 2 D, то новая формула f (A1; A2; : : : ; An) над C будет также формулой и над D.

IТак как других формул над C нет, каждая формула над C будет формулой над D, то есть [C] [D].

Замкнутые классы функций

Свойства замыкания

Предложение 4. Для каждого C F имеет место [C] = [[C]].

Замкнутые классы функций

Свойства замыкания

Предложение 4. Для каждого C F имеет место [C] = [[C]].

Доказательство. По предложению 2 имеем [C] [[C]].