6-

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предложению 1 новая формула f (A1; A2; : : : ; An) над [C] будет также формулой и над C.

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

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

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

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

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

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

Предложению 1 новая формула f (A1; A2; : : : ; An) над [C] будет также формулой и над C.

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

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

Замкнутые классы

Определение. Класс функций C F называется замкнутым, если [C] = C,

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

Замкнутые классы

Определение. Класс функций C F называется замкнутым, если [C] = C,то есть каждая формула над C принадлежит C.

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

Замкнутые классы

Определение. Класс функций C F называется замкнутым, если [C] = C,то есть каждая формула над C принадлежит C.

Примеры

I Класс всех функций F замкнутый.

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

Замкнутые классы

Определение. Класс функций C F называется замкнутым, если [C] = C,то есть каждая формула над C принадлежит C.

Примеры

IКласс всех функций F замкнутый.

IВ силу Предложения 4 любое замыкание [C] является замкнутым классом.

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

Замкнутые классы

Определение. Класс функций C F называется замкнутым, если [C] = C,то есть каждая формула над C принадлежит C.

Примеры

IКласс всех функций F замкнутый.

IВ силу Предложения 4 любое замыкание [C] является замкнутым классом.

IM = [f0; 1; _; &g] класс монотонных функций.