ydmitry
С нами с 29-12-2023
Карма: 12
Постов: 1
Комментариев: 4
С нами с 29-12-2023
Карма: 12
Постов: 1
Комментариев: 4
Этот пользователь пока ничего о себе не написал
Был у меня был период увлечения математической логикой в тщетной попытке понять доказательство независимости континуум-гипотезы от ZFC. Хочу рассказать оттуда об одном занимательном факте и предложить не очень сложную, но красивую, на мой взгляд, задачку.
Сначала немного определений. Назовём структурой произвольное множество M, на котором заданы какие-то отношения. Например, (N, <) - множество натуральных чисел с отношением "меньше", или (R, +) - множество действительных чисел с отношением сложения. "Отношение сложения" - это множество всех троек (x, y, z), для которых x + y = z.
Имея структуру, можно задаться вопросом, какие множества в ней определяемы с помощью стандартных логических формул (и, или, отрицание, существует, для любого). Разрешён знак =, который означает совпадение элементов.
Чтобы определить множество, нужно написать формулу с одной свободной переменной, которая будет верна только на этом множестве. Например, множество чётных чисел в структуре (Z, +) определяется формулой "существует y такое, что x = y + y". Свободная переменная здесь - x, и утверждение верно тогда и только тогда, когда x чётное.
Ещё несколько примеров.