С нами с 29-12-2023
Карма: 11
Постов: 1
Комментариев: 3
Этот пользователь пока ничего о себе не написал
Был у меня был период увлечения математической логикой в тщетной попытке понять доказательство независимости континуум-гипотезы от 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".
Читать дальше →