Божественные натуральные числа

[filin]

Преамбула. Среди математиков гуляет крылатая фраза "Бог создал натуральные числа, остальное - дело рук человека". На самом деле, если википедия и словарь немецкого нам не врут, то Кронекер сказал про целые, а не натуральные, и рук там тоже не было (что логично, остальную математику человек создал по большей части не руками).

Амбула. Предположим, что Бог действительно создал натуральные или целые числа. Из соображений божественности :) понятно, что все-таки натуральные, а не целые, отрицательное число отчетливо небожественно. Таки у меня к вам два вопроса.

1. Какую именно структуру создал Бог?

2. Ноль входит?

Понятно, что натуральные числа можно задавать разными способами. Понятно, что просто натуральный ряд, без операций, Бог не создавал, смысла нет. Понятно, что, скажем, вычитание и деление не входят (множество натуральных чисел относительно них не замкнуто). Очевидно, что и, скажем, факториал тоже придуман людьми. А какие операции божественны?

Я ставлю на: единицу (ноль не входит), следующее число (AKA +1), и... а вот что "и"? В основаниях математики тут используют рекурсию. Но рекурсия - понятие, мягко говоря, недетской сложности, его в школе до сих пор фактически не дают. Даже в вузах проходят построение целых чисел, рациональных, предела, действительных, производной, интеграла, и с легкостью доходят до гребеней математической статистики, рекурсию даже не упомянув. Между тем сложение детям, если объясняют, то объясняют по сути через примитивную рекурсию... Хотя нет, через итерацию. Через разворачивание числа в последовательность. Умножение тоже так вводят. "... и понятие последовательности"?

Comments

[aywen]

Так Бог-то не обязан создавать только простые понятия.
Ну и кстати, я бы включала ноль.
И вычитание и деление - как инструменты.
Ну как руки человеку даны Богом, а то, что человек руками делает - уже создано человеком считается.

[filin]

Я включаю ноль в натуральные числа, когда работаю с ними, но мне все же представляется (и история математики это подтверждает), что ноль - человеческое изобретение. Так же как вычитание и деление, только ноль на самом деле куда изощреннее. Потому что при счете реальных предметов числа, большие нуля, имеют естественную размерность (одно яблоко само по себе задает размерность "яблоки", а не "крокодилы"), а ноль - не имеет.

А уж вычитание и деление, как обратные операции, однозначно созданы человеком. Но я на самом деле считаю, что и умножение тоже. Вот за сложение не поручусь.

[slobin]

Рандомные мысли по поводу:

(1) "Бог создал натуральные числа, остальное -- дело рук человека" (якобы Кронекер), "Итерация свойственна человеку, рекурсия божественна" (якобы Дойч). Отметим разные модели: в первой Бог начинает, а дальше человек сам справляется, а во второй -- Бог продолжает с того места, где человек уже не справляется.

(2) Есть у меня богохульное подозрение, что ноль был ДО того, как Бог создал натуральные числа. Ну или, немножко поиграв словами, ноля НЕ БЫЛО до того, как он создал что-бы то ни было. "Не быть" -- определяющее свойство нуля.

(3) А чисто практически у меня на эту тему давно уже ориджин есть. Сейчас нагло руками подставлю, случайно он вряд ли выпадет. И вообще, хочу нормальный общесистемный (общескриптовый?) язык, где нумерация с единицы. Потому что задолбало писать не то, что думаешь! Смолтоллк и луа по разным причинам не годятся. Что-то вроде MATLAB, из которого выкинули большую часть математики и взамен добавили нормальные библиотеки в стиле питона. Может быть, Джулия в эту сторону разовьётся, посмотрим.

(4) Update: мне кажется, определяющим содержательным свойством "счёта" является то, что предметы можно считать в разном порядке, и ответ сойдётся. Нет, это не коммутативность сложения (сложение мы ещё не ввели), а что? И да, я неявно предроложил, что "натуральные числа" == "счёт".

... Натуральный ряд начинается с единицы ...

[vladimir000]

> Есть у меня богохульное подозрение, что ноль был ДО того, как Бог создал натуральные числа.

И был Бог единица, и было false нулем? :)))

[filin]

(1) Гм... Бог таки создал рекурсию, "естественную как дыхание", но понял, что человек не справляется, и пришлось вводить итерацию?

(2) Но как только Бог что-то создал, нуля не стало. И его пришлось создавать заново уже человеку. Потому что пропало абсолютно нулевое состояние "ничего нет". А для утилитарных целей пришлось вводить искусственно привнесенную размерность, не свойственную имманентно нулю. Теперь может быть ноль яблок (яблоки нас интересуют), но то же самое состояние соответствует и нулю крокодилов, а крокодилы нас не интересуют... А одно яблоко не может быть одновременно и одним крокодилом. Хотя, конечно, может быть одним фруктом, и еще много чем одним, но у одного яблока есть, гм, естественная (в смысле восприятия человеческой психикой) размерность. А у нуля яблок ее нет, ее приходится вводить искусственно, воображать, а не воспринимать.

(4) Да, натуральные числа идут от счета, и да, с определяющим свойством ты прав. Что, пожалуй, приводит нас к божественности сложения - именно в этой операции как сущности выражено это свойство.

[slobin]

А поскольку "естественная" размерность в глазах смотрящего (с одной стороны, яблоко, но не фрукт, а с другой -- дерево, но не яблоня), то от нуля яблок переходим к нулю антоновок, и далее к нулю яблок, на которых я вырезал сердечко в честь дня святого Валентина. Дальнейшая история здесь (ключевая фраза -- последняя в третьем абзаце). На всякий случай, если мы считаем по разному: "A list of no 2s differs from a list of no 3s!"

... Асимметричный дуализм языкового знака ...

[filin]

> А поскольку "естественная" размерность в глазах смотрящего

Тем не более, в ней есть некоторая корреляция, на которой основана возможность взаимодействия между особями. Как правило, интерпретация одного яблока как одной антоновки или одного фрукта - это уже искусственное действие, причем чаще твой собеседник воспримет ее как троллинг, чем как специфический подход к задаче. При том, что "яблоко" - это само по себе уже довольно сильная абстракция. Но - естественная.

Ты никогда не обращал внимания на байки того типа, что дети на начальной стадии обучения арифметике довольно хорошо складывают антоновки с грушевками, а вот яблоки с апельсинами - плохо? Они правы. Они еще не оторвались от жизни, а в жизни я не могу придумать неизвращенную задачу, в которой было бы все равно, что у тебя есть - 5 яблок или 2 яблока и 3 апельсина. Задачу, в которой не все равно, антоновка у тебя или грушевка, могу, но во всех, что придумываются, в принципе годятся обе, только если уделять внимание сорту, то результат будет лучше. Ну там, в шарлотку лучше антоновку, а в варенье грушевку.

А вот к нулю любая размерность искусственна.

А так да, в строго типизированном языке, типа хаскеля, даже без явного объявления типов нельзя объединить пустой список целых с пустым списком символов. Хотя обозначать их одной константой при этом можно :) Но глядя на одну эту константу саму по себе, ты не сможешь определить, пустой список чего это. Строго говоря, глядя на [1,2,3], ты тоже не сможешь сказать, [Int] это, [Double] или [Word8]. Но по крайней мере это будет список каких-то чисел, и числовые операции (тайпкласс Num) с ними будут давать ожидаемый результат. Ты можешь быть уверен, что foldr (+) 0 [1,2,3] тебе в любом случае выдаст 6, вне зависимости от контекста. А с [], не зная контекста, ты ничего сделать не можешь, кроме проверки на пустоту.

[slobin]

Да, перегрузка констант иногда поражает. Например, в Окамле вот такое типизируется:

Printf.printf "%s = %d\n" "magic" 42;;

Просто первая строчка в кавычках имеет тип не string, а, щас,

(string -> int -> unit, out_channel, unit) format

(мне пришлось немножко подумать, чтобы заставить интерпретатор это вывести). С монадами там не заморачиваются, с точки зрения ввода-вывода язык просто процедурный, но с типизацией там всё аккуратно. :-)

... На палатку падали чипы холода ...

[filin]

Если у него при этом форматная строка парсится компилятором и проверяется, что тип у нее действительно такой, то с его стороны это весьма любезно... Хотя по-хорошему, конечно, чтобы вывести, что там string -> int, а не text -> double, информации недостаточно. Впрочем, хаскель в подобной ситуации принудительно выберет String и Integer, глядя на константы.

Хаскельный Text.Printf.printf в этом смысле устроен хуже и кидается исключениями, если недодать параметров. Хотя форматная строка константная и можно было бы при компиляции проверить. И все наработки на эту тему, похоже в состоянии experimental...

[slobin]

C int и float в окамле тяжёлое историческое наследие -- они не полиморфны. Даже плавающие бинарные операции выглядят как +. -. *. /. Хотя в SML полиморфны (и стандарт не определяет точно, сколь широкий контекст должен посмотреть компилятор перед тем, как сдаться и признать его просто int'ом, а не float и не word). Но строки формата (ну то есть не строки), да, парсятся и проверяются. Начиная с какой-то версии их можно даже конкатенировать без потери этой проверки.

... Зачем мне ДВЕ шизофрении? ...

[vladimir000]

> Но рекурсия - понятие, мягко говоря, недетской сложности

Функция, как известно, от человека, а вот рекурсия...:)

Проблема в том, что без архимедовости возникают как системы над полями вычетов, так и "истинные" бесконечно малые числа:(

В общем, на мой вкус у бога нет другого выхода, как создавать полный эквивалент аксиоматики Пеано:)

[filin]

Вот я тут, комментируя ответ Кира, получил божественность сложения. Но не умножения.

Я не думаю, что аксиоматику. Бог создает, а значит, будет конструктивная система. Алгоритм построения, а не аксиомы свойств. Даже если имелось в виду создать систему, обладающую определенными свойствами, ключевое тут - создать, она не возникнет сама по себе из аксиоматики.

[vladimir000]

Да пофиг мне, что там Эру запретил:) Главное, что создаст он систему эквивалентную пеановской, а остальное - детали:)

[filin]

Дохтур, систему, эквивалентную пеановской, можно создать хмурой тучей различных способов, бесконечное множество из которых будут извращенными. Если я правильно помню, у самого Пеано, во-первых, сами числа, весь натуральный ряд, были данностью. Ему пофиг, у него аксиоматика, а не алгоритм. Я уверен, что в случае создания натурального ряда это не так, там как максимум 1 и 2, а скорее только 1. А остальные - строятся, и есть инструментарий для построения.

Кроме того, с одной стороны, я считаю, что у него изначально система более слабая, чем пеановская арифметика, ибо умножения нет. Не нужно. Пеановской нужно, без него нормального кодирования не построишь (хотя я не знаю, зачем Пеано ее строил, это у Геделя она используется для кодирования - но есть фрагменты только со сложением и только с умножением, и они действительно слабее полной, вплоть до чуть ли не линейной разрешимости). С другой стороны, зато в правилах развития нет ограничений, можно вводить новые операции и через них новые абстракции.

Так вот, мне, собственно, интересно, какие детали вложены в конструктор.

[elentin]

Раз. Я (как пидагох) разделяю такую нетривиальную точку зрения что чем раньше детям что-то расскажешь, тем легче им потом будет в старшей школе (ну, с определённого возраста, после 7 лет, мы же школьников обсуждаем, абстрактное мышлениедолжно появиться, младенчиков можно обсудить отдельно, тут я как раз против "раннего развития"). Ну, т.е. 1-2-классникам вполне можно рассказывать циклы, скажем, про это есть пара удачных учебников и среда программирования Пиктомир. Почему бы и не рекурсию шестиклассникам рассказать? (Могу спросить у коллег, которые более регулярно, чем я в последнее время, рассказывают что-то шестиклассникам - а и спрошу, пожалуй).

Два. Всякий, кого как-то учили формальной логике, по-моему, знает, что можно вот из чего числа соорудить: "сделать множество из того, что внутри" и "пустое множество". {}, {{}, {{}}}, {{}, {{}}, {{}, {{}}}} etc. - есть ли тут рекурсия?

И, да, про Кронекера мне как-то всегда казалось, что бог - натуральнве, а человек - всё остальное без уточнений, руками или чем-то ещё, ноя не заглядывала в оригинал.

[filin]

Ты вот Сэнту знаешь? Вот она жаловалась, что не понимает рекурсию. И натурально, не она одна. Нет, идею "позвать ту же функцию с другими параметрами" можно школьнику рассказать, и он ее прекрасно схватит. А вот идею, что первое, о чем надо думать - это о гарантии завершения, - уже нет. Я уж не говорю о разнице между примитивной и общей рекурсиями и отдельно - об особенности хвостовой рекурсии. В математике, правда, хвостовость традиционно несущественна, но даже в математике уже все-таки начали различать не только разрешимые и неразрешимые задачи, но и практически разрешимые, и считать хотя бы асимптотику глубины стека :)

Короче, рекурсия как математический аппарат требует куда более развитого абстрактного мышления, чем освоение умножения через сложение.

Два. Не всякий. Если формальной логике учили пятиклассника, то со связками и кванторами он обращаться научается довольно неплохо, а вот с идеей так строить числа освоится вряд ли. Ну и эта... Хорошо, построить ты так числа сможешь. А оперировать с ними? Ну-ка, сложи 2 и 2 в таком представлении...

Вот тут как раз Кир приводил другую цитату, про то, что итерация от человека, а рекурсия от бога. В смысле, требуется божественный уровень понимания...

Нутром чую понятие последовательности, но доказать не могу...

[slobin]

Мне в последнее время кажется, что все сложности в понимании рекурсии оттого, что завершение традиционно происходит в тот же самый момент, когда общий случай сводится к вырожденному. А это ("завершение" и "общий vs вырожденный") два разных понятия, которые мы таким образом успешно перемешиваем в головах. Мне кажется, что софизм "все лошади одинакового цвета" как раз на эксплойте этой трудности построен.

... Трудно быть багом ...

[filin]

Боюсь, что попытка совместить общий случай (т.е. никаких дополнительных условий) c завершением в один шаг приводит к общерекурсивному мю-оператору, т.е. к неразрешимой проблеме. А это неконструктивно.

А в примитивно-рекурсивном случае завершение происходит именно в частном случае (а нифига не вырожденном, кстати - антитезой общему случаю будет частный) и не может происходить иначе.

[slobin]

По-моему, проблема останова в рекурсивном случае не страшнее, чем в итеративном. Если вас смущает рекурсия, но не смущает ряд Коллатца (n := odd(n) ? 3n+1 : n/2)... ну я не знаю. А проблема, на мой взгляд, именно в том, что частный случай в программах, написанных понимающими рекурсию людьми, почему-то оказывается заодно и вырожденным. Ну, например... нет, не факториал. :-) Давайте определим ну хотя бы понятие "сумма n чисел". Для нормального человека простейший ("содержательный") частный случай -- это когда n=2. И сведение n=3 к n=2, n=4 к n=3 и так далее трудностей, по-моему, не вызывает. Но уже даже случай n=1 слегка нервирует, а уж n=0...

"Сумма ничего есть ничего" -- это игра слов, потому что произведение ничего равно единице, а чему равна конъюнкция ничего -- мне приходится каждый раз заново решать эту задачу в обратную сторону: чему она должна быть равна, чтобы применять рекурсию? Мне кажется, что если бы реальный код останавливался на n=2, то он был бы гораздо понятнее. Правда, у этого есть другая сторона: не факт, что он правильно работал бы при n=1 и n=0. А если и работал бы, то случайно. Я не знаю, что с этим делать.

P.S. В языке k (это такой потомок APL) пустых списков пять -- гетерогенный и четыре гомогенных по четырём базовым типам. Забавно, как они печатаются, какой вид автор считает "каноническим изображением": (), !0, 0#0.0, "" и 0#`

... Я купил за три рубля компилятор с паскаля ...

[filin]

Сумма ничего и произведение ничего используют единицу полугруппы, если она есть. Ну, левую или правую, если они различны, в зависимости от того, foldl там или foldr. Это как раз понятно. Но при этом в хаскеле им эту единицу надо указать явно (что заодно позволяет использовать у элемента списка и результата разные типы, и это порой вельми удобно). Но fold - он по жизни гораздо толще, чем просто суммирование последовательности.

Есть еще foldr1 и foldl1, которым единицу указывать не надо, но которые за это на пустом списке хряпаются. Как раз тот случай с естественной размерностью - посчитать яблоки можно только если есть хотя бы одно. На одноэлементном списке работают правильно. Вот они как раз соответствуют идее "сложить последовательность". Что тут важно. Одноэлементная последовательность считается валидной последовательностью в смысле данной задачи. Для нее понятие суммы поэтому приходится доопределять. После чего n=2 уже превращается из частного случая в общий. Хотя (снова в тему "первый-второй") одноэлементная последовательность - это таки да, вырожденная последовательность. (А пустая - совершенно вырожденная.) А так-то, естественным образом, говоря о сумме или произведении последовательности, нужно иметь хотя бы два элемента - операция-то бинарная.

Другое дело, что на самом деле задач суммирования последовательностей не бывает. На самом деле бывает только задача интегрирования, а это fold в чистом виде с явным заданием стартового значения, и да, с типом результата, на самом деле отличным от типа элемента последовательности, даже если случайно совпавшим (так, размерность факториала - количество перестановок, а его аргумента - количество элементов, яблоки и крокодилы). И именно по этой причине про foldr/foldl помнят все, а про foldr1/foldl1 напрочь забывают. Применений у них практически нет, а те, что есть - извращенные.

[p_govorun]

Рекурсия действительно не вмещается в человеческий мозг. Я только что сказал «рекурсия не вмещается в человеческий мозг -- и это действительно так». Предыдущее высказывание неверно, хотя и является высказыванием о верном высказывании.

Может ли первоклассник разобраться в предыдущем абзаце? Для этого ведь и взрослому придётся соответствующим образом вывернуть мозг.

[p_govorun]

Есть такая математическая операция, о которой математики не любят говорить. Если мы определяем 10 как 1+1+...+1 (10 раз) то мы должны уметь считать единицы. Без операции счёта нельзя даже определить умножение через многократное сложение.

То есть, Бог не просто создал (натуральные) числа, как абстрактные объекты -- он создал их пригодными для счёта.

[filin]

Да, разумеется, именно для счета. Но счет - это не структура, это приложение. Пригодность для счета - требуемое свойство. А какая конструкция ее обеспечивает?

Восприятию (скорее даже, самоосознанию) непосредственно доступны 1 (я) и как максимум 2 (я и ты или я и он). Недаром в примитивных языках, брешут, нет других числительных. Остальные числа - уже построение. Но пока еще божественное.

Я вот в защиту нумерации с 0 говорил, что в доступных мне языках порядковые числительные "первый" и "второй" с количественными "один" и "два" даже не однокоренные. Теперь доходит, почему. Потому что "первый" - это head последовательности, а "второй" - head (tail) (указание на то, что за головой там еще что-то есть, то есть, что рассматриваемый объект - таки последовательность), они к числам вообще никаким боком. А вот к операции построения натуральных чисел как раз имеют довольно прямое отношение, и вот когда мы начинаем зачем-то пересчитывать элементы последовательности, у нас и появляются "третий" и "четвертый" - это те, из которых мы строим 3 и 4.

[vladimir000]

В английском регулярность появляется с четвертого:)

[filin]

Что-то мне сдается, что third и three все-таки однокоренные. Перемещение звуков "и" и "р" с последующей модификацией произношения вполне в рамках.

[slobin]

Из этого можно сделать вывод (а можно и не делать :-), что правильное соответствие выглядит так:

x[0] - первый
x[1] - второй
x[2] - дватый
x[3] - третий
x[4] - четвёртый

и даже перевести эту хрень с английского на русский, потому что особенность эта, наверное, общеиндоевропейская, если не шире. Что я и сделал однажды. А система местоимений в "примитивных" языках -- это отдельная песня. Её надо начинать петь с "я -- Робинзон, ты -- Пятница", а потом постепенно переходить к "мы втроем с приятелями, но без тебя".

... Veni, vidi, evasi, narravi ...

[filin]

Лучше не делать. Третий - это с которым стало три. Если у тебя индексация с 42, то третий - это x[44]. Собственно, индексация с 0 и с 1 - это парадигмы "считать состояние перед" и "считать состояние после". Порядковые числительные, которые уже числительные, сформированы по второй парадигме, а индексацию массивов в компьютере действительно удобнее формировать по первой.

Хотя мне приходилось делать списковые структуры, где голова была управляющей, а данные начинались со второго элемента...

[slobin]

Наверное, я не понимаю нумерацию с нуля примерно так же, как Сента не понимает рекурсию. Нет, я вижу, что, скажем, кольцевой буфер получается компактнее, и даже сам так пишу, но всё равно не оставляет ощущение "фокуса". А от тождества a[:n]+a[n:]==a веет чем-то божественным (в смысле непостижимым). Но когда мне нужно разбить последовательность на три куска a[1..k-1], a[k] и a[k+1..n] ... ну вот, я, собственно, сформулировал задачу. Словами у меня получится дольше. А в счёт с нуля я это могу только оттранслировать.

... Неравенство строгое, но справедливое ...

[filin]

А для меня последовательность естественным образом разобьется на

splitAt (k-1), head и tail

но я думаю, что я даже буду переводить в splitAt k, head и tail

[slobin]

"я даже буду" непонятно. :-(

... Фиолетовая контрреволюция ...

[filin]

В смысле, увидев описание, где последовательность разбивается на 1..k-1, k и так далее, я преобразую его в 1..k, k+1 и так далее (или, если угодно, 0..k-1, k и так далее). Короче, буду откусывать первые k, а не k-1.

[p_govorun]

Такая вот идея: порядковые числа начинаются с нуля, а количественные -- с единицы. Скажем, на дороге десять километровых столбов, на начальном написано "0", на конечном - "9".

[slobin]

Вспомнилось при перечитывании: "это в соседнем магазине нет мяса, а в нашем магазине нет рыбы!".

... Потому что холодильник так устроен ...