о абстрактном и осязаемом и корне из двух
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}
no subject
Date: 2002-07-04 12:18 pm (UTC)Как насчет e**(ln(2)) = 2?
no subject
Date: 2002-07-04 12:37 pm (UTC)no subject
Date: 2002-07-04 12:44 pm (UTC)no subject
Date: 2002-07-04 01:07 pm (UTC)no subject
Date: 2002-07-04 02:00 pm (UTC)шёл в комнату, попал в другую
Date: 2013-02-04 02:51 pm (UTC)"Неконструктивное" доказательство, конечно, красиво, но есть и "явное", на школьном уровне, не ссылающееся при этом ни на Гельфонда, ни на другие сложные результаты. Тут, конечно, достаточно логарифмов типа log2(3), где иррациональность равносильна очевидному факту, что 2m не равно 3n (гораздо проще "корня из двух"!). А далее берём x=21/2, и возводим в степень y=2*log2(3), получая в итоге 3.
no subject
Date: 2002-07-04 12:54 pm (UTC)no subject
Date: 2002-07-04 01:06 pm (UTC)Сама теорема говорит что для любого конечного множества алгебраических чисел линейно независимых над полем рациональных чисел их экспоненты алгебраически независимы.
Я когда-то знал, как она доказывается.
Поправка-следует читать
Date: 2002-07-04 01:10 pm (UTC)no subject
no subject
Date: 2002-07-04 02:01 pm (UTC)no subject
Date: 2002-07-06 08:55 am (UTC)