Арифметика Пеано — теория первого порядка с равенством, описывающая свойства натуральных чисел. Впервые неформально была предложена итальянским математиком Джузеппе Пеано.
Булева алгебра — это непустое множество B с заданными на нем двуместными операциями ۸ (аналог конъюнкции), ۷ (аналог дизъюнкции), одноместной операцией ⌐ (аналог отрицания) и двумя выделенными элементами 0 и 1 (аналоги лжи и истины).
Колмогоровской сложностью или сложностью описания слова w (то есть конечной последовательности из нулей и единиц) относительно способа описания D (частичной вычислимой функции из {0,1}* в {0,1}) называется минимальная длина такого слова x, что значение функции D на аргументе x равно w: D(x) = w.
Континуум-гипотеза — это следующее утверждение: любое бесконечное подмножество континуума является либо счетным, либо континуальным. Здесь под континуумом (или континуальным множеством) понимается множество, равномощное множеству всех действительных чисел. Счетным же называется множество, равномощное множеству натуральных чисел.
Элиминация (или устранение) кванторов — это процесс нахождения, для всякой заданной формулы, другой формулы, не содержащей кванторов и эквивалентной данной.