Трансфинитная рекурсия и редукция.

ssz1977

Раскажите плиз об этих понятиях.
Или где можно прочитать о них?

Alexx13

Трансфинитную рекурсию можно определить например так:
1) h(x,o)=g(x)
2) h(x,n+1)=f(x,h(x,nn)
3) h(x,w)=sup{ h(x,k) : k<w }
здесь : n, k - ординалы, w - предельный ординал (типа омеги x - кортеж параметров, функции f,g,h принимают значения в частично-упорядоченном множестве.
Трансфинитная индукция - частный случай трансфинитной рекурсии.
Термин редукция встречается в лямда-исчислении. Барендрегт - автор бестеллеров по лямда-исчислению.
Можно также смотреть книги по (математической) логике.

ssz1977

Спасиб!

Alexx13

Оу! Пожалуйста.
Вы можете посмотреть более простые книжечки, для ознакомления (введения) в тему. А имено: про трансфинитную индукцию, упорядоченные множества, мощности (кардиналы) и порядковые числа (ординалы) просто и хорошим языком достаточно и немного по количеству страниц текста написано в 1ой главе Колмогоров, Фомин "Элементы теории функций и функционального анализа"; и есть ещё научно-популярная книжица: Виленкин "В поисках бесконечности".
П.С. Трансфинитная индукция из определения получается след. образом: х пусто, g(x) есть "истина" (константа 0, например, если алгебраически, в числах толковать функция f толкуется как импликация.
Вы всё легко и быстро поймёте (и даже гораздо больше, чем спрашивали если ознакомитесь с приведёнными книжечками. Это всё очень просто (не какой-нить дифгем с его дифференциальными тензорными полями на гладких многообразиях и философски интересно.

Xephon

по-моему, наиболее понятно написано в книге Верещагина и Шеня "Теория Множеств"

Alexx13

Есть ещё неплохая книжечка Архангельского "Теория множеств"

vitusi1

"Трансфинитная индукция - частный случай трансфинитной рекурсии."
Неверно.
Индукция - это МЕТОД ДОКАЗАТЕЛЬСВА с помощью указанных соотношений (см. выше).
Рекурсия - это МЕТОД ОПРЕДЕЛЕНИЯ (т.е. построения) некоторых объектов с помощью указанных соотношений.

vitusi1

Со своей стороны тоже очень советую книжечку Шеня-Верещагина
Оставить комментарий
Имя или ник:
Комментарий: