Предпочтительное определение функции в курсе логики

[Alexey Romanov]

Моя исходная посылка: определения должны быть такими, чтобы их было удобнее использовать; в частности, формулировки теорем должны получаться как можно проще и иметь меньше оговорок. Когда я читал новую книгу Gallier, Discrete Mathematics: Some Notes, я обратил внимание, что он вводит как основное определение частично определённую функцию (то есть функция $f: X \to Y$ у него не обязательно всюду определена на $X$). Что это даёт (например):

1) Большая симметричность.
2) Обратная функция есть у любого вложения, а не только у биекций.
3) $|X| \leq |Y|$ тогда и только тогда, когда есть сюръекция из $Y$ в $X$ (не нужно оговорки, что $X$ непусто).
4) Ближе к функциям в программировании, вычисление которых может зациклиться. В частности, мы можем сказать, что любая чистая (то есть не имеющая побочных эффектов, не обращающаяся к внешнему состоянию и т.д.) функция на языке программирования вычисляет какую-то математическую функцию.
5) Когда дойдём до общерекурсивных функций, не придётся оговариваться, что это не "настоящие" функции, а частично определённые.

Какие есть причины предпочитать традиционное определение? Какие формулировки ухудшаются?

[migmit]

Alexey Romanov в сообщении #303420 писал(а):

1) Большая симметричность.

Симметричность дают бинарные отношения. Функции для того и созданы, чтобы быть НЕсимметричными.

Alexey Romanov в сообщении #303420 писал(а):

2) Обратная функция есть у любого вложения, а не только у биекций.

Что вы понимаете под "обратной" функцией? По-моему, функция $g$ является обратной к функции $f$, если как $f\cdot g$, так и $g\cdot f$ являются тождественными функциями. В вашем случае это, очевидно, не так.

Alexey Romanov в сообщении #303420 писал(а):

Ближе к функциям в программировании, вычисление которых может зациклиться.

В программировании как раз гораздо удобнее рассматривать не частично определённые функции, а непрерывные функции из домена в домен. Не нужно волноваться на тему "определена ли функция в этой точке" - да, определена, но её значение может быть равно (_|_). Это означает, что мы по-прежнему можем, например, подставлять это значение в какие-либо формулы, и т.п.

Alexey Romanov в сообщении #303420 писал(а):

Когда дойдём до общерекурсивных функций, не придётся оговариваться, что это не "настоящие" функции, а частично определённые.
Какие есть причины предпочитать традиционное определение? Какие формулировки ухудшаются?

Да почти все. На каждом шагу придётся спотыкаться и оговаривать "всюду определённая".

[AD]

Переношу в вопросы преподавания.

[Alexey Romanov]

(Оффтоп)

AD в сообщении #304788 писал(а):

Переношу в вопросы преподавания.

Спасибо, об этом подфоруме не знал.

-- Ср мар 31, 2010 13:05:32 --

migmit в сообщении #303904 писал(а):

Симметричность дают бинарные отношения. Функции для того и созданы, чтобы быть НЕсимметричными.

Полной симметричности тут и не будет. Но в общем, согласен

migmit в сообщении #303904 писал(а):

Что вы понимаете под "обратной" функцией? По-моему, функция $g$ является обратной к функции $f$, если как $f\cdot g$, так и $g\cdot f$ являются тождественными функциями. В вашем случае это, очевидно, не так.

Да, согласен.

migmit в сообщении #303904 писал(а):

В программировании как раз гораздо удобнее рассматривать не частично определённые функции, а непрерывные функции из домена в домен. Не нужно волноваться на тему "определена ли функция в этой точке" - да, определена, но её значение может быть равно (_|_). Это означает, что мы по-прежнему можем, например, подставлять это значение в какие-либо формулы, и т.п.

В логике это даёт свои проблемы. См., например, свободную логику, "Adapting Calculational Logic to the Undefined", и т.д.

migmit в сообщении #303904 писал(а):

Да почти все. На каждом шагу придётся спотыкаться и оговаривать "всюду определённая".

Вот мне и интересно, насколько "на каждом шагу".

[Профессор Снэйп]

На самом деле все эти "спотыкания" есть следствия неудачности русского языка. В англоязычной литературе используют термин "computable function" для вычислимой функции, возможно, не всюду определённой, и термин "total computable function" для всюду определённой вычислимой функции. Английскому языку в этом плане повезло: прилагательное "total" короткое и легко произносится, в отличие от русского "всюду определённая".

Если изучать теорию алгоритмов, то есть темы, где функции, в основном, всюду определены, а есть темы, где они, в основном, частичные. Какую терминологию не задай, в одном из случаев "спотыкания" неизбежны: либо в первой группе тем к каждой функции придётся прибавлять "всюду определённая", либо во второй группе тем придётся всё время говорить "частичная". Выход простой: в начале лекции (главы в книжке) делается заявление: сегодня мы под "функцией" будем понимать всюду определённую/частичную функцию, если термин "функция" будет использоваться в другом смысле, то это будет оговорено отдельно. И дальше шпаришь, не спотыкаясь

P. S. Частичная функция есть всюду определённая функция на своей области определения

[ewert]

Профессор Снэйп в сообщении #305841 писал(а):

Английскому языку в этом плане повезло: прилагательное "total" короткое и легко произносится, в отличие от русского "всюду определённая".

А почему не заменить слово "total" на, скажем, столь же короткое слово "вполне"? (я не в теме, потому и спрашиваю, сильно не пинайте)

[Alexey Romanov]

ewert в сообщении #305845 писал(а):

А почему не заменить слово "total" на, скажем, столь же короткое слово "вполне"?

То есть вместо "f -- всюду определённая функция из $\mathbb N$ в $\mathbb N$" Вы предлагаете говорить "f -- вполне функция из $\mathbb N$ в $\mathbb N$"? Хм. А вот "f -- полная функция из $\mathbb N$ в $\mathbb N$" звучит, по-моему, прилично.

[ewert]

Там совсем не та пара.

Речь шла о том, что "computable function" -- это, дескать, "вычислимая функция".

Ну а тогда "total computable function" -- это... ну, допустим, "вполне вычислимая функция", почему бы и нет?...

Ну или, скажем, "абсолютно вычислимая функция" (я просто перебираю возможные более-менее синонимы к слову "total").

(если, конечно, эти термины ещё не заняты; я просто не в курсе)

[Профессор Снэйп]

В данном контексте, наверное, можно говорить "всюду вычислимая функция".

Вообще все эти вопросы, касающиеся терминологии, слегка надуманы

[Maslov]

Профессор Снэйп в сообщении #305879 писал(а):

В данном контексте, наверное, можно говорить "всюду вычислимая функция".

+1
В английском языке в названии total computable function прилагательное total относится, скорее, к function, чем к computable. Другими словами, дословный перевод -- "всюду определенная вычислимая функция".

(Оффтоп)

Забавнее получилось при переводе с английского с обще-рекурсивными и частично-рекурсивными функциями. В оригинале они называются "general recursive function" (общая рекурсивная функция) и "partial recursive function" (частичная рекурсивная функция). Каким образом при переводе прилагательные "общая" (всюду определенная) и "частичная" (не всюду определенная) отклеились от слова "функция" и приклеились к слову "рекурсивная" остается загадкой. В результате некоторых (*смотрится в зеркало*) долгое время мучил вопрос: чем частичная рекурсия отличается от общей.

[Профессор Снэйп]

Maslov в сообщении #305889 писал(а):

В английском языке в названии total computable function прилагательное total относится, скорее, к function, чем к computable. Другими словами, дословный перевод -- "всюду определенная вычислимая функция".

В точности так. "Total function" --- всюду определённая функция.

Maslov в сообщении #305889 писал(а):

Забавнее получилось при переводе с английского с обще-рекурсивными и частично-рекурсивными функциями. В оригинале они называются "general recursive function" (общая рекурсивная функция) и "partial recursive function" (частичная рекурсивная функция). Каким образом при переводе прилагательные "общая" (всюду определенная) и "частичная" (не всюду определенная) отклеились от слова "функция" и приклеились к слову "рекурсивная" остается загадкой. В результате некоторых (*смотрится в зеркало*) долгое время мучил вопрос: чем частичная рекурсия отличается от общей.

Ага! А ещё сейчас многие студенты не понимают разницы между "рекурсивной функцией" и "общерекурсивной функцией". К сожалению, в некоторых учебниках эти вещи перепутаны