Привет!
Подскажите, как решать такую задачку.
Преподаватель дал, сказал - дома подумай, а я не знаю как ее решить.
Задача:
(тут обозначения: "А" - для любого (тоже что А перевернутое), "Э" - существует)
Назовем АЭ-формулой любую формулу вида
Ах1 Ах2 ... Ахm Эу1 Эу2 ... Эуn Ф
где x1,...,xm,y1,...,yn - произвольные переменные, m,n>=0, Ф - бескванторная.
Доказать, что множество геделевских номеров всех АЭ-формул сигнатуры s0 (симга 0) является рекурсивным.