Арифметическая иерархия и ее простейшие свойства. Универсальные множества в арифметической иерархии. Строгость арифметической иерархии. Теоремы Тарского и Геделя. Системы доказательств и перечислимые множества. Колмогоровская сложность, ее невычислимость. Доказательство Чайтина теоремы Геделя о неполноте.