avva | мимоходом, математическое

monomyth дает ссылку на блог-запись, в которой рассказывается, как доказать несчетность действительных чисел с помощью игры.

Аня и Борис играют следующим образом: сначала они выбирают какое-то подмножество отрезка [0,1], назовем его S. Затем, начиная с последовательности 0, 1, ... они на каждом шагу выбирают число, находящееся между двумя предыдущими. Например: 0, 1, А-0.5, Б-0.9, А-0.73, Б-0.742, А-0.739991 итд. Вырастающая таким образом последовательность сходится к какому-то числу x. Если x лежит внутри S, то Аня победила, если нет - Борис.

С одной стороны, если S - весь отрезок [0,1], to Аня тривиальным образом побеждает в любой игре. С другой стороны, если S - счетное множество {s_1, s_2, s_3, ...}, то у Бориса есть выигрышная стратегия: на шаге номер n он выбирает число s_n, если оно лежит в разрешенных границах, или наугад, если не лежит; в итоге в любом случае предел последовательности не может быть s_n. Так как он делает это для каждого n, предел последовательности не лежит в S и он выиграл. Вывод: [0,1] не может быть счетным множеством.

На первый взгляд это кажется остроумным способом доказать несчетность отрезка, хотя интуитивно сразу ясно, что он не более прост, чем каноническое доказательство Кантора. Но если присмотреться, то видно, что на самом деле "игра" тут вещь наносная, ненужная. Есть доказательства или понятия, которые выигрывают оттого, что их формулируют в терминах стратегии какой-то простой игры, но это - не одно из них. Можно ведь то же самое сказать так: предположим, что [0,1] можно пересчитать как {s_1, s_2, ...}. Начнем делить отрезок пополам, каждый раз выбирая ту половину, в которой нет следующего из чисел s_1, s_2, ... Продолжая таким образом, получим последовательность вложенных отрезков, сходящихся к одной точке, которая не может быть ни одной из s_1, s_2, ... - противоречие. Это то же самое доказательство, но внезапно куда-то исчезла Аня и вообще "игра". Они не были на самом деле нужны. В конечном итоге все это частные случаи доказательства того, что любое совершенное множество несчетно. Но стандартное доказательство этого факта требует знакомства с началами топологии, и его не объяснить "на пальцах".