Был у меня был период увлечения математической логикой в тщетной попытке понять доказательство независимости континуум-гипотезы от ZFC. Хочу рассказать оттуда об одном занимательном факте и предложить не очень сложную, но красивую, на мой взгляд, задачку.
Сначала немного определений. Назовём структурой произвольное множество M, на котором заданы какие-то отношения. Например, (N, <) - множество натуральных чисел с отношением "меньше", или (R, +) - множество действительных чисел с отношением сложения. "Отношение сложения" - это множество всех троек (x, y, z), для которых x + y = z.
Имея структуру, можно задаться вопросом, какие множества в ней определяемы с помощью стандартных логических формул (и, или, отрицание, существует, для любого). Разрешён знак =, который означает совпадение элементов.
Чтобы определить множество, нужно написать формулу с одной свободной переменной, которая будет верна только на этом множестве. Например, множество чётных чисел в структуре (Z, +) определяется формулой "существует y такое, что x = y + y". Свободная переменная здесь - x, и утверждение верно тогда и только тогда, когда x чётное.
Ещё несколько примеров.
-
Ноль в структуре ( Z, +) определяется формулой "x + x = x".
-
Отношение порядка в структуре ( N, +) определяется формулой "существует z такое, что x + z = y". Эта формула верна, когда x < y.
-
Множество неотрицательных чисел в структуре ( Z, +, *) можно определить с помощью теоремы Лагранжа: "cуществуют такие k, l, m, n, что x = k*k + l*l + m*m + n*n".
-
Объединяя формулы 2 и 3, на структуре ( Z, +, *) можно определить и отношение x < y: "существуют такие z, k, l, m, n что (x + z = y и z = k*k + l*l + m*m + n*n и !(z = 0)).
Ещё одно определение, обещаю что последнее. До сих пор все формулы в примерах не использовали константы из множества M. Если константы использовать разрешено (например "x < 0" - отрицательные числа в структуре (Z, <)) то определение называется параметрическим.
Очевидно, что в любой структуре любое конечное множество (например, <42, 12345, 100500>) является параметрически определяемым: мы просто перебираем в формуле все его элементы: "x = 42 или x = 12345 или x = 100500". С помощью отрицания можно определить дополнение к любому конечному множеству.
Наконец, обещанный занимательный факт.
В структуре (С, +, *) -т.е. на множестве комлексных чисел с операциями сложения и умножения - ничего другого определить нельзя! Только конечные множества и дополнения к ним. Можно составлять сколько угодно сложные логические конструкции, с любой степенью вложенности квантификаторов "существует" и "для любого", использовать в формуле любые константы - и всё равно формуле будет удовлетворять либо конечный набор чисел, либо всё, кроме конечного набора. Мне это кажется поразительным.
И задача: выше приводились примеры, как определить (непараметрически, без использования констант) отношение x < y в структурах (N, +) и (Z, +, *). А сможете доказать, что в структуре (Z, +) это сделать нельзя? #math