Ученые записки математических кафедр вып. 1970 г.

формула, о которой шла речь в определении 5. Докажем, что Ф* истинна т* ит-т>. к Ф* истинна на Ci . Будем считать для определенности, что 1-1 . Пусть = , С1/и^ ~ & е ( й ) > ) У . ЩА)- по-прежнему, множество всех слов в алфавите А. со (соответственно. со,у ) отношение эквивалентности на М1(А), которое определяется с помощьюслов <2-^ , Я■(&■/) (соответственно с помощьюслов Я^ {&>>) , (^ч) )• Ф*яв,х, ...йь.Х.п.У*, У*5 V Л Ч а Г п с ^> А т ¿ч <Г ч Ф*яй1г ,,,МпХп. Г / 1 у / I V А Р*Ыф , где Р*(х) получается из Р (Я.) заменой всюду знака = на ,со и 1 на Л Очевидно, чтобы доказать, что Ф истинна на С</н, т. и т.т., к Ф, истинна на (7у , согласно лемме I, доста­ точно доказать, что Ф истинна на М7(А) т. и т.т,, к истинна на У/(А) . Пусть У при Ь=2к*1 при где ¿¿.=^ ^ * О Пусть Ф, истинна на МА(А). £)уществуют разрешающие ф у и ц я и у , ! ..... . V для Ф , определенные на М/М). Покажем, что они будут разрешающими функциями идля~ Ф, , Всамом деле, пусть А “ лю*«е слова из \УМ) , тогдаУЛ *<¿(6 ,,.,.,^, ^ .../¿ ¡)-)^Л истинна на МА(А) , значит найдется ¿„ такое, что при'всех : ■ , У, А А < тогда очевидно; что существуют такие слова А.. ; ЧТо А € Н к , ^ Ч у ^Ч/ (А " А , ),■■■) 0° Лу для всех у