о абстрактном и осязаемом и корне из двух
Jul. 4th, 2002 09:39 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaОчень люблю эту задачку за её неортодоксальное, поразительное своей красотой решение.
Задача: доказать, что существуют два иррациональных числа x и y, так, что xy (икс в степени игрек) - рациональное число.
Решение закрываю элжекатом, но если кто хочет сам подумать, не читайте эту запись дальше пока - в ней оно всё равно обсуждается.
Решение: обозначим sqrt(2) = корень из двух. Рассмотрим число X = sqrt(2)sqrt(2).
Одно из двух: либо X - рациональное число, либо иррациональное.
Если X - рациональное число, то sqrt(2) и sqrt(2) - два иррациональных числа, одно в степени другого дают рациональное, задача решена.
Если X - иррациональное число, то заметим, что X^sqrt(2) = (sqrt(2)sqrt(2))sqrt(2) = sqrt(2)2 = 2. Таким образом, X и sqrt(2) - два иррациональных числа, одно в степени другого дают рациональное - двойку. Задача решена.
Итак, что есть примечательного в этом решении? Мы доказали, что существуют такие иррациональные x и y, что xy - рациональное число. Но мы не показали ни одной такой пары x и y, вообще ни на шаг не приблизились к доказательству того, что вот эти конкретные x и y действительно представляют собой нужную пару.
В принципе понятно, конечно, что наше число X, по-видимому, иррациональное, и, возможно, есть способ это доказать (или нету ещё? я всё время путаюсь в том, что здесь уже умеют делать, а что нет -- кажется, иррациональность epi ещё не доказали, например?). Но в принципе можно себе представить ситуацию, при которой иррациональность или рациональность числа X в принципе были бы недоказуемы; это совсем маловероятно в данном случае, но в каком-нибудь несколько более сложном вполне могло бы такое произойти.
Но даже если бы в принципе невозможно было доказать, что X рационально или что X иррационально -- всё равно наше доказательство оставалось бы верным.
Казалось бы, чего особенного. Подумаешь, доказательство о существовании, не использующее конструктивного построения. Да на каждом шагу в математике. Возьми хоть существование базы у произвольного векторного пространства.
То, да не то. Существование базы требует "мощной" аксиоматической механики - аксиомы выбора. Она изначально и очевидно неконструктивна, затем и нужна. В случае нашей задачки никакой аксиомы выбора не требуется, конструктивность нарушается на гораздо более "примитивном", "осязаемом" уровне - это, может быть, и делает её столь интересной. Мы не привыкли к столь явному нарушению "осязаемости" в столь простых вещах. Нам хочется взять и "пощупать" руками наши x и y, но мы не можем.
Математик-интуиционист, последователь Брауэра, назвал бы наше доказательство неприемлемым, неверным. Проблема его не в том даже, что доказывается существование чего-то без того, чтобы привести конкретный пример. Принципы интуиционизма (а вслед за ним конструктивизма) допускают, например, конструктивные доказательства от обратного. Если бы мы предположили, что таких x и y не существует, и это предположение смогли бы конструктивным путём привести к противоречию - это было бы приемлемое с точки зрения строгого интуициониста доказательство.
Проблема в другом: в использовании принципа исключённого третьего без конструктивного его разрешения. Мы говорим: либо X рационально, либо нет. Для математика-интуициониста это утверждение имеет смысл только в том случае, когда мы можем собственно описать какую-то процедуру, позволяющую нам решить, рационально X или нет. Мы не можем разбить решение на два случая (соответствующие рациональности и иррациональности X), не давая при этом возможности решить, какой из них "в действительности" верен (и, более того, допуская, что этот вопрос в принципе может оказаться нерешаемым!).
Все эти претензии математика-интуициониста практических последствий не имеют, просто потому, что математиков-интуиционистов уже много лет как нет (а горстка конструктивистов никакой значительной роли не играет). В математике победил торжествующий платонизм, а интуиционизм изучается философами и логиками, но не используется в своей повседневной работе математиками. Я отнюдь не пытаюсь утверждать, что приведенное выше доказательство существования x и y действительно неверно или неприемлемо.
Но претензии эти, придирки гипотетического интуициониста на самом деле полезны: они помогают нам понять, что нам кажется странным, неординарным в этом доказательстве. Вот это, действительно, и кажется - это торжествующе-неконструктивное применение принципа исключённого третьего (который, напомню, гласит: "либо A, либо не-А"; "третьего" не дано).
В случае нашей задачки это скорее курьёз, забавная штука. Несколько по-другому выходит, когда речь заходит о теории вычислимости, алгоритмах, машинах Тюринга и т.п. Мне кажется, что там, или по крайней мере в философии вычислимости, вопрос конструктивности становится более релевантным, более неотложным.
Вот простой пример. Возьмём какой-то нерешённый математикой вопрос. Например:
Верно ли то, что любое чётное число может быть представлено в виде суммы двух простых чисел?
Обозначим утверждение любое чётное число может быть представлено в виде суммы двух простых чисел буквой G. Теперь спросим следующее:
1. Существует ли машина Тюринга (иными словами, алгоритм), который выдаёт на выходе 1, если гипотеза G верна, и 0, если она неверна?
Казалось бы, задать этот вопрос - всё равно, что спросить "можем ли мы решить G алгоритмическим путём?" Но выясняется что это не так. Оказывается, существует тривиальный положительный ответ на вопрос 1.:
Если G верна, то возьмём в качестве нашей машины Тюринга машину, которая пишет в качестве вывода 1 и останавливается.
Если G неверна, то возьмём в качестве нашей машины Тюринга машину, которая пишет в качестве вывода 0 и останавливается.
В любом случае, существует машина Тюринга, к-я пишет 1, если G верна, и 0, если G неверна.
Мы ощущаем, что такое "решение" является обманом, подлогом. Но почему? Что здесь происходит? Что не так?
Легко увидеть аналогию с доказательством задачки про иррациональные числа. Мы не знаем, верна G или нет. Но если она верна, то мы можем сделать так-то, а если неверна, то по-другому. В результате мы получаем вполне правильное доказательство существования искомой машины, которое, тем не менее, совершенно нас не устраивает.
Проблема в том, что мы отождествляем понятия "существует алгоритм, который делает X" и "мы можем решить X алгоритмическим путём". Вышеизложенный подлог как раз и показывает, что это одождествление неправомочно. Нам недостаточно знать о существовании алгоритма; нам нужно держать "в руках" сам алгоритм.
Нам нужно конструктивное доказательство того, что существует алгоритм, решающий проблему G, и только такое доказательство мы примем в качестве верного. Неконструктивное доказательство формально верно, но мы отметаем его как бесполезное, обманное. Ситуация здесь полностью противоположна ситуации с числами.
Но вот формально выразить это "держать в руках" оказывается делом непростым. С точки зрения формальной математики мы можем пользоваться квантором существования и всё. Не поможет и мета-переход внутри самой теории вычислимости, хотя на первый взгляд он мог бы быть полезен. Мы могли бы попробовать сказать следующее: мы можем алгоритмически решить проблему G если не просто существует машина Тюринга, дающая на неё правильный ответ, а кроме того, существует другая машина Тюринга, эту первую машину правильно распознающая: говорящая нам, когда мы имеем дело с ней, а когда с какой-то другой машиной, G не решающей. Но увы, этот трюк только отодвигает некоструктивность на один уровень выше: тогда эта самая мета-машина будет существовать, но будет разной в зависимости от того, верна G или нет.
Возможно, действительно стоит попробовать подойти к теории вычислимости с точки зрения интуициониста, возможно, даже с формальным набором интуиционистской логики и методологии. Действительно ли это поможет? не знаю, и, честно говоря, сомневаюсь. Но что тогда вместо этого?
Над этим вопросом - конструктивизма в теории вычислимости, над тем, что означает в разных контекстах задать алгоритм, над разницей между существованием и "держанием в руках" - я размышляю уже больше года (не всё время, конечно - время от времени), в разных аспектах и под разными углами. Время от времени мне кажется, что я вижу что-то, какой-то многообещающий подход, нечто интересное, позволяющее подойти к этой проблеме несколько по-другому... но ни разу ничего конкретного мне получить так и не удалось.
Задача: доказать, что существуют два иррациональных числа x и y, так, что xy (икс в степени игрек) - рациональное число.
Решение закрываю элжекатом, но если кто хочет сам подумать, не читайте эту запись дальше пока - в ней оно всё равно обсуждается.
Решение: обозначим sqrt(2) = корень из двух. Рассмотрим число X = sqrt(2)sqrt(2).
Одно из двух: либо X - рациональное число, либо иррациональное.
Если X - рациональное число, то sqrt(2) и sqrt(2) - два иррациональных числа, одно в степени другого дают рациональное, задача решена.
Если X - иррациональное число, то заметим, что X^sqrt(2) = (sqrt(2)sqrt(2))sqrt(2) = sqrt(2)2 = 2. Таким образом, X и sqrt(2) - два иррациональных числа, одно в степени другого дают рациональное - двойку. Задача решена.
Итак, что есть примечательного в этом решении? Мы доказали, что существуют такие иррациональные x и y, что xy - рациональное число. Но мы не показали ни одной такой пары x и y, вообще ни на шаг не приблизились к доказательству того, что вот эти конкретные x и y действительно представляют собой нужную пару.
В принципе понятно, конечно, что наше число X, по-видимому, иррациональное, и, возможно, есть способ это доказать (или нету ещё? я всё время путаюсь в том, что здесь уже умеют делать, а что нет -- кажется, иррациональность epi ещё не доказали, например?). Но в принципе можно себе представить ситуацию, при которой иррациональность или рациональность числа X в принципе были бы недоказуемы; это совсем маловероятно в данном случае, но в каком-нибудь несколько более сложном вполне могло бы такое произойти.
Но даже если бы в принципе невозможно было доказать, что X рационально или что X иррационально -- всё равно наше доказательство оставалось бы верным.
Казалось бы, чего особенного. Подумаешь, доказательство о существовании, не использующее конструктивного построения. Да на каждом шагу в математике. Возьми хоть существование базы у произвольного векторного пространства.
То, да не то. Существование базы требует "мощной" аксиоматической механики - аксиомы выбора. Она изначально и очевидно неконструктивна, затем и нужна. В случае нашей задачки никакой аксиомы выбора не требуется, конструктивность нарушается на гораздо более "примитивном", "осязаемом" уровне - это, может быть, и делает её столь интересной. Мы не привыкли к столь явному нарушению "осязаемости" в столь простых вещах. Нам хочется взять и "пощупать" руками наши x и y, но мы не можем.
Математик-интуиционист, последователь Брауэра, назвал бы наше доказательство неприемлемым, неверным. Проблема его не в том даже, что доказывается существование чего-то без того, чтобы привести конкретный пример. Принципы интуиционизма (а вслед за ним конструктивизма) допускают, например, конструктивные доказательства от обратного. Если бы мы предположили, что таких x и y не существует, и это предположение смогли бы конструктивным путём привести к противоречию - это было бы приемлемое с точки зрения строгого интуициониста доказательство.
Проблема в другом: в использовании принципа исключённого третьего без конструктивного его разрешения. Мы говорим: либо X рационально, либо нет. Для математика-интуициониста это утверждение имеет смысл только в том случае, когда мы можем собственно описать какую-то процедуру, позволяющую нам решить, рационально X или нет. Мы не можем разбить решение на два случая (соответствующие рациональности и иррациональности X), не давая при этом возможности решить, какой из них "в действительности" верен (и, более того, допуская, что этот вопрос в принципе может оказаться нерешаемым!).
Все эти претензии математика-интуициониста практических последствий не имеют, просто потому, что математиков-интуиционистов уже много лет как нет (а горстка конструктивистов никакой значительной роли не играет). В математике победил торжествующий платонизм, а интуиционизм изучается философами и логиками, но не используется в своей повседневной работе математиками. Я отнюдь не пытаюсь утверждать, что приведенное выше доказательство существования x и y действительно неверно или неприемлемо.
Но претензии эти, придирки гипотетического интуициониста на самом деле полезны: они помогают нам понять, что нам кажется странным, неординарным в этом доказательстве. Вот это, действительно, и кажется - это торжествующе-неконструктивное применение принципа исключённого третьего (который, напомню, гласит: "либо A, либо не-А"; "третьего" не дано).
В случае нашей задачки это скорее курьёз, забавная штука. Несколько по-другому выходит, когда речь заходит о теории вычислимости, алгоритмах, машинах Тюринга и т.п. Мне кажется, что там, или по крайней мере в философии вычислимости, вопрос конструктивности становится более релевантным, более неотложным.
Вот простой пример. Возьмём какой-то нерешённый математикой вопрос. Например:
Верно ли то, что любое чётное число может быть представлено в виде суммы двух простых чисел?
Обозначим утверждение любое чётное число может быть представлено в виде суммы двух простых чисел буквой G. Теперь спросим следующее:
1. Существует ли машина Тюринга (иными словами, алгоритм), который выдаёт на выходе 1, если гипотеза G верна, и 0, если она неверна?
Казалось бы, задать этот вопрос - всё равно, что спросить "можем ли мы решить G алгоритмическим путём?" Но выясняется что это не так. Оказывается, существует тривиальный положительный ответ на вопрос 1.:
Если G верна, то возьмём в качестве нашей машины Тюринга машину, которая пишет в качестве вывода 1 и останавливается.
Если G неверна, то возьмём в качестве нашей машины Тюринга машину, которая пишет в качестве вывода 0 и останавливается.
В любом случае, существует машина Тюринга, к-я пишет 1, если G верна, и 0, если G неверна.
Мы ощущаем, что такое "решение" является обманом, подлогом. Но почему? Что здесь происходит? Что не так?
Легко увидеть аналогию с доказательством задачки про иррациональные числа. Мы не знаем, верна G или нет. Но если она верна, то мы можем сделать так-то, а если неверна, то по-другому. В результате мы получаем вполне правильное доказательство существования искомой машины, которое, тем не менее, совершенно нас не устраивает.
Проблема в том, что мы отождествляем понятия "существует алгоритм, который делает X" и "мы можем решить X алгоритмическим путём". Вышеизложенный подлог как раз и показывает, что это одождествление неправомочно. Нам недостаточно знать о существовании алгоритма; нам нужно держать "в руках" сам алгоритм.
Нам нужно конструктивное доказательство того, что существует алгоритм, решающий проблему G, и только такое доказательство мы примем в качестве верного. Неконструктивное доказательство формально верно, но мы отметаем его как бесполезное, обманное. Ситуация здесь полностью противоположна ситуации с числами.
Но вот формально выразить это "держать в руках" оказывается делом непростым. С точки зрения формальной математики мы можем пользоваться квантором существования и всё. Не поможет и мета-переход внутри самой теории вычислимости, хотя на первый взгляд он мог бы быть полезен. Мы могли бы попробовать сказать следующее: мы можем алгоритмически решить проблему G если не просто существует машина Тюринга, дающая на неё правильный ответ, а кроме того, существует другая машина Тюринга, эту первую машину правильно распознающая: говорящая нам, когда мы имеем дело с ней, а когда с какой-то другой машиной, G не решающей. Но увы, этот трюк только отодвигает некоструктивность на один уровень выше: тогда эта самая мета-машина будет существовать, но будет разной в зависимости от того, верна G или нет.
Возможно, действительно стоит попробовать подойти к теории вычислимости с точки зрения интуициониста, возможно, даже с формальным набором интуиционистской логики и методологии. Действительно ли это поможет? не знаю, и, честно говоря, сомневаюсь. Но что тогда вместо этого?
Над этим вопросом - конструктивизма в теории вычислимости, над тем, что означает в разных контекстах задать алгоритм, над разницей между существованием и "держанием в руках" - я размышляю уже больше года (не всё время, конечно - время от времени), в разных аспектах и под разными углами. Время от времени мне кажется, что я вижу что-то, какой-то многообещающий подход, нечто интересное, позволяющее подойти к этой проблеме несколько по-другому... но ни разу ничего конкретного мне получить так и не удалось.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Re:
Date: 2002-07-04 02:45 pm (UTC)Ну как, X ведь является частью решения.
Вы видите в этом какую–то тонкость (математическую или философскую) которую я не улавливаю, сколько я не перечитываю.
Философскую, несомненно. У нас есть утверждение: "Либо X рационально, либо X иррационально". Это утверждение есть пример принципа исключённого третьего. В данном случае, однако, интуиционизм запрещает использовать такое утверждение внутри доказательства, если у нас нет никакого эффективного способа решить, какая из двух альтернатив имеет место.
Далее, как следствие применения этого принципа в данном случае, наше доказательство получается неконструктивным. Мы знаем, что есть x и y, но не знаем, какие они; может быть, sqrt(2) и sqrt(2), а может быть, X и sqrt(2). Это очень люпобытный случай локализованной неконструктивности. Сравните его, например, с двумя разными доказательствами существования иррациональных чисел вообще:
1. Берём sqrt(2), доказываем, что оно иррационально, всё.
2. Пересчитываем рациональные числа - их алеф-0, а всех действительных 2^алеф-0, поэтому должны быть иррациональные.
Второе док-во неконструктивно (не даёт нам ни одного иррационального числа). Но это более привычный вид неконструктивности, нежели в случае X. Вот если бы док-во выглядело так: мы находим два числа a и b, и доказываем что одно из них обязано быть иррациональным, но мы не знаем точно, какое из двух - это было бы похожим на случай с X. Но такое вообще редко встречается.
no subject
Date: 2002-07-04 03:22 pm (UTC)Я видимо очень математически толстокожий человек, т.к. ощущаю одинаковый комфорт от доказательств 1 и 2. На вопрос ответил: "иррациональные числа –– их есть," и ушел.
Я даже не подозревал, что неконструктивные доказательства чем–то хуже (или необычней) конструктивных.
Фразу "могу доказать что оно есть, но я его не знаю" произношу без дрожи в голосе.
Также спокойно как и фразу "решение этой задачи –– А или Б, и ничто другое; но А оно или Б –– об этом математики еще не додумались, так как не знают верно ли заявление ХХХ" если я "вижу", что заявление ХХХ (например, "число Х –– рационально") никаких "геделевских" проблем не создает. А если ХХХ создает "геделевские" проблемы, то и сама задача сводится к неразрешимости (будь ты хоть конструктивист, хоть интуитивист, хоть кто).
Ну и что же мне эти проклятые интуитивисты запретить хотят?:)
Re:
Date: 2002-07-04 03:34 pm (UTC)То, что у Вас не возникает никаких проблем от неконстурктивных доказательств, всего лишь говорит о том, что Вы - платонист. Ну и ладно, я тоже платонист. Вообще почти все действующие сегодня математики тоже платонисты (обычно наивные, т.е. не задумывающиеся об этом). Для меня тоже 2 вполне нормально док-во. Я ощущаю разницу между 2 и 1, но не в том смысле, чтобы считать 2 худшим или неверным, а только для изучения разных видов доказательств, для мета-математических целей.
Но во второй части моей записи, мне кажется, я привёл достаточно убедительный случай, когда это действительно оказывается важным - пример неконструктивного "алгоритма", который мы интуитивно не воспринимаем в качестве "правильного" решения. Т.е. волей-неволей нам приходится, если мы хотим понять, откуда берутся такие случаи, вернуться к конструктивистской терминологии и, в частности, проводить различие между "существованием алгоритма" и "нашим знанием алгоритма".
Мне так, по крайней мере кажется. Я не убеждён в том, что я прав. Но в любом случае это не просто исторический дискурс в интуиционизм, а попытка понять философские аспекты некоторых ситуаций, которые (в теории вычислимости и алгоритмов) обычно игнорируют или заметают под ковёр.