Только что был приведён наглядный пример провала метода неполной индукции. Тем не менее любой человек в повседневной жизни постоянно применяет – не может не применять – этот метод. Вот, например, вы покупаете яблоки. Вам предлагают попробовать. Вы пробуете, яблоко вам нравится, и вы покупаете два кило, применив неполную индукцию, т. е. рассуждая так: если одно яблоко хорошее, то и все хороши. Однако ведь не исключено, что, в отличие от выбранного вами на пробу плода, все остальные окажутся плохи. Да, не исключено, но надкусить все яблоки вам не дадут, потому что это выведет яблоки из категории товаров.
Если магазин, закупающий яблоки ящиками, серьёзно подходит к делу, он подвергнет дегустации не одно, а несколько яблок (но, конечно, не все) из каждого ящика. Если результат дегустации оказался положительным, магазин закупает все ящики целиком, т. е. на практическом уровне принимает решение «Все яблоки хорошие», а следовательно, опять-таки применяет неполную индукцию. Сходная процедура применяется при контроле качества многих товаров. Чтобы проверить, хорошо ли сделана, скажем, электрическая лампочка, нужно её разбить, т. е. уничтожить как товар. Таким образом, полный контроль партии в тысячу лампочек предполагает тотальное уничтожение всей партии. Разработана математическая теория, которая указывает, сколько яблок из ящика или лампочек из тысячи надо опробовать, чтобы при положительном результате их исследования можно было с большой вероятностью заключить о годности всех яблок или всех лампочек партии.
Строго говоря, даже универсальные законы природы формулируются лишь на основе отдельных наблюдений, т. е. на основе метода неполной индукции. Поэтому и наши практические решения (типа решения о качестве яблок или лампочек), и наши теоретические суждения (типа законов природы), если они высказаны в виде универсальных формулировок, верны не в абсолютном смысле, а в лучшем случае лишь с высокой степенью правдоподобия. Иное дело математика, истины которой признаются незыблемыми. А потому и метод неполной индукции, действующий в естественных науках, в математике не действует.
В математике нередко случается, что частная формулировка A(n) оказывается верной для отдельных значений n и вместе с тем не удаётся найти таких значений, для которых частная формулировка была бы неверна. Тогда есть основание выдвинуть гипотезу об истинности универсальной формулировки – но всего только гипотезу, ибо то, чего не удалось найти сегодня, будет, возможно, обнаружено завтра. Вот три замечательных примера, показывающих, что метод неполной индукции не работает в математике.
Пример 28. Великий французский математик XVII в. Пьер Ферма изучал числа вида 22ⁿ + 1, которые стали называть числами Ферма. Ферма полагал, что все они суть числа простые. Для такого мнения, казалось бы, имелись основания, ведь при n = 0, 1, 2, 3, 4 числа Ферма и в самом деле являются простыми. Однако в XVIII в. великий швейцарский (да и российский тоже) математик Леонард Эйлер обнаружил, что число 2²5 + 1 есть произведение двух простых чисел 641 и 6 700 417. Более того, неизвестно, существуют ли простые числа Ферма помимо вышеуказанных пяти, открытых ещё самим Ферма.
Пример 29. Трёхчлен x² + x + 41, указанный Эйлером, принимает простые значения при x = 0, 1, 2, …, 39. Однако при x = 40 его значением будет число составное, а именно 41².
Пример 30. Если брать различные значения n и разлагать двучлен xn – 1 на множители с целыми коэффициентами, то можно заметить, что у каждого из многочленов сомножителей все его коэффициенты равны либо 1, либо –1. Например, x6 – 1 = (x – 1) (x + 1) (x² + x + 1) × (x² – x + 1). Была выдвинута гипотеза, что это обстоятельство справедливо для любого n. Однако доказать эту гипотезу почему-то не удавалось. А в 1941 г. выяснилось, что, хотя коэффициенты разложения действительно обладают указанным свойством при всех n до 104 включительно, в разложении на множители двучлена x105 – 1 среди сомножителей появляется многочлен, у которого некоторые из коэффициентов равны –2.
§ 8. Алфавиты и буквы. Слова и строки. Взаимно однозначные соответствия и мощность. Диагональный метод
В математике любой конечный список знаков принято называть алфавитом. Не предполагается, что эти знаки что-нибудь означают. Иногда говорят не о знаках, а о символах, но опять-таки не предполагая, что они что-либо символизируют. (Честнее было бы говорить не о знаках или символах, а о закорючках, но это уж как-то слишком ненаучно.) Члены алфавита называются буквами.
Первый математический алфавит, который узнаёт школьник, – это алфавит десятичных цифр с буквами 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. А вот алфавит римских цифр: I, V, X, L, C, D, M.
Конечная последовательность идущих друг за другом букв алфавита называется словом в этом алфавите. Например, «ъЪрйрьоь» есть слово в русском алфавите. Пример показывает, что далеко не всякое слово в русском алфавите является русским словом, т. е. словом русского языка.
Слова также называют строками. Содержание этих терминов одинаковое, а различаются они сферами употребления: термин «слово» чаще употребляют те, кто занимается теоретическими изысканиями, тогда как термин «строка» употребителен в более прикладной среде, в частности в информатике. Мы будем использовать оба термина.
Количество букв в слове (строке) именуют его (её) длиной. Так, длина приведённого выше слова в русском алфавите есть 8.
Пример 31. Если алфавит состоит из одной буквы, то число слов длины n равно 1.
Пример 32. Доказать, что если алфавит состоит из двух букв, то число слов длины n равно 2n.
Каждое слово длины n получается приписыванием одной из двух букв алфавита к слову длины n – 1. Стало быть, при удлинении слова на одну букву количество слов удваивается. А количество слов длины 1 есть два.
В примере 32 мы начали с двух слов длины 1. А могли бы начать и с одного слова длины 0, вовсе не содержащего букв. Такое слово называется пустым и обозначается заглавной греческой буквой «лямбда» (Λ).
Рассмотрим множество {a; b; c} из трёх элементов: a, b и c. Напомним, что для того, чтобы получить имя множества, достаточно заключить в фигурные скобки список имён его элементов, разделив их имена запятой или точкой с запятой (последнее удобнее). Найдём все части, или подмножества, нашего множества. Во-первых, три одноэлементные части: {a}, {b}, {c}. Во-вторых, три двухэлементные части: {b; c}, {a; c}, {a; b}. В-третьих (поскольку всякое множество считается частью самого себя), трёхэлементную часть {a; b; c}. Наконец, пустое множество Ø, не содержащее ни одного элемента и считающееся частью любого множества. Всего частей оказалось 8.
Пример 33. Сколько частей у множества, содержащего n элементов?
Пронумеруем элементы числами от 1 до n. Каждой части отнесём строку длины n из плюсов и минусов, образованную по следующему правилу: если элемент с номером k принадлежит нашей части, на k-м месте строки ставим плюс; если же k-й элемент не принадлежит рассматриваемой части, на k-м месте строки ставим минус. Заметим, что не только каждой части множества соответствует ровно одна строка, но и каждой строке длины n, составленной из плюсов и минусов, соответствует ровно одна часть.
Мы получили то, что называется взаимно однозначным соответствием между двумя множествами – в данном случае между множеством частей и множеством строк.
В общем случае взаимно однозначным соответствием между множествами X и Y называется такое соответствие между ними, когда каждому элементу из X соответствует ровно один элемент из Y и каждый элемент из Y соответствует ровно одному элементу из X. Если между двумя множествами имеет место взаимно однозначное соответствие, то количества элементов в обоих множествах совпадают.
Собственно, количество элементов – это и есть то общее свойство, что несут в себе все те множества, между которыми можно установить взаимно однозначные соответствия. Невозможность такого соответствия между множествами X и Y означает различие количеств элементов, содержащихся в этих множествах.
Это математическое уточнение интуитивного понятия количества элементов множества, основанное на понятии взаимно однозначного соответствия, принадлежит одному из величайших математиков XIX в., создателю теории множеств, без которой немыслима современная математика, немецкому учёному Георгу Кантору. Кантор, в частности, первым обнаружил, что бесконечные множества могут содержать различные количества элементов.
В математике количество элементов множества принято называть его мощностью.
Таким образом, выражения:
1. Два множества имеют одинаковое количество элементов;
2. Два множества равноколичественны;
3. Два множества имеют одинаковую мощность;
4. Два множества равномощны;
5. Между двумя множествами можно установить взаимно однозначное соответствие
синонимичны. Они несут в себе одинаковый смысл.
Очевиден следующий принцип транзитивности:
если два множества равномощны третьему, то они равномощны друг другу.
(Предлагаем читателю в качестве упражнения самостоятельно сформулировать принцип транзитивности в терминах взаимно однозначных соответствий.)
Но вернёмся к примеру 33.
В силу только что сказанного частей нашего подмножества столько же, сколько цепочек плюсов и минусов длины n, а число таких цепочек, как показано в примере 32, есть 2n.
