Матричные иерархии языков первого порядка

157

Семейства всех кодов и полукодов языка Z^ обозначим через Си и $Ij соответственно. Нетрудно сообразить, что любой язык ладает полукодом, состоящим, например, из кодов всех формул го языка. Однако не всякий язык обладает кодом. В самом деле, пусть LI- квазиэквациональный язык, т.е. совокупность всех тождеств или формул вида (Р =» УЖ,..^Г„ ( V 1 öl?'V 4^ ) . Тогда ясно,

Щ^р ) ^

Пусть ^ ^ Vdy.»' ьГ^ (У "Ï ^/ ) . Тогда ^^Ц и, очевидно.

Для кода или полукода L-'JI^CZj некоторого языка 2/ через

iQ обозначим код или полукод языка nZ r=^|^£'é 1 ^"^ ^Zr } ,

где J " пренексная нормальная форма отрицания!^ , полученная по закону дистрибутивности Л относительно V . Нетрудно нять, как на матричном языке описать построение множества риц Ли из множества матриц О . Для семейства Ег^ некоторых подмножеств множества и , которое содержит само С , обозна-

Для сокращения обозначений кодов и полукодов путем их торизации будем, как обычно, использовать отношения ности, согласованные с отношением ^ . Такие эквивалентности мы будем называть стандартными и определим их следующим образом: эквивалентность ^"^^ на множестве 7Т^ CZi назовем стандартной, если й"^^^^ ^^ЛСе'о^'^'—^<Il^''^ÎU^ . Через $Г^ обозначим

класс этой эквивалентности, содержащий ^^.

ОПРЕДЕЛЕНИЕ . Упорядоченное включением семейство языков //££ называется матричной иерархией языков, если существует множество WE2 ^ , семейство t,^ для каждого о €х1 w дартная эквивалентность '^ такие, что для любого языка и^ Ъ

Обозначения : //=//f^j Vi, [SJC^ ^}]при \(lФф и И^'НС'^) при

Ч - Ф • ^