Диагональные конструкции: Кантор, Бэр, теория вычислимости|Александр Шень|Семинар КТ №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 ответы на вопросы