Диагональные конструкции: Кантор, Бэр, теория вычислимости|Александр Шень|Семинар КТ №17

Знаменитая "диагональная конструкция" придумана Кантором для доказательства того, что нельзя пронумеровать натуральными числами все последовательности нулей и единиц. Она может быть пересказана так: "на n-м шаге мы гарантируем выполнение n-го требования и так строим объект, удовлетворяющий всем требованиям". Этот тип рассуждений встречается во многих ситуациях (в теории алгоритмов и не только). Мы разберём несколько примеров в зависимости от интересов слушателей. Задача для разогрева: можно ли отметить точки на прямой так, чтобы расстояния между ними были натуральными числами и каждое из них встречалось ровно по одному разу? Александр Шень (CNRS, ИППИ РАН) — специалист по дискретной математике и информатике, автор книг, популяризатор. Канал t.me/turings_crossword Страница семинара turing.tilda.ws 00:00:00 начало 00:06:30 диагональный метод Кантора 00:12:00 перерыв 00:13:50 продолжение 00:15:30 идея метода Кантора 00:20:45 задача для разминки 00:38:00 сумма трёх биекций 00:53:00 транфинитная индукцию 01:11:00 две точки на каждой прямой 01:15:30 теорема Гёделя о полноте 01:27:00 ответы на вопросы