Cтраница 2
Таким образом, для всех правил образования рекурсивных термов наше утверждение доказано. Так как оно верно для исходных рекурсивных термов, то тем самым наше индуктивное доказательство закончено, и мы доказали, что для каждой рекурсивной константы можно определить цифру такую, что равенство данной константы и цифры выводимо в ограниченной арифметике. [16]
Автор прилагал усилия, чтобы сделать изложение доступным для возможно более широкого круга читателей. От читателя требуется определенная математическая культура и готовность терпеливо восполнять недостающие рутинные шаги в многочисленных индуктивных доказательствах. Что касается логики, то достаточно владеть вводным в классическую математическую логику курсом. Учебник Мендельсона [1], например, содержит все необходимые сведения. Знакомство с литературой по интуиционистской логике, в особенности с книгой Гейтинга [3] и Клини и Весли [1], является желательным, но не необходимым. Возможно, при первом чтении книги читатель пожелает получить представление о различных интуиционистских теориях и способах их исследования и при этом избежать длинных и утомительных доказательств. [17]
Этот принцип называется структурной индукцией. Ьп часто могут являться конструкторами с отсутствующими аргументами, например nil в случае со списками, но в общем случае они могут быть и конструкторами, применимыми к другим типам, отличным от D, если так, то этап базового случая в любом индуктивном доказательстве будет более сложным. [18]
Мы заключаем, что если 0 - корень многочлена / ( ж), отличный от а, то является и корнем q ( x) в Zp. Следовательно, / ( ж) не может иметь больше k разных корней, что завершает индуктивное доказательство. [19]
Доказательство достаточности - трудная часть теоремы. Известные доказательства основаны на индуктивном по числу ребер е построении 3-многогранника, который реализует данный трехсвяз-ный граф G. Предположение, что G - трехсвязный граф, влечет, что е б, причем равенство возможно в том и только том случае, когда G Кц. Общий шаг индуктивного доказательства разбивается на две стадии. На первой стадии указывается метод, по которому каждому трехсвязному планарному графу с более чем 6 ребрами ставится в соответствие граф G такого же типа, но имеющий меньшее число ребер, чем G. На второй стадии дается метод, по которому из 3-многогранника, реализующего G, строится 3-многогранник М, реализующий G. Имеющиеся доказательства различаются методами, используемыми на второй стадии. [20]
Предельные случаи особенно поучительны. Если выведен закон, относящийся ко всем млекопитающим, то он должен быть верен и по отношению даже к такому млекопитающему, как кит. Рассматривая его, нам даже возможно удастся опровергнуть обобщающий характер этого закона. Если мы, однако, обнаружим, что обобщающее правило подтверждается даже и этими крайними случаями, индуктивное доказательство, полученное из этого подтверждения, будет очень убедительным, поскольку надежды на опровержение как раз возлагались на предельные случаи. [21]
Особую роль сыграла работа Цермело [1], ознаменовавшая начало применения к изучению игр с полной информацией теоретико-множественного подхода. Его доказательство отличается от классического только тем, что полная индукция заменяется в нем трансфинитной. Поскольку индуктивное доказательство является также и конструктивным, нахождение ситуаций равновесия представляется не слишком затруднительным, если не считать технических сложностей, которые, однако, как в случае шахмат, могут оказаться существенными. [22]
Хотя все это интуитивно ясно и было сформулировано еще Гауссом, а возможно, и еще раньше, точные доказательства не столь очевидны. Лемма Шпернера позволяет доказывать приведенные утверждения с помощью некоторых арифметических выкладок. Помимо этого, она представляет собой образец изящной арифметизации, влияющей на развитие математики и позволяющей оценить могучую роль абстракции. Заметим, кстати, что первоначальная форма доказательства леммы Шпернера иллюстрирует следующую важную особенность доказательств по индукции. Иногда необходимо заменять утверждение, требующее доказательства, на более сильное, с тем чтобы доказывать его с помощью математической индукции. Впервые, насколько известно автору, эта мысль была высказана в публичной лекции Германом Вейлем. Так, в лемме Шпернера мы хотим показать, что некая конфигурация встречается по меньшей мере один раз, а в индуктивном доказательстве мы должны показать, что она встречается нечетное число раз. В индуктивных доказательствах существует следующая деликатная альтернатива. [23]
Хотя все это интуитивно ясно и было сформулировано еще Гауссом, а возможно, и еще раньше, точные доказательства не столь очевидны. Лемма Шпернера позволяет доказывать приведенные утверждения с помощью некоторых арифметических выкладок. Помимо этого, она представляет собой образец изящной арифметизации, влияющей на развитие математики и позволяющей оценить могучую роль абстракции. Заметим, кстати, что первоначальная форма доказательства леммы Шпернера иллюстрирует следующую важную особенность доказательств по индукции. Иногда необходимо заменять утверждение, требующее доказательства, на более сильное, с тем чтобы доказывать его с помощью математической индукции. Впервые, насколько известно автору, эта мысль была высказана в публичной лекции Германом Вейлем. Так, в лемме Шпернера мы хотим показать, что некая конфигурация встречается по меньшей мере один раз, а в индуктивном доказательстве мы должны показать, что она встречается нечетное число раз. В индуктивных доказательствах существует следующая деликатная альтернатива. [24]