«Хорошо определена» - означает, что указан явным образом способ, как по каждой паре натуральных чисел получить другое натуральное число соответствующее ей.
А способ и алгоритм здесь не одно и то же ? Насколько я понимаю, способ – это мысль, алгоритм – выражение этой мысли на языке. Т.к. передать мысль Вы можете только с помощью языка, то здесь их можно рассматривать как синонимы.
Это обычное устойчивое выражение. «Список» - означает, что существует биекция N на множество функций арифметики. Если такой биекции не существует, то и доказывыть вообще нечего – результат теоремы следует просто автоматически. Потому мы и предполагаем обратное - что всякую функцию можно запрограммировать, а потом показываем, что множество всех функций какого либо языка можно занумеровать (см. метод лексикографической сортировки) т.е. построить биекцию между N и функциями нашего языка. (тут надо бы добавить –«не просто занумеровать, а «эффективно занумеровать» - но на том уровне на котором мы пока разговариваем – этого вполне достаточно)
Честно говоря, мало что понял. Здесь есть что-то важное, или можно сразу читать дальше?
Нам начхать какой список мы возьмем, все списки равномощны друг другу и являют собой одно и тоже множество состоящее из одних и тех же элементов, они отличаются только порядком.
Конечно начхать, но взять какой-то список всё-равно надо. Вы же пишете программы, значит понимаете, что если вместо списка Вы в качестве аргумента попытаетесь использовать множество списков, компилер Вас просто отругает.
Но списков – ровно континуум, и каждый список дает по крайней мере одну функцию, которая не может быть записана на нашем языке, а потому, всех функций которые не могут быть записаны – тоже не менее континуума.
Не доказано. Это может оказаться и одна и та же функция.
А вот всего того, что можно написать не только на каком-то конкретном языке, но и вообще на всех языках, уже существующих и ещё не созданных – счетно. Но континуум и счетное множество не равномощны. А потому, существует подножество функций, равномощное R и такое, что ни одна из них не может быть запрограммирована никогда.(последние два тезиса предлагая Вам в качестве самостоятельного упражнения)
Про континуум и множество функций?
Но континуум и счетное множество не равномощны.
Континуум – это мощность множества действительных чисел. Т.е. здесь надо доказать, что действительных чисел больше, чем счётное множество. Та же самая диагонализация, только вместо значений функций – десятичные цифры, вместо аргументов – позиция цифры в числе.
А потому, существует подножество функций, равномощное R и такое, что ни одна из них не может быть запрограммирована никогда.
Странно, а разве это не то, что Вы давеча уже доказали? А я, вроде бы как, оспариваю это.
Оно не может быть «не так» - поскольку явным образом указано, «что именно» и «как».
Я усматриваю в этом противоречие. Поскольку у Вас в одном месте «явным образом указано, «что именно» и «как»», а в другом неявным указывается, что на входе есть список функций. Если же списка нет, то и funcn_k(x) нет, не определена. Можно было бы в качестве аргумента функции использовать константу. Например F(x,y) можно превратить в функцию одной переменной так – F(1,y). Но для этого нужно явно указать x=1. А Вам, соответственно, нужно указать конкретный список.
Это то и замечательно. Отсюда и следует, что раз разных H –у нас не менее континуума, то и разных G – у нас тоже не менее континуума. И не одна из них не может быть запрограммирована.
Э-э-э не так быстро. Из всех, сколько бы их ни было, нас интересует лишь одна, та которая построена для данного конкретного списка. Вы утверждаете, что функция определена, но не программируется. Я подозреваю, что функция не определена.
( Кстати Вам буква «G» – имя никакого ученого случайно не напоминает?).
Нет. Его имя напоминает мне буква о-умляут.
Вот для этого случая я заранее привел определение функции, Вам остается проверить, что именно это и имеет место.
Давайте проверим вместе, а то у меня не получается.
Как это «невыразима»? Функция ваша – определена плохо, потому, что не указана область её определения и область значения
Сам не понимаю как это получилось. Я же собирался написать, что это функция действительных чисел. А способа нет, это да. Поэтому, я считаю функция не определена.
Но сама функция –выразима в том смысле, что существует такой х, что х*х=-1,
Не х, а f(x). Функция, очевидно, равна константе, если бы справа стояло неотрицательное число.
Но вообще, то о чем я говорю в той теореме, когда говорю о выразимости - несколько больше, чем то что предпологаете видимо Вы.
Да, похоже. Никак не могу взять в толк, чем отличается выразимость от возможности построить алгоритм, вычисляющий значение с любой наперёд заданной точностью. (Ну, может быть, ещё и не дольше, чем за известное заранее количество времени.)
Какая система уравнений? Это Вас куда –то уже не туда понесло извините…
Ну одно уравнение. Собственно, его можно рассматривать как систему, состоящую из одного уравнения. Какая разница как назвать?
У нас и в помине нет никакой системы уравнений.
Ну как же нет? Если стоит знак равно, это разве не уравнение?
G(1) == A(1)+1, G(2) == B(2)+1 …– пока хорошо, но как только мы доходим до определённой точки – G(6) == F(6)+1, G(7) == G(7)+1 (!) - как видим, что если бесконечность не входит в наши числа, то система уравнений несовместна. Значит и функции такой G – нет.
Этого я, увы, вообще не понял.
Это гипотетический пример того, во что превращается выражение H(k,x)=funcn_k(x). Если конкретного списка нет, то он, как я писал ранее, должен быть аргументом функции H. Т.е. надо бы написать H(list, k, x) = func_list_k(x). Здесь же я предположил, что конкретный список уже указан. Тогда вместо func_list_k можно взять конкретные имена функций. Я заглянул в предполагаемый список и увидел, что они идут по алфавиту. А Ваша функция G фигурирует там под седьмым номером. То что Вы назвали определением представляет собой бесконечное множество выражений. По одному для каждого х. Для х==7 выражение G(7,7) = func_7(7)+1 превращается в G(7,7) = G(7,7)+1. В определении функции нельзя ссылаться на неё же. Поэтому я и написал, что это не определение, а система уравнений.
Подытаживая,
похоже разногласия у нас заключаются в том, что Вы считаете, что у Вас есть определение функции, а я считаю, что на самом деле там задаётся система уравнений. Похоже, всё сводится к этому.
PS. Насколько мне известно, в теории множеств было обнаружено какое-то противоречие (видимо, связано с бесконечными множествами). Теперь эта теория исправляется (как я надеюсь) или строится заново. Но, однако, после случившегося утвержения теории о бесконечных множествах уже не вызывают такого доверия как ранее. В любой момент может быть обнаружено и ещё какое-нибудь противоречие.
PPS. Истинность конечного множества высказываний может быть проверена простым перебором всех высказываний. Истинность счётного множества высказываний может быть установлена с помощью аксиомы мат. индукции. Собственно, её можно рассматривать как неявное обределение понятия «истина» для бесконечного множества высказываний. Есть ли соответствующий инструмент для континуума высказываний? Если нет, то мы даже не сможем математически строго проверить даже истинность простой формулы f1(x) == f2(x), ибо надо проверить целый континуум совпадений. В самой же формальной логике определения, что такое истинность континуума высказываний, нет, поскольку там когда создаются сложные высказывания, их составляющие перечисляются через запятую. Т.е. речь идёт не более, чем о счётном множестве. Более того, человеческая мысль (по всей видимости) не может представить себе континуум, а логика изучает мышление. В общем, о континууме логика и понятия не имеет. Исходя из этого, а также из предыдущего замечания, интересно было бы построить другую математику, такую, где нет множеств более, чем счётных.
Может быть, получится система более стройная и красивая, чем сейчас.
Скорей всего, кто-нибудь из мэтров уже высказывал подобные мысли, только выразил более строго.
Пожалуйста. Если есть вопросы – рад помочь интересующемуся человеку. (только я завтра улетаю в Москву, так шо сильно не торопитесь с вопросами)
:wink:
Ничего страшного. Продолжим после нового года. Главное запомнить, что мы на 10-й странице.
